数据结构(C语言版)第2章线性表

1、1/95数据结构数据结构(Data Structures)(C语言版语言版)Instructor: WU, RANGZHONGE-mail: 2/95第二章第二章 线性表线性表 2.1 2.1 线性表的类型定义线性表的类型定义 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现 2.3.1 2.3.1 线性链表线性链表 2.3.2 2.3.2 循环链表循环链表 2.3.3 2.3.3 双向链表双向链表 2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加3/95 2.1 线性表的逻辑结构线性表的逻辑结构 线性表线性

2、表(Linear List) (Linear List) ：由：由n(nn(n0)0)个数据元素个数据元素( (结结点点)a)a1 1，a a2 2， aan n组成的有限序列。其中数据元素的组成的有限序列。其中数据元素的个数个数n n定义为表的长度。当定义为表的长度。当n=0n=0时称为空表，常常将时称为空表，常常将非空的线性表非空的线性表(n0)(n0)记作：记作： (a(a1 1，a a2 2，aan n) ) 这里的数据元素这里的数据元素a ai i(1(1i in)n)只是一个抽象的符号，只是一个抽象的符号，其具体含义在不同的情况下可以不同。其具体含义在不同的情况下可以不同。 例例1

3、 1、2626个英文字母组成的字母表个英文字母组成的字母表 （A A，B B，C C、Z Z） 例例2 2、某校从、某校从19781978年到年到19831983年各种型号的计算机拥有年各种型号的计算机拥有量的变化情况。量的变化情况。 （6 6，1717，2828，5050，9292，188188）4/95例例3、学生健康情况登记表如下：、学生健康情况登记表如下：姓姓 名名学学 号号性性 别别年龄年龄 健康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般刘建平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 神经

4、衰弱神经衰弱 . . .5/95例例4 4、一副扑克的点数、一副扑克的点数（2 2，3 3，4 4，J J，Q Q，K K，A A） 从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a a1 1，它没，它没有直接前趋，而仅有一个直接后继有直接前趋，而仅有一个直接后继a a2 2；有且仅有一个终端结点有且仅有一个终端结点a an n，它没有直接后继，而仅，它没有直接后继，而仅有一个直接前趋有一个直接前趋a a n-1n-1；其余的内部结点其余的内部结点a ai i(2(2i in-1)n-1)都有且仅

5、有一个直接都有且仅有一个直接前趋前趋a ai-1i-1和一个直接后继和一个直接后继a ai+1i+1。 线性表是一种典型的线性结构。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。实现则是在存储结构上进行的。抽象数据类型的定义为：抽象数据类型的定义为：P P19196/95抽象数据类型线性表的定义抽象数据类型线性表的定义ADT List数据对象：数据对象：D=ai=aiElemSet，i=1，2，n，n0数据关系：数据关系：R1= |ai-1 ， ai D, i=2,.,n 基本操作：基本操作：In

6、itList(&L); Destory(&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);7/952 The List ADTObjects: ( item0, item1, , itemN 1 )Operations: Finding the length, N,

7、of a list. Printing all the items in a list. Making an empty list. Finding the k-th item from a list, 0 k N. Inserting a new item after the k-th item of a list, 0 k N. Deleting an item from a list. Finding next of the current item from a list. Finding previous of the current item from a list. ADT:Wh

8、y after?8/95【Definition】Data Type = Objects Operations Example int = 0, 1, 2, , INT_MAX, INT_MIN , , , , , 【Definition】An Abstract Data Type (ADT) is a data type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated fro

9、m the representation of the objects and the implementation on the operations.9/95 算法算法2.12.1 例例2-1 2-1 利用两个线性表利用两个线性表LALA和和LBLB分别表示两个集合分别表示两个集合A A和和B B，现要求一个新的集合，现要求一个新的集合A=ABA=AB。 void Union(SqList *La,SqList Lb) ElemType e; int La_len,Lb_len; int i; La_len=ListLength(*La); Lb_len=ListLength(Lb); f

10、or(i=1;i=Lb_len;i+) GetElem(Lb,i,&e); if( !LocateElem(*La, e, equal) ) ListInsert( La, +La_len, e); 10/95 算法算法2.22.2 例例2-2 2-2 巳知线性表巳知线性表LALA和线性表和线性表LBLB中的数中的数据元素按值非递减有序排列，现要求将据元素按值非递减有序排列，现要求将LALA和和LBLB归并为一个新的线性表归并为一个新的线性表LCLC，且，且LCLC中的元素仍按值非递减有序排列。中的元素仍按值非递减有序排列。 此问题的算法如下：此问题的算法如下： 11/95void merge

