单链表应用示例.doc

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

2、如下： typedef 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; /*指向后继元素

4、的指针域*/ LinkList; 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) /*在屏幕上显示所有学生的成绩

5、信息*/ LinkList *p; p=L-next; 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 是指向

6、新建结点的指针*/ char sno5; /*存储学号的数组*/ printf(“n “); 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; print

7、f(“ name: “); scanf(“%s“,s-studentInfo.sname); /*输入姓名*/ printf(“score: “); scanf(“%d“, /*输入成绩*/ return s; LinkList *createTailList( ) /*以尾插法建立带头结点的学生信息单链表*/ LinkList *L,*s, *r; /*L 头指针，r 尾指针，s 是指向新建结点的指针*/ L=( LinkList *)malloc(sizeof (LinkList); /*建立头结点，申请结点存储空间*/ r=L; /*尾指针指向头结点*/ printf(“请输入学生成绩，

8、当学号 no 为“#“时结束：nn “); while (1) /*逐个输入学生的成绩*/ 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 (

9、 p if (!p) printf(“nntDont find the student!n“ ); else display(p); /*显示查找到的学生信息*/ void locateElemByname(LinkList *L, char sname8)/*按姓名查找学生的算法*/ LinkList *p=L-next; /*从第一个结点开始查找*/ while ( p if (!p) printf(“nntDont find the student!n“ ); else display(p); /*显示查找到的学生信息*/ int lengthList (LinkList *L) /*求

10、学生总人数的算法*/ 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; /*从头结点开始查找学号为 ch 的结点的前趋结点 p */ while (p-next) s=inputdata(); /*输入欲插入学生信息*/ s-next=p-next; p-next=s; v

11、oid deleteElem (LinkList *L, char ch5) /*删除给定学号的学生信息的算法*/ LinkList *p,*q; p=L; while ( (p-next) /*从头结点开始查找学号为 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; /

12、*改变指针*/ free(q); /*释放 q 占用空间 */ printf(“nnall students information :“); displayAll(L); void insertSort(LinkList *L) /*用直接插入排序思想把学生的成绩按从高到低排序， 结果保存在新有序链表中，原链表不变*/ LinkList *L1,*p; /*L1 有序链表的表头，p 插入位置前结点*/ LinkList *q,*s; /*q 欲插入 L1 中的结点*/ int len; len=lengthList (L) ; L1=( LinkList *)malloc(sizeof (L

13、inkList); /*建立头结点，申请结点存储空间*/ if (L-next) /*链表 L 非空*/ /*生成有序链表的第一个结点 */ s=( LinkList *)malloc(sizeof (LinkList); /*建立结点，申请结点存储空间*/ strcpy(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; L

14、1-next=s; /*只有原单链表的第一个结点的有序链表 L1*/ q=L-next-next; /*原单链表的第二个结点，q 即要插入有序链表 L1 中的结点*/ else printf(“nthe student link list is empty!n“); return; while(q) /*链表 L 中有结点*/ p=L1 ; /*从链表 L1 的第一个结点开始比较*/ while(p-next) /*查找插入位置前结点*/ /*生成欲插入有序链表中的结点*/ s=( LinkList *)malloc(sizeof (LinkList); /*建立结点，申请结点存储空间*/ s

15、trcpy(s-studentInfo .sno ,q-studentInfo.sno); strcpy(s-studentInfo .sname ,q-studentInfo.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); /*显示生成的有序链表*

16、/ void main() printf(“=nn“); printf(“ 带头结点的学生成绩管理程序nn“); printf(“=nn“); LinkList *L; char ch5,sname8; int b=1; while(b) int a; printf(“nn“); printf(“ 创建（带头尾插） 指定学号前插入 按学号删除n “); printf(“计算学生总数 按学号查找 按姓名查找n“); printf(“ 显示所有学生 成绩排序 退出n“); printf(“n 请输入功能选项：“); scanf(“%d“, switch(a) case 1: L=CreateTai

17、lList(); 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) ;

18、break; case 6: printf(“n 输入欲查找学生的姓名:“); scanf(“%s“,sname); locateElemByname(L, sname );break; case 7: displayAll(L); break; case 8: insertSort(L); break; case 9: printf(“n 已退出n“); b=0;break; ; 上机运行程序后，程序执行结果如图 2.31（）（）所示。 （b） 建立成绩链表时输入数据 替换 （c ） 建好的成绩链表数据 （d） 在学号 0002 的学生前插入数据 （e） 在学号 0002 的学生前插入数据后显示所有学生数据 （a ） 程序运行的初始界面 （f） 删除学号 0009 的学生数据后显示的数据 （g） 查找学号为 0002 的学生数据 （h） 查找姓名为 john 的学生数据 （i） 学生成绩排序的结果 图 2.31 单链表应用程序上机运行结果