C\C++编写的链表排序问题,数据结构与算法,技术交流,鱼C论坛

Swarm 发表于 2019-3-13 21:22:07

C\C++编写的链表排序问题

代码如下，使用C\C++混合语言编写的带有头指针的单链表。但两个排序模块void Sort_No和void Sort_Sal处无法完成任务，也就是说执行这两个排序模块操作后输出的链表依旧是未排过序的链表顺序，希望有人可以帮忙解答一下，谢谢！
代码中的emp.dat是一个包含有员工编号、员工姓名。员工工资的文件，比如：
010 张三 8000
008 李四 10000
056 王五 6000
001 赵六 1000

代码部分：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>

typedef struct Staff_Infor
{
char No; //员工编号
char Name; //员工姓名
double Sal; //员工工资
Staff_Infor *next;
}List;

List *L;

//初始化链表
void InitList(List *&L)
{
L=(List *)malloc(sizeof(List));
L->next=NULL;
}

//尾插法插入数据
void CreateList(List *&L,char No[],char Name[],double Sal)
{
List *p=L,*q;
while(p->next!=NULL)
p=p->next;
q=(List *)malloc(sizeof(List));
strcpy(q->No,No);
strcpy(q->Name,Name);
q->Sal=Sal;
p->next=q;
q->next=NULL;
}

//销毁链表
void DestroyList(List *&L)
{
List *pre=L,*p=L->next;
while(p!=NULL)
{
p=p->next;
pre=pre->next;
free(pre);
}
}

//判断链表是否为空
bool ListEmpty(List *L)
{
return(L->next==NULL);
}

//求线性表长度
int ListLength(List *L)
{
int n=0;
List *p=L;
while(p->next!=NULL)
{
n++;
p=p->next;
}
return n;
}

//打印链表
void PrintList(List *L)
{
List *p=L->next;
int n=0;
printf("\n\n\n正在打印链表……\n");
while(p!=NULL)
{
n++;
printf("第%d个数据为：%s，%s，%lf$\n",n,p->No,p->Name,p->Sal);
p=p->next;
}
printf("\n打印完毕\n\n\n");
}

//删除指定数据
bool DeleteList(List *&L,char ID)
{
List *pre=L,*p=L->next;
while(p!=NULL && strcmp(p->No,ID)!=0)
{
p=p->next;
pre=pre->next;
}
if(p==NULL)
return false;
else
{
pre->next=p->next;
free(p);
return true;
}
}

//根据编号排序
void Sort_No(List *L)
{
List *p,*q,*Pre,*Next;
int i=0;
int n=ListLength(L);
while(i<n)
{
p=L->next->next;
q=L->next;
Pre=L;
while(!p)
{
if(strcmp(p->No,Pre->No)<0)//后面的＜前面的
{
if(p->next!=NULL)
{
Next=p->next;
p->next=q;
q->next=Next;
Pre->next=p;
q=p;
p=p->next;
}
else
{
p->next=q;
Pre->next=p;
q->next=NULL;
}
}
p=p->next;
Pre=Pre->next;
q=q->next;
}
i++;
}
printf("\n\n\n排序完成\n");
PrintList(L);
}

//根据工资排序
void Sort_Sal(List *L)
{
List *p,*q,*Pre,*Next;
int i=0;
int n=ListLength(L);
while(i<n)
{
p=L->next->next;
q=L->next;
Pre=L;
while(p!=NULL)
{
if((p->Sal) < (q->Sal))//后面的＜前面的
{
if(p->next!=NULL)
{
Next=p->next;
p->next=q;
q->next=Next;
Pre->next=p;
q=p;
p=p->next;
}
else
{
p->next=q;
Pre->next=p;
q->next=NULL;
}
}
p=p->next;
Pre=Pre->next;
q=q->next;
}
i++;
}
printf("\n\n\n排序完成\n");
PrintList(L);
}

