算法与数据结构_张晨光_第2章1

1、第二章 线性表 线性结构 w 在数据元素的非空的有限集合中：在数据元素的非空的有限集合中： n存在唯一的一个被称为存在唯一的一个被称为“第一个第一个”的数据元的数据元 素；素； n存在唯一的一个被称为存在唯一的一个被称为“最后一个最后一个”的数据的数据 元素；元素； n除第一个元素外，集合中每个元素都有且仅除第一个元素外，集合中每个元素都有且仅 有一个前驱；有一个前驱； n除最后一个元素外，集合中每个元素都有且除最后一个元素外，集合中每个元素都有且 仅有一个后继；仅有一个后继； 线性表(Linear List)定义 w 定义：定义： n个具有相同特性的数据元素组成的有限 序列； w 表示：表示

2、：a1,ai-1,ai,ai+1,an w ai必须具有相同特性，即属于同一数据对象 w ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素 w 数据元素ai在线性表中有确定的位置i，i称为位 序 w 线性表中数据元素的个数n称为线性表的长 度,n=0时，线性表称为空表 抽象数据类型定义 ADT LinearList 数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：数据关系：R=|ai,ai-1D,i=2,n 基本操作：基本操作： virtual int Length() const = 0;/求表长度 virtual int Search(T x)

