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

3.2.3顺序表其它算法举例 例3.6 用顺序表表示集合，完成例3.4。 算法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 算法3.28 复杂度 O(n+m) 思考： 在头元素中放最大元素MAX 简化操作 ,时间复杂度 O(n+m), 时间略长，算法表达略简单 类似：两个带头结点的有序单链表，表示集合A、B，判断A=B? 对比：无序表完成同样功能的时间复杂度为O(n*n)

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

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

谢 谢

算法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

算法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

算法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

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

算法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;

算法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

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

算法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

算法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

算法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

算法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

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

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

算法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

算法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

算法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

算法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 表示待处理集合第一个元素下标

算法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

算法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

算法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

算法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