数据结构-第2章-V2A.ppt

08:56:33,1,第2章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加,08:56:33,CH.2,2,2.l 线性表的类型定义,线性表是最常用、最简单的数据结构。 一个线性表是n个数据元素的有限序列。 数据元素可以是一个数、一个符号、也可是一幅图、一页书或更复杂的信息。,08:56:33,CH.2,3,2.l 线性表的类型定义,一般定义 线性表(Linear List) ：由n(n0)个同种类型数据元素(结点)a1，a2， an组成的有限序列。其中n为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。,08:56:33,CH.2,4,2.l 线性表的类型定义,举例 例1、26个英文字母组成的字母表 （A，B，C、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188）,08:56:33,CH.2,5,2.l 线性表的类型定义,例3、学生健康情况登记表如下：,08:56:33,CH.2,6,2.l 线性表的类型定义,线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋； 有且仅有一个终端结点an，它没有直接后继； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。 通常ai是ai+1的直接前趋（前驱、前件）元素，ai+1是ai的直接后继（后件）元素。 i为位序。,08:56:33,CH.2,7,2.l 线性表的类型定义,形式化定义 Linearlist = (D, R),其中： D0为某个数据对象的集合 N为线性表长度,08:56:33,CH.2,8,2.l 线性表的类型定义,抽象数据类型线性表的定义(P19) ADT List 数据对象: D=ai| ai(-ElemSet，i=1,2,.,n,n=0 数据关系: R1=| ai-1,ai(- D, i=2,.,n 基本操作： InitList(&L) DestroyList(&L),08:56:33,CH.2,9,2.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),08:56:33,CH.2,10,2.l 线性表的类型定义,ListInsert(&L,i,e) ListDelete(&L,i,&e) ListTraverse(L,visit() union(&La, Lb)/也可作为基本操作之一 ADT List,08:56:33,CH.2,11,例2-1 求A=AUB（P20),void union (List /union,08:56:33,CH.2,12,2.2 线性表的顺序表示和实现,线性表的顺序表示 用一组地址连续的存储单元依次存储线性表的数据元素。 C语言中的数组即采用顺序存储方式。,08:56:33,CH.2,13,图示：数组在内存中的存放,08:56:33,CH.2,14,顺序表：顺序存储结构的线性表,假设线性表的每个元素需占用 L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系： LOC(ai+1)=LOC(ai)+L LOC(ai)=LOC(a1)+(i-1)*L 式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用b表示。 线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。 顺序存储结构的线性表也简称为顺序表。 顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。,08:56:33,CH.2,15,顺序表的类C语言表示,线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 100 #define LIST_INCREMENT 10 /用于动态分配 typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 int listsize; /当前分配的存储容量以一数据元素存储长度为单位 SqList;,08:56:33,CH.2,16,顺序表部分操作的类C实现：,Status InitList_Sq(SqList /GetElem,08:56:33,CH.2,17,顺序表的插入与删除操作,插入过程： 准备、后移、插入、调整,插入前n=8;插入后n=9;,删除前n=8;删除后n=7;,删除过程： 准备、（取出）前移、调整,08:56:33,CH.2,18,顺序表的插入算法（算法2.4）,Status ListInsert_Sq(SqList /ListInsert_Sq,08:56:33,CH.2,19,顺序表的插入算法的T(n),问题规模是表的长度，设它的值为n,插入位置为i。 该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。 当循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，此时T(n)=O(1)； 当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况。此时T(n)=O(n)。,08:56:33,CH.2,20,顺序表的插入算法的T(n),算法的平均复杂度： 在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点移动的平均次数，则在第i个位置上插入一个结点的移动次数为n-i+1。故 Eis(n)=pi*(n-i+1) 假设在表中任何位置(1in+1)上插入结点的机会是均等的，则有： p1=p2=p3=p n+1=1/(n+1) 此时：Eis(n)= (n-i+1)/(n+1)=n/2 也就是说，在顺序表上做插入运算，平均要移动表上一半结点。 所以算法的平均复杂度为T(n)=O(n/2)=O(n),08:56:33,CH.2,21,顺序表的合并算法（算法2.7）,void MergeList_Sq(SqList La, SqList Lb, SqList ,08:56:33,CH.2,22,顺序表的合并算法（算法2.7）,pa_last= La.elem+La.length-1; pb_last= Lb.elem+Lb.length-1; /=归并 while(pa=pa_last /MergeList_Sq,08:56:33,CH.2,23,2.3 线性表的链式表示和实现,线性表顺序表示的特点 物理位置上的邻接关系来表示结点间的逻辑关系. 可以随机存取表中的任一结点. 但插入和删除操作会移动大量的结点，效率低。 存储空间不适宜动态分配。 为克服顺序表的不足，我们介绍线性表的另一种存储方式链式存储结构,08:56:33,CH.2,24,2.3.1线性链表,链式存储结构的线性表，简称为链表(Linked List)。 链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。 因此，链表中结点的逻辑次序和物理次序不一定相同。,08:56:33,CH.2,25,单链表,为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针域(pointer)或链(link)。 其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。 这种链表的每一个结只有一个链域，称为单链表（Single Linked)。,08:56:33,CH.2,26,线性链表图示,链表中的结点结构：,2000:1000,头指针：,08:56:33,CH.2,27,线性链表的存储实现,用C语言描述的单链表如下 typedef struct LNode ElemType data; struct LNode *next; LNode; typedef struct LNode * LinkList; 头指针与头结点的区别： 头指针只相当于结点的指针域，头结点即整个线性链表的第一个结点，它的数据域可以放数据元素，也可以放线性表的长度等附加信息，也可以不存储任何信息。,08:56:33,CH.2,28,单链表的操作实现(类C语言),初始化操作 Status Init_L(LinkList L) if (L=(LinkList *) malloc(sizeof(LNode) L-next=NULL; return OK; else return ERROR; /Init_L,08:56:33,CH.2,29,单链表的插入：准备、定位、分配、写入、调整。,08:56:33,CH.2,30,单链表的操作实现(算法2.9),插入操作 Status ListInsert_L(LinkList /ListInsert_L,08:56:33,CH.2,31,单链表的删除：准备、定位、调整、(取出)、释放。,08:56:33,CH.2,32,单链表的操作实现(算法2.10),删除操作 Status ListDelete_L(LinkList /ListDelete_L,08:56:33,CH.2,33,单链表的操作实现(算法2.12),归并两个单链表的算法 void MergeList_L(LinkList /MergeList_L,08:56:33,CH.2,34,2.3.2循环链表,循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。 循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是它们是否等于头指针。,08:56:33,CH.2,35,2.3.3双向链表,单链表的单向性缺点：寻找结点的直接前趋比较困难。 双向链表可以克服这一缺点。 在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。,08:56:33,CH.2,36,线性表的双向链表存储结构,typedef struct DulNode ElemType data; struct DulNode *prior; struct DulNode *next; DulNode,*DuLinkList; 对指向双向链表任一结点的指针d，有下面的关系： d-next-prior=d-prior-next=d 即：当前结点后继的前趋是自身， 当前结点前趋的后继也是自身。,08:56:33,CH.2,37,双向链表的删除操作,p-prior-next=p-next; p-next-prior=p-prior; free(p);,08:56:33,CH.2,38,双向链表的删除操作(算法2.19),Status ListDelete_DuL(DuLinkList /ListDelete_DuL,08:56:33,CH.2,39,双向链表的插入操作,(0) s-data=e; (1) s-prior=p-prior; (2) s-next=p; (3) p-prior-next=s; (4) p-prior=s;,08:56:33,CH.2,40,双向链表的插入操作(算法2.18),Status ListInsert_DuL(DuLinkList /ListInsert_DuL,08:56:33,CH.2,41,一个完整的带头结点的线性链表类型定义,typedef struct LNode ElemType data; struct LNode *next; *Link,*Position; typedef struct Link head,tail; int len; LinkList;,next,data,08:56:33,CH.2,42,一个完整的带头结点的线性链表类型定义,Status MakeNode(Link /将线性链表L重置为空表，并释放原链表的结点空间,08:56:33,CH.2,43,一个完整的带头结点的线性链表类型定义,Status InsFirst(Link h,Link s); /已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前 Status DelFirst(Link h,Link /删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点,08:56:33,CH.2,44,一个完整的带头结点的线性链表类型定义,Status InsBefore(LinkList /已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值,08:56:33,CH.2,45,一个完整的带头结点的线性链表类型定义,ElemType GetCurElem(Link p); /已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 Status ListEmpty(LinkList L); /若线性链表L为空表，则返回TRUE,否则返回FALSE int ListLength(LinkList L); /返回线性链表L中的元素个数,08:56:33,CH.2,46,一个完整的带头结点的线性链表类型定义,Position GetHead(LinkList L); /返回线性链表L中头结点的位置 Position GetLast(LinkList L); /返回线性链表L中最后一个结点的位置 Position PriorPos(LinkList L,Link p); /已知p指向线性链表L中的一个结点，返回p所指结点的直接前趋的值,若无前趋，返回NULL Position NextPos(LinkList