第三章 线性表 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.12 时间复杂度O(n)

10 3.2.3顺序表其它算法举例 例3.6 用顺序表表示集合，完成例3.4。 算法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 单循环链表

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

25 双向循环链表

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

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

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

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

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

31 rc 5 La (a) 8 18 22 52 12 45 Lb pa pb (b)

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

33 谢 谢

34 算法3.1 void union( List &La, List &Lb) {
La_len=ListLength(La); // 求La的长度 while(!ListEmpty(Lb)) // 循环处理Lb中的元素 ListDelete(Lb,1,e); // 删除Lb中第一个元素并赋予e If(!LocateItem(La,e))ListInsert(La,++La_len,e); //若e不在La中则插入La的最后一个元素后面 }//end while DestroyList(Lb); }//end unoin

35 算法3.2 void minus( List &La, List &Lb) {
while(!ListEmpty(Lb)) // 循环处理Lb中的元素 ListDelete(Lb,1,e); // 删除Lb中第一个元素并赋予e If((i=LocateItem(La,e))!=0)ListDelete(La,i,e); //若e在La中则从La中删除 }//end while DestroyList(Lb); }//end minus

36 算法3.3 void InitList_sq(SqList &L,int msize=LIST_INIT_SIZE)
L.elem=new ElemType[msize]; L.listsize=msize; //顺序表的最大容量 L.length=0; // 顺序表初始时的元素数是0 }// end InitList_sq

37 算法3.4 void DestroyList_sq(SqList &L) {//销毁顺序表L
delete [] L.elem; // 释放数组空间 L.length=0; L.listsize=0; }// end DestroyList_sq

38 算法3.5 /3.6/ 3.7 bool ListEmpty_sq(SqList L) { return (L.lenth==0); }
bool ListFull_sq(SqList L) return (L.lenth==L.listsize); int ListLength_sq(SqList L) return L.lenth;

39 算法3.8 int LocateItem_sq(SqList L,Elemtype e)
for(i=1;i<=L.length;i++) //依次查找每个元素 if(L.elem[i-1]==e)return i; //找到位序为i的元素 return 0; //没有找到值为e的元素 }// end LocateItem_sq

40 算法3.9 void GetItem_sq(SqList L,int i,Elemtype &e)
{//将顺序表L中位序为i的元素值赋予e. e=L.elem[i-1]; }// end GetItem_sq

41 算法3.10 void ListInsert_sq(SqList &L，int i，Elemtype e)
{//在顺序表L中位序为i的元素前插入一个新的元素e //同时需要考虑i的合法性和满状态 if(i<1||i>L.length+1){ErrorMsg(“i值非法！”);return;} if(L.length==L.listsize)Increment(L); //当前L已满 for(j=L.length-1;j>=i-1;j--) //由后往前逐个后移元素 L.elem[j+1]=L.elem[j]; L.elem[i-1]=e; //在L.elem[i-1]放入e ++L.length; }// end ListInsert_sq

42 算法3.11 #define LIST_INC_SIZE 20
void Increment(SqList &L，int inc_size=LIST_INC_SIZE) { //增加顺序表L的容量为listsize+inc_size ElemType *a; a=new ElemType[L.listsize+inc_size]; if(!a){ErrorMsg(“分配内存错误！”);return;} for(i=0;i<L.length;i++)a[i]=L.elem[i]; delete [] L.elem; // 释放原数组空间 L.elem=a; // 将新的数组赋予顺序表的指针 L.listsize+=inc_size; // 顺序表的容量增加inc_size }// end ListInsert_sq

43 算法3.12 void ListDelete_sq(SqList &L，int i，Elemtype &e)
{//从顺序表L中删除位序为i的元素并把值赋予e if(i<1||i>L.length){ErrorMsg(“i值非法！”);return;} e=L.elem[i-1]; //保存L.elem[i-1]到e for(j=i;j<=L.length-1;j++) //由前往后逐个前移 L.elem[j-1]=L.elem[j]; L.length--; }// end ListDelete_sq

44 算法3.13 void Union_sq(SqList &La，SqList &Lb)
{//实现顺序表A和B所表示的集合的并，结果放在A，销毁B for(i=0;i<Lb.length;i++){ //逐个处理Lb的元素 e=Lb.elem[i]; //取Lb中第i个元素 j=0; while(j<La.length&&La.elem[j]!=e)++j; //在La中查找e if(j==La.length){ //La中没有找到e La.elem[La.length]=e; //e插入到La的最后 La.length++; //La长度增加1 }//if }//for delete [] Lb.elem; //释放Lb内存 Lb.length=0;Lb.listsize=0; }// end Union_sq

45 算法3.14 void InitList_L(LinkList &L) {//初始化链表L L=NULL;
}// end InitList_L

46 算法3.15 Int ListLength_L(LinkList L) {//求链表L的长度 p=L;k=0; while(p){
k++;p=p->next; }//while return k; }// end ListLength_L

47 算法3.16 {//在链表L中查找元素e p=L; while(p&&p->data!=e)p=p->next;
LNode * LocateItem_L(LinkList L,ElemType e) {//在链表L中查找元素e p=L; while(p&&p->data!=e)p=p->next; return p; }// end LocateItem_L

48 算法3.17 void ListInsert_L(LinkList &L,LNode *p，LNode *s)
{//在链表L中，在p所指结点前插入s所指的结点 if(p==L){ //p是第一个结点 s->next=L; L=s; }//if else { //p不是第一个结点 q=L; while(q&&q->next!=p)q=q->next;//找后继是p的结点 if(q){q->next=s;s->next=p;} //在p前插入s else ErrorMsg(“p不是L中的结点”); }//else }// end ListInsert_L

49 算法3.18 void ListDelete_L(LinkList &L,LNode *p，ElemType &e)
{//在链表L中，删除p所指结点 if(p==L)L=p->next; //p是第一个结点 else { //p不是第一个结点 q=L; while(q&&q->next!=p)q=q->next;//找后继是p的结点 if(q)q->next=p->next; //使p的原前驱直接指向p的后继 else ErrorMsg(“p不是L中的结点”); // p不在L中 }//else e=p->data;delete p; //保存被删除的元素值，释放空间 }// end ListDelete_L

50 算法3.24 void Purge(SqList &L) {//把顺序有序表L中相同的元素删除。 i=-1;j=0;
while(j<L.length){ if(j==0||L.elem[j]!=L.elem[i]) L.elem[++i]=L.elem[j]; j++; }//while L.length=i+1; }// end Purge i 表示纯化后集合的最后元素下标 j 表示待处理集合第一个元素下标

51 算法3.25 void exchange(SqList &L,int m,int n) {//实现L中前m个元素和后n个元素的交换。
for(k=1;k<=n;k++){ //对b1,b2,...,bn逐个处理 w=L.elem[m+k-1]; //移出bk for(j=m+k-1;j>=k;j--) //a1,a2,...am均后移 L.elem[j]=L.elem[j-1]; L.elem[k-1]=w; //bk放到a1前 }//for }// end exchange

52 算法3.26 void invert(ElemType &R[],int s,int t) {//实现数组R中从下标s到t的逆置
for(k=s;k<=(s+t)/2;k++){ w=R[k]; //交换R[k]和R[t-k+s] R[k]=R[t-k+s]; R[t-k+s]=w; }//for }// end invert

53 算法3.27 void exchange2(SqList &L,int m,int n)
{//利用invert实现L中前m个元素和后n个元素的交换 invert(L.elem,0,m+n-1); invert(L.elem,0,n-1); invert(L.elem,n,m+n-1); }// end exchange2

54 算法3.28 void union_ord(LinkList &La,linkList &Lb)
{//有序循环链表La、Lb表示的集合A、B，求表示集合A∪B的链表Lc，结果存储在La pa=La->next->next; pb=Lb->next->next; rc=La->next; ha=La->next; hb=Lb->next; //保留头结点指针 while(pa!=ha && pb!=hb){ if(pa->data < pb->data){ //pa所指结点值小 rc->next=pa;rc=pa;pa=pa->next; //pa链入Lc } else if(pa->data > pb->data){ //pb所指结点值小 rc->next=pb;rc=pb;pb=pb->next; //pb链入Lc else{ rc->next=pa;rc=pa;pa=pa->next; //pa链入Lc qb=pb;pb=pb->next;delete qb; //删除pb所指结点 }//while if(pb==hb)rc->next=pa; //Lb结束直接链入La剩余部分 rc->next=pb; //直接链入Lb剩余部分 Lb->next=ha;La=Lb; }//else delete hb; //释放Lb头结点,结果在La中 }// end union_ord