作业03
第一题
题目
已知一个数组中存放了一个字符串如：str[]=”abcdefg”;现根据字符串的内容建立一个单向链表，并输出该链表，然后把原链表逆转成一个新的链表，并输出逆转后的新链表。
node {
char data;
node *link
};
node *create_link(char a[]){}
void Out_link(node *head){}
node *reverse_link(node *head){}
思路
- 首先是根据字符串建立链表，我们直接一个一个取char数组的值，创建新的链表结点即可。
- 接着是反转链表，对于不到2个结点的情况，我们直接反转。对于>=2个结点的情况，我们可以创建三个指针指向连续的三个结点（第三个可以为NULL）。
将第二个指针的link指向第一个指针指向的结点，然后根据第三个指针所保存的信息（没有它就会与后面部分的链表断连），将这三个指针整体向后移动一位，直到全部反转完
源程序清单
#include<iostream>
using namespace std;
struct node {
char data;
node* link;
};
//这是根据字符串创建链表的函数
node* create_link(char a[]){
if (a[0] == '\0') return NULL;
node* head = new node;
head -> data = a[0]; head->link = NULL;
node* p = head, * q; //p:指向尾结点，q：创建新结点
int i = 1;
while (a[i] != '\0') {
q = new node;
q->data = a[i]; q->link = NULL; //建新结点
p->link = q; p = q; //处理旧结点
i++;
}
return head;
}
//这是根据传入的头结点输出链表的函数
void Out_link(node* head){
node* p = head;
while (p != NULL) {
cout << p->data << " -> ";
p = p->link;
}
cout << "\n";
}
//这是反转链表的函数
node* reverse_link(node* head)
{
if (head == NULL || head->link == NULL) return head; //不多于2个结点
node* left = head, * mid = head->link, * right = mid->link; //三个变量分别表示左中右结点（包含NULL）
head->link = NULL; //这里的head变成尾指针了
while (right != NULL) {
mid->link = left; //反转，将第二个指针指向的结点接到第一个指向的上面
left = mid; mid = right; right = right->link; //整体后移一位
}
mid->link = left; //最后right == NULL，所以还差最后两个结点没有接上去，此时mid为头结点
return mid;
}
int main() {
char s[] = "abcdefg";
node* head = create_link(s);
Out_link(head);
head = reverse_link(head);
Out_link(head);
return 0;
}
第二题（略）
题目
已知数据如下：
20 10 90 99 40 50 30 60 80 70
请写出分别用插入排序、选择排序、冒泡排序的、合并排序、快速排序的每趟处理后的数据清单。
第三题
题目
实现如下算法：以单链表为存储结构实现简单选择排序的算法。
链表结点结构： struct nofr {int data; nofe *link };
思路
- 首先，选择排序是找到某一段数据中的最小值，然后把它和开头元素交换。
- 如果是数组，我们可以直接用双重for循环做。到了链表这里，处理稍微有点麻烦，但是总体思路是一样的。
- 首先，我们需要一个指针指向“开头”，这个开头指未排好序的开头，便于与最小值交换（交换后就属于排好序的那部分了）。
既然要找到最小值，那么我们就要有一个指针能去遍历“开头”后面的结点；还得有一个指针去指向目前最小值的结点，便于比较和交换。 - 遍历完成后，将最小值与“开头”交换，然后将“开头”往后移动一位，就可以重复下去了。
源程序清单
#include <iostream>
using namespace std;
struct node {
int data;
node* link;
};
//选择排序
void selectionSort(node *head) {
node* p = head;//p用于往后遍历每一个元素
node* q = head; //q用于指向排好序的末尾的结点的后一个结点
node* t = head; //t用于指向最小元素
p = q->link;
while (q->link != NULL && p != NULL) {
t = q; //从q开始
while (p != NULL) { //往后遍历所有结点
if (p->data < t->data) { //如果找到了更小的元素
t = p;//t指向最小元素
}
p = p->link;//继续向后遍历
}//此时已经找到了最小的值所在的结点，由t指向
if (t != q) {//最小值在后面的话，就交换两个结点的值
/*int tem = t->data;
t->data = q->data;
q->data = tem;*/
swap(t->data, q->data);
}
q = q->link;//排好序后，更新末尾结点
p = q->link;//因为t指向q，所以p从q的下一个开始
}
}
//此函数用于创建随机单链表
node* createRandLink()
{
srand((unsigned int)time(NULL));
node* head = NULL, * p, * q;
int n = rand() % 20 - 10;
head = new node;
p = head;
p->data = n;
p->link = NULL;
for (int i = 1; i < 10; i++) {
q = new node;
q->data = rand() % 40 - 20; //随机数
q->link = NULL;
p->link = q;
p = q;
}
return head;
}
//此函数用于输出链表
void outPutLink(node *head) {
node* p = head;
while (p != NULL) {
cout << p->data << " -> ";
p = p->link;
}
cout << endl;
}
int main() {
node* head = createRandLink();
outPutLink(head);
selectionSort(head);
outPutLink(head);
}
第四题
题目
直接选择排序算法是不稳定的排序算法。这主要是由于每次从无序记录区选出最小记录后，与无序区的第一个记录交换而引起的，因为交换可能引起关键字相同的数据元素位置发生变化。如果在选出最小记录后，将它前面的无序记录依次后移，然后再将最小记录放在有序区的后面，这样就能保证排序算法的稳定性。编写一个稳定的直接选择排序算法。
思路
- 题目说得很清楚，直接将“替换”改为“后移”即可。
源程序清单
//int a[]为传入的数组，int n为数组长度
void dirSelSort(int a[], int n) {
int i = 0; //i用于指向排好序的末尾
int search = 1; //用于遍历后面的内容
int min = 0; //最小值位置
for (; i < n; i++) {
search = i + 1;
min = i;
while (search < n) {//找到最小值编号
if (a[search] < a[min]) {
min = search;
}
search++;
}//找到了最小值编号，跟search值无关了
//开始替换
int tem = a[min];
while (min > i) {
a[min] = a[min - 1]; //每一个都后移一位
min--;
}
a[i] = tem;
}
}
第五题
题目
实现自然二路归并排序算法，算法思想如下 ，从左到右扫描，扫描到二路已经有序的自然数据段，把扫描到的二路合并成一路有序的数据段，继续对后续的数据进行扫描，同样对二路有序数据合并成一路有序的，如最后只剩下一路有序的数据就照抄下来，这样经过一趟全部数据的合并后，整个数据更加有序了，不断重复上述过程，只到全部数据有序。
思路
- 这是自然归并排序算法(Natural Merge Sort)
- 最首先的，是要找到哪些数据片段是有序的。以升序为例，一段升序的数据的结束标志是它的下一个元素比它小。
- 所以，根据这个特点，我们可以生成一个数组，这个数组记录了这段数据中，每一处“前一个元素比后一个元素大”的位置。
比如，1 2 3 5 6 5 4 3 5 6 经过分组后，变成:
[1 2 3 5 6] [5] [4] [3 5 6]
而这个数组记录了每一组的开头的位置。 - 同时，我们知道归并排序的
merge()函数需要知道某一段数据的开头、中间、结尾位置，便于合并两段（下面的代码有写）。这个merge()函数与普通的归并排序函数一模一样，我们需要更改的，只是传入的开头、中间、结尾位置。 - 得到分组后，我们只需要合并前两个组，直到组数为1。这个过程中需要合并的总次数为
组数 - 1。
接第3点的例子，[1 2 3 5 6] [5] [4] [3 5 6] [1 2 3 5 5 6] [4] [3 5 6] [1 2 3 4 5 5 6] [3 5 6] [1 2 3 3 4 5 5 5 6 6] - 代码注释应该算是非常清楚了。
源程序清单
#include<iostream>
constexpr int N = 10; //数组长度
using namespace std;
//void printArr(int a[]) {
// for(int i =0; i < N; i++)
// cout << a[i] << " ";
// cout << "\n";
//}
//利用pos数组记录长度为a的数组的升序的“断掉的地方”，
//pos记录的是升序的起始位置，如果需要上一个组的结束位置，减一即可
//n是a 的长度
int getPos(int a[], int pos[]) {
int tem = 1; //pos要记录的下标从1开始
pos[0] = 0; //首先开头记录为0，因为第一个组的起始位置一定是0
for (int i = 0; i < N - 1; i++) {//注意此处的 n - 1 ，因为是i+1，防止越界！
if (a[i] > a[i + 1]) { //举例：1 2 3 5 0 1 2 3 中，从5到0就是个断点，此时5 > 0，记录好0的位置
pos[tem++] = i + 1;//记录非升序的部分，这样就可以分成多个升序的组，通过pos记录下标
}
}
return tem; //返回pos的尾标
}
//将数组a的beg到mid和mid+1到end的两组通过数组b合并到一起
void merge(int* a, int* b, int beg, int mid, int end) {
int i = beg, //i 是遍历前半部分数组，上限是mid
j = mid + 1, //j 是第二个数组起始的下标，上限是end
k = beg; //k 是遍历数组b，上限是end
while (i <= mid && j <= end) { //开始合并，i、j记录比较到这两半数组的哪里了
if (a[i] < a[j]) //看这两部分中，哪个值更小，如果a[i]更小就把它塞到b[k]里面去。
b[k++] = a[i++]; //++直接放在[]里，不用单独写，更简洁
else
b[k++] = a[j++]; //如果a[j]更小就把它塞到b[k]里面去。
}
while (i <= mid) b[k++] = a[i++]; //如果j到顶了，即后半部分全部塞进去了，那么前半部分直接按顺序填入即可
while (j <= end) b[k++] = a[j++]; //同理
for (i = beg; i <= end; i++)
a[i] = b[i];
//cout << "a= "; printArr(a); cout << "\n"; //debug
//cout << "b= "; printArr(b); cout << "\n"; //debug
}
//a[]:原始数组，b[]：临时数组
void mergeSort(int a[],int b[]) {
int pos[N]; //定义pos数组
int posLen = getPos(a, pos); //生成pos数组并获取其长度
//总需的merge次数为：组数（posLen） - 1。
for (int i = 0; i < posLen - 2; i++) { //排序
merge(a, b, pos[0], pos[i + 1] - 1, pos[i + 2] - 1);
//cout << "a merge = "; printArr(a); cout << "\n"; //debug
}//这个过程完毕后，还会剩下最后两个组
merge(a, b, pos[0], pos[posLen - 1] - 1, N - 1); //合并最后的2组
}
int main() {
int a[N] = {1, 2, 3, 0, 1, 0 ,5 ,6, 5, 4}; //分成5组
int b[N];
mergeSort(a, b);
for (int i : a) cout << i << " ";
}
第六题
题目
假设要排序的数据最多是4位十进制的正整数，编写对应的基数排序程序。
链表结点结构： struct nofr {int data; nofe *link };
例如数据如下： 30 901 48 9 3912 88 1925
排序后： 9 30 48 88 901 1925 3912
思路
- 这是个典型的基数排序
- 由于我们是用链表进行操作，所以我们需要一个结点数组来储存每个“桶”的头结点，还需要一个数组来指向每一个“桶”的尾结点。
- 对于链表中的每一个结点，我们做如下处理：
- 首先得到它的倒数第i位数（从个位到高位），如果位不足就视为0。
- 接着根据这一位上的数把它放入对应的“桶”里，放入的方式和创建链表差不多。
- 遍历完所有结点后，我们得到了按某一位排好的数。将这些数从0开始，依次取出，放回到链表里。（这里我采取的是覆盖式的，因为这些桶已经装了整段数据，所以可以直接覆盖）
- 重复第3~5点，直到最高位。
源程序清单
- 此处我们先确定了桶数和最高位数，所以直接定义常量
#include<iostream>
constexpr auto N = 10; //有10个桶，0~9;
constexpr auto DIG = 4; //最大位数为4;
using namespace std;
struct node {
int data;
node* link;
};
//作用：获取a的倒数第n + 1位数字
int getNNum(int a, int n) {
while (n--)
a = a / N; //这里的N可以是10，为了使程序统一
return a % N;
}
void radixSort(node* arr) {
if (arr == NULL) return;
node* p = arr; //p的作用是遍历链表
for (int i = 0; i < DIG; i++) { //排4次
node* head[N] = { NULL }; //十个桶的头结点 一定要放在里面，相当于初始化！
node* tail[N] = { NULL }; //十个桶的尾结点
p = arr; //相当于初始化
while (p != NULL) { //入桶
int temp = getNNum(p->data, i); //获取本轮次对应的位数的值，记为temp
if (head[temp] == NULL) { //如果头结点为空
head[temp] = new node;
head[temp]->data = p->data;
head[temp]->link = NULL;
tail[temp] = head[temp];
}
else {
node* q = new node;
q->data = p->data;
q->link = NULL;
tail[temp]->link = q; //连接尾结点
tail[temp] = q; //更新尾结点
}
p = p->link;
}
//出桶
p = arr;
for (int j = 0; j < N; j++) { //j就是桶对应的数
node* tmp = head[j]; //tmp用于遍历当前桶内的所有元素
while (tmp != NULL && p != NULL) {
p->data = tmp->data; //覆盖式插回
p = p->link;
tmp = tmp->link;
}
}
}
}
//创建随机链表
node* createRandLink()
{
srand((unsigned int)time(NULL));
node* head = NULL, * p, * q;
int n = rand() % 15; //n为有序链表的起点
if (N == 0) return NULL;
head = new node;
p = head;
p->data = n;
p->link = NULL;
for (int i = 1; i < N; i++) {
q = new node;
q->data = rand() % 9999; //随机数
q->link = NULL;
p->link = q;
p = q;
}
return head;
}
//这个函数的作用是输出链表
void printLink(node* head) {
node* p = head;
while (p != NULL) {
cout << p->data << " -> ";
p = p->link;
}
cout << "\n";
}
int main() {
node* arr = createRandLink();
printLink(arr);
radixSort(arr);
printLink(arr);
return 0;
}
