数据结构链表部分PPT课件

i位置 1 2
︰ i ︰
n n+1
移动次数 n n-1 ︰ n-i+1
0
︰ 1
最好情况下：T(n)=O(1)
最坏情况下：T(n)=O(n)
平均时间复杂度：
长度为n的顺序表中，插入一个结点，令E(n)表 示移动结点的期望值(移动平均次数)，在表中第 i个位置插入一个结点移动的次数为n-i+1.
else{ for (j=L.length; j>i-1; j--) L.a[j]=L.a[j-1]; L.a[i-1]=e; L.length++;
} }
插入操作时间复杂度分析
这里的问题规模是表的长度，设它的值为n。该 算法的时间主要花费在循环的元素后移语句上，所需 移动元素的次数不仅依赖于表的长度，而且还与插入 位置有关。
5. i是数据元素ai在线性表中的位序 (1≤i ≤ n)
二、抽象数据类型线性表的定义
ADT List {
数据对象：D={ai︱ai ∈Elemset, i=1,2,…,n , n≥0} 数据关系：R1={< ai-1 , ai > ︱ ai-1 , ai ∈D, i=2, …,n}
基本操作：
构造、销毁、置空、判空、获取元素、插入、删除、 定位等。
L.length=0; } Sqlist Sl;
initlist(Sl);
建立顺序表
void creat_sqlist(Sqlist &L) {
int i,n; cout<<"n=?; cin>>n; L.length=n; for (i=0; i<n; i++) cin>>L.a[i]; }
输出顺序表
void insert_sq(Sqlist &L, int i, ElemType e) {
int j; if (L.length==MAXSIZE) cout<<"ERROR! "<<endl; else
if (i<1 || i>L.length+1) cout<<"ERROR! "<<endl;
顺序表是一种随机存取的存储结构。
高级语言中一般用数组来描述顺序存储。 #include<stdio.h> #define MAXSIZE 100 typedef int ElemType; typedef struct{
ElemType a[MAXSIZE]; int length; }Sqlist;
n 1
E(n) pi * (n i 1) i 1
其中pi表示在表中第i位置插入结点的概率。Pi＝ 1/(n+1)
计算得 E(n)=n/2，所以平均时间复杂度为O(n)
因为线性表长度可变，且所需最大空间随问题不同 而不同，所以用动态分配的一维数组(P22)。为使得
算法简明扼要，暂使用静态数组。
线性表的建立、输出算法
初始化
void initlist(Sqlist *L) {
L->length=0; } Sqlist Sl;
initlist(&Sl);
void initlist(Sqlist &L) {
(a1,a2,….,ai,…..,an)
2.注逻意辑:特1征.数：据仅元有素一a个i是开一始个结抽点象和的一符个号终端结点，并且所有结
点都2最. 多ai只可有取一各个种前数驱据和类一型个后继
3. 同一线性表中的元素必定具有相同的特性，属
于同一数
线性表是一个线性结构
据对象
4. 相邻数据元素之间存在序偶关系
线性表主要操作的实现
1. 插入：在线性表第i （1≤i ≤ n+1）个位置上插 入元素e (a1, …, ai-1, ai, …, an) 改变为 (a1, …, ai-1, e, ai, …
a1 a2 … ai-1 ai … an
a1 a2 … ai-1 e ai … an
表的长度加1
注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist 类型的顺序表，则表中第i个元素是L.a[i-1]。
存在惟一的一个开始结点，称做“第一个”的数据元素 存在惟一的一个终端结点，称做“最后一个”的数据元素 除第一个外，每个数据元素只有一个前驱 除最后一个外，每个数据元素只有一个后继
1
2
3
4
5
2.1 线性表的类型定 义
一、逻辑结构 1.描述: 线性表是由n (n>=0)个数据元素(结
点)a1,a2,….,ai,….,an组成的有限序列。其中，数据元 素的个数n定义为表长。当n=0时称为空表，非空的线性表 (n>0)记为：
}ADT List
a1是第一个元素，有且仅有一个直接后继元素a2； an是最后一个元素，有且仅有一个直接前趋元素an-1 ； 其余ai(1<i<n)有且仅有一个直接前趋ai-1，有且仅有
一个直接后继ai+1
2.2 线性表的顺序表示和实现
一．顺序表示（存 储）：指在内存中 用地址连续的一块 存储空间顺序存放 线性表的各元素， 用这种存储形式存 储的线性表称其为 顺序表。
存储地址
d d+L d+2L
... d+(i-1)L
... d+(n-1)L
...
内存单元
... a1 a2 a3 …
ai …
an ...
线性表顺序存储结构示意图
数据元素存储位置表示
设 a１的存储地址为Loc(a１)，每个数据元素占 l个存储地址，则第i个数据元素的地址为：
Loc(ai)=Loc(a１)+(i-1)* l ，1≤i≤n 逻辑上相邻的ai和ai+1以相邻的存储位置。 确定起始位置后，顺序表中任一数据元素都可 随机存取。
void outputl(Sqlist L) {
int i; cout<<"List length" <<L.length<<endl; for (i=0; i<L.length; i++)
{ cout<<L.a[i]<<" "; if ((i+1)%10==0) cout<<endl;
} cout<<endl; }
回顾上次课内容
数据结构的相关概念 数据的存储结构 逻算辑法结分构 析方法
存储结构
顺序存储结构 链接存储结构
集合 线性结构 树形结构
图状结构或网 状结构
第二章 线性表
主要内容：
线性表的类型定义 线性表ห้องสมุดไป่ตู้顺序表示和实现 线性表的链式表示和实现 线性表的应用举例
线性结构的特点