单链表应用示例

1、学生成绩管理 以单链表作为存储结构，设计和实现某班某门课程成绩管理的完整程序。程序要求完成如下功能： （1）创建成绩链表，学生数据包含学生的学号、姓名和成绩。（2）可以在指定学号学生前插入学生成绩数据。 （3）可以删除指定学号的学生数据。 （4）可以计算学生的总数。 （5）可以按学号和姓名查找学生。 （6）可以显示所有学生的成绩。 （7）可以把学生成绩按从高到低的顺序排列。此处的设计思想基本与顺序表相同，只是对保存学生成绩的线性表采用不同的存储结构实现。本例中用到的学生数据也是程序运行时由用户从键盘输入，保存到一个单链表中。学生结构体类型的定义与顺序表应用举例处的定义相同，用语言描述如下：ty

2、pedef struct Student /*学生类型定义*/ int score; /*成绩*/ char sno5,sname8; /*学号,姓名*/ Student;当学生的学号为“#”时，也是表示数据输入的结束。单链表中保存的数据元素均为学生Student类型，则单链表定义如下：typedef struct Node /*结点类型定义*/Student studentInfo; /*学生信息*/ struct Node *next; /*指向后继元素的指针域*/ LinkList;对学生的成绩按从高到低排序时，使用的也是直接插入排序思想。此外，为了排序后还能在原单链表上继续进行操作，这

3、里是把单链表中的内容复制到一个新单链表中，对新单链表排序，原单链表不变。下面是以单链表作为存储结构实现的学生某门课程成绩管理的完整语言程序。 #include #include #include #include typedef struct Student /*学生类型定义*/ int score; /*成绩*/ char sno5,sname8; /*学号,姓名*/ Student; typedef struct Node /*结点类型定义*/ Student studentInfo; /*学生信息*/ struct Node *next; /*指向后继元素的指针域*/ LinkList;

4、 void display(LinkList *p) /*在屏幕上显示一个学生的成绩信息*/ printf(nnnnottnamettscore: ); printf(n%s,p-studentInfo.sno); /*打印学号*/ printf(tt ); printf(%s,p-studentInfo.sname); /*打印姓名*/ printf(tt ); printf(%-4dn,p-studentInfo.score); /*打印成绩*/ void displayAll(LinkList *L) /*在屏幕上显示所有学生的成绩信息*/ LinkList *p; p=L-next;

