第二章 线性表
线性表定义
- 由n(n>=0) 个数据特性相同的元素构成的有限序列
n： 线性表的长度 n=0：空表
线性表实现
顺序表（顺序存储）
- 用一组地址连续的存储单元依次存储的线性表的数据元素
逻辑上相邻，物理上也相邻
由元素首地址和长度 两部分构成
B
基本操作：（文本语言实现）
-
初始化 O(1)
- 顺序表初始化 ，为顺序表再内存中开辟数据空间大小
- 定义一个变量elem指向这片空间的首地址
-
取值O(1)
- 判断i<=i<=length,若不符合，返回false
- 否则 取elem[i-1]
-
顺序表查找O(n)
给定要查找的元素，返回元素的位置
从第一个元素开始查找，依次和查找的元素比较，若要查找的元素与之相等，返回i+1
若整个顺序表都没有要查找的元素，查找失败，返回false
-
插入（ASL=n/2）
插入元素 插入位置i
1. 判断插入的位置是否合法 1<=i<=(length+1)- 判断顺序表是否满了，若满返回false
- 从n开始到i的元素依次向后移动一个位置(从后往前)
- 将插入的元素放入i位置
- 将顺序表的长度length+1
-
删除(ASL=(n-1)/2)
删除某个元素 ，删除位置
1. 判断i 是否合法 1<=i<=length,不合法返回false 2. 合法，将删除元素的位置i到n,依次向前移动一个位置 3. 讲顺序表长度length-1
链表
用一组任意的存储单元存储线性表的数据元素（逻辑上连续，物理不连续）
- 单链表：
image-20200403150956182
头指针 头节点 没有值 首元结点
单链表基本操作
**单链表初始化**
1. 生成一个新节点，作为头节点，用头节点L 指向头结点
2. 头结点指针域置空
<img src="https://i.loli.net/2020/05/22/j5sxF7ynmG13Z8B.png" alt="image-20200403151547792" style="zoom: 50%;" />
带头节点判空 L.next==NULL
不带头节点判空 L==NULL
单链表取值（n-1）/2
- 用指针p 指向首元结点，定义一个计数器j=1
- 从首元结点开始依次向后查看每一个要查的元素 若 p->data==c，返回查找元素
- 如果指针p 指向null还没有要查找的元素 返回false
单链表插入
1. 生成一个新结点，将数据域设置成E.
2. 将一个指针p 指向插入元素之前
3. 新节点的指针域zhi'xiang'g S 为定义新节点 （s->next=p.next p.next=s）
顺序表和单链表插入比较 如果插入数据量大 单链表好
如果要大量的查找 ，顺序表好
A
单链表删除
- 将指针p 移动到删除结点前
- 定义一个指针q 指向p的指针域
- 将p的指针域指向q的指针域
- 释放删除结点空间
循环链表(单项循环链表和双向循环链表)
对于循环链表如何判断 一个结点是否为最后一个结点
- p->next=L p指向的结点为最后一个结点
如何判断他是一个空表
- L->next==L; L的指针域还是L 哈哈 空表
如何判断一个单链表是最后一个结点
- p->next==null
-
双向循环链表
双向链表插入
若指针移动到插入之前p,将指针q插入其中
- q->prior=p;
- q->next=p->next;
- p->next->prior=q;
- p->next=q;
双向链表删除
指针移动到删除结点上p
p->next->prior=p->prior;
p->prior->next=p->next;
free(p)
存储密度
数据元素本身占用的存储量/结点结构占用的存储量
算法
线性表的合并
A和B两个线性表合并
A=(1,2,3,4)
B=(5,6,7,1,2)
先取A的表长 m和B的表长n
从B中第一个元素到最后一个元素查找，判定没一个元素是否在A中存在，若存在则插入
void merglist(List A,List B)
{
m=Length(A); //A的长度m
n=Length(B);//B的长度 n
for(int i=1;i<=n;i++) //遍历B的元素
{
GetElem(B,i,e); //取B中元素 赋值给e
if(!LocateElem(A,e))//如果e不存在A 顺序表中
{
ListInsert(A,++m,e);//将元素e 加入到A后面
}
}
}
顺序有序表合并
void meList(List A,List B,List *C)
{
m=Length(A); //A的长度
n=Length(B); //B的长度
LC=m+n; //C的长度
C=malloc(LC*sizeof(List)); // 初始化C
pA=A.elem; //将A的首地址指向pA
pB=A.elem; //将B的首地址指向pB
pc=C.elem; //将C的首地址指向pC
pA_last=PA+m-1; //将A的尾地址指向pA_last
pB_last=PB+n-1; //将B的尾地址指向pB_last
while(pA<=pA_last&&pB<=pB_last) //a表和b表都还没有到达表尾部
{
if(*pA<*pB) // 依次摘取两节点 小的结点插入c中
{
*pc++=*pA++；
}
else{
*pc++=*pB++；
}
}
while(pA<=pA_last) //如果A 没有查完，B 查完了，将A 剩下的元素插入C 后
{
*pc++=*pA++；
}
while(pA<=pA_last)
{
*pc++=*pB++； //如果B 没有查完 ，A 查完了，将B 剩下的元素插入c后
}
}
