线性表（二）

客官°小女子只卖身不卖艺 2022-05-31 13:48 123阅读 0赞

**1.什么是线性表**

线性表是0个或多个数据元素的有限序列。

线性表的操作：  
InitList(\*L) //初始化线性表 空表  
ListEmpty(L) //判断 线性表是否为空 true/false  
ClearList(\*L) //清空线性表  
GetElem(L,i,&e) //将线性表L 中第i个位置元素 返回给e  
LocateElem(L,e) //查找e在线性表l中的位置 没有的话返回0  
ListInsert(\*L,i,e) //在第i个位置插入e  
ListDelete(\*L，i,\*e) // 删除第i个位置的元素 并返回个e  
ListLength(L) //返回线性表元素个数

**顺序存储的定义**  
线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表中的数据元素。  
就是 java中的数组。

获取元素的时间复杂度是 O(1)  
LOC（ai-1） = LOC（ai） +C //C是一个数据元素占用几个存储单元

第i个元素位置  
LOC(ai) = LOC(a1)+(i-1)\*c

**顺序存储结构的优缺点**  
优点：  
1.无需为表中的元素之间的逻辑关系而添加额外的存储位置。  
2.快速查询表中任意元素的位置。  
缺点：  
1.插入和删除都需要移动大量的元素。  
2.线性表长度变化大时，无法确定存储空间容量 因为需要一开始指定容量大小  
3.容易造成存储空间的碎片 。

**链式存储结构**。

每个节点都有一个前驱元素和后继元素。  
为了表示每个节点与其后继元素之间的逻辑关系 除了存储元素本身的信息之外，还需要存储指示其后继元素地址的信息。

即将节点分为了**数据域和指针域**  
**数据域存储数据元素信息。**  
**指针域存储后继元素的位置**

链表有 以下几种：  
单链表 静态链表 循环链表 双向链表

以单链表为例  
单链表的新增元素

节点p -> 节点q

要在节点p和节点q 中插入一个 节点s

操作为：

s->next = p->next
    p->next = s

单链表 删除节点  
节点p -> 节点p next -> 节点p next next

要想删除中间的 节点p next 则需要

p->next = p->next->next

**链式存储 中单链表的结构和 顺序存储结构之间的优缺点。**

1.存储  
单链表中的内存分配 可以不连续  
顺序存储 必须是连续的存储单元  
2.时间复杂度  
单链表中查询一个元素的复杂度为O(n)  
顺序存储查询仅为O(1)  
单链表新增和删除的复杂度为O（1）  
顺序存储新增和删除需要O（n）  
3.空间性能  
顺序空间存储需要预分配空间 确定长度 扩容麻烦  
链式存储不需要分配 元素个数不受限制。

**静态链表、循环链表**  
用数组描述的链表 叫做静态链表 即 两个数据域 一个存数据 另一个存下一个数据元素的下表 循环链表即将最后节点指向头结点 这里不做赘述。

**双向链表**  
即节点除了拥有数据域和next之外 还能指向前驱元素的位置  
拥有 data 、prisor、next  
p->next 指向下一个数据元素位置 p-prisor 指向上一个数据元素位置

双向链表的插入

节点p -> 节点p next

要在节点p 和 节点p-next 插入 节点s  
需要四步  
1.确定s的后继指针  
2.确定s的前驱指针  
3.修改p next的前驱指针指向s  
4.修改p 的后继指针指向s

详细操作为：

s->next = p->next
    s-prisor = p
    p-next-prisor = s 
    p-next = s

双向链表的删除

p的前驱元素(A) p p的后继元素 (B)

要想删除p 需要  
将p的前驱元素的后继指针指向p的后继元素 ====A的后继指针指向B  
将p的后继元度的前驱指针指向p的前驱元素 =====B的前驱指针指向A

详细操作为：

p->prisor->next = p->next 
    p->next->prisor = p->prisor