完整代码在最后
一.单链表基本操作
1.初始化
1）创建结构体，储存节点的数据+指针域； 2）创建指向结构体的指针； 3）用结构体定义单链表； 4）初始化链表头节点：为头节点开辟内存； 5）判断内存是否开辟成功； 6）头节点的指针域置空，使链表长度为0。
typedef struct Node//1{ ElemType data; struct Node *next;}Node;typedef struct Node *LinkList;//2Status InitList(LinkList& L)//3{ L=(Node*)malloc(sizeof(Node));//4 if(L==NULL)//5 { printf("申请内存空间失败\n"); } L->next=NULL;//6}2.创建单链表（尾插法）
1）生成新结点p和尾结点r； 2）为新节点开辟内存； 3）存入数据域； 4）存入指针域：把原来的尾结点指针域存入，即在末尾插入p； 5）更新r，使其依然为链表尾结点； 6）尾结点指针域置空
void CreateListTail(LinkList *L,int n){ LinkList p,r;//1 while(n--) { p=(Node*)malloc(sizeof(Node));//2 scanf("%d",&p->data);//3 r->next=p;//4 r=p;//5 } r->next=NULL;}3.整表清除
1）结点p储存头结点； 2）判断p是否到表尾，没到就进入以下循环； a.结点q指向p下一个结点； b.释放p结点； c.p指向q结点。 3）头指针置空，相当于初始化链表。
注：不能用p=p->next代替q，∵在free(p)时也释放了指针域，∴p->next不存在。
Statue ClearList(ListLine *L){ ListLine p,q; p=(*L)->next;//1 while(p)//2 { q=p->next;//a free(p);//b p=q;//c } (*L)->next=NULL; }4.获取第 i 个元素
1）用p指向链表第一个元素； 2）用j遍历链表，直到找到i或p已经到链表结尾，即p=NULL； 3）如果没找到，p指向下一个结点； 4）若退出循环时p为NULL或i元素不存在，则返回ERROR； 5）若找到就把数据存入。
Statue GetElem(LinkList *L,int i,int *e){ int j=1; p=(*L)->next;//1 while(jnext;//3 j++; } if(j>i||!p)//4 { return ERROR; } *e=p->data;//5 return OK;}5.插入元素
在第i位后插入元素e。变成a，e，a+1。
1）遍历链表找到第i位； 2）创立要插入的新节点s； 3）开辟新节点s的内存； 4）s的数据域存入e； 5）连接e与a+1：把a+1的指针域给新结点s； 6）连接a与e：把s给a的指针域。
Statue ListInsert(LinkList *L,int i,ElemType e){ //1 int j=1; LinkList p; p=(*L)->next;//p从头开始找：将链表头结点给p while(p&&jnext; j++; } if(!p||j>i) { return ERROR; } LinkList s;//2 s=(Node*)malloc(sizeof(Node));//3 s->data=e;//4 s->next=p->next;//5 p->next=s;//6 return OK;}6.删除元素
删除i位的元素，并把删除的元素值返回到e中。
1）遍历列表找到i位，注：∵要删除p->next结点，∴p->next不能为NULL； 2）将预删除的结点储存在q内； 3）将p->next赋值为q->next,即进行了p->next=p->next->next操作; 4）把q里的数据——需删除的数据，给e； 5）释放结点q。
Statue ListDelete(LinkList *L,int i,ElemType *e){ //1 int j=1; LinkList p; p=(*L)->next; while(p->next&&jnext; j++; } if(!(p->next)||j>i) { return ERROR; } LinkList q; q=p->next;//2 p->next=q->next;//3 *e=q->data;//4 free(q);//5 return OK;}7.输出链表
void OutPutList(LinkList *L){ LinkList p; p=(*L)->next; while(p) { printf("%d\n",p->data); }}完整代码
#include#include#include//用于生成随机数typedef int Status;//用Status来进行替代int,方便数据类型的修改typedef int ElemType;#define OK 1;#define ERROR 0;//单链表储存结构typedef struct Node//定义结构体LNode{ElemType data;//结点数据域struct Node* next;//结点指针域}Node;typedef struct Node* LinkList;//LinkList为指向结构体Node的指针类型//初始化一个空的单链表LStatus InitList(LinkList& L) //InitList()顺序表的初始化函数{ L = (Node*)malloc(sizeof(Node)); //申请空间，生成新结点作为L头结点if (L == NULL) //判断是否有足够的内存空间{printf("申请内存空间失败\n"); }L->next = NULL; //头结点的指针域置空，初始长度为0return OK;}//尾插法创建链表void CreateListTail(LinkList* L, int n)//*L即调用已经存在的线性表L{LinkList p, r;//L：指整个单链表；p：需创建的新节点；r：指向尾结点的变量。r = *L;//r指向尾部节点printf("1.输入初始数据\n2.自动生成数据\n");//链表生成类型选择int a;scanf("%d", &a);if (a == 1) {while (n--) {p = (Node*)malloc(sizeof(Node));//为新结点开辟内存scanf("%d", &p->data);//读取数据r->next = p;//在原来的尾结点r后存入r = p;//更新尾结点 }r->next = NULL;//链表结束 } else if(a==2) {srand(time(0));//初始化随机数种子r = *L;//r指向链表尾部while (n--) {p = (Node*)malloc(sizeof(Node));//生成新结点p->data = rand() % 100 + 1;//随机产生100以内的数r->next = p;//将新结点添加到表尾r = p;//更新尾结点：将新结点更新为尾结点 }r->next = NULL;//表示链表结束 }printf("链表创建成功！\n");}//整表删除，即变成空表Status ClearList(LinkList* L){LinkList p, q;p =(*L)->next;//使p指向线性表第一个结点while (p)//如果p不为NULL {q = p->next;//q指向p的下一个结点,防止释放p后找不到下一个结点free(p);//释放p结点p = q;//p指向下一个结点 } (*L)->next = NULL;//使头结点为空，相当于链表初始化时的操作return OK;}//查找，读取元素，获取第i个元素数据,返回到eStatus GetElem(LinkList *L, int i, ElemType* e){int j=1;//计数,最后一个结点是NULL，不需要遍历∴从1开始计LinkList p;p=(*L)->next;//p从头结点开始找//遍历链表，找到第i个元素while (j next;//指向下一个结点j++; }if (!p||j>i)//p为空||不存在i结点时 {printf("出错！查找位置在链表之外！\n");return ERROR; }*e = p->data;return OK;}//在位置i插入元素e,使链表成为 a，e，a+1Status ListInsert(LinkList* L, int i, ElemType *e){//先遍历找到第i个结点int j=1;LinkList p;p = (*L)->next;//p指向链表头结点if (i == 0)//头结点插入特判 {LinkList s;s = (Node*)malloc(sizeof(Node));s->data = *e;//存数据域s->next = (*L)->next;//把原头结点给s的下一个结点 (*L)->next = s;//更新新结点printf("成功！\n");return OK; }while (j next;j++; }if (!p || j > i)//没找到 {printf("出错！插入位置在链表之外！\n");return ERROR; }//找到位置后插入LinkList s;//创建要插入的新结点s= (Node*)malloc(sizeof(Node));//为新节点开辟内存s->data = *e;//储存数据域s->next = p->next;//将p后继结点给s的后继，即连接e和a+1p->next = s;//将s给p的后继，即连接a和eprintf("成功！\n");return OK;}//删除第i个元素，并用e返回其值Status ListDelete(LinkList* L, int i, ElemType* e){//遍历找到第i个结点int j=1;LinkList p;p = (*L)->next;if (i == 1)//若是头结点需特判 {*e = p->data; (*L)->next = p->next;//使链表头结点直接指向下一个printf("删除元素的值为：%d\n", *e);printf("成功！\n");return OK; }i--;while (j next)//∵需删除p后的结点，∴p->next必须存在 {p = p->next;j++; } if (!(p->next) || i next;//将预删除的结点给qp->next = q->next;//p连接需删除结点后的结点，即p->next=p->next->next*e = q->data;//删除结点中的数据给efree(q);//释放删除的结点printf("删除元素的值为：%d\n", *e);printf("成功！\n");return OK;}//输出链表void OutPutList(LinkList* L){LinkList p;p = (*L)->next;while (p) {printf("%d\n", p->data);p = p->next; }}int main(){Node *L;int n,i,e,q;InitList(L);//目录printf(" 目录\n");printf("1.创建链表\n2.查找列表元素\n3.清空链表\n4.插入元素\n5.删除元素\n6.输出链表\n\n");while (~scanf("%d", &q)) {if (q == 1) {printf("请输入链表数据个数：\n");scanf("%d", &n);CreateListTail(&L, n); }else if (q == 2) {scanf("%d", &i);GetElem(&L, i, &e); }else if (q == 3) {ClearList(&L);printf("链表已清空！\n"); }else if(q==4) {printf("请输入需插入的位置：\n");scanf("%d", &i);printf("请输入需插入元素的值：\n");scanf("%d", &e);ListInsert(&L, i, &e); }else if (q == 5) {printf("请输入需删除的元素位置：\n");scanf("%d", &i);ListDelete(&L, i, &e); }else if (q == 6) {printf("\n");OutPutList(&L); }printf(" 目录\n");printf("1.创建链表\n2.查找列表元素\n3.清空链表\n4.插入元素\n5.删除元素\n6.输出链表\n\n"); }return 0;}运行截图：
