⑴ 數據結構的循環鏈表實驗
#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;
}