《数据结构》课件第二章

第二章线性表内容提要线性表的基本概念（逻辑结构）线性表的存储结构及相关操作和运算顺序存储的表示和实现链式存储的表示和实现单链表静态链表循环链表双向链表线性表的应用2.1线性表的类型定义线性表：是n个数据元素的有限序列。线性结构的特点：存在唯一一个被称为“第一”的数据元素存在唯一一个被称为“最后”的数据元素除第一个之外，集合中的每个数据元素均只有一个前驱除最后一个之外，集合中的每个数据元素均只有一个后继2.1线性表的类型定义线性表的特点：同一性——线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性——线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性——线性表中表中相邻数据元素之间存在着序偶关系<ai,ai+1>。线性表的基本操作(逻辑）构造一个空表L获取L的长度（即元素个数）访问L中第i个数据元素的值访问L中第i个数据元素的前驱/后继的值在L中第i个元素之前插入新的元素e删除L的第i个数据元素注意在插入或者删除之后，线性表的长度应能随之改变一

顺序存储线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构：物理位置相邻数据元素之间的逻辑关系也相邻顺序表的类型定义1——静态#defineMAXSIZE100typedefstruct{charData[MAXSIZE];//100个字节intcurlen;//4个字节inttotalLen;//4个字节}SeqList,*PSeqList;//SeqList是什么？

定义的新结构体类型名称//PSeqList又是什么？指向该结构体的新指针类型名称SeqListlist1,list2;//list1和list2是什么？两个结构体变量，每个变量占108个字节//其空间是否存在？存在，当定义变量时，就已分配好对应的存储空间顺序表的类型定义2——动态typedefstruct{char*pData;//4个字节

intcurLen;//4个字节inttotalLen;//4个字节}SeqList,*PSeqList;//SeqList是什么？

定义的新结构体类型名称//PSeqList又是什么？指向该结构体的新指针类型名称SeqListlist1,list2;//list1和list2是什么？两个结构体变量，每个变量占12个字节，一个变量表示一个线性表，而不是一个元素！//其空间是否存在？变量存在，但指针成员指向的存储数据的空间不存在，尚未为pData指针分配空间（pData值未确定或者说pData未指向任何空间）list1.pData=(char*)malloc(100*sizeof(char));//分配空间，本行代码在顺序表的创建函数中执行。注意，一定要判断malloc的返回值！L——顺序表的变量名或对象名或者地址L.curlen——线性表的长度L.curlen=0L是空表L.curlen=MaxL是满表相关操作创建顺序表静态下如何创建?动态下如何创建？算法的时间复杂度是常数c=O(1)相关操作访问第i个元素采用顺序表这种存储结构，如何实现这个逻辑操作？因为顺序存储结构具有“直接存取”的特点，所以Y=L.Data[i];算法的时间复杂度是常数c=O(1)2.在第i个元素前插入值为x的元素已知：L,i,xL——顺序表的变量名或对象名或地址i——要插入的元素的逻辑编号（设从1开始）x——要插入的元素的值在右移元素和插入元素之前首先应判断该表是否已经是满表，且i的值必须在1～L.len+1之间121321242830427712345678插入25序号121321242528304277123456789一般来说，在第i（1<=i<=n)个元素之前插入一个元素时，需将第n至第i（共n-i+1个元素）向后移动一个位置序号顺序表插入插入算法的时间复杂度分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：关于“上溢”问题的预防取Max为充分大：内存浪费大，且有可能在内存中没有如此大的连续空间块，且仍有可能在插入大量的元素后终究产生上溢（下策）动态修改Max的值：操作系统在编译时自动寻找更大的内存空间连续块，将原表整体复制到新的内存块中，同时更改该表的首地址，但仍不能从根本上消除上溢3.删除第i个元素已知：L,i注意参数校验和下溢7742302824211312删除24774230282113121234567812345678序号序号一般来说，删除第i（1<=i<=n)个元素时，需从第i+1至第n（共n-i）个元素依次向前移动顺序表的删除删除操作的时间复杂度分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：a1a2……an对顺序存储的一点改进在插入和删除时，先判断i是否小于n/2，再决定左移还是右移思考：该算法时间复杂度是多少？ T(n)=O(n/4)

LR3.线性表的合并LA、LB分别表示两个集合，现要求对线性表做如下操作：扩大LA，将存于LB中而不在LA中的数据元素补到LA集合后面。….….…LALB新的LA…LB中的每个元素是否要插入，需要遍历整个LA的长度的个数才知道。那么整个时间的复杂度为O(listlength(LA)*listlength(LB))有序线性表的合并LA、LB分别表示两个集合，且其中的数据元素按非递减有序排列并且不重复，现要求将两表合并为一个新表LC，其中的数据元素仍按非递减排列，且也不重复。a<b

则拷贝a，后移paa>b

则拷贝b，后移pb比较当某个表先比较完时，另一个表后面的数据元素直接插入Lc中118532015119862LALB算法算法的时间复杂度为O(La.length+Lb.length)a=b

则拷贝a或b，后移pa,pbpapb思考：为何不是O(La.length*Lb.length)？2.3线性表的链式表示和实现顺序线性表的缺点：插入和删除操作时需要移动大量元素。要给长度变化较大的线性表预先分配空间，利用率不好。表的容量难以扩充线性链表存储的特点：用一组任意的存储单元存储线性表的数据元素（可连续可不连续）(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)31头指针H存储地址数据域指针域0x10x70x130x190x250x310x370x43LIQIANSUNWANGWUZHAOZHENGZHOU0x430x130x1NULL0x370x70x190x25datanext链表的存取必须从头指针开始H头结点HZHAOQIANSUNLIZHOUWUZHENGWANG∧

∧

空表头指针HtypedefstructLnode//结点类型定义{elemtypedata；structLnode*next；}Lnode,*LinkList；//LinkList为结构指针类型Java语言没有指针，如何实现链表？Java语言中的对象引用，能实现类似指针的作用。classNode{Objectdata;Nodenext;//指向下一个结点}将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。插入操作的时间复杂度O(n/2)链表中的插入、删除操作没有上溢的情况，并且节省内存资源思考：若现已知道指向某元素节点的指针p，希望能在该节点之前插入元素x，该如何操作？其算法时间复杂度是多少？abpc…删除b删除的表示为(不保留删除点）P-next=P->next->next删除第i个元素，由e返回值1)寻找第i-1个结点2)保留结点b的地址3)将a的指针指向结点c4)释放结点b（值赋给e）3)单链表的删除4)单链表的生成输入一：an、an-1、…

a2、a1输入二：a1、a2、…

an-1、an流程图如何画？思考求一个单链表的表长算法在一个单链表中查找某个值的算法在L表的表尾插入S表，合成一个新表L合并有序链表的方法和复杂度的分析合并有序链表的方法与顺序表相比，时间复杂度相同，空间复杂度不同，归并成新表时不需要建立新的结点空间，只需将原来链表结点之间的关系解除、建立新的结点链接即可。（顺序表借助了数组来完成）静态链表链表有时可以不用指针来表示，而使用一维数组来描述#definemaxsize1000//事先分配空间Typedefstruct{Elemtypedata;intcur;//游标代替指针指示结点在数组中的相对位置}这种结构需要事先分配空间，在做插入和删除等操作时不需要移动元素，只需修改指针(整数cur)的值0WANG8ZHENG7WU6ZHOU5LI4SUN3QIAN2ZHAO19876543210头结点5SHI0WANG8ZHENG7WU6ZHOU9LI4SUN3QIAN2ZHAO198765432105SHI0WANG8ZHENG8WU6ZHOU9LI4SUN3QIAN2ZHAO19876543210i=s[i].cur指针后移s[0].cur第i个分量表示链表的第k个结点，则s[i].cur指示第k+1个结点的位置插入元素SHI删除元素ZHENG相关操作1.访问静态链表中第i个元素（i为逻辑顺序）设p表示数组下标值的整型量，AA为静态数组2.在第i个元素之前插入元素x思考静态链表的删除操作应该怎么做?如何维护备用链表?6SHI0WANG9ZHENG8WU0ZHOU3LI5SUN4QIAN2ZHAO19876543210BK6SHI0WANG9ZHENG8WU0ZHOU5LI7SUN4QIAN2ZHAO19876543210BK2.3.2循环链表特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环；从表中任一结点出发都可以找到表中其他结点。

…L

L循环结束条件不是P或P->next是否为空，而是P->next=L循环链表的访问操作已知L，访问头节点之后的第i个元素思考若已知L和p，如何访问p节点之后的第i个元素？若已知L和p，如何在p节点之前插入元素x？删除节点p1)表中只有一个元素

