数据结构清华大学殷人昆02

1、92-1第二章第二章 线性表线性表清华大学计算机系清华大学计算机系 殷人昆殷人昆数据结构课件数据结构课件第第101-2n线性表线性表n顺序表顺序表 n链表链表n顺序表与链表的比较顺序表与链表的比较n字符串字符串n多项式多项式第二章 线性表101-3线性表线性表 (Linear List)n线性表的定义和特点线性表的定义和特点r定义定义 n（0）个数据元素的有限序列，记作个数据元素的有限序列，记作 （a1, a2, , an） ai 是表中数据元素，是表中数据元素，n 是表长度。是表长度。r特点特点 线性排列线性排列 除第一个元素外，其他每一个元素有一个除第一个元素外，其他每一个元素有一个且仅有

2、一个且仅有一个直接前驱直接前驱。 除最后一个元素外，其他每一个元素有一除最后一个元素外，其他每一个元素有一个且仅有一个个且仅有一个直接后继直接后继。101-4n理解线性表的要点是理解线性表的要点是r 表中元素具有逻辑上的顺序性，在序列中表中元素具有逻辑上的顺序性，在序列中各元素排列有其先后次序。各元素排列有其先后次序。r 表中元素个数有限。表中元素个数有限。r 表中元素都是数据元素。就是说，每一表表中元素都是数据元素。就是说，每一表元素都是不可再分的原子数据。元素都是不可再分的原子数据。a) 表中元素的数据类型都相同。这意味着每表中元素的数据类型都相同。这意味着每一表元素占有相同数量的存储空间

3、。一表元素占有相同数量的存储空间。a1a2a3a4a5a6101-5顺序表顺序表 (Sequential List)n顺序表的定义和特点顺序表的定义和特点r定义定义 将线性表中的元素相继存放在一个连续将线性表中的元素相继存放在一个连续的存储空间中，即构成顺序表。的存储空间中，即构成顺序表。r存储存储 它是线性表的顺序存储表示，可利用一它是线性表的顺序存储表示，可利用一维数组描述存储结构。维数组描述存储结构。r特点特点 元素的元素的逻辑顺序与物理顺序一致逻辑顺序与物理顺序一致。r访问方式访问方式 可顺序存取，可按下标直接存取。可顺序存取，可按下标直接存取。 25 34 57 16 48 09 0

4、 1 2 3 4 5elem101-6顺序表的连续存储方式顺序表的连续存储方式LOC(i) = LOC(i-1) + l = a + i * l, LOC 是元素存储位置是元素存储位置，l 是元素大小是元素大小LOC(i) = LOC(i-1)+l = a +i*l, i 0 a, i = 0 a+i*l35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 l l l l l l l l l l a101-7顺序表的静态结构定义顺序表的静态结构定义#define ListSize 100 /最大允许长度最大允许长度typedef int ElemT

5、ype;/元素的数据类型元素的数据类型typedef struct ElemType elemListSize; /存储数组存储数组 int length; /当前表元素个数当前表元素个数 SeqList; n顺序表静态定义，假定顺序表静态定义，假定 L 是一个类型是一个类型 SeqList 的顺序表，一般用的顺序表，一般用 L.elemi 来访问它。来访问它。n表一旦装满，不能扩充。表一旦装满，不能扩充。101-8顺序表的动态结构定义顺序表的动态结构定义#define ListSize 100 /最大允许长度最大允许长度typedef int ElemType;/元素的数据类型元素的数据类型

6、typedef struct ElemType *elem; /存储数组存储数组 int length; /当前表元素个数当前表元素个数 int maxSize; /表的最大长度表的最大长度 SeqList; n顺序表动态定义，它可以扩充，新的大小计入顺序表动态定义，它可以扩充，新的大小计入数据成员数据成员maxSize中。中。101-9顺序表基本运算的实现顺序表基本运算的实现n构造一个空的顺序表构造一个空的顺序表void InitList (SeqList& L) L.elem = new ElemTypeListSize; if (L.elem = NULL) printf (“存储分配失

7、败存储分配失败!n”); exit (1); L.length = 0; L.maxSize = ListSize; n判断判断L.elem是否为空语句是后置条件。是否为空语句是后置条件。101-10n动态分配命令动态分配命令 new 是是Pascal、C+、Java常用的常用的语句，它的作用与语句，它的作用与 C 的的 malloc 命令等效，但比命令等效，但比malloc简洁，它不用计算分配字节数，不用做指简洁，它不用计算分配字节数，不用做指针转换，一切工作针转换，一切工作 new 替你代劳了。替你代劳了。n注意指针的使用。指针所指示元素也有它的数注意指针的使用。指针所指示元素也有它的数据

8、类型。例如对于指针据类型。例如对于指针 *p 和和 *q： char *p = new charmaxSize; float *q = new floatmaxSize;n用用 p+ 让让 p 指到下一字符位置，用指到下一字符位置，用 q+ 让让 q 指指到下一浮点数位置，它们移过的字节数不同。到下一浮点数位置，它们移过的字节数不同。101-11n引用型参数引用型参数 & 的使用的使用r例如，例如， void InitList (SeqList& L) rC+的引用型参数的引用型参数“&”与与Pascal的变量参数一的变量参数一样，是把形参样，是把形参 L 看作是实际变量（一个表）的看作是实际

9、变量（一个表）的别名，别名，在函数体内对在函数体内对 L 的操作将是直接对实际的操作将是直接对实际变量的操作变量的操作。r好处之一是可在函数体内像普通变量那样对好处之一是可在函数体内像普通变量那样对 L 操作，使得操作简单。操作，使得操作简单。r好处之二是可直接从实际变量得到操作结果。好处之二是可直接从实际变量得到操作结果。r好处之三是不必创建实际变量的副本空间。好处之三是不必创建实际变量的副本空间。101-12n按值查找：在顺序表中从头查找结点值等于给按值查找：在顺序表中从头查找结点值等于给定值定值 x 的结点的结点int Find ( SeqList& L, ElemType x ) in

10、t i = 1; ElemType * p; for ( p = L.elem; p; p+ ) /p+将指针将指针 p 进进 if ( *p != x ) i+; /到到L.elem 的下的下 else break; /一个元素位置一个元素位置. if ( i = L.length ) return i; /*p取取 p 所指元所指元 else return 0; /素的值素的值 101-13n按值查找：按值查找：在顺序表中从头查找结点值等于给定在顺序表中从头查找结点值等于给定值值 x 的结点的结点int Find ( SeqList& L, ElemType x ) int i = 0;

11、while ( i L.length & L.elemi != x ) i+; if ( i L.length ) return i+1; /i 与实际位置与实际位置 else return 0; /差一差一 n注意注意 i L.length & L.elemi != x 位置不能颠倒位置不能颠倒101-14n查找成功的平均比较次数查找成功的平均比较次数 n若查找概率相等，则若查找概率相等，则n查找不成功查找不成功 数据比较数据比较 n 次。次。i-1n0iicp=ACN2n12nn)(1n1 n)2(1n11)(in1=ACN-1n0i查找算法性能分析查找算法性能分析101-15表项的插入表

12、项的插入bool Insert ( SeqList& L, ElemType x, int i ) /在表中第在表中第 i (1in+1) 个位置插入新元素个位置插入新元素 x if ( i L.length+1 ) return 0; if ( L.length = ListSize ) return 0; /参数不合理或表已满，插入不成功参数不合理或表已满，插入不成功 for (int j = L.length-1; j = i-1; j-) L.elemj+1 = L.elemj; L.elemi-1 = x; /实际插在第实际插在第i-1个位置个位置 L.length+; return

13、 1; /插入成功插入成功 101-162n21)n(n1)(n1 0)1(n1n1i)(n1n1=AMNn0i25 34 57 16 48 09 63 0 1 2 3 4 5 6 7L.elem50插入插入 x25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7L.elem50i=4101-17bool Delete ( SeqList& L, int i, ElemType& x ) /在表中删除第在表中删除第 i 个元素，通过个元素，通过 x 返回其值返回其值 if ( i 0 & i = L.length ) x = L.elemi-1; L.length-;

14、 for (int j = i-1; j link 进到下一结点。进到下一结点。datalinkp 指示结点地址指示结点地址datalinkp- 结点本身结点本身datalinkp-data 结点结点data域的值域的值datalinkp-link 结点结点link域的值域的值101-24单链表中的插入与删除单链表中的插入与删除n插入的考虑插入的考虑r 第一种情况：在第第一种情况：在第 1 个结点前插入：个结点前插入： newnode-link = first ; first = newnode; /修改头指针修改头指针（插入前）（插入前） （插入后）（插入后） firstnewnodenew

15、nodefirst101-25第二种情况：在链表中间插入：第二种情况：在链表中间插入： 首先定位指针首先定位指针 p 到插入位置，再将新结点插到插入位置，再将新结点插 在其后：在其后： newnode-link = p-link; p-link = newnode；( (插入前插入前) () (插入后插入后) )newnodepnewnodep101-26第三种情况：在链表末尾插入：第三种情况：在链表末尾插入： 首先定义指针首先定义指针 p 到尾结点位置，再将新结点到尾结点位置，再将新结点 插在其后，新结点成为新的尾结点。插在其后，新结点成为新的尾结点。 newnode-link = p-li

16、nk; p-link = newnode；(插入前插入前) (插入后插入后)newnodenewnodepp 101-27bool Insert ( LinkList& first, ElemType x, int i ) /在链表第在链表第 i (1)个结点处插入新元素个结点处插入新元素 x ListNode * p = first; int k = 1; while ( p != NULL & k link; k+; /找第找第 i-1个结点个结点 if ( p = NULL & first != NULL ) printf (“无效的插入位置!n” ); return 0; /给的给的

17、i 太大太大 ListNode * newnode = new ListNode; /创建新结点创建新结点101-28 newnode-data = x; if (first = NULL | i = 1) /插在表前端插在表前端 newnode-link = first; first = newnode; /考虑为何在参数表中考虑为何在参数表中 first 定义为引用型定义为引用型 else /插在表中或末尾插在表中或末尾 newnode-link = p-link; p-link = newnode; return 1; 101-29n删除的考虑删除的考虑r第一种情况第一种情况: 删除表中

18、第删除表中第 1 个元素个元素r第二种情况第二种情况: 删除表中或表尾元素删除表中或表尾元素在单链表中删除含在单链表中删除含 ai 的结点的结点ai-1ai-1aiaiai+1ai+1pq删除前删除前删除后删除后101-30bool Delete (LinkList& first, int i, ElemType& x) /在链表中删除第在链表中删除第 i 个结点。如果要删除表中第个结点。如果要删除表中第 1 个个/结点，需要改变表头指针，所以结点，需要改变表头指针，所以 first 定义为引用定义为引用/型，被删元素的值通过引用型参数型，被删元素的值通过引用型参数 x 返回返回 ListNo

19、de *p, *q; if (i = 1) /删除表中第删除表中第 1 号结点号结点 q = first; first = first-link; else p = first; int k = 1; /找第找第 i-1个结点个结点 while ( p != NULL & k link; k+; 101-31 if ( p = NULL | p-link = NULL ) printf ( “无效的删除位置无效的删除位置!n” ); return 0; else /删除表中或表尾元素删除表中或表尾元素 q = p-link; /重新链接重新链接 p-link = q-link; x = q-d

20、ata; delete q; /删除删除q return 1; /delete作用与作用与free相同相同101-32带头结点的单链表带头结点的单链表n头结点位于表的最前端，本身不带数据，仅标头结点位于表的最前端，本身不带数据，仅标志表头。志表头。n设置头结点的目的是设置头结点的目的是r统一空表与非空表的操作统一空表与非空表的操作r简化链表操作的实现。简化链表操作的实现。非空表非空表 空表空表ana1firstfirst101-33前插法建立单链表前插法建立单链表n从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：生成新结点生成新结点将读入数据存放到新结点的数据域中将读入数据存放到新

21、结点的数据域中将该新结点插入到链表的前端将该新结点插入到链表的前端n直到读入结束符为止。直到读入结束符为止。firstnewnodefirstnewnode（空表）（空表） （非空表）（非空表）101-34LinkList& createListF ( ElemType finishi ) ElemType x; ListNode *s; LinkList first = new ListNode; /建立头结点建立头结点 first-link = NULL; cin x; /约定以约定以 finish 结束连续输入结束连续输入while ( x != finish ) newNode = n

22、ew ListNode; /建立新结点建立新结点 newNode-data = x; newNode-link = first-link; /插入到表前端插入到表前端 first-link = newNode;cin x;101-35 return first;n主程序可用主程序可用LinkList L = createF(finish)得到新建得到新建链表。要求链表。要求 finish 是链表中不可能出现的元素。是链表中不可能出现的元素。n算法中数据的输入算法中数据的输入输出使用了流对象（输出使用了流对象（cincout）和输入（）和输入（）、输出（）、输出（）操作符，它们）操作符，它们取代

23、了取代了C中的中的 scanf 和和 printf 操作函数，省去了格操作函数，省去了格式符（式符（%d, %s, %f），简化了操作。），简化了操作。n要求在程序首部使用要求在程序首部使用 #include ，不，不再使用再使用 #include 。101-36后插法建立单链表后插法建立单链表n每次将新结点加在插到链表的表尾；每次将新结点加在插到链表的表尾；n设置一个尾指针设置一个尾指针 r，总是指向表中最后一个结，总是指向表中最后一个结点，新结点插在它的后面；点，新结点插在它的后面；n尾指针尾指针 r 初始时置为指向表头结点地址。初始时置为指向表头结点地址。newnodefirstnewn

24、oderrrr（空表）（空表） （非空表）（非空表）101-37LinkList& createListR ( ElemType finish ) ElemType x; LinkList first = new ListNode; /建立头结点建立头结点 ListNode *s, *rear = first; / rear 指向表尾指向表尾 cin x; while ( x != finish ) s = new ListNode; /建立新结点建立新结点 s-data = x; rear-link = s; rear = s; /插入到表末端插入到表末端 cin x; 101-38 rea

25、r-link = NULL; /表收尾表收尾 return first; n主程序可用主程序可用 LinkList L = createR(finish) 得到新得到新建链表。建链表。n使用使用前插法前插法建立链表，每次新元素插入在表头，建立链表，每次新元素插入在表头，数据元素的链接顺序与输入顺序完全数据元素的链接顺序与输入顺序完全相反相反。n使用使用后插法后插法建立链表，每次新元素插入在表尾，建立链表，每次新元素插入在表尾，数据元素的链接顺序与输入顺序完全数据元素的链接顺序与输入顺序完全一致一致。101-39单链表清空单链表清空firstqa1a2a3firstqa2a3firstqa3fi

26、rst101-40void makeEmpty ( LinkList first ) /删去链表中除表头结点外的所有其他结点删去链表中除表头结点外的所有其他结点 ListNode *q; while ( first-link != NULL ) q = first-link; first-link = q-link;/将表头结点后第将表头结点后第 1 号结点从链中摘下号结点从链中摘下 delete q; /释放它释放它 101-41pcount = 0计算单链表长度计算单链表长度firsta3a2a1pcount = 1firsta3a2a1pcount = 2firsta3a2a1pcoun

27、t = 3firsta3a2a1101-42int Length ( LinkList first ) ListNode *p = first-link; /检测指针检测指针 p 跳过表头结点指示第跳过表头结点指示第 1 号结点号结点 int count = 0; while ( p != NULL ) /逐个结点计数逐个结点计数 p = p-link; count+; return count;n结点计数与链表指针前移同步进行。结点计数与链表指针前移同步进行。101-43在单链表中按值查找在单链表中按值查找ListNode * Find ( LinkList first, ElemType

28、x ) /在链表中从头搜索其数据值为在链表中从头搜索其数据值为 x 的结点的结点 ListNode * p = first-link; /检测指针检测指针 p 指示第指示第 1 号结点号结点 while ( p != NULL & p-data != x ) p = p-link; return p; n查找成功返回结点地址；查找不成功返回空。查找成功返回结点地址；查找不成功返回空。101-44ListNode * Locate ( LinkList first, int i ) /返回表中第返回表中第 i 个元素的地址个元素的地址, 表头结点为表头结点为 0 号号 if ( i 0 ) re

29、turn NULL; / i 值不合理值不合理 ListNode * p = first; int k = 0; while ( p != NULL & k link; k+; /找第找第 i 个结点个结点 return p; /当返回地址非空则为第当返回地址非空则为第 i 个结点地址个结点地址/否则返回否则返回NULL在单链表中按序号查找（定位）在单链表中按序号查找（定位）101-45bool Insert ( LinkList first, ElemType x, int i ) /将新元素将新元素 x 插入在链表中第插入在链表中第 i (1i) 号结点位置号结点位置 ListNode *

30、 p = Locate (first, i-1); if ( p = NULL ) return 0; / i-1个结点未找到个结点未找到 ListNode * newNode = new ListNode; newNode-data = x; /创建新结点创建新结点 newNode-link = p-link; /链入链入 p-link = newNode; return 1; /插入成功，函数返回插入成功，函数返回1在单链表中插入新元素在单链表中插入新元素101-46bool delete ( LinkList first, int i, ElemType& x ) /将链表第将链表第 i

31、 号元素删去号元素删去, 通过通过 x 返回返回 ListNode * p = Locate (first, i-1); /寻找被删结点的前驱结点寻找被删结点的前驱结点 if ( p = NULL | p-link = NULL) return 0; ListNode * q = p-link; /被删结点地址被删结点地址 p-link = q-link; /摘下被删结点摘下被删结点 x = q-data; delete q; /释放释放 return l;在单链表中删除一个结点在单链表中删除一个结点101-47循环链表循环链表 (Circular List)n循环链表是单链表的变形。循环链表

32、尾结点的循环链表是单链表的变形。循环链表尾结点的 link 指针不是指针不是 NULL，而是指向了表的前端。，而是指向了表的前端。n为简化操作，在循环链表中往往加入表头结点。为简化操作，在循环链表中往往加入表头结点。a1firsta2a3anfirsta1anfirst(空表，也要保留表头空表，也要保留表头)(非空表非空表)101-48n循环链表的判空条件是：循环链表的判空条件是：first-link = first。n循环链表的特点是：只要知道表中某一结点的循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。地址，就可搜寻到所有其他结点的地址。n在搜寻过程中，没有一个

33、结点的在搜寻过程中，没有一个结点的 link 域为空。域为空。 for (p = first-link; p != first; p = p-link ) do S;n循环链表的所有操作的实现类似于单链表，差循环链表的所有操作的实现类似于单链表，差别在于检测到链尾，指针不为别在于检测到链尾，指针不为NULL，而是回，而是回到链头。到链头。a1firsta2a3an101-49带尾指针的循环链表带尾指针的循环链表reara1a2a3ann如果插入与删除仅在链表的两端发生，可采用带如果插入与删除仅在链表的两端发生，可采用带表尾指针的循环链表结构。表尾指针的循环链表结构。r在表尾可直接插入新结点，时

34、间复杂性在表尾可直接插入新结点，时间复杂性 O(1);r在表尾删除时要找前驱，时间复杂性在表尾删除时要找前驱，时间复杂性 O(n);r在表头插入相当于在表尾插入在表头插入相当于在表尾插入;r在表头可直接删除，时间复杂性在表头可直接删除，时间复杂性 O(1)。101-50n双向链表是指在前驱和后继方向都能遍历的线双向链表是指在前驱和后继方向都能遍历的线性链表。双向链表每个结点的结构为：性链表。双向链表每个结点的结构为： n双向链表通常采用带表头结点的循环链表的形双向链表通常采用带表头结点的循环链表的形式。每一个结点处于两个链中。式。每一个结点处于两个链中。双向链表双向链表 (Doubly Lin

35、ked List)前驱方向 后继方向llink data rlink非空表非空表 空表空表firstfirst101-51n结点指向结点指向rp-llink 指示结点指示结点 p 的的前驱前驱结点结点rp-rlink 指示结点指示结点 p 的的后继后继结点结点rp-llink-rlink指示结点指示结点 p 的的前驱前驱结点的结点的后继后继结结点，即结点点，即结点 p 本身本身rp-rlink-llink指示结点指示结点 p 的的后继后继结点的结点的前驱前驱结结点，即结点点，即结点 p 本身本身p-llinkp-rlinkpllinkrlink101-52双向循环链表的定义双向循环链表的定义t

36、ypedef int ElemType; /每个元素的类型每个元素的类型typedef struct Dblnode /结点定义结点定义 ElemType data; /数据数据 struct Dblnode *llink, *rlink; /指针指针 *DblList; /双向链表双向链表n传统教材上用传统教材上用 prior 定义前驱指针，用定义前驱指针，用 next 定定义后继指针。单链表寻找结点后继，时间复杂义后继指针。单链表寻找结点后继，时间复杂度度O(1)，寻找结点前驱，时间复杂度，寻找结点前驱，时间复杂度O(n)； 而而双向链表都是双向链表都是O(1)。 101-53建立空的双向

37、循环链表建立空的双向循环链表void CreateDblList ( DblList &first ) first = new DblNode;/分配结点空间分配结点空间 if ( first = NULL ) /如果分配失败如果分配失败 printf (“存储分配错存储分配错!n” ); exit (1); first-llink = first-rlink = first; /表头结点的链指针指向自己表头结点的链指针指向自己101-54查找成功查找成功查找不成功查找不成功双向循环链表的查找双向循环链表的查找firstfirst3131484815155757查找查找15 查找查找25 10

38、1-55双向循环链表的查找双向循环链表的查找n若在以若在以 first 为表头结点的双向循环链表中搜寻为表头结点的双向循环链表中搜寻含含 x 的结点，要区分是在后继方向还是在前驱的结点，要区分是在后继方向还是在前驱方向。当搜索结果方向。当搜索结果 p 指向表头，则搜索失败，指向表头，则搜索失败，否则返回找到结点地址。否则返回找到结点地址。n后继方向后继方向DblNode *p = first-rlink; while ( p != first & p-data != x ) p = p-rlink; return p;n前驱方向类似，只需把前驱方向类似，只需把 rlink 换成换成 llink

39、。101-56定位定位:查找第查找第 i 个结点在链中的位置个结点在链中的位置DblNode *Locate ( DblList first, int i, int d ) if ( i 0 ) return first; DblNode *p = first; int j = 0; while ( j llink : p-rlink;j+; /d = 0前驱方向前驱方向, d = 1后继方向后继方向 if ( p = first ) return NULL; / i太大太大 return p;/返回第返回第 i 个结点地址个结点地址101-57first314815ppnewNode双向循环

40、链表的插入双向循环链表的插入 (非空表非空表)n在结点在结点 *p 后插入后插入25newNode-rlink = p-rlink;p-rlink = newNode;newNode-llink = p;newNode-rlink-llink = newNode;first31481525101-58firstpnewNode25firstp双向循环链表的插入双向循环链表的插入 (空表空表)n在结点在结点 *p 后插入后插入25newNode-rlink = p-rlink; ( = first ) p-rlink = newNode; newNode-llink = p;newNode-rl

41、ink-llink = newNode; ( first-llink = newNode )101-59bool Insert (DblList first, ElemType x, int i, int d ) DblNode *p = Locate (first, i-1, d); /指针定位于插入位置指针定位于插入位置 if ( p = NULL ) return 0; DblNode *newNode = new DblNode; /分配结点分配结点 newNode-data = x; if ( d ) /在后继方向插入到在后继方向插入到 p 右方右方 newNode-rlink =

42、p-rlink; p-rlink = newNode; newNode-llink = p; newNode-rlink-llink = newNode; 101-60 else /在前驱方向插入到在前驱方向插入到 p 左方左方 newNode-llink = p-llink; p-llink = newNode; newNode-rlink = p; newNode-llink-rlink = newNode; return 1;n两个方向的插入语句类似，只是两个方向的插入语句类似，只是 llink 与与 rlink 互互换了一下。换了一下。101-61first删除后删除后表非空表非空31

43、4815pfirst3115双向循环链表的删除双向循环链表的删除n删除删除 48 p-rlink-llink = p-llink;p-llink-rlink = p-rlink;101-62n删除删除31p-rlink-llink = p-llink;p-llink-rlink = p-rlink;firstfirst31p双向循环链表的删除双向循环链表的删除删除后删除后表为空表为空101-63bool Remove (DblList first, int i, int d, ElemType& x) /删除在删除在 d 指明方向的第指明方向的第 i 个结点个结点, x 返回其值返回其值 Db

44、lNode *p = Locate (first, i, d); /指针定位于删除结点位置指针定位于删除结点位置 if (p = NULL) return 0; /不能删除不能删除 p-rlink-llink = p-llink; p-llink-rlink = p-rlink; /将被删结点将被删结点 p 从链上摘下从链上摘下 x = p-data; delete p; /删去删去 return 1;101-64顺序表与链表的比较顺序表与链表的比较n基于空间的比较基于空间的比较r存储分配的方式存储分配的方式顺序表的存储空间可以是顺序表的存储空间可以是静态分配静态分配的，的，也可以是也可以是动

45、态分配动态分配的。的。链表的存储空间是链表的存储空间是动态分配动态分配的。的。r存储密度存储密度 = = 结点数据本身所占的存储量结点数据本身所占的存储量/ /结点结构所占的存储总量结点结构所占的存储总量顺序表的存储密度顺序表的存储密度 = 1= 1链表的存储密度链表的存储密度 1 T。/ 返回返回值值= 1; 若若S T, 返回值返回值 = -1。 return strcmp ( S.ch, T.ch );字符串其他部分操作的实现字符串其他部分操作的实现101-74利用串的操作实现串的定位算法利用串的操作实现串的定位算法n此算法就是求子串此算法就是求子串P在串在串T中首次出现的位置中首次出现

46、的位置 101-75int index ( HeapString& T, HeapString& P ) /在串在串T中寻找与串中寻找与串P相匹配的子串。若有，相匹配的子串。若有，函数返回函数返回/子串子串首字符首字符在串中在串中首次出现首次出现位置，若无，返回位置，若无，返回-1。 int LT = Length (T), LP = Length (P); string *subString; int i = 0; while ( i curLen- -1 修改修改 count = curLen- -posi n f i n i t yi n f i n i t ypos = 2, coun

47、t = 3pos = 5, count = 4f i ni t y超出超出101-77void SubStr ( HeapString& T, HeapString& S, int pos, int len ) /从串从串S中第中第pos字符起连续取字符起连续取len个字符，由个字符，由T返回返回 int i; char *p, *q; if ( pos = S.n ) cout 位置位置pos无效无效!n ; exit(1); if ( len 0 ) cout S.n-pos ) len = S.n-pos; delete T-ch;101-78 T.ch = new charlen+1;

48、 if ( T.ch = NULL) /重新分配子串空间重新分配子串空间 cout overflow; exit(1); p = T.ch; q = S.ch+pos; for ( i = 1; i link; /多项式多项式 A 的检测指针的检测指针 pb = B-link; /多项式多项式 B 的检测指针的检测指针多项式相加的链表实现多项式相加的链表实现101-93 while ( pa != NULL & pb != NULL ) a = pa-coef; if ( pa-exp = pb-exp ) /对应项指数相等对应项指数相等 a = a + pb-coef; /系数相加系数相加 p = pb; pb = pb-link; delete p; /指数相等的结点仅保留一个加入结果链指数相等的结点仅保留一个加入结果链 if ( fabs (a) 0.001 ) /相加不为零相加不为零 pa-coef = a; pc-link = pa; pc = pa; pa = pa-link; /加入结果链加入结果链 101-94 else /相加为零相加为零,该项不要该项不要 p = pa; pa = pa-link; delete p; else if ( pa-e