夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

2.3.2_3_单链表的建立_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表

查看资料信息、公开预览和下载状态。

共 9 页PDF · 673.0KB
下载

文档在线预览

公开展示前 5 页
100%
1
《2.3.2_3_单链表的建立_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第1页预览
2
《2.3.2_3_单链表的建立_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第2页预览
3
《2.3.2_3_单链表的建立_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第3页预览
4
《2.3.2_3_单链表的建立_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第4页预览
5
《2.3.2_3_单链表的建立_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第5页预览

本文档共 9 页 剩余 4 页未展示,请下载后查阅

下载

文档文本内容

本节内容
单链表
建立
王道考研/CSKAOYAN.COM知识总览
如果给你很多个数据元素(ElemType),要把它们存到一个单链表里
边,咋 neng 呢?
本节探讨带头
Step 1:初始化一个单链表
结点的情况
Step 2:每次娶一个数据元素,插入到表尾/表头
王道考研/CSKAOYAN.COM尾插法建立单链表
L 头 NULL
王道考研/CSKAOYAN.COM尾插法建立单链表
尾插法建立单链表:
初始化单链表
设置变量 length 记录链表长度
While 循环 {
每次取一个数据元素 e;
ListInsert (L, length+1, e) 插到尾部;
length++;
}
每次都从头开始之后遍历,
时间复杂度为 O(n2)
L 头 10 16 27 NULL
设置一个
length=3
表尾指针 r
王道考研/CSKAOYAN.COM尾插法建立单链表
后插操作
L 头 10 16 27 NU40LL
设置一个
表尾指针 r
王道考研/CSKAOYAN.COM尾插法建立单链表
LinkList List_TailInsert(LinkList &L){ //正向建立单链表
int x; //设ElemType为整型
L=(LinkList)malloc(sizeof(LNode)); //建立头结点 初始化空表
LNode *s,*r=L; //r为表尾指针
scanf("%d",&x); //输入结点的值
while(x!=9999){ //输入9999表示结束
s=(LNode *)malloc(sizeof(LNode)); O(n)
时间复杂度:
s->data=x; 在r结点之后插入元素 x
r->next=s;
r=s; //r指向新的表尾结点 永远保持 r 指向
最后一个结点
scanf("%d",&x);
}
r->next=NULL; //尾结点指针置空
return L;
}
如果不带头结点呢?
x 输入: 10 输入: 16 输入: 27 输入: 9999
L 头 10 16 27 NULL
r s
王道考研/CSKAOYAN.COM头插法建立单链表
对头结点的
后插操作
L 头 10 16 27 NULL
4101
头插法建立单链表:
初始化单链表
While 循环 {
每次取一个数据元素 e;
InsertNextNode (L, e);
}
王道考研/CSKAOYAN.COM头插法建立单链表
养成好习惯,只要是
初始化单链表,都先
LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表
把头指针指向 NULL
LNode *s; 如果去掉这
int x; 一句呢?
L=(LinkList)malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //初始为空链表
scanf("%d",&x); //输入结点的值
while(x!=9999){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode)); //创建新结点
s->data=x;
s->next=L->next;
L->next=s; //将新结点插入表中,L为头指针
scanf("%d",&x);
} 重要应用!!!
return L; 链表的逆置
}
如果不带头结点呢?
x 输入: 10 输入: 16 输入: 27 输入: 9999
一定要动手鸭
L 头 27 16 10 NULL
王道考研/CSKAOYAN.COM知识回顾与重要考点
头插法、尾插法:核心就是初始化操作、指定结点的后插操作
注意设置一个指向
表尾结点的指针
头插法的重要应用:链表的逆置
动手试一试:给你一个 LinkList L,
如何逆置?
L 头 27 16 10 NULL
王道考研/CSKAOYAN.COM