DS02-线性表

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,其次章 线性表,21线性表概念定义：具有一样类型的N个数据元素a0、a1、an-1的有限系列称为线性表。表示为A=a0、a1、an-1。数据元素的个数n为线性表长度，长度为零的线性表称为空表。,说明：1 一个线性表可用一个标识符来命名，如A=a0、a1、an-1。2 线性表中的元素要求具有一样的类型。3 表中的两相邻元素ai、ai+1，称ai是ai+1的前驱元素，而ai+1是ai的后继元素。4 线性表中数据元素的相对位置是固定的。,22线性表存储构造2.2.1 挨次存储方法：,存储方法：在内存开拓一块连续的存储空间用来依次存放表中的每个元素。,元素位置确定：设有线性表A=a0、a1、an-1，由于A中的元素具有一样类型，且占s字节，那么元素ai的地址为 ai=&a0+i*s。,对线性表的挨次存储常承受数组来实现。这是由于数组具有如下特性：,一维数组的特点,连续存储的线性表别名 向量,除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。,除最终一个元素外，其他每一个元素有一个且仅有一个直接后继。,线性表的创立：,1 用数组表示线性表：,如：#define MAXSIZE 100,int listMAXSIZE;,int n;,如：#define MAXSIZE 100,struct char 学号；,char 姓名；,int 数据构造；,int 操作系统；,int 离散数学；,int 英语listMAXSIZE；,int n;,2 线性表的创立程序：,设list为已定义的存放线性表的数组，n为线性表的长度。,Void creat_sq_list(int n,list),int i;,for(i=0;ilink=q;p=q;scanf(“%c”,/*返回建成链表的头指针*/,四、单链表的几种变化形式,1 循环链表：链表中最终一个结点的指针域指向第一个结点(原单链表末结点置NULL处改为置头指针即可),2 带表头结点的链表,3带表头结点的循环链表,Head,Head,Head,Head,Head,五、双向链表的几种变化形式,1 双向循环链表：链表中最终一个结点的指针域指向第一个结点,2 带表头结点的双向链表3带表头结点的双向循环链表,Head,Head,2.3.3 其他存储方法,一、索引存储,把线性表A中的结点划分成子线性表A0A m-1，划分方法是将A中的具有某种性质的元素归并到同一个子表中，常使用索引函数来计算出每个元素的索引值i,将一样索引i值的元素归并到同一个Ai中。再使用挨次或链接存储方法来存储索引表X和子线性表A0A m-1。一般状况下索引表用挨次存储，而子线性表用链接存储方法。,实例见P18,a,b,c,d,apple,car,bear,duck,bus,bird,cat,dog,例:,线性表A=(apple,cat,bus,dog,duck,bear,bird,car)使用索引函数：index(key)=(key的第1个字母ASCII码)-(a的ASCII码)。则把A划分为A0=(apple),A1=(bus,bird,bear),A2=(cat,car),A3=(dog,duck),x,0,X,1,x,2,x,3,二、分块存储,把线性表A划分成假设干块，每一块中的元素挨次是任意的，但块与块的之间必需按关键字大小排列，再建立一个索引表，索引表中的一项对应于表中一块，索引项由大小域(块中的元素个数)、键域(块中最大值)和链域(结点指针)。,实例见P19.,05,30,15,24,35,48,39,38,50,60,70,65,第一块,其次块,第三块,0,5,8,5,3,4,35,48,70,链 域,大小 域,键 域,分块有序表,三、压缩存储,假设线性表A=(a0、a1、an-1)中有很多具有一样值的元素V,由A构造A=(0,a0)、(1,a1)、(n-1,an-1),将A中的全部(j,v)元素删除，得到线性表达式A。再将A中的元素以挨次或链接方式存储。,例：A=(12,0,0,11,0,18,0,0,17,0,16,0,0,0,15)经压缩处理后A=(0,12),(3,11),(5,18),(8,17),(10,16),(14,15)再对A进展挨次或链接存储。,四、散列存储(HASH函数),根本思想：把线性表中的每个元素的值K通过一个函数H(k)转换成该元素在一块连续存储空间(数组)的单元地址(下标)来存放。实现关键字到地址映射的函数h(k)称为散列函数或哈希(Hash)函数，h(k)的值称散列地址或哈希地址，用于线性表进展散列存储的地址空间(数组)称为散列表或哈希表。,冲突问题：有ki=kj,但有H(ki)=H(kj),消逝地址冲突。,散列函数构造：原则：削减冲突、计算简洁；常用方法：直接定址、除留余数法等。,冲突处理,：开放定址法、链接法。,实例见P23,2.3 线性表的根本运算2.3.1 线性表的运算概述 1 创立一个空线性表；2 求线性表的长度；3 查找表中的第i个元素 4 依据关键字求在线性表的位置；5 在线性表中第i个元素位置插入一个新元素；6 修改线性表中元素的值；7 删除线性表中第i个元素；8 对线性表中的元素按关键字排序；9 复制一个线性表；10 合并线性表；11 拆分线性表；12 打印线性表输出线性表。,2.3.2 线性表的插入一、插入运算,有长度为n的线性表(a,0,、a,1,、a,n-1,),现将元素值为x的元素插入线性表中，使之变为(a,0,、a,1,、a,i-1,、x、a,i,、a,n-1,)，其长度变为n+1。,二、挨次存储的线性表的插入算法：1 将ai、ai+1、an-1 依次后移一个位置，留 出位置i;2 将新元素x存入位置i;3 线性表长度加1。,软件实现见C程序,。,int sq_ins(list,n,i,x)int list;int*n;int i,x;int j;if(i*n)return(1);if(*n=MAXSIZE)return(2):for(j=*n;ji,j-)listj=listj-1;listi=x;(*n)+;return(0);,三、链接存储的线性表插入,1、算法 创立新结点 newnode=(NODE)malloc(sizeof(NODE);newnode-data=x;确定插入位置：从头结点挨次搜寻i-1次即到达i-1个结点p;,修改指针：newnode-link=p-link;p-link=newnode;,Head,Head,插入的三种状况,第一种状况：在第一个结点前插入,newnodelink=head;,head=newnode；,插入前 插入后,(,插入前)(插入后),其次种状况：在链表中间插入,newnodelink=plink;,plink=newnode；,第三种状况：在链表末尾插入,newnodelink=plink;,plink=last=newnode；,(插入前)(插入后),2.3.2 线性表的删除一、删除运算 将长度为n的线性表删除第I个元素，使其长度变为n-1的线性表。二、挨次存储的线性表删除 算法：从挨次存储的线性表中删除ai的步骤是：领奖将ai+1,ai+2,an-1依次前移一位，线性表长度减1。实现程序：见sq_del(list,n,i)。int sq_del(list,n,i)int list,*n,i;int j;if(i*n)return(1);/*第1种状况，i不在可删除位置上*/for(j=i+1;jlink;p-link=q-link;,2 实现程序：通过函数link_del实现上述链表的删除算法。int link_del(head,i)/*head为链表头指针，I为被删元素位置*/NODE*head;int i;int j;NODE*p,*q;if(q=NULL)return(1);/*不能删除状况1*/if(i=0)/*删除头结点*/q=*head;*head=q-link;free(q);/*修改指针*/return(0);j=0;p=*head;while(+jlink;if(Ilink;p-link=q-link;free(q);/*修改指针,释放空间*/return(0);,带表头结点的单链表,表头结点位于表的最前端，本身不带数据，仅标志表头。,设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。,非空表 空表,在带表头结点的单链表,第一个结点前插入新结点,newnode,link=p,link,;,if(,p,link=NULL,),last,=,newnode,;,p,link=newnode,;,q,=,p,link,;,p,link=q,link,;,delete,q,;,if(,p,link=NULL,),last=p,;,从带表头结点的单链表中删除第一个结点,循环链表(,Circular List,),循环链表是单链表的变形。,循环链表最终一个结点的link指针不为 0(NULL)，而是指向了表的前端。,为简化操作，在循环链表中往往参与表头结点。,循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到全部其他结点的地址。,循环链表的例如,带表头结点的循环链表,用循环链表求解约瑟夫问题,约瑟夫问题的提法,n 个人围成一个圆圈，首先第2个人从1开头一个人一个人顺时针报数,报到第m个人，令其出列。然后再从下一个人开头，从1顺时针报数，报到第m个人，再令其出列，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。,例如 n=3 m=8,例如,n,=3,m,=8,2.4 线性表的应用举例:,一、一元多项式的线性表示,一般的n次多项式A(x)按降幂排列，记为：,A(x)=a,n,x,n,+a,n-1,x,n-1,+.+a,1,x,1,+a,0,，当a,n,0j时称A(x)为n阶多项式,。,在数据构造中,一个n阶多项式可用一个线性表A表示：A=an，an-1，an-2，.，a1，a0 由于多项式中系数不为零的很少，例如：A(x)=8x3000+3为了节省存储空间，应用中只需将多项式中不为零的系数与对应的幂次数用两个数据项进展描述，并表示成线性表，则有：A=(am，em)，(am-1，em-1)，.，(a1，e1)，(a0，e0),二、多项式的加法：一元多项加法运算原则：两个多项式中全部指数一样的项对应系数相加，假设和不为零，则构成“和多项式”中的一项，而全部指数不一样的那些项，均应复制到“和多项式中”。,多项式加法的算法描述：设A、B分别表示两个线性表，A和B相加的结果构成线性表C,其操作步骤如下：线性表C置空；各取线性表A和B的第一个元素分别作为各自线性表当前处理的元素比较当前处理的两个元素的指数值，假设指数相等且它们相加后的系数和不为零，则把系数和与指数值构成一个数据元素加到线性表C中，各取A和B的下一个元素进展处理，假设指数不等，则把指数大的数据元素追加到C中，再取该元素所在表的下一元素，另一表的当前处理元素不变；重复步骤,2.4.2 多项式加法的挨次存储实现方法一、数据元素的定义：,#define MAXN 100,typedef struct term,float coef;,int exp;,TERM;TERM polyMAXN;,A(x),=4,x,80,+7,x,60,+9,x,5,+5,B(x),=2,x,80,-7,x,60,+3,x,12,例：多项式挨次存储的相加,A(x),=4,x,80,+7,x,60,+9,x,5,+5,B(x),=2,x,80,-7,x,60,+3,x,12,两多项式系数与指数在构造数组poly中的存储表示为,4,7,9,5,2,-7,3,.,80,60,5,0,80,60,12,.,0 1 2 3 4 5 6 7 8,MAXN-1,coef,exp,ah,bh,at,bt,free,下标,多项式的链接存储及其相加,在多项式的链表