数据结构--单链表创建、增删改查功能以及与结构体合用
一、作业要求
单链表操作，要求节点是结构体类型，实现以下功能：
1.尾插学生
2.任意位置插入学生
3.任意位置删除学生
4.逆置单链表
5.学生按学号排序
6.销毁单链表
二、实现过程
1.代码如下：
（1）头文件创建
#ifndef _LINK_L_ #define _LINK_L_ #include <myhead.h> //学生信息结构体 typedef struct { int id; char name[20]; }stu,*Stu; //单链表结构体 typedef struct Link { union { int len; stu xs; }; struct Link *next; }links,*Plink; //创建头节点 Plink create(); //尾插法 int rear_insert(Plink,stu); //输出函数 int output_link(Plink); //学生信息输入 Stu input_stu(Stu); //任意位置插入 int anypos_insert(Plink,int,Stu); //任意位置删除 int anypos_delete(Plink,int); //单链表逆置 int rev_stulink(Plink); //按学号排序 int id_sort(Plink); //单链表销毁 int link_destroy(Plink); #endif
（2）主函数编写
#include "link.h" int main(int argc, const char *argv[]) { int n,pos; Stu s=NULL; Stu sp=NULL; Plink L=create(); //学生信息管理系统结构 while(1){ printf("\t++++++学生管理系统++++++++++\n"); printf("\t\t1、尾插法\n"); printf("\t\t2、任意位置插入信息\n"); printf("\t\t3、任意位置删除信息\n"); printf("\t\t4、单链表逆置\n"); printf("\t\t5、学生学号排序\n"); printf("\t\t6、销毁链表退出系统\n"); printf("\n"); int cz=0; printf("请输入操作数："); scanf("%d",&cz); switch(cz){ case 1: //尾插法 printf("请输入学生个数："); scanf("%d",&n); s=malloc(sizeof(stu)*n); for(int i=0;i<n;i++){ printf("请输入学生信息："); scanf("%d %s",&s[i].id,s[i].name); } for(int i=0;i<n;i++){ rear_insert(L,s[i]); } output_link(L);break; case 2: //任意位置插入 printf("请输入要插入位置："); scanf("%d",&pos); sp=input_stu(sp); anypos_insert(L,pos,sp); output_link(L);break; case 3: //任意位置删除 printf("请输入要删除位置："); scanf("%d",&pos); anypos_delete(L,pos); output_link(L);break; case 4: //单链表逆置 rev_stulink(L); output_link(L);break; case 5: id_sort(L); output_link(L); break; case 6: //销毁单链表并退出程序 link_destroy(L); return 0; } } return 0; }
（3）功能函数编写
#include "link.h" Plink create() { Plink L=malloc(sizeof(links)); if(L==NULL) { printf("创建头节点失败\n"); return NULL; } L->next=NULL; L->len=0; printf("创建成功\n"); return L; } //任意位置删除 int anypos_delete(Plink L,int pos) { if(L==NULL||pos<1||pos>L->len) { printf("删除失败\n"); return -1; } Plink t=L; //t指针移至指定节点的前驱 for(int i=1;i<pos;i++) t=t->next; //p指针指向要删除节点 Plink p=t->next; //t指针链接要删除节点的后一节点 t->next=t->next->next; //长度-1 L->len--; //释放p节点 free(p); p=NULL; return 0; } //单链表逆置 int rev_stulink(Plink L) { if(L==NULL||L->len<1) { printf("逆置失败\n"); return -1; } //Q指针指向头节点下一节点 Plink Q=L->next; //t指向Q的下一节点 Plink t=Q->next; //后移直到next指向空 while(Q->next!=NULL) { //Q指针指向t节点下一节点 //单拎t节点 Q->next=t->next; //t节点放到头节点之后 t->next=L->next; //头节点链接t节点 L->next=t; //再次将t指针指向Q节点的下一节点 t=Q->next; } return 0; } //按学号排序 int id_sort(Plink L) { Plink j=L; //遍历次数 for(int i=1;i<L->len;i++) { //指针指向头节点后一节点 //后移直到j指针的next为空 for(j=L->next;j->next!=NULL;j=j->next) { //判断学号大小 if(j->xs.id>j->next->xs.id){ //结构体内容交换 stu temp=j->xs; j->xs=j->next->xs; j->next->xs=temp; } } } return 0; } //尾插法 int rear_insert(Plink L,stu s) { if(L==NULL) { printf("插入失败\n"); return -1; } Plink t=L; for(int i=0;i<L->len;i++) t=t->next; Plink p=malloc(sizeof(links)); p->xs.id=s.id; strcpy(p->xs.name,s.name); p->next=NULL; t->next=p; L->len++; return 0; } //输出函数 int output_link(Plink L) { if(L==NULL) { printf("该链表为空\n"); return -1; } Plink t=L; for(int i=0;i<L->len;i++) { t=t->next; printf("学号：%d\t姓名：%s\n",t->xs.id,t->xs.name); } printf("\n"); return 0; } //学生信息输入 Stu input_stu(Stu s) { s=malloc(sizeof(stu)); printf("请输入学生信息:"); scanf("%d %s",&s->id,s->name); return s; } //任意位置插入 int anypos_insert(Plink L,int pos,Stu s) { if(L==NULL||pos<1||pos>L->len+1) { printf("插入失败\n"); return -1; } Plink t=L; for(int i=1;i<pos;i++) t=t->next; Plink p=malloc(sizeof(links)); p->xs.id=s->id; strcpy(p->xs.name,s->name); p->next=t->next; t->next=p; L->len++; return 0; } //销毁单链表 int link_destroy(Plink L) { //链表为空销毁失败 if(L==NULL) { printf("销毁失败\n"); return -1; } //t指针指向单链表 Plink t=L; while(L!=NULL) { //t指针后移 t=t->next; //从头节点开始释放 free(L); //指向t L=t; } printf("销毁成功\n"); return 0; }
2.运行结果如图所示：
（1）尾插法插入学生信息
（2）任意位置插入学生信息
（3）任意位置删除学生信息
（4）单链表逆置
（5）按学号给学生排序
（6）销毁单链表并退出系统
