《ds第二章 线性表.ppt》由会员分享，可在线阅读，更多相关《ds第二章 线性表.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第二章 线性表n n2.1 线性表的类型定义n n2.2 线性表的顺序表示和实现n n2.3 线性表的链式表示和实现n n 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加专升本社会类要求：第2章 线性表（熟练掌握）2.1 线性表的逻辑结构2.2 线性表的顺序存储结构2.3 线性表的链式存储结构2.4 线性表应用举例n n2.1 线性表的类型定义n n线性表线性表(Linear List)Linear List)：由：由n(nn(n)个数据元素个数据元素(结结点点)a a1 1，a a2 2，aan n组成的有限序列。其中数据元组成的有限序列。
2、其中数据元素的个数素的个数n n定义为表的长度。当定义为表的长度。当n=0n=0时称为空表，时称为空表，常常将非空的线性表常常将非空的线性表(n0)n0)记作：记作：n n (a a1 1，a a2 2，aan n)n n这里的数据元素这里的数据元素a ai i(1(1i in)n)只是一个抽象的符号，只是一个抽象的符号，其具体含义在不同的情况下可以不同。其具体含义在不同的情况下可以不同。n n例例1 1、2626个英文字母组成的字母表个英文字母组成的字母表n n （A A，B B，C C、Z Z）n n例例2 2、某校从、某校从19781978年到年到19831983年各种型号的计算年各种型
3、号的计算机拥有量的变化情况。机拥有量的变化情况。n n （6 6，1717，2828，5050，9292，188188）例例3 3、学生健康情况登记表如下：、学生健康情况登记表如下：姓姓 名名学学 号号性性 别别 年龄年龄 健康情况健康情况王小林王小林790631790631 男男 1818 健康健康陈陈 红红790632790632 女女 2020 一般一般刘建平刘建平790633790633 男男 2121 健康健康张立立张立立790634790634 男男 1717 神经衰弱神经衰弱 .从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开
4、始结点在非空的线性表，有且仅有一个开始结点a a1 1，它没有直接前趋，而仅有一个直接后继它没有直接前趋，而仅有一个直接后继a a2 2；有且仅有一个终端结点有且仅有一个终端结点a an n，它没有直接后继，它没有直接后继，而仅有一个直接前趋而仅有一个直接前趋a a n-1n-1；其余的内部结点其余的内部结点a ai i(2(2i in-1)n-1)都有且仅有一个都有且仅有一个直接前趋直接前趋a a i-1i-1和一个直接后继和一个直接后继a a i+1i+1。线性表是一种典型的线性结构。线性表是一种典型的线性结构。n n数据的运算是定义在逻辑结构上的，而运算的数据的运算是定义在逻辑结构上的，
5、而运算的具体实现则是在存储结构上进行的。具体实现则是在存储结构上进行的。n n抽象数据类型的定义为：抽象数据类型的定义为：P P1919 算法2.1n n例例2-1 2-1 利用两个线性表利用两个线性表LALA和和LBLB分别表示两个集合分别表示两个集合A A和和B B，现要求一个新的集合现要求一个新的集合A=AA=AB B。void union(List&Lavoid union(List&La，List Lb)List Lb)La-La-lenlen=listlengthlistlength(La);(La);Lb-Lb-lenlen=listlengthlistlength(Lb);(L
6、b);for(I=1;I for(I=1;I=Lb-len;I=Lb-len;I+)+)getelem(Lbgetelem(Lb，I I，e);e);if if(!locateelem(La(!locateelem(La，e e，equalequal)listinsert(La)listinsert(La，+La-len+La-len，e)e)n n n n 算法2.2n n例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。n n 此问题的算法如下：void mergelist(list la，l
7、ist lb，list&lc)initlist(lc);i=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while(i=la-len)&(j=lb-len)n n getelemgetelem(la(la，i i，aiai););getelemgetelem(lb(lb，j j，bjbj););n n if(if(aiai=bj=bj)listinsertlistinsert(lclc，+k+k，aiai);+i;);+i;else elselistinsertlistinsert(lclc，+k+k，bjbj);+j;);+j;wh
8、ile(i while(i=la-len=la-len)getelemgetelem(la(la，i+i+，aiai););listinsertlistinsert(lclc，+k+k，aiai););while(j while(j=lb-len=lb-len)getelem(getelem(lblb，j+j+，bjbj););listinsertlistinsert(lclc，+k+k，bi);bi);n n 2.2 线性表的顺序存储结构n n2.2.1 2.2.1 线性表线性表 把线性表的结点按逻辑顺序依次存放在一组把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储
9、的线性地址连续的存储单元里。用这种方法存储的线性表简称顺序表。表简称顺序表。假设线性表的每个元素需占用假设线性表的每个元素需占用l l个存储单元，个存储单元，并以所占的第一个单元的存储地址作为数据元素并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第的存储位置。则线性表中第I+1I+1个数据元素的存个数据元素的存储位置储位置LOC(a LOC(a i+1i+1)和第和第i i个数据元素的存储位置个数据元素的存储位置LOC(a LOC(a I I )之间满足下列关系：之间满足下列关系：LOC(a LOC(a i+1i+1)=LOC(a)=LOC(a i i)+l)+l 线性表的第
10、线性表的第i i个数据元素个数据元素a ai i的存储位置为：的存储位置为：LOC(LOC(a ai i)=LOC(a)=LOC(a1 1)+(i-1)+(i-1)*l)*l n n由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。n n#define ListSize 100n n typedef int DataType;n n typedef structn n DataType dataListSize;n n int length;n n
11、Sqlist;n n2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.datai-1。以下主要讨论线性表的插入和删除两种运算。1、插入 线性表的插入运算是指在表的第i(1in+1)个位置上，插入一个新结点x，使长度为n的线性表 (a1，a i-1，ai，an)变成长度为n+1的线性表 (a1，a i-1，x，ai，an)算法2.3n nVoid InsertList(Sqlist&L，DataType x，int i)n n n
12、n int j;n n if(il.length+1)n n printf(“Position error”);n n return ERROR;n n n n if(l.length=ListSize)n n printf(“overflow”);n n exit(overflow);n n for(j=l.length-1;j=i-1;j-)n n l.dataj+1=l.dataj;n n l.datai-1=x;n n l.length+;n nn n 现在分析算法的复杂度。n n 这里的问题规模是表的长度。该算法的时间主要化费在循环的结点后移语句上，所需移动结点的次数不仅依赖于表的长
13、度，而且还与插入位置有关。n n当i=l.length+1时，结点后移语句不进行；这是最好情况，其时间复杂度O（1）；n n当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，n n其其时间复杂度为时间复杂度为OO（n n）。）。n n 由于插入可能在表中任何位置上进行，因由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度此需分析算法的平均复杂度 在长度为在长度为n n的线性表中第的线性表中第i i个位置上插入一个位置上插入一个结点，令个结点，令E Eisis(n)(n)表示移动结点的期望值（即移动表示移动结点的期望值（即移动的平均次数），则在第的平均次数），则
14、在第i i个位置上插入一个结点的个位置上插入一个结点的移动次数为移动次数为n-i+1n-i+1。故故 E Eisis(n)=(n)=p pi i(n-i+1)(n-i+1)不失不失一般性，假设在表中任何位置一般性，假设在表中任何位置(1(1i in+1)n+1)上插入结点的机会是均等的，则上插入结点的机会是均等的，则 p p1 1=p=p2 2=p=p3 3=p=p n+1n+1=1/(n+1)=1/(n+1)因此，在等概率插入的情况下，因此，在等概率插入的情况下，E Eisis(n)=(n)=(n-i+1(n-i+1)/(n+1)=n/2)/(n+1)=n/2 也就是说，在顺序表上做插入运算
15、，平均要移动也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长表上一半结点。当表长 n n较大时，算法的效率相较大时，算法的效率相当低。算法的平均时间复杂度为当低。算法的平均时间复杂度为O(n)O(n)。2 2、删除删除 线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表：(a1，a i-1，ai，a i+1，an)变成长度为n-1的线性表 (a1，a i-1，a i+1，an)Void deleteList(Sqlist&L，int i)int j;if(il.length)printf(“Position error”);return ERROR;for(j=
16、i;jdata=ch;pnext=head;head=p;ch=getchar();return(head);listlink createlist(int n)int data;linklist head;listnode*p head=null;for(i=n;i0;-i)p=(listnode*)malloc(sizeof(listnode);scanf(%d，&pdata);pnext=head;head=p;return(head);2 2、尾插法建表尾插法建表 头插法建立链表虽然算法简单，但生成的链头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者表中
17、结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个点插入到当前链表的表尾上，为此必须增加一个尾指针尾指针r r，使其始终指向当前链表的尾结点。例：使其始终指向当前链表的尾结点。例：linklist linklist creatercreater()()char char chch;linklist linklist head;head;listnode listnode *p*p，*r;r;/head=NULL;r=NULL;head=NULL;r=NULL;while(while
18、(chch=getchargetchar()!=()!=n)n)p=(p=(listnode listnode*)*)mallocmalloc(sizeofsizeof(listnodelistnode););pdata=pdata=chch;if(head=NULL)if(head=NULL)head=p;head=p;else else rnext=p;rnext=p;r=p;r=p;if(r!=NULL)if(r!=NULL)rnext=NULL;rnext=NULL;return(head);return(head);说明：第一个生成的结点是开始结点，将开始结点说明：第一个生成的结点是
19、开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。而其余结点的位置是在其前趋结点的指针域中。算法中的第一个算法中的第一个if if语句就是用来对第一个位置上的语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个插入操作做特殊处理。算法中的第二个if if语句的作
20、语句的作用是为了分别处理空表和非空表两种不同的情况，用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表若读入的第一个字符就是结束标志符，则链表headhead是空表，尾指针是空表，尾指针r r亦为空，结点亦为空，结点*r r不存在；不存在；否则链表否则链表headhead非空，最后一个尾结点非空，最后一个尾结点*r r是终端结是终端结点，应将其指针域置空。点，应将其指针域置空。如果我们在链表的开始结点之前附加一个如果我们在链表的开始结点之前附加一个结点，并称它为结点，并称它为头结点头结点，那么会带来以下两个优，那么会带来以下两个优点：点：a a、由于开始结点的
21、位置被存放在头结点的指由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就针域中，所以在链表的第一个位置上的操作就 和在表的其它位置上的操作一致，无需进行特殊处和在表的其它位置上的操作一致，无需进行特殊处理；理；b b、无论链表是否为空，其头指针是指向头结点无论链表是否为空，其头指针是指向头结点 在的非空指针（空表中头结点的指针域为空），因在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。此空表和非空表的处理也就统一了。其算法如下：其算法如下：linklistlinklist createlist1createlist1()()char cha
22、r chch;linklist linklist headhead=(=(linklistlinklist)mallocmalloc(sizeofsizeof(listnodelistnode););listnode listnode *p*p，*r r r=head;while(ch=getchar()!=n p=(listnode*)malloc(sizeof(listnode);pdata=ch;rnext=p;r=p;rnext=NULL;return(head);二、查找运算 1 1、按序号查找、按序号查找 在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号i i，
23、也不能象顺序表中那样直接按序号也不能象顺序表中那样直接按序号i i访问结点，访问结点，而只能从链表的头指针出发，顺链域而只能从链表的头指针出发，顺链域nextnext逐个逐个结点往下搜索，直到搜索到第结点往下搜索，直到搜索到第i i个结点为止。个结点为止。因此，链表不是随机存取结构。因此，链表不是随机存取结构。设单链表的长度为设单链表的长度为n n，要查找表中第要查找表中第i i个结个结点，仅当点，仅当11inin时，时，i i的值是合法的。但有时的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是需要找头结点的位置，故我们将头结点看做是第第0 0 个结点，其算法如下：个结点，其算法如
24、下：Listnode*getnode(linklist head，int i)int j;listnode*p;p=head;j=0;while(pnext&jnext;j+;if(i=j)return p;else else return NULL;return NULL;2 2、按值查找按值查找 按值查找是在链表中，查找是否有结点值等于按值查找是在链表中，查找是否有结点值等于给定值给定值keykey的结点，若有的话，则返回首次找到的的结点，若有的话，则返回首次找到的其值为其值为keykey的结点的存储位置；否则返回的结点的存储位置；否则返回NULLNULL。查查找过程从开始结点出发，顺着链
25、表逐个将结点的找过程从开始结点出发，顺着链表逐个将结点的值和给定值值和给定值keykey作比较。其算法如下：作比较。其算法如下：Listnode*locatenode(linklist head，int key)p=head-next;while(p!=NULL)if(p-data=key)return p;p=p-next;return NULL;该算法的执行时间亦与输入实例中的的取值该算法的执行时间亦与输入实例中的的取值keykey有关，其平均时间复杂度的分析类似于按序号查有关，其平均时间复杂度的分析类似于按序号查找，也为找，也为O(n)O(n)。三、插入运算 插入运算是将值为x的新结点插
26、入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点ai-1的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：具体算法如下：具体算法如下：void void insertnodeinsertnode(linklist linklist head head，datetype datetype x x，int int i)i)listnode listnode *p*p，*q;q;p=getnode(headp=getnode(head，i-
27、1);i-1);if(pif(p=NULL)=NULL)errorerror(position errorposition error););q=(q=(listnode listnode*)*)mallocmalloc(sizeofsizeof(listnodelistnode););qdata=x;qdata=x;qnext=pnextqnext=pnext;p pnext=q;next=q;设链表的设链表的长度为长度为n n，合法的插入位置是合法的插入位置是1 1i in+1n+1。注意当注意当i=1i=1时，时，getnodegetnode找到的是头结点，当找到的是头结点，当 i=n+
28、1i=n+1时，时，getnodegetnode找到的是结点找到的是结点a an n。因此，用因此，用i-i-1 1做实参调用做实参调用getnodegetnode时可完成插入位置的合法性时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作检查。算法的时间主要耗费在查找操作getnodegetnode上，上，故时间复杂度亦为故时间复杂度亦为O(n)O(n)。四、删除运算 删除运算是将表的第删除运算是将表的第i i个结点删去。因为在单个结点删去。因为在单链表中结点链表中结点a ai i的存储地址是在其直接前趋结点的存储地址是在其直接前趋结点a a i-1i-1的指针域的指针域nextnex
29、t中，所以我们必须首先找到中，所以我们必须首先找到 a a i-1i-1的存储位置的存储位置p p。然后令然后令pnextpnext指向指向a ai i的直的直接后继结点，即把接后继结点，即把a ai i从链上摘下。最后释放结点从链上摘下。最后释放结点a ai i的空间，将其归还给的空间，将其归还给“存储池存储池”。具体算法如下具体算法如下：void deletelist(linklist head，int i)listnode*p，*r;p=getnode(head，i-1);if(p=NULL|pnext=NULL)return ERROR;r=pnext;pnext=rnext;free
30、(r);设单链表的长度为n，则删去第i个结点仅当1in时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点（即pnext!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是O(n)。从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。2.3.2 循环链表 循环链表是一种头尾相接的链表。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。
31、为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：a1 an .head 非空表 空表 在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rearnext)next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链
32、表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。2.3.3双向链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：typedef struct dlistnode datatype data;struct dlistnode*prior，*next;dlistnode，*dlinklist;和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链
33、表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：(pprior)next=p=(pnext)priorpprior)next=p=(pnext)prior 即结点*p的存储位置既存放在其前趋结点的直接后继指针域中，也存放 在它的后继结点的直接前趋指针域中。双向链表的前插操作算法如下：void dinsertbefor(dlistnode*p，datatype x)dlistnode *q=malloc(sizeof(dlistnode);qdata=x;qprior=pprior;qnext=p;
34、ppriornext=q;pprior=q;void ddeletenode(dlistnode*p)ppriornext=pnext;pnextprior=pprior;free(p);注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。填空(1)在顺序表中插入或删除一个元素，需要平均移动_元素，具体移动的元素个数与_有关。(2)顺序表中逻辑上相邻的元素的物理位置_紧邻。单链表中逻辑上相邻的元素的物理位置_紧邻。(3)在单链表中，除了首元结点外，任一结点的存储位置由_指示。(4)在单链表中设置头结点的作用是_。答:
35、(1)表中一半，该元素的位置。(2)必定，不一定。(3)其直接前驱结点的链域的值。(4)插入和删除首元素时不必进行特殊处理思考n n1、已知一个顺序表中元素按元素值非递减有序排序，编写一个函数删除顺序表中多余的值相同的元素，返回顺序表新长度。n n2、单链表的倒置。比如一个链表是这样的：1-2-3-4-5 通过反转后成为5-4-3-2-1 n n3、线性表的合并。intint deldel(SqlistSqlist&L&L，intint n)n)intint i=0,j;i=0,j;while(i=n-1)while(i=n-1)if(if(L.dataL.datai!=L.datai+1)i
36、+;i!=L.datai+1)i+;elseelse for(for(j=i;jj=i;jnext;pre=head;cur=head-next;while(cur)while(cur)nene=cur-next;=cur-next;cur-next=pre;cur-next=pre;pre=cur;cur=pre=cur;cur=nene;head-next=NULL;head-next=NULL;head=pre;head=pre;2 2、遍历一遍链表，利用一个辅助指针，存储遍历过程中的、遍历一遍链表，利用一个辅助指针，存储遍历过程中的下一个元素，然后将当前节点元素的指针反转后，利用已经下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。存储的指针往后面继续遍历。