⑴ 数据结构的循环链表实验
#include<iostream.h>
#include<iomanip.h>
//25个人围成一圈，从第一个人开始顺序报号1、2、3、4。凡报到4者退出圈子
//找出最后留在圈子中的人的原来的序号
typedef struct Lnode{
int data;
struct Lnode *next;
}LNode,*LinkList;
void CreatList(LinkList &L,int n);
void Show(LinkList L);
void ShowList(LinkList L);
void main(){
int number;
LinkList L;
cout<<"多少个人围成的圈子:";
cin>>number;
CreatList(L,number);
cout<<"原圈子的样子:"<<endl;
ShowList(L);
Show(L);
}
void CreatList(LinkList &L,int n){//创建的链基庆迅表没有空的头节点
LinkList pc,p;
int num=1;
while(num<=n){
if(num==1){
L=new LNode;
L->data=1;
L->next=L;
pc=L;
}else{
p=new LNode;
p->data=num;
p->next=pc->next;
pc->next=p;
pc=p;
}
num++;
}
}
void ShowList(LinkList L){
LinkList p=L;
while(p->next!=L){
cout<<p->data<<setw(3);
p=p->next;
}//注意循环结束后还有最后一个元素没有显示出来搏此
cout<<p->data<<endl;
}
void Show(LinkList L){
LinkList pc=L;
LinkList pr;
int count=1;
int n=4;//
for(;pc->next!=pc;count++){//注意结束条件
if(n==0)
n=4;//注意回复n
if(count%n==0){ //注意修改下n
count=0;//注意count这一定要修*******
n--;//
pr->next=pc->差烂next;
if(pc==L)
L=pc->next;
delete pc;//free
pc=pr->next;//注意别忘了重新指定pc
ShowList(L);
}else{
pr=pc;
pc=pc->next;
}
}
cout<<"最后留在圈子里的人的号码是: "<<pc->data<<endl;
}
好了,一切ok
⑵ 【悬赏】数据结构，c语言，循环链表的问题！
在回答你们问题之前..我先把你的LinkList类型和LNode类型定义了..方便讲解
typedef struct NODE
{
int i;//假设这里是内容
struct NODE *next;/好扒/下一个节点连接
}LNODE;//定义了LNODE类型
typedef LNODE *LinkList;//定义了LinkList类型
问题1：头节点的next指向下一个节点的地址(不一定是最后一个节点的地址),而最后一个节点的next指针指向头节点的地址(因为这样才能形成环)
问题2:
不对;如果不考虑函数来创建循环列表..那么在main()函数中的创建代码应该为
LinkList head=NULL,p,q;//这里定义了头指针,并且初始化
p=q=head;
while (输入数字有效，否则停止)
{
//准备节点数据
p=(LinkList)malloc(sizeof(LNODE));//申请一个节点
p->i=你输入的数据;
p->next=NULL;//设为NULL..便于成为尾部时重复设置
if (head==NULL) head=p;//将表头设置为你才申请的地址
else q->next=p;//若头指针已经创建..那么连接下一个节点
q=p;//让q指向当前节点
}
//输入完成后..开始结成环..使之循环
q->next=head;//完成
问题3：
根据问题2创建的循环列表ha,hb,你会得到两个头指针ha,hb
p=ha;ha=hb-next;hb=p;
这样做相当于在hb这个环上第友搜昌二个节点(相对于表头)接了一个ha环(环和循环列表同义)..所以实质上没有改变
如果你要合并它们两个..方法很多..如果只是单纯的连接在一块并且在形成一个新的循环列表
以ha表头为准(因为表头保留了地址..当然你可以选择任何节点..但是需要先寻找)
p=ha->next;//保留下下一个节点的地址
ha->next=hb;//ha表头将连接到hb表头，此时ha环已经断开
断开hb环..此时只能断开首尾相接处.
假设你已经保留了尾节点地址q(这需要你用算法取得.)
那么
q->next=p;//让hb的尾节点和ha断开后的第二个节点相连接
这样就完整的把两个循环列表连接了成了一个循环列表...
问题4:
free(hb)只是释放一个节点而已..不会影响hb->next这个地址（节点）.因为hb和hb->next是两个独立的地址..
所以你要释放全部节点..
只需要遍历全表
将要释放的节点选出来..利用一个同类型变量来取值..然后依次释放..
综上:free(hb->next)只是下一个节点的释放..到最后..就是释放最后一个节点了..
PS:
从上面的描述..如果你要在其他函数中建立表..重新定义一个数据
typedef struct Link
{
LNODE *head;//这里完全就被封装了..提供了一个入口
int size;//记录循环表长度..
}Linklist;//这个类型就是一个入口.. 所以建立时需要判断入口是否建立..
typedef Linklist *LinkList;//这样可以产生漏野一个size伴随函数记录环的长度..便于你寻找尾节点.
当然上述在main()中完成的定义.你只需要定义一个变量来记录环的长度就行了..
后面的定义就不给代码了.因为很长..相信你以后学习到后面时也可以掌握后面的定义..
GOOD LUCK
⑶ 数据结构中循环链表是怎么实现的，对其指针的变化不理解
首穗旁先链表的概念你要理解啊， 链表一个节点里有数据和下一个节点的地址， 指针指向节点本身，或者指向下一个节点地址， 通过 p=p-》next 这种操作，就可以实现链表的遍历， 循环链表就是链表尾指向了链表头凳竖节点， 只猜粗橡要找到任意一个节点， 就可以遍历整个链表
⑷ 用数据结构实现附加头结点循环单链表的基本操作
直接复制粘贴到VC就是对的，根据注释，想要什么操作自己进行
#include<stdio.h>
#include<戚瞎stdlib.h>
#define Max 100
typedef struct node
{
int data;
struct node *link;
}LNode,*LinkList;
LinkList Creat();
int Length();
void Print();
LinkList Find();
LinkList InsertLink1();
void InsertLink2();
void InsertLink3();
void InsertLink4();
LinkList InsertLink5();
void DeleteLink1();
void DeleteLink2();
void DeleteList();
LinkList DeleteList2();
LinkList Invert();
LinkList Copy();
void LinkSort();
void Remove1();
int main()
{
int i=0,n,a[Max],item;
LinkList list=NULL,p=NULL;
scanf("%d"高李空,&item);
while(scanf("%d",&a[i])==1)
{
i++;
if(getchar()=='\n')
break;
}
n=i;
list=Creat(n,a);
Print(list);
//确定元素item在线性链表中的位置
p=Find(item,list);
//printf("%d\n",p->data);
/*
//在非空线性链表的第一个链结点前插入一个数据信息为item的链结点
list=InsertLink1(list,item);
Print(list);
//在非空线性链表的末尾插入一个数据信息为item的链结点
InsertLink2(list,item);
Print(list);
//在线性链表中由指针q指出的链结点后面插入一个数据信息为item的链结点
InsertLink3(list,item,p);
Print(list);
//在线性链表中第i个链结点后面插入一个数据信息为item的链结点
InsertLink4(list,item,2);
Print(list);
//在按值有序链接的线性链表中插入一个数据信息为item的链结点
InsertLink5(list,item);
Print(list);
//从非空线性扰老链表中删除q所指的链结点——不知道被删除结点q的直接前驱结点r
DeleteLink2(list,p);
Print(list);
//删除线性链表中数据域值为item的所有链结点
list=DeleteList2(list,item);
Print(list);
//逆转一个线性链表
list=Invert(list);
Print(list);
list=InsertLink5(list,item);
Print(list);
LinkSort(a,n);
*/
Remove1(list);
Print(list);
DeleteList(list);
return 0;
}
//建立一个线性链表
LinkList Creat(int n,int a[])
{
LinkList p,r,list=NULL;
int i;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=a[i];
p->link=NULL;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
return(list);
}
//求线性链表的长度
int Length(LinkList list)
{
LinkList p=list;
int n=0;
while(p!=NULL)
{
p=p->link;
n++;
}
return n;
}
//打印线性链表的元素
void Print(LinkList list)
{
LinkList p=list;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->link;
}
printf("\n");
}
//确定元素item在线性链表中的位置
LinkList Find(int item,LinkList list)
{
LinkList p=list;
while(p!=NULL)
{
if(item==p->data)
return p;
p=p->link;
}
return NULL;
}
//在非空线性链表的第一个链结点前插入一个数据信息为item的链结点
LinkList InsertLink1(LinkList list,int item)
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
p->data=item;
p->link=list;
list=p;
return list;
}
//在非空线性链表的末尾插入一个数据信息为item的链结点
void InsertLink2(LinkList list,int item)
{
LinkList p=list,q;
q=(LinkList)malloc(sizeof(LNode));
q->data=item;
q->link=NULL;
if(list==NULL)
list=q;
else
{
while(p->link!=NULL)
p=p->link;
p->link=q;
}
}
//在线性链表中由指针q指出的链结点后面插入一个数据信息为item的链结点
void InsertLink3(LinkList list,int item,LinkList q)
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
p->data=item;
p->link=q->link;
q->link=p;
}
//在线性链表中第i个链结点后面插入一个数据信息为item的链结点
void InsertLink4(LinkList list,int item,int i)
{
LinkList p=list,q;
int j=0;
q=(LinkList)malloc(sizeof(LNode));
q->data=item;
q->link=NULL;
while(j<i&&q!=NULL)
{
p=p->link;
j++;
}
q->link=p->link;
p->link=q;
}
//在按值有序链接的线性链表中插入一个数据信息为item的链结点
LinkList InsertLink5(LinkList list,int item)
{
LinkList p,q=list;
p=(LinkList)malloc(sizeof(LNode));
p->data=item;
p->link=NULL;
//如果链表为空或者item小于第一个链结点
if(list==NULL||item<list->data)
{
p->link=list;
list=p;
}
else
{
while(q->link!=NULL)
{
if(item<q->link->data)
break;
else
q=q->link;
}
p->link=q->link;
q->link=p;
}
return list;
}
//从非空线性链表中删除q所指的链结点——已知其前驱结点的地址为r
void DeleteLink1(LinkList list,LinkList r,LinkList q)
{
if(q==list)
list=q->link;
else
r->link=q->link;
free(q);
}
//从非空线性链表中删除q所指的链结点——不知道被删除结点q的直接前驱结点r
void DeleteLink2(LinkList list,LinkList q)
{
LinkList p=list;
if(q==list)
{
list=q->link;
free(q);
}
else
{
while(p->link!=NULL)
{
if(q==p->link)
{
p->link=q->link;
free(q);
}
else
p=p->link;
}
}
}
//销毁一个线性链表
void DeleteList(LinkList list)
{
LinkList p=list;
while(p!=NULL)
{
list=p->link;
free(p);
p=list;
}
}
//删除线性链表中数据域值为item的所有链结点
LinkList DeleteList2(LinkList list,int item)
{
LinkList q=list,p=q->link;
while(p!=NULL)
{
if(p->data==item)
{
q->link=p->link;
free(p);
p=q->link;
}
else
{
q=q->link;
p=p->link;
}
}
//第一个链结点满足条件
if(list->data==item)
{
q=list;
list=list->link;
free(q);
}
return list;
}
//逆转一个线性链表
LinkList Invert(LinkList list)
{
LinkList p,q,r;
p=list;
q=NULL;
while(p!=NULL)
{
r=q;
q=p;
p=p->link;
q->link=r;
}
list=q;
return list;
}
//复制一个线性链表
LinkList Copy(LinkList lista)
{
LinkList listb;
if(lista==NULL)
return NULL;
else
{
listb=(LinkList)malloc(sizeof(LNode));
listb->data=lista->data;
listb->link=lista->link;
}
return listb;
}
//利用线性链表进行数据排序
void LinkSort(int a[],int n)
{
LinkList p,list=NULL;
int i;
for(i=0;i<n;i++)
list=InsertLink5(list,a[i]);
p=list;
i=0;
while(p!=NULL)
{
a[i++]=p->data;
printf("%d ",a[i-1]);
p=p->link;
}
}
//已知某非空线性链表第一个链结点的指针为list，将链表中数据域值最大的那个链结点移至链表的末尾
//这是我的算法，只是移动了值
void Remove1(LinkList list)
{
LinkList p=list,temp=list;
int x;
while(p->link!=NULL)
{
if(p->data>p->link->data)
{
if(temp->data<p->data)
temp=p;
else
temp=temp;
}
p=p->link;
}
x=temp->data;
while(temp->link!=NULL)
{
temp->data=temp->link->data;
temp=temp->link;
}
temp->data=x;
}
//这是第二种算法，直接用链表的链接做的
void Remove2(LinkList list)
{
LinkList q=list,r=list,p=list->link,s;
while(p!=NULL)
{
if(p->data>q->data)
{
s=r;
q=p;
}
r=p;
p=p->link;
}
if(q!=r)
{
if(q==list)
list=list->link;
else
s->link=q->link;
r->link=q;
q->link=NULL;
}
}
⑸ 数据结构— 循环链表、双向(循环)链表
链表的两头连接，形成了一个环状链表，称为循环链表。
约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（以编号1，2，3，…，n分别表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，要求找到最后出列的那个人。
例如有 5 个人，要求从编号为 3 的人开始，数到 2 的那个人出列：
出列顺序依次为：
编号为 3 的人开始数 1，然后 4 数 2，所以 4 先出列；
4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；
1 出列后，从 2 开始数 1，3 数 2，所以 3 出列；
3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；
最后只剩下 5 自己，所以 5 出列。
循环链表和动态链表唯一不同在于它的首尾连接，这也注定了在使用循环链表时，附带的最多的操作就是遍历链表。在遍历的过程中，尤其要注意循环链表虽然首尾相连，但并不扰山表示该链表没有第一个节点和最后一个结点。所以，不要随意改变头指针的指向。
整个链表只能单方向从表头访问到表尾，这种结构的链表统称为 “单向链表”或“单链表”。
如果算法中需要频繁地找某结点的前趋结点，单链表的解决方式是遍历整个链表，增加算法的时间复杂度，影响整体效率。
为了快速便捷地解决这类问题，在单向链表的基础上，给各个结点额外配备一个指针变量，用于指向每个结点的直接前趋元素。这样的链表被称为“双向链表”或者“双链表”。
双向链表中的结点有两个指针域，一个指向直接前趋，一个指向直接后继。（链表中第一个结点的前趋结点为NULL，最后一个结点的后继结点为NULL）
结点的具体构成：
双向链表创建的过程中，每一个结点需要初始化数据域和两个指针域，一个指向直接前趋结点，另一个指向直接后继结点。
创建一个双向链表line（1，2，3）：
比如在（1，2，3）中插入一个结点 4，变成（1，4，2，3）。
实现效果图：
在双向链表中插入数据时，首先完成图中标注为 1 的两步操作，然后完成标注为 2 的两步操作；反之，如果先完成 2，就无法通过头指针访问结点 2，需要额外增设指针，虽然能实现，但较前一种麻烦。
双链表删除结点时，直接遍历链表，找到要删除的结点，然后利用该结点的两个指针域完成删除操作。
在（1，4，2，3）中删除结点 2：
双向链表的查找操作和单链表的实现方法完全一样，从链表的头结点或者首元结点开始遍历，正氏这里不做过多解释。
更改链表中某结点的数据域的操作是在查找的基础上完成的。通过遍历找到存储有该数据元素的结点后，直接更改其数据域就可以。
其实举李散就是双向链表和循环链表的结合体
例如：约瑟夫环问题其实还可以这样玩：如果顺时针报数，有人出列后，顺时针找出出列位置的下一个人，开始反方向（也就是逆时针）报数，有人出列后，逆时针找出出列位置的下一个人，开始顺时针报数。依次重复，直至最后一个出列。
有兴趣可以自行尝试，这里就不再分析了，因为本质就是双向链表和循环链表。
⑹ 数据结构 循环单链表
package e.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 e.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(i<-1 || i >size-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(i<0 || i>size)
{
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(i<0 || i>size-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(i<-1 || i>size-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 e.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) 编辑 收藏
⑺ 【悬赏】C语言，数据结构，循环链表问题！
1、指针指向一个结点是指枣行闷利用此指针可以直接访问这个结点，包括这带亏个结点的data和next所以指针指向最后一个结点，代表这个指针是最后一个结点的地址
2、循环链表是最后一个结点的next域指向头结点，上面的方法是尾插法建链表，新建的结点插在表尾，即为最后一个结点，所以每建一个，其next域就应修改为head
3、//La和Lb是两个仅设尾凳弯指针的循环链表
//将Lb合并到La的表尾，由La指示新表
void MergeList(LinkList * La,LinkList Lb)
{
LinkList p = Lb->next;
Lb->next = (* La)->next;
(* La)->next = p->next;
free(p);
(* La) = Lb;
}