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

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.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) 1<=i<= ListLength (L)+1 ListDelete(&L,i,&e) 1<=i<= ListLength (L) ListTraverse(L)

【例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空

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

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

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

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

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

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

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

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

常见指针操作

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

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

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

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

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

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

以单链表表示集合，完成例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

【算法改进】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

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

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

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

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

单链表的实际应用改进 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++; }

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

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

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