boolListDelete(LinkList&L,inti,int&x)删除前.I/查找第i-1个元素paiap=L; j=0,Dwhile(p&& j<i-1)(p=p->next, j++;执行①之后//若存在第1个元素，则用x返回数据，并删除之if（p&&j==i-1&&p->next）（//可以删除pTsTo①s = p->next,②p->next = s->next;执行②之后x = s->dataaa1free (s);Dreturn true,0sTo1elsereturn false,1注意：a）要求p找到第i-1个而非第i个元素。为什么？b）能够进行删除的条件：p&&j-=i-1&&p->next。条件中的p->next就是要保证第i个元素存在，否则无法删除。若写成p->next&&j-=i-1也不妥，因为此时（循环结束时)可能有p==NULL，所以必须先确定p不空。技巧：将条件中的“大前提”放在前面。该条件也不可以写成p->next&&p&&j=i-1，因为先有pl=0才有p->next，上式颠倒了这一关系。c)释放结点的方法。free(s);d）完成删除的步骤：①②。（8）建立链表的两种方法思路：建立空表（头结点）；依次插入数据结点（每次插入表尾得(ai,a2..an)，每次插入表头得(am.,a2,ai))。1°顺序建表void CreateLinkList (LinkList &L, int n)1Ⅱ建立空表L= (LinkList) malloc(sizeof(LNode);L->next=NULL:Ⅱ空表p=L;/用p指向表尾I插入元素for(i=0; i<n, i++) scanf(x )- 15 -
- 15 - bool ListDelete ( LinkList &L, int i, int &x ) { // 查找第 i-1 个元素 p p = L; j = 0; while ( p && j<i-1 ) { p = p->next; j++; } //若存在第 i 个元素，则用 x 返回数据，并删除之 if ( p && j==i-1 && p->next ) { // 可以删除 s = p->next; // ① p->next = s->next; // ② x = s->data; free (s); return true; } else return false; } 注意： a) 要求 p 找到第 i-1 个而非第 i 个元素。为什么？ b) 能够进行删除的条件： p && j==i-1 && p->next 。条件中的 p->next 就是要保证 第 i 个元素存在，否则无法删除。若写成 p->next && j==i-1 也不妥，因为此时(循环 结束时)可能有 p==NULL，所以必须先确定 p 不空。技巧：将条件中的“大前提”放 在前面。该条件也不可以写成 p->next && p && j==i-1，因为先有 p!=0 才有 p->next， 上式颠倒了这一关系。 c) 释放结点的方法。 free(s); d) 完成删除的步骤：①②。 (8) 建立链表的两种方法 思路： 建立空表（头结点）； 依次插入数据结点（每次插入表尾得(a1,a2,.,an)，每次插入表头得(an,.,a2,a1)）。 1°. 顺序建表 void CreateLinkList ( LinkList &L, int n) { // 建立空表 L = (LinkList) malloc(sizeof(LNode)); L->next = NULL; // 空表 p = L; // 用 p 指向表尾 // 插入元素 for ( i=0; i<n; i++ ) { scanf ( x ); ai-1 · - 删除前 ai · - p · - s ai-1 · - 执行①之后 ai · - p · - ① s ai-1 · - 执行②之后 ai · - p · - ① ②
s=(LinkList) malloc(sizeof(LNode);s->data = x:Ⅱ插入表尾s->next = p->next;p->next = s;1新的表尾p=s,172°逆序建表void CreateLinkList(LinkList&L,intn)1Ⅱ建立空表L= (LinkList) malloc(sizeof(LNode);L->next=NULL; I空表1插入元素for(i=0; i<n, i++)scanf(x)s = (LinkList) malloc(sizeof(LNode);s->data = x1插入表头s->next=L->nextL->next = s;114.循环链表(1) 特点最后一个结点的指针指向头结点。(2)类型定义同单链表。(3）基本形态空表：L->next=-L。aian非空表。(4）与单链表的联系判断表尾的方法不同：单链表用p=-NULL；循环链表用p—L。其余操作相同。-16 -
- 16 - s = (LinkList) malloc(sizeof(LNode)); s->data = x; // 插入表尾 s->next = p->next; p->next = s; p = s; // 新的表尾 } } 2°. 逆序建表 void CreateLinkList ( LinkList &L, int n) { // 建立空表 L = (LinkList) malloc(sizeof(LNode)); L->next = NULL; // 空表 // 插入元素 for ( i=0; i<n; i++ ) { scanf ( x ); s = (LinkList) malloc(sizeof(LNode)); s->data = x; // 插入表头 s->next = L->next; L->next = s; } } 4. 循环链表 (1) 特点 最后一个结点的指针指向头结点。 (2) 类型定义 同单链表。 (3) 基本形态 空表：L->next == L。 非空表。 (4) 与单链表的联系 判断表尾的方法不同：单链表用 p==NULL；循环链表用 p==L。 其余操作相同。 an C B A ( b ) (a ) E L a1 . L
5.双向循环链表(1)特点一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链表。(2类型定义typedef struct DuLNode tDataTypedatadatapriornextstructDuLNode*prior,*next;I/两个指针DuLNode, *DuLinkList,(3)基本形态空表：用后向指针判断L->next=L，或者用前向指针判断L->prior==L。非空表。Lar（4）与单链表和循环链表的联系最大不同：前驱容易求得，可以向前遍历。判断表尾的方法与循环链表相同：PL。插入和删除时需要修改两个方向的指针。(5)插入和删除需要修改两个方向的指针。例如：（见下表）表2.2双向循环链表的插入和删除p之前插入s删除p之后继s删除pp之后插入ss->next = p->next, 1s->priors=p->next,p->prior->nextp->next = s;p->prior,p->next = s->next;p->next;二s->prior =p;p->prior = s;p->next->priorp->next->prior=p;s->next->prior = s,s->next = p,p->prior,s->prior->next=s,6.顺序表与单链表的比较表2.3顺序表和单链表的比较顺序表单链表以地址相邻表示关系用指针表示关系随机访问，取元素O(1)顺序访问，取元素O(n)插入、删除不用移动元素O(n)(用于查找插入、删除需要移动元素O(n)- 17 -
- 17 - 5. 双向循环链表 (1) 特点 一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链 表。 (2) 类型定义 typedef struct DuLNode { DataType data; struct DuLNode *prior, *next; // 两个指针 } DuLNode, *DuLinkList; (3) 基本形态 空表：用后向指针判断 L->next == L，或者用前向指针判断 L->prior == L。 非空表。 (4) 与单链表和循环链表的联系 最大不同：前驱容易求得，可以向前遍历。 判断表尾的方法与循环链表相同：p==L。 插入和删除时需要修改两个方向的指针。 (5) 插入和删除 需要修改两个方向的指针。例如：(见下表) 表 2.2 双向循环链表的插入和删除 p 之后插入 s p 之前插入 s 删除 p 之后继 s 删除 p s->next = p->next; p->next = s; s->prior = p; s->next->prior = s; s->prior = p->prior; p->prior = s; s->next = p; s->prior->next = s; s = p->next; p->next = s->next; p->next->prior = p; p->prior->next = p->next; p->next->prior = p->prior; 6. 顺序表与单链表的比较 表 2.3 顺序表和单链表的比较 顺序表 单链表 以地址相邻表示关系 用指针表示关系 随机访问，取元素 O(1) 顺序访问，取元素 O(n) 插入、删除需要移动元素 O(n) 插入、删除不用移动元素 O(n)(用于查找 L L a1 a2 an . . data prior next
位置)总结：需要反复插入、删除，宜采用链表；反复提取，很少插入、删除，宜采用顺序表。二、习题2.1将顺序表中的元素反转顺序。2.2在非递减有序的顺序表中插入元素×，并保持有序。2.3删除顺序表中所有等于×的元素。2.4编写算法实现顺序表元素唯一化（即使顺序表中重复的元素只保留一个），给出算法的时间复杂度。2.5非递减有序的顺序表元素唯一化(参见习题2.4)，要求算法的时间复杂度为O(n)。2.6将单链表就地逆置，即不另外开辟结点空间，而将链表元素翻转顺序。2.7采用插入法将单链表中的元素排序。2.8采用选择法将单链表中的元素排序。2.9将两个非递减有序的单链表归并成一个，仍并保持非递减有序。-18-
- 18 - 位置) 总结：需要反复插入、删除，宜采用链表；反复提取，很少插入、删除，宜采用顺序 表。 二、习题 2.1 将顺序表中的元素反转顺序。 2.2 在非递减有序的顺序表中插入元素 x，并保持有序。 2.3 删除顺序表中所有等于 x 的元素。 2.4 编写算法实现顺序表元素唯一化(即使顺序表中重复的元素只保留一个)，给出算法的 时间复杂度。 2.5 非递减有序的顺序表元素唯一化(参见习题 2.4)，要求算法的时间复杂度为 O(n)。 2.6 将单链表就地逆置，即不另外开辟结点空间，而将链表元素翻转顺序。 2.7 采用插入法将单链表中的元素排序。 2.8 采用选择法将单链表中的元素排序。 2.9 将两个非递减有序的单链表归并成一个，仍并保持非递减有序
第3章栈和队列一、基础知识和算法1.栈栈，栈顶，栈底，空栈，后进先出(LIFO)，入栈(Push)，出栈(Pop)。顺序栈：栈的顺序存储结构；链栈：栈的链式存储结构。2.链栈(1)存储结构用不带头结点的单链表实现。saa(2)类型定义同单链表。(3）基本形态1°栈空条件：S=-NULLSΛ2°栈非空Stanan-1ai3°栈满（一般不出现）(4)基本算法1°入栈Push(&s,x)bool Push(LinkList&s,DataTypex):I新建结点- 19 -
- 19 - 第3章 栈和队列 一、基础知识和算法 1. 栈 栈，栈顶，栈底，空栈，后进先出(LIFO)，入栈(Push)，出栈(Pop)。 顺序栈：栈的顺序存储结构；链栈：栈的链式存储结构。 2. 链栈 (1) 存储结构 用不带头结点的单链表实现。 (2) 类型定义 同单链表。 (3) 基本形态 1°. 栈空 条件: S == NULL 2°. 栈非空 3°. 栈满（一般不出现） (4) 基本算法 1°. 入栈 Push (&s, x) bool Push ( LinkList &s, DataType x ) { // 新建结点 S an an . a1 /\ -1 S /\ S an an . a1 /\ -1