第二章 线性表091001.ppt

1、第二章 线性表,线性结构特点： 在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继,2.1 线性表的类型定义 1、线性表 线性表(Linear List) ：由n(n0)个数据元素(结点)a1，a2， an组成的有限序列。 其中：数据元素的个数n定义为表的长度。 当n=0时称为空表 常将非空的线性表(n0)记作： (a1，a2，an) 说明 ：数据元素ai(1i n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 例1、26个英文

2、字母组成的字母表 （ A，B，C、Z）,例3、学生健康情况登记表如下：,例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况： （6，17，28，50，92，188）,例4、一副扑克的点数 （2，3，4，J，Q，K，A） 从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1； 其余的内部结点ai(2 i n-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。 线性表是一种典型的线性结构。,2、抽象数据类型线性表的定义 ADT Li

3、st 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： InitList( ListInsert(Lc，+k，ai); while(j=Lb _ len) GetElem(Lb，j+，bj);ListInsert(Lc，+k，bi); ,数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,2.2 线性表的顺序表示和实现 2.2.1 顺序表 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用L个存储单元，并以所

4、占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a i )之间满足下列关系： LOC(a i+1)=LOC(a i)+L 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*L,图示,a1,a2,ai,b,b+L,b+L*(I-1),1,2,i,内存,元素序号,b+L*(n-1),an,n,返回,typedef struct card int num; char name20; char author10; char publisher30; float price;

5、 elemtype;,#define LIST_INIT_SIZE 100 /线性表初始空间， 是单位空间的倍数 #define LISTINCREMENT 10 /分配空间增量 typedef struct ElemType *elem; /存储空间起始地址 int length; /当前长度 int listsize; /当前分配空间 SqList;,例如： SqList l, *pl;,下面为用C语言描述的可动态分配的一维数组：,2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。 1.顺序表的初始化: 顺序表的初始化即构

6、造一个空表 。算法如下： Status InitList_Sq( SqList ,return OK; 2、插入: 线性表的插入运算是指在表的第i (1 i n+1)个位置上，插入一个新结点e，使长度为n的线性表,(a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，e，ai，an) 算法2.4,图示,Status ListInsert_sq (SqList ,if (!newbase) exit ( OVERFLOW ); L.elem=newbase; L.listsize+=LISTINCREMENT; q= ,e,返回,现在分析算法的复杂度。 这里的问题规模是

7、表的长度，设它的值为n。该算法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。,当i=n时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；,当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。,算法时间复杂度T(n) 设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较

8、大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。 3、删除 线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表： (a1，a i-1，ai，a i+1，an) 变成长度为n-1的线性表 (a1，a i-1，a i+1，an),Status ListDelete (SqList ,return OK; 分析： 该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。 若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点； 若i=1，则前移语句将循环执行n-1次，需移

9、动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。 删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 式中，Qi表示删除表中第i个结点的概率。,在等概率的假设下， p1=p2=p3=pn=1/n 由此可得： 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。,结论1：在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低,4. 按值查找 线性表中的按值查找是指在线性表中查找与给定值e相等的数据元素。在顺序表

10、中完成该运算最简单的方法是：从第一个元素 a1 起依次和e比较，直到找到一个与e相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与 e 相等的元素，返回-1或0。 int Locate_Sq(SqList L, ElemType e ) i=0; /此题与书不同 p=L.elem;,2.2.3 顺序表应用举例,while(i=L.length) return -1; else return i; /*返回的是存储位置*/ /算法2.6,例 1 有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升

11、序排列。 算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。,void MergeList_Sq( SqList La, SqList Lb,SqList while (pa=pa_last else *pc+=*pb+; while (pa=pa_last) *pc+=*pa+; while (pb=pb_last) *pc+=*pb+; ,顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需

12、要移动大量的元素 预先分配空间需按最大空间分配，利用不充分,2.3 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。 结点形式： 其中： data域是数据域，用来存放结点的值。 next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。 特点：链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。,定义形式,typedef struc

13、t LNode elemtype data; struct LNode *next; LNode , *LinkList;,2.3.1 线性链表 一、基本概念和使用 单链表：结点中只含一个指针域的链表叫，也叫单链表,注意：区分指针变量和结点变量这两个不同的概念。 LNode是结点的类型，LinkList是指向Lnode类型结点的指针类型。,头指针：为增强程序的可读性，通常设置一个链表的头指针，单链表可以用头指针的名字来命名。如：下面链表可称为表head,说明： 通常将标识链表的头指针说明为LinkList类型的变量，如： LinkList head ; 当head有定义时， NULL，则表示一

14、个空表； 第一个结点的地址，即链表的头指针； 将指向某结点的指针变量说明为LNode *类型，如: LNode *p； 例如 ：p=malloc(sizeof(LNode)； free(p)；,引用方法,练习：指针赋值的操作,指针指向结点 p=q,指针指向后继 p=q-next,指针移动 p=p-next,链指针改接 p-next =q,链指针改接后继 p-next =q-next,练习：指针赋值的操作,例 线性表 ( ZHAO , QIAN , SUN , LI , ZHOU , WU , ZHENG , WANG),43,13,1,NULL,37,7,19,52,头指针, 110 130

15、135 160 头指针 head 165 170 200 205 ,例1、已知线形表的链式表示如下：求该线形表,线性表:(bat，cat，eat，fat，hat，jat，lat，mat),二、基本算法 1、建立单链表 动态地建立单链表的常用方法有如下两种： 1) 头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。,Status CreateList (LinkList / 先建立一个空的单链表,scanf(x); while (x !=FLAG) p=(LNode*)malloc(sizeof

16、(LNode); /省略不成功时的语句 pdata=x; pnext=L; L=p; scanf(x); return OK; / CreateList,42,25,在头部插入建立单链表,2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。 例：,初始状态：头指针H=NULL，尾指针 r=NULL; 按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到 r 所指结点的后面，然后 r 指向新结点（但第一个

17、结点有所不同，读者注意下面算法中的有关部分）。,在尾部插入建立单链表,H=NULL r=NULL /*初始状态*/,29,r,H,76,r,H,编程分析： 如果第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。,如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：,a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进

18、行特殊处理； b、无论链表是否为空，其头指针是指向头结点（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。,头结点：在单链表第一个结点前附设一个结点 线性表为空:头结点指针域为空 ;,带头结点的算法如下： Status CreateList_L( LinkList ,练习：如果不带头 结点算法如何设计,Status CreateList_L( LinkList ,上述算法里动态申请新结点空间时未加错误处理，可作下列处理： p=(LinkList )malloc(sizeof(LNode) if(p=NULL) error(No space for node can be obta

19、ined); return ERROR; 以上算法的时间复杂度均为O(n)。,2、查找运算 1）按序号查找 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，其算法如下： Status GetElem (LinkList L, int i,ElemType j=1; while(p ,2）查找元素操作（练习 ）,LNode

20、* LocateElem_L( LinkList L， ElemType e ) / 在 L 所指的链表中查找第一个值和 e 相等的数据元素， /若存在，则返回它在链表中的位置，即指向该数据元 /素所在结点的指针；否则返回 NULL p=L; while ( p / LocateElem_L,LNode * LocateNode(LinkList head，ElemType key) p=headnext; while( p 该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。,同样是按值 查找两者有何 不同,插入：在线性表两个数据元素a和b

21、间插入e，已知p指向a,s-next=p-next;,p-next=s;,3、插入运算 插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：,具体算法如下： Status ListInsert_L(LinkList return OK /算法2.9,4 删除运算,删除：单链表中删除b，设p指向a,p-next=p-next-next;,设链表的长度为n，合法

22、的插入位置是1in+1。 当i=1时，要找到的是头结点， 当i=n+1时，应该找到的是结点an。因此，算法的时间主要耗费在查找操作上，故时间复杂度亦为O(n)。,具体算法如下： 算法2.10 Status ListDelete_L(LinkList ,显然此算法的时间复杂度也是O(n)。 从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。 单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢,练习与分析：将两个非递减排列的单链表归并为一个新的非递减排列的单链表（算法2.12),先回顾算法2.2 已知

23、线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 此问题的算法如下：,void mergelist(list la，list lb，list ,while(i=la-len) getelem(la，i+，ai);listinsert(lc，+k，ai); while(j=lb-len) getelem(lb，j+，bj);listinsert(lc，+k，bi); ,数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,顺序表的实现 void mergelist_sq(sqliat la,

24、sqliat lb,sqliat while (papa_last else *pc+=*pb+; while (pa=pa_last) *pc+=*pa+; while (pb=pb_last) *pc+=*pb+; ,链表的实现,void mergelist_l (linklist ,静态链表定义如下： #define MAXSIZE 1000 /*足够大的数*/ typedef struct elemtype data; int cur; component, SlinkNodeMAXSIZE; 这种链表的结点中也有数据域data和指针域cur，与前面所讲的链表中的指针不同，该指针是结点

25、的相对地址(数组的下标)，称之为静态指针，这种链表称之为静态链表。 空指针用0表示 ,表明表尾。 数组的第零分量看作头结点。,data cur,0 1 2 3 4 5,三 静态链表,与链表的主要区别,与线性表的主要区别：物理地址连续，但逻辑结构不一定连续。,2.3.2 循环链表(circular linked list) 循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：头尾相接无须增加存储量，仅对表的链接方式稍作改变，却使得从表中任一结点出发均可找到表中其他结点，提高查找效率，更加方便灵活。,带头结点的循环链表,单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结

26、点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。,操作与单链表基本一致,循环条件不同 单链表p或p-next=NULL 循环链表p-next=H,练习： 两个用尾指针标识的单循环链表的连接,heada,headb,free,headb-next=heada-next ?,例、在链表上实现将两个线性表(a1，a2，a3，an)和(b1，b2，b3，bn)链接成一个线性表的运算。 LinkList connect(LinkList heada，LinkList headb) /heada、 headb均为用尾指针表示的单循环链表 p=headanext; headanext=(h

27、eadbnext)next free(headbnext); headbnext=p; return(headb); ,2.3.3双链表（double Linked list） 双向链表(double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为： typedef struct DuLNode ElemType data; struct DuLNode *prior，*next; DuLNode, * DuLinkList; DuLinkList head;,和单链表类似，双链表一般也

28、是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。,设指针p指向某一结点，则双向链表结构的对称性可用下式描述： (pprior)next=p=(pnext)prior 即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放 在它的后继结点*(pnext)的直接前趋指针域中。,p,Status ins_dulist(DuLinkList p,ElemType e) s=(DuLinkList )malloc(sizeof(DuLNode); s-data=e; s-prior=p-prio

29、r; p-prior-next=s; s-next=p; p-prior=s; return OK; ,算法描述,算法评价：T(n)=O(1),插入：在结点p前插入数据域为x的结点,Status del_dulist(DuLinkList ,删除,算法描述,算法评价：T(n)=O(1),p-prior-next=p-next;,p-next-prior=p-prior;,小结： 如何选取存储结构呢？通常有以下几点考虑： 基于存储的考虑 顺序表的存储空间是静态分配的,链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。 基于运

30、算的考虑 如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。,基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是考虑的一个因素。 总之，两中存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。,2.4 线性表的应用举例 一元多项式的表示及相

31、加 一元多项式的表示： Pn(x)=P0 + P1x + P2x2 + + Pnxn,一元多项式单链表的结点定义,typedef struct node float coef; int exp; struct node *next; polynomial;,一元多项式相加,设p,q分别指向A,B中某一结点，p,q初值是第一结点,运算规则,算法描述,顺序存储线性表的插入和删除的一个完整C程序实例,typedef int ElemType; typedef int Status; #define OK 1 #define OVERFLOW -2 #define ERROR 0 #define LI

32、ST_INIT_SIZE 100 #define LISTINCREMENT 10,typedef struct ElemType *elem; int length; int listsize; Sqlist,Status ListInsert_Sq(Sqlist *L, int i, ElemType e);,Status InitList_Sq(Sqlist *L);,Status ListDelete_Sq(Sqlist *L,int i,ElemType *e);,Sqlist Lst; int i, n=101; ElemType e; if(InitList_Sq( / 换行,f

33、or(i=0;iLst.length;i+) printf(i,e=%d,%dn,i,Lst.elemi); / 打印值1到n getch(); / 等待键盘响应 if(ListDelete_Sq( / 等待键盘响应,for(i=0;iLst.length;i+) printf(i,e=%d,%dn,i,Lst.elemi); / 打印线性表Lst的所有元素 ,Status InitList_Sq(Sqlist *L) / 算法2.3 / 构造一个空的线性表L L-elem=(ElemType *)malloc (LIST_INIT_SIZE *sizeof(ElemType); if(!L-el