数据结构线性表

.,本章学习要点1.了解线性表逻辑结构的特征;2.重点掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关系；如何用C语言描述它们的类型定义；3.掌握在顺序存储结构下，线性表的基本操作的算法；4.掌握在链式存储结构下，线性表的基本操作算法；5.能够从时间复杂度的角度，比较线性表两类存储结构不同特点及适用场合；,第2章线性表,.,线性结构的基本特征为:,线性结构是一个数据元素的有序（次序）集合。1集合中必存在唯一的一个“第一元素”；2集合中必存在唯一的一个“最后元素”；3除最后元素在外，均有唯一的后继；4除第一元素之外，均有唯一的前驱。,.,2.1线性表的类型定义,2.3线性表类型的实现链式映象,2.4一元多项式的表示,2.2线性表类型的实现顺序映象,.,2.1线性表的类型定义,线性表是n个类型相同数据元素的有限序列，通常记作（a1,a2,a3,an）。,例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。例3、某单位的电话号码簿。,一、线性表的逻辑结构,电话号码簿是数据元素的有限序列，每一数据元素包括两个数据项，一个是用户姓名，一个是对应的电话号码。,.,说明：设A=（a1,a2,.,ai-1,ai,ai+1,an）是一线性表，则1、线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2、在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前趋，ai+1是ai的直接后继；3、在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。4、线性表中元素的个数n称为线性表的长度，n=0时称为空表；5、ai是线性表的第i个元素，称i为数据元素ai的位序。,.,二、线性表的抽象数据类型定义：,ADTList,数据对象：,Dai|aiElemSet,i=1,2,.,n,n0,数据关系：,R1|ai-1,aiD,i=2,.,n,基本操作：,结构初始化操作结构销毁操作引用型操作加工型操作,ADTList,.,InitList(/取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和e相同的数据元素，则插入之,voidunion(List,for(i=1;i=Lb_len;i+),/union,.,例2-2已知线性表LA和LB中的元素按值非递减有序，现要求将它们归并成一个新的线性表LC，且LC的元素也按值非递减有序。解题思路：建立空线性表LC，将LA、LB表中的元素逐个插入到LC中，插入规则为：在LA、LB中分别设立指针i、j，比较i,j位置上的元素（设它们分别为a,b)。则C继续往下比较以下是算法。,.,voidMergeList(ListLa,ListLb,List/构造空的线性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);,代码见下页（1）,代码见下页（2）,代码见下页（3）,.,/La和Lb均非空，i=j=1,k=0GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)/将ai插入到Lc中ListInsert(Lc,+k,ai);+i;else/将bj插入到Lc中ListInsert(Lc,+k,bj);+j;,while(i=La_len)/当La不空时GetElem(La,i+,ai);ListInsert(Lc,+k,ai);/插入La表中剩余元素,while(j=Lb_len)/当Lb不空时GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/插入Lb表中剩余元素,代码（1）,代码（2）,代码（3）,.,例一和例二的算法时间复杂度分析：上述算法中基本操作GetElem和ListInstert的执行时间，它们与表长无关，LocateElem与表长成正比。所以例一的时间复杂度为：O(ListLength(LA)ListLength(LB)例二的时间复杂度为：O(ListLength(LA)+ListLength(LB),.,2.2线性表的实现顺序映象,用一组地址连续的存储单元依次存放线性表中的数据元素,a1a2ai-1aian,线性表的起始地址称作线性表的基地址,.,以“存储位置相邻”表示有序对即：LOC(ai)=LOC(ai-1)+C一个数据元素所占存储量,所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai)=LOC(a1)+(i-1)C基地址,.,顺序映像的C语言描述,typedefstructSqList;/俗称顺序表,#defineLIST_INIT_SIZE80/线性表存储空间的初始分配量#defineLISTINCREMENT10/线性表存储空间的分配增量,ElemType*elem;/存储空间基址,intlength;/当前长度,intlistsize;/当前分配的存储容量(以sizeof(ElemType)为单位),.,线性表的基本操作在顺序表中的实现,InitList(if(!L.elem)exit(OVERFLOW);,L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;,.,顺序表中查找数据元素,e=,38,i,1,2,3,4,1,8,50,可见，基本操作是：将顺序表中的元素逐个和给定值e相比较。,.,intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)/在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回0/LocateElem_Sq,O(ListLength(L),算法的时间复杂度为：,i=1;/i的初值为第1元素的位序p=L.elem;/p的初值为第1元素的存储位置,while(ii)/第i个元素不存在returnERROR;e=p-data;/取得第i个元素returnOK;,.,2.单链表中ListInsert(/生成新结点s-data=e;s-next=p-next;p-next=s;/插入returnOK;,p=L;j=0;while(p/i大于表长或者小于1,.,3.单链表中ListDelete(p-next=q-next;e=q-data;free(q);,p,q,.,StatusListDelete_L(LinkListL,inti,ElemTypej=0;while(p-next/删除位置不合理,q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);returnOK;,.,4.单链表中ClearList(,算法时间复杂度：,O(ListLength(L),.,链表是一个动态的结构，从线性表得到单链表它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。例如：逆位序输入n个数据元素的值，建立带头结点的单链表。,一、建立一个“空表”；,二、输入数据元素an，建立结点并插入；,三、输入数据元素an-1，建立结点并插入；,四、依次类推，直至输入a1为止。,an,an,an-1,.,voidCreateList_L(LinkListL-next=NULL;/先建立一个带头结点的单链表,for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(/插入,.,线性链表归并操作算法（直接对原链表进行操作）算法2.12voidMergeList_L(LinkList/释放Lb的头结点/MergeList_L,.,四静态链表,1.静态链表的概念用一维数组来实现线性链表，用一维数组表示的线性链表，称为静态链表。2.静态链表的类型定义,SLinkList：数组的类型名；SLinkList类型的数组变量是结构数组，每一数组分量包括两个域：data用于存储线性表元素；cur用于存储直接后继元素在数组中的位置（下标）。,#defineMAXSIZE1000/链表的最大长度typedefstructElemTypedata;intcur;component,SLinkListMAXSIZE;,.,静态链表图示,数组下标,地址,.,插入前,3.静态链表插入操作图示,插入后,.,删除前,删除sun,删除后,4.静态链表删除插入操作图示,.,5.静态链表的空间管理,初始化：,voidInitSpace_SL(Slinklist/InitSpace_SL,intMalloc_SL(Slinklist/返回值i为0表示分配不成功/Malloc_SL,voidFree_SL(Slinklist/Malloc_SL,分配：,回收：,.,1.循环链表的概念循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点2.循环链表图示,五循环链表,(a)非空表（b）空表,.,注意：在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；对循环链表，有时不给出头指针，而是给出尾指针，设立尾指针可以很方便的找到线性表的第一个元素和最后一个元素结点，可使某些操作易于实现；例如将两个链表首尾相连的操作；循环链表与线性链表操作的主要差别是算法中循环结束的条件；,给出尾指针的循环链表,是什么呢？,.,1.双向链表的概念双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。,六双向链表,(a)结点图示,存储数据元素,存储后继结点的地址,存储前趋结点的地址,.,2.双向链表图示,（c）非空的双向循环链表,(b)空的双向循环链表,.,3.双向链表的基本操作算法,在双向链表中插入一个结点时指针的变化情况,在双向链表中删除结点时指针变化情况,.,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,s,插入若P定位在i的前驱上,.,插入操作算法（算法2.18）StatusListInsert_DuL(DuLinkList/LinstInsert_DuL,.,删除若P定位在i的前驱上,p-next=p-next-next;p-next-prior=p;,p,.,删除操作算法（算法2.19）StatusListDelete_DuL(DuLinkList/LinstDelete_DuL,.,七一个带头结点的线性链表类型,typedefstructLNode/结点类型ElemTypedata;structLNode*next;*Link,*Position;,StatusMakeNode(Link/分配由p指向的值为e的结点，并返回OK，/若分配失败，则返回ERROR,voidFreeNode(Link/释放p所指结点,.,typedefstruct/链表类型Linkhead,tail;/分别指向头结点和/最后一个结点的指针intlen;/指示链表长度Linkcurrent;/指向当前被访问的结点/的指针，初始位置指向头结点LinkList;,.,链表的基本操作:,结构初始化和销毁结构,StatusInitList(LinkList/构造一个空的线性链表L，其头指针、/尾指针和当前指针均指向头结点，/表长为零。,StatusDestroyList(LinkList/销毁线性链表L，L不再存在。,O(1),O(n),.,引用型操作,StatusListEmpty(LinkListL);/判表空,intListLength(LinkListL);/求表长,StatusPrior(LinkListL);/改变当前指针指向其前驱,StatusNext(LinkListL);/改变当前指针指向其后继,ElemTypeGetCurElem(LinkListL);/返回当前指针所指数据元素,O(1),O(1),O(n),O(1),O(1),.,StatusLocatePos(LinkListL,inti);/改变当前指针指向第i个结点,StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType);/若存在与e满足函数compare()判定关系的元素，/则移动当前指针指向第1个满足条件的元素的/前驱，并返回OK;否则返回ERROR,StatusListTraverse(LinkListL,Status(*visit)();/依次对L的每个元素调用函数visit(),O(n),O(n),O(n),.,加工型操作,StatusClearList(LinkList/重置L为空表,StatusSetCurElem(LinkList/更新当前指针所指数据元素,StatusAppend(LinkList/在表尾结点之后链接一串结点,StatusInsAfter(LinkList/将元素e插入在当前指针之后,StatusDelAfter(LinkList/删除当前指针之后的结点,O(1),O(n),O(s),O(1),O(1),.,StatusInsAfter(LinkList/否则返回ERROR。/InsAfter,if(!L.current)returnERROR;if(!MakeNode(s,e)returnERROR;s-next=L.current-next;L.current-next=s;if(L.tail=L.current)L.tail=s;L.current=s;returnOK;,.,StatusDelAfter(LinkList否则返回ERROR。/DelAfter,if(!(L.current,.,例一StatusListInsert_L(LinkListL,inti,ElemTypee)/在带头结点的单链线性表L的第i个元素之前插入元素e/ListInsert_L,利用上述定义的线性链表如何完成线性表的其它操作,if(!LocatePos(L,i-1)returnERROR;/i值不合法，第i-1个结点不存在if(InsAfter(L,e)returnOK;/完成插入elsereturnERROR;,.,StatusMergeList_L(LinkList/存储空间分配失败,while(!(a=MAXCLocatePos(Lb,0);/当前指针指向头结点,if(DelAfter(La,e)a=e;/取得La表中第一个元素aelsea=MAXC;/MAXC为常量最大值if(DelAfter(Lb,e)b=e;/取得Lb表中第一个元素belseb=MAXC;/a和b为两表中当前比较元素,DestroyList(La);DestroyList(Lb);/销毁链表La和LbreturnOK;,.,if(*compare)(a,b)=0)/abInsAfter(Lc,a);if(DelAfter(La,e1)a=e1;elsea=MAXC;,else/abInsAfter(Lc,b);if(DelAfter(Lb,e1)b=e1;elseb=MAXC;,.,2.4一元多项式的表示,在计算机中，可以用一个线性表来表示:P=(p0,p1,，pn),但是对于形如S(x)=1+3x100002x20000的多项式，上述表示方法是否合适？,.,一般情况下的一元稀疏多项式可写成Pn(x)=p1xe1+p2xe2+pmxem其中：pi是指数为ei的项的非零系数，0e1e2em=n,可以下列线性表表示：（p1,e1）,(p2,e2),(pm,em)）,例如:P999(x)=7x3-2x12-8x999可用线性表(7,3),(-2,12),(-8,999)表示,.,ADTPolynomial数据对象：数据关系：,抽象数据类型一元多项式的定义如下：,Dai|aiTermSet,i=1,2,.,m,m0TermSet中的每个元