|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
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);
}
输入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
输入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
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2019-8-16 10:18:00
置顶卡
千斤顶
显身卡
楼主