单链表应用示例.docx

学生成绩管理以单链表作为存储结构，设计和实现某班某门课程成绩管理的完整程序程序要求完 成如下功能：（1）创建成绩链表，学生数据包含学生的学号、姓名和成绩2）可以在指定学号学生前插入学生成绩数据3）可以删除指定学号的学生数据4）可以计算学生的总数5）可以按学号和姓名查找学生6）可以显示所有学生的成绩7）可以把学生成绩按从高到低的顺序排列 此处的设计思想基本与顺序表相同，只是对保存学生成绩的线性表采用不同的存储结构 实现本例中用到的学生数据也是程序运行时由用户从键盘输入，保存到一个单链表中学 生结构体类型的定义与顺序表应用举例处的定义相同，用C语言描述如下：/*学生类型定义*//*成绩*//*学号,姓名*/typedef struct Student { int score;char sno[5],sname[8]; }Student;当学生的学号为“#”时，也是表示数据输入的结束单链表中保存的数据元素均为学生 Student 类型，则单链表定义如下：typedef struct Node { Student studentInfo;struct Node *next;/*结点类型定义*//*学生信息*//*指向后继元素的指针域*/}LinkList;对学生的成绩按从高到低排序时，使用的也是直接插入排序思想。

此外，为了排序后还 能在原单链表上继续进行操作，这里是把单链表中的内容复制到一个新单链表中，对新单链 表排序，原单链表不变下面是以单链表作为存储结构实现的学生某门课程成绩管理的完整C语言程序include#include#include #include /*学生类型定义*//*成绩*//*学号,姓名*/typedef struct Student { int score;char sno[5],sname[8];}Student;typedef struct Node { Student studentInfo;struct Node *next;/*结点类型定义*//*学生信息*//*指向后继元素的指针域*/}LinkList;void display(LinkList *p){ printf("\n\n\nno\t\tname\t\tscore: ");/*在屏幕上显示一个学生的成绩信息*//*打印学号*/printf("\n%s",p->studentInfo.sno); printf("\t\t ");printf("%s",p->studentInfo.sname); /*打印姓名*/printf("\t\t ");printf("%-4d\n",p->studentInfo.score); /*打印成绩*/}void displayAll(LinkList *L) { LinkList *p;/*在屏幕上显示所有学生的成绩信息*/p=L->next; printf("\n\n\nno\t\tname\t\tscore: "); while(p){ printf("\n%s",p->studentInfo.sno); /*打印学号 */printf("\t\t ");printf("%s",p->studentInfo.sname); /*打印姓名*/printf("\t\t ");printf("%-4d\n",p->studentInfo.score); /*打印成绩*/ p=p->next;}}LinkList *inputdata( ) { LinkList *s=NULL ;char sno[5]; printf("\n "); printf(" no: "); scanf("%s",sno); if(sno[0]=='#') return s;/*输入学生信息*//*s 是指向新建结点的指针*//*存储学号的数组*//*输入学号*//*#结束输入*/s=( LinkList *)malloc(sizeof(LinkList)); strcpy(s->studentInfo.sno,sno);if(strlen(sno)>4) /*如果sno字符个数大于等于5,因为字符串没有'\0'结束标志,在读数据时将把姓名字符一起读到sno数组，因此做了如下处理*/ s->studentInfo.sno[4]='\0';printf(" name: ");scanf("%s",s->studentInfo.sname); /*输入姓名*/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为\"#\"时结束：\n\n ”）;while (1){ s=inputdata( ); if(!s) break; r->next=s; r=s;} r->next=NULL; displayAll(L);return L;}/*逐个输入学生的成绩*//*s 为空时结束输入*/ /*把新结点插入到尾指针后*//*r 指向新的尾结点*//*尾指针的指针域为空*//*显示所有学生信息*/Void locateElemByno(LinkList *L, char ch[5]) /*按学号查找学生的算法*/{ LinkList *p=L->next; /*从第一个结点开始查找*/while ( p && (strcmp(p->studentInfo.sno,ch)!=0))/*p 不空且输入学号与链表中学号不等*/ p = p ->next;if (!p){ printf("\n\n\tDon't find the student!\n" );}else{ display(p); /*显示查找到的学生信息*/}}void locateElemByname(LinkList *L, char sname[8]》* 按姓名查找学生的算法 */{ LinkList *p=L->next; /*从第一个结点开始查找*/while ( p&& (strcmp(p->studentInfo.sname,sname)!=0)) /*p 不空且输入姓名与链表中姓名不等*/ p = p ->next;if (!p){ printf("\n\n\tDon't find the student!\n" ); }else{display(p); /*显示查找到的学生信息*/}}/*求学生总人数的算法*//* p 指向第一个结点*//* p 所指的是第 j 个结点*/int lengthList (LinkList *L) { LinkList * p=L->next;int j=0;while (p){ p=p->next; j++ ;} return j;void insertElem ( LinkList *L, char ch[5])/*在带头结点的单链表L中指定学号前插入学生*/ { LinkList *p,*s;P=L; /*从头结点开始查找学号为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 ch[5]) /*删除给定学号的学生信息的算法*/{ LinkList *p,*q;p=L;while ( (p->next)&&(strcmp(p->next->studentInfo.sno,ch)!=0 )){ p=p->next; /*从头结点开始查找学号为ch的结点的前趋结点p*/}if (!p->next) /* 已经扫描到表尾也没找到*/{ printf("\n\n\tDon't find the student!\n" );}else{ q=p->next; /*q指向学号为ch的结点*/printf("\n\ndeleted student's information:");display(q);p->next=q->next; /*改变指针*/free(q); /*释放q占用空间*/printf("\n\nall student's information :");displayAll(L);}}/*用直接插入排序思想把学生的成绩按从高到低排序，结果保存在新有序链表中，原链表不变*//*L1有序链表的表头，p插入位置前结点*//*q欲插入L1中的结点*/void insertSort(LinkList *L){ LinkList *L1,*p; LinkList *q,*s; int len; len=lengthList (L) ;L1=( LinkList *)malloc(sizeof (LinkList)); /*建立头结点，申请结点存储空间*/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;L1->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) && (p->next->studentInfo.score>=q->studentInfo.score))p=p->next ; /*查找插入位置前结点*//*生成欲插入有序链表中的结点*/s=( LinkList *)malloc(sizeof (LinkList)); /*建立结点，申请结点存储空间*/strcpy(s->s。