单链表的创建，插入，删除以及查找

本文章依据学校的实验作业完成

目录

前言

一、链表是什么？

1.概念

2.链表的分类

二、单链表的创建，插入，删除以及查找

1.单链表的存储结构

2.单链表的创建

3.单链表的插入

4.单链表的删除

5.单链表的查找

6.主函数

7.完整代码

8.编译结果

三、总结

前言

链表是一种物理存储单元上非连续、非顺序的存储结构，由一系列结点组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

一、链表是什么？

1.概念

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

逻辑上连续是我们想象的连续，并不是真正的连续。

2.链表的分类

单向双向，带头结点不带头结点，循环非循环，组合起来共有8种

二、单链表的创建，插入，删除以及查找

1.单链表的存储结构

typedef int ElemType;//便于后期的修改//定义结点类型 typedef struct Node {ElemType data;//单链表中的数据域 struct Node *next;//单链表的指针域 }Node,*LinkedList;

2.单链表的创建

//单链表的建立（头插法）LinkedList ListCreatH() {Node *L;L = (Node *)malloc(sizeof(Node)); //申请头结点空间L->next = NULL;//初始化一个空链表int i=0;ElemType x; //x为链表数据域中的数据while(idata = x; //结点数据域赋值 p->next = L->next;//将结点插入到表头L-->|2|-->|1|-->NULL L->next = p; i++;}return L; } //单链表的建立（尾插法）(注：比较常用) LinkedList ListCreatT() {Node *L;L = (Node *)malloc(sizeof(Node)); //申请头结点空间L->next = NULL;//初始化一个空链表Node *r;r = L;//r始终指向终端结点，开始时指向头结点 int i=0 ; //x为链表数据域中的数据for(i=0;idata);r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL r = p; //将r结点移动到最后一个节点}r->next = NULL;//让r结点的指针域置空(链表创建完成)return L; }

3.单链表的插入

//单链表的插入，在链表的第i个位置插入x的元素/*初始条件：单链表L已存在，1<=i<=ListLength(L)*//*在L中第i个位置之前插入新的数据元素e，L的长度加1*/LinkedList ListInsert(LinkedList L,int i,ElemType x) {LinkedList pre;//pre为前驱结点 pre = L;int tempi = 0;for (tempi = 1; tempi next; //查找第i个位置的前驱结点 }Node *p;//插入的结点为pp = (Node *)malloc(sizeof(Node));p->data = x; //主要代码p->next = pre->next;//主要代码pre->next = p;return L; } 

4.单链表的删除

//单链表的删除，在链表中删除第i个数据元素/*初始条件：单链表L已存在，1<=inext;while(p->next&&jnext;++j;}if(!(p->next)||j>i)//第i个元素不存在printf("第i个元素不存在\n");q=p->next;p->next=q->next;//将q的后继赋值给p的后继 free(q);//释放q结点return L;} 

5.单链表的查找

//单链表的查找/*初始条件：单链表L已存在，1<=inext;//让p指向链表L的第一个结点while(p&&jnext;//让p指向下一个结点++j; } if(!p||j>i)//链表p为空否则链表长度过短 printf("第i个元素不存在");//第i个元素不存在*e=p->data;//取第i个元素的数据printf("%d\n",*e); }

6.主函数

