线性表-循环链表-双向链表ppt课件.ppt

《线性表-循环链表-双向链表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构2013年秋季中国地质大学信息工程学院Chapter2线性表3目录线性表顺序表单链表线性链表的变形循环链表双向链表循环链表(CircularList)循环链表是单链表的变形。循环链表的最后一个结点的link指针不为NULL，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。循环链表的示例带表头结点的循环链表a0a1a2an-1firstan-1firsta1a0first(空表)(非空表)循环链表类的定义templatestructCircLinkNode{//

2、链表结点类定义Tdata;CircLinkNode*link;CircLinkNode(CircLinkNode*next=NULL){link=next;}CircLinkNode(Td,CircLinkNode*next=NULL){data=d;link=next;}boolOperator==(Tx){returndata.key==x.key;}boolOperator!=(Tx){returndata.key!=x.key;}};template//链表类定义classCircList{private:CircLinkNode

3、*first,*last;//头指针,尾指针public:CircList(constTx);//构造函数CircList(CircList&L);//复制构造函数～CircList();//析构函数intLength()const;//计算链表长度boolIsEmpty(){returnfirst->link==first;}//判表空否CircLinkNode*getHead()const;//返回表头结点地址voidsetHead(CircLinkNode*p);//设置表头结点地址CircLinkNode*Search(Tx);//搜

4、索CircLinkNode*Locate(inti);//定位T*getData(inti);//提取voidsetData(inti,Tx);//修改boolInsert(inti,Tx);//插入boolRemove(inti,T&x);//删除};循环链表与单链表的操作实现，最主要的不同就是扫描到链尾，遇到的不是NULL，而是表头。搜索不成功搜索25搜索成功搜索15first31481557currentcurrentcurrentfirst31481557currentcurrentcurrentcurrentcurrent循环链表的搜索算法t

5、emplateCircListNode*CircList::Search(Tx){//在链表中从头搜索其数据值为x的结点current=first->link;while(current!=first&¤t->data!=x)current=current->link;returncurrent;}循环链表的搜索算法rear3148155722如果插入与删除仅在链表的两端发生，可采用带表尾指针的循环链表结构。在表尾插入，时间复杂性O(1)在表尾删除，时间复杂性O(n)在表头插入，相当于在表尾插入在表头删除，时间复杂性O(1)带尾指针

6、的循环链表用循环链表求解约瑟夫问题约瑟夫问题的提法n个人围成一个圆圈，首先第1个人从1开始，一个人一个人顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。约瑟夫环示例例如n=8m=3012345671234567801234567123456780123456712345678012345671234567801234567123456780123456712345678n=8m=30123456712345678012345671234567801234567123

7、45678【数据结构设计】采用循环单链表【算法思想】2、寻找、输出、删除循环单链表的第m个节点：（1）从第一个节点开始，循链找到第m个节点；（2）输出该节点的值（data域中的内容）；（3）删除该节点；1、定义一个具有n个节点的循环单链表；（4）转至（1），从被删除节点的下一个节点开始，直到剩一个节点为止（需循环n-1次）。3、输出所剩节点的值。求解Josephus问题的算法#include#include“CircList.h”templatevoidJosephus(CircList