搜索
数据结构与算法《数据结构（C语言版）》第2章线性表安财.管理科学与工程学.计算机.王准生邮箱：bbwhs@163.com2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示的实现第2章线性表线性结构的特点：•在数据元素的非空有限集中，–存在唯一的一个被称作“第一个”的数据元素–存在唯一的一个被称作“最后一个”的数据元素–除第一个之外，集合中的每个数据元素均只有一个前驱–除最后一个之外，集合中的每个数据元素均只有一个后继2.1线性表的类型定义•什么是线性表–一个线性表是n个数据元素的有限序列。在稍复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下常把数据元素称为记录（Record）,含有大量记录的线性表又称文件（File）。–若将线性表记为（a1，．．．，ai-1，ai，ai+1，．．．，an）,–则表中ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。–n是线性表的长度，n≥0，n=0时称为空表。a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i是数据元素ai在线性表中的位序。•抽象数据类型线性表的定义应用举例•例2－1假设利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A＝A∪B。（集合中的成员即线性表中的元素）voidunion(List&La,ListLb){//将所有在线性表Lb中但不在La中的数据元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);//分别求两个线性表的长度for(i=1;i=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);//假如La中不存在和e相同的数据元素，则将e插入到La中}}//union例2－2已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，LC中的数据元素仍按值非递减有序排列。voidMergeList(ListLa,ListLb,List&Lc){//已知线性表La和Lb中的数据元素按值非递减有序排列//归并La和Lb得到新的线性表LC，LC中的数据元素仍按值非递减排列。InitList(Lc);//初始化一个线性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i=La_len)&&(j=Lb_len))//当La和Lb均为非空时{GetElem(La,i,ai);GetElem(Lb,,j,bj);if(ai=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i=La_len){//当La仍为非空时GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j=Lb_len){//当Lb仍为非空时GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//MergeList2.2线性表的顺序表示和实现•线性表的顺序表示–指的是用一组地址连续的存储单元依次存储线性表的数据元素。•线性表的顺序存储结构／顺序映象–假设线性表的每个元素需占用l个存储单元，则线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l,式中LOC(a1)是线性表中的第一个数据元素a1的在存储位置，通常称做线性表的起始位置，或基地址。–线性表的这种机内表示称作线性表的顺序存储结构或顺序映象，反之，称这种存储结构的线性表为顺序表。特点•以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。只要确定了存储线性表的起始位置，线性表中任一个数据元素都可随机存取，所以，线性表的顺序存储结构是一种随机存取的存储结构。线性表的顺序存储结构的实现•C语言的描述•由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组描述。//――――线性表的动态顺序存储结构――――#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{Elemtype*elem;//存储空间基址，即线性表的基址intlength;//线性表的当前长度intlistsize;//顺序表当前分配的存储容量（以sizeof(ElemType)为单位）//插入空间不足时可再分配能存储LISTINCREMENT个数据元素的空间}SqList;初始化顺序表L的算法2.3StatusInitList_Sq(SqList&L){//构造一个空的线性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));If(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//空表长度应为0L.listsize=LIST_INIT_SIZE://初始的存储容量returnOK;}//InitList_Sq•注意：C语言中数组的下标从0开始，因此，若L是SqList类型的顺序表，则表中第i个数据元素是L.elem[i-1]。算法2.4：在第i个元素之前插入一个数据元素e。StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表L中第i个位置之前插入新的元素e。//i的合法值为1≤i≤ListLength_Sq(L)+1if(i1||iL.length+1)returnERROR;//i值不合法if(L.length=L.listsize){//当前存储空间已满，应增加分配newbase＝（ElemType*）realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加了存储容量}q=&(L.elem[i–1]);//q为插入位置，C语言数组从0开始下标for(p=&(L.elem[L.length–1];p=q;--p)*(p+1)=*p;//从最后一个元素开始直到第i个元素为止，所有元素依次后移*q=e;//插入元素e到第个i位置++L.length;//表长增1returnOK;}//ListInsert_sq算法2.5删除第i个元素StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序线性表L中删除第i个元素,并用e返回其值//i的合法值为1≤i≤ListLength_Sq(L)if((i1)||(iL.length))returnERROR;//i值不合法p=&(L.elem[i–1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length–1;//表尾元素的位置for(++p;p=q;++p)*(p–1)=*P;//从被删元素之后的下一个位置，元素依次左移，覆盖前一个――L.length;//表长减一returnOK;}//ListDelete_Sq对以上两个算法的时间复杂度的分析•以上两个算法的时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。•算法2.4假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的期望值（平均次数）为•11)1(niinpiisE•假定概率相等，即pi=1/(n+1)，则上式可简化为•若表长为n,则时间复杂度为O（n）•112)1(11niisninnE算法2.5分析•假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均次数）为niinqidlE1)(•假定概率相等，即qi=1/n，则上式可简化为•若表长为n,则时间复杂度为O（n）nidlninnE121)(1定位算法，即求线性表中元素e的位置2.6intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在顺序线性表L中查找第1个值与e满足compare()(即相等)的元素的位序//若找到,则返回其在L中的位序,否则返回0i=1;//i的初值为第1个元素的位序p=L.elem;//p的初值为第1个元素的存储位置while(i=L.length&&!(*compare)(*P++,e))++i;if(i=L.length)returni;elsereturn0;}//LocateElem_Sq两个非递减有序的线性表的合并算法2.7voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){//已知顺序表La和Lb的元素按值非递减排列//归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列Pa=La.elem;Pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);//存储分配失败pa_last=La..elem+La.length–1;pb_last=Lb..elem+Lb.length–1;while(pa=pa_last&&pb=pb_last){//归并if(*pa=*pb)*pc++=*pa++;else*pc++=*pb++;}//插入La的剩余元素while(pa=pa_last)*pc++=*pa++;//插入Lb的剩余元素while(pb=pb_last)*pc++=*pb++;}//MergeList_Sq2.3线性表的链式表示的实现•线性链表–①链式存储结构的特点是用任意的一组存储单元（不连续）存储线性表的数据元素。–②对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素ai的存储映象，称为结点。即结点包括两个域：数据域和指针域。指针域中存储的信息称作指针或链。–③N个结点的结成一个链表。即为线性表（a1,a2,．．．,an）的链式存储结构。逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，因此，这种存储结构为非顺序映象或链式映象。–由于每个结点只包含一个指针域，故又称线性链表或单链表。–④头指针指示链表中的第一个结点的存储位置。–⑤头结点：在单链表的第一个结点之前附设的一个结点，其数据域可以不存储任何信息，也可以存储诸如线性表的长度等之类的附加信息，其指针域存储指向第一个结点的指针。定义描述•//单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述•//线性表的单链表存储结构•typedefstructLnode{•ElemTypedata;•StructLnode*next;•}LNode,*LinkList;函数GetElem在单链表中的实现，算法2.8StatusGetElem_L(LinkListL,inti,ElemType&e){//L为带头结点的单链表的头指针,当第i个元素存在//时，其值赋给e并返回OK，否则返回ERRORp=L－＞next;j=1;//初始化，p指向第一个结点，j为计数器while(p&&ji){p=p－＞next;+