int main() {LinkedList list,start; printf("请输入单链表的数据：\n"); list = ListCreatT();printf("成功创建链表：\n");for(start = list->next; start != NULL; start = start->next) {printf("%d ",start->data);}printf("\n");menu();int i,option;ElemType x;do{printf("请输入选项：");scanf("%d",&option);switch(option){ case 1:{ printf("请输入插入数据的位置：");scanf("%d",&i);printf("请输入插入数据的值：");scanf("%d",&x);ListInsert(list,i,x);printf("插入后的链表为：");//打印链表 for(start = list->next; start != NULL; start = start->next){printf("%d ",start->data);}printf("\n");break;}case 2:{int i; printf("请输入删除的位置\n");scanf("%d",&i);ListDelete(list,i);printf("删除后的链表为：");//打印链表for(start = list->next; start != NULL; start = start->next){printf("%d ",start->data);}printf("\n");break;}case 3:GetElem(list);break;case 0:break;default:printf("输出错误！\n");break; } }while(option>0);return 0;}

7.完整代码

#include #include  typedef int ElemType;//便于后期的修改//定义结点类型 typedef struct Node {ElemType data;//单链表中的数据域 struct Node *next;//单链表的指针域 }Node,*LinkedList; //建立菜单void menu() {printf("*****1.单链表的插入*****\n");printf("*****2.单链表的删除*****\n");printf("*****3.单链表的查找*****\n");printf("*****0. 退出 *****\n"); } //单链表的初始化 LinkedList LinkListInit() {Node *L;L = (Node *)malloc(sizeof(Node)); //申请结点空间 if(L == NULL) //判断是否有足够的内存空间{printf("申请内存空间失败\n");}L->next = NULL;//将next设置为NULL,初始长度为0的单链表return L;}//单链表的建立（头插法）LinkedList ListCreatH() {Node *L;L = (Node *)malloc(sizeof(Node)); //申请头结点空间L->next = NULL;//初始化一个空链表int i=0;ElemType x; //x为链表数据域中的数据while(idata = x; //结点数据域赋值 p->next = L->next;//将结点插入到表头L-->|2|-->|1|-->NULL L->next = p; i++;}return L; } //单链表的建立（尾插法） LinkedList ListCreatT() {Node *L;L = (Node *)malloc(sizeof(Node)); //申请头结点空间L->next = NULL;//初始化一个空链表Node *r;r = L;//r始终指向终端结点，开始时指向头结点 int i=0 ; //x为链表数据域中的数据for(i=0;idata);r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL r = p; //将r结点移动到最后一个节点}r->next = NULL;//让r结点的指针域置空 return L; }//单链表的插入，在链表的第i个位置插入x的元素/*初始条件：单链表L已存在，1<=i<=ListLength(L)*//*在L中第i个位置之前插入新的数据元素e，L的长度加1*/LinkedList ListInsert(LinkedList L,int i,ElemType x) {LinkedList pre;//pre为前驱结点 pre = L;int tempi = 0;for (tempi = 1; tempi next; //查找第i个位置的前驱结点 }Node *p;//插入的结点为pp = (Node *)malloc(sizeof(Node));p->data = x; p->next = pre->next;pre->next = p;return L; } //单链表的删除，在链表中删除第i个数据元素/*初始条件：单链表L已存在，1<=inext;while(p->next&&jnext;++j;}if(!(p->next)||j>i)//第i个元素不存在printf("第i个元素不存在\n");q=p->next;p->next=q->next;//将q的后继赋值给p的后继 free(q);return L;}//单链表的查找/*初始条件：单链表L已存在，1<=inext;//让p指向链表L的第一个结点while(p&&jnext;//让p指向下一个结点++j; } if(!p||j>i) printf("第i个元素不存在");//第i个元素不存在*e=p->data;//取第i个元素的数据printf("%d\n",*e); }int main() {LinkedList list,start; printf("请输入单链表的数据：\n"); list = ListCreatT();printf("成功创建链表：\n");for(start = list->next; start != NULL; start = start->next) {printf("%d ",start->data);}printf("\n");menu();int i,option;ElemType x;do{printf("请输入选项：");scanf("%d",&option);switch(option){ case 1:{ printf("请输入插入数据的位置：");scanf("%d",&i);printf("请输入插入数据的值：");scanf("%d",&x);ListInsert(list,i,x);printf("插入后的链表为：");//打印链表 for(start = list->next; start != NULL; start = start->next){printf("%d ",start->data);}printf("\n");break;}case 2:{int i; printf("请输入删除的位置\n");scanf("%d",&i);ListDelete(list,i);printf("删除后的链表为：");//打印链表for(start = list->next; start != NULL; start = start->next){printf("%d ",start->data);}printf("\n");break;}case 3:GetElem(list);break;case 0:break;default:printf("输出错误！\n");break; } }while(option>0);return 0;}

8.编译结果

三、总结

常考的知识点：链表的插入，删除的关键语句、在头部插入，中间插入，尾部插入的时间复杂度，以及单链表和顺序表的区别

在链表尾部添加（addLast()）需要从头遍历，时间复杂度为O(n)
在链表头部添加（addFirst()），时间复杂度为O(1)
在链表任意位置添加(add(int index,E e))，平均情况下为O(n/2)=O(n)

单链表和顺序表的区别：

顺序表的优点：

1. 元素可以随机存储
2. 节省存储空间
3. 元素位置可用一个简单、直观的公式表示并在常量时间内访问

顺序表的缺点：

1. 在作插入或删除操作时，需要移动大量元素

单链表的优点：

1. 链表是线性表的链式存储表示
2. 链表中逻辑关系相邻的元素不一定在存储位置上相连，用一个链(指针)表示元素之间的邻接关系即：链表中结点的逻辑顺序和物理顺序不一定相同
3. 在插入和删除时，不需要大量移动数据元素，只需找到结点，对该结点做删除和插入的工作即可

单链表的缺点：

在访问第i个位置的元素时，需要遍历链表，不能想顺序表一样直接找到第i个位置。