int main()
{
FILE *f;
List *p;
char No={'\0'},Name={'\0'};
double Sal=0.0;
printf("开始执行。\n\n\n\n\n\n\n\n\n\n");
Sleep(2000);

printf("打开文件");
f=fopen("d:\\emp.dat","r");
if(f==NULL)
{
printf("\n文件打开失败！\n\n\n");
exit(0);
}
printf("\n打开成功！\n\n\n\n\n\n\n\n\n\n");
Sleep(2000);

printf("\n\n初始化链表中……\n\n");
InitList(L);
printf("初始化完成\n\n\n\n\n\n\n\n\n\n");
Sleep(2000);

printf("开始读入数据……");
while(!feof(f))
{
fscanf(f,"%s",&No);
fscanf(f,"%s",&Name);
fscanf(f,"%lf",&Sal);
CreateList(L,No,Name,Sal);
}
printf("\n读取成功！\n\n\n\n\n\n\n\n\n\n");
Sleep(3000);

printf("请输入一个职工的数据");
printf("\n编号：");
scanf("%s",&No);
printf("\n姓名：");
scanf("%s",&Name);
printf("\n工资：");
scanf("%lf",&Sal);
CreateList(L,No,Name,Sal);
printf("\n创建完成！\n\n\n\n\n\n\n\n\n\n");
Sleep(3000);

PrintList(L);
system("PAUSE");

printf("开始按编号排序\n");
Sort_No(L); //问题就出现在这里，执行Sort_No时输出的链表依旧是未排序的链表
printf("\n\n\n\n\n\n\n\n\n\n");
system("PAUSE");

printf("开始按工资排序\n");
Sort_Sal(L); //同样的问题也出现在这里……
printf("\n\n\n\n\n\n\n\n\n\n");
system("PAUSE");

printf("删除指定数据，请输入制定编号：");
scanf("%s",&No);
DeleteList(L,No);
PrintList(L);
printf("删除完成\n\n\n\n\n\n\n\n\n\n");
system("PAUSE");

fclose(f);
f=fopen("d:\\emp.dat","w");
printf("\n删除完成，请打开文件查看\n\n\n\n\n\n\n\n\n\n");
system("PAUSE");

printf("开始将链表写入文件……\n\n\n");
p=L->next;
while(p!=NULL)
{
fprintf(f,"%s\t",p->No);
fprintf(f,"%s\t",p->Name);
fprintf(f,"%lf",p->Sal);
p=p->next;
if(p==NULL)
{
fprintf(f,"^Z");
break;
}
else
fprintf(f,"\n");
}
fclose(f);
return 0;
}

jackz007 发表于 2019-3-13 22:38:55

本帖最后由 jackz007 于 2019-3-14 00:04 编辑

我把问题相关部分代码做了修改，为了尽量压缩修改范围，各个函数均直接使用全局变量 L 。请楼主测试：
int ListLength(void)
{
   int n = 0          ;
   List * p = L       ;
   while(p != NULL) {
            n ++       ;
            p = p -> next ;
   }
   return n          ;
}

void PrintList(void)
{
   List * p = L -> next                                                             ;
   int n = 0                                                                         ;
   printf("\n\n\n正在打印链表……\n")                                                 ;
   while(p != NULL) {
            n ++                                                                      ;
            printf("第%d个数据为：%s , %s , %lf\n" , n , p -> No , p -> Name , p -> Sal) ;
            p = p -> next                                                             ;
   }
   printf("\n打印完毕\n\n\n")                                                       ;
}

void Sort_No(void)
{
   List * p , * x , * m                      ;
   int i , j , n                               ;

   n = 0                                        ;
   p = L                                        ;
   while(p != NULL) {
            m = p                         ;
            p = p -> next                         ;
            n ++                                  ;
   }
   if(n > 1) {
            for(i = 1 ; i < n ; i ++) {
                     j = i                         ;
                     while(j > 0 && m -> No < m -> No) {
                           x = m          ;
                           m = m       ;
                           m = x             ;
                           m -> next = m ;
                           j --                ;
                     }
            }
            L = m                            ;
            printf("\n\n\n排序完成\n")          ;
            PrintList()                         ;
   }
}

void Sort_Sal(void)
{
   List * p , * x , * m                      ;
   int i , j , n                               ;

   n = 0                                        ;
   p = L                                        ;
   while(p != NULL) {
            m = p                         ;
            p = p -> next                         ;
            n ++                                  ;
   }
   if(n > 1) {
            for(i = 1 ; i < n ; i ++) {
                     j = i                         ;
                     while(j > 0 && m -> Sal < m -> Sal) {
                           x = m          ;
                           m = m       ;
                           m = x             ;
                           m -> next = m ;
                           j --                ;
                     }
            }
            L = m                            ;
            printf("\n\n\n排序完成\n")          ;
            PrintList()                         ;
   }
}

Swarm 发表于 2019-3-14 08:31:01

jackz007 发表于 2019-3-13 22:38
我把问题相关部分代码做了修改，为了尽量压缩修改范围，各个函数均直接使用全局变量 L 。请楼主测试：
...

确实可以了。但我还想知道为什么我的那个方法没法完成排序呢？

翼是孤独 发表于 2019-3-16 19:26:11

加&号
void Sort_No(List *&L)
void Sort_Sal(List *&L)
试试行不行

Swarm 发表于 2019-3-18 07:41:54

翼是孤独发表于 2019-3-16 19:26
加&号
void Sort_No(List *&L)
void Sort_Sal(List *&L)

试了，还是不行……也许我应该把它写进主函数单步调试试试看

翼是孤独 发表于 2019-3-18 21:59:13

本帖最后由翼是孤独于 2019-3-18 22:08 编辑

1.NO里面
if(strcmp(p->No,Pre->No)<0)//后面的＜前面的

Pre改成q，指针顺序是：pre，q，p 你要比较的是q和p
2.
函数形参里面的 *L,也应该改成*&L

sort的没看，你先试试No行不行

Swarm 发表于 2019-3-19 10:55:20

翼是孤独发表于 2019-3-18 21:59
1.NO里面
if(strcmp(p->No,Pre->No)

并不可以……还是和以前一样……

Swarm 发表于 2019-3-19 10:55:57

我放弃了，我选择插入法排序了……这冒泡简直要我命

页: [1]

鱼C论坛's Archiver

C\C++编写的链表排序问题