定义：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。
在链式存储结构中，每个数据元素除了要存储数据元素信息外，还要存储它的后继元素的存储地址(指针).我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储印象，称为结点(Node)。
n个结点链接成一个链表，即为线性表(a1,a2,a3,…,an)的链式存储结构
因为此链表的每个结点中只包含一个指针域，所以叫做单链表
我们把链表中的开始结点的存储位置叫做头指针，最后一个结点的指针为空(NULL)
单链表
1.头指针、头结点、开始结点
开始结点：指链表中的第一个结点，它没有直接前驱
头指针：指向开始结点的指针(没有头结点的情况下,若链表有头结点，则是指向头结点的指针)，一个单链表可以由其头指针唯一确定，一般用其头指针来命名单链表，无论链表是否为空，头指针均不为空，头指针是链表的必要元素
单链表头指针示例图
头结点：头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义(但也可以用来存放链表的长度)，有了头结点，对在第一元素节点前插入节点和删除第一节点起操作与其它节点的操作就统一了，头结点不一定是链表的必须元素
包含头结点的单链表
空链表示例图
2.单链表的定义
//结点的定义
typedef struct Node{
ElemType data;//数据域
struct Node *next;//指针域
}Node;
typedef struct Node *LinkList;
我们可以看到节点由存放数据元素的数据域和存放后继结点地址的指针域组成
问题:
如果p->data = ai,那么p->next->data = ?
答案: p->next->data = ai+1
3.单链表的读取
获取链表第i个数据的算法思路：
— 声明一个结点p指向链表第一个结点，初始化j从1开始
— 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j++
— 若到链表末尾p为空，则说明第i个元素不存在
— 否则查找成功，返回结点p的数据
GetElem
/**
使用头指针表示单链表 LinkList L表示头指针
*/
Status GetElem(LinkList L,int i,ElemType *e){
LinkList p = L->next;//获取头结点的指针 p代表第一个结点
int j = 1;//赋值为1的意思是此单链表没有头结点，如果有头结点赋值给0即可
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
return ERROR;
}
*e = p->data;
return OK;
}
可以看出，此算法的时间复杂度为O(n),此算法的核心思想叫做”工作指针后移”,这其实也是很多算法的常用技术
4.单链表的插入
单链表第i个数据插入结点的算法思路：
— 声明一个节点p指向链表头结点，初始化j从1开始
— 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
— 若到链表末尾p为空，则说明第i个元素不存在
— 否则查找成功，在系统中生成一个空结点s
— 将数据元素e复制给s->data
— 将i的next赋值给s,将i的next指向s
— 返回成功
ListInsert
/*
LinkList *L是一个二级指针，代表指向头指针的指针
插入的时候，在第i个位置插入结点，
也就是在之前在第i个位置的的结点之前插入一个新的结点，
所以插入的时候是获取第i个位置之前的结点的指针进行操作。
*/
Status listInsert(LinkList *L,int i,ElemType e){
int j = 1;
LinkList p,s;
p = *L;//这里就代表p指向第一个结点，即头指针
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {//如果没找到
return ERROR;
}
//下面表示找到了
s = (LinkList)malloc(sizeof(Node));//初始化结点s
s->data = e;//数据域赋值
//指针域赋值
s->next = p->next;
p->next = s;
return OK;
}
单链表的插入示例图
5.单链表的删除
单链表第i个数据删除结点的算法思路:
— 声明结点p指向链表的第一个结点，初始化j=1
— 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
— 若到链表末尾p为空，则说明第i个元素不存在
— 否则查找成功，将欲删除结点p->next赋值给q
— 单链表的删除标准语句p->next = q->next
— 将q结点中的数据复制给e，作为返回
— 释放q结点
ListDelete
/*
LinkList *L是一个二级指针，代表指向头指针的指针
删除的时候，在第i个位置删除结点，
也就是在将i-1位置结点的指针指向i+1的结点，然后释放第i个结点，
*/
Status listDelete(LinkList *L,int i,ElemType *e){
int j = 1;
LinkList p = *L;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
return ERROR;
}
LinkList q = p->next;
*e = q->data;
p->next = q->next;
free(q);
return OK;
}
单链表的插入与删除
6.单链表与线性表的顺序存储结构的效率PK
在单个元素插入与删除算法中，单链表的时间复杂度为O(n),线性表的顺序存储结构的时间复杂度也为O(n)，效率差别不大。
但是，如果我们希望从第i个位置开始，插入连续10个元素，对于顺序存储结构而言，每次插入都要移动n-i个位置，所以每次都是O(n)
而单链表，我们只需要在第一次时候，找到第i个位置的指针，此时为O(n),接下来只是简单的通过赋值移动指针而已，时间复杂度为O(1)
显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显
7.单链表的整表创建
顺序存储结构的线性表的整表创建，我们可以用数组的初始化来直观理解。单链表不同，它的数据可以是分散的，它的增长是动态的，所以它的创建是根据系统情况和实际需求即时生成。
创建单链表的过程是一个动态生成链表的过程，从“空表”的初始状态起，依次建立各元素结点并逐个插入链表。
创建单链表的算法思路:
— 声明一结点p和计数器变量i
— 初始化一个空链表L
— 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
— 循环实现后继结点的赋值和插入
.头插法建立单链表
头插法是从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。
简单来讲，就是把新加入的元素放在表头后的第一个为止：
— 先让新结点的next指向头结点之后
— 然后让表头的next指向新节点
CreateListHead
/*
头插法每次新插入的结点都放在第一位
*/
void CreateListHead(LinkList *L,int n){
//创建头结点
LinkList p = (LinkList)malloc(sizeof(Node));
*L = p;
p->next = NULL;
srand(0);
//循环创建结点
for (int i = 1; i <= n; i++) {
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 + 1;
//核心代码:新结点插入在头结点之后
p->next = (*L)->next;
(*L)->next = p;
}
}
.尾插法创建单链表
头插法建立链表虽然算法简单，但生成的链表中结点的次序与输入的顺序相反
尾插法刚好相反，每次把新结点都插入到最后，这种算法称之为尾插法
CreateListTail
void CreateListTail(LinkList *L,int n){
//创建头结点
LinkList p = (LinkList)malloc(sizeof(Node));
*L = p;
//中间变量r
LinkList r = p;
srand(0);
for (int i = 1; i <= n; i++) {
//创建新结点
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 + 1;
//将前面结点的next指向新结点
r->next = p;
//让中间变量r指向新结点，作为后面创建结点的前驱
r = p;
}
r->next = NULL;//将最后一个结点的next置为NULL
}
8.单链表的整表删除
单链表整表删除的算法思路如下:
— 声明结点p和q
— 将第一个结点赋值给p，下一结点赋值给q
— 循环执行释放p和将q赋值给p的操作
ClearList
Status clearList(LinkList *L){
LinkList p = (*L)->next;
LinkList q;
while (p) {
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}
9.单链表结构与顺序存储结构的优缺点
存储分配方式：
— 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
— 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能：
— 查找
. 顺序存储结构O(1)
. 单链表O(n)
— 插入和删除
. 顺序存储结构需要平均移动表长一般的元素，时间为O(n)
. 单链表在计算出某位置的指针后，插入和删除时间仅为O(1)
空间性能:
-- 顺序存储结构需要预分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出
-- 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
结论:
— 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构
— 若需要频繁插入和删除时，宜采用单链表结构
10.单链表小结腾讯面试题
.题目：快速找到未知长度的单链表的中间节点
普通方法思路：
首先遍历一遍单链表以确定单链表的长度L，然后再次从头结点触发循环L/2次找到单链表的中间节点,其算法复杂度为：O(L+L/2) = O(3L/2)
巧妙方法:
利用快慢指针原理：设置两个指针*search、*mid都指向单链表的头结点。其中*search的移动速度是*mid的两倍，当*search指向末尾结点的时候，mid正好就在中间了，这也是标尺的思想
Status GetMiddleNode(LinkList L,ElemType *e){
//使用快慢指针方法 search遍历到末尾，mid速率是search的一半
LinkList search,mid;
mid = search = L;
while (search->next != NULL) {
if (search->next->next != NULL) {
search = search->next->next;
mid = mid->next;
} else {
search = search->next;
}
}
*e = mid->data;
return OK;
}
网友评论