【教学课件】第二章线性表.ppt

第二章 线性表,学习要点 了解线性表的逻辑结构是数据元素之间存在着线性关系，在计算机中表示这种关系的两种不同的存储结构是顺序存储结构和链式存储结构。熟练掌握线性表的两种存储结构，即顺序存储结构和链式存储结构。熟练掌握线性表的两种存储结构的基本算法:查找、插入、删除等。,2.1 线性表的基本概念,线性表的定义线性表是n 个类型相同数据元素的有限序列，Linear-list=(D,R)其中：D=ai|ai datatype,i=0,1,n-1 R=|ai,ai+1 D,1in-1 或记作（a0,a1,a2,an-1）。,例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,E Z）。例3、某单位的电话号码簿。,说明：设 A=（a0,a1,.,ai-1,ai,ai+1,an-1）是一线性表1)不同线性表中数据元素的类型可以是各种各样的，但同一线性表中的元素必须是同一类型的；2)在表中 ai-1 领先于ai，ai 领先于ai+1，称ai-1 是ai 的直接前驱，ai+1 是ai 的直接后继；3)在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，这是所有线性结构的共同特征。线性表是一种线性数据结构；4)线性表中元素的个数n 称为线性表的长度，n=0 时称空表；5)ai是线性表的第i+1个元素，称i+1 为数据元素ai 的序号，每一个元素在线性表中的位置，仅取决于它的序号；,线性表的其他表示方式二元组表示 L=，其中D=a0,a1,a2,.an-1 S=R R=,图示表示,顶点：表示一个数据元素边：表示是数据间的顺序结构关系,线性表的基本操作初始化操作：Initiate（L）设定一个空的线性表L；求长度函数：Length（L）求线性表L中数据元素的个数；查找函数：Get（L,i）取得线性表L的第i个数据元素；定位函数：Locate（L,x）求数据元素x在线性表L中的位置；插入操作：Insert（L,i,x）在线性表中第i个位置插入一个数据元素;删除操作：Delete（L,i）在线性表中第i（0in-1）个结点；,为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；,2.2 线性表的顺序存储结构,一、线性表的顺序存储结构顺序表,线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。,线性表（a0,a1,a2.an-1）的顺序存储结构,用顺序存储结构存储的线性表称为顺序表,说明：在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（表示）出来，即逻辑关系相邻，物理位置也相邻；假设线性表中每个数据元素占用d 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：Loc(ai-1)=Loc(a0)+(i 1)*d,因为高级语言中的一维数组是采用顺序结构储存的，因此我们使用一维数组来表示线性表，数组的类型由线性表中的数据元素的性质决定。,顺序表的类型定义#define Maxnum 200/*分配的顺序表总长度*/elementtype elementMaxnum；/*定义元素类型数组*/int n；/*当前顺序表存储数据的个数*/为了把线性表的表元素和当前长度整合作为该线性表的特性，我们定义一个结构体如下：struct sqlistelementtype elementMaxnum;/*顺序表数组*/int n;/*当前线性表长度*/;typedef struct sqlist*ptsqlist；,设 A=（a0,a1,a2,.an-1）是一线性表，L是sqlist 类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：,12i-1ii+1n,存放线性表元素 的一维数组,顺序表通过元素的存储顺序反映线性表元素间的逻辑关系,二、顺序表的基本操作算法1.创建并初始化顺序表 2.在顺序表中查找下标为i的元素（0in-1）并返回该元素 3.顺序表的判空操作,int Empty(ptsqlist list)if list-n=0return(1);return(0);,ptsqlist Initiate(void)ptsqlist list;list=(ptsqlist)malloc(sizeof(struct sqlist)if!listprintf(overflow!n);return(null);elselist-n=0;return(list);,elementtype Get(ptsqlist list,int i)if(i=list-n)printf(not existn);return(null);return(list-elementi);,4.插入 insert(L,i,x)功能：在顺序表L中第i个位置后插入一元素插入一个新元素x,插入前线性表为(a0,a1,a2,ai-1,ai,an-1)插入后,线性表长度为n+1,线性表为(a0,a1,a2,ai-1,x,ai,an-1),插入前n=7,插入后n=8,插入操作示意图：insert(p,3,11),插入操作算法,int Insert(ptsqlist list,int i,elementtype x)int j;if(i=list-n)/*位置不合理*/printf(“not exit!n”);return(0);if(list-n=Maxnum)/*空间已满*/printf(“out of space!n”);return(0);for(j=list-n-1;j=i;j-)/*向后移动元素*/list-elementj+1=list-elementj;list-elementi=x;/*插入元素*/list-n+;/*长度加1*/return(1);,演示,5.删除 delete(L,i)功能：删除顺序表L中下标为i（0in-1）的数据元素,删除前线性表为(a0，a1，an-1)删除后,线性表长度为n-1,线性表为(a0，a1，ai-1，ai+1，an-1),删除前n=8,删除后n=7,删除操作示意图：Delete(p,3),删除操作算法,int Delete(ptsqlist list,int i)int j;if(i=list-n)/*位置不合理*/printf(“not exist!n”);return(0);for(j=i;jn-1;j+)/*向前移动元素*/list-elementj=list-elementj+1;list-n-;/*长度减1*/return(1);,演示,6.顺序表的反转操作,viod fanzhuanlist(ptsqlist list)elementtype mid;int a,z;a=0;z=list-n-1;for(;aelementa;list-elementa=list-elementz;list-elementz=mid;,在下标为i的位置(第i+1个位置)前插入 元素下标 移动元素个数0n1n-1in-in-11n0,三、算法时间复杂度分析在顺序表中插入元素，时间主要耗费在移动元素上，而移动的个数取决于插入的位置以及表的长度。,12i-1ii+1n,假设在线性表的任何位置插入元素的概率相同，即 pi=1/(n+1)则有：,假设pi是在第i个元素之前插入元素的概率，在长度为n的顺序表中插入一个元素，所需移动元素个数数学期望值为：,假设在线性表的任何位置删除元素的概率相同，即 pd=1/n则有：,删除下标为i的元素（第i+1个）需移动n-i-1个元素，设在相应位置删除元素的概率是pd，则删除的平均移动次数是：,在顺序表中插入或删除元素的时间时间复杂度为O(n),相关例题,例1 利用顺序表设计一算法，用以清除表L中的多余的重复结点。如表L（21，3，5，3，21，3，90，5）运算后变为L（21，3，5，90）,算法思想应该是怎样的呢？,相关代码：,void Purge(ptsqlist list)int i,j,k;i=0;while(in)j=i+1;while(jn)if(list-elementi=list-elementj)for(k=j+1;kn;k+)list-elementk-1=list-elementk;list-n=list-n-1;else j=j+1;i=i+1;,作业：设计相关算法，完成线性表的其它操作：Locate(p,x);Union(p,q).,小结顺序表的特点：1 通过元素的存储顺序反映线性表中 数据元素之间的逻辑关系；2 可随机存取顺序表的元素；3 顺序表的插入、删除操作要通过移动 元素实现；,线性表的链式存储结构是用一组任意的存储单元存储线性表的数据元素。为了表示线性表中元素的先后关系，每个结点除了需要存储自身的信息外，还需存储一个指示其直接后继的信息（直接后继的存储位置）。,2.3 线性表的链式存储结构,101010121014101610181020102210241026,用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来实现的,2.3.1 线性链表一，线性链表的概念,线性链表有关术语结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；结点的数据域：结点中用于保存数据元素的部分;结点的指针域：结点中用于保存数据元素直接后继存储地址的部分;,存储数据元素,存储直接后继结点的地址,怎样在计算机上实现线性链表？,？,结点变量图示,LNode：结构类型名；LNode类型结构变量有两个域：data：用于存放线性表的数据元素，next：用于存放元素直接后继结点的地址；该类型结构变量用于表示线性链表中的一个结点；,data next,LNode类型 结构变量,p是LNode类型的指针变量,线性链表的结点类型定义及指向结点的指针类型定义,typedef struct Node Etype data;struct Node*next;LNode,*LinkList;,顺序建立单链表（尾插法）,H,p,q,H,p,q,H,p,q,q,H,p,q,q,Lnode*Screat_List(void)char ch;LinkList H,p,q;H=NULL;q=H;scanf(ch);while(ch!=n)p=(LinkList)malloc(sizeof(LNode);p-data=ch;if(H=NULL)H=p;else q-next=p;q=p;scanf(ch);p-next=NULL;return H;,head是头指针,头结点,空指针,head,头指针：用于存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针;头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点；带头结点的线性链表：第一元素结点前面增加一个附加头结点的线性链表称为 带头结点的线性链表；,非空表,空表,二，线性链表基本操作的算法,如何在线性链表上实现线性表的基本操作？如何建表?查找?如何插入?删除?,？,约定用带头结点的线性链表存储线性表,1.建立单链表（前插法）,1.建立单链表（前插法）,LinkList CreateList(int n)LinkList L,p;int i;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(%d,2.按序号查找,LNode*Get_List_Node(LinkList head,int i)/*在单链表中查找第i个结点,返回其指针,若失败返回空*/LNode*p;int j;p=head;j=0;while(p-next!=NULL),3.按值查找,LNode*Locate_List_Node(LinkList head,Etype x)/*在单链表中查找值为x的结点,返回其指针,查找失败返回空*/LNode*p;p=head-next;while(p!=NULL),4.插入操作 int ListInsert(LinkList L,int i,Etype e)功能：在线性链表的第i个结点之前插入一个新结点；,插入操作主要步骤：1）查找链表L的第 i-1个结点；2）为新元素建立结点；3）修改第 i-1个元素结点的指针和新元素结点指 针完成插入；,注意 的顺序！,head,head,插入前,插入后,s-next=p-next;,p-next=s;,int ListInsert(LinkList L,int i,Etype e)LinkList p;p=Get_List_Node(L,i-1);if(p=NULL)return ERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return OK;,4.插入操作,5.删除操作 int ListDelete(LinkList L,int i,Etype e)功能：删除线性链表的第i个结点；,删除操作主要步骤：1）查找链表的第 i-1个元素结点,使指针p指向它,将 指针q指向第i个结点；2）修改第 i-1个元素结点指针，使其指向第i个元素 结点的后继；3）回收q指针所指的第i个结点空间；,head,删除前,删除后,head,an,p,q,p,q,插入操作图示：,p-next=q-next;p-next=p-next-next;,free(q);,int ListDelete(LinkList L,int i,Etype e)LinkList p,q;int j;ElemType e;p=Get_List_Node(L,i-1);if(p=NULL|p-next=NULL)return ERROR;q=p-next;p-next=q-next;e=q-data;free(q);return OK;,5.删除操作,演示,三、线性链表的其他操作的实现,例1 将两个递增有序线性链表归并成一个递增有序表。设线性表A、B分别用头指针为La、Lb 的两个带头结点的线性链表存储,归并后的递增有序表头指针为Lc,将两表数据较小的结点依次取出插入到新表。,演示,利用基本操作直接对链表进行操作,LinkList MergeList(LinkList La,LinkList Lb)LinkList Lc,pa,pb,pc;pa=La-next;pb=Lb-next;Lc=pc=La;while(pa,例2 某仓库中有一批电视机，按价格从低到高构成一单链表存于计算机中。链表的每个结点指出同样价格的若干台，现又到新m台价格为h的电视机入库。请写出链表增加电视的算法。,typedef struct LNODEfloat cost;int number;struct LNODE*next;LNode,*LinkList;,LinkList TVSets(LinkList s,int m,float h)LinkList p,q,t;q=s;p=s-next;while(p!=NULL,线性链表是线性表的一种链式存储结构,线性链表小结 线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系；2 插入删除操作通过修改结点的指针实现；3 不能随机存取元素；,(a)非空表（b）空表,2.3.2 单向循环链表,循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的头结点循环链表图示,(c)给出尾指针的循环链表,说明对循环链表，有时不给出头指针，而是给出尾指针循环链表与线性链表操作的主要差别是算法中循环结束的条件不是p或p-next是否为NULL,而是它们是否等于某一特定指针（头指针/尾指针）；在解决某些实际问题时，循环链表要比线性链表方便些。如将一个链表链在另一个链表的后面；,p=a-next;q=b-next;a-next=q-next;b-next=p;free(q);,存储数据元素,存储后继结点 的地址,存储前趋结点 的地址,2.3.3 双向链表,双向链表的概念 双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。,(a)结点图示,(b)空的双向循环链表 head-prior=head-next,（c）非空的双向循环链表,typedef struct DulNodeElemType data;struct DulNode*prior;struct DulNode*next;dlNode,*DullinkList；,双向链表图示,双向链表的基本操作算法,插入 S-prior=p-prior;p-prior-next=S;S-next=p;p-prior=S;,删除 p-prior-next=p-next;p-next-prior=p-prior;,插入操作算法,int dList_Insert(DlinkList H,int i,Etype e)dLNode*p=H-next;int j=0;do p=p-next;j+;while(p!=H-next,删除操作算法,int dList_Delete(DLinkList H,int i,Etype*e)dLNode*p=H-next;int j=0;do p=p-next;j+;while(p!=H-next,2.4 静态链表,针对不设“指针”的编程语言，怎样用不连续的内存区域来描述线性表？我们想到用一维数组来表示这种情况下的链表。,#define MAXSIZE 1000 typedef structElemType data；int cur；Snode,SLinkListMAXSIZE；,用数组的一个分量表示一个结点，同时用游标cur代替指针指示结点在数组的相对位置。,(a)修改前状态,012345678910,012345678910,8,9,(b)修改后状态,在Li后插入Shi；删除元素Zheng,shead,SN,假设S为SLinkList型变量，则S0.cur指示第一个结点在数组中的位置，若S0.cur=i，则Si.data存储线性表的第一个元素，且Si.cur指示第二个结点在数组中的位置。若第i个分量表示链表的第k个结点，则si.cur指示第k+1个结点的位置。i=si.cur为指针后移（类似于p=p-next)在静态链表中，当用户需要结点时，必须向系统的存储池中的空闲结点申请。,顺序表和链式表的比较基于时间的考虑顺序存储是一种随机存取的结构，而链表则是一种顺序存取的结构。基于空间的考虑顺序表的存储空间是静态分配的链表的存储空间是动态分配的基于语言考虑,2.5 线性表的应用举例,一元多项式的表示及相加数学表示：,Pn(x)=p0+p1x+p2x2+pnxn,在计算机中，用线性表P表示：,P=(p0,p1,p2,pn),一元m次多项式Qm(x)可表示为：,Q=(q0,q1,q2,qm),R=(p0+q0,p1+q1,p2+q2,pm+qm,pm+1,pn),设mn，则相加结果Rn(x)=Pn(x)+Qm(x),void addlist(ptsqlist list_a,ptsqlist list_b)int i;for(i=0;ilist_now_size;i+)list_a-elementi+=list_b-elementi;return();,List_aList_b,N+1M+1,T（x）=12x100+3x10000,通常情况下，多项式的次数可能很高且变化大，例如：,考虑用系数和指数一起来表示多项式的一个项，即用序偶 表示多项式的一个非零项pixi(pi0)。则T(x)可表示为：T=(，),若只对多项式求值，则不会改变多项式的系数和指数，宜用顺序表；若对多项式求和，则要进行插入、删除操作，应采用链表。,多项式T(x)用带头结点的单链表表示如下：,T,设多项式的指数为整数，设系数为实数，则多项式可以描述为：typedef struct Pnode float coef;int exp;Pnode*next;*Polyn;,对两个多项式La、Lb，可以这样实现运算La+Lb：实现方法：把多项式Lb的元素插入La中。用指针p、q分别扫描两个多项式，比较当前结点*p、*q的指数，会有下列三种情况：（1）p-expq-exp。*q应为结果多项式的一项，故把*q插入到*p之前。因为涉及到在*p前插入用，所以用指针pre指向*p的直接前驱。（2）p-expq-exp。*p、*q两结点的系数就相加，若相加后为0，则删除结点*p与*q。否则修改*p的系数域并删除结点*q。（3）p-expq-exp。*p应为结果多项式的一项，对*q不做处理。,La,Lb,La,Lb,void PolyAdd(Polyn La,polyn Lb)p=La-next;pre=La;q=Lb-next;while(p!=NULL/释放Lb表的头结点,if(p-exp=q-exp)x=p-coef+q-coef;if(x=0)pre-next=p-next;/删除*pfree(p);elsep-coef=x;/修改*p的系数pre=p;p=pre-next;s=q-next;free(q);q=s;/q右移else/p-expexp时pre=p;p=p-next;,p-expq-exp和p-expq-exp的处理部分,为了把线性表的表元素和当前长度整合作为该线性表的特性，我们定义一个结构体如下：struct sqlistelementtype elementMaxnum;/*顺序表数组*/int n;/*当前线性表长度*/;typedef struct sqlist*ptsqlist；,线性表小结顺序表,顺序表插入 insert(L,i,x)步骤：1)定位for(j=list-n-1;j=i;j-)/*向后移动元素*/list-elementj+1=list-elementj;2)插入list-elementi=x;/*插入元素*/list-n+;/*长度加1*/,顺序表删除 delete(L,i)步骤：1)定位for(j=i;jn-1;j+)/*向前移动元素*/list-elementj=list-elementj+1;2)删除list-n-;/*长度减1*/,结点变量图示,data next,链表的结点类型定义及指向结点的指针类型定义,typedef struct Node Etype data;struct Node*next;LNode,*LinkList;,head,带头结点的链表,链表,插入操作主要步骤：1）查找链表L的第 i-1个结点；2）为新元素建立结点；3）修改第 i-1个元素结点的指针和新元素结点指 针完成插入；,注意 的顺序！,head,s-next=p-next;,p-next=s;,删除操作主要步骤：1）查找链表的第 i-1个元素结点,使指针p指向它,将 指针q指向第i个结点；2）修改第 i-1个元素结点指针，使其指向第i个元素 结点的后继；3）回收q指针所指的第i个结点空间；,head,an,p,q,p-next=q-next;p-next=p-next-next;,free(q);,循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的头结点循环链表图示,(c)给出尾指针的循环链表,双向链表 双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。,typedef struct DulNodeElemType data;struct DulNode*prior;struct DulNode*next;dlNode,*DullinkList；,双向链表的基本操作算法,插入 S-prior=p-prior;p-prior-next=S;S-next=p;p-prior=S;,删除 p-prior-next=p-next;p-next-prior=p-prior;,在不设“指针”的编程语言中，用一维数组表示链表。,#define MAXSIZE 1000 typedef structElemType data；int cur；Snode,SLinkListMAXSIZE；,用数组的一个分量表示一个结点，同时用游标cur代替指针指示结点在数组的相对位置。,静态链表,012345678910,012345678910,8,9,SLinkListk.cur=SLinkListp.cur;SLinkListp.cur=k;,k,p,