线性表的链式存储结构定义
结点
结点由存放数据元素的数据域和存放后继结点地址的指针域组成。
线性表的线性存储结构(也叫单链表)
n个结点链成一个链表，即为线性表的链式存储结构。
头结点
在单链表的第一个结点前附设一个头结点，头结点的数据域可以不存储任何数据，头结点的指针域存储指向第一个结点的指针，链表可以没有头结点。
头指针
头指针是链表指向第一个结点的指针，如果链表有头结点，头指针指向头结点。
空表
- 有头结点的空表，头指针指向头结点，头结点的指针域为空。
- 没有头结点的空表，头指针为空。
数组与链表对比
- 数组是内存上一段连续的存储空间
- 链表是内存上非连续，非顺序的存储空间(结构)。
- 数组是线性表的顺序存储结构
- 链表是线性表的链式存储结构
单链表的读取
获得链表第i个数据的方法，定义一个指针，从链表第一个数据开始遍历，不断指向下一个结点，直到第i个。
单链表的插入
- 单链表第i个数据插入结点s
遍历链表寻找i-1结点，记为p结点。让原p的后继结点改成s的后继结点，s结点变成p的后继结点。
s->next=p->next;
p->next=s; - 伪代码
/* LinkList是链表类，ElemType是一种数据类型，ListInsert是单链表第i个数据插入结点的算法*/
void ListInsert(LinkList L,int i,ElemType e){
LinkList p,s; //结点p、s
p=L;//p结点是指向链表L第一个结点的指针
//寻找第i-1个结点
int j=1；
while(j<i){//遍历寻找i-1个结点，让指针p指向它。只要j<i,指针p就向后移动，指向下一个结点，直到j=i;跳出循环，此时p指向第i-1结点。
p=p->next;
++j;
}
定义结点s的值和插入位置
s->data=e;//结点s的值是e
p->next=s->next;//将p的后继结点赋值给s的后继
p->next=s;//将s赋值给p的后继
}
-
图
1.jpg
2.jpg
单链表的删除
- 删除链表的第i个结点。
遍历链表，寻找第i-1个结点，把i-1结点的后继改成i+1结点。 -
图
微信图片_20180912214450.jpg - 伪代码
/* LinkList是链表，ElemType是数据类型，ListDelete是删除链表第i个结点的方法*/
void ListDelete(LinkList L,int i,ElemType e){
LinkList p,s;//
p=L;//结点p是指向链表L第一个元素的指针
int j=1;
//遍历寻找第i-1个结点，指针p指向i-1结点
while(j<i){
p=p->next
++j;
}
//p的后继的后继结点赋值给p的后继
p->next=p->next-next;
}
线性表的顺序存储结构与线性表的链式存储结构(单链表)分析
- 第i个位置插入或删除结点
1.对于线性表的顺序存储结构，每一次插入结点或者删除结点，都需要移动n-i个结点。时间复杂度O(n)
2.对于单链表，只需要赋值移动指针而已。时间复杂度O(1) - 读取第i个位置的数据
- 顺序表的顺序存储结构，支持下标来访问元素，可以直接获取第i个元素，时间复杂度O(1)。
- 链表的链式存储结构，想要获取第i个数据，只能从第一个结点开始遍历,每次指针往后移动一次，最多需要移动n次才能获取第i个数据(i=n)。时间复杂度O(n)