11、list(list la，list lb，list &lc) initlist(lc); I=j=1;k=0; la_len=listlength(la); lb_len=listlength(lb); while(I=la_len)&(j=lb_len)12/95 getelem(la，I，ai);getelem(lb，j，bj); if(ai=bj)listinsert(lc，+k，ai);+I; elselistinsert(lc，+k，bj);+j; while(I=la_len) getelem(la，I+，ai);listinsert(lc，+k，ai); while(j0n0）。

12、）。 【清华大学清华大学 1998 1998 一一.4.4（2 2分）分）】 A A表元素表元素 B B字符字符 C C数据元素数据元素 D D数据项数据项 E E信息项信息项15/95 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构 2.2.1 2.2.1 线性表线性表( (Linear List) ) 把线性表的结点按逻辑顺序依次存放在一组地址连把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序续的存储单元里。用这种方法存储的线性表简称顺序表。表。 假设线性表的每个元素需占用假设线性表的每个元素需占用l l个存储单元，并以个存储单元，并以所

13、占的第一个单元的存储地址作为数据元素的存储位所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第置。则线性表中第i+1i+1个数据元素的存储位置个数据元素的存储位置LOC(aLOC(ai+1i+1) )和第和第i i个数据元素的存储位置个数据元素的存储位置LOC(aLOC(ai i) )之间满足下列关之间满足下列关系：系： LOC(aLOC(ai+1i+1)=LOC(a)=LOC(ai i)+l)+l 线性表的第线性表的第i i个数据元素个数据元素a ai i的存储位置为：的存储位置为： LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)+(i-1)* *l

14、l16/95 由于由于C C语言中的一维数组也是采用顺序存储表语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。所以我们用结构类型来定义顺序表类型。 # define ListSize 100# define ListSize 100 typedef int DataType; typedef int DataType; typedef

15、struc typedef struc DataType dataListSize; DataType dataListSize; int length; int length; Sqlist; Sqlist;17/95Simple Array implementation of Listsarray i = itemi MaxSize has to be estimated.AddressContentarray+iitemiarray+i+1itemi+1Sequential mapping Find_Kth takes O(1) time. Insertion and Deletion

16、not only take O(N) time, but also involve a lot of data movements which takes time.3/1818/95 2.2.2 2.2.2 顺序表上实现的基本操作顺序表上实现的基本操作 在顺序表在顺序表( (Sequential List) )存储结构中，很容易存储结构中，很容易实现线性表的一些操作，如线性表的构造、第实现线性表的一些操作，如线性表的构造、第i i个元个元素的访问。素的访问。 注意：注意：C C语言中的数组下标从语言中的数组下标从“0”0”开始，因此，若开始，因此，若L L是是SqlistSqlist类型的顺

17、序表，则表中第类型的顺序表，则表中第i i个元素是个元素是L.datai-1L.datai-1。 以下主要讨论线性表的插入和删除两种运算。以下主要讨论线性表的插入和删除两种运算。 1 1、插入插入(Insert)(Insert) 线性表的插入运算是指在表的第线性表的插入运算是指在表的第i i个位置上，插入个位置上，插入一个新结点一个新结点x x，19/95使长度为使长度为n n的线性表的线性表 (a(a1 1，a a i-1i-1，a ai i，a an n) ) 变成长度为变成长度为n+1n+1的线性表的线性表 (a(a1 1，a a i-1i-1，x x，a ai i，a an n) )

18、算法算法2.32.3 void InsertList(Sqlistvoid InsertList(Sqlist* *L L，DataType xDataType x，int i)int i) int j; int j; if(il.length+1) if(il.length+1) printf(“Position error”); printf(“Position error”); return ERROR return ERROR 20/95 if(L.length=ListSize) printf(“overflow”); exit(overflow); for(j=L.length-1

19、;j=i-1;j-) L.dataj+1=L.dataj; L.datai-1=x; L.length+; 21/95 现在分析算法的复杂度。现在分析算法的复杂度。 这里的问题规模是表的长度，设它的值为。这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。赖于表的长度，而且还与插入位置有关。 当时，由于循环变量的终值大于初值，结点后当时

20、，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂移语句将不进行；这是最好情况，其时间复杂度度O O（1 1）；）； 当当i=1i=1时，结点后移语句将循环执行时，结点后移语句将循环执行n n次，需移次，需移动表中所有结点，这是最坏情况，动表中所有结点，这是最坏情况，其时间复杂其时间复杂度为度为O O（n n）。）。22/95 由于插入可能在表中任何位置上进行，因此需分由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度析算法的平均复杂度 在长度为在长度为n n的线性表中第的线性表中第i i个位置上插入一个结点，个位置上插入一个结点，令令E Eisis(n)(

21、n)表示移动结点的期望值（即移动的平均次表示移动结点的期望值（即移动的平均次数），则在第数），则在第i i个位置上插入一个结点的移动次数为个位置上插入一个结点的移动次数为n-i+1n-i+1。故。故 E Eisis(n)=(n)=p pi i(n-i+1)(n-i+1) 不失一般性，假设在表中任何位置不失一般性，假设在表中任何位置(1(1i in+1)n+1)上插入结点的机会是均等的，则上插入结点的机会是均等的，则 p p1 1=p=p2 2=p=p3 3=p =p n+1n+1=1/(n+1)=1/(n+1) 因此，在等概率插入的情况下，因此，在等概率插入的情况下， E Eisis(n)=

22、(n)= (n-i+1)/(n+1)=n/2 (n-i+1)/(n+1)=n/2 23/95 也就是说，在顺序表上做插入运算，平均要移动也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长表上一半结点。当表长 n n较大时，算法的效率相当较大时，算法的效率相当低。虽然低。虽然E Eisis(n)(n)中中n n的的系数较小，但就数量级而言，的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为它仍然是线性阶的。因此算法的平均时间复杂度为O(n)O(n)。 2 2、删除删除(Delete)(Delete) 线性表的删除运算是指将表的第线性表的删除运算是指将表的第i(

23、1i(1i in)n)结点删除，使长度为结点删除，使长度为n n的线性表：的线性表： (a(a1 1，a a i-1i-1，a ai i，a a i+1i+1，a an n) ) 变成长度为变成长度为n-1n-1的线性表的线性表 (a(a1 1，a a i-1i-1，a a i+1i+1，a an n) )24/95 void deleteList(Sqlist*L，int i) int j; if(iL.length) printf(“Position error”); return ERROR for(j=i; jdata = ZHAO ;N2-data = QIAN ;N1-next =

24、 N2 ;N2-next = NULL ;ptr = N1 ;ZHAOQIANptrNULLLocations of the nodes maychange on different runs.4/1830/95 2.3.1 2.3.1 线性链表线性链表 链表是指用一组任意的存储单元来依次存放线链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序置上的。因此，链表中结点的逻辑次序和物理次序

25、不一定相同。为了能正确表示结点间的逻辑关系，不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针结点的地址（或位置）信息，这个信息称为指针(pointer)(pointer)或链或链(link)(link)。这两部分组成了链表中的。这两部分组成了链表中的结点结点结构：结构：31/95 其中：其中：datadata域域是数据域，用来存放结点的值。是数据域，用来存放结点的值。nextnext是是指针域（亦称链域），用来存放结点的直接后指针域（亦称链域），用来存放结点的直接后继的

26、地址（或位置）。链表正是通过每个结点的链域继的地址（或位置）。链表正是通过每个结点的链域将线性表的将线性表的n n个结点按其逻辑次序链接在一起的。由于个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称上述链表的每一个结只有一个链域，故将这种链表称为为单链表单链表（Single Linked)Single Linked)。 显然，单链表中每个结点的存储地址是存放在其显然，单链表中每个结点的存储地址是存放在其前趋结点前趋结点nextnext域中，而开始结点无前趋，故应设头指域中，而开始结点无前趋，故应设头指针针headhead指向开始结点。同时，由于终端结点无后继，

27、指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即故终端结点的指针域为空，即nullnull（图示中也可用（图示中也可用 表表示示) )。 例例1 1、线性表、线性表:(bat:(bat，catcat，eateat，fatfat，hathat，jatjat，latlat，mat)mat)datalink32/95单链表示意图如下：单链表示意图如下： 110 130 135 160头指针头指针 head 165 170 200 205 hathat200200.catcat135135eateat170170.matmatNullNullbatbat130130fatfat110

