第二章线性表A

1、第第2 2章章 线性表线性表1第第2章章 线性表线性表 2.1 线性表的基本概念线性表的基本概念 2.2 线性表的顺序存储线性表的顺序存储 2.3 线性表的链式存储结构线性表的链式存储结构 2.4 一元多项式的表示及相加一元多项式的表示及相加第第2 2章章 线性表线性表2 从本章开始到第四章讨论的线性表、栈、队列从本章开始到第四章讨论的线性表、栈、队列和串的逻辑结构都属于线性结构。在线性结构中，和串的逻辑结构都属于线性结构。在线性结构中，元素之间存在一个对一个的相互关系，其逻辑特征元素之间存在一个对一个的相互关系，其逻辑特征为：在数据元素的为：在数据元素的非空有限非空有限集中：集中： （1）存

2、在唯一的一个被称为）存在唯一的一个被称为“起始起始”的数据元的数据元素。素。 （2）存在唯一的一个被称为）存在唯一的一个被称为“终端终端”的元素。的元素。 2.1 线性表的类型定义线性表的类型定义第第2 2章章 线性表线性表3 （3）除起始元素外，其它每个元素有且仅有一个）除起始元素外，其它每个元素有且仅有一个直接前趋。直接前趋。 （4）除终端元素之外，其它每个元素有且仅有一）除终端元素之外，其它每个元素有且仅有一个直接后继。个直接后继。 本章的基本内容：线性表的逻辑结构定义和各本章的基本内容：线性表的逻辑结构定义和各种存储结构、描述方法及其建立在这两种存储结构种存储结构、描述方法及其建立在这

3、两种存储结构上的运算实现。上的运算实现。第第2 2章章 线性表线性表42.1.1 线性表的逻辑结构线性表的逻辑结构 在实际应用中，线性表是最常用而且最简单的一种数据在实际应用中，线性表是最常用而且最简单的一种数据结构。结构。 线性表定义：线性表是由线性表定义：线性表是由n个数据元素组成的有限序列，个数据元素组成的有限序列，其中，其中，n即数据元素的个数，定义为线性表的长度，当即数据元素的个数，定义为线性表的长度，当n为为零时称为空表，一般将零时称为空表，一般将n0时的线性表记为：时的线性表记为： 其中，其中， 是第一个数据元素，又称为起始结点，是第一个数据元素，又称为起始结点， 是是最后一个数

4、据元素，又称为终端结点。最后一个数据元素，又称为终端结点。12(,)ina aaa1ana第第2 2章章 线性表线性表5 当当i=1，2，n-1时，时， 有且仅有一个直接有且仅有一个直接后继后继 ；当；当i =2，3，n 时，时， 有且仅有有且仅有一个直接前趋一个直接前趋 。注意这里。注意这里 （1 i n）仅仅是一个抽象的符号，其具体含义，在不同的情仅仅是一个抽象的符号，其具体含义，在不同的情况下各不相同，它可以是一个数，一条记录或一个况下各不相同，它可以是一个数，一条记录或一个符号，甚至是更复杂的信息。例如，英文字母表符号，甚至是更复杂的信息。例如，英文字母表(A，B，Z)是一个线性表，职

5、工工资表等。是一个线性表，职工工资表等。 线性表的结点之间的逻辑关系符合线性结构线性表的结点之间的逻辑关系符合线性结构的逻辑特征，是一种线性结构。的逻辑特征，是一种线性结构。 ia1iaia1iaia第第2 2章章 线性表线性表6线性表的特点：线性表的特点：(1)同一线性表中的元素必定具有相同特性；同一线性表中的元素必定具有相同特性；(2) 相邻数据元素之间存在着序偶关系；相邻数据元素之间存在着序偶关系；(3) 线性表中元素个数线性表中元素个数n(n=0)为线性表的长度为线性表的长度,当当n=0时称为空表；时称为空表；(4)在非空线性表中，每个数据元素都有一个确定的位在非空线性表中，每个数据元

6、素都有一个确定的位置；置；(5)线性表的长度可以根据需要增长或缩短。线性表的长度可以根据需要增长或缩短。第第2 2章章 线性表线性表7抽象数据类型线性表的定义格式抽象数据类型线性表的定义格式ADT list 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作： 以下是一些常用操作，以函数方式出现以下是一些常用操作，以函数方式出现 ADT list0,.,2 , 1,| nniElemSetaaDii,.,2 , 1,|,111niDaaaaRiiii ElemSet 是某个确定的、将由用户自行定是某个确定的、将由用户自行定义的、含某个关系运算的数据对象义的、含某个关系运算的数据对象第第

