当前位置:
首页 > Python基础教程 >
-
单链表的创建，插入，删除以及查找
前言
链表是一种物理存储单元上非连续、非顺序的存储结构，由一系列结点组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
一、链表是什么？
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(i<10) {
Node *p;
p = (Node *)malloc(sizeof(Node)); //申请新的结点
scanf("%d",&x);
p->data = 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;i<10;i++)
{
Node *p;
p = (Node *)malloc(sizeof(Node)); //申请新的结点
scanf("%d",&p->data);
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 < i; tempi++) {
pre = pre->next; //查找第i个位置的前驱结点
}
Node *p; //插入的结点为p
p = (Node *)malloc(sizeof(Node));
p->data = x; //主要代码
p->next = pre->next; //主要代码
pre->next = p;
return L;
}
4.单链表的删除
//单链表的删除，在链表中删除第i个数据元素
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*操作结果：删除L的第i个数据元素，L的长度减1*/
LinkedList ListDelete(LinkedList L,int i)
{
LinkedList p,q;
int j=2;
p = L->next;
while(p->next&&j<i) { //查找第i个位置
p=p->next;
++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<=i<=ListLength(L)*/
/*操作结果：用e打印中第i个数据元素的值*/
void GetElem(LinkedList L)
{
int i,j=1; //j为计数器
int *e;
LinkedList p; //声明一结点p
printf("请输入查找的位置:");
scanf("%d",&i);
p=L->next; //让p指向链表L的第一个结点
while(p&&j<i) //p不为空且到达i结点
{
p=p->next; //让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 <stdio.h>
#include <stdlib.h>
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(i<10) {
Node *p;
p = (Node *)malloc(sizeof(Node)); //申请新的结点
scanf("%d",&x);
p->data = 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;i<10;i++)
{
Node *p;
p = (Node *)malloc(sizeof(Node)); //申请新的结点
scanf("%d",&p->data);
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 < i; tempi++) {
pre = pre->next; //查找第i个位置的前驱结点
}
Node *p; //插入的结点为p
p = (Node *)malloc(sizeof(Node));
p->data = x;
p->next = pre->next;
pre->next = p;
return L;
}
//单链表的删除，在链表中删除第i个数据元素
/*初始条件：单链表L已存在，1<=i<=ListLength(L)*/
/*操作结果：删除L的第i个数据元素，L的长度减1*/
LinkedList ListDelete(LinkedList L,int i)
{
LinkedList p,q;
int j=2;
p = L->next;
while(p->next&&j<i) { //查找第i个位置
p=p->next;
++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<=i<=ListLength(L)*/
/*操作结果：用e打印中第i个数据元素的值*/
void GetElem(LinkedList L)
{
int i,j=1; //j为计数器
int *e;
LinkedList p; //声明一结点p
printf("请输入查找的位置:");
scanf("%d",&i);
p=L->next; //让p指向链表L的第一个结点
while(p&&j<i)
{
p=p->next; //让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)
单链表和顺序表的区别：
顺序表的优点：
元素可以随机存储
节省存储空间
元素位置可用一个简单、直观的公式表示并在常量时间内访问
顺序表的缺点：
在作插入或删除操作时，需要移动大量元素
单链表的优点：
链表是线性表的链式存储表示
链表中逻辑关系相邻的元素不一定在存储位置上相连，用一个链(指针)表示元素之间的邻接关系即：链表中结点的逻辑顺序和物理顺序不一定相同
在插入和删除时，不需要大量移动数据元素，只需找到结点，对该结点做删除和插入的工作即可
单链表的缺点：
在访问第i个位置的元素时，需要遍历链表，不能想顺序表一样直接找到第i个位置。
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/Lookdrama/article/details/127466859
栏目列表
最新更新
python爬虫及其可视化
使用python爬取豆瓣电影短评评论内容
nodejs爬虫
Python正则表达式完全指南
爬取豆瓣Top250图书数据
shp 地图文件批量添加字段
爬虫小试牛刀（爬取学校通知公告）
【python基础】函数-初识函数
【python基础】函数-返回值
HTTP请求：requests模块基础使用必知必会
SQL SERVER中递归
2个场景实例讲解GaussDB(DWS)基表统计信息估
常用的 SQL Server 关键字及其含义
动手分析SQL Server中的事务中使用的锁
openGauss内核分析：SQL by pass & 经典执行
一招教你如何高效批量导入与更新数据
天天写SQL，这些神奇的特性你知道吗？
openGauss内核分析：执行计划生成
[IM002]Navicat ODBC驱动器管理器 未发现数据
初入Sql Server 之 存储过程的简单使用
uniapp/H5 获取手机桌面壁纸 (静态壁纸）
[前端] DNS解析与优化
为什么在js中需要添加addEventListener（）？
JS模块化系统
js通过Object.defineProperty() 定义和控制对象
这是目前我见过最好的跨域解决方案！
减少回流与重绘
减少回流与重绘
如何使用KrpanoToolJS在浏览器切图
performance.now() 与 Date.now() 对比