|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
排序问题已经思考了很多天了,尝试了不少方法,都做不出来,求指点
下面是题目和我写的代码,想知道自己的错误在哪
/*有两个链表a和b,设节点中包含学号,成绩,要求将两个链表合并,并根据学号升序排序*/
#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct Student)
struct Student
{
int num;
int score;
struct Student *next;
};
void main()
{
struct Student *p, *q, *p1, *p2;
struct Student *creat();
struct Student *mix(struct Student *head1, struct Student *head2);
struct Student *sort(struct Student *head);
struct Student *print(struct Student *head);
printf("输入a班学生学号和成绩:\n");
p1 = creat();
printf("输入b班学生学号和成绩:\n");
p2 = creat();
printf("a,b班成绩如下:\n");
printf("a班:");
print(p1);
printf("b班:");
print(p2);
p = mix(p1, p2);
q = sort(p);
printf("合并并排序后的结果为:\n");
print(q);
getchar();
getchar();
}
struct Student *creat()
{
int j = 0;
struct Student *p1, *p2, *head;
p1 = p2 = malloc(LEN);
scanf_s("%d%d", &p1->num, &p1->score);
head = NULL;
while (p1->num != 0)
{
j = j + 1;
if (j == 1)
head = p1;
else
p2->next = p1;
p2 = p1;
p1 = malloc(LEN);
scanf_s("%d%d", &p1->num, &p1->score);
}
p2->next = NULL;
return(head);
}
struct Student *print(struct Student *head)
{
struct Student *p;
p = head;
if (head != NULL)
{
while (p != NULL)
{
printf("number is %d,score is %d\n", p->num, p->score);
p = p->next;
}
}
return(head);
}
struct Student *mix(struct Student *head1, struct Student *head2)
{
struct Student *p1, *p2;
p2 = head2;
if (head1 != NULL)
{
p1 = head1;
while (p1->next != NULL)
{
p1 = p1->next;
}
p1->next = p2;
}
return(head1);
}
struct Student *sort(struct Student *head)
{
struct Student *p1, *p2, *pt;
int cont = 0;
pt = head;
p1 = pt;
p2 = p1->next;
if (head != NULL)
{
while (pt != NULL)
{
pt = pt->next;
cont++;
}
pt = head;
}
if (cont == 1)
{ }
if (cont == 2)
{
if (p1->num < p2->num)
{
p2->next = p1;
p1->next = NULL;
}
}
if (cont > 2)
{
if (p1 == head)
{
if (p1->num < p2->num)
{
p1->next = p2->next;
p2->next = p1;
pt = p2;
p2 = p1->next;
}
else
{
p1 = p1->next;
p2 = p1->next;
}
}
while (p2 != NULL)
{
if (p1->num < p2->num)
{
p1->next = p2->next;
p2->next = p1;
pt->next = p2;
pt = p2;
p2 = p1->next;
}
else
{
pt = pt->next;
p1 = p1->next;
p2 = p1->next;
}
}
p2->next = NULL;
}
return(head);
}
本帖最后由 迷雾少年 于 2019-8-16 15:39 编辑
Ps: 1.以后记得发代码的时候选格式发
2.打多点注释,方便自己,也方便他人
你的原来的代码,添加了注释
- #include<stdio.h>
- #include<stdlib.h>
- #pragma warning(disable:4996)
- #define LEN sizeof(struct Student)
- struct Student
- {
- int num;
- int score;
- struct Student* next;
- };
- void main()
- {
- struct Student* p, * q, * p1, * p2;
- struct Student* creat();
- struct Student* mix(struct Student* head1, struct Student* head2);
- struct Student* sort(struct Student* head);
- struct Student* print(struct Student* head);
- printf("输入a班学生学号和成绩:\n");
- p1 = creat();
- //
- sort(p1);
- printf("输入b班学生学号和成绩:\n");
- p2 = creat();
- printf("a,b班成绩如下:\n");
- printf("a班:");
- print(p1);
- printf("b班:");
- print(p2);
- p = mix(p1, p2);
- q = sort(p);
- printf("合并并排序后的结果为:\n");
- print(q);
- getchar();
- getchar();
- }
- struct Student* creat()
- {
- int j = 0;
- struct Student* p1, * p2, * head;
- p1 = p2 = malloc(LEN);
- scanf_s("%d%d", &p1->num, &p1->score);
- head = NULL;
- while (p1->num != 0)
- {
- j = j + 1;
- if (j == 1)
- head = p1;
- else
- p2->next = p1;
- p2 = p1;
- p1 = malloc(LEN);
- scanf_s("%d%d", &p1->num, &p1->score);
- }
- p2->next = NULL;
- return(head);
- }
- struct Student* print(struct Student* head)
- {
- struct Student* p;
- p = head;
- if (head != NULL)
- {
- while (p != NULL)
- {
- printf("number is %d,score is %d\n", p->num, p->score);
- p = p->next;
- }
- }
- return(head);
- }
- //你这个算法是直接把head2的粘到p1后面 ,但是前提是head1是递减序列,head2是递减序列,并且head1的最后一个元素大于head2的第一个元素
- struct Student* mix(struct Student* head1, struct Student* head2)
- {
- struct Student* p1, * p2;
- p2 = head2;
- if (head1 != NULL)
- {
- p1 = head1;
- while (p1->next != NULL)
- {
- p1 = p1->next;
- }
- p1->next = p2;
- }
- return(head1);
- }
- //你的排序算法问题很多
- struct Student* sort(struct Student* head)
- {
- struct Student* p1, * p2, * pt;
- int cont = 0;
- pt = head;
- p1 = pt;
- p2 = p1->next;
- if (head != NULL)
- {
- while (pt != NULL)
- {
- pt = pt->next;
- cont++;
- }
- pt = head;
- }
- if (cont == 1)
- {
- }
- if (cont == 2)
- {
- if (p1->num < p2->num)
- {
- p2->next = p1;
- p1->next = NULL;
- }
- }
- if (cont > 2)
- {
- if (p1 == head)
- {
- //保证头2个元素是降序
- if (p1->num < p2->num)
- {
- p1->next = p2->next;
- p2->next = p1;
- pt = p2; //指向头
- p2 = p1->next; //指向第三个元素
- }
- else
- {
- p1 = p1->next;
- p2 = p1->next;
- }
- }
- //然后p1指向第二个数 //p2指向第三个数
- while (p2 != NULL)
- {
-
- //如果p1<p2,交换两者,并且p1指向小的数,p2指向p1的下一个数?这样一趟比较交换就排序完不对的
- //但是问题是你下面return (head)的这个head并不能完整看到所有结点啊,有些不见了
- if (p1->num < p2->num)
- {
- //此时的pt:2 1 3
- //pt 2 1 3 0
- //p2 3 0
- //p1 1 3 0
- p1->next = p2->next;//p1: 1 0
- p2->next = p1; //p2: 3 1 0
- pt->next = p2; //pt: 2 3 1 0
- pt = p2; //pt: 3 1 0
- p2 = p1->next; //p2: 0
- }
- //否则p1 p2一起右移
- else
- {
- pt = pt->next;//1 3 0
- p1 = p1->next;//3 0
- p2 = p1->next;//0
- }
- }
- p2->next = NULL;
- }
- return(head);
- }
复制代码
下面是我的修改思路:
- struct Student* mysort(struct Student* head)
复制代码
函数输入参数是一个链表,直接递减排序。
所以只需要调用你那个mix函数把两个链表无条件接起来,再调用这个函数即可。
链表排序方法:
1.空间换时间
开辟空间新建一个数组线性空间,把链表的数据一个个对应写上去,然后运用数组排序的方法(冒泡,快速,选择,插序等...)
2.时间和空间
不开辟空间,每次在链表上找一个最大的元素,找到了添加到上一个比他大的元素后面,然后把这个元素从head中去掉,继续寻找第二大的。
修改后(写得比较简陋估计有bug,你根据思路自己写就行了,思路最重要)
- #include<stdio.h>
- #include<stdlib.h>
- #pragma warning(disable:4996)
- #define LEN sizeof(struct Student)
- struct Student
- {
- int num;
- int score;
- struct Student* next;
- };
- void main()
- {
- struct Student* p, * q, * p1, * p2;
- struct Student* creat();
- struct Student* mix(struct Student* head1, struct Student* head2);
- struct Student* sort(struct Student* head);
- struct Student* print(struct Student* head);
- struct Student* mysort(struct Student* head);//
- printf("输入a班学生学号和成绩:\n");
- p1 = creat();
- //
- printf("输入b班学生学号和成绩:\n");
- p2 = creat();
- printf("a,b班成绩如下:\n");
- printf("a班:");
- print(p1);
- printf("b班:");
- print(p2);
- p = mix(p1, p2);
- q = mysort(p);
- printf("合并并排序后的结果为:\n");
- print(q);
- getchar();
- getchar();
- }
- struct Student* creat()
- {
- int j = 0;
- struct Student* p1, * p2, * head;
- p1 = p2 = malloc(LEN);
- scanf_s("%d%d", &p1->num, &p1->score);
- head = NULL;
- while (p1->num != 0)
- {
- j = j + 1;
- if (j == 1)
- head = p1;
- else
- p2->next = p1;
- p2 = p1;
- p1 = malloc(LEN);
- scanf_s("%d%d", &p1->num, &p1->score);
- }
- p2->next = NULL;
- return(head);
- }
- struct Student* print(struct Student* head)
- {
- struct Student* p;
- p = head;
- if (head != NULL)
- {
- while (p != NULL)
- {
- printf("number is %d,score is %d\n", p->num, p->score);
- p = p->next;
- }
- }
- return(head);
- }
- //你这个算法是直接把head2的粘到p1后面 ,但是前提是head1是递减序列,head2是递减序列,并且head1的最后一个元素大于head2的第一个元素
- struct Student* mix(struct Student* head1, struct Student* head2)
- {
- struct Student* p1, * p2;
- p2 = head2;
- if (head1 != NULL)
- {
- p1 = head1;
- while (p1->next != NULL)
- {
- p1 = p1->next;
- }
- p1->next = p2;
- }
- return(head1);
- }
- //先无要求混合起来,再调用这个排序链表
- struct Student* mysort(struct Student* head)
- {
- struct Student* tmphead = head;
- int nodes = 0;
- if (NULL == head)
- return NULL;
- /*
- //方法1:空间换时间
- //统计结点数量
- while (tmphead)
- {
- nodes++;
- tmphead = tmphead->next;
- }
- struct Student* ptrArrays = malloc(sizeof(struct Student) * nodes);
- int k = 0;
- tmphead = head;
- while (tmphead)
- {
- ptrArrays[k++] = *tmphead;
- tmphead = tmphead->next;
- }
- //然后对数组ptrArrays排序,然后把排序完的结果一一低写会head即可
- //.....
- */
- //方法2:直接法
- int maxval = NULL;//假设第一个是最大值
- struct Student* ptrTmp = NULL,*headptrTmp= NULL,*pLast=head,*tmp,*pllast=head;
- //先找出最大的那个结点
- tmphead = head;
- while (tmphead)
- {
- if (maxval <= tmphead->num) {
- maxval = tmphead->num;
- headptrTmp = tmphead;
- }
- tmphead = tmphead->next;
- }
- ptrTmp = NULL;
- tmp = head;
-
- while (1)
- {
- tmphead = head;
- maxval = -9999999;
- //寻找最大的结点
- while (tmphead) {
- if (tmphead == headptrTmp)
- {
- pllast = tmphead;
- tmphead = tmphead->next;
- continue;
- }
- if (tmphead->num > maxval) {
- maxval = tmphead->num;
- tmp = tmphead;
- pLast = pllast;
- }
- pllast = tmphead;
- tmphead = tmphead->next;
- }
- //把这个结点从链表中移除添加到ptrTmp中
- //【移除】
- if (tmp->next == NULL)//最后一个结点
- {
- pLast->next = NULL;
- }
- else if (head != tmp && tmp->next != NULL)//中间的结点
- {
- pLast->next = tmp->next;
- }
- else if (tmp == head) //第一个结点
- {
- head = tmp->next;
- }
- //【添加】
- if (ptrTmp == NULL)
- {
- ptrTmp = tmp;
- ptrTmp->next = NULL;
- }
- else
- {
- //遍历到链表尾添加上
- struct Student* tmv = ptrTmp;
- while (tmv&&tmv->next!=NULL) {
- tmv = tmv->next;
- }
- tmv->next = tmp;
- tmv->next->next = NULL;
- }
- if (head->next == NULL && head == headptrTmp) {//最后就剩下那个最大的结点
- break;
- }
- }
- if (ptrTmp && headptrTmp)
- headptrTmp->next = ptrTmp;
- return headptrTmp;
- }
- //你的排序算法问题很多
- struct Student* sort(struct Student* head)
- {
- struct Student* p1, * p2, * pt;
- int cont = 0;
- pt = head;
- p1 = pt;
- p2 = p1->next;
- if (head != NULL)
- {
- while (pt != NULL)
- {
- pt = pt->next;
- cont++;
- }
- pt = head;
- }
- if (cont == 1)
- {
- }
- if (cont == 2)
- {
- if (p1->num < p2->num)
- {
- p2->next = p1;
- p1->next = NULL;
- }
- }
- if (cont > 2)
- {
- if (p1 == head)
- {
- //保证头2个元素是降序
- if (p1->num < p2->num)
- {
- p1->next = p2->next;
- p2->next = p1;
- pt = p2; //指向头
- p2 = p1->next; //指向第三个元素
- }
- else
- {
- p1 = p1->next;
- p2 = p1->next;
- }
- }
- //然后p1指向第二个数 //p2指向第三个数
- while (p2 != NULL)
- {
-
- //如果p1<p2,交换两者,并且p1指向小的数,p2指向p1的下一个数?这样一趟比较交换就排序完不对的
- //但是问题是你下面return (head)的这个head并不能完整看到所有结点啊,有些不见了
- if (p1->num < p2->num)
- {
- //此时的pt:2 1 3
- //pt 2 1 3 0
- //p2 3 0
- //p1 1 3 0
- p1->next = p2->next;//p1: 1 0
- p2->next = p1; //p2: 3 1 0
- pt->next = p2; //pt: 2 3 1 0
- pt = p2; //pt: 3 1 0
- p2 = p1->next; //p2: 0
- }
- //否则p1 p2一起右移
- else
- {
- pt = pt->next;//1 3 0
- p1 = p1->next;//3 0
- p2 = p1->next;//0
- }
- }
- p2->next = NULL;
- }
- return(head);
- }
复制代码
运行结果 1:
- 输入a班学生学号和成绩:
- 1 1
- 2 2
- 3 3
- 0 0
- 输入b班学生学号和成绩:
- 4 4
- 5 5
- 6 6
- 0 0
- a,b班成绩如下:
- a班:number is 1,score is 1
- number is 2,score is 2
- number is 3,score is 3
- b班:number is 4,score is 4
- number is 5,score is 5
- number is 6,score is 6
- 合并并排序后的结果为:
- number is 6,score is 6
- number is 5,score is 5
- number is 4,score is 4
- number is 3,score is 3
- number is 2,score is 2
- number is 1,score is 1
复制代码
运行结果 2:
- 输入a班学生学号和成绩:
- 1123 66
- 1699 77
- 1267 55
- 121684 77
- 0 0
- 输入b班学生学号和成绩:
- 126967 33
- 26644 11
- 0 0
- a,b班成绩如下:
- a班:number is 1123,score is 66
- number is 1699,score is 77
- number is 1267,score is 55
- number is 121684,score is 77
- b班:number is 126967,score is 33
- number is 26644,score is 11
- 合并并排序后的结果为:
- number is 126967,score is 33
- number is 121684,score is 77
- number is 26644,score is 11
- number is 1699,score is 77
- number is 1267,score is 55
- number is 1123,score is 66
复制代码
|
|