数据结构与算法 线性表

1第2章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4线性表的应用示例2•线性结构是最简单且最常用的一种数据结构。包括线性表、栈、队列、串。•线性结构具有下列特点：•存在一个唯一的没有前驱的（头）数据元素。•存在一个唯一的没有后继的（尾）数据元素。•此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。线性结构32.1线性表的类型定义•线性表由一组具有相同属性的数据元素构成。•数据元素在不同的具体情况下，可以有不同的含义。•在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record）。4职工号姓名基本工资岗位工资奖金应发工资扣款实发工资1201张强54030020010402010201301周敏500200200900208801202徐黎芬55030020010503010201105黄承振53025020098020960┇┇┇┇┇┇┇┇例如，职工工资表每一个职工的工资是一个记录（数据元素）。每个记录包含八个数据项。5如果n0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素。如果n=0，则为一个空表，表示无数据元素。一个线性表是n（n≥0）个数据元素a0，a1，a2，…，an-1的有限序列。综上所述：6LinearList=(D,R)其中，D={ai|ai∈ElemSet,i=0,1,2,…，n-1n≥1}R={ai-1，ai|ai-1，ai∈D,i=1,2,…，n-1}Elemset为某一数据对象集；n为线性表的长度。抽象数据类型线性表的定义如下：7ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…，nn≥0}数据关系：R={ai-1，ai|ai-1，ai∈D,i=2,…，n}基本操作：InitList(&L)DestroyList(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,i,&e)抽象数据类型线性表的定义如下：LocateElem(L,e,compare())PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListTraverse(L,visit())}ADTList82.2线性表的顺序表示和实现一、线性表的顺序存储结构二、线性表在顺序存储结构下的运算9一、线性表的顺序存储结构在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大小相同线性表的顺序存储结构:在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素。假设线性表中的第一个数据元素的存储地址为Loc(a0)，每一个数据元素占d字节，则,线性表中第i个元素ai在计算机存储空间中的存储地址为：Loc(ai)=Loc(a0)+i*d10这是因为数组具有如下特点：（1）数据中的元素间的地址是连续的；（2）数组中所有元素的数据类型是相同的。这与线性表的顺序存储空间结构是类似的。在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。11二、线性表在顺序存储结构下的运算•定义ElemType为int类型typedefintElemType;•顺序表存储空间的总分配量#defineMAXSIZE100#defineTRUE1#defineFALSE0•顺序存储类型typedefstruct{ElemTypedata[MAXSIZE];/*存放线性表的数组*/intlength;/*length是顺序表的长度*/}SeqList;121.求顺序表长度•intListLength(SeqListL){return(L.length);}132.检查顺序表是否为空intListEmpty(SeqListL){if(L.length)return(FALSE);elsereturn(TRUE);}143.遍历顺序表•voidListTraverse(SeqListL){inti;if(L.length=0)printf(顺序表为空\n);else{printf(当前顺序表中的元素为:\n);for(i=0;i=L.length-1;i++)printf(%d,L.data[i]);printf(\n);}0，1，2，…，i-1,i,i+1,…,length-1lengthMAXSIZE154.从顺序表中查找元素ElemTypeGetElem(SeqListL,inti){ElemTypee;e=L.data[i-1];//第i个元素return(e);}0，1，2，…，i-1,i,i+1,…,length-1lengthMAXSIZE165.查找定位•/*从顺序表中查找与给定元素值相同的元素在顺序表中的位置*/intLocateElem(SeqListL,ElemTypee){inti=0;while(iL.length&&L.data[i]!=e)i++;if(iL.length)return(i-1);elsereturn-1;}176.求顺序表中元素的前驱ElemTypePriorElem(SeqListL,ElemTypee){inti=0;while(iL.length&&L.data[i]!=e)i++;if(i==0){printf(第一个元素没有前驱\n);return0;}elseif(i=L.length-1)return(L.data[i-1]);else{printf(不存在值为%d的元素\n,e);return0;}}187.求顺序表中元素的后继ElemTypeNextElem(SeqListL,ElemTypee){inti=0;while(iL.length&&L.data[i]!=e)i++;if(i==L.length-1){printf(最后一个元素没有后继\n);return0;}elseif(iL.length-1)return(L.data[i+1]);else{printf(不存在值为%d的元素\n,e);return0;}}198.向顺序表中前插元素SeqListListInsert(SeqListL,inti,ElemTypee){intj;if(L.length==MAXSIZE)printf(表满,不能插入\n);elseif(i1||iL.length)/*i=L.length时插在最后*/printf(插入位置不正确\n);else{for(j=L.length-1;j=i-1;j--)L.data[j+1]=L.data[j];L.data[i-1]=e;L.length++;}returnL;}在第i个元素之前插入一个元素时，需将第n至第i(共n-i+1)个元素向后移动一个位置209.从顺序表中删除元素SeqListListDelete(SeqListL,inti,ElemType&e){intj;if(i1||iL.length-1)printf(删除位置不正确\n);else{e=L.data[i-1];for(j=i;j=L.length-1;j++)L.data[j-1]=L.data[j];L.length--;printf(%d已被删除\n,x);}returnL;}删除第i个元素时需将从第i+1至第n(共n-i)个元素向前移动一个位置21算法演示一、插入元素算法演示二、删除元素算法演示三、线性表合并算法演示演示程序DSDemoW\DSDemoW.exe(选择C语言)22假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的平均次数为：从上述两个算法来看，在线性表的顺序存储结构中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。移动元素的操作为预估算法时间复杂度的基本操作。移动元素的次数取决于插入或删除元素的位置。)1(11inpEniiins算法的时间复杂度假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的平均次数为：)(10inqEniidel23可见，在顺序存储结构的线性表中插入或删除一个元素时，平均要移动表中大约一半的数据元素。若表长为n，则插入和删除算法的时间复杂度都为O(n)。11npinqi12)1(110ninnEniins21)(110ninnEnidel如果在线性表的任何位置插入或删除元素的概率相等，即则,24顺序表存储结构的特点顺序存储结构的线性表可以随机存取其中的任意元素。定位操作可以直接实现。高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表，使其程序设计十分方便。•优点：•缺点：（1）数据元素最大个数需预先确定，需预先分配相应的存储空间。（2）在插入操作和删除操作时需移动大量数据，运算效率很低。（3）顺序存储结构的线性表的存储空间不便于扩充。如果线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。252.3线性表的链式存储结构2.3.1线性单链表2.3.2循环链表2.3.3双向链表26线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。对线性表中的每一个数据元素(结点)，都需用两部分来存储：一部分用于存放数据元素值，称为数据域。另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域。在链式存储结构方式下，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系由指针域来确定。线性表的链式存储272.3.1线性单链表此种形式的链表因每个节点只含有一个指针域，称为单向链表，简称单链表。图2-7(a)所示为一个空线性链表。图2-7(b)所示为一个非空线性链表（a0，a1，a2，…，an-1）。a0a1an-1LL…(a)(b)图2-7线性链表的存储结构1．线性单链表上图中，通常在线性链表的第一结点之前附设一个称为头结点的结点。头结点的数据域可以不存放任何数据，也可以存放链表的结点个数的信息。对空线性表，附加头结点的指针域为空（NULL或0表示），用∧表示。对于链表的各种操作必须从头指针开始。28例如，如下结点类型，数据域包含三个数据项：学号、姓名、成绩。structstudent{charnum[8];/*数据域*/charname[8];/*数据域*/intscore;/*数据域*/structstudent*next;/*指针域*/}在C语言中，定义链表结点的形式如下：struct结构体名{数据成员表；struct结构体名*指针变量名；}29假设h,p,q为指针变量，可用下列语句来说明：structstudent*h,*p,*q;在C语言中，用户可以利用malloc函数向系统申请分配链表结点的存储空间，该函数返回存储区的首地址，例如：p=(structstudent*)malloc(sizeof(structstudent));指针p指向一个新分配的结点。如果要把此结点归还给系统，则用函数free(p)来实现。30２．线性链表的基本操作下面给出的单链表的基本操作实现算法都是以带头结点的单链表为数据结构基础。typedefintElemType;#defineTRUE1#defineFALSE0#defineflag-1/*定义ElemType为int类型*/#includestdio.h#includemalloc.h31单链表的结点类型typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkedList;32（1）初始化单链表LinkedListLinkedLi