3、const = 0; /搜索 virtual E* getData(int i) const = 0; /取值 virtual void setData(int i, E x) = 0; /赋值 virtual bool Insert(int i, E x) = 0; /插入 virtual bool Remove(int i, E /删除 virtual bool IsEmpty() const = 0; /判表空 virtual bool IsFull() const = 0; /判表满 ADT LinearList 线性表举例1（遍历线性表）遍历线性表） ListTraverse(Lin

4、earList L，visit() /遍历线性表遍历线性表 if(L. IsEmpty() printf(“空表空表”); else for(i=1;i=L.Length();i+) visit(L.getData(i) )； 线性表举例2（合并线性表）合并线性表） LinearList ListMerge(LinearList La,LinearList Lb) /La/La和和LbLb是两个非递减有序的线性表，将线性表是两个非递减有序的线性表，将线性表LaLa和和LbLb合并合并 成一个新的线性表成一个新的线性表LcLc，LcLc也非递减有序。也非递减有序。 LinearList Lc i

5、=j=1;k=0; La_len=La.Length();Lb_len=Lb.Length(); while(i=La_len) bj=Lb.getData(j); if(ai=bj)Lc.Insert(+k,ai);+i; else Lc.Insert(+k,bj);+j; 线性表举例2（合并线性表）合并线性表） while(i=La_len) /Lb已空，将已空，将La表的剩余部分复制到新表表的剩余部分复制到新表 ai=La.getData(i+); Lc.Insert(+k,ai); while(j=Lb_len) /La已空，将已空，将Lb表的剩余部分复制到新表表的剩余部分复制到新表

6、bj=Lb.getData(j+); Lc.Insert(+k,bj); return(Lc); /ListMerge 逻辑结构是本质 通过上面两个例子可以看出： w 逻辑结构是数据组织的某种“本质性” 的东西： （1）逻辑结构与数据元素本身的形式、内容无关。）逻辑结构与数据元素本身的形式、内容无关。 （2）逻辑结构与数据元素的相对位置无关。）逻辑结构与数据元素的相对位置无关。 （3）逻辑结构与所含数据元素的个数无关。）逻辑结构与所含数据元素的个数无关。 w 算法的设计取决于选定的逻辑结构，算法的设计取决于选定的逻辑结构， 而算法的实现依赖于采用的存储结构而算法的实现依赖于采用的存储结构 线性

7、表的顺序表示和实现 线性表的顺序表示线性表的顺序表示 : :线性表的顺序存储是指在内存中线性表的顺序存储是指在内存中 用地址连续的一块存储空间顺序存放线性表的各元素，用地址连续的一块存储空间顺序存放线性表的各元素， 用这种存储形式存储的线性表称为用这种存储形式存储的线性表称为顺序表顺序表。 设设 a a 的存储地址为 的存储地址为Locate(a(a ) )，每个数据元素占 ，每个数据元素占L L个个 存储单元，则第存储单元，则第i i个数据元素的地址为：个数据元素的地址为： Locate(a(ai i)=)=Locate(a(a1 1)+(i)+(i- -1)1)* *L 1L 1i in

8、n 0 1 i-1 i n-1 MAXSIZE-1 a a1 1a a2 2a ai ia an n datadata a ai-1i-1a ai+1 i+1 w 顺序存储结构的线性表的类型定义如下：顺序存储结构的线性表的类型定义如下： #define maxSize 100 typedef int T; typedef struct T datamaxSize; /顺序表的静态存储表示 int n; SeqList; w 或者：或者： typedef int T; typedef struct T *data; /顺序表的动态存储表示 int maxSize, n; SeqList; 顺序表

9、顺序表(SeqList)(SeqList)类的定义类的定义 #include /定义在“seqList.h”中 #include #include LinearList.h const int defaultSize = 100; template class SeqList: public LinearList protected: E *data; /存放数组 int maxSize; /最大可容纳表项的项数 int n; /当前已存表项数 void reSize(int newSize);/改变数组空间大小 public: SeqList(int sz = defaultSize); /

10、构造函数 SeqList(SeqList /复制构造函数 SeqList() delete data; /析构函数 int Size() const return maxSize; /求表最大容量 int Length() const return n; /计算表长度 int Search(T x) const; /搜索x在表中位置，函数返回表项序号 int Locate(int i) const; /定位第 i 个表项，函数返回表项序号 bool Insert(int i, E x);/插入 bool Remove(int i, E/删除 ; 顺序表上基本运算的实现:构 造函数和拷贝构造函数

11、 顺序表的初始化顺序表的初始化 : : #include #include “seqList.h” template SeqList:SeqList(int sz) if (sz 0) maxSize = sz; n = 0; data = new EmaxSize; /创建表存储数组 if (data = NULL) /动态分配失败 cerr 存储分配错误！ endl; exit(1); ; template SeqList:SeqList ( SeqList n = L.Length(); data = new EmaxSize;/创建存储数组 if (data = NULL)/动态分配失

12、败 cerr 存储分配错误！ endl; exit(1); for (int i = 1; i = n; i+) /传送各个表项 datai-1 = L.getData(i); ; 复制构造函数复制构造函数 基本操作：顺序表的搜索算法基本操作：顺序表的搜索算法 template int SeqList:search(T i = n; i+)/顺序搜索 if ( datai-1 = x ) return i; /表项序号和表项位置差1 return 0; /搜索失败 ; w 搜索成功的平均比较次数搜索成功的平均比较次数 pi 是搜索第是搜索第 i 项的概率项的概率 ci 是找到时的比较次数是找到

13、时的比较次数 w 若搜索概率相等，则若搜索概率相等，则 w 搜索不成功搜索不成功 数据比较数据比较 n 次次 i n i i cp 1 =ACN 2 1 2 )(11 )2(1 11 = 1 nnn n n n i n n i ACN 搜索性能分析搜索性能分析 基本操作：顺序表的插入算基本操作：顺序表的插入算 法法 插入运算插入运算: :在第在第 i 个位置，插入元素个位置，插入元素e 思想：思想：把从第把从第i个位置开始的元素，依次后移个位置开始的元素，依次后移 步骤：步骤： 1.当前表是否已经满？当前表是否已经满？ 2.输入是否有效？输入是否有效？ 3.插入元素。插入元素。 表项的插入表项

14、的插入 25 34 57 16 48 09 63 0 1 2 3 4 5 6 7 data 50插入 x 25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7 data50 i 表项的插入算法表项的插入算法 template bool SeqList:Insert (int i, E x) /将新元素x插入到表中第i (1in+1) 个表项位 /置。函数返回插入成功的信息 if (n = maxSize) return false; /表满 if (i n+1) return false; /参数i不合理 for (int j = n; j = i; j-) /依次后

15、移 dataj = dataj-1; datai-1 = x; /插入(第 i 表项在datai-1处) n+; return true; /插入成功 ; 时间复杂度：时间复杂度：O(n) 基本操作：删除基本操作：删除 删除运算删除运算: :删除第删除第 i 个元素个元素e 思想：思想：把第把第i1个位置开始的元素，依次前移个位置开始的元素，依次前移 步骤：步骤： 1.要检查删除位置的有效性；要检查删除位置的有效性； 2.依次移动元素；依次移动元素； 3.长度减长度减1。 顺序表上基本运算的实现(3) void SeqListDelete(SeqList L,int i) /删除顺序表中的第删

16、除顺序表中的第i个元素个元素 if(iL.length) printf(“位置非法位置非法”) exit(0); /检查空表及删除位置的合法性检查空表及删除位置的合法性 for(j=i;j=L.length-1;j+) L.dataj-1=L.dataj; /向上移动向上移动 L.length-; /顺序表长度减顺序表长度减1 时间复杂度：时间复杂度： O(n) 删除元素删除元素 : : 表项的删除表项的删除 25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7 data16 删除 x 25 34 57 50 48 09 63 0 1 2 3 4 5 6 7 data

17、 表项的删除算法表项的删除算法 template bool SeqList:Remove (int i, E /表空 if (i n) return false; /参数i不合理 x = datai-1; for (int j = i; j link = p; w p-link = q; 上面四句话代表什么意思？ 带头结点的单链表 w 通常情况下，为了运算的统一，常在第一个结点前附设通常情况下，为了运算的统一，常在第一个结点前附设 一个结点，称为一个结点，称为“头结点头结点”，头指针具有标识作用，因，头指针具有标识作用，因 而，常用作链表的名字而，常用作链表的名字 ListNode *p= n

18、ew ListNode; 则完成了申请一块则完成了申请一块ListNode类型的存储单元的操作，类型的存储单元的操作， 并将其地址赋值给变量并将其地址赋值给变量p p。 H(a) a1a2an H (b) P p-data p-next 链表类 class List /链表类, 直接使用链表结点类的数据和操 作 private: ListNode *first; /表头指针 ; 用模板定义的单链表类用模板定义的单链表类 template /定义在“LinkedList.h” struct LinkNode /链表结点类的定义 E data; /数据域 LinkNode *link; /链指针域

19、 LinkNode() link = NULL; /构造函数 LinkNode(E item, LinkNode *ptr = NULL) data = item; link = ptr; /构造函数 bool operator= (E x) return data.key = x; /重载函数，判相等 bool operator != (E x) return data.key != x; ; template class List : public LinearList /单链表类定义, 不用继承也可实现 protected: LinkNode *first; /表头指针 public:

20、List() ; /构造函数 List(E x) first = new LinkNode(x); List( List/复制构造函数 List() /析构函数 void makeEmpty();/将链表置为空表 int Length() const;/计算链表的长度 LinkNode *Search(E x); /搜索含x元素 LinkNode *Locate(int i);/定位第i个元素 E *getData(int i);/取出第i元素值 void setData(int i, E x);/更新第i元素值 bool Insert (int i, E x); /在第i元素后插入 bool

21、 Remove(int i, E /删除第i个元素 bool IsEmpty() const /判表空否 return first-link = NULL ? true : false; LinkNode *getFirst() const return first; void setFirst(LinkNode *f ) first = f; void Sort(); /排序 ; 线性链表操作的实现(1) template List:List() /建立一个空的单链表建立一个空的单链表 first = new LinkNode; 带头结点的单链表的初始化：带头结点的单链表的初始化： firs

22、t p a0a1a2 c = 0 first p a0a1a2 c = 1 first p a0a1a2 c = 2 first p a0a1a2 c = 3 线性链表操作的实现(2) 求表长求表长: : template int List : Length ( ) const ListNode *p = first-link; /检测指针 p 指示第一号结点 int count = 0; while ( p != NULL ) /逐个结点检测 p = p-link; count+; return count; 取第取第i i个元素个元素: : 线性链表操作的实现(3) template Li

23、nkNode *List:Locate ( int i ) /函数返回表中第 i 个元素的地址。若i 0或 i 超 /出表中结点个数，则返回NULL。 if (i 0) return NULL;/i不合理 LinkNode *current = first; int k = 0; while ( current != NULL k+; return current; /返回第 i 号结点地址或NULL ; 线性链表操作的实现(4) template LinkNode *List:Search(E x) /在表中搜索含数据x的结点, 搜索成功时函数返 /该结点地址; 否则返回NULL。 Link

24、Node *current = first-link; while ( current != NULL /沿着链找含x结点 return current; ; 按值查找按值查找: : 线性链表操作的实现(5) LinkedList LinkedListLocate(LinkedList L, LinkedList p) /在单链表在单链表L中求中求p p指向的结点指向的结点( (假定存在）的前驱假定存在）的前驱 if(L-next=p)printf(“p p指向第一元素结点，指向第一元素结点， 无前驱无前驱”);exit(0); pre=L; pre=L; while(pre!=NULL if

25、(pre) return pre; else return null; 查找结点的前驱查找结点的前驱: : 线性链表操作的实现(6) LinkedList LinkedListLocate(LinkedList L, LinkedList p) /在单链表在单链表L中求中求p p指向的结点指向的结点( (假定存在）的后继假定存在）的后继 pre=L;pre=L; while(pre!=NULL if(p-next=null)printf(“p p指向最后元素指向最后元素 结点，无后继结点，无后继”);exit(0); else return p; 查找结点的后继查找结点的后继: : 线性链表操

26、作的实现(7) newNode表示当前结点，表示当前结点，current 表示前一个结点。表示前一个结点。 在在current 后插入元素插入元素newNode newNode-link= current -link; current -link= newNode; aklink 插入元素：插入元素： ai-1linkailink current 线性链表操作的实现(7) 插入算法插入算法: template bool List:Insert (int i, E x) /将新元素 x 插入在链表中第 i 个结点之后。 LinkNode *current = Locate(i); if (cur

27、rent = NULL) return false; /无插入位置 LinkNode *newNode = new LinkNode(x); /创建新结点 newNode-link = current-link; /链入 current-link = newNode; return true; /插入成功 ; 线性链表操作的实现(8) del 表示当前结点，表示当前结点，current 表示前一个结点。表示前一个结点。 LinkNode *del = current-link; current-link = del-link; delete del ; 删除元素删除元素: ai-1linkai

28、linkai+1link 线性链表操作的实现(8) 删除元素删除元素: template bool List:Remove (int i, E if ( current = NULL | current-link = NULL) return false; /删除不成功 LinkNode *del = current-link; current-link = del-link; x = del-data;delete del; return true; ; 线性链表操作的实现(9) 建立单链表头插法建立单链表头插法: L 36 L 36 45 L 103645 L 23103645 L 36

29、451023 67 L 线性链表操作的实现(9) template void inputFront (T endTag) LinkNode *newNode; T val; makeEmpty(); cin val; while (val != endTag) newNode = new LinkNode(val); if (newNode = NULL)cerrErrorlink = first-link; /插在表前端 first-link = newNode; cin val; ; 头插法建立单链表算法头插法建立单链表算法: 线性链表操作的实现(10) 建立单链表尾插法建立单链表尾插法:

30、 67 r L 2367 r L 102367 r L 36 45102367 r L 45102367 r L 线性链表操作的实现(10) LinkedList LinkedListCreat3( ) /用尾插法建立带头结点的单链表用尾插法建立带头结点的单链表 LinkedList L; L=(LNode*)malloc(sizeof(LNode); L-next=NULL; r=L; scanf( while (x!=flag) /设置结束标志设置结束标志 p=(LNode*)malloc(sizeof(LNode); p-data=x; /赋值元素值赋值元素值 p-next=r-next

31、; r-next=p; /在尾部插入新结点在尾部插入新结点 r=p; /r 指向新的尾结点指向新的尾结点 scanf( r-next=NULL; /最后结点的指针域放空指针最后结点的指针域放空指针 return L; 尾插法建立单链表算法尾插法建立单链表算法: 链表的遍历 void print(LinkedList la) /void print(LinkedList la) /非递归非递归 LinkedList p=la-next;LinkedList p=la-next; while (p) while (p) printf(“%c”,p-data); printf(“%c”,p-data

32、); p=p-next; p=p-next; void out(LinkedList p) /void out(LinkedList p) /递归递归 if(p)if(p) out(p-next); out(p-next); printf(“%c”,p-data); printf(“%c”,p-data); 链表算法举例1 请写一个算法将单链表（a1,.,an）逆置为(an,.,a1)。 LinkedList invert1(LinkedList head） /*逆置单链表*/ LinkedList p=head-next; /p为工作指针 head-next=null；/将头结点的指针域置空

33、 while（p!=null） r=p-next； /暂存p的后继 p-next=head-next； head-next=p； p=r； return（head）； /结束invert1函数 链表算法举例2 在一个非递减有序的线性表中，有数值相同的元素存在。若存储方式为在一个非递减有序的线性表中，有数值相同的元素存在。若存储方式为 单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。分析算单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。分析算 法的时间复杂度。法的时间复杂度。 LinkedList DelSame(LinkedList la） /la是非递减有序的单链表，

34、本算法去掉数值相同的元素，使表是非递减有序的单链表，本算法去掉数值相同的元素，使表 中不再有重复的元素。中不再有重复的元素。 p=la-next-next； /p是工作指针。设链表中至少有一个结点是工作指针。设链表中至少有一个结点 pre=la-next； /pre是是p所指向结点的前驱结点的指针。所指向结点的前驱结点的指针。 while（p!=null） if（pre-data=p-data） /处理相同元素值的结点处理相同元素值的结点 u=p；p=p-next；free(u); /释放相同元素值的结点释放相同元素值的结点 else /处理前驱，后继元素值不同处理前驱，后继元素值不同 pre

35、-next=p；pre=p；p=p-next； pre-next=p；/置链表尾置链表尾 return (la); 算法时间复杂度为算法时间复杂度为O(n) 链式结构的特点 w 非随机存贮结构，所以取表元素要慢于顺非随机存贮结构，所以取表元素要慢于顺 序表。序表。 n节约了大块内存 w 适合于插入和删除操作适合于插入和删除操作 n实际上用空间换取了时间，结点中加入 了指针，使得这两种操作转换为指针操 作; 线性表实现方法的比较 w 实现不同实现不同 n顺序表方法简单，各种高级语言中都有数组类型，顺序表方法简单，各种高级语言中都有数组类型， 容易实现；链表的操作是基于指针的，相对来讲复容易实现；

36、链表的操作是基于指针的，相对来讲复 杂些。杂些。 w 存储空间的占用和分配不同存储空间的占用和分配不同 n从存储的角度考虑，顺序表的存储空间是静态分配从存储的角度考虑，顺序表的存储空间是静态分配 的，在程序执行之前必须明确规定它的存储规模，的，在程序执行之前必须明确规定它的存储规模， 也就是说事先对也就是说事先对“MAXSIZE”要有合适的设定，过要有合适的设定，过 大造成浪费，过小造成溢出。而链表是动态分配存大造成浪费，过小造成溢出。而链表是动态分配存 储空间的，不用事先估计存储规模。可见对线性表储空间的，不用事先估计存储规模。可见对线性表 的长度或存储规模难以估计时，采用链表。的长度或存储

37、规模难以估计时，采用链表。 w 线性表运算的实现不同线性表运算的实现不同 n按序号访问数据元素，使用顺序表优于链表。按序号访问数据元素，使用顺序表优于链表。 n插入删除操作插入删除操作 ，使用链表优于顺序表。，使用链表优于顺序表。 循环链表 单循环链表单循环链表: : 循环链表：循环链表：链表尾链表尾结点的指针域指向结点的指针域指向头结点头结点。 这样形成的链表我们叫做循环链表。这样形成的链表我们叫做循环链表。 (a)非空表非空表 a1 Han (b)空表空表 H 循环链表往往只设尾指针循环链表往往只设尾指针 template struct CircLinkNode /链表结点类定义 E da

38、ta; CircLinkNode *link; CircLinkNode ( CircLinkNode *next = NULL ) link = next; CircLinkNode ( E d, CircLinkNode *next = NULL ) data = d; link = next; bool Operator=(E x) return data.key = x.key; bool Operator!=(E x) return data.key != x.key; ; 循环链表类的定义循环链表类的定义 template /链表类定义 class CircList : publi

39、c LinearList private: CircLinkNode *first, *last; /头指针, 尾指针 public: CircList(const E x); /构造函数 CircList(CircList /复制构造函数 CircList(); /析构函数 int Length() const; /计算链表长度 bool IsEmpty() return first-link = first; /判表空否 CircLinkNode *getHead() const; /返回表头结点地址 void setHead ( CircLinkNode *p ); /设置表头结点地址

40、CircLinkNode *Search ( T x );/搜索 CircLinkNode *Locate ( int i );/定位 E *getData ( int i ); /提取 void setData ( int i, E x ); /修改 bool Insert ( int i, E x ); /插入 bool Remove ( int i, E /删除 ; w 循环链表与单链表的操作实现，最主要的不同就循环链表与单链表的操作实现，最主要的不同就 是扫描到链尾，遇到的不是是扫描到链尾，遇到的不是NULL，而是表头。，而是表头。 搜索不成功搜索不成功 循环链表的搜索算法循环链表的搜

41、索算法 搜索搜索25 搜索成功搜索成功 搜索搜索15 first31481557 current current current first31481557 current current current currentcurrent 循环链表的搜索算法循环链表的搜索算法 template CircListNode * CircList:Search( E x ) /在链表中从头搜索其数据值为 x 的结点 current = first-link; while ( current != first return current; 用循环链表求解约瑟夫问题用循环链表求解约瑟夫问题 w约瑟夫问题的

42、提法约瑟夫问题的提法 n 个人围成一个圆圈，首先第个人围成一个圆圈，首先第 1 个人从个人从 1 开始，一个人一个人顺时针报数开始，一个人一个人顺时针报数, 报报 到第到第 m 个人，令其出列。然后再从下一个人，令其出列。然后再从下一 个人开始，从个人开始，从 1 顺时针报数，报到第顺时针报数，报到第 m 个人，再令其出列，个人，再令其出列，如此下去，如此下去, 直直 到圆圈中只剩一个人为止。此人即到圆圈中只剩一个人为止。此人即为优为优 胜者。胜者。 用不带表头结点的循环链表来组织。用不带表头结点的循环链表来组织。 例如例如 n = 8 m = 3 0 1 2 3 4 5 6 7 1 2 3

43、45 6 7 8 0 1 2 3 4 5 6 7 1 2 3 45 6 7 8 0 1 2 3 4 5 6 7 1 2 3 45 6 7 8 0 1 2 3 4 5 6 7 1 2 3 45 6 7 8 0 1 2 3 4 5 6 7 1 2 3 45 6 7 8 0 1 2 3 4 5 6 7 1 2 3 45 6 7 8 n = 8 m = 3 0 1 2 3 4 5 6 7 1 2 3 45 6 7 8 0 1 2 3 4 5 6 7 1 2 3 45 6 7 8 0 1 2 3 4 5 6 7 1 2 3 45 6 7 8 求解求解JosephusJosephus问题的算法问题的算法

44、#include #include “CircList.h” template void Josephus(CircList int i, j; for ( i = 0; i n-1; i+ ) /执行n-1次 for ( j = 1; j link; cout “出列的人是” data link = p-link; delete p; /删去 p = pre-link; ; void main() CircList clist; int i, n m; cout n m; for (i = 1; i lLink-data? w p-rLink-lLink? p-lLinkp-rLinkp l

45、LinkrLink template struct DblNode /链表结点类定义 E data;/链表结点数据 DblNode *lLink, *rLink; /前驱、后继指针 DblNode ( DblNode *l = NULL, DblNode *r = NULL ) lLink = l; rLink = r; /构造函数 DblNode ( E value, DblNode *l = NULL, DblNode *r = NULL) data = value; lLink = l; rLink = r; /构造函数 ; template class DblList /链表类定义 p

46、ublic: DblList ( E uniqueVal ) /构造函数 first = new DblNode (uniqueVal); first-rLink = first-lLink = first; ; DblNode *getFirst () const return first; void setFirst ( DblNode *ptr ) first = ptr; DblNode *Search ( T x, int d); /在链表中按d指示方向寻找等于给定值x的结点, /d=0按前驱方向,d0按后继方向 DblNode *Locate ( int i, int d ); /

47、在链表中定位序号为i(0)的结点, d=0按前驱方 /向,d0按后继方向 bool Insert ( int i, E x, int d ); /在第i个结点后插入一个包含有值x的新结点,d=0 /按前驱方向,d0按后继方向 bool Remove ( int i, E /删除第i个结点 bool IsEmpty() return first-rlink = first; /判双链表空否 private: DblNode *first; /表头指针 ; 搜索成功搜索成功 搜索不成功搜索不成功 first first 31 31 48 48 15 15 57 57 搜索搜索15 搜索搜索25 双

48、向循环链表的搜索算法双向循环链表的搜索算法 template DblNode *DblList:Search (T x, int d) /在双向循环链表中寻找其值等于x的结点。 DblNode *current = (d = 0)? first-lLink : first-rLink; /按d确定搜索方向 while ( current != first if ( current != first ) return current; /搜索成功 else return NULL; /搜索失败 ; 双向链表的插入 current newNode 1234 newNode-rLink = curr

49、ent-rLink; current-rLink = newNode; newNode-rLink-lLink = newNode; newNode-lLink = current; 双向循环链表的插入算法双向循环链表的插入算法 template bool DblList:Insert ( int i, E x, int d ) /建立一个包含有值x的新结点, 并将其按 d 指定的 /方向插入到第i个结点之后。 DblNode *current = Locate(i, d); /按d指示方向查找第i个结点 if ( current = NULL ) return false; /插入失败 Db

50、lNode *newNd = new DblNode(x); if (d = 0) /前驱方向:插在第i个结点左侧 newNd-lLink = current-lLink; /链入lLink链 current-lLink = newNd; 双向链表的删除 current 1 2 current-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink; 双向循环链表的删除算法双向循环链表的删除算法 template bool DblList:Remove( int i, E if (current = NULL) retu

51、rn false; /删除失败 current-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink; /从lLink链和rLink链中摘下 x = current-data; delete current; /删除 return true; /删除成功 ; 循环链表算法举例循环链表算法举例（1 1） 假设一个单循环链表，其结点含有三个域假设一个单循环链表，其结点含有三个域pre、data、 link。其中。其中data为数据域；为数据域；pre为指针域，它的值为空指针为指针域，它的值为空指针 （null）；）；lin

52、k为指针域，它指向后继结点。请设计算法，将为指针域，它指向后继结点。请设计算法，将 此表改成双向循环链表。此表改成双向循环链表。 void SToDouble（LinkedList la） / la是结点含有是结点含有pre，data，link三个域的单循环链表。其中三个域的单循环链表。其中 data为数据域；为数据域； pre为空指针域，为空指针域，link是指向后继的指针域。是指向后继的指针域。 本算法将其改造成双向循环链表。本算法将其改造成双向循环链表。 while（la-link-pre=null） la-link-pre=la/将结点将结点la后继的后继的pre指针指向指针指向la

53、la=la-link； /la指针后移指针后移 /算法结束算法结束 循环链表算法举例循环链表算法举例（2） 已知一双向循环链表，从第二个结点至表尾递增有序，已知一双向循环链表，从第二个结点至表尾递增有序， （设（设a1xan）如下图。试编写程序，将第一个结点删）如下图。试编写程序，将第一个结点删 除并插入表中适当位置，使整个链表递增有序除并插入表中适当位置，使整个链表递增有序 x a1 a2 an L 循环链表算法举例循环链表算法举例（2） void DInsert（） L是无头结点的双向循环链表，自第二结点起递增有序。本算法是无头结点的双向循环链表，自第二结点起递增有序。本算法 将第一结点（将第一结点（a1xrLink； 将第一结点从链表上摘下将第一结点从链表上摘下 p-lLink=first-prior；p-lLink-rLink=p； while（p-datarLink； 查插入位置查插入位置 s-rLink=p；s-lLink=p-lLink；插入原第一结插入原第一结 点点 p-lL