7、2 2章章 线性表线性表8 常见的线性表的基本运算：常见的线性表的基本运算： （1）置空表）置空表ClearList(L)：将线性表：将线性表L置成空表。置成空表。 （2）求长度）求长度ListLenght(L)：求给定线性表：求给定线性表L中数中数据元素的个数。据元素的个数。 （3）取元素）取元素GetElem(L,i,&e)：用：用e返回线性表返回线性表L中中的第的第i个数据元素。个数据元素。 （4）插入）插入ListInsert(&L,i, e)：在线性表：在线性表L中第中第i个个位置之前插入新的元素位置之前插入新的元素e,L的长度加的长度加1。 2.1.2 线性表的运算线性表的运算第第

8、2 2章章 线性表线性表9 （5）删除）删除ListDelete (&L,i,&e)：删除：删除L中第中第i个元素，个元素，并用并用e返回其值，返回其值，L的长度减的长度减1。 （6）判定）判定ListEmpty(L)：若：若L为空表，则返回为空表，则返回true,否则返回否则返回false。 利用基本运算可以实现线性表的其它复杂运算。利用基本运算可以实现线性表的其它复杂运算。 需要指出的是，这里给出的只是定义在逻辑结构上需要指出的是，这里给出的只是定义在逻辑结构上的抽象运算，即只关心这些运算是的抽象运算，即只关心这些运算是“做什么做什么”的，至的，至于于“怎样实现怎样实现”则依赖于所选定的存

9、储结构。则依赖于所选定的存储结构。第第2 2章章 线性表线性表102.2 线性表的顺序表示和实现线性表的顺序表示和实现 顺序表是线性表的顺序存储结构，即按顺序存储顺序表是线性表的顺序存储结构，即按顺序存储方式构成的线性表的存储结构。其存储方式是：线性方式构成的线性表的存储结构。其存储方式是：线性表的第一个元素存放在个一片连续的存储空间开始位表的第一个元素存放在个一片连续的存储空间开始位置处，第二个元素紧跟着存放在第一元素之后置处，第二个元素紧跟着存放在第一元素之后，以，以此类推。此类推。 利用顺序表来存储线性表，可借助数据元素在计利用顺序表来存储线性表，可借助数据元素在计算机内的物理位置相邻特

10、性来表示线性表中数据元素算机内的物理位置相邻特性来表示线性表中数据元素之间的线性逻辑关系。之间的线性逻辑关系。 线性表中第线性表中第 i 个数据元素个数据元素 的存储位置计算公的存储位置计算公式为：式为： L 是每个元素占用的存储单元是每个元素占用的存储单元 liaLOCaLOCi) 1()()(1ia第第2 2章章 线性表线性表11 这样，一旦起始地址这样，一旦起始地址LOC（a1）（图）（图2.2中设为中设为b）和一个数据元素占用的存储单元的大小（和一个数据元素占用的存储单元的大小（L值）确定值）确定下来，就可求出任一个数据元素的存储地址，显然，下来，就可求出任一个数据元素的存储地址，显然

11、，这种表便于进行随机访问，因此，顺序表是一种随机这种表便于进行随机访问，因此，顺序表是一种随机存取的结构。存取的结构。第第2 2章章 线性表线性表12第第2 2章章 线性表线性表13 在具体实现时，可利用高级程序设计语言中的在具体实现时，可利用高级程序设计语言中的一维数组即向量来为线性表的顺序存储开辟存储空一维数组即向量来为线性表的顺序存储开辟存储空间，存储空间大小应大于等于线性表长度，用一个间，存储空间大小应大于等于线性表长度，用一个整型变量来表示线性表的长度，从而可将顺序表描整型变量来表示线性表的长度，从而可将顺序表描述为：述为： # define List_INIT 100 typede

12、f int elemtype ； /* elemtype表示元素类型，表示元素类型，此处设为此处设为 int */ typedef struct elemtype vecList_INIT； int lenght； sequenlist ； 第第2 2章章 线性表线性表14 在上面描述中，顺序表是一个结构体类型。其在上面描述中，顺序表是一个结构体类型。其中，中，vec成员（又称为数据域）指线性表数据元素成员（又称为数据域）指线性表数据元素所占用的存储空间，而所占用的存储空间，而lenght成员（又称为长度域）成员（又称为长度域）则用于存储线性表长度，它表示线性表最后一个元则用于存储线性表长度，

13、它表示线性表最后一个元素在向量中的位置，素在向量中的位置，elemtype 则为线性表中数据元则为线性表中数据元素类型。素类型。第第2 2章章 线性表线性表15 本节讨论在定义线性表顺序存储结构之后，本节讨论在定义线性表顺序存储结构之后，如何在这种结构上实现有关数据运算。下面重点如何在这种结构上实现有关数据运算。下面重点讨论线性表的顺序表的建立、数据元素的插入和讨论线性表的顺序表的建立、数据元素的插入和删除运算。删除运算。 2.2.2 顺序表上的基本运算顺序表上的基本运算第第2 2章章 线性表线性表163. 顺序表的常用算法顺序表的常用算法算法算法1 顺序表的建立顺序表的建立 (P23 算法算

14、法2.3)输入输入n个整数，产生一个存储这些整数的顺序表个整数，产生一个存储这些整数的顺序表A的函数如下：的函数如下：void create(A,n)vector A; int n; int i;for (i=1;iAi;/* scanf(“%d”,Ai); */typedef int vector m 定义了一个新的类型，顺序表中定义了一个新的类型，顺序表中n小于或等于小于或等于mmain() vector B; int j,n; cinn;create(B,n);for (j=1;j=n;j+) coutBj;/*Printf(“%d”,Bj ); */第第2 2章章 线性表线性表172插

15、入运算插入运算 线性表的插入运算是指在表的第线性表的插入运算是指在表的第i个元个元素之前插入一个新的数据元素，插入的结素之前插入一个新的数据元素，插入的结果使得线性表的长度由果使得线性表的长度由n变为变为n+1，线性表，线性表的数据元素间的逻辑关系发生了变化，使的数据元素间的逻辑关系发生了变化，使得物理存储顺序也发生相应的变化。插入得物理存储顺序也发生相应的变化。插入过程如图过程如图2.3所示。所示。第第2 2章章 线性表线性表18121321242830427712345678插入插入25121321242528304277123456789插入后插入后(a)(b)第第2 2章章 线性表线性

16、表19算法算法2 顺序表的插入顺序表的插入 （如图（如图2.3）121321242830427712345678插入插入25 在一个有在一个有n个元素的顺序表个元素的顺序表A中的第中的第i个元素之个元素之前插入一个元素前插入一个元素x的函数如下：的函数如下： void insert(A,n,x) vector A; int n,x; int i,j; scanf(“%d”,&i); /*确定插入位置确定插入位置*/ if(in) print(“i值错误！值错误！n”); else for (j=n;j=i;j-) Aj+1=Aj; Ai=x; n+; 第第2 2章章 线性表线性表20int I

17、nsert(Elemtype List ,int *num,int i,Elemtype x)/*在顺序表在顺序表List 中，中，*num为表尾元素下标位置，在第为表尾元素下标位置，在第i个元素前插入数据元素个元素前插入数据元素x，若成功，返回，若成功，返回TRUE，否则返回，否则返回FALSE。*/int j; if (i*num+1) printf(“Error!”); /*插入位置出错插入位置出错*/ return FALSE; if (*num=MAXNUM-1) printf(“overflow!”); return FALSE; /*表已满表已满*/for (j=*num;j=i

18、;j-)Listj+1=Listj; /*数据元素后移数据元素后移*/Listi=x; /*插入插入x*/(*num)+; /*长度加长度加1*/return TRUE; P24【算法算法2.4 顺序表的插入顺序表的插入】第第2 2章章 线性表线性表21 在本算法中是从最后一个元素开始后移，直到第在本算法中是从最后一个元素开始后移，直到第i个元素为止。该算法时个元素为止。该算法时间主要花费在间主要花费在for循环语句上，执行的次数为循环语句上，执行的次数为n-i+1。当。当i=1时，全部元素均参时，全部元素均参加移动，共需要移动加移动，共需要移动n次；当次；当i = n+1时，不需移动元素。时

19、，不需移动元素。 算法在最坏情况下，时间复杂度为算法在最坏情况下，时间复杂度为O(n)，最好情况下时间复杂度为，最好情况下时间复杂度为O(1)。显然，元素移动的次数直接影响了算法执行时间，平均移动次数。显然，元素移动的次数直接影响了算法执行时间，平均移动次数。 假设假设pi为在第为在第i个元素之前插入一个元素的概率，且为等概率，则平均移个元素之前插入一个元素的概率，且为等概率，则平均移动次数的期望值为：动次数的期望值为： 其中，当其中，当1in+1时，时，p1=p2= =pn+1 = 可见，在顺序存储的线性表中插入一个元素，约平均移动线性表中一半可见，在顺序存储的线性表中插入一个元素，约平均移

20、动线性表中一半的元素，显然，当的元素，显然，当n较大时，算法效率较低，算法的平均时间复杂度为较大时，算法效率较低，算法的平均时间复杂度为O(n)。11112)1(11)1(niniiisninninpE11n第第2 2章章 线性表线性表22 在本算法中是从最后一个元素开始后移，直到第在本算法中是从最后一个元素开始后移，直到第i个元素个元素为止。该算法时间主要花费在为止。该算法时间主要花费在for循环语句上，执行的次数循环语句上，执行的次数为为n-i+1。当。当i=1时，全部元素均参加移动，共需要移动时，全部元素均参加移动，共需要移动n次；次；当当i = n+1时，不需移动元素。时，不需移动元素

21、。 算法在最坏情况下，时间复杂度为算法在最坏情况下，时间复杂度为O(n)，最好情况下时，最好情况下时间复杂度为间复杂度为O(1)。显然，元素移动的次数直接影响了算法执。显然，元素移动的次数直接影响了算法执行时间，平均移动次数。行时间，平均移动次数。 假设假设pi为在第为在第i个元素之前插入一个元素的概率，且为等个元素之前插入一个元素的概率，且为等概率，则平均移动次数的期望值为：概率，则平均移动次数的期望值为： 其中，当其中，当1in+1时，时，p1=p2= =pn+1 = 11112)1(11)1(niniiisninninpE11n第第2 2章章 线性表线性表23 可见，在顺序存储的线性表中

22、插入一可见，在顺序存储的线性表中插入一个元素，约平均移动线性表中一半的元素，个元素，约平均移动线性表中一半的元素，显然，当显然，当n较大时，算法效率较低，算法的较大时，算法效率较低，算法的平均时间复杂度为平均时间复杂度为O(n)。 第第2 2章章 线性表线性表243删除运算删除运算 删除运算是指将线性表中的第删除运算是指将线性表中的第i个元素删除，个元素删除，使线性表的长度由使线性表的长度由n变成变成n-1，由：，由： (a1，a2，ai-1，ai，ai+1，an)变成为：变成为： (a1，a2，ai-1，ai+1，an) 其中，其中， 1in。 线性表进行删除元素后，仍是一个线性表。删线性表

23、进行删除元素后，仍是一个线性表。删除过程如图除过程如图2.4所示。所示。第第2 2章章 线性表线性表25算法算法3 顺序表的删除顺序表的删除 （如图（如图2.4）具体算法如下：具体算法如下： void delete(L，i) sequenlist *L； int i； int j； if (i(*L).len+1) printf(“delete fail！n”)； /*删除位置不正确删除位置不正确*/ else *y =(*L).veci-1；/*y为一外部变量，用于接收被删除的元素为一外部变量，用于接收被删除的元素*/ for(j= i；j=(*L).len；j +) (*L).vecj-1

24、=(*L).vecj； /*元素前移元素前移*/ (*L).Len-； /*修改表长修改表长*/ /*delete*/ 第第2 2章章 线性表线性表26 与插入算法相似，要删除一个元素需向前移动元素，与插入算法相似，要删除一个元素需向前移动元素，删除第删除第i个元素时，将第个元素时，将第i+1，i+2，n个元素依次前移，个元素依次前移，其移动次数为其移动次数为n-i，假设删除线性表中的任一位置上元素的，假设删除线性表中的任一位置上元素的概率相等（等于概率相等（等于1/n），则删除运算所需的移动元素的平均），则删除运算所需的移动元素的平均移动次数如下所示。移动次数如下所示。 由此可见，对线性表删

25、除一个元素时，约需有一半的由此可见，对线性表删除一个元素时，约需有一半的元素参加移动。元素参加移动。21)()(1111nininnEninnids第第2 2章章 线性表线性表27 显然，该算法的时间复杂度为显然，该算法的时间复杂度为(n)。 通过以上讨论可以发现，当表长较大时，对通过以上讨论可以发现，当表长较大时，对顺序存储结构进行插入和删除运算，由于要移动顺序存储结构进行插入和删除运算，由于要移动元素，运算效率低，但这种存储结构对于随机存元素，运算效率低，但这种存储结构对于随机存取元素却十分方便。取元素却十分方便。第第2 2章章 线性表线性表28 例如，一个线性表中可能含有重复的元素（值相

26、同），现例如，一个线性表中可能含有重复的元素（值相同），现要求删除重复元素中的多余元素，只保留其中位序最小的一个。要求删除重复元素中的多余元素，只保留其中位序最小的一个。如线性表（如线性表（5，2，2，3，5，2），经过清除重复元素后变为），经过清除重复元素后变为( 5，2，3 )。 假定线性表以顺序存储方式存储，则其算法可描述如下：假定线性表以顺序存储方式存储，则其算法可描述如下： void purge(sequenlist *L ) int i=0，j ，k； while ( i=(*L).Len-1) j = i+1； while ( j=(*L).Len-1) if (*L).veci

27、= =(*L).vecj) for ( k =j；k=(*L). Len-1；k +) (*L) .vec k 1 = (*L) .vec k ；/ *元素前移元素前移*/ (*L ) .Len- -；/*修改表长度修改表长度*/ else j + +； i + +； /* purge */第第2 2章章 线性表线性表29算法算法4 顺序表的查找顺序表的查找(P26 算法算法2.6)在一个有在一个有n个元素线性表个元素线性表A中查找值为中查找值为x的元素的函数如下：的元素的函数如下： void find(A ,n,x) int n.x; int j; i=1; while (i=n & Ai

28、!=x ) i+; if (i=n) printf(“找到了！找到了！ n”); else printf (“没找到没找到n”);第第2 2章章 线性表线性表30算法算法5:顺序表的合并顺序表的合并(P26 算法算法2.7) 有两个顺序表有两个顺序表A(有有m个元素个元素)和和B(有有n个元素个元素),其其元素均以从小到大的升序排列元素均以从小到大的升序排列,编写一个函数将它们编写一个函数将它们合并成一个顺序表合并成一个顺序表C,要求要求C的元素也是从小到大的升的元素也是从小到大的升序排列序排列. 解解:本题的解法思想是本题的解法思想是:依次扫描依次扫描A和和B的元素的元素,比较比较当前的元素

29、的值当前的元素的值,将较小值的元素赋给将较小值的元素赋给C,如此直到一个如此直到一个表扫描完毕表扫描完毕,然后将未完的一个表余下所有元素赋给然后将未完的一个表余下所有元素赋给C即可即可.第第2 2章章 线性表线性表31Void link(int A ,int B ;int m,n;int C ) int i=1,j=1,k=1,s; while (i=m & j=n) /*扫描扫描A和和B,将当前的较小元素赋给将当前的较小元素赋给C */ if AiBj) Ck=AI; i+; k+; else Ck=B j; j+; k+; if(j=n) /*当当A未完时未完时,将将A余下的元素赋给余下的

30、元素赋给C */ for(s=i+1;s=m;s+) Ck=As;k+; if (i=m) /*当当B未完时未完时,将将B余下元素赋给余下元素赋给C*/ for (s=j+1;sdata=x; p-next=s; p=s; /*把把s结点链接到前面建立的单链表中结点链接到前面建立的单链表中*/else cycle=0; head=head-next; /*删除头结点删除头结点*/ p-next=NULL;如果输入的整数序列是：如果输入的整数序列是： 6 10 3 6 7 5 0 第第2 2章章 线性表线性表43 linklist * creatlist ( ) /* 函数返回一个指向单链表表头

31、的指针函数返回一个指向单链表表头的指针 */ char ch；int x ； linklist *head ， *r ， *p ； p =（linklist *）malloc（sizeof（linklist）；）； head = p ； p-next =NULL； /* 生成头结点生成头结点*/ r = p ； /*建立单链表表尾指针建立单链表表尾指针 */ ch = getchar ( ) ； /*ch为建立与否标志为建立与否标志 */ while ( ch ! = ? ) /*? 为输入结束标志符为输入结束标志符 */ scanf ( “ % d ” , &x ) ； /*读入新数据元素读

32、入新数据元素*/ p =（linklist *）malloc (sizeof (linklist )； p-data = x ; p -next = NULL； /*生成新结点生成新结点*/ r-next = p ； /*连接新结点连接新结点 */ r = r-next ； /*修改尾指针修改尾指针 */ ch = getchar ( ) ； /*读入建立与否的标志读入建立与否的标志*/ return ( head ) ； /*返回表头指针返回表头指针head */ /* creatlist */（2）建立带头结点的单链表）建立带头结点的单链表第第2 2章章 线性表线性表44（3）建立不带头结

33、点的单链表）建立不带头结点的单链表 linklist * creatlist ( ) /*函数返回一个指向链表表头的指针函数返回一个指向链表表头的指针*/ char ch；int x ；linklist *head ， *p， *r head =NULL ；r =NULL ； /*设立尾指针设立尾指针r，其初值为空，其初值为空 */ ch = getchar ( )； /*读入建立与否标志读入建立与否标志 */ while ( ch != ? ) /* ? 为输入结束标志符为输入结束标志符 */ p=(linklist *)malloc(sizeof(linklist)； /*申请新结点空间申

34、请新结点空间 */ scanf ( “ % d ”，&x ) ； p-data = x ; if (head = = NULL) head = p； else r-next = p； /*非空表，则新结点非空表，则新结点*p插入到插入到*r之后之后 */ r = p ； /*尾指针移动，指向新的表尾尾指针移动，指向新的表尾 */ ch = getchar ( )； /* 读入建立与否的标志读入建立与否的标志 */ if ( r! = NULL ) r-next = NULL； return head ； /*返回表头指针返回表头指针head */ /* creatlist */ 在算法中引入头

35、结点可以不必区分空表与非空表，可以在算法中引入头结点可以不必区分空表与非空表，可以统一空链表与非空链表的处理。统一空链表与非空链表的处理。 上述两个算法的时间复杂上述两个算法的时间复杂度都为度都为O(n)。第第2 2章章 线性表线性表45 插入结点的指针变化图插入结点的指针变化图2.9所示。指针的修改操所示。指针的修改操作为：作为： s-next=p-next； p-next=s； 上述指针进行相互赋值的语句顺序不能颠倒，上述指针进行相互赋值的语句顺序不能颠倒，若若次序变化为：次序变化为： p-next=s； s-next=p-next；则会导致错误。；则会导致错误。 同样，要删除单链表结点同

36、样，要删除单链表结点*p的后继结点也很简单的后继结点也很简单，只要用一个指针指向被删除结点，修改，只要用一个指针指向被删除结点，修改*p的指针的指针域，最后释放结点域，最后释放结点*p即可，如图即可，如图2.10所示。所示。删除一个删除一个结点结点* p的后继结点的指针操作为：的后继结点的指针操作为： p-next = p-next -next ； 不难发现，不难发现，在单链表存储结构中进行元素的插在单链表存储结构中进行元素的插入和删除时，只需要修改有关的指针内容，而不需入和删除时，只需要修改有关的指针内容，而不需要移动元素。要移动元素。 2单链表上元素的插入和删除运算单链表上元素的插入和删除

37、运算第第2 2章章 线性表线性表46第第2 2章章 线性表线性表47 （a） insert (linklist *p ,elemtype x) /*将值为将值为x的新结点插入的新结点插入*p之后之后 */ linklist *s； s =（linklist *）malloc ( sizeof( linklist) ； /* 生成生成x的新结点的新结点*s */ s-data=x； s-next=p-next ； /*新结点链入单链表新结点链入单链表 */ p-next=s； /*insert*/（1） 插入算法插入算法第第2 2章章 线性表线性表48 （b） void insert (link

38、list *head,elemtype k,elemtype x) /*在单链表中值为在单链表中值为k的结点之前插入一个值为的结点之前插入一个值为x的新结点的新结点*/ linklist *q， *p， *r； r =(linklist *)malloc( sizeof( linklist)； / *生成新结点生成新结点 */ r-data = x； if ( head-next = =NULL) head-next = r ； r-next = NULL ； else q = head-next ； p = head-next-next ； while ( p ! = NULL ) if (

39、 p-data ! = k ) */ q = p； p = p-next ； else break ； 第第2 2章章 线性表线性表49 if ( p ! = NULL ) q -next = r ； r-next = p； else /*在链表表尾处插入新结点在链表表尾处插入新结点 */ q -next = r； r-next =NULL； /* insert */ 该算法的时间主要耗费在查找值为该算法的时间主要耗费在查找值为k的结点位置上，算法时间复杂的结点位置上，算法时间复杂度为度为O(n) 。第第2 2章章 线性表线性表50 算法算法2.9 单链表的插入（单链表的插入（ C语言函数）语

40、言函数） 在单链表中第在单链表中第i个结点（个结点（i=0)之后插入一个元素为之后插入一个元素为x的结点。的结点。 void inser(head,i) node *head; int i,x; node *s,*p; int j; s=(node *) malloc(sizeof(node); /*建立一个待插入的结点建立一个待插入的结点s*/ scanf(“%s”,&x); s-data=x; if (i=0) /*如果如果i=0，则将，则将s所指所指结点插入到表头后返回结点插入到表头后返回*/ s-next=head; head=s; else p=head; j=i; /*在单链表中查

41、找第在单链表中查找第i 个结点，由个结点，由p指向指向*/ while (p!=NULL & jnext; if(p!=NULL) /*若找查成功若找查成功,则把则把s插入到其后插入到其后*/ s-next=p-next; p-next=s; else printf(“未找到！未找到！n”); 第第2 2章章 线性表线性表51（a） delete (linklist *p ) /*删除删除*p结点的后继结点结点的后继结点*/ linklist *r； r = p-next ； if(r!=NULL) p-next = r-next； free (r)； /*delete*/（b）linklis

42、t *delete(linklist *head，int i) /*删除单链表删除单链表head的第的第i个结点个结点*/ int j = 0 ； linklist *p，*s，*q； p = head ；j = 0 ； while ( p-next != NULL)& (jnext ； j + ； （2）删除算法）删除算法第第2 2章章 线性表线性表52 if ( p-next!=NULL ) q = p-next ； p-next = p-next-next ； free (q) ； else return NULL ； s = head ； return s ； /* delete */

43、 该算法时间复杂度为该算法时间复杂度为O(n) 。第第2 2章章 线性表线性表53一般情况下，可以按某个元素的序号或按某给定值两种方法一般情况下，可以按某个元素的序号或按某给定值两种方法检索。检索。 （1）按值检索）按值检索 按值检索，即是检索单链表中是否存在值为给定值按值检索，即是检索单链表中是否存在值为给定值k的结的结点，整个过程可以通过结点的值和给定值的比较而实现。点，整个过程可以通过结点的值和给定值的比较而实现。 linklist *locate（ linklist *head ， elemtype k ） linklist *s； s= head-next ； /*从第一个结点起开始

44、比较从第一个结点起开始比较*/ while ( s!= NULL ) /*扫描整个链表扫描整个链表*/ if ( s-data != k) s = s-next ； else break ； return s； /*返回结点的位置或返回结点的位置或NULL*/ /*Locate*/ 算法时间复杂度为算法时间复杂度为O(n)。 3.单链表上元素的检索单链表上元素的检索第第2 2章章 线性表线性表54 即利用被访问结点的序号而检索或查找结点的过程。即利用被访问结点的序号而检索或查找结点的过程。 linklist *get(linklist *head，int i) int j； linklist

45、*p ； p = head ；j = 0； while ( (p-next != NULL )&( i j ) p = p-next； j + ； if (i= =j) return p； else return NULL ； /*get */ 该算法中最坏情况下的时间复杂度为该算法中最坏情况下的时间复杂度为O(n)。（2） 按序号检索按序号检索第第2 2章章 线性表线性表55 例，将两个递增的单链表合并为一个递增单链表，且要例，将两个递增的单链表合并为一个递增单链表，且要求不重新开辟空间，其算法可描述如下：求不重新开辟空间，其算法可描述如下： void *union (linklist *h

46、eada，linklist *headb ) /*合并单链表合并单链表heada与与headb */ linklist *p，*q，*r，*u ； p = heada-next ； q = headb-next ； r = heada ； while ( p ! = NULL )& (q ! = NULL ) if ( p-data q-data ； u = q-next ； r-next = q ； r = q ； q-next = p ； q = u ； 第第2 2章章 线性表线性表56 else if ( p-data data ) r = p； p = p-next ； if ( q

47、! = NULL) r-next = q； /* union */第第2 2章章 线性表线性表57 1.基础知识：题集基础知识：题集2.1、2.4、2.5、2.6、2.7； 2.算法实现：写出教材算法算法实现：写出教材算法2.10单链表的删除单链表的删除 C/C+语言程序，语言程序，并上机调试通过并上机调试通过; 2. 算法设计题算法设计题: 2.15、2.16。作作 业业第第2 2章章 线性表线性表58 如果将单链表最后一个结点的指针域改为存放链表中头结如果将单链表最后一个结点的指针域改为存放链表中头结点（或第一个表结点）的地址值，就使得整个链表构成一个点（或第一个表结点）的地址值，就使得整

48、个链表构成一个环，如图环，如图2.12所示，这样的链表称为循环链表。显然，它是所示，这样的链表称为循环链表。显然，它是一种首尾相接的链表，从循环链表中任一个结点出发都可访一种首尾相接的链表，从循环链表中任一个结点出发都可访问到表中所有其它结点。对单链表的链接方式稍作一些改变问到表中所有其它结点。对单链表的链接方式稍作一些改变，就可构成一个新的存储结构，就可构成一个新的存储结构单循环链表单循环链表。同样，也有。同样，也有多重链的循环链表。在循环链表中，为了使空表和非空表的多重链的循环链表。在循环链表中，为了使空表和非空表的处理一致，同样可设置一个头结点。处理一致，同样可设置一个头结点。2.3.2

49、 循环链表循环链表第第2 2章章 线性表线性表59 循环链表的基本运算与单链表基本一致循环链表的基本运算与单链表基本一致 ，差别只在于最后，差别只在于最后一个结点的循环处理上。只要将单链表算法中出现一个结点的循环处理上。只要将单链表算法中出现NULL处改处改为头指针即可。为头指针即可。 例如，将单循环链表倒置或逆置。例如，将单循环链表倒置或逆置。 linklist *invert (head ) linklist *head； linklist *p，*q，*s; q = head； p= head-next； while ( p ! = head ) s = q ； q = p ； p =

50、p-next ； q-next = s； p-next = q； return head； /* invert */第第2 2章章 线性表线性表60 在单循环链表中，从任一个已知结点出发可以找到其前在单循环链表中，从任一个已知结点出发可以找到其前趋结点，但时间耗费需趋结点，但时间耗费需O(n )，若希望能快速确定一个结点的，若希望能快速确定一个结点的直接前趋，可以再加上一个指针域存储其直接前趋的信息，直接前趋，可以再加上一个指针域存储其直接前趋的信息，这样就可以构成双向链表，它有两个方向不同的链这样就可以构成双向链表，它有两个方向不同的链 ，如果将，如果将每个方向的链表构成一个环，则可以构成每

51、个方向的链表构成一个环，则可以构成双向循环链表双向循环链表。 双向链表的双向链表的C语言描述：语言描述： typedef struct dupnode elemtype data ； struct dupnode *next，*prior ； dulinklist ； dulinklist *head ; 双向循环链表也可由头指针双向循环链表也可由头指针head唯一确定，同样可增加唯一确定，同样可增加头结点，使得双链表的某些运算简便一些，如图头结点，使得双链表的某些运算简便一些，如图2.14所示。所示。2.3.3 双向链表双向链表第第2 2章章 线性表线性表61第第2 2章章 线性表线性表62

52、 由于双向链表在其结构中，每个结点既有指向其直接前由于双向链表在其结构中，每个结点既有指向其直接前趋的指针域，又有指向其直接后继的指针域，因此比起单趋的指针域，又有指向其直接后继的指针域，因此比起单链表来，要在一个双向链表中检索某一个已知结点的直接链表来，要在一个双向链表中检索某一个已知结点的直接前趋和后继结点要方便得多。前趋和后继结点要方便得多。 结点结点*p可通过多种方式访问，设指针可通过多种方式访问，设指针p指向双向链表中指向双向链表中某个结点，则有：某个结点，则有：p-next-prior = p = p-prior-next 双向链表中结点的插入情况如图双向链表中结点的插入情况如图2

53、.16所示。所示。 第第2 2章章 线性表线性表63 在在*p结点之前插入结点结点之前插入结点*s的正确步骤应为：的正确步骤应为： p-prior-next = s； s-prior = p-prior； s-next = p ； p-prior = s ； 由于双向链表中每个结点涉及两个指针的运算，对于某些由于双向链表中每个结点涉及两个指针的运算，对于某些运算要注意运算顺序。运算要注意运算顺序。 在上面的步骤中指针在上面的步骤中指针p-prior的修改必的修改必须在须在 *p结点的前趋结点结点的前趋结点 *(p-prior)的后继指针修改之后方可改的后继指针修改之后方可改动，否则会不能正确地

54、插入结点。动，否则会不能正确地插入结点。 在双向链表中删除一个结点在双向链表中删除一个结点*p的指针变化如图的指针变化如图2.15所示。所示。指指针修改的运算步骤为：针修改的运算步骤为： p-prior-next= p-next； p-next-prior =p-prior；第第2 2章章 线性表线性表64 void indulist (dulinklist *head ,int i, elemtype x)/*在双向循环链表在双向循环链表head中的第中的第i个结点之前插入值为个结点之前插入值为x的新结点的新结点 */ dulinklist *p，*s ;int j ; p = head ; j = 0 ; while ( p-next! = head)&(j next ; j+ ; if ( i 0)&(j= =i-1) s = malloc (sizeof(dulinklist) ; s-data =