资源描述
线性结构包括线性表、栈、队列、串、数组和广义表。其特点是：在数据元素的非空有限集合中,存在惟一的一个被称作“第一个”的数据元素；,存在惟一的一个被称作“最后一个”的数据元素；,除第一个数据元素之外，集合中的每个数据元素均只有一个前驱；,除最后一个数据元素之外，集合中的每个数据元素均只有一个后继。,1,2,2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4线性表两种存储结构比较,3,例2-126个英文字母组成的字母表：（A，B，C，Z）是一个线性表，表中数据元素是单个字母字符。,例2-2某校从1978年到1983年各种型号的计算机拥有量的变化情况可以用一个线性表表示：（6，17，28，50，92，188）表中数据元素是整数。,例2-3一个学校的学生健康情况登记表如下图所示。,表中每个学生的情况为一个记录，它的姓名、学号、性别、年龄、班级和健康情况等六个数据项组成。,4,5,线性表中的数据元素可以是各种各样的，但同一线性表中的元素必须具有相同的特性，即属同一数据对象，且相邻数据元素之间存在着序偶关系。,线性表的定义,线性表的基本操作,一个线性表（linear_list）是n（n0）个具有相同属性的数据元素的有限序列，其中各元素有着依次相邻的逻辑关系。,线性表中数据元素的个数n称为线性表的长度。当n=0时该线性表称为空表。当n0时该线性表可以记为：（a1，a2，a3，ai，an）,6,2.1.1线性表的定义,7,2.1.2线性表的基本操作,线性表的顺序存储表示,8,基本操作在顺序表上的实现,线性表顺序存储的小结,(1)定义用一组地址连续的存储单元依次存储线性表中的各个数据元素，称为线性表的顺序存储。,9,2.2.1线性表的顺序存储表示,1,2,i,n,空闲,LOC(a1),LOC(a1)+k,LOC(a1)+(i-1)k,LOC(a1)+(n-1)k,线性表的最大空间,存储地址,内存状态,数据元素在线性表中的位序,10,(2)特点只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。顺序存储结构的特点是：逻辑上相邻的数据元素在物理存储上（在存储器中）也相邻。,(3)线性表的顺序存储结构可以使用一维数组来表示线性表的顺序存储结构。线性表的顺序存储结构的语言描述如下。,12,#defineMAXSIZE100/*此处的宏定义常量表示线性表可能达到的最大长度*/typedefstructElemTypeelemMAXSIZE;/*线性表占用的数组空间*/intlast;SeqList;/*顺序表的类型名*/,2.2.1线性表的顺序存储表示,(1)算法思想,按序号查找GetData(L,i):要求查找线性表L中第i个数据元素,其结果是L.elemi-1或L-elemi-1.,按内容查找Locate(L,e):要求查找线性表L中与给定值e相等的数据元素,结果:若在表L中找到与e相等的元素,则返回该元素在表中的序号;若找不到,则返回一个”空序号”,如-1.,13,2.2.2基本操作在顺序表上的实现,1.查找操作,(2)算法编写,i=0;/*i为扫描计数器,初值为0*/,while(ilast+2)/*首先判断插入位置是否合法*/printf(“插入位置i值不合法”）；returnERROR；,17,(2)算法编写,if(L-last=MAXSIZE-1)printf(“表已满无法插入”);return(ERROR);,18,for(k=L-last;k=i-1;k-)/*为插入元素而移动位置*/L-elemk+1=L-elemk;,L-elemi-1=e;/*在C语言数组中,第i个元素的下标为i-1*/L-last+;return(OK);,(3)算法分析算法InsList的基本操作是数据元素后移操作。执行元素后移的次数是ni+1。可以看到：移动元素的次数不仅和线性表的长度n有关，而且还与插入元素的位置i有关。当i=n+1时，无须移动元素；当i=1时，则元素后移执行n次。也就是说，该算法在最好的情况下时间复杂度是O(1)，在最坏的情况下时间复杂度是O(n)。,19,设ins为在长度为n的表中插入一个元素所需移动元素的平均次数，假设i为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相同,(1)算法思想在一般情况下，删除第i个元素时，需要将n至第i+1个（共n-i）元素向前移动一个位置。,检查删除位置的合理性；,把原来第i+1个数据元素至第n个数据元素依次向前移一个数组元素位置；,修正线性表的数据元素个数。,20,3.顺序线性表的删除算法,要删除的元素,(a)删除元素前,ai+1,ai+2,已删除元素ai,(b)删除元素后,an,空闲,21,IntDelList(SeqList*L,inti,ElemType*e)/*在顺序线性表L中删除第i个元素，并用e返回其值i的合法值为1iLlast+1*/,intk;if(iL-last+1)printf(“删除位置不合法！”）；return（ERROR）;/*i值不合法*/,for(k=i;ilast;k+)L-elemk-1=L-elemk;/*被删除元素之后的元素前移*/,*e=L-elemi-1;/*被删除元素存放到e所指向的变量中*/,22,(2)算法编写,L-last-;/*表长减1*/returnOK;/*DelList*/,(3)算法分析算法DelList的基本操作是数据元素前移操作。执行元素前移的次数是n-i。可以看到：移动元素的次数不仅和线性表的长度n有关，而且还与删除元素的位置i有关。当i=n时，无须移动元素；当i=1时，则元素前移执行n-1次。也就是说，该算法在最好的情况下时间复杂度是O(1)，在最坏的情况下时间复杂度是O(n)。进一步分析算法的平均性能：算法DelList的时间复杂度为O(n)。,24,线性表顺序存储结构的最大特点就是逻辑上相邻的两个元素在物理位置上也相邻。这一特点使顺序表具有十分鲜明的优点和缺点。,25,2.2.3线性表顺序存储的小结,(2)顺序存储结构的缺点,(1)插入或删除一个数据元素时，需要对插入点或删除点后面的全部元素逐个进行移动，需要花费较多的时间。(2)在给长度变化较大的线性表预先分配空间时必须按照最大空间分配，使存储空间不能得到充分利用。(3)线性表的容量难以扩充。,1.顺序存储结构的优点,(1)便于随机存取线性表中任一个数据元素，且存取任一个数据元素所花费的时间相同。(2)存储空间连续，不必增加额外的存储空间。,27,线性表的链式存储表示,28,基本操作在单链表上的实现,循环链表,双向链表,线性表链式存储结构小结,线性表链式存储结构的特点是用一组任意的存储单元存储该线性表中的各个数据元素（存储单元可以连续，也可以不连续）。,相关的概念有：结点，线性表的单链表存储结构，头结点和头指针。,29,2.3.1线性表的链式存储表示,(1)结点一个数据元素ai的存储结构由两部分信息组成，称之为结点(node)。结点包括两个域：数据域(data)，存储数据元素信息；指针域(next)，存储直接后继元素地址（没有后继元素时指针为“空”(NULL)）。指针域中存储的信息称为指针或链。,30,数据域,指针域,(2)线性表的单链表存储结构,31,通过每个结点的指针域将线性表中n个结点按其逻辑顺序链接在一起的结点序列称为链表，即为线性表(a1,a2,a3,ai,an)的链式存储结构。如果线性链表中的每个结点只有一个指针域，则链表又称为线性链表或单链表(linkedlist)。,例：线性表如下：（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG）,线性链表在内存的存储结构,起始地址,32,31,7,13,1,43,25,37,19,33,线性表的单链表存储表示：,typedefstructNodeElemTypedata;/*数据域*/structNode*next;/*指针域*/Node,*LinkList;/*单链表的类型名*/,(3)头结点和头指针,34,在单链表的第一个结点之前附加一个同结构的结点，称之为头结点。头结点的数据域可以不存储任何信息也可以存储如线性表的长度等类的附加信息；头结点的指针域指向第一个结点（即第一个元素结点的存储位置）。头指针就是指向头结点的指针。当头结点的指针域为“空”时，单链表为空链表。,头指针,头结点,35,非空单链表,空链表,建立线性表的链式存储结构的过程是一个动态生成单链表的过程，即从“空表”的初始状态起，依次建立各元素结点，并逐个插入到单链表中。(1)算法思想,首先建立一个空表，然后重复下面操作：,生成一个新结点；,读入数据，并存入新结点的数据域；,将新结点插入到单链表的头结点之后；,修改单链表头结点的指针域。,36,2.建立单链表(头插法）,2.3.1线性表的链式存储表示,L,s,c1,s,cn,s,c2,s-next=L-next,L-next=s,s-next=L-next,L-next=s,s-next=L-next,L-next=s,37,38,p45:算法编写(线性表的长度不知道）,voidGreateFromHead(LinkListL)/*L是已经初始化好的空链表的头指针,通过键盘输入表中元素*/*值,利用头插法建单链表L*/Node*s;charc;intflag=1;,While(flag)/*flag初值为了,当输入”$”时,置flag为0,建表结束*/c=getchar();if(c!=$),s=(Node*)malloc(sizeof(Node);/*生成新结点*/,s-data=c;s-next=L-next;/*将新结点插入到单链表的头*/L-next=s;/*修改单链表头结点的指针域*/*while结束*/elseflag=0/*若输入字符为$,置flag=0*/*CreatFromTail*/,(1)算法思想在单链表中，任何两个元素存储位置间没有固定的联系，每一个元素的存储位置都包含在其直接前驱结点的next之中。,假设p是指向线性表中第i个元素的指针，则该结点称为p结点或结点ai；而p-next是指向第i+1个元素的指针。若p-data=ai，则p-next-data=ai+1。由此，在单链表中，取得第i个数据元素必须从头指针出发寻找。因此，单链表是非随机的存储结构。,40,3.单链表的查找元素算法(按序号查找),L,p-next,p,41,Node*Get(LinkListL,inti)/*L是带头结点单链表的头指针，当第i个元素存在时，则返回该结点的存储位置;否则返回NULL。1i表长。*/,intj;Node*p;if(inext!=NULL)/*顺指针向后查找，直到p指向第i个元素或p为空*/,if(i=j)returnp;/*取第i个元素,elsereturnNULL/*第i个元素不存在,/*Get*/,42,(2)算法编写,(3)算法分析算法Get的基本操作：比较j和i且后移指针。while循环体中的语句执行次数与被查数据元素在线性表中的位置有关。假设线性表长为n，如果1in，则while循环体中语句的执行次数为i，否则执行次数为n，因此算法Get的时间复杂度为O(n)。,43,IntListLength(LinkListL)/*L是带头结点单链表的头指针，求链表长度*/,Node*p;p=L-next;j=0;/*初始化，p指向头结点，j为计数器,初始时为*/,while(p!=NULL)p=p-next;j+;,returnj;/*j为求得的单链表长度*/,/*ListLength*/,44,4.求单链表长度操作,算法分析,若单链表L为空,p的初值为”NULL”,算法中while循环未执行，则返回链表长度j为0,若单链表L为非空表，算法中while循环执行次数为表长度n,故算法的时间复杂度为O(n).,(1)算法思想假设要在带头结点的单链表的两个数据元素ai-1和ai之间插入一个数据元素e。,查找第i-1个结点，检查有关参数的合理性；,查找第i-1个结点并由指针pre指示，,生成一个新结点；使新结点数据域的值为e；,将新结点插入到单链表中；,修改第i-1个结点的指针域。,46,5.单链表的插入元素算法,47,pre,s-next=pre-next,pre-next=s,e,IntInsList(LinkListL,inti,ElemTypee)/*在带头结点单链表L中第i个位置前插入e。1i表长+1。,Node*pre,*s;intk;/*k为计数器，初始为0*/if(ii-1)/*i1或表长+1*/printf(“插入位置不合理!”);returnERROR;s=(Node*)malloc(sizeof(LNode);/*生成新结点*/,48,(2)算法编写,49,s-data=e;/*将e放入新结点数据域*/s-next=pre-next;/*将新结点插入表L中*/p-next=s;/*修改第i-1个结点指针*returnOK;/*InsList*/,(3)算法分析算法InsList的基本操作是：在插入之前，需要找到第i-1个结点，从算法Get的讨论中我们可以得知，算法InsList的时间复杂度为O(n)。,(1)算法思想假设要在线性表中删除数据元素ai。,寻找第i-1个结点，并由pre指示,指示检查有关参数的合理性；,用一个指针r指向被删除结点；,删除第i个结点，即修改第i-1个结点的指针；,释放第i个结点。,50,6.单链表的删除元素算法,pre,pre-next=pre-next-next,51,r,r,IntDelList(LinkListL,inti,ElemType*e)/*在带头结点的单链表L中，删除第i个元素，并由e返回其值。*/*1i表长。*/,Node*pre,*r;intk;pre=L;k=0;*初始化，pre指向头结点,k为计数器，初始为0*/,while(pre-next!=NULL/*顺指针向后查找，直到pre指向第i1个元素或pre-next为空,if(!pre-next)printf(“删除位置不合理”);returnERROR;/*删除位置不合理*/r=pre-next;/*用r指向第i个结点*/pre-next=r-next;/*删除第i个结点r*/e=r-data;/*取出第i个结点数据*/,free(r);/*释放第i个结点*/returnOK;/*DelList*/,52,(2)算法编写,(3)算法分析算法的基本操作是：在删除之前，需要找到第i-1个结点，从算法Get的讨论中，我们可以得知，算法DelList的时间复杂度为O(n)。,53,循环链表（circularlinkedlist）是另一种形式的链式存储结构。循环链表的特点是：表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，由表中任一结点出发均可以找到表中其他的结点。在有些应用问题中，用循环链表可以使操作更加方便灵活。为了和单链表一致，在循环链表中也设置一个头结点。空循环链表仅由一个头结点组成，并自成循环。,54,2.3.3循环链表,L,非空循环链表,L,空循环链表,55,56,例2-3,LinkListmerge_1(LinkListLA,LinkListLB)/此算法将两个采用头指针的循环单链表首尾连接起来Node*p,*q;p=LA;q=LB;,While(p-next!=LA)p=p-next;,While(q-next!=LB)q=q-next;,q-next=LA;p-next=LB-next;free(LB);return(LA);/merge_1,58,在单链表或循环链表结构的结点中，只有一个指示直接后继结点的指针域，因此，从某个结点出发只能顺着指针往后寻查其他结点。如果要寻查结点的直接前驱结点，则需要从表头指针出发。换句话说，在单链表中，NextElem算法的执行时间为O(1)，而PriorElem算法的执行时间为O(n)。为了克服这种单向性的缺点，可以利用双向链表。,2.3.4双向链表,1.双向链表的存储表示,(1)结点在双向链表(doublelinkedlist)中，每个结点应该包括3个部分：数据域(data)、前向指针域(prior)和反向指针域(next)。数据域存放结点本身的数据，前向指针域指向其直接前趋结点，后向指针域指向其直接后继结点。这样，每次处理结点时都可以从当前结点出发前向或者后向查找。,59,数据域,前向指针域,后向指针域,(2)线性表的双向链表存储表示,typedefstructDNodeElemTypedata;structDNode*prior,*next;DNode,*DoubleList;/双向链表的类型名,60,(3)头结点和头指针在双向链表的第一个结点之前附加一个同结构的结点，称之为头结点。头结点的数据域可以不存储任何信息也可以存储如线性表的长度等类的附加信息；头结点的前向指针域prior存储指向最后一个结点的指针，后向指针域next存储指向第一个结点的指针。,61,头指针为指向头结点的指针。当头结点的前向指针域prior和后向指针域next均指向头结点自己的时候，称为空双向链表。,头结点,头指针,头结点的前向指针域指向链表的最后一个结点,头结点的后向指针域指向链表的第一个结点,前向指针域指向前一个结点,后向指针域指向下一个结点,最后一个结点的后向指针域指向链表的头结点,62,头结点的前向指针域指向头结点自身,头结点的后向指针域指向头结点自身,63,2.基本操作在双向链表上的实现在双向链表中，有些操作仅仅需要涉及一个方向的指针，比如：ListLength、Get和Locate等的，则它们的算法描述和单链表的操作相同，但是在插入和删除数据元素时有很大的不同，在双向链表中需要同时修改两个方向上的指针。,64,p,s-prior=p-prior,p-prior-next=s,s-next=p,p-prior=s,65,e,(1)双向链表的插入操作,intDlinkIns(DoubleListL,inti,ElemTypee)/*在带头结点的双向循环线性表L中第i个位置之前插入元素e*/*i的合法值为1i表长+1*/,DNode*s,*p;/*p为指向第i个结点的指针*/s=(DNode*)malloc(sizeof(DNode);/*生成新结点*/,if(s)/*若成功生成*/s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;returnTRUE;,elsereturnFALSE;/*若空间不足，则返回*/,/*DoubleList*/,66,67,p,p-prior-next=p-next,p-next-prior=p-prior,(2)双向链表的删除操作,intDlinkDel(DoubleListL,inti,ElemType*e)/*删除带头结点的双向循环线性表L中第i个元素并将元素值返回*/*i的合法值为1i表长*/,if(!(p=GetElemP_DuL(L,i)returnERROR;/*在L中确定第i个元素，p为指向该结点的指针；若i表长，则p=NIL，第i个元素不存在*/,*e=p-data;p-prior-next=p-next;p-next-prior=p-prior;,free(p);returnTURE;/*DlinkDel*/,68,线性表的链式存储结构的最大特点是逻辑上相邻的两个元素在物理位置上不相邻，因此存储器中的碎片可得到充分的利用。线性表的链式存储结构只能顺序存取数据元素，不能随机存取数据元素。,69,2.3.5线性表链式存储结构小结,线性表有两种存储结构：顺序存储结构和链式存储结构。在实际应用中要根据具体问题的要求来选择合适的存储结构。我们从两个方面对线性表的两种存储结构进行比较。,70,线性表的顺序存储结构是静态分配的，在程序运行之前必须明确规定它的存储规模；线性表的链式存储结构是动态分配的，在程序运行之中，只要内存空间有空闲，就可以成功分配。在链表中的每个结点，除了数据域外，还要有存放结点地址的指针域。因此，在线性表的长度变化较大，预先难以确定的情况下，最好采用动态链表作为存储结构；当线性表的长度变化不大时，最好采用顺序表作为存储结构，这样比较节省存储空间。,71,1.空间性能的比较,线性表的顺序存储结构是随机存储结构，表中任一数据元素都可通过计算直接得到地址进行存取，时间复杂度为O(1)；线性表链式存储结构是非随机存储结构，表中的数据元素需要从头指针起顺着链表扫描才能取得，时间复杂度为O(n)（n为线性表的表长）。在顺序表中进行插入和删除数据元素时，平均要移动近一半的元素；在链式表中进行插入和删除数据元素时，只需修改指针。因此，若线性表的操作主要是查找和读取时，采用顺序存储结构为宜；若线性表的操作主要是插入和删除时，采用链式存储结构为宜。,72,2.时间性能的比较,
展开阅读全文