哈工大数据结构1

1、第第2章章 线性表线性表 2.1 线性表的定义与运算线性表的定义与运算非空的线性表非空的线性表 (n0) 记作：记作：（ a1,a2, ai, an）1.线性表的定义线性表的定义 线性表是由线性表是由 n (n=0)个数据元素（结点）个数据元素（结点）a1,a2, ai, an组成的有限序列。组成的有限序列。其中：其中： n为数据元素的个数，也称为表的长度。为数据元素的个数，也称为表的长度。当当n=0 时，称为空表。时，称为空表。（4） ai 是属于某个数据对象的元素，是属于某个数据对象的元素， 它可以是它可以是 一个数字、一个字母或一个记录。一个数字、一个字母或一个记录。（a1,a2, ai

2、-1, ai, ai+1, an）2. 线性表的逻辑结构线性表的逻辑结构（1）有且仅有一个开始结点）有且仅有一个开始结点a1，它没有直接前驱。，它没有直接前驱。（2）有且仅有一个终端结点）有且仅有一个终端结点an，它没有直接后继。，它没有直接后继。（3）其余的结点）其余的结点ai (1in) 都都有且仅有有且仅有一个直接一个直接 前驱前驱 ai-1 和一个直接后继和一个直接后继 ai+1 3.线性表的特性线性表的特性（3）数据元素在线性表中的位置只取决于它的序号。）数据元素在线性表中的位置只取决于它的序号。（1）结点间的逻辑关系是线性的。）结点间的逻辑关系是线性的。（2）线性表中所有数据元素的

3、数据类型是一致的。）线性表中所有数据元素的数据类型是一致的。例：例： 26个英文字母组成的字母表个英文字母组成的字母表（A，B，C、Z）例：例： 某校从某校从1978年到年到1983年各种型号的计算机拥有量的年各种型号的计算机拥有量的 变化情况。变化情况。（6，17，28，50，92，188）姓姓 名名学学 号号性性 别别年龄年龄 健康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般刘建平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 健康健康 . . .例例2_3 学生健康情况登记表学生健康情况登记表 4.

4、线性表的运算线性表的运算（1）存取）存取（2）插入）插入（3）删除）删除（4）查找）查找（5）合并）合并（6）分解）分解（7）排序）排序（8）求线性表的长度）求线性表的长度 数据的运算是定义在逻辑结构上的。数据的运算是定义在逻辑结构上的。 具体的实现则在存储结构上进行。具体的实现则在存储结构上进行。 运算分为运算分为: 加工型加工型：改变结构的运算。：改变结构的运算。 例：初始化线性表。插入、删除某个结点。例：初始化线性表。插入、删除某个结点。 引用型引用型：不改变结构的运算。：不改变结构的运算。 例：在线性表上的查找运算。例：在线性表上的查找运算。2.2 线性表的顺序表示和实现线性表的顺序表

5、示和实现 1. 顺序表的定义顺序表的定义 用一组连续的存储单元（地址连续）依次存放线性表用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。的各个数据元素。 即：在顺序表中逻辑结构上相邻的数据元素，其物理即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。位置也是相邻的。 2. 顺序表中数据元素的存储地址顺序表中数据元素的存储地址a1a2.ai.an线性表的顺序存储示意图线性表的顺序存储示意图数组的下标last 存储地址data01i-1n-1loc(a 1)=BB+dB+(i-1)*dB+(n-1)*dMAXLEN-1 只要知道顺序表基地址和每个数据元素所占字节数，即可只

6、要知道顺序表基地址和每个数据元素所占字节数，即可求出第求出第 i 个数据元素的存储地址。个数据元素的存储地址。 所以顺序表具有所以顺序表具有按数据元素序号按数据元素序号随机存取的特点。随机存取的特点。 若每个数据元素占用若每个数据元素占用 d 个字节，则第个字节，则第 i 个数据元素的存储地个数据元素的存储地址为：址为： loc( ai ) = loc( a1 ) + (i-1)*d (1=i=n) = B + (i-1)*d 其中：其中：loc(a1)为第为第 1 个数据元素的存储地址，称为基地址。个数据元素的存储地址，称为基地址。 3. 顺序表的描述（静态）顺序表的描述（静态） 在在C语言

7、中，一维数组在内存中占用一组连续的存储区域。语言中，一维数组在内存中占用一组连续的存储区域。可用一维数组来表示顺序表的数据存储。可用一维数组来表示顺序表的数据存储。typedef int datatype;datatype dataMAXLEN;int last; 线性表的数据元素线性表的数据元素 a1,a2, ai, an 可依次存入数组元素可依次存入数组元素data0, data1, datai-1.,datan-1中。中。 其中：其中： MAXLEN 是一个根据实际问题定义的足够大的整是一个根据实际问题定义的足够大的整数。数。 变量变量 last 用来记录当前线性表中最后一个元素用来记录

8、当前线性表中最后一个元素在数组中在数组中的位置的位置，起到了指针的作用，始终，起到了指针的作用，始终指向线性表中的最后一个指向线性表中的最后一个元素元素。 数据元素分别存放在数据元素分别存放在data0到到datalast中中 从从datalast+1 到到dataMAXLEN-1为空闲区为空闲区 表长为表长为last+1，即为，即为 n 当当last0时，表示表为空。时，表示表为空。从结构性考虑，通常将一个顺序表封装成一个结构（静态）：从结构性考虑，通常将一个顺序表封装成一个结构（静态）：typedef int datatype;typedef struct datatype dataMAX

9、LEN; int last; SeqList; / 定义定义SeqList为此种结构类型为此种结构类型Seqlist L; / 定义一个顺序表定义一个顺序表 （a1,a2,ai-1,x,ai,an） （a1,a2,ai-1,ai,an）（1）插入运算）插入运算 在线性表的第在线性表的第 i ( 1=ilast=MAXLEN-1) printf(“顺序表已满顺序表已满”); / 最后一个结点的位置是最后一个结点的位置是 MAXLEN-1 / 表明顺序表表明顺序表 已满，不能插入。已满，不能插入。 return( -1 ); if( iL-last+2 ) / i1 即即 ilast=n-1 L-

10、last+2=n-1+2=n+1 / i L-last+2 即即 i n+1 即即 i = n+2 / 检查空表及插入位置合法性检查空表及插入位置合法性 printf(“位置出错位置出错”); return( 0 ); / 以下处理以下处理 i 的有效范围的有效范围 1=ilast; j=i-1; j-) L-dataj+1=L-dataj ; / 结点依次向后移动结点依次向后移动 / 当当 i=n+1 时，时，j= L-last=n-1, i-1=n+1-1=n / 不满足不满足j=i-1 所以不做此循环即不移动结点所以不做此循环即不移动结点L-datai-1=x ; / 新元素插入新元素插

11、入 将将 x 放在原来放在原来 ai 的位置的位置 / 当当 i=n+1时，时， datai-1= datan= x / 将将 x 直接作为直接作为an+1 放在线性表的最后放在线性表的最后L-last+; / last仍指向最后的元素仍指向最后的元素 return( 1 )插入算法时间性能分析：插入算法时间性能分析： 顺序表的插入运算，时间主要消耗在数据的移动上，在第顺序表的插入运算，时间主要消耗在数据的移动上，在第 i 个位置上插入个位置上插入 x，从，从 an 到到 ai 都要向后移动一个位置，共需移都要向后移动一个位置，共需移 动动 n-i+1 个元素。个元素。 而而 i 的取值范围为

12、：的取值范围为： 1=i=n+1 即：有即：有 n+1 个位置可以插入。个位置可以插入。 设在第设在第 i 个位置上作插入的概率为个位置上作插入的概率为 pi 则平均移动结点的次数：则平均移动结点的次数：)1(11inPEniiI按等概率考虑：按等概率考虑： 可能插入的位置为可能插入的位置为 i=1,2,n,n+1 共共 n+1 个，个，则则 pi=1/(n+1) 所以：所以：1111)1(11)1(niniiIinninPE2)1(2)1)1()1111nnnnnn（得出：得出： 顺序表插入算法平均约需移动一半结点。顺序表插入算法平均约需移动一半结点。 时间复杂度为时间复杂度为O(n) （线

13、性阶）（线性阶） 。（a1,a2,ai-1,ai+1,an）（2）删除运算）删除运算 （a1,a2,ai-1,ai,ai+1,an） 将线性表的第将线性表的第 i（1=i=n)个结点删除，使得长度为个结点删除，使得长度为 n 的的线性表变为长度为线性表变为长度为 n-1 的线性表。的线性表。若若i=n，只需删除终端结点，不用移动结点。，只需删除终端结点，不用移动结点。当当1=in时，将时，将ai+1-an之间的结点依次向前移动。之间的结点依次向前移动。（共需移动（共需移动 n-i 个结点）。个结点）。修改修改 last 指针（相当于修改表长）使之仍指向最后一个指针（相当于修改表长）使之仍指向最

14、后一个结点。结点。删除算法思想：删除算法思想：删除算法：删除算法：int DelList( SeqList *L, int i ) int j; if( iL-last+1 ) / iL-last+1 即即in n为原表长为原表长 / 检查空表及删除位置合法性检查空表及删除位置合法性 printf(“不存在第不存在第 i 个结点个结点”) ; return( 0 ) ; /以下处理以下处理 i 的有效范围的有效范围 1=i=n for( j=i; jlast; j+ ) L-dataj-1=L-dataj ; / j=i ai+1 移到了移到了ai 的位置的位置 / j=L-last an 移

15、到了移到了 an-1 的位置的位置 / 当当 i=n 时，时，j=n 不满足此循环条件不满足此循环条件 L-last- ; / 当当 i=n 时，不用移动结点，表长直接减时，不用移动结点，表长直接减1 return( 1 ) ; 与插入运算相同，时间主要消耗在移动表中结点上。删除与插入运算相同，时间主要消耗在移动表中结点上。删除第第 i 个结点，其后面的结点个结点，其后面的结点 ai+1-an 都要向前移动一个位置，共都要向前移动一个位置，共移动移动 n-i 个结点。个结点。 若若 i=1, 最坏：最坏：O(n) 若若 i=n, 无需移动结点，直接删除即可。最好：无需移动结点，直接删除即可。最

16、好：O(1)i)(nPEn1iid 删除算法时间性能分析：删除算法时间性能分析：移动结点的平均次数：移动结点的平均次数：按等概率考虑：按等概率考虑：可能删除的位置为可能删除的位置为 i=1,2,n 共共 n 个，则个，则 pi=1/n 所以：所以： niniiIinninPE11)(1)(212)1(111 nnnnnninnnni得出：顺序表删除算法平均约需移动一半结点。得出：顺序表删除算法平均约需移动一半结点。 时间复杂度为时间复杂度为O(n) （线性阶）。（线性阶）。（3）按值查找）按值查找按值查找是指在线性表中查找与给定值按值查找是指在线性表中查找与给定值 x 相等的结点。相等的结点。

17、查找算法思想：查找算法思想：从第一个结点从第一个结点 a1 起依次和起依次和 x 比较，直到找到一个与比较，直到找到一个与 x 相等的相等的结点，则返回它的序号或在顺序表中的存储下标结点，则返回它的序号或在顺序表中的存储下标 。 若查遍整个线性表都没有找到与若查遍整个线性表都没有找到与 x 相等的结点，则返回相等的结点，则返回 -1。查找算法：查找算法：int LocationSeqList( SeqList *L, datatype x) int i=0 ; while ( ilast & L-datai!=x ) i+ ; if ( iL-last ) return -1 ; / 当当 i

18、L-last 时肯定没找着时肯定没找着 else return i ; / 返回的是存储位置返回的是存储位置 即数组元素的下标即数组元素的下标查找算法时间性能分析：查找算法时间性能分析：查找算法的主要运算是比较。查找算法的主要运算是比较。比较次数与比较次数与 x 在表中的位置及表的长度有关。在表中的位置及表的长度有关。当当 a1=x 时，比较时，比较 1 次成功。次成功。当当 an=x 时，比较时，比较 n 次成功。次成功。平均比较次数为平均比较次数为 (n+1)/2 。时间复杂度为时间复杂度为O(n)，即线性阶。即线性阶。5. 顺序表其他基本运算顺序表其他基本运算 (动态分配顺序存储结构动态

19、分配顺序存储结构)约定约定:Data0=a1(1)初始化初始化-构造一个空的线性表构造一个空的线性表 L void InitList ( SeqList & L ) L.data = ( ListData * ) malloc ( ListSize * sizeof ( ListData ) ); if ( L.data = = NULL ) printf ( “存储分配失败存储分配失败!n” ); exit (overflow); L.length = 0; L.listsize=ListSize (2)(2)顺序表的插入顺序表的插入( (动态分配顺序存储结构动态分配顺序存储结构) )int

20、 Insert ( SeqList &L, ListData x, int i ) /在表中第在表中第 i 个位置之前插入新元素个位置之前插入新元素 x if (i L.length +1) return error; if( L.length = = L.listSize) newbase=( ListData * ) realloc(L.date, ( listSize +listadd)* sizeof ( ListData ) ); if(!newbase) exit(overflow); L.Data=newbase; L.listsize+=listadd; q=&(L.Datai

21、-1); /q为插入位置为插入位置 for ( p =&( L.DataL.length-1); p=q; -p) *(p+1)=*p; *q=x; L.length+; return 1; /插入成功插入成功 找找x x在表中的位置，若查找成功，返回在表中的位置，若查找成功，返回x x元素第一次出现在表元素第一次出现在表 中的位序，否则返回中的位序，否则返回-1-1int Locate-sq ( SeqList *L, ListData x ) int i = 1; /按序列下标按序列下标 while ( i = L.length & L.datai-1 != x ) i+; if ( i

22、= 0 & i L.length ) return L.datai-1; else printf ( “参数参数 i 不合理不合理！n” ); int Length ( SeqList L ) return L.length; (4) 求表的长度求表的长度(5) 提取提取函数函数(1) (1) 集合的集合的“并并”运算运算void Union ( SeqList &A, SeqList B ) int n = Length ( A ); int m = Length ( B ); for ( int i = 0; i m; i+ ) int x = GetData ( B, i ); /在在B

23、中取一元素中取一元素 int k = Locate-sq (A, x); /在在A中查找它中查找它 if ( k = - -1 ) /若未找到插入它若未找到插入它 Insert ( A, x, +n ); n+; n n先先+再传再传参数参数6. 顺序表的应用顺序表的应用 void Intersection ( SeqList &A, SeqList &B ) int n = Length ( A ); int m = Length ( B ); int i = 0; while ( i data P-next结点结点 node p 为指向链表中某一结点的指针变量。为指向链表中某一结点的指针变

24、量。 *p 表示表示 指针指针 p 所指向的结点所指向的结点 。 (*p).data 或或 p-data 表示表示 p 所指向结点的数据域所指向结点的数据域 。 (*p).next 或或 p-next 表示表示 p 所指向结点的指针域所指向结点的指针域 。p=(node*)malloc(sizeof(node) =(linklist)malloc(sizeof(node) 对指针对指针 p 赋值使其指向某一新结点赋值使其指向某一新结点（按需生成一个（按需生成一个node结点类型的新结点，动态申请空间）结点类型的新结点，动态申请空间）其中：其中： (node*) 进行类型转换。进行类型转换。si

25、zeof(node) 求结点需占用的字节数。求结点需占用的字节数。malloc(size) 在内存中分配在内存中分配 size 个个连续可用字节连续可用字节的空间的空间结点的申请与释放：结点的申请与释放：free(p)系统回收系统回收 p 结点结点，即，即动态动态释放释放 p 指向的结点的空间指向的结点的空间 单链表上的基本运算：单链表上的基本运算：（1）建立单链表）建立单链表B A C HeadHead S 头插法头插法建表（在链表的头部插入结点建立线性链表）：建表（在链表的头部插入结点建立线性链表）： 思想：从一个空表开始，重复读入数据，生成新结点：将读思想：从一个空表开始，重复读入数据，

26、生成新结点：将读入数据存放在新结点的数据域中，然后将新结点插入到当前入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。链表的表头上，直到读入结束标志为止。 DB A C HeadHead S 头插法头插法建表（在链表的头部插入结点建立线性链表）：建表（在链表的头部插入结点建立线性链表）： 思想：从一个空表开始，重复读入数据，生成新结点，将读思想：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。链表的表头上，直到读入结束标

27、志为止。 DB A C HeadHead S 头插法头插法建表（在链表的头部插入结点建立线性链表）：建表（在链表的头部插入结点建立线性链表）： 思想：从一个空表开始，重复读入数据，生成新结点，将读思想：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。链表的表头上，直到读入结束标志为止。 DB A C HeadHead S注：头插法生成的链注：头插法生成的链表中结点的次序和输表中结点的次序和输入的顺序相反。入的顺序相反。 头插法头插法建表（在链表的头部插入结点

28、建立线性链表）：建表（在链表的头部插入结点建立线性链表）： 思想：从一个空表开始，重复读入数据，生成新结点，将读思想：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。链表的表头上，直到读入结束标志为止。 Dvoid CREATELISTF( )char x; / 逐个插入字符，以逐个插入字符，以x为结束符为结束符 node *head, *s; int n=0; / n 为链表表长为链表表长 head=NULL; / 链表开始为空链表开始为空 x=getch

29、ar( ); / 读入第读入第1个结点的值个结点的值 while(x!=x) s=（node *）malloc(sizeof(node); / 生成新结点生成新结点 s-data=x; / 将将 x 的值存入新结点的数据域中的值存入新结点的数据域中 s-next=head; /第第1个结点链域为空个结点链域为空head=s; n+; /表长加表长加1 x=getchar(); 头插法建表头插法建表: : 尾插法建表：尾插法建表：尾插建表可使生尾插建表可使生成的结点次序和成的结点次序和输入的顺序相同输入的顺序相同算法思想：算法思想： 将新结点插入到当前链表的表尾上。将新结点插入到当前链表的表尾上

30、。 可增加一个尾指针可增加一个尾指针 r r ，使其始终指向链表的尾结点。，使其始终指向链表的尾结点。A C B 尾插法建表：尾插法建表：head r S rD 尾插建表可使生尾插建表可使生成的结点次序和成的结点次序和输入的顺序相同输入的顺序相同void CREATLISTR( ) char x; / 逐个插入字符，以逐个插入字符，以 x 为为 结束结束符符 node *head, *s, *r; head=NULL; / 链表开始为空链表开始为空 r=NULL; / 尾指针初值为空尾指针初值为空 int n=0; / n 为链表表长为链表表长 x=getchar(); / 读入第读入第1个结

31、点的值个结点的值 while(x!=x) / x为输入结束符为输入结束符 s=( node * ) malloc(sizeof(node); / 生成新结点生成新结点s-data=x; / 将将x 的值存入新结点的数据域中的值存入新结点的数据域中 if (head=NULL) head=s;else r-next=s;r=s; / r 始终指向链表的尾结点始终指向链表的尾结点n+; / 表长加表长加1 x=getchar(); if(r!=NULL) r-next=NULL; / 保证尾结点的链域为空保证尾结点的链域为空尾插法建表：尾插法建表：尾插法建表分析：尾插法建表分析： 上述尾插法建表由

32、于没有设头结点（附加），因此上述尾插法建表由于没有设头结点（附加），因此开始结点和其它结点的插入处理并不一样。开始结点和其它结点的插入处理并不一样。算法思想：算法思想： 设设头结点头结点，使第一个结点和其余结点的插入操作一致。，使第一个结点和其余结点的插入操作一致。 尾插法建表的改进算法尾插法建表的改进算法增加头结点：增加头结点： 头结点的数据域：可有可无头结点的数据域：可有可无 头结点的指针域：为指向第一个结点的指针。头结点的指针域：为指向第一个结点的指针。改进的尾插法建表算法：改进的尾插法建表算法：带头结点的单链表：带头结点的单链表：特点：特点：无论链表是否为空，其头指针是指向头结点的非空

33、指针。无论链表是否为空，其头指针是指向头结点的非空指针。所以对于尾插法建表，表的第所以对于尾插法建表，表的第 1 个结点和其它结点的操作一致。个结点和其它结点的操作一致。heada1 an 头结点头结点开始结点开始结点非空表：除头结点外还有其他结点非空表：除头结点外还有其他结点终端结点终端结点空表：只有空表：只有1个头结点个头结点head头结点头结点void CREATLISTR1( ) / 带头结点的尾插法建立单链表带头结点的尾插法建立单链表char x; int n=0; node *head, *s, *r; head=(node*)malloc(sizeof(node); / 生成头结

34、点生成头结点 r=head; /尾指针初值指向头结点尾指针初值指向头结点 x=getchar(); while(x!=x) / x为输入结束符为输入结束符 s=（node *）malloc(sizeof(node); / 生成新结点生成新结点 n+; / 表长加表长加1 s-data=x;r-next=s; / 新结点插入表尾新结点插入表尾 r=s; / 尾指针尾指针 r 指向新的表尾指向新的表尾x=getchar(); / 读下一结点读下一结点 r-next=NULL;改进的改进的尾插建表算法尾插建表算法: :void createlist()node *p,*s; char x; int

35、z=1;n=0; head=(node*)malloc(sizeof(node); p=head; printf(ntt建立一个线性表建立一个线性表); printf(“ntt请逐个输入字符，请逐个输入字符， 结束标记为结束标记为xn); while(z)printf(tt输入：输入：); scanf(%c,&x); getchar();if(x!=x) s=(node*)malloc(sizeof(node); n+; s-data=x; p-next=s; s-next=NULL; p=s;else z=0;带头结点的带头结点的尾插建表算法（尾插建表算法（p总指向尾结点）：（不讲）总指向尾

36、结点）：（不讲）（2）查找运算）查找运算设单链表的长度为设单链表的长度为 n n ，要查找表中第，要查找表中第 i i 个结点。个结点。算法思想：算法思想：从头结点开始顺链扫描。从头结点开始顺链扫描。用指针用指针 p p 指向当前扫描到的结点。指向当前扫描到的结点。用用 j j 作统计已扫描结点数的计数器。作统计已扫描结点数的计数器。p p 的的初值指向头结点，初值指向头结点，j j 的初值为的初值为 0 0 。当当 p p 扫描下一个结点时，扫描下一个结点时，j j 自动加自动加 1 1 。 当当 j=ij=i时，指针时，指针 p p 所指的结点就是第所指的结点就是第 i i 个结点。个结点

37、。按序号查找按序号查找node * searchlist1( linklist L, int i ) / L接收已存在的链表的头指针接收已存在的链表的头指针/ i 接收要查找的结点的位置接收要查找的结点的位置 node *p; int j=0; p=L; while( p-next!=NULL & jnext; j+; if(j= =i) return p; else return NULL;i 的合法位置为：的合法位置为：1=i=n带头结点，则可：带头结点，则可：0=inext=NULL) / 链表只有头结点链表只有头结点 printf(tt线性表为空！线性表为空！); return; p=

38、L-next; / 从除头结点外的第从除头结点外的第 1 个结点开始个结点开始while( p!=NULL & p-data!=x ) p=p-next; i+; if( p!=NULL ) return p; printf(tt 在第在第%d位上找到值为位上找到值为%d的结点！的结点！, i, x ); else / p为空，肯定将最后一个结点的链域给了为空，肯定将最后一个结点的链域给了p，即没找到，即没找到 printf(tt 未找到值为未找到值为%c的结点！的结点！n, x ); return NULL; 设设 指针指针 p 指向单链表的某一结点。指向单链表的某一结点。设设 指针指针 s

39、 指向等待插入的、值为指向等待插入的、值为 x 的新结点。的新结点。实现方法（两种）：实现方法（两种）： 后插：将新结点后插：将新结点 * *s s 插在结点插在结点 * *p p 之后。之后。 前插：将新结点前插：将新结点 * *s s 插在结点插在结点 * *p p 之前。之前。（3）插入运算）插入运算算法思想：算法思想： 取一新结点，将其数据域置为新结点，再修改有关结点的取一新结点，将其数据域置为新结点，再修改有关结点的链域：链域： 把原把原 p 结点的直接后继结点作为结点的直接后继结点作为 s 结点的直接后继；结点的直接后继； s 结点作为结点作为 p 结点的直接后继。结点的直接后继。

40、 后插操作后插操作X S PINSERTAFTER( p，x ) / 将值为将值为 x 的新结点插在的新结点插在*P 之后之后 node *p; datatype x; s=( node *)malloc(sizeof(node); / 生成新结点生成新结点 s-data=x; s-next=p-next; / p-next=s; / 将将 *s 插在插在 *p 之后之后后插算法：后插算法：后插算法时间复杂度：后插算法时间复杂度：O（1）先找到先找到 p 结点的前驱结点（单链表无前驱指针）；结点的前驱结点（单链表无前驱指针）；然后修改此前驱结点的链域，使其指向等待插入的然后修改此前驱结点的链域

41、，使其指向等待插入的 s 结点结点 ；然后将然后将 s 结点的链域指向结点的链域指向 p 结点结点 。 前插操作：前插操作：X S q p INSERTBEFORE（p, x） / 在带头结点的单链表在带头结点的单链表 head 中中,将值为将值为 x 的新结点插在的新结点插在 *P 之前之前 node *p; datatype x; node *q; q=head; / 从头指针开始从头指针开始 if( q= =NULL ) printf(“error!”); else s=（node*）malloc(sizeof(node); / 生成新结点生成新结点 s-data=x; while(q-

42、next!=p) q=q-next; / 找找 *p 的前驱结点的前驱结点 s-next=p; / q-next=s; / 将将 *s 插在插在 *p 之之 前前,插在插在 *q 之后之后 前插算法前插算法：前插算法的平均时间复杂度为：前插算法的平均时间复杂度为：O（n） 改进的前插算法改进的前插算法算法思想：算法思想：后插算法为后插算法为 O(1) ，而前插算法为，而前插算法为O(n) 。可在可在 *p 之后插入新结点之后插入新结点 *s ，然后，然后交换交换 *s 和和 *p 的的值值。交换后实际上就是前插。交换后实际上就是前插。pA X s插入前：插入前：后插：后插：A X ps交换调整

43、：交换调整：x A p sINSERTBEFORE2( p，x) / 将值为将值为 x 的新结点插在的新结点插在 *p 之后之后 node *p; datatype x, y; s=（node *）malloc(sizeof(node); / 生成新结点生成新结点 s-data=x; s-next=p-next; p-next=s; / 将将 *s 插在插在 *p 之后之后 y=s-data ; / 交换交换 *s 和和 *p 的值的值 s-data=p-data ; p-data=y ; p=s ;算法描述：算法描述：算法思想：算法思想：先求出第先求出第 i-1 个结点，个结点，然后在第然后

44、在第 i-1 个结点之后插入结点个结点之后插入结点 x。 插入运算插入运算 inslist（i,x ) )（不讲）（不讲）void inslist(int i,char x) /i 的合法位置为：的合法位置为：1=i=n node *s,*p; int j; if(idata=x; s-next=p-next; p-next=s; else printf( tt 未找到前驱结点未找到前驱结点!n); （4）删除运算）删除运算删除单链表中删除单链表中 *p 的后继结点。的后继结点。算法描述：算法描述：DeleteA( p ) / 删除删除 *p 的后继结点的后继结点 *r, 设设 *r 存在存在

45、 node *p; node *r; if(p-next!=NULL) / 说明其后继结点存在说明其后继结点存在 r=p-next; / 将后继结点存到将后继结点存到 r 中，便于释放中，便于释放 p-next=r-next; / 将将 p 的链域指向其后继结点的后继的链域指向其后继结点的后继 free(r); 存储池p r例：在单链表上删除序号为例：在单链表上删除序号为 i 的结点的结点 Delete( L, i ) （按序号删除结点）（按序号删除结点）算法思想：算法思想：（1）找到被删结点（第）找到被删结点（第 i 个结点）的前驱结点（第个结点）的前驱结点（第 i-1个个结结点点）（2）用

46、指针）用指针 p 指向该前驱结点；指向该前驱结点；（3）删除）删除 *p 的后继结点即第的后继结点即第 i 个结点。个结点。思考：思考：（1）如何删除单链表中）如何删除单链表中 p 结点本身？结点本身？ （找前驱结点）（找前驱结点）（2）如何删除单链表中）如何删除单链表中 p 结点的前驱结点？结点的前驱结点？ （找前驱的前驱）（找前驱的前驱）DELETE(L,i)node *L;int i; node*p; int j; j=i-1; p=searchlist1(L,j)；/ 找到第找到第i-1个结点个结点*p if (p!=NULL)&(p-next!=NULL) DeleteA(p); e

47、lse printf(“errorn”)算法实现：算法实现：例：删除线性表例：删除线性表 head 中数据域为中数据域为 x 的结点。的结点。 （按值删除结点）（按值删除结点）算法思想：算法思想： （1）若链表为空，返回；）若链表为空，返回； （2）查找值为）查找值为 x 的结点及其前驱结点；的结点及其前驱结点； （3）将）将 x 结点删除。结点删除。 void dellist( char x ) node *p,*q; / 始终用始终用 q 指向指向 *p 的前驱的前驱 if(head=NULL) / 为空表为空表 printf(tt链表下溢！链表下溢！n); return; if(head

48、-next=NULL) /表只有头结点表只有头结点 printf(tt线性表为空！线性表为空！); return; q=head; p=head-next;算法实现：算法实现：while(p!=NULL&p-data!=x) / 始终用始终用 q 指向指向 *p 的前驱的前驱 q=p; p=p-next; if ( p!=NULL ) / p!=NULL说明说明 p 不是尾结点，不是尾结点，p还在表内还在表内 ，说明找到了值为，说明找到了值为x的结点，就是的结点，就是p q-next=p-next; free(p); printf(tt %c 已经被删除！已经被删除！,x); else pri

49、ntf(tt 未找到！未找到！n);3. 单单循环链表循环链表 整个链表形成一个环，从表中任一结点出发均可找到整个链表形成一个环，从表中任一结点出发均可找到表中其它结点。表中其它结点。a1 an .(非空表）非空表） h(空表）空表）h特点：特点：（1）表中最后一个结点的指针域指向第一个结点或）表中最后一个结点的指针域指向第一个结点或表头结点（如果有表头结点）。表头结点（如果有表头结点）。（2）循环链表的运算与单链表基本一致。但两者判断是否）循环链表的运算与单链表基本一致。但两者判断是否到表尾的条件不同：到表尾的条件不同：单链表：判断某结点的链域是否为空。单链表：判断某结点的链域是否为空。循环

50、链表：判断某结点的链域值是否等于头指针。循环链表：判断某结点的链域值是否等于头指针。（3）用只有头指针表示的单循环链表查找结点：）用只有头指针表示的单循环链表查找结点： 找找 a1(开始结点开始结点) O(1) 找找 an 需要遍历表需要遍历表 O(n) 由于在实际问题中，对表的操作常在表的首尾位置进行，因由于在实际问题中，对表的操作常在表的首尾位置进行，因此可增加一个尾指针此可增加一个尾指针(rear)，则：，则： 找找a1(开始结点开始结点) ：rear-next-next O(1) 找找an ： rear O(1) 实用中多用实用中多用尾指针尾指针表示表示单循环链表单循环链表。尾指针表示

51、的单循环链表：尾指针表示的单循环链表：headhead非空表非空表空表空表rearrear例：表的合并例：表的合并 在链表上实现将两个线性表在链表上实现将两个线性表(a1,a2,.,an)和和(b1,b2bm)链接成链接成一个线性表一个线性表(a1,a2,.,an,b1,b2,.,bm)的的运算。运算。分析：分析： 若在若在单链表单链表或或只有头指针表示的单循环链表只有头指针表示的单循环链表上做这种链接上做这种链接运算，运算， 都要遍历第一个链表找到结点都要遍历第一个链表找到结点 an ， 然后将结点然后将结点 b1 链接链接到到 an 的后面的后面，其执行时间为其执行时间为 O(n) 。算法

52、思想：算法思想： 在尾指针表示的单循环链表上实现，则只需修改指针，无在尾指针表示的单循环链表上实现，则只需修改指针，无需遍历，需遍历，其执行时间为其执行时间为O(1) 。两个单循环链表（用尾指针表示）的链接示意图：两个单循环链表（用尾指针表示）的链接示意图：rarbp 两个单循环链表（用尾指针表示）的链接示意图：两个单循环链表（用尾指针表示）的链接示意图：rarbnode *CONNECT(ra,rb)node *ra,*rb; node*p;p=ra-next;/ 保存链表保存链表ra的头结点地址的头结点地址 ra-next=rb-next-next; / 将表将表rb的开始结点链接到表的开

53、始结点链接到表ra的终端结点之后的终端结点之后 free(rb-next);/ 释放链表释放链表rb的头结点的头结点 rb-next=p；/ 链表链表ra的头结点链到链表的头结点链到链表rb的终端结点之后的终端结点之后 return rb ;/返回新循环链表的尾指针返回新循环链表的尾指针4 .双向链表（双向链表（Double linked list)查找某个结点：查找某个结点： 单链表只能顺链向后（顺着直接后继指针）查找。单链表只能顺链向后（顺着直接后继指针）查找。查找某个结点的前驱结点：查找某个结点的前驱结点： 单链表：从头顺链找。单链表：从头顺链找。O(n) 单循环链表：可从任一已知结点出

54、发进行查找。单循环链表：可从任一已知结点出发进行查找。O(n)双向链表（双向链表（Double linked list)： 单链表的每个结点再增加一个指向其前驱的指针域单链表的每个结点再增加一个指向其前驱的指针域 prior，这样形成的链表有两条不同方向的链，称之为双向链表。这样形成的链表有两条不同方向的链，称之为双向链表。特点：特点：双链表一般也由头指针双链表一般也由头指针 head 唯一确定。唯一确定。每一结点均有：每一结点均有： 数据域数据域 （data ） 左链域左链域 （prior） 指向前驱结点。指向前驱结点。 右链域右链域 （next ） 指向后继结点。指向后继结点。是一种对称结

55、构（既有左链域，又有右链域）。是一种对称结构（既有左链域，又有右链域）。（1）双向链表的分类：）双向链表的分类： 非循环双向链表非循环双向链表 循环双向链表循环双向链表 为了运算方便，还可添加一个表头结点。为了运算方便，还可添加一个表头结点。（2）双链表的结点类型描述）双链表的结点类型描述typedef struct dnode datatype data; struct dnode *prior,*next;dlinknode;dlinknode *head;(3)结点结构示意图结点结构示意图headheadhead结点结构示意图结点结构示意图带头结点的双循环带头结点的双循环空空链表链表带头

56、结点的双循环链表带头结点的双循环链表 p-prior-next=p-next-prior=p 即：即： 结点结点*p 的存储位置的存储位置 ： 既存放在其前驱结点既存放在其前驱结点( * p-prior )的后继指针域中；的后继指针域中； 也存放在其后继结点也存放在其后继结点( * p-next ) 的前驱指针域中。的前驱指针域中。(4)双链表结构对称性描述：双链表结构对称性描述：插入；插入；删除；删除；查找；查找；在单链表中：在单链表中：前插不如后插方便；前插不如后插方便；删除某结点自身不如删除该结点的后继方便。删除某结点自身不如删除该结点的后继方便。而在双向链表中，上述运算均十分方便。而在

57、双向链表中，上述运算均十分方便。双链表的基本运算：双链表的基本运算：/在带头结点的双链表中，将值为在带头结点的双链表中，将值为 x 的新结点插在的新结点插在 *p 之前之前 void dinsert(p,x)dlinknode *p;datatype x; dlinknode *s; s= (dlinknode*) malloc(sizeof(dlinknode); s-data=x; s-prior=p-prior; s-next=p; p-prior-next=s; p-prior=s; （1）前插操作（将结点）前插操作（将结点 x 插在插在 *p 之前）之前）spax注意：注意：5，6步

58、的顺序不能颠倒步的顺序不能颠倒如果是后插，则注意如果是后插，则注意5，6步的顺序步的顺序spxa p-next-prior=s; p-next=s;Ddelete(p)dlinknode *p; p-prior-next=p-next; p-next-prior=p-prior; free(p);pxa（2）删除操作（在双向链表中删除）删除操作（在双向链表中删除 p 结点）结点）算法思想：算法思想： 从第一个结点开始（从第一个结点开始（头结点的后继头结点的后继）依次比较每个结点）依次比较每个结点的数据域的值，若找到结点的数据域的值，若找到结点 x，则，则返回指向该结点的指针返回指向该结点的指针

59、； 否则：若又回到头结点，说明表中不存在结点否则：若又回到头结点，说明表中不存在结点 x，则，则返回返回空指针空指针。（3）查找（在带头结点的双向循环链表中查找结点）查找（在带头结点的双向循环链表中查找结点 x ）算法描述：算法描述：( 自己完成）自己完成）5. 静态链表静态链表 静态链表可以借助一维数组来描述：静态链表可以借助一维数组来描述： #define MAXSIZE 1000 typedef struct ElemType data; int cur; component, SlinkListMAXSIZE; 为了便于在不设指针类型的高级程序设计语言中使用为了便于在不设指针类型的高级

60、程序设计语言中使用链表结构，引入静态链表。链表结构，引入静态链表。 静态链表和前面的动态链表一样，便于插入和删除操静态链表和前面的动态链表一样，便于插入和删除操作：插入和删除同样不需要移动元素。作：插入和删除同样不需要移动元素。 设设 S S 为为 SlinkList SlinkList 型变量，则型变量，则 S0.cur S0.cur 指示第一个结点在指示第一个结点在数组中的位置，设数组中的位置，设 i=s0.curi=s0.cur，则，则 si.datasi.data存放线性表的第一存放线性表的第一个元素，且个元素，且 si.cur si.cur 指示第二个结点在数组中位置。指示第二个结点