5、printf(nnnnottnamettscore: ); while(p) printf(n%s,p-studentInfo.sno); /*打印学号*/ printf(tt ); printf(%s,p-studentInfo.sname); /*打印姓名*/ printf(tt ); printf(%-4dn,p-studentInfo.score);/*打印成绩*/ p=p-next; LinkList *inputdata( ) /*输入学生信息*/ LinkList *s=NULL ; /*s是指向新建结点的指针*/ char sno5; /*存储学号的数组*/ printf(n

6、); printf( no: ); scanf(%s,sno); /*输入学号*/ if(sno0=#) /*#结束输入*/ return s; s=( LinkList *)malloc(sizeof(LinkList); strcpy(s-studentInfo.sno,sno); if(strlen(sno)4) /*如果sno字符个数大于等于5，因为字符串没有0结束标志， 在读数据时将把姓名字符一起读到sno数组，因此做了如下处理*/ s-studentInfo.sno4=0; printf( name: ); scanf(%s,s-studentInfo.sname); /*输入姓名

7、*/ printf(score: ); scanf(%d,&s-studentInfo.score); /*输入成绩*/ return s; LinkList *createTailList( ) /*以尾插法建立带头结点的学生信息单链表*/ LinkList *L,*s, *r; /*L头指针，r尾指针，s是指向新建结点的指针*/ L=( LinkList *)malloc(sizeof (LinkList); /*建立头结点，申请结点存储空间*/ r=L; /*尾指针指向头结点*/ printf(请输入学生成绩，当学号no为#时结束：nn ); while (1) /*逐个输入学生的成绩*

8、/ s=inputdata( ); if(!s) break; /*s为空时结束输入*/ r-next=s; /*把新结点插入到尾指针后*/ r=s; /*r 指向新的尾结点*/ r-next=NULL; /*尾指针的指针域为空*/ displayAll(L); /*显示所有学生信息*/ return L; Void locateElemByno(LinkList *L, char ch5) /*按学号查找学生的算法*/ LinkList *p=L-next; /*从第一个结点开始查找*/ while ( p & (strcmp(p-studentInfo.sno,ch)!=0)/*p不空且输

9、入学号与链表中学号不等*/ p = p -next; if (!p) printf(nntDont find the student!n ); else display(p); /*显示查找到的学生信息*/ void locateElemByname(LinkList *L, char sname8)/*按姓名查找学生的算法*/ LinkList *p=L-next; /*从第一个结点开始查找*/ while ( p& (strcmp(p-studentInfo.sname,sname)!=0) /*p不空且输入姓名与链表中姓名不等*/ p = p -next; if (!p) printf(

10、nntDont find the student!n ); else display(p); /*显示查找到的学生信息*/ int lengthList (LinkList *L) /*求学生总人数的算法*/ LinkList * p=L-next; /* p指向第一个结点*/ int j=0; while (p) p=p-next; j+ ; /* p所指的是第 j 个结点*/ return j; void insertElem ( LinkList *L, char ch5) /*在带头结点的单链表L中指定学号前插入学生*/ LinkList *p,*s; p=L; /*从头结点开始查找学

11、号为ch的结点的前趋结点p */ while (p-next) & (strcmp(p-next-studentInfo.sno,ch)!=0) p = p -next; s=inputdata(); /*输入欲插入学生信息*/ s-next=p-next; p-next=s; void deleteElem (LinkList *L, char ch5) /*删除给定学号的学生信息的算法*/ LinkList *p,*q; p=L; while ( (p-next)&(strcmp(p-next-studentInfo.sno,ch)!=0 ) p=p-next; /*从头结点开始查找学号为

12、ch的结点的前趋结点p*/ if (!p-next) /* 已经扫描到表尾也没找到*/ printf(nntDont find the student!n ); else q=p-next; /*q指向学号为ch的结点*/ printf(nndeleted students information:); display(q); p-next=q-next; /*改变指针*/ free(q); /*释放q占用空间 */ printf(nnall students information :); displayAll(L); void insertSort(LinkList *L) /*用直接插入

13、排序思想把学生的成绩按从高到低排序， 结果保存在新有序链表中，原链表不变*/ LinkList *L1,*p; /*L1有序链表的表头，p插入位置前结点*/ LinkList *q,*s; /*q欲插入L1中的结点*/ int len; len=lengthList (L) ; L1=( LinkList *)malloc(sizeof (LinkList); /*建立头结点，申请结点存储空间*/ if (L-next) /*链表L非空*/ /*生成有序链表的第一个结点*/ s=( LinkList *)malloc(sizeof (LinkList); /*建立结点，申请结点存储空间*/ s

14、trcpy(s-studentInfo .sno ,L-next-studentInfo.sno); strcpy(s-studentInfo .sname,L-next-studentInfo.sname); s-studentInfo .score =L-next-studentInfo.score; s-next =NULL; L1-next=s; /*只有原单链表的第一个结点的有序链表L1*/ q=L-next-next; /*原单链表的第二个结点，q即要插入有序链表L1中的结点*/ else printf(nthe student link list is empty!n); ret

15、urn; while(q) /*链表L中有结点*/ p=L1 ; /*从链表L1的第一个结点开始比较*/ while(p-next) & (p-next-studentInfo.score=q-studentInfo.score) p=p-next ; /*查找插入位置前结点*/ /*生成欲插入有序链表中的结点*/ s=( LinkList *)malloc(sizeof (LinkList); /*建立结点，申请结点存储空间*/ strcpy(s-studentInfo .sno ,q-studentInfo.sno); strcpy(s-studentInfo .sname ,q-stud

16、entInfo.sname); s-studentInfo .score =q-studentInfo.score; if(!p-next) /*p是有序链表的最后一个结点*/ s-next =NULL ; p-next =s; else s-next =p-next ; p-next =s; q=q-next; /*下一个欲插入有序链表的结点*/ /*while(!q)*/ displayAll(L1); /*显示生成的有序链表*/ void main() printf(=nn); printf( 带头结点的学生成绩管理程序nn); printf(=nn); LinkList *L; cha

17、r ch5,sname8; int b=1; while(b) int a; printf(nn); printf( 创建（带头尾插） 指定学号前插入 按学号删除n ); printf(计算学生总数 按学号查找 按姓名查找n); printf( 显示所有学生 成绩排序 退出n); printf(n请输入功能选项：); scanf(%d,&a); switch(a) case 1: L=CreateTailList(); break; case 2: printf(n输入欲在哪个学号前插入数据:); scanf(%s,ch); insertElem(L, ch) ; break; case 3: printf(n输入欲删除学生的学号:); scanf(%s,ch); deleteElem(L, ch) ; break; case 4: printf( n学生总数为： %d n,lengthList (L) ); break; case 5: printf(n输入欲查找学生的学号:); scanf(%s,ch); locateElemByno(L, ch) ;break; case 6: printf(n输入欲查找学生的姓名:); scanf(%s,sname); locateElemByname(L, sname );break; case 7: displayAll(L);