L

Hp布尔条件：L.next=p并且p.next=L实施方法：L.next=L;

dispos(p); 2)表中至少有两个元素，而p是最后一个元素

…Lpq方法：将q的数据传至p节点，然后再删除q节点

q=L.next;

p.data=q.data; L.next=q.next;

dispos(q);3)表中至少有两个元素，而p不是最后一个元素

…Lpq方法：将q的数据传至p节点，然后再删除q节点

q=p->next;

p->data=q->data; p->next=q->next;

dispos(q);

…作业有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。提示：循环链表的特点找到两个表的表尾，对指针做适当的修改思考：有没有更好的方法?双向链表定义：链表中的结点有两个指针域，一个指向直接后继，一个指向直接前驱。priorelementnextLABCLd->next->prior=d->prior->next=dABCL双向链表的插入和删除LABCxsPP->prior->next=s;s->prior=p->prior;S->next=p;P->prior=s;插入删除P->prior->next=p->next;P->next->prior=p->prior;操作4在操作1之后,否则p的前驱指针会丢失应用1:约瑟夫问题(点杀罪犯问题)约瑟夫（Joseph）问题：一个旅行社要从n名旅客中选出一名幸运旅客，为他提供免费环球旅行服务。方法是，大家站成圈，然后选定一个m，从第1个人开始报数，报到m时，这个人OUT，然后从下一个人开始重新从1报数，重复这个过程，直到最后剩下一个人就是幸运之星。问题就是谁是幸运者呢？或者说是怎样才能赢大奖。约瑟夫问题已知p和m(m>1),数据结构采用无表头的循环单向链表约瑟夫问题的延伸有许多问题都是在这个问题基础上的变化，但实质都是一个循环链表的相关操作。若要求顺时针删除第u个数后再逆时针删除第v个数，则抽象模型变为双向循环链表应用2:一元多项式的表示和相加在数学上，一个一元多项式Pn(x)可按升幂的形式写成：若假设m<n，则两个多项式相加的结果Rn(x)=Pn(x)+Qm(x)，也可以用线性表R来表示：存储方式：顺序存储结构来存储多项式：p［0］存系数p0，p［1］存系数p1,…,p［n］存系数p

n缺点：多项式项数少、指数高时会造成空间的浪费链表存储结构来存储多项式：typedefstructPolynode{intcoef;//系数

intexp;//指数

Polynode*next;}//指向下个结点的指针-1703198517polya多项式相加的运算规则 两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。允许算法执行后更改原本的数据结构。“比较”的思路设p、q分