37哈工大 数据结构课件 第3章线性表

1数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—1第三章第三章线线性性表表3.13.1抽象数据型线性表抽象数据型线性表3.23.2线性表的实现线性表的实现3.33.3栈（栈（StackStack））3.43.4队列队列（（QueueQueue））3.53.5串（串（StringString））3.63.6数组（数组（ArrayArray））3.73.7广义表广义表（（GeneralizedListGeneralizedList））第三章第三章线性表（线性表（LinerListLinerList））数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—2第三章第三章线线性性表表知识点：§线性表的逻辑结构和各种存储表示方法§定义在逻辑结构上的各种基本运算（操作）§在各种存储结构上如何实现这些基本运算§各种基本运算的时间复杂性重点：§熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析难点：§使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—3第三章第三章线线性性表表3.13.1抽象数据型线性表抽象数据型线性表[定义]线性表是由n(n≥0)个相同类型的元素组成的有序集合。记为：(a1,a2,a3,……ai-1,ai,ai+1,……an)其中：①n为线性表中元素个数，称为线性表的长度；当n=0时，为空表，记为（）。②ai为线性表中的元素，类型定义为elementtype③a1为表中第1个元素，无前驱元素；an为表中最后一个元素，无后继元素；对于…ai-1,ai,ai+1…(1in)，称ai-1为ai的直接前驱，ai+1为ai的直接后继。(位置概念！）④线性表是有限的，也是有序的。数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—4第三章第三章线线性性表表3.13.1抽象数据型线性表抽象数据型线性表线性表LIST=(D,R)D={ai|ai∈Elementset,i=1,2,…,n,n≥0}R={H}H={ai-1,ai|ai-1,ai∈D,i=2,…,n}操作：设L的型为LIST线性表实例，x的型为elementtype的元素实例，p为位置变量。所有操作描述为：①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)数学模型PDF文件以FinePrintpdfFactoryPro试用版创建—5第三章第三章线线性性表表3.13.1抽象数据型线性表抽象数据型线性表举例：设计函数DELEVAL（LIST&L,elementtyped)，其功能为删除L中所有值为d的元素。voidDELEVAL(LIST&L,elementtyped){positionp;p=FIRST(L);while(p!=END(L)){if(same(RETRIEVE(p,L),d))DELETE(p,L);elsep=NEXT(p,L);}}数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—6第三章第三章线线性性表表3.23.2线性表的实现线性表的实现问题：确定数据结构（存储结构）实现型LIST，并在此基础上实现各个基本操作。存储结构的三种方式：①连续的存储空间（数组）→静态存储②非连续存储空间——指针（链表）→动态存储③游标（连续存储空间+动态管理思想）→静态链表3.2.13.2.1指针和游标指针和游标指针：地址量，其值为另一存储空间的地址；游标：整型指示量，其值为数组的下标，用以表示指定元素的“地址”或“位置”（所在的数组下标）数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—7第三章第三章线线性性表表3.2.23.2.2线性表的数组实现线性表的数组实现第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图3-1线性表的数组实现存储池容量……第i个元素1≤i≤last顺序表：把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的下标。特点：§元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）；§是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示。数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—8第三章第三章线线性性表表3.2.23.2.2线性表的数组实现线性表的数组实现第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图3-1线性表的数组实现存储池容量……第i个元素1≤i≤last类型定义：#definemaxlength100structLIST{elementtypeelements[maxlength];intlast;};位置类型：typedefintposition;线性表L:LISTL;表示：L.elements[p]//L的第p个元素L.lastL的长度，最后元素的位置PDF文件以FinePrintpdfFactoryPro试用版创建—9第三章第三章线线性性表表3.2.23.2.2线性表的数组实现线性表的数组实现操作：①voidINSERT(elementtypex,positionp,LIST&L){positionq;if(L.last=maxlength–1)error(“表满”)；elseif((pL.last+1)||(p1))error(“指定位置不存在”)；else{for(q=L.last;q=p;q--)L.elements[q+1]=L.elements[q];L.last=L.last+1;L.elements[p]=x;}}//时间复杂性：O(n)第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图线性表的数组实现存储池容量……第i个元素1≤i≤last数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—10第三章第三章线线性性表表②positionLOCATE(elementtypex,LISTL){positionq;for(q=1;q=L.last;q++)if(L.elements[q]==x)return(q);return(L.last+1);}//时间复杂性：O(n)3.2.23.2.2线性表的数组实现线性表的数组实现③elementtypeRETRIEVE(positionp,LISTL){if(pL.last)error(“指定元素不存在”);elsereturn(L.elements[p]);}//时间复杂性：O(1)第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图线性表的数组实现存储池容量……第i个元素1≤i≤last数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—11第三章第三章线线性性表表④voidDELETE(positionp,LIST&L){positionq;if((pL.last)||(p1))error(“指定位置不存在”)；else{L.last=L.last–1;for(q=p;q=L.last;q++)L.elements[q]=L.elements[q+1];}}//时间复杂性：O(n)3.2.23.2.2线性表的数组实现线性表的数组实现⑤positionPREVIOUS(positionp,LISTL){if((p=1)||(pL.last))error(“前驱元素不存在”);elsereturn(p–1);}//时间复杂性：O(1)第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图线性表的数组实现存储池容量……第i个元素1≤i≤last数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—12第三章第三章线线性性表表⑧positionEND(LISTL){return(L.last+1);}//O(1)⑦positionFIRST(LISTL){return(1);}//复杂性：O(1)positionNEXT(positionp,LISTL){if((p1)||(p=L.last))error(“前驱元素不存在”);elsereturn(p+1);}//时间复杂性：O(1)⑥positionMAKENULL(LIST&L){L.last=0;return(L.last+1);}//时间复杂性：O(1)3.2.23.2.2线性表的数组实现线性表的数组实现第1个元素第2个元素……最后1个元素……012maxlength-1last表空单元图3-1线性表的数组实现存储池容量……第i个元素1≤i≤lastPDF文件以FinePrintpdfFactoryPro试用版创建—13第三章第三章线线性性表表3.2.33.2.3线性表的指针实现线性表的指针实现结点形式elementnext结点信息下一结点地址celltypeLISTheader;positionp,q;a1a2a3an∧…headerqp单链表：一个线性表由若干个结点组成，每个结点均含有两个域：存放元素的信息域和存放其后继结点的指针域，这样就形成一个单向链接式存储结构，简称单向链表或单向线性链表。结构特点：§逻辑次序和物理次序不一定相同；§元素之间的逻辑关系用指针表示；§需要额外空间存储元素之间的关系；§非随机存储结构数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—14第三章第三章线线性性表表3.2.33.2.3线性表的指针实现线性表的指针实现结点形式elementnext结点信息下一结点地址celltype类型定义：structcelltype{elementtypeelement;celltype*next;};/*结点型*//*线性表的型*/typedefcelltype*LIST;/*位置型*/typedefcelltype*position;LISTheader;positionp,q;a1a2a3an∧…headerqpa2:(*p).element;q:(*p).next;a2:p→element;q:p→next;记法:数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—15第三章第三章线线性性表表操作讨论：3.2.33.2.3线性表的指针实现线性表的指针实现插入元素:pa1xheaderqai-1aixpqan∧x∧qp(a)表头插入元素(b)中间插入元素(c)表尾插入元素q=newcelltype;q→element=x;q→next=p→next;p→next=q;或:temp=p→next;p→next=newcelltype;p→next→element=x;p→next→next=temp;讨论表头结点的作用数据结构与算法哈尔滨工业大学计算机科学与技术学院张岩3—16第三章第三章线线性性表表操作讨论：3.2.33.2.3线性表的指针实现线性表的指针实现删除元素:q=p→next;p→next=q→next;deleteq;或：q=p→next;p→next=p→next→next;deleteq;讨论结点ai的位置pa1header(a)删除第一个元素a2qpai-1aipq(b)删除中间元素ai+1an∧an-1qp(c)删除表尾元素∧PDF文件以FinePrintpdfFactoryPro试用版创建数据结构与算法哈