数据结构--单链表创建、增删改查功能以及与结构体合用

一、作业要求

单链表操作，要求节点是结构体类型，实现以下功能：

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;//长度-1L->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);//指向tL=t;}printf("销毁成功\n");return 0;
}

2.运行结果如图所示：

（1）尾插法插入学生信息

 （2）任意位置插入学生信息

 （3）任意位置删除学生信息

 （4）单链表逆置

 （5）按学号给学生排序

（6）销毁单链表并退出系统