同济C C 软件基础 数据结构3费下载

1、 将单链表最后一个结点的link字段指向第一个结点就构成了循环链表circular list，一般的单链表只能访问某结点后面的结点,而循环链表从任一结点出发都可以访问所有的结点.如下所示：对于环链表：对于环链表：最后一个结点的最后一个结点的linklink值不再是值不再是NULL,NULL,而是表头指针而是表头指针first.first.可通过检查可通过检查 currentcurrentlink = firstlink = first 来判断当前指针来判断当前指针currentcurrent是否指向最后结点；是否指向最后结点；firsta1ai-1anai程序处理步骤程序处理步骤: :1 1、

2、建立环链。、建立环链。 通过通过void add(int i)void add(int i)函数将值为函数将值为i i的数据不断加到环链的的数据不断加到环链的 尾部尾部. .2 2、选择获胜者、选择获胜者. . 通过通过void josph(int n, int m)void josph(int n, int m)函数在含有函数在含有n n个结点的环个结点的环 链中从表头开始按步长链中从表头开始按步长m m顺时针删除顺时针删除n-1n-1个结点个结点. .具体步骤如下：具体步骤如下：(1)(1)当前工作指针指向表头结点。当前工作指针指向表头结点。current=headcurrent=head

3、(2)(2)当前指针向后移动当前指针向后移动m-1m-1次次 void move()void move()函数函数, ,其功能其功能: : 移动移动currentcurrent指针到下一结点并保存其原值到前驱指指针到下一结点并保存其原值到前驱指针针(3)current(3)current指向的结点出列并删除指向的结点出列并删除 int getdata()int getdata()函数获取出列结点的数据，函数获取出列结点的数据，void del()void del()函数将其指向结点从环链中删除函数将其指向结点从环链中删除(4)(4)重复执行重复执行(2)(3)(2)(3)步共步共n-1n-1次

4、最终次最终currentcurrent指向获胜者指向获胜者class node /定义结点类定义结点类 friend class Cirlist;/环链表类为环链表类为 其友元类其友元类 int data; node *next;public:node(int value)data=value;next=NULL;class Cirlist /定义环链表类定义环链表类node *head,*tail,*current,*pr; public: Cirlist() head=tail=NULL; void add(int n);/向表尾添加一结点向表尾添加一结点 void move();/工作指

5、针后移一位工作指针后移一位 void del();/删除当前指针指向的结点删除当前指针指向的结点 int getdata();/获取当前结点的数据获取当前结点的数据 void print(); void josph(int m,int n);/选获胜者选获胜者;根据分析，环链类设计如下：根据分析，环链类设计如下：currentcurrent代表当前工作指针代表当前工作指针prpr代表其前驱指针代表其前驱指针void Cirlist:add(int i) node *newnode; newnode= ; if(head=NULL) head=newnode ; ; else ; newnode

6、-next=head; ;成员函数的实现：成员函数的实现：void Cirlist:move()pr=current; ;void Cirlist:del() ; current=current-next;int Cirlist:getdata()return current-data;void Cirlist:print()node *p=head; while( )/不是最后一个结点不是最后一个结点 coutdatanext; coutdatanext=headtail-next=newnodetail=newnodecurrent=current-nextpr-next=current-

7、nextp-next!=headvoid Cirlist:josph(int n,int m)int i,j; current=head; for(i=0;in-1;i+)/删除删除n-1n-1个结点个结点 for(j=0;jm-1;j+)/定位第定位第m个结点个结点move(); coutgetdata()t;/输出出列结点输出出列结点 del();/删除第删除第m m个结点个结点 主函数主函数void main()Cirlist cl; int i,m,n; coutnm; for(i=1;i=n;i+) cl.add(i); cout环链内容为环链内容为:n; (); coutn出列顺序

8、为出列顺序为:; cl.josph(n,m); coutn获胜者获胜者:prior=p; s-next=p-next;p-next-prior=s;p-next=s; ai-1aipxs注意指针修改的注意指针修改的相对相对顺序顺序(2)(2)双链表的删除操作双链表的删除操作( (p-prior) )-next=p-next; ( (p-next) )-prior=p-prior; ai-1aipaidelete p; 作业作业定义一个带表头结点的单链表类，将该类说明为是结点类的友元类。结点类具有一个整数类型的数据成员和指向结点的指针。要求该链表类具有如下操作: void print() 输出链表中的全部结点. int max() 求链表结点中数据的最大值.