数据结构-清华大学-殷人昆-02

第二章线性表清华大学计算机系殷人昆数据结构课件第二章线性表排排坐吃果果最有童趣最有规矩的线性表101-2线性表顺序表链表顺序表与链表的比较字符串多项式第二章线性表101-3线性表(LinearList)线性表的定义和特点定义n（≥0）个数据元素的有限序列，记作（a1,a2,…,an）ai是表中数据元素，n是表长度。特点线性排列除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。101-4理解线性表的要点是a)表中元素具有逻辑上的顺序性，在序列中各元素排列有其先后次序。b)表中元素个数有限。c)表中元素都是数据元素。就是说，每一表元素都是不可再分的原子数据。d)表中元素的数据类型都相同。这意味着每一表元素占有相同数量的存储空间。a1a2a3a4a5a6101-5顺序表(SequentialList)顺序表的定义和特点定义将线性表中的元素相继存放在一个连续的存储空间中，即构成顺序表。存储它是线性表的顺序存储表示，可利用一维数组描述存储结构。特点元素的逻辑顺序与物理顺序一致。访问方式可顺序存取，可按下标直接存取。253457164809012345elem101-6顺序表的连续存储方式LOC(i)=LOC(i-1)+l=a+i*l,LOC是元素存储位置，l是元素大小LOC(i)=LOC(i-1)+l=a+i*l,i0a,i=0a+i*l352749186054778341020123456789lllllllllla101-7顺序表的静态结构定义#defineListSize100//最大允许长度typedefintElemType;//元素的数据类型typedefstruct{ElemTypeelem[ListSize];//存储数组intlength;//当前表元素个数}SeqList;顺序表静态定义，假定L是一个类型SeqList的顺序表，一般用L.elem[i]来访问它。表一旦装满，不能扩充。101-8顺序表的动态结构定义#defineListSize100//最大允许长度typedefintElemType;//元素的数据类型typedefstruct{ElemType*elem;//存储数组intlength;//当前表元素个数intmaxSize;//表的最大长度}SeqList;顺序表动态定义，它可以扩充，新的大小计入数据成员maxSize中。101-9顺序表基本运算的实现构造一个空的顺序表voidInitList(SeqList&L){L.elem=newElemType[ListSize];if(L.elem==NULL){printf(“存储分配失败!\n”);exit(1);}L.length=0;L.maxSize=ListSize;}判断L.elem是否为空语句是后置条件。101-10动态分配命令new是Pascal、C++、Java常用的语句，它的作用与C的malloc命令等效，但比malloc简洁，它不用计算分配字节数，不用做指针转换，一切工作new替你代劳了。注意指针的使用。指针所指示元素也有它的数据类型。例如对于指针*p和*q：char*p=newchar[maxSize];float*q=newfloat[maxSize];用p++让p指到下一字符位置，用q++让q指到下一浮点数位置，它们移过的字节数不同。101-11引用型参数&的使用例如，voidInitList(SeqList&L)C++的引用型参数“&”与Pascal的变量参数一样，是把形参L看作是实际变量（一个表）的别名，在函数体内对L的操作将是直接对实际变量的操作。好处之一是可在函数体内像普通变量那样对L操作，使得操作简单。好处之二是可直接从实际变量得到操作结果。好处之三是不必创建实际变量的副本空间。101-13按值查找：在顺序表中从头查找结点值等于给定值x的结点intFind(SeqList&L,ElemTypex){inti=0;while(iL.length&&L.elem[i]!=x)i++;if(iL.length)returni+1;//i与实际位置elsereturn0;//差一}注意iL.length&&L.elem[i]!=x位置不能颠倒101-14查找成功的平均比较次数若查找概率相等，则查找不成功数据比较n次。i-1n0iicp=ACN2n12nn)(1n1n)2(1n11)(in1=ACN-1n0i查找算法性能分析101-15表项的插入boolInsert(SeqList&L,ElemTypex,inti){//在表中第i(1≤i≤n+1)个位置插入新元素xif(i1||iL.length+1)return0;if(L.length==ListSize)return0;//参数不合理或表已满，插入不成功for(intj=L.length-1;j=i-1;j--)L.elem[j+1]=L.elem[j];L.elem[i-1]=x;//实际插在第i-1个位置L.length++;return1;//插入成功}101-162n21)n(n1)(n10)1(n1n1i)(n1n1=AMNn0i2534571648096301234567L.elem50插入x253457501648096301234567L.elem50i=4101-17boolDelete(SeqList&L,inti,ElemType&x){//在表中删除第i个元素，通过x返回其值if(i0&&i=L.length){x=L.elem[i-1];L.length--;for(intj=i-1;j=L.length;j++)L.elem[j]=L.elem[j+1];return1;//成功删除}return0;//表中没有x}表项的删除101-18-1n0i21n21)n(nn11)i(nn1=AMN253457501648096301234567L.elem16删除2534575048096301234567L.elem表项的删除平均移动元素个数AMN101-19链表（LinkedList）线性链表是线性表的链接存储表示。元素之间的逻辑顺序是通过各结点中的链接指针来指示的。线性链表分类：单链表循环链表双向链表101-20特点每个元素(表项)由结点(Node)构成。线性结构结点可以连续，可以不连续存储结点的逻辑顺序与物理顺序可以不一致表可扩充单链表(SinglyLinkedList)datalinka1a2a3a4a5∧first101-21单链表的存储映像free(a)可利用存储空间a1a3a2a4∧freefirst(b)经过一段运行后的单链表结构101-22单链表的结构定义typedefcharElemType;typedefstructnode{//链表结点ElemTypedata;//结点数据域structnode*link;//结点链域}ListNode;typedefListNode*LinkList;//链头指针使用时定义实际链表，只需定义链表头指针LinkListfirst;//链表头指针101-23有关指针的一些概念在链表中，如果没有定义重载“++”函数，不能使用p++这样的语句进到逻辑上的下一个结点。一般用p=p-link进到下一结点。datalinkp指示结点地址datalinkp-结点本身datalinkp-data结点data域的值datalinkp-link结点link域的值101-24单链表中的插入与删除插入的考虑第一种情况：在第1个结点前插入：newnode-link=first;first=newnode;//修改头指针（插入前）（插入后）firstnewnodenewnodefirst101-25第二种情况：在链表中间插入：首先定位指针p到插入位置，再将新结点插在其后：newnode-link=p-link;p-link=newnode；(插入前)(插入后)newnodepnewnodep101-26第三种情况：在链表末尾插入：首先定义指针p到尾结点位置，再将新结点插在其后，新结点成为新的尾结点。newnode-link=p-link;p-link=newnode；(插入前)(插入后)newnodenewnodepp101-27boolInsert(LinkList&first,ElemTypex,inti){//在链表第i(≥1)个结点处插入新元素xListNode*p=first;intk=1;while(p!=NULL&&ki-1){p=p-link;k++;}//找第i-1个结点if(p==NULL&&first!=NULL){printf(“无效的插入位置!\n”);return0;//给的i太大}ListNode*newnode=newListNode;//创建新结点101-28newnode-data=x;if(first==NULL||i==1){//插在表前端newnode-link=first;first=newnode;}//考虑为何在参数表中first定义为引用型else{//插在表中或末尾newnode-link=p-link;p-link=newnode;}return1;}101-29删除的考虑第一种情况:删除表中第1个元素第二种情况:删除表中或表尾元素在单链表中删除含ai的结点ai-1ai-1aiaiai+1ai+1pq删除前删除后101-30boolDelete(LinkList&first,inti,ElemType&x){//在链表中删除第i个结点。如果要删除表中第1个//结点，需要改变表头指针，所以first定义为引用//型，被删元素的值通过引用型参数x返回ListNode*p,*q;if(i==1)//删除表中第1号结点{q=first;first=first-link;}else{p=first;intk=1;//找第i-1个结点while(p!=NULL&&ki-1){p=p-link;k++;}101-31if(p==NULL||p-link==NULL){printf(“无效的删除位置!\n”);return0;}else{//删除表中或表尾元素q=p-link;//重新链接p-link=q-link;}x=q-data;deleteq;//删除qreturn1;//delete作用与free相同}101-32带头结点的单链表头结点位于表的最前端，本身不带数据，仅标志表头。设置头结点的目的是统一空表与非空表的操作简化链表操作的实现。非空表空表∧ana1firstfirst∧101-33前插法建立单链表从一个空表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端直到读入结束符为止。firstnewnodefirstnewnode∧∧（空表）（非空表）101-34LinkList&createListF(ElemTypefinishi){ElemTypex;ListNode*s;LinkListfirst=newListNode;//建立头结点first-link=NULL;cinx;//约定以finish结束连续输入while(x!=finish){newNode=newListNode;//建立新结点newNode-data=x;newNode-link=first-link;//插入到表前端first-link=newNode;cinx;}101-35returnfirst;}主程序可用LinkListL=createF(fin