数据结构线性表学习

第二章线性表存在唯一的头元素存在唯一的尾元素除头元素外，每个元素均有一个直接前驱除尾元素外，每个元素均有一个直接后继线性结构的特点OOOOO线性头尾12345§2.1线性表的定义1.线性表的语言定义线性表是n个数据元素的有限序列。例:英文字母表(A，B，C，……，Z)线性表中的数据元素也可以由若干个数据项构成。这时，数据元素称为记录，含有大量记录的线性表又称为文件。例:学生情况登记表姓名学号性别年龄班级王晓林790631男21计90陈红790632女22计902.线性表的形式定义其中：a1是头元素，an是尾元素，ai是第i个元素，ai-1是ai的直接前驱，ai+1是ai的直接后继。线性表可以表示为n个数据元素的有限序列:(a1，…，ai-1，ai，ai+1，…，an)n为线性表的长度(可根据需要增长或缩短)，n=0时为空表i为数据元素ai在线性表中的位序3.抽象数据类型线性表List的定义InitList(&L)操作结果:构造一个空的线性表L。数据对象:D={ai|ai∈ElemSet，i=1,2,…,n,n≥0}数据关系:R1={ai-1,ai|ai-1,ai∈D，i=2,…,n}基本操作:ADTList{}ADTListDestroyList(&L)操作结果:销毁线性表L。初始条件:线性表L已存在。…例2-1：用线性表完成集合的并运算，A=A∪B若：A={1，3，8}B={2，3，6，9}则：A=A∪B{1，3，8，2，6，9}voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);}}执行过程：La_len=3Lb_len=4i=1,e=2,La中没有2，La_len=4，将2插到第4个位置即：A={1，3，8，2}----------------------------------------------i=2,e=3,La中有3，返回位序为2if条件不满足，3不插入----------------------------------------------i=3,e=6,La中没有6，La_len=5，将6插到第5个位置即：A={1，3，8，2，6}----------------------------------------------i=4,e=9,La中没有9，La_len=6，将9插到第6个位置即：A={1，3，8，2，6，9}例2-2：已知线性表LA、LB为有序表，将LA、LB归并为一个新线性表LC，且保持其有序性若：LA=(1，3，8)LB=(2，3，6，9，12，15)则：LC=(1，2，3，3，6，8，9，12，15)138LA23691215LBLC12336812159voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=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);}}算法2.2归并两个有序的线性表§2.2线性表的顺序表示和实现线性表的顺序表示:用一组地址连续的存储单元依次存储线性表的数据元素。LOC(a1)LOC(ai)a1a2aian……存储地址内存状态设每个元素需占用l个存储单元LOC(ai)表示元素ai的存储地址LOC(a1)是第一个数据元素a1的存储地址，也是整个线性表的起始地址lLOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)×l顺序存储结构的线性表称为顺序表顺序表的特点：表中相邻元素ai和ai+1赋以相邻的存储位置LOC(ai)和LOC(ai+1)即：以元素在计算机内“物理位置相邻”来表示元素间的逻辑关系只要确定了存储线性表的起始位置，线性表中任一元素都可以随机存取。线性表顺序存储结构表示#defineLIST_INIT_SIZE100//初始分配量#defineLISTINCREMENT10//分配增量typedefstruct{}SqList;Elemtype*elem;//线性表的起始地址intlength;//表长，初始为0intlistsize;//表存储容量线性表的顺序存储结构是一种随机存取的存储结构。StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}算法2.3初始化空线性表线性表的顺序存储结构的优点可随机存取表中任意数据元素(第i个)直接可获取线性表中数据元素的个数L.lengthL.elem[i-1]*(L.elem+i-1)算法2.4在第i个数据元素之前插入一个新元素算法思想:1.找到第i个元素的位置。3.将新元素b插入到第i个位置。例：在第i个元素前插入bb2.将第n个到第i个元素均向后移动一个位置。a1ai-1aian……a1ai-1aian……aiq=L.elem+i-1；//找到第i个元素位置for(p=L.elem+L.length-1；p=q；--p)*(p+1)=*p；//后移元素*q=e；//插入新元素++L.length；returnOK；intListInsert_Sq(SqList&L，inti，ElemTypee){}ElemType*p,*q;算法2.4的简化描述不用指针，可以直接用下标for(k=L.length-1;k=i-1;k--)L.elem[k+1]=L.elem[k];L.elem[i-1]=e;L.length++;例：在第4个元素之前插入元素25。(即：i=4b=25)451293369512345657693325q=L.elem+3平均时间复杂度：O(n)L.elemp=L.elem[5]*(p+1)=*pp--p*(p+1)=*pp--p*(p+1)=*pp--p*q=e=25q=L.elem+i-1;for(p=L.elem+L.length-1；p=q；--p)*(p+1)=*p;*q=e;++L.length;returnOK;intListInsert_Sq(SqList&L，inti，ElemTypee){}算法2.4的完整描述if(L.length==L.listsize)//越界处理{L.elem=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.listsize+=LISTINCREMENT;}if(i1||iL.length+1)returnERROR;//i合法性检查补充：realloc()函数函数原型：void*realloc(void*p，unsignedintsize);函数功能：将指针p所指向的存储空间的大小改为size个字节。函数返回值：如果重新分配成功，则返回新分配的存储空间的首地址(该地址与原来p所指向的地址不一定相同)，否则返回空指针NULL。MSDN中对realloc()函数的描述：reallocreturnsavoidpointertothereallocated(andpossiblymoved)memoryblock.ThereturnvalueisNULLifthesizeiszeroandthebufferargumentisnotNULL,orifthereisnotenoughavailablememorytoexpandtheblocktothegivensize.Inthefirstcase,theoriginalblockisfreed.Inthesecond,theoriginalblockisunchanged.Thereturnvaluepointstoastoragespacethatisguaranteedtobesuitablyalignedforstorageofanytypeofobject.Togetapointertoatypeotherthanvoid,useatypecastonthereturnvalue.realloc()函数使用说明：1.realloc调用成功时返回void*指针，指向新分配的内存空间。一般需要对这个指针进行强制类型转换。2.若传入的第一个指针参数为NULL，则该函数等同与malloc函数。3.当第二个参数为0，且第一个参数不为NULL时，或者没有足够的内存空间进行分配时，返回NULL。4.realloc是从堆上分配内存的，当扩大一块内存空间时，realloc函数首先试图从原来分配的内存块后面获得附加的内存空间，如果原内存块后面的内存空间不够的话，就使用堆上第一个有足够大小的内存空间，将原内存块中的数据拷贝到新分配的内存空间中，此时原内存块被free。算法2.5删除第i个数据元素算法思想:1.找到第i个数据元素。3.将第i+1个到第n个元素均向前移动一个位置。2.取出第i个数据元素。a1ai-1ai+1an……aiaia1ai-1ai+1an……intListDelete_Sq(SqList&L，inti，ElemType&e){p=&L.elem[i-1]；//找到第i个元素for(++p；p=q；++p)*(p-1)=*p；//第i+1个到第n个元素前移e=*p；//取第i个元素的值returnOK；}--L.length；//表长减1算法2.5的描述q=L.elem+L.length-1；//表尾元素的位置if(i1||iL.length)returnERROR；例:删除第4个元素25。45129253369123456753369平均时间复杂度:O(n)线性表的顺序存储结构的缺点:进行元素的插入、删除操作时，需要移动大量的元素p=L.elem[3]L.eleme=*p=25++pp*(p-1)=*p++pp*(p-1)=*p++pp*(p-1)=*p++pp5q补充：函数的指针:函数的入口地址在程序调用函数时,计算机会转去执行函数体内的语句,因此计算机必须知道函数在什么地方。实际上，函数在内存中也要占据一片存储单元,这片存储单元有一个起始地址,我们称其为函数的入口地址,即函数的指针,函数的入口地址是用函数名来表示。我们可以定义一个指针变量,让它的值等于函数的入口地址,然后通过该指针变量来调用函数,该指针变量称为指向函数的指针变量指向函数的指针变量的定义：数据类型(*指针变量名)(形参列表)；例：int(*pt)(intarr[],intn);//注意:格式中的小括号不能省略让指针变量指向函数就是直接将函数名赋给指针变量使用指针变量调用函数的格式:(*指针变量名)(实参列表)例：编写一个用矩形法求定积分的通用函数10)sin(dxx21)cos(dxx31dxex矩形法