《[工学]数据结构讲义2》由会员分享，可在线阅读，更多相关《[工学]数据结构讲义2（51页珍藏版）》请在金锄头文库上搜索。
1、2018/9/27,1,柳 青 Email: School of Software , Yunnan University,数据结构 (Data Structure),2018/9/27,2,第二章 线 性 表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现2.3.1 线性链表2.3.2 循环链表2.3.3 双向链表 2.4 一元多项式的表示及相加,2018/9/27,3,线性表(Linear List) ：由n(n0)个数据元素(结点)a1，a2， an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表， n0时线性表记作： (a
2、1，a2，an) 数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 Eg1. 某学院学生人数从2005年到2010年的变化情况：（455，580，736，910，1000, 1090）,2.1 线性表的逻辑结构,2018/9/27,4,Eg2 . 学生健康情况登记表如下：,2.1 线性表的逻辑结构,数据项(Item)、记录(Record)、文件(File),2018/9/27,5,从以上例子可看出线性表的逻辑特征是： 对非空线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-
3、1； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,2.1 线性表的逻辑结构,2018/9/27,6,线性表的抽象数据类型定义：,ADT List 数据对象：D=ai|aiElemSet, i=1,2,n,n0数据关系：R=| ai-1,ai D,i=2,n基本操作：1.InitList(&L) /构造空表L。2.LengthList(L) /求表L的长度3.GetElem(L,i,&e) /取元素ai,由e返回ai4.LocateElem(L,e,c
4、ompare() /求满足e关系的元素序号5.PriorElem(L,ce,&pre_e) /求ce的前驱,由pre_e返回6.NextElem(L,ce,&next_e) /求ce的后继,由next_e返回7.InsertElem(&L,i,e) /在元素ai之前插入新元素e8.DeleteElem(&L,i) /删除第i个元素9.EmptyList(L) /判断L是否为空表10.ClearList(&L) /置L为空表ADT List,2.1 线性表的逻辑结构,2018/9/27,7,算法2.1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。void unio
5、n(List 算法2.2 MergeList P 21,2.1 线性表的逻辑结构,2018/9/27,8,一. 顺序存储结构把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。,a1,a2,ai,an,1 2,.,.,.,.,i,n,Loc(a1),Loc(a1)+L,Loc(a1)+(i-1)*L,Loc(a1)+(n-1)*L,逻辑地址,数据元素,存储地址,2.2 线性表的顺序存储结构,2018/9/27,9,2.2 线性表的顺序存储结构,特点：线性表中相邻的元素ai，ai+1，其存储地址也相邻。即以元素在内存中的物理地址的相邻关系隐含地表示元素在
6、逻辑关系上的相邻关系。假设每个元素需占 L 个存储单元，则有 地址公式：Loc(ai+1)=Loc(ai)+L 一般地有：Loc(ai)=Loc(a1)+(i-1)*L 随机存取：访问任何一个数据元素或结点花费同样多时间。,2018/9/27,10,由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。#define ListSize 100typedef int DataType;typedef structDataType dataListSize;
7、int length; Sqlist; 算法2.3 InitList_Sq P23,2.2 线性表的顺序存储结构,2018/9/27,11,二. 顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.datai-1。以下主要讨论线性表的插入和删除两种运算。 1. 插入线性表的插入运算是指在表的第i(1in+1个位置 上，插入一个新结点x，使长度为n的线性表(a1，a i-1，ai，an) 变成长度为n+1的线性表(a1，a i-1，x，ai，an)
8、,2.2 线性表的顺序存储结构,2018/9/27,12,算法2.4 P24 Status InsertList(Sqlist ,2.2 线性表的顺序存储结构,演示,2018/9/27,13,插入算法的时间复杂度分析:设pi是在长度为n的线性表中第i个位置上插入一 个结点的概率，令Eis表示移动结点的期望值，在第i个位置上插入一个结点的移动次数为n-i+1，则,2.2 线性表的顺序存储结构,假设在表中任何位置(1in+1)上插入结点的机会是均等的，即 p1=p2=p3=p n+1=1/(n+1)，则,因此算法的平均时间复杂度为O(n)。,2018/9/27,14,2、删除线性表的删除运算是指将
9、表的第i(1in)个结点删 除，使长度为n的线性表(a1，a i-1，ai，a i+1，an)， 变成长度为n-1的线性表(a1，a i-1，a i+1，an)。 算法2.5 P24Status DeleteList(Sqlist ,2.2 线性表的顺序存储结构,演示,2018/9/27,15,删除算法的时间复杂度分析:设qi是在长度为n的线性表中第i个位置上删除一个 结点的概率，令Edl表示移动结点的期望值，在第i个位置上删除一个结点的移动次数为n-i，则,2.2 线性表的顺序存储结构,假设在表中任何位置(1in)上删除结点的机会是 均等的，既 q1=q2=q3=qn=1/n，则,因此算法的
10、平均时间复杂度为O(n)。,2018/9/27,16,1. 顺序存储结构是以元素在物理存储地址上的相邻关系隐含表示其逻辑关系上的相邻关系。 2. 顺序存储结构便于实现读写表中某个元素的值，求表的长度，求某个元素的直接前驱或后继等操作。 3. 对于插入、删除等操作，需要移动大量的元素，算法的效率不好。 HW: P 16-17 10, 11,算法2.6 P25 算法2.7 P26 小结:,2.2 线性表的顺序存储结构,2018/9/27,17,链表是指用一组任意的存储单元来依次存放线性表的结点(Node)，这组存储单元既可以是连续的，也可以是不连续的。因此，链表中结点的逻辑次序和物理次序不一定相同
11、。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针或链。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结点只有一个链域，故将这种链表称为单链表。,2.3 线性表的链式表示和实现,2.3.1 线性链表,data：数据域，用来存放结点的值。 next：指针域（亦称链域），用来存放结点的直接后继的地址。,2018/9/27,18,例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)的单链表示意图如下：,bat,cat,eat,mat ,单链表是由表头唯一确定，
12、因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用表示)。,head,2.3 线性表的链式表示和实现,2018/9/27,19,用C语言描述的单链表如下：,Typedef char datatype; Typedef struct nodedatatype data;struct node *next; listnode; typedef listnode *linkl
13、ist;,2.3 线性表的链式表示和实现,一、建立单链表假设线性表中结点的数据类型是字符，逐个输入这些字符型的结点，并以换行符n为输入结束标记。动态地建立单链表的常用方法有如下两种：,2018/9/27,20,1、头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。,2.3 线性表的链式表示和实现,linklist createlistf(void) char ch;linklist head;listnode *p;head=null;while (ch=getchar( )!=n)p=(lis
14、tnode*)malloc(sizeof(listnode);pdata=ch; pnext=head; head=p;return (head);,2018/9/27,21,2、尾插法建表头插法建立链表 虽然算法简单，但生 成的链表中结点的次 序和输入的顺序相反。 若希望二者次序一致， 可采用尾插法建表。 该方法是将新结点插 入到当前链表的表尾 上，为此必须增加 一个尾指针r，使其 始终指向当前链表的 尾结点。,2.3 线性表的链式表示和实现,linklist creater( ) char ch;linklist head;listnode *p，*r; head=NULL; r=NULL
15、;while(ch=getchar( )!=n)p=(listnode *)malloc(sizeof(listnode);pdata=ch;if(head=NULL) head=pelse rnext=p;r=p;if (r!=NULL) rnext=NULL;return(head);,2018/9/27,22,说明： 第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。,2.3 线性表的链式表示和实现,2018/9/27,