28、110jatjat205205latlat160160 16533/95 headbat cat eat mat 单链表是由表头唯一确定，因此单链表可以用头单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。指针的名字来命名。例如：若头指针名是例如：若头指针名是headhead，则把链表称为表，则把链表称为表headhead。用用C C语言描述的单链表如下：语言描述的单链表如下：Typedef char datatype; Typedef struct node datatype data; struct node *next;listnode;34/95 typedef listno

29、de typedef listnode * *linklist;linklist; listnode listnode * *p;p; linklist head; linklist head;注意区分指针变量和结点变量这两个不同的概念。注意区分指针变量和结点变量这两个不同的概念。P P为动态变量，它是通过标准函数生成的，即为动态变量，它是通过标准函数生成的，即 p=(listnodep=(listnode* *) )mallocmalloc(sizeof(listnode);(sizeof(listnode);函数函数mallocmalloc分配了一个类型为分配了一个类型为listnodel

30、istnode的结点变量的的结点变量的空间，并将其首地址放入指针变量空间，并将其首地址放入指针变量p p中。一旦中。一旦p p所指所指的结点变量不再需要了，又可通过标准函数的结点变量不再需要了，又可通过标准函数 freefree(p)(p)释放所指的结点变量空间。释放所指的结点变量空间。35/95一、建立单链表一、建立单链表 假设线性表中结点的数据类型是字符，我们逐个输假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符入这些字符型的结点，并以换行符n为输入结束为输入结束标记。动态地建立单链表的常用方法有如下两种：标记。动态地建立单链表的常用方法有如下两种： 1、头插法建

31、表、头插法建表 该方法从一个空表开始，重复读入数据，生成新该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志新结点插入到当前链表的表头上，直到读入结束标志为止。为止。36/95 linklist createlistf(void) char ch; linklist head; listnode *p; head=null; ch=getchar( ); while (ch!= n) p=(listnode*)malloc(sizeof(listnode); pda

32、ta=ch; pnext=head; head=p; ch=getchar( ); return (head); 37/95 listlink createlist(int n) int data; linklist head; listnode *p head=null; for(i=n;i0;-i) p=(listnode*)malloc(sizeof(listnode); scanf(%d，&pdata); pnext=head; head=p; return(head); 38/952 2、尾插法建表、尾插法建表 头插法建立链表虽然算法简单，但生成的链头插法建立链表虽然算法简单，但生成

33、的链表中结点的次序和输入的顺序相反。若希望二者表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个点插入到当前链表的表尾上，为此必须增加一个尾指针尾指针r r，使其始终指向当前链表的尾结点。例：，使其始终指向当前链表的尾结点。例：39/95 linklist creater( ) char ch; linklist head; listnode *p，*r; head=NULL;r=NULL; while(ch=getchar( )!= n) p=(listnode *)mall

34、oc(sizeof(listnode); pdata=ch; if(head=NULL) head=p; else rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); 40/95 说明：说明：第一个生成的结点是开始结点，将开始结点第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放作处理是不一样的，原因是开始结点的位置是存放在头指针（

35、指针变量）中，在头指针（指针变量）中，而其余结点的位置是在而其余结点的位置是在其前趋结点的指针域中。算法中的第一个其前趋结点的指针域中。算法中的第一个ifif语句就语句就是用来对第一个位置上的插入操作做特殊处理。算是用来对第一个位置上的插入操作做特殊处理。算法中的第二个法中的第二个ifif语句的作用是为了分别处理空表和语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表结束标志符，则链表headhead是空表，尾指针是空表，尾指针r r亦为空，亦为空，结点结点* *r r不存在；否则链表不存在；否则链表head

36、head非空，最后一个尾结非空，最后一个尾结点点* *r r是终端结点，应将其指针域置空。是终端结点，应将其指针域置空。41/95 如果我们在链表的开始结点之前附加一个结点，如果我们在链表的开始结点之前附加一个结点，并称它为头结点并称它为头结点( (dummy head node ) )，那么会带来，那么会带来以下两个优点：以下两个优点： a a、由于开始结点的位置被存放在头结点的指针、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；的其它位置上的操作一致，无需进行特殊处理；

37、 b b、无论链表是否为空，其头指针是指向头结点、无论链表是否为空，其头指针是指向头结点 在的非空指针（空表中头结点的指针域为空），因在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。此空表和非空表的处理也就统一了。H(a)a1a2anH(b)42/95其算法如下：其算法如下：linklist createlistr1( ) char ch; linklist head=(linklist)malloc(sizeof(listnode); listnode *p，*r; r=head; while(ch=getchar( )!= n p=(listnode*)mall

38、oc(sizeof(listnode); pdata=ch; pnext=p; r=p; rnext=NULL; return(head); 43/95上述算法里动态申请新结点空间时未加错误处理，上述算法里动态申请新结点空间时未加错误处理，可作下列处理：可作下列处理： p=(listnode*)malloc(sizeof(listnode) if(p=NULL) error(No space for node can be obtained); return ERROR; 以上算法的时间复杂度均为以上算法的时间复杂度均为O(n)。44/95二、查找运算二、查找运算 1 1、按序号查找、按序号查

39、找 在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号i i，也不，也不能象顺序表中那样直接按序号能象顺序表中那样直接按序号i i访问结点，而只能从访问结点，而只能从链表的头指针出发，顺链域链表的头指针出发，顺链域nextnext逐个结点往下搜索，逐个结点往下搜索，直到搜索到第直到搜索到第i i个结点为止。因此，链表不是随机存个结点为止。因此，链表不是随机存取结构。取结构。 设单链表的长度为设单链表的长度为n n，要查找表中第，要查找表中第i i个结点，仅个结点，仅当当1 1i in n时，时，i i的值是合法的。但有时需要找头结的值是合法的。但有时需要找头结点的位置，故我们

40、将头结点看做是第点的位置，故我们将头结点看做是第0 0 个结点，其个结点，其算法如下：算法如下：45/95Listnode * getnode(linklist head ， int i) int j; listnode * p; p=head; j=0; while(pnext & jnext; j+; if (i=j) return p; else return NULL; 46/95 2 2、按值查找、按值查找 按值查找是在链表中，查找是否有结点值等于给定按值查找是在链表中，查找是否有结点值等于给定值值keykey的结点，若有的话，则返回首次找到的其值为的结点，若有的话，则返回首次找到的

41、其值为keykey的结点的存储位置；否则返回的结点的存储位置；否则返回NULLNULL。查找过程从开。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值始结点出发，顺着链表逐个将结点的值和给定值keykey作作比较。其算法如下：比较。其算法如下：47/95Listnode * locatenode(linklist head，int key) listnode * p=headnext; while( p & pdata!=key) p=pnext; return p; 该算法的执行时间亦与输入实例中的的取值该算法的执行时间亦与输入实例中的的取值keykey有有关，其平均时间复杂度的分析类

42、似于按序号查找，关，其平均时间复杂度的分析类似于按序号查找，也为也为O(n)O(n)。48/95三、插入运算三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上，即插入到个结点的位置上，即插入到a ai-1i-1与与a ai i之间。因之间。因此，我们必须首先找到此，我们必须首先找到a ai-1i-1的存储位置的存储位置p p，然，然后生成一个数据域为后生成一个数据域为x x的新结点的新结点* *p p，并令结点，并令结点* *p p的指针域指向新结点，新结点的指针域指的指针域指向新结点，新结点的指针域指向结点向结点a ai i。从而

43、实现三个结点。从而实现三个结点a ai-1i-1，x x和和a ai i之间之间的逻辑关系的变化，插入过程如：的逻辑关系的变化，插入过程如：49/95 s-next=p-next; p-next=s; pxsaianhai-1 注意：两条语句的顺序不能颠倒注意：两条语句的顺序不能颠倒，否则，否则ai的地址会的地址会 丢失。丢失。 另外，要注意合法另外，要注意合法 i 值为：值为：1i n+1 若若 in+1，则，则 i 值非法。值非法。 Question: What will happen if the order of the two steps is reversed?50/95具体算法如

44、下：具体算法如下： void insertnode(linklist head，datetype x，int i) listnode * p，*q; p=getnode(head，i-1); if(p=NULL) error(position error); q=(listnode *)malloc(sizeof(listnode); qdata=x; qnext=pnext; pnext=q; 51/95 设链表的长度为设链表的长度为n n，合法的插入位置是，合法的插入位置是1 1i in+1n+1。注意当注意当i=1i=1时，时，getnodegetnode找到的是头结点，当找到的是头结点

45、，当 i=n+1i=n+1时，时，getnodegetnode找到的是结点找到的是结点a an n。因此，用。因此，用i-1i-1做做实参调用实参调用getnodegetnode时可完成插入位置的合法性检查。时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作算法的时间主要耗费在查找操作getnodegetnode上，故时上，故时间复杂度亦为间复杂度亦为O(n)O(n)。四、删除运算四、删除运算 删除运算是将表的第删除运算是将表的第i i个结点删去。因为在单链个结点删去。因为在单链表中结点表中结点a ai i的存储地址是在其直接前趋结点的存储地址是在其直接前趋结点a a a a i-1i

46、-1的指针域的指针域nextnext中，所以我们必须首先找到中，所以我们必须首先找到 52/95 a a i-1i-1的存储位置的存储位置p p。然后令。然后令p pnextnext指向指向a ai i的的直接后继结点，即把直接后继结点，即把a ai i从链上摘下。最后释放从链上摘下。最后释放结点结点a ai i的空间，将其归还给的空间，将其归还给“存储池存储池”。此过。此过程为：程为：53/95s=p-next;phai-1sp-next=p-next-next;free(s);aianai+1ai Question: How can wedelete the first node from

47、 a list?Answer: We can add a dummy head node to a list.54/95具体算法如下具体算法如下： void deletelist(linklist head， int i) listnode * p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; 55/95 设单链表的长度为设单链表的长度为n n，则删去第，则删去第i i个结点仅当个结点仅当1 1i in n时是合法的。注意，当时是合法的。

48、注意，当i=n+1i=n+1时，虽然时，虽然被删结点不存在，但其前趋结点却存在，它是被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋终端结点。因此被删结点的直接前趋* *p p存在并存在并不意味着被删结点就一定存在，仅当不意味着被删结点就一定存在，仅当* *p p存在存在（即（即p!=NULLp!=NULL）且）且* *p p不是终端结点不是终端结点 （即（即p pnext!=NULLnext!=NULL）时，才能确定被删结点）时，才能确定被删结点存在。存在。 显然此算法的时间复杂度也是显然此算法的时间复杂度也是O(n)O(n)。 从上面的讨论可以看出，链表上实现插入和

49、从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。删除运算，无须移动结点，仅需修改指针。56/95线性表实现方法的比较线性表实现方法的比较 实现不同实现不同 顺序表方法简单，各种高级语言中都有数组类型，容顺序表方法简单，各种高级语言中都有数组类型，容易实现；链表的操作是基于指针的，相对来讲复杂些。易实现；链表的操作是基于指针的，相对来讲复杂些。 存储空间的占用和分配不同存储空间的占用和分配不同 从存储的角度考虑，顺序表的存储空间是静态分配的，从存储的角度考虑，顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是在程序执行之前必须明确规定它的存储

50、规模，也就是说事先对说事先对“MAXSIZE”MAXSIZE”要有合适的设定，过大造成浪要有合适的设定，过大造成浪费，过小造成溢出。而链表是动态分配存储空间的，费，过小造成溢出。而链表是动态分配存储空间的，不用事先估计存储规模。可见对线性表的长度或存储不用事先估计存储规模。可见对线性表的长度或存储规模难以估计时，采用链表。规模难以估计时，采用链表。 线性表运算的实现不同线性表运算的实现不同 按序号访问数据元素，使用顺序表优于链表。按序号访问数据元素，使用顺序表优于链表。 插入删除操作插入删除操作 ，使用链表优于顺序表。，使用链表优于顺序表。 57/95 2.3.2 2.3.2 循环链表循环链表

51、( (Linked Circular Lists) ) 循环链表时一种头尾相接的链表。其特点是无须循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。得表处理更加方便灵活。 单循环链表：单循环链表：在单链表中，将终端结点的指针在单链表中，将终端结点的指针域域NULLNULL改为指向表头结点的或开始结点，就得到了改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。单链形式的循环链表，并简单称为单循环链表。 为了使空表和非空表的处理一致，循环链表中为了使空表和非空表的处理

52、一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：自成循环的头结点表示。如下图所示：58/95 a1 an .head 非空表非空表 空表空表 在用头指针表示的单链表中，找开始结点在用头指针表示的单链表中，找开始结点a1的时间是的时间是O(1)，然而要找到终端结点，然而要找到终端结点an，则需，则需从头指针开始遍历整个链表，其时间是从头指针开始遍历整个链表，其时间是O(n)head59/95 在很多实际问题中，表的操作常常是在表的首尾位在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单

53、循环链表就显得不够置上进行，此时头指针表示的单循环链表就显得不够方便方便. .如果改用尾指针如果改用尾指针rearrear来表示单循环链表，则查来表示单循环链表，则查找开始结点找开始结点a a1 1和终端结点和终端结点a an n都很方便，它们的存储位都很方便，它们的存储位置分别是置分别是(rear(rearnext) nextnext) next和和rearrear，显然，查找，显然，查找时间都是时间都是O(1)O(1)。因此，实际中多采用尾指针表示单循。因此，实际中多采用尾指针表示单循环链表。环链表。 由于循环链表中没有由于循环链表中没有NULLNULL指针，故涉及遍历操作指针，故涉及遍历

54、操作时，其终止条件就不再像非循环链表那样判断时，其终止条件就不再像非循环链表那样判断p p或或ppnextnext是否为空，而是判断它们是否等于某一指定指是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等针，如头指什或尾指针等. .60/95算法举例算法举例 单链表的合并单链表的合并 LinkedList Union(LinkedList la，LinkedList lb) 将非递减有序的单链表将非递减有序的单链表la和和lb合并成新的合并成新的 非递减有序单链表非递减有序单链表lc，并要求利用原表空间，并要求利用原表空间 lc=(LNode*)malloc(sizeof(LNod

55、e); 申请结点申请结点 lc-next=NULL; 初始化链表初始化链表lc pa=la-next; pa是链表是链表la的工作指针的工作指针 pb=lb-next; pb是链表是链表lb的工作指针的工作指针 pc=lc; pc是链表是链表lc的工作指针的工作指针 while(pa & pb) la和和lb均非空均非空 if(pa-datadata) la中元素插入中元素插入lc pc-next=pa; pc=pa; pa=pa-next; 61/95 （接上页）（接上页） else lb中元素插入中元素插入lc pc-next=pb; pc=pb; pb=pb-next; if(pa) p

56、c-next=pa; 若若pa未到尾，将未到尾，将pc指向指向pa else pc-next=pb; 若若pb未到尾，将未到尾，将pc指向指向pbreturn(lc); Union 62/95自测题自测题 2 2 若线性表最常用的操作是存取第若线性表最常用的操作是存取第I I个元素及其前驱个元素及其前驱和后继元素的值，为节省时间应采用的存储方式和后继元素的值，为节省时间应采用的存储方式( )( )。 A.A.单链表单链表 B.B.双向链表双向链表 C.C.单循环链表单循环链表 D.D.顺序表顺序表【北京理工大学北京理工大学20042004一一.3(1.3(1分分) )】63/952.3.3 双

57、向循环链表双向循环链表Doubly Linked Circular Lists Dont we have enough headache already?Why do we need the doubly linked lists? Suppose you have a list 1-2-3-m.Now how would youget the m-th node? Ill go from the 1st nodeto the m-th node. Then you are asked to find its previous node m 1? Uhhh . Then Ill have to

58、 go from the 1st node again.But hey, why do I wantta find the previous node? Why do you ask me? :-)Maybe you wantta deletethe m-th node?typedef struct node *node_ptr ;typedef struct node node_ptr llink; element item; node_ptr rlink; ;item llinkrlinkptr = ptr-llink-rlink = ptr-rlink-llinkA doubly lin

59、ked circular list with head node:item1 item2 item3 HAn empty list : H7/1864/95 双向链表双向链表( (Doubly Linked Lists)Doubly Linked Lists): :在单链表的每在单链表的每个结点里再增加一个指向其直接前趋的指针域个结点里再增加一个指向其直接前趋的指针域priorprior。这样就形成的链表中有两个方向不同的链，故称为双这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：向链表。形式描述为： typedef struct dlistnode datatype dat

60、a; struct dlistnode *prior，*next; dlistnode; typedef dlistnode * dlinklist; dlinklist head;65/95 和单链表类似，双链表一般也是由头指针唯和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。成循环链表，并称之为双向链表。 设指针设指针p p指向某一结点，则双向链表结构的对指向某一结点，则双向链表结构的对称性可用下式描述：