第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较.

Presentation on theme: "第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较."— Presentation transcript:

1 第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较

2 3.1线性表的类型定义 3.1.1线性表的定义 线性表是n(n>=0)个数据元素的有限序列，表中各个元素具有相同地属性，表中相邻元素间存在“序偶”关系。 记做：(a1,a2,…….ai-1,ai,ai+1,…,an-1,an ) ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序

3 3.1.2线性表的基本操作 InitList(&L) Destroy(&L) ClearList(&L) ListEmpty(L)
ListLength(L) GetElem(L,i,&e) 1<=i<= ListLength (L) LocateItem(L,e) PriorElem(L,Cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) <=i<= ListLength (L)+1 ListDelete(&L,i,&e) 1<=i<= ListLength (L) ListTraverse(L)

4 【例3.4】对两个线性表La、Lb表示的集合A和B，求一个新集合A＝AUB 算法3.1
若La中不存在，则将其插入La，重复直至Lb空 【例3.5】对两个线性表La、Lb表示的集合A和B ，求A=A-B 算法3.2 若La中存在，则将从La删除，重复直至Lb空

5 3.2线性表的顺序表示和实现 3.2.1顺序表——线性表的顺序存储表示 Const LISTINCREMENT=10;
Const LIST_INIT_SIZE=100; (C++规范) Const LISTINCREMENT=10; #define LIST_INIT_SIZE (C规范) Typedef Struct { Elemtype * elem; Int length; Int listsize; Int incrementsize; }SqList;

6 3.2.2顺序表中基本操作的实现 Ein=Σpi(n-i+1)=n/2 Edl=Σqi(n-i)=(n-1)/2
初始化操作 InitList_Sq 算法3.3 销毁操作 DestroyList_Sq 算法3.4 是否为空 ListEmpy_Sq 算法3.5 是否满 ListFull_Sq 算法3.6 求长度 ListLength_sq 算法3.7 查找元素操作 LocateElem_Sq 算法3.8 获取元素操作 GetItem_Sq 算法3.9 插入元素操作 ListInsert_Sq 算法3.10 时间复杂度O(n) 删除元素操作 ListDelete_Sq 算法3.11 时间复杂度O(n) 插入和删除操作的时间分析： Ein=Σpi(n-i+1)=n/2 Edl=Σqi(n-i)=(n-1)/2

7 查找元素操作 算法3.8 时间复杂度O(n)

8 插入元素操作 算法3.10 时间复杂度O(n)

9 删除元素操作 算法3.11 时间复杂度O(n)

10 3.2.3顺序表其它算法举例 例3.6 用顺序表表示集合，完成例3.1。 算法3.13 时间复杂度O(n2)
例3.10 用尽量少得辅助空间将前m个元素和后n个元素互换 算法 exchange1 时间复杂度：O(m×n) 算法 invert 时间复杂度：O(t-s+1) 算法 exchange2 时间复杂度：O(m+n)

11 3.3线性表的链式表示和实现 3.3.1单链表和指针 typedef struct Lnode{ 数据域（data）和指针域（next）
存储表示 typedef struct Lnode{ ElemType data; Struct Lnode *next; }Lnode, *LinkList;

12 单链表种类 不带头结点单链表 带头结点单链表

13 常见指针操作

14 3.3.2单链表的基本操作 求线性表的长度 算法3.15时间复杂度：O(n)

15 查找元素操作 算法3.16时间复杂度：O(n)

16 插入结点操作 ：前插、后插 算法3.17 时间复杂度：前插O(n)、后插O(1)

17 删除结点操作 算法3.18 时间复杂度O(n)

18 3.3.3单链表的其它操作举例 逆序创建链表 时间复杂度O(n)

19 逆置单链表 时间复杂度O(n)

20 以单链表表示集合，完成例3.1 算法3.19时间复杂度O(m×n)
void union_L( LinkList &La, LinkList &Lb ) { if (!La) La = Lb;return; while ( Lb ) { s = Lb; Lb = Lb->next; p = La; while ( p && p->data != s ->data ) { pre = p; p = p->next; }//while if ( p ) delete s; else { pre->next = s; s->next = NULL;} }// while(Lb) }// union_L

21 【算法改进】Lb中元素只需要和原La元素比较
void union_L( LinkList &La, LinkList &Lb ) { if (!La) La = Lb;return; pa=La; while ( Lb ) { s = Lb; Lb = Lb->next; p = pa; while ( p && p->data != s ->data )p =p->next; if ( p) delete s; else {s->next=La; La=s} }// while(Lb) }// union_L

22 3.3.4循环链表 什么是循环链表 判断表尾的循环条件： 通常增加头结点 最后一个结点的指针指向头结点 头指针指向最后一个结点
空的循环链表是头结点自循环 判断表尾的循环条件： 不是p==NULL，而是p是否等于头指针的next域。

23 3.3.5双向链表 概念：两个指针，分别指向前驱和后继 typedef struct DuLnode{ ElemType data;
Struct DuLnode *prior; Struct DuLnode *next; }DuLnode, *DuLinkList;

24 插入结点操作 算法3.21 时间复杂度O(1)

25 删除结点操作 算法3.22 时间复杂度O(1)

26 单链表的实际应用改进 typedef struct { 例3.8 改写逆序创建链表算法 ：算法3.23 L.head=NULL;
LinkList head,tail; int length; }AdvancedLinkList; 例3.8 改写逆序创建链表算法 ：算法3.23 L.head=NULL; for(i=n-1; i>=0; i--){ s=new LNode; s->data=A[i]; s->next=L.head; L.head=s; if(i=n-1)L.tail=s; L.length++; }

27 3.4有序表 什么是有序表 插入结点操作 例3.9 以顺序表表示集合，完成集合的纯化 数据元素在线性表中依值非递减或非递增的
时间复杂度 O(n) 例3.9 以顺序表表示集合，完成集合的纯化 算法3.24 时间复杂度 O(n)

28 例3.11 两个带头结点的循环有序链表，表示集合A、B，完成C=A U B 算法 复杂度 O(n+m)
算法3.28 在头元素中放最大元素MAX 简化操作 ,时间复杂度 O(n+m), 时间略长，算法表达略简单 类似：两个带头结点的有序单链表，表示集合A、B，判断A=B? 对比：无序表完成同样功能的时间复杂度为O(n*n)

29 3.5顺序表和链表的综合比较 线性表的长度能否预先确定？处理过程中变化范围如何？ 对线性表的操作形式如何？ 长度确定、变化小时用顺序表
长度变化大、难以估计最大长度时宜采用链表 对线性表的操作形式如何？ 查询操作多、删除和插入操作少时使用顺序表 频繁插入和删除操作宜采用链表