一、实验目的
1.掌握链表的基本结构和关系。
2.掌握C指针和结构体的使用方法，掌握链表编程。
链表知识点讲解：
链表的遍历：
有·两种链表，第一种是第一个节点数据部分为空。另一种是第一个节点就存放数据。
两种方式的编程是有点不同的：
第一种方式，不管怎样对链表进行增加修改和删除，head的位置都不会变化，head的值只需要传入到函数中，不需要返回，不需要返回。
第二种方式，如果数据插入到第一个节点，head存储的地址会发生变化。这种方式的链表在定义函数时，需要返回链表的head。
实现思路：
①用head指针永远指向链表头。
②用q指针一开始指向第一个有数据的节点，然后就可以访问到节点中的数据了。访问结束后，q移动到下一个节点（q=q->next;）,直到q的值为NULL，结束对链表的访问。
typedef struct Student{
char studentNo[20];
char studentName[11];
}st;
typedef struct node{
struct Student data; //数据段
struct node *next; //指针域
}Node,*link； //Node为node类型的别名，link为node类型的指针别名
Node st1;
link p;(link 本身就是一个指针类型的结构体变量）
链表的插入（建立）：
在这个例子中，学生节点的插入是有顺序的（链表按照学号排序），也就是说，每次准备插入一个学生节点时，先要找到这个节点应该插入到那个节点的前面。有几种情况需要考虑：
1.当前链表是空的(head的指针域为空)，状态如下（node为新节点（用malloc创立），准备插入的第一个节点）：
此时，则直接用head->next = node;这条语句，就可以把node插入到链表中。
if(head->next==NULL)
head->next=node;
2.当前链表已经有节点的情况，状态如下图（node为新建立，准备插入的节点）:
想要插入节点就需要两个一前一后的指针
那么此时，就需要比较“node中studentNo”和“p的studentNo”，查看大小关系。如果“node中的studentNo”小于“p中的studentNo”，这把node插入到q，p之间。如果q，p永远保持一前一后的关系，这样才能保证在找到节点位置后，可以顺利的插入。 q=head;
p=head->next;
bool addNode(link head)
{
link p,q; //p,q两个节点一前一后
link node; //node指针指向新创建的节点
node=(link)malloc(sizeof(Node));
inputStudent(node);
q=head;
p=head->next; //p指向head后面的第一个有效节点
if(head->next==NULL)
head->next=node;
else{
//循环访问链表中的所有节点
while(p!=NULL)
{
if(node->data.studentNo < p->data.studentNo){
//如果node节点的学号比p节点的学号小，则插在p的前面，完成插入后，提前退出子进程
q->next = node;
node->next=p;
return true;
}
else{
//如果node节点的学号比p节点的学号大，继续向后移动指针(依然保持q p一前一后)
q=p;
p=p->next;
}
}
//如果没能提前退出循环，则说明之前没有插入，那么当前node节点的学号是最大值，此时插在链表的最后面
q->next=node;
}
return true;
}
实现步骤：
①
②
③
④
链表的删除：
删除链表的思路：
首先，利用p指针扫描链表，根据学生的学号找到要删除的节点位置。
如果找到，则用以下语句就可以删除p所指向的节点（free p）：
q->next = p->next;
free(p);
这里编程的要点是：保证q在前，p在后的关系，这样才能保证在找到节点位置后，可以顺利的删除。
如果当前p的学号不等于要删除的学号，则p指针后移。
要考虑如果找不到学生学号的情况。
测试数据时，应该实验可以找到学号的情形，和给定的学号找不到的情形，然后查看删除是否成功。
链表的修改，链表的查询：
这两个功能和删除链表的思路类似：
都是先找到要处理的节点，然后处理即可。
“修改”还需要考虑修改内容是否是学号，如果修改了学号，则应该编写程序保证不能破坏链表有序性的这个特点。
链表的清除：（养成好的习惯）
当在菜单中选择了退出功能后，则结束程序。在结束程序之间，要考虑到一个问题：前面用malloc语句建立的节点，在main函数退出时，分配的存储空间是不会自动释放的，所以必须主动释放链表中所有节点占用的内存。（free语句释放所有malloc产生的节点）
定义一个clearlink函数，实现链表的遍历，并用free语句释放所有malloc产生的节点。
#include#include #include #include #include typedef struct Student{ char studentNo[20]; char studentName[11]; }st; typedef struct node{ struct Student data; //数据段 struct node *next; //指针域 }Node,*link; //Node为node类型的别名，link为node类型的指针别名 //定义提示菜单 void myMenu() { printf("******************************菜 单*************************************n"); printf(" 1 增加学生记录 2 删除学生记录 n"); printf(" 3 查找学生记录 4 修改学生记录 n"); printf(" 5 统计学生人数 6 显示学生记录 n"); printf(" 7 退出系统 n"); printf("***************************************************************************n"); } void inputStudent(link l) { printf("请输入学生学号："); scanf("%s",l->data.studentNo); printf("请输入学生的姓名："); scanf("%s",l->data.studentName); //每个新创建的节点的next指针域都初始化为NULL l->next = NULL; } void inputStudentNo(char s[],char no[]) { printf("请输入要%s的学生学号：",s); scanf("%s",no); } void displayNode(link head) { //填写代码，根据传入的链表head头指针，扫描链表显示所有节点的信息 } bool addNode(link head) { link p,q; //p,q两个节点一前一后 link node; //node指针指向新创建的节点 node=(link)malloc(sizeof(Node)); inputStudent(node); q=head; p=head->next; //p指向head后面的第一个有效节点 if(head->next==NULL) head->next=node; else{ //循环访问链表中的所有节点 while(p!=NULL) { if(node->data.studentNo < p->data.studentNo){ //如果node节点的学号比p节点的学号小，则插在p的前面，完成插入后，提前退出子进程 q->next = node; node->next=p; return true; } else{ //如果node节点的学号比p节点的学号大，继续向后移动指针(依然保持q p一前一后) q=p; p=p->next; } } //如果没能提前退出循环，则说明之前没有插入，那么当前node节点的学号是最大值，此时插在链表的最后面 q->next=node; } return true; } bool deleteNode(link head,char no[]) { //按照给定的学号删除学生记录，如果删除成功返回true，如果没找到学号返回false //输入要处理的学号 inputStudentNo("删除",no); return false; } bool queryNode(link head,char no[]) { //按照给定的学号查询学生记录，如果查询成功返回true，如果没找到学号返回false //输入要处理的学号 inputStudentNo("查询",no); return false; } bool modifyNode(link head,char no[]) { //按照给定的学号找到学生记录节点，如果修改成功返回true，如果没找到学号返回false //输入要处理的学号 inputStudentNo("修改",no); return false; } int countNode(link head) { //统计学生的人数，扫描链表统计节点个数，返回节点数 //link p; //int count = 0; //p = head->next; return false; } void clearlink(link head) { //link q,p; //遍历链表，用free语句删除链表中用malloc建立起的所有节点 } int main() { int select; int count; link head; //定义链表 char no[20]; //建立head头结点，在这个程序中head指向头结点，头结点data部分没有内容，其后续节点才有真正的 head = (link)malloc(sizeof(Node)); head->next = NULL; while(1)//死循环 { myMenu(); printf("n请输入你的选择（1-7）："); //显示提示信息 scanf("%d",&select); switch(select) { case 1: //增加学生记录 if(addNode(head)) printf("成功插入一个学生记录。nn"); break; case 2: //删除学生记录 if(deleteNode(head,no)) printf("成功删除一个学生记录。nn"); else printf("没有找到要删除的学生节点。 nn"); case 3: //查询学生记录 if(queryNode(head,no)) printf("成功找到学生记录。nn"); else printf("没有找到学生记录。nn"); break; case 4: //修改学生记录 if(modifyNode(head,no)) printf("成功修改一个学生记录。nn"); else printf("没有找到要修改的学生节点。nn"); break; case 5: //统计学生人数 count = countNode(head); printf("学生人数为：%dnn",count); break; case 6: //显示学生记录 displayNode(head); break; case 7: //退出前清除链表中的所有节点 clearlink(head); return 0; default: printf("输入不正确，应该输入0~7之间的数。nn"); break; } } return 0; }
