DS-数据结构线性表完美版资料.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第2章 线性表,线性表的顺序存储,线性表的链式存储,线性表两种不同存储结构的比较,线性表的应用,具体介绍一种数据结构时，总是从下述三个方面展开：,逻辑结构：,是从逻辑关系上描述数据，可看作上从具体问题中抽象出来的数据模型，与计算机存储无关。,存储结构：,是逻辑结构在存储器中的实现（数据及其关系运算的映像）。,数据操作：,是定义在数据逻辑结构上的一组运算。每种数据结构都有一个运算集合。,书中给出的数据类型的描述，实际上是一种数据结构在某一存储结构下的实现。,2.1 线性表的基本概念,线性结构,的基本特征是：,有而且只有一个“第一元素”；,有而且只有一个“最后元素”；,除第一元素之外，其他元素都有唯一的,直接前趋；,除最后元素之外，其他元素都有唯一的,直接后继。,线性表是一种常用的简单的数据结构，它属于线性结构的范畴。,线性表（Linear List）,是具有相同数据类型的n(n0)个数据元素的有限序列，通常记为：,(a,1,，a,2,，a,i-1,，a,i,，a,i+1,，a,n,),其中，数据元素的个数n称为线性表的,长度,。,当n0 时称为,空表,。,字母表（A,B,C,Z）的表长是26，起始结点是A，没有直接前趋，A的唯一的直接后继是B；终端结点Z没有直接后继，Z的唯一的直接前趋是Y；而对于B,C,D,Y中的任意一个字母，都有一个唯一的,直接前趋,和一个唯一的,直接后继,。,例2.3,26个大写英文字母表,线性表的基本操作,initList(L),：初始化操作，置L为空线性表。,ClearList(L),：,清除线性表的内容，将L 置为空线性表,ListLength(L),：,求表长(表中元素个数),ins(L，i，Item),：,插入数据,Del(L，i),：,删除数据,GetNext(L，Item，p),:获取下一个结点,线性表的基本操作,GetNode(L，i),：,获取表L中位置i的结点值,Loc(L，Item),：,定位(按值查找),GetPrior(L，Item，p),：,获取值为Item的结点的前趋结点,这是一个算法，在此是用C语言编写的一个函数,2.2,线性表的顺序存储,线性表,的顺序存储方式，就是利用一段,连续的内存,地址来存储线性表的数据元素。在C语言中，用一个,数组,来实现。,线性表,的这种机内表示称作线性表的,顺序存储结构,或,顺序映象,。同时，我们把这种顺序存储结构的线性表称为,顺序表,。,对线性表A,(a,1,，a,2,，a,i-1,，a,i,，a,i+1,，a,n,),a,1,a,2,a,i-1,a,i,a,i+1,a,n,typedef,struct,char name20;/*,姓名,*/,char no10;/*,学号,*/,float score;/*,成绩,*/,STUDENT,；,STUDENT s20;,则s就是一个以STUDENT类型为数据元素的线性表。,例2.4,一个顺序存储结构的,线性表,的例子,线性表L,中，若每个元素占用m个存储单元，则第i+1个数据元素的存储位置,LOC(i+1),和第i个数据元素的存储位置,LOC(i),之间满足如下关系：,LOC(i+1)=LOC(i)+m,线性表L的第i个元素的存储位置和第一个元素的存储位置的关系为：,LOC(i)=LOC(1)+(i-1)*m,其中,LOC(1),是线性表的第一个数据元素的存储位置，通常称为线性表的,起始位置,或,基地址,。,顺序表的基本操作,顺序表的C语言描述,typedef int datatype;,/*定义表元素类型*/,#define maxsize 1024,;,/*线性表的最大长度*/,typedef struct,datatype elemmaxsize,;,/*,存放表结点的数组*/,int length;,/*表长*/,sequenli,顺序表的基本操作,顺序表的初始化,算法2.1,构造一个空的顺序表,void InitList(sequenlist*L),L-length=0;,删除一个线性表,要删除一个已经存在的线性表，只需要把该线性表设置为空表，也就是把表长置为0。,算法2.2,删除一个线性表,void DestroyList(sequenlist*L),L-length=0;,本算法时间复杂度为O（1）。,顺序表的基本操作,定位(按值查找),：,要查找一个值，只需要从头到尾的遍历线性表，如果找到，则返回找到的位置，否则继续，如果一直到最后一个位置都没有找到，则返回-1。,本算法中，n是线性表的长度；可能找到值为Item的元素，也可能找不到Item，这时候，算法的比较次数为O(n)。因此，总结起来，本算法的时间复杂度为O(n)。,顺序表的基本操作,int Loc(sequenlist L，datatype item),int i,j;,j=L.length;,/*表的长度*/,if(j=0)return,FALSE,;,for(i=1;ilength)return FALSE；,for(j=L-ength;ji-1;j-),/*因为数组的下标从0开始*/,L-elemj=L-elemj-1;,/*后移*/,L-elemi-1=item;,/*插入*/,L-length+;,/*元素个数增1*/,return TRUE;,本算法的时间主要花在移动数据上，n是线性表的长度。因此，本算法的时间复杂度为,O(n),。,删除数据,删除数据和插入数据很相似，都要求判断i的值是否合适，如果位置合适，则把后面的数据向前移动，删除成功，表的长度,减1,，返回TRUE，否则，返回FALSE。如下图所示：,顺序表的基本操作,删除前,删除后,算法2.5,删除线性表中第i个结点数据,int Del(sequenlist*L，int i),int j;,if(iL-length-1),return FALSE；,for(j=i;jlength-1;j+),L-elemj=L-elemj+1;,L-length-;,return TRUE；,2.3 线性表的链式存储,为了提高增加、删除元素的效率，介绍线性表的另一种存储方式,链式存储,。,在链式存储方式中，能够方便地增加和删除线性表中的元素，但是同时也使随机存取、获取直接前趋和直接后继变得较为复杂。,一个数据元素映射到内存后叫,结点,链表,：,以链式结构存储的线性表称之为,链表,（Linked List）,链式存储结构是用一组,任意的,存储单元来存储线性表的,结点,。,也就是说，链式存储结构中，存储单元可以是,相邻,的，也可以是,不相邻,的；同时，相邻的存储单元中的数据，不一定是相邻的结点。,存储地址,数据域,指针域,1,李,40,7,张,15,头指针,H,15,赵,NULL,20,王,1,40,钱,14,14,孙,13,13,吴,7,例2.7,线性表（“王”，“李”，“钱”，“孙”，“吴”，“张”，“赵”）的单链表示意图,存放数据元素的结点至少包含两个域,数据域,和,指针域,数据域,存放元素的数据,指针域,存放其后继元素的存储地址,指针域中存放的信息称为指针或链，n个结点连接成一个链表，称为线性表的,链式存储结构,只有一个,指针域,的,链表,，称为,单链表,。,用,单链表,表示线性表时，结点之间的逻辑关系是由结点中的指针指示的，如下图。,typedef,struct LNode,ElemType data；,/数据域,Struct LNode*next;,/指针域,LinkList;,LinkList*L,*head;,单链表,的C语言描述：,这里的L（或head）可以作为单链表的,头指针,，它指向该链表的第一个结点。如果L=NULL，则表示该单链表为一个,空表,，其长度为0。,为了更方便的判断空表、插入和删除结点，我们在,单链表,的第一个结点前面加上一个附设的节点，称为,头结点,。,头结点的数据域可以不存储任何信息，也可以存储一些附加信息；而头结点的指针域存储链表第一个结点的地址。,如果,头结点,的,指针域,为“空”，即L-next=NULL，则表示该链表为,空表,。,整个链表的存取必须从头指针开始进行！,单链表的基本操作,清除带头单链表的内容,分析：要清除链表的内容，就必须从头结点开始，,依次的释放,每一个节点所占有的存储空间，然后把表长设置为0，头结点的next域设置为NULL。,int ClearList(LinkList*L),/*使线性表L变成空表*/,LinkList*temp;,while(L-next!=NULL),temp=L-next;,/*使工作指针指向第1个结点*/,L-next=L-next-next;,free(temp);,return TRUE;,算法2.6,清除带表头单链表内容,本算法首先把,头结点,指向第二个结点，然后释放第一个结点的存储空间，依此类推。,要清除表的内容，就必须对链表进行一次遍历，因此，时间复杂度为O(n)，其中，n表示链表的长度。,分析：,由于在结点中没有保存链表的长度，因此，要获得表长，必须对链表进行完整的遍历。,求表长,算法2.7,求带表头单链表长度(结点数),int ListLength(LinkList*L),int len=0;LinkList*temp;temp=L;,while(temp-next!=NULL),len+;temp=temp-next;,return len;,本算法时间复杂度为O(n)，其中n是链表的长度。,单链表的基本操作,定位(按值查找),：,分析：与求链表长度类似，要在链表中查找,给定值,的结点，也需要对链表进行遍历。,算法2.8,在带表头单链表中按值查找定位,int Loc(LinkList*L，ElemType Item),int i=0;,/*记值为Item 的结点在表中的位置*/,LinkList*temp;,temp=L-next;,/*使temp指向第一个结点*/,while(temp!=NULL&temp-date!=Item),i+;temp=temp-next;,if(temp=NULL)return 0;,else return i;,本算法的时间复杂度为O(n)。,单链表的基本操作,插入数据（在第i个结点的后面插入）,：,解决：,插入时的新结点从何处取?链表与向量不同，向量建立时已定义好它的存储空间，而链表的结点数事先不确定。但我们,设想：,内存中有一个可用空间表，要调用新结点时就到这个可用空间表中去,取,，,删除时就把这个结点归,还,给这个可用空间。,分析：,在链表中插入数据比较方便，不需要进行大量的数据移动。只需要找到插入点即可，我们给出的是一个后插入的算法，也就是在插入点的后面添加结点，如图所示。,算法2.9,在带表头单链表第i个结点之后插入结点,int Ins(LinkList*L，int i，ElemType Item),int j=1;LinkList*node,*temp;,node=(LinkList*)malloc(sizeof(LinkList);,if(node=NULL),return FALSE;,node-data=Item;,temp=L,-next,;,/*使temp指向第一个结点*/,if(temp=NuLL),/*作为第一个结点插入*/,if(i=0),L-next=node;,node-next=NULL;,return TRUE;,else,/*插入位置不合理*/,return FALSE;,while(jnext;,j+;,/*向后查找第i个结点*/,if(temp=NULL),/*已找到表尾了*/,return FALSE;,node-next=temp-next;,temp-next=node;,return TRUE;,单链表的基本操作,删除数据,：,删除第i个结点,分析,：,在带表头结点的单链表中，删除数据和插入数据很相似。也是一个寻找删除点，找到后进行指针赋值的一种操作。,算法2.10,删除第i个结点,int Del(LinkList*L，int i),LinkList*temp,*q;int j=0;,temp=L;,/*工作指针指向头结点*/,if(temp-next=NULL),/*空表*/,return FALSE;,while(jnext!=NULL),j+;temp=temp-next;,/*找第i-1个结点*/,if(temp-next=NULL),/*第i个结点不存在*/,return FALSE;,q=temp-next;,/*q指向第i个结点*/,temp-next=q-next;,free(q);,/*释放q结点*/,return TRUE;,本算法的时间复杂度也是O(n)。,是一种首尾相接的链表。在单链表中，最后一个结点的指针域为空（NULL），如果,使线性链表的最后一个结点的指针域存放链表的表头结点的地址,，,则能构成一个单链形式的循环链表，简称为单循环链表；如果链表中每个结点都具有两个指针域，就称为是双向链表。,循环链表（Circular Linked List）,特点：,在循环线性链表中，从表的任何一个结点出发都能访问到表中的所有结点。,带头结点的单循环链表,单循环链表的操作,循环链表的建立,分析：,循环链表是对单向链表的一种改善。单向链表中末尾结点的next=NULL，只需要把这个结点的next域的值设置为头结点的地址，就能够获得一个循环链表。,创建一个空循环链表,的算法：,算法2.11,创建单循环链表,int InitCList(LinkList*L),L=(LinkList*)malloc(sizeof(LinkList);,if(L=NULL),/*申请结点不成功*/,return FALSE;,L-next=L;return TRUE;,本算法时间复杂度为O(1)，和创建单向空链表相同，唯一的区别是：,带头结点单空链表中,L-next=NULL,带头结点空循环链表中,L-next=L,（也就是指向了自身）,单循环链表的操作,空循环链表的判断：,分析：,在单向链表中，判断一个链表是否为空，只需要看头结点的next域是否为,NULL,；相似的，在循环链表中，要判断一个链表是否为空，只需要,看头结点的,next,域是否等于自身,。算法如下：,算法2.12,判断单循环链表是否为空,int isempty(LinkList*L),if(,L-next=L,),return TRUE;,else,return FALSE;,本算法时间复杂度为O(1)。,单循环链表的操作,算法2.13,插入结点(在i位置),int InsertCList(LinkList*L，int i，ElemType e),int j;,/*,在单循环链表L中的第i个位置插入值为e结点*/,LinkList*temp,*node,;,temp=L;,j=1;,while(jnext!=L),j+;temp=temp-next;,/*找第i-1位置后*/,/*使temp指向第i-1个结点，这时j=i*/,if(jnext=L),/*无合适的插入位置*/,return FALSE;,node=(LinkList*)malloc(sizeof(LinkList);,if(node=NULL),/*申请结点不成功*/,return FALSE;,node-next=temp-next;,temp-next=node;,return TRUE;,本算法时间复杂度为O(n)，其中n是链表的长度。,带头结点单循环链表的操作,删除结点(删除第i个结点):,int DelCList(LinkList*L,int i),int j;,LinkList *t1,*t2,j=1;,/*定义两个工作指针t1，t2*/,t1=L-next;,/*工作时t1在前，t2在后*/,t2=L;,if(t1=t2|i1)return FALSE;,/*空表或i不合理*/,while(jnext;t2=t2-next;,if(t1=L)return FALSE;,/*查遍没找到被删除结点*/,t2-next=t1-next;,free(t1);,/*删除t1所指结点*/,return TRUE;,带头结点的双向链表,在双向链表的结点中有两个指针域：一个指向其直接前趋，另一个指向其直接后继。如图所示。,在C语言中，双向链表的存储结构可定义如下：,typedef,struct DNode,struct DNode *prior;,/*指向前趋*/,ElemType data;,/*结点数据域*/,Struct DNode *next;,/*指向后继*/,DLinkList;,DLinkList *DL,*p;,若指针p指向双向链表中的某一结点，则有如下关系,：,p-next-prior=p,p-prior-next=p,双向链表的操作,双向链表的建立,由于双向链表具有指向前趋和指向后继的两个指针，因此，在创建空双向链表的时候，,需要对两个指针赋值为NULL,。,算法2.15,建立一个空双向链表,int InitDList(DLinkList*DL),DL=(DLinkList*)malloc(sizeof(DNode);,if(DL=NULL)return FALSE;,/*申请失败*/,DL-prior=DL-next=NULL;,return TRUE;,本算法时间复杂度为O(1),双向链表的操作,双向链表为空表的判断,双向链表是否为空表，要看两个指针域是否同时为NULL。,算法2.16,判断双向链表是否为空表,int DlEmpty(DLinkList*DL),if(DL-prior=DL-next&DL-prior=NULL),return TRUE;,else,return FALSE;,在双向链表内插入结点,分析：,在双向链表中插入新的结点，必须修改插入位置的前趋和后继。,双向链表的操作,return FALSE;,int Ins(sequenlist*L，int i，datatype item),若指针p指向双向链表中的某一结点，则有如下关系：,本算法时间复杂度为O(n)，其中n是链表的长度。,Info next,node SlinkListMAXSIZE;,int DLDelete(DLinkList*DL,int i),q-next=NULL;,for(i=1;in;i+)/*将n个结点连入单链表中*/,return FALSE;,线性表L的第i个元素的存储位置和第一个元素的存储位置的关系为：,Struct DNode *next;/*指向后继*/,free(t1);/*删除t1所指结点*/,for(i=1;ilength-1),分析：本问题用一个链表来解决。,算法2.17,在双向链表中插入数据,int DLInsert(DLinkList*DL,int i,ElemType e),int j=1;,/*在带头双向链表DL的第i个位置插入新结点e*/,DLinkList *temp，*node;,temp=DL;,while(jnext!=NULL),j+;temp=temp-next;,/*temp指向第i-1个结点，j=i*/,if(j,data=e;,/*输入新结点的数据*/,node-prior=temp;,/*修改链指针，通常要修改四个指针域，插入的结点地表尾修改三个指针域*/,node-next=temp-next;,if(temp-next!=NULL)temp-next-prior=node;,temp-next=node;,return TRUE;,在双向链表内删除结点,分析：,和插入结点相似，双向链表中删除结点，也是要注意指针的修改。,双向链表的操作,算法2.18,在带头结点的双向链表中删除数据,int DLDelete(DLinkList*DL,int i),int j=1;,/*删除双向链表中第i个结点*/,DLinkList*temp;,/*工作指针*/,temp=DL-next;,while(jnext;,if(jprior-next=temp-next;,if(temp-next!=NULL),/*被删结点不是尾*/,temp-next-prior=temp-prior;,free(temp);,return TRUE;,本算法时间复杂度为O(n),双向循环链表,将双向链表中的头结点和尾结点链接起来，就构成了双向循环链表。如图所示。,双向循环链表的操作,算法2.19,在双向循环链表中删除结点e,int DLClist(DLinkList,*DL,ElemType,e,),DLinkList*temp;,/*工作指针,指向被删结点*/,temp=DL-next;,if(temp-next=temp),/*空表*/,return FALSE;,while(temp-data!=e&temp!=DL),temp=temp-next;,/*找结点e*/,if(temp!=DL),/*找到需要删除的结点,而且要删的节点不是表头*/,temp-prior-next=temp-next;,/*删除结点*/,temp-next-prior=temp-prior;,free(temp);,/*释放空间*/,return TRUE;,else,return FALSE;,静态链表,在C语言中用标准函数,malloc,和,free,来,动态,执行内存分配,并用指针实现链表，因此称为动态链表。而有的程序设计语言不支持指针类型，所以不能使用动态链表，为此引入静态链表的概念。,用数组描述的链表称为,静态链表,（Static Linked List,）,线性表静态单链表存储结构定义如下：,#define MAXSIZE 1024,typedef int ElemType;,typedef,struct SList,ElemType data;,int next;,/*表示指针域,用来指向其下一个结点*/,/*下一个结点的下标*/,node;,node SlinkListMAXSIZE;,int av;,例,2.9,线性表（A,B,C,D,E）经过修改，在B后面插入X和删除D之后，成为线性表（A,B,X,C,E）。如图所示。,1,A,2,B,3,C,4,D,5,E,0,1,A,2,B,6,C,5,D,5,E,0,X,3,0,1,2,3,4,5,6,0,1,2,3,4,5,6,data next data next,修改前的状态 修改后的状态,线性表顺序存储与链式存储的,比较,从时间的角度考虑，按位置查找数据时，查找元素的前趋和后继等方面，顺序存储有着较大的优势。,线性表顺序存储与链式存储的,比较,在插入数据、删除数据时，链式存储就有较大的优势，这是由于在链表中只要修改指针即可做到；而在顺序表中进行插入和删除，平均要移动表中将近一半的结点。,线性表顺序存储与链式存储的,比较,从空间的角度考虑，顺序表的存储空间是静态分配的，在程序执行之前必须规定其存储规模。,而动态链表的存储空间是动态分配的，只要内存空间有空闲，就不会产生溢出。,线性表的应用,约瑟夫问题,例2.10,设有n个人坐在圆桌周围，从第s个人开始报数，数到m的人出列，然后再从下一个人开始报数，同样数到m的人出列，如此重复，直到所有人都出列为止。要求输出出列的顺序。,分析：,本问题用一个链表来解决。设圆桌周围的n个人组成一个带表头的循环链表。先找到第s个人对应的结点，由此结点开始，顺序扫描m个结点，将扫描到的第m个结点删除。重复上述过程，直到链表为空。,#include“stdio.h”,Typedef char datatype;,typede struct,node,datatype info;,struct node*next;,NODE;,定义表结点,Info next,void joseph(int n,int s,int m),/*n,是链表中结点个数,*/,int i,j;,NODE*creatlinklist(int);,/*,是建立带头结点单链表的,函数说明*/,NODE*h,*p,*q,*r;,if(ns)return;,/*,开始时表中结点数少于,s，,即找不到第s个结点,*/,h=creatlinklist(n);,/*函数调用,建立一个含有n个结点的带表头的单链表*/,q=h;,for(i=1;inext;,/*循环结束后,q指向第s结点的前趋结点*/,p=q-next;,/*p指向第s个结点*/,for(i=1;in;i+),for(j=1;jnext!=NULL)&(q-next!=NULL),/*如果当前指针p,q所指的下一个结点都不是表尾,则向下移指针p和q*/,q=q-next;p=p-next;,else,/*即指针p,q的下一结点至少有一个是空*/,if(p-next=NULL),/*p所指的下一结点是空,则其下一结点就是第一个*/,q=q-next;p=h-next;,else,/*q所指的下一结点是空,则其下一结点就是第一个*/,q=h-next;p=p-next;,printf(“%cn”,p-info);,/*,印要出列,元素,的信息,*/,r=p;,/*让指针r指向要删的结点p,准备释放*/,if(p-next=NULL),/*,如表中还有结点，且这时指针,p,的下一结*/,/*,点为空，而p,所指结点,将被释放。,这表示p所指结点为链表尾*/,p=h-next;,q-next=NULL;,else,/*p所指结点不为链表尾*/,p=p-next;,if(q-next!=NULL),/*这表示q所指结点不为链表尾*/,q-next=p;,else,/*这表示q所指结点为链表尾*/,h-next=p;,free(r);,/*,释放r,结点*/,printf(“%cn”,(h-next)-info);,/*输出最后,出列的,结点*/,NODE*creatlinklist(int n),/*建立含有n个结点并带表头的单链表的函数*/,int i;,NODE*head,*p,*q;,if(n=0),return NULL;,head=(NODE*)malloc(sizeof(head);,/*申请一个结点为表头*/,q=head;,for(i=1;inext=p;,q=p;,/*q指向表尾,准备链入下一个结点*/,p-next=NULL;,/*将最后一个结点的链域置为NULL*/,return head;,LinkList*L,*head;,线性表的这种机内表示称作线性表的顺序存储结构或顺序映象。,NODE*creatlinklist(int n),链表中每个结点表示多项式中的一项，格式如下图（a）所示。,插入数据（在第i个结点的后面插入）：,而头结点的指针域存储链表第一个结点的地址。,void InitList(sequenlist*L),typedef struct SList,temp=L-next;/*使temp指向第一个结点*/,DLinkList*temp;/*工作指针*/,int isempty(LinkList*L),线性表静态单链表存储结构定义如下：,return TRUE;,当n0 时称为空表。,带头结点空循环链表中,main(),int n,s,m;,printf(“Please input n,s and m:n”);,/*输入单链表的结点数n*/,scanf(“%d%d%d”,joseph(n,s,m);,线性表的应用,多项式加法,例2.11,设有三个变元为x，y和z的整系数多项式p和q，用循环链表表示多项式。链表中每个结点表示多项式中的一项，格式如下图（a）所示。,多项式 3x,6,-5x,5,y,2,+6y,6,z 的链表表示,线性表的应用,电文加密,例2.12,对某电文（字符串）进行加密，形成密码文（1991年高级程序员试题）。,假定原文为C1C2C3Cn，加密后产生密文为S1S2S3Sn，首先读入一个正整数key(key1)作为加密钥匙，并将密文字符位置按顺时针方向连成一个环，如图2.15所示：,