链式存储结构：结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻，又称为非顺序映像或链式映像，用一组物理位置任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置，链表中元素的逻辑次序和物理次序不一定相同
对数据元素ai来说，除了存储其本身的信息外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为结点（node）。它包括两个域：存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域
与链式存储有关的术语：
（1）结点：数据元素的存储映像，有数据域和指针域两部分组成
（2）链表：n个结点由指针链组成一个链表，它是线性表的链式存储映像，称为线性表的链式存储结构
（3）单链表：结点只有一个指针域的链表，称为单链表或线性链表
（4）双链表：结点有两个指针域的链表，称为双链表
（5）循环链表：首尾相接的链表称为循环链表
（6）头指针：是指向链表中第一个结点的指针
（7）首元结点：是指链表中存储第一个数据元素a1的结点
（8）头结点：是在链表的首元结点之前附设的一个结点
在链表中设置头结点有什么好处？
（1）便于首元结点的处理。首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无须进行特殊处理
（2）便于空表和非空表的统一处理。无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也统一了
头结点的数据域内装的是什么？
头结点的数据库可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值
链表（链式存储结构）的特点：
（1）结点在存储器上的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
（2）访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点（顺序存取法），所以寻找第一个结点和最后一个结点所花费的时间不等
单链表的存储结构：
typedef struct Lnode{ //声明结点的类型和指向结点的指针类型
ElemType data; //结点的数据域
struct Lnode next; //结点的指针域
}Lnode LinkList //LinkList为指向结构体Lnode的指针类型
单链表基本操作的实现：
（1）单链表的初始化
步骤：a）生成新结点作为头结点，用头指针L指向头结点
b）将头结点的指针域置空
（2）判断链表是否为空
空表：链表中无元素，称为空链表（头指针和头结点仍然在）
思路：判断头结点指针域是否为空
算法描述：
int ListEmpty(LinkList L){
if(L->next)//非空
return 0;
else
return 1;
}
（3）单链表的销毁：链表销毁后不存在
思路：从头指针开始，依次释放所有结点
算法描述：
Status DestroyList_L(LinkList &L){ //销毁单链表
Lnode p;//或LinkList p;
while(L!=NULL){
p=L;
L=L->next;
delete p;
}
return OK;
}
（4）清空单链表
链表仍存在，但链表中无元素，称为空链表（头指针和头结点仍然在）
思路：依次释放所有结点，并将头结点指针域设置为空
算法描述：
Status ClearList(LinkList &L){ //将L重置为空表
Lnode p,q;
p=L->next;
while(p!=NULL){ //没到表尾
q=p->next;
delete p;
p=q;
}
L->next=NULL; //头结点指针域为空
return OK;
}
（5）求单链表的表长
思路：从首元结点开始，依次计数所有结点
算法描述：
int ListLength_L(LinkList L){ //返回L中数据元素个数
LinkList p;
p=L->next; //p指向第一个结点
i=0;
while(p!=NULL){ //遍历单链表，统计结点数
i++;
p=p->next;
}
return i;
}
（6）取值——取单链表中第i个元素的内容
算法步骤：1）从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p=L->next
2）j做计数器，累计当前扫描过的结点数，j初值为1
3）当p指向扫描到的下一结点时，计数器j加1
4）当j==i时，p所指的结点就是要找的第i个结点
（7）查找
1)按值查找——根据指定数据获取该数据所在的位置（地址）
算法步骤：1）从第一个结点起，依次和e相比较
2）如果找到一个值与e相等的数据元素，则返回其在链表中的“位置”或地址
3）如果查遍整个链表都没有找到其值和e相等的元素，则返回0或者“NULL”
算法描述：
LNode LocateElem(LinkList L ,ElemType e){
//在线性表L中查找值为e的数据元素
//找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
p=L->next;
while(p&&p->data!=e)
p=p->next;
return p;
}
2)按值查找——根据指定数据获取该数据位置序列
//在线性表L中查找值为e的数据元素的位置序号
int LoacateElem_L(LinkList L, Elemtype e){
//返回L中值为e的数据元素的位置序号，查找失败返回0
p=L->next;j=1;
while(p&&p->data!=e)
{p=p->next;j++}
if(p) return j;
else return 0;
}
（8）插入——在第i个结点前插入值为e的新结点
算法步骤：1）首先找到ai-1的存储位置p
2）生成一个数据域为e的新结点s
3）插入新结点：a）新结点的指针域指向结点ai
b）结点ai-1的指针域指向新结点
算法描述：
//在L中第i个元素之前插入数据元素e
Status ListInsert_L(LinkList &L,int i ,ElemType e){
p=L;j=0;
while(p && j
if(!p|| j>i+1) return ERROR; //i大于表长+1或者小于1，插入位置非法
s=new LNode; s->data=e; //生成新结点s，将结点s的数据域置为e
s->next=p->next; //将结点s插入L中
p->next=s;
return OK;
}
（9）删除——删除第i个结点
算法步骤：1）首先找到ai-1的存储位置p，保存要删除的ai的值
2）令p->next指向ai+1
3）释放结点ai的空间
算法描述：
//将线性表L中第i个数据元素删除
Status ListDelete_L(LinkList &L,int i,ElemType &e){
p=L;j=0;
while(p->next && j
if(!(p->next)||j>i-1) return ERROR; //删除位置不合理
q=p->next; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
e=q->data; //保存删除结点的数据域
delete q; //释放删除结点的空间
return OK;
}
（10）建立单链表
1）头插法——元素插入在链表头部，也叫前插法
a）从一个空表开始，重复读入数据
b）生成新结点，将读入数据存放到新结点的数据域中
c）从最后一个结点开始，依次将各结点插入到链表的前端
算法描述：
void CreateList_H(LinkList &L,int n){
L= new LNode;
L->next = NULL;//先建立一个带头结点的单链表
for(i=n;i>0;—i){
p=new LNode;//生成新结点
cin>>p->data;//输入元素值
p->next = L->next;//插入到表头
L->next = p;
}
2)尾插法——元素插入在链表尾部，也叫后插法
a）从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点
b）初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点
算法描述：
//正位序输入n个元素的值，建立带表头结点的单链表L
void CreateList_R(LinkList &L,int n){
L=new LNode; L->next =NULL;
r=L;//尾指针r指向头结点
for(i=0;i
r->next = p;//插入到表尾
r=p;//r指向新的尾结点
}
单链表时间效率分析
1.查找
因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)
2.插入和删除
因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)
但是，如果要在单链表中进行前插或者删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)
若有收获，就点个赞吧
0 人点赞
