Question

循环单链表

1、有13个人围成一圈，并给他们从小到大进行编号1-13号，从第一个人开始循环报号1、2、3。凡报到“3”者退出圈子，找出最后留在圈子中的人原来的序号。
提示：
(1) 用循环单链表实现。
(2) 可以用一个函数建立初始链表。设置好头指针和尾指针，用尾插入法形成队列，再让最后一个结点指向第一个结点，形成循环链表。
(3) 退出圈子的过程可以用循环实现。按顺序访问链表，比如用count循环报号1、2、3，用i统计已经出列的人数。
(4) count计数到3则相应的结点要出队，注意删除结点的关键在于要先找出前驱结点的地址。然后可以使count重置为1，出列人数增加1. 如果出列人数已经为12，则退出循环。
(5) 可以在程序中输出出列的顺序，以方便检查程序是否已经正确。

Answer 1

///v6
#include "stdio.h"
#include <stdlib.h>

enum Status{OK,ERROR};

typedef int ElemType;

typedef struct Lnode
{
ElemType num;///结点元素类型为int
Lnode *next;///指向下一结点的指针
}LNode,*LinkList;

Status CreatLink(LinkList &L,int n)///创建n个人序号的链表
{
LinkList p;
LinkList head;
L = (LinkList)malloc(sizeof(LNode));///带头结点的链表
if (L == NULL)
{
return ERROR;
}
L->next = L;
head = L;

for (int i = 0; i < n; ++i)
{
p = (LinkList)malloc(sizeof(LNode));///生成新结点
if (p == NULL)
{
return ERROR;
}

p->num = i+1;
p->next = L;

head->next = p;///尾插法插入新结点
head = p;
}

return OK;
}

Status PrintLink(LinkList L)///打印链表
{

LinkList p = L->next;
LinkList q;
while (p != L)
{
q = p->next;
printf("最后剩的是%d\n",p->num);
p = q;
}

return OK;
}

Status DestroyLink(LinkList &L)//销毁链表
{
LinkList p = L->next;
LinkList q;
while (p != L)
{
q = p->next;
free(p);
p = q;
}

free(L);

return OK;
}

Status DelLink(LinkList &L,int n)///删除符合要求的结点
{

int i = 1;
int j = n;
LinkList Pre = L;///当前结点的前一结点指针
LinkList Pcur = Pre->next;///当前结点指针
LinkList q;
while ( j > 1)///当剩余人数大于1时继续删除
{
if (Pcur->next != L)///当当前结点指向的下一个结点不是空时
{
if (i == 3)
{
q = Pcur;
printf("%d ",Pcur->num);
Pre->next = Pcur->next;///删除当前结点前，把当前结点的下一个结点赋给前一结点的指针
Pcur = Pcur->next;///当前结点指针指向下一结点
i = 1;
--j;///人数减1
free(q);///释放当前结点
}
else
{
Pre = Pre->next;///不需要删除时，当前结点前一结点指向当前结点
Pcur = Pcur->next;///当前结点指向下一结点
++i;

}
}
else
{
if (i == 3)
{
q = Pcur;///当当前结点的下一个结点是空时
printf("%d ",Pcur->num);
Pre->next = Pcur->next;///删除当前结点前，把当前结点的下一个结点赋给前一结点的指针
i = 1;
--j;
free(q);
}
else
{

++i;

}

Pre = L;///当前结点的前一结点为头结点
Pcur = Pre->next;///当前结点

}

}

return OK;
}

int main()
{

LinkList L;
CreatLink(L,13);
DelLink(L,13);
PrintLink(L);
DestroyLink(L);

return 0;
}

Answer 2

package edu.cquptzx.List;
publicinterface List
{
publicvoid insert(int i ,Object obj) throws Exception; //插入
public Object delete(int i ) throws Exception; //删除
public Object getData(int i ) throws Exception; //获取i元素
publicint size(); //表数据总数
publicboolean isEmpty(); //是否为空

}
循环单链表实现:
package edu.cquptzx.List;

publicclass LoopLinkList implements List {
Node head;
Node current;
intsize;

LoopLinkList()
{
head = current = new Node(null);
head.next = head;
size =0;
}
/**
* 定位成员函数index(int i)的实现
* 循环从头开始查找,循环的条件是:1.定位完成j==i;2.链表查找结束了.
* @param i
* @throws Exception 当参数i错误时,抛出异常.
*/
publicvoid index(int i )throws Exception
{
if(isize-1)
{
thrownew Exception("i error in INDEX.");
}
if(i == -1) return;
current = head.next;
int j = 0;
while(current!=head && j<i)
{
current = current.next;
j++;
}
}
/**
* 插入节点算法:
* 1.调用index(i-1),让成员变量current指向第i-1个节点.
* 2.以obj,current.next为参数创建新的节点.
* 3.更改current指向,改为下一个节点.
* 4.表元素总数加1.
*/
publicvoid insert(int i, Object obj) throws Exception {
if(isize)
{
thrownew Exception ("i error in INSERT.");
}
index(i-1);
current.setNext(new Node(obj,current.next));
size++;
}

/**
* 删除节点算法:
* 1.调用index(i-1),让成员变量current指向第i-1个节点.
* 2.把第i个节点脱链:让第i-1个节点的next域等于第i个节点的next域.
* 3.数据元素总数size减1.
*/
public Object delete(int i) throws Exception {
if(size == 0)
{
thrownew Exception ("Link Blank in DELETE.");
}
if(isize-1)
{
thrownew Exception ("i error in DELETE.");
}
index(i-1);
Object obj = current.next.getElement();
current.setNext(current.next.next);
size--;
return obj;
}
/**
* 获取指定的元素
* 1.调用index(i),让成员变量current指向第i个节点.
* 2.返回该节点的数据域的值.
*/
@Override
public Object getData(int i) throws Exception {
// TODO Auto-generated method stub
if(isize-1)
{
thrownew Exception ("i error in getData.");
}
index(i);
returncurrent.getElement();
}

@Override
publicint size() {
// TODO Auto-generated method stub
returnsize;
}

@Override
publicboolean isEmpty() {
// TODO Auto-generated method stub
returnsize ==0;
}

}
循环单链表输出测试:
package edu.cquptzx.List;

publicclass LoopLinkListTest
{
publicstaticvoid main(String agrs[])
{
LoopLinkList lplklt = new LoopLinkList();
int n = 10;
try
{
for(int i = 0;i<n;i++)
{
lplklt.insert(i, new Integer(i+1));
}
lplklt.delete(4);
for(int i = 0;i<lplklt.size;i++)
{
System.out.print(lplklt.getData(i)+"...end ");
}
}
catch(Exception e)
{
System.out.println(e.getMessage());
}
}
}

输出结果:

分类: 数据结构-java标签: 循环单链表绿色通道： 好文要顶 关注我 收藏该文与我联系 淅沥枫
关注 - 6
粉丝 - 9 +加关注 1 0 (请您对文章做出评价) « 上一篇：单链表-数据结构-java实现
» 下一篇：双向链表-数据结构-java实现
posted @ 2012-10-06 17:59 淅沥枫 阅读(951) 评论(0) 编辑 收藏