数据结构第二章线性表

数学与软件科学学院信息与计算科学专业2006-2007年第1学期《数据结构》教案-详案-2004级6班作者：冯山第二章线性表2-1概述及定义线性表：n个数据元素的有限序列，记为),...,,...,,...,,(1121niiiaaaaaa。术语：1a----唯一的头元素(FirstElement)；na----唯一的尾元素(LastElement)；ia的后继----1ia；ia的前驱----1ia；ia----有限序列中的一个元素。特点：(1)非空有限元素的有序集合；(2)元素的类型可以根据具体问题而定；(3)所有的元素应具有相同的属性；(4)元素之间有顺序关系或序偶关系；(5)线性表有且只有唯一的一个头节点和尾节点，除头元素只有一个后继，尾元素只有一个前驱外，每一个元素有且仅有唯一的一个前驱和后继；(6)线性表中元素的个数(n=0)即线性表的长度。长度为0的线性表被称之为空表(Null/Empty)。非空表中，每一个元素在序列中都有一个确定的位置。2-2线性表的类型定义线性表的类型由元素的类型来定义，而元素的类型可以多种。简单线性表：元素是简单的数、字符等。例如：(1,3,4,8,9,4)----简单的数字序列(A,B,C,D,E,F)----英文字母序列(‘2’,‘A’,‘B’,‘9’,‘e’,‘x’)----字符序列(6,17,28,89,92,77)----某校从1978年到1983年的计算机数复杂线性表：数据元素由若干数据项(DataItem)构成。此时，元素可以称为记录(Record)。含有大量记录的线性表又可以构成文件(File)。例如：(教材P18图2.1)注：复杂线性表往往由记录元素构成，一般由struct表示。2-3线性表的ADT描述ADTList{数据对象：D={ia|0,,...,2,1,nniElemSetai}数据关系：R1={niDaaaaiiii,...,2,,|,11}数学与软件科学学院信息与计算科学专业2006-2007年第1学期《数据结构》教案-详案-2004级6班作者：冯山基本操作：InitList(&L)//操作结果：构造一个空线性表LDestroy(&L)//初始条件：L存在。操作结果：销毁线性表LListEmpty(L)//初始条件：L存在。操作结果：L空返回TRUE,否则FALSEClearList(&L)//初始条件：L存在。操作结果：将L置为空表。ListLength(L)//初始条件：L存在。操作结果：获得L的长度。GetElem(L,i,&e)//初始条件：L存在，且i在表长范围内。操作结果：返回L的第i个元素到e。LocateElem(L,e,compare())//初始条件：L存在，compare()是有关元素的判定函数。//操作结果：返回L中第一个与e满足关系compare()的数据元素的位序。如不存在这样的元素，则返回结果为0。PriorElem(L,cur_e,&pre_e)//初始条件：L存在。//操作结果：若cur_e是L的元素，且不是第一个，则用pre_e返回其前驱，否则，操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)//与PriorElem(L,cur_e,&pre_e)相似ListInsert(&L,i,e)//初始条件：L存在，且1=i=ListLength(L)+1//操作结果：在L中第i个位置之前插入新数据元素e，L的长度加1ListDelete(&L,i,e)//与ListInsert(&L,i,e)相似ListTraverse(L,visit())//用visit()对L中元素一一处理，visit()失败，则操作失败}注：以上均为线性表的常规操作。其C语言的实现相对简单。线性表的复杂操作：(1)表的合并；(2)表的拆分；(3)表的复制(1)表的合并问题描述：BAA基本思想：依次将B中的元素合并到A中(如A中有，则不插入，否则插入A中)算法描述：voidunion(List&La,ListLb){//将所有在Lb不在La中的元素插入La中La_len=ListLength(La);//O(1)Lb_len=ListLength(Lb);//获取线性表的长度O(1)For(i=1;i=Lb_len;i++)//O(Lb.length*?){GetElem(Lb,i,e);//取Lb中第i个数据元素的值O(1)if(!LocateElem(La,e,equal))//如果在La中找不到与e相等的元素O(La.length)ListInsert(La,++La_len,e);//则在La中第La+1位置处插入eO(1)(表尾插入)}}//union时间复杂度分析：取决于其抽象数据类型List定义中的基本操作之时间。假设GetElem()和ListInsert()的时间与表长无关，LocateElem()与表长成正比，则本算法的时间复杂度为O(ListLength(LA)*ListLength(LB))。数学与软件科学学院信息与计算科学专业2006-2007年第1学期《数据结构》教案-详案-2004级6班作者：冯山例2-2已知线性表LA和LB中数据元素按值非递减有序排列。现要求将LA和LB归并到LC中，且LC中的数据元素也要按非递减有序排列。例如：LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)LC=(2,3,5,6,8,8,9,11,11,15,20)算法设计分析：第一种：LC=LA，然后将LB中的元素一一插入LC。算法描述：(略)。第二种：分别设两指针或指示变量cur_la和cur_lb，指向LA和LB的当前元素位置，cur_lc表示LC中的当前插入位置。则分别扫描LA和LB，将其当前之小者插入LC即可。算法描述：voidMergeList(ListLa,ListLb,List&Lc){//InitList(Lc);//O(1)cur_la=cur_lb=1;cur_lc=0;//指示当前位置的三个指针之初值//O(1)La_len=ListLength(La);//O(1)Lb_len=ListLength(Lb);//获取LA和LB的表长度//O(1)while((cur_la=La_len)&&(cur_lb=Lb_len))//两表都没有被处理完时O(com){GetElem(La,cur_la,a_cur);//O(1)GetElem(Lb,cur_lb,b_cur);//分别取出两个元素a_cur和b_cur//O(1)//a_cur=b_cur则将a_cur插入LC，然后cur_la指向表LA之下一元素位置//否则，将b_cur插入LC，cur_lb指向表LB之下一元素位置if(a_cur=b_cur){ListInsert(Lc,++cur_lc,a_cur);cur_la++;}//O(1)else{ListInsert(Lc,++cur_lc,b_cur);cur_lb++;}//O(1)}while(cur_la=La_len)//如果LA还没有结束，则将其元素一一取出，插入LC{//com=Lb.length+xx;cur_lb==Lb.length;xx=cur_la;GetElem(La,cur_la++,a_cur);ListInsert(Lc,++cur_lc,a_cur);//O(La_len-xx)}while(cur_lb=Lb_len)//如果LB还没有结束，则将其元素一一取出，插入LC{//com=La.length+xx;cur_la==La.length;xx=cur_lbGetElem(Lb,cur_lb++,b_cur);ListInsert(Lc,++cur_lc,b_cur);//O(Lb_len-xx)}}//MergeList时间复杂度分析：在前面的假设前提下，本算法的时间复杂度为O(ListLength(LA)+ListLength(LB))。(2)表的拆分(课外思考)(3)表的复制(课外思考)数学与软件科学学院信息与计算科学专业2006-2007年第1学期《数据结构》教案-详案-2004级6班作者：冯山2-4线性表的顺序表示和实现基本思想：用一组地址连续的存储单元依次存储线性表中的数据元素。如图2-2所示。假定每一元素需要的存储单元字节数为L。其线性表表示成：),...,,,...,,(121niiaaaaa。其第i个元素的地址为：LiaLOCaLOCi)1()()(1注：线性表的这种机内表示被称为线性表的顺序存储结构或顺序映像(SequentialMapping)。线性表的顺序存储之特点：(1)相邻元素在机内的存放位置也是相邻的。即：物理位置与逻辑位置一致。(2)随机存取的特点。实现方法：静态数组或动态分配的一维数组。静态数组的方法----即C语言中本身提供的数组结构。动态数组的方法----需要用动态分配功能和结构描述功能共同完成。动态分配的一维数组的定义与初始化实现：#defineLIST_INIT_SIZE100//线性表分配大小值的基本分配单位#defineLISTINCREMENT10//线性表的增长步长(每次加10个元素空间)typedefstruct{ElemType*elem;//线性表存储空间的基址intlength;//线性表的实际长度(已存放元素的个数)intlistsize;//当前线性表的总体大小(注：以sizeof(ElemType)为单位)}SqList;StatusInitListSq(SqList&L)//构造一个空的线性表L{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储空间分配失败，退出程序L.length=0;//表的实际长度L.listsize=LIST_INIT_SIZE;//线性表的大小returnOK;}//InitList_Sq线性表的基本操作：插入、删除、查询、合并、复制、运算等(应保证逻辑相邻的物理上也相邻)。线性表的插入操作：初始条件：带入线性表L，插入位置i，元素e1)L是否已超长，如是则重新动态分配L，并修正相应参数b1b+L2b+(n-1)*Lnb+n*Ln+1b+(maxlen-1)*Lmaxlen图2-2线性表的顺序存储空间结构示意图a1a2…an地址内存状态元素位序空前空间数学与软件科学学院信息与计算科学专业2006-2007年第1学期《数据结构》教案-详案-2004级6班作者：冯山2)q=&(L.elem[i-1]);//获取插入位置3)for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;//将包含在内的q以后的元素后移一个元素位置4)*q=e;5)++L.length算法复杂度分析：移动元素的耗时多。因此，移动元素的操作可以作为此算法的基本操作来表示算法的时间复杂度。(具体分析过程见P25)结论：O(n)。线性表的删除操作：初始条件：带入线性表L，删除位置i，元素e1)删除位置i是否合法；不合法则退出程序2)保存被删除的元素到e3)将被删除元素之后的元素前移一个位置4)修改线性表的长度参数算法复杂度分析：与插入算法相似。(具体分析过程见P25)结论：O(n)。线性表的查询操作：初始条件：带入线性表L，元素e，compare函数指针1)初始化查询条件2)依次对每一元素，用compare指针所指函数进行比较3)如果找到的元素之位序超过线性表的大小，则返回失败标志，否则返回该元素在线性表中的位序值算法复杂度分析：与插入算法相似，但基本操作是比较。结论：O(n)。线性表的合并操作：初始条件：带入线性表La，Lb，返回Lc(算法见P26)注1：线性表的合并操作与集合的并操作之间的算法差异与联系。注2：建立在有序线性表上的线性表