單向循環(huán)鏈表

單向循環(huán)鏈表

1.定義結(jié)點(diǎn)

#define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */ typedef int Status;/* Status是函數(shù)的類(lèi)型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */ typedef int ElemType;/* ElemType類(lèi)型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

//定義結(jié)點(diǎn) typedef struct Node{ ? ? ElemType data;//數(shù)據(jù)域 ? ? struct Node *next;//指針域 }Node;

typedef struct Node *LinkList;

2.創(chuàng)建

2種情況:① 第一次開(kāi)始創(chuàng)建; ②已經(jīng)創(chuàng)建,往里面新增數(shù)據(jù)

?1. 判斷是否第一次創(chuàng)建鏈表

?YES->創(chuàng)建一個(gè)新結(jié)點(diǎn),并使得新結(jié)點(diǎn)的next 指向自身; (*L)->next = (*L);

?NO-> 找鏈表尾結(jié)點(diǎn),將尾結(jié)點(diǎn)的next = 新結(jié)點(diǎn). 新結(jié)點(diǎn)的next = (*L);

創(chuàng)建方法1

Status CreateList(LinkList *L) {

? ? intvalue =0;

? ? printf("輸入節(jié)點(diǎn)的值，輸入0結(jié)束\n");

? ? LinkListtemp =NULL;

? ? LinkListtarget =NULL;

? ? while(1) {

? ? ? ? //輸入要插入的數(shù)據(jù)

? ? ? ? scanf("%d",&value);

? ? ? ? if(value ==0) {

? ? ? ? ? ? break;

? ? ? ? }

? ? ? ? //如果輸入的鏈表是空。則創(chuàng)建一個(gè)新的節(jié)點(diǎn)，使其next指針指向自己? (*head)->next=*head;

? ? ? ? if(*L ==NULL) {

? ? ? ? ? ? *L = (LinkList)malloc(sizeof(Node));

? ? ? ? ? ? if(!L) {

? ? ? ? ? ? ? ? exit(0);

? ? ? ? ? ? }else{

? ? ? ? ? ? ? ? //給數(shù)據(jù)域賦值

? ? ? ? ? ? ? ? (*L)->data= value;

? ? ? ? ? ? ? ? //將指針域指向自己

? ? ? ? ? ? ? ? (*L)->next= *L;

? ? ? ? ? ? }

? ? ? ? }else{

?? ? ? //輸入的鏈表不是空的，尋找鏈表的尾節(jié)點(diǎn)，使尾節(jié)點(diǎn)的next=新節(jié)點(diǎn)。新節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)

? ? ? ? ? ? //找到尾結(jié)點(diǎn)


? ? ? ? ? ? for(target = *L; target->next!= *L; target = target->next) {

? ? ? ? ? ? ? ? //target先指向首元結(jié)點(diǎn)

? ? ? ? ? ? ? ? //判斷target->next是否指向首元結(jié)點(diǎn)（結(jié)束的標(biāo)志）

? ? ? ? ? ? ? ? //target不是尾結(jié)點(diǎn)，則target->next指向下一個(gè)結(jié)點(diǎn)

? ? ? ? ? ? }

? ? ? ? ? ? //找到尾結(jié)點(diǎn)后

? ? ? ? ? ? temp = (LinkList)malloc(sizeof(Node));

? ? ? ? ? ? //

? ? ? ? ? ? temp->data= value;

? ? ? ? ? ? //新結(jié)點(diǎn)的next指向首元結(jié)點(diǎn)

? ? ? ? ? ? temp->next= *L;

? ? ? ? ? ? //將target->next 指向新結(jié)點(diǎn)

? ? ? ? ? ? target->next= temp;

? ? ? ? }

? ? }


? ? returnOK;

}

創(chuàng)建方法2

Status CreateList2(LinkList *L) {

? ? intvalue =0;

? ? printf("輸入節(jié)點(diǎn)的值，輸入0結(jié)束\n");


? ? LinkListtemp =NULL;

? ? //記錄尾結(jié)點(diǎn)

? ? LinkListr =NULL;

? ? while(1) {

? ? ? ? //輸入要插入的數(shù)據(jù)

? ? ? ? scanf("%d",&value);

? ? ? ? if(value ==0) {

? ? ? ? ? ? break;

? ? ? ? }

? ? ? ? //如果輸入的鏈表是空。則創(chuàng)建一個(gè)新的節(jié)點(diǎn)，使其next指針指向自己? (*head)->next=*head;

? ? ? ? if(*L ==NULL) {

? ? ? ? ? ? *L = (LinkList)malloc(sizeof(Node));

? ? ? ? ? ? if(!L) {

? ? ? ? ? ? ? ? exit(0);

? ? ? ? ? ? }else{

? ? ? ? ? ? ? ? //給數(shù)據(jù)域賦值

? ? ? ? ? ? ? ? (*L)->data= value;

? ? ? ? ? ? ? ? //將指針域指向自己

? ? ? ? ? ? ? ? (*L)->next= *L;

? ? ? ? ? ? ? ? //指向尾結(jié)點(diǎn)

? ? ? ? ? ? ? ? r = *L;

? ? ? ? ? ? }

? ? ? ? }else{

? ? ? ? ? ? //生成新結(jié)點(diǎn)

? ? ? ? ? ? temp = (LinkList)malloc(sizeof(Node));

? ? ? ? ? ? //

? ? ? ? ? ? temp->data= value;

? ? ? ? ? ? //新結(jié)點(diǎn)的next指向首元結(jié)點(diǎn)

? ? ? ? ? ? temp->next= *L;

? ? ? ? ? ? //將target->next 指向新結(jié)點(diǎn)

? ? ? ? ? ? r->next= temp;

? ? ? ? ? ? //記錄尾結(jié)節(jié)

? ? ? ? ? ? r = temp;

? ? ? ? }

? ? }


? ? returnOK;

}

遍歷

單向循環(huán)鏈表的遍歷最好用do while,因?yàn)轭^結(jié)點(diǎn)就有值

void TraversalList(LinkList L){

? ? //如果是空

? ? if(L ==NULL) {

? ? ? ? printf("打印的鏈表為空!\n");

? ? ? ? return;

? ? }else{

? ? ? ? inti =1;

? ? ? ? LinkListtemp;

? ? ? ? temp = L;

? ? ? ? do{

? ? ? ? ? ? printf("鏈表第%d個(gè)值=%d\n",i,temp->data);

? ? ? ? ? ? temp = temp->next;

? ? ? ? ? ? i++;

? ? ? ? }while(temp != L);//當(dāng)temp是首元節(jié)點(diǎn)時(shí)結(jié)束循環(huán)

? ? ? ? printf("鏈表遍歷完成\n");

? ? }


}

循環(huán)鏈表插入數(shù)據(jù)

StatusListInsert(LinkList*L,intindex,intvalue){

? ? if(*L ==NULL|| index <1) {

? ? ? ? returnERROR;

? ? }

? ? //1. 創(chuàng)建新結(jié)點(diǎn)temp,并判斷是否創(chuàng)建成功,成功則賦值,否則返回ERROR;

? ? LinkListnewNode = (LinkList)malloc(sizeof(Node));

? ? newNode->data= value;

? ? //

? ? LinkListtarget =NULL;


? ? if(newNode ==NULL) {

? ? ? ? returnERROR;

? ? }

? ? if(index ==1) {

? ? ? ? //如果是插入首元結(jié)點(diǎn)

? ? ? ? //找到尾結(jié)點(diǎn)

? ? ? ? for(target = *L; target->next!= *L; target = target->next) {


? ? ? ? }

? ? ? ? //新結(jié)點(diǎn)作為首元結(jié)點(diǎn)

? ? ? ? newNode->next= *L;

? ? ? ? //尾結(jié)點(diǎn)指向新結(jié)點(diǎn)

? ? ? ? target->next= newNode;

? ? ? ? //首地址指向新結(jié)點(diǎn)

? ? ? ? *L = newNode;

? ? }else{

? ? ? ? //找到目標(biāo)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)

? ? ? ? inti=0;

? ? ? ? //先指向首元結(jié)點(diǎn)

? ? ? ? target = *L;

? ? ? ? for(i=1; i!= index-1; i++) {


? ? ? ? ? ? if(target->next== *L) {

? ? ? ? ? ? ? ? //找到尾結(jié)點(diǎn),說(shuō)明尾結(jié)點(diǎn)就是目標(biāo)結(jié)點(diǎn)，結(jié)束

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? }

? ? ? ? ? ? //下一個(gè)結(jié)點(diǎn)

? ? ? ? ? ? target = target->next;

? ? ? ? }

? ? ? ? //結(jié)點(diǎn)的next指向目標(biāo)結(jié)點(diǎn)的next

? ? ? ? newNode->next= target->next;

? ? ? ? //目標(biāo)結(jié)點(diǎn)的next指向新結(jié)點(diǎn)

? ? ? ? target->next= newNode;

? ? }

? ? returnOK;

}

循環(huán)鏈表刪除元素

StatusLinkListDelete(LinkList*L,intindex){

? ? if(*L ==NULL|| index <=0) {

? ? ? ? returnERROR;

? ? }

? ? //指向首元結(jié)點(diǎn)

? ? LinkListtemp = *L;

? ? LinkListtarget ;

? ? if(index ==1) {

? ? ? ? if((*L)->next== (*L)) {

? ? ? ? ? ? free(temp);

? ? ? ? ? ? *L =NULL;

? ? ? ? ? ? returnOK;

? ? ? ? }

? ? ? ? //刪除首元結(jié)點(diǎn)

? ? ? ? //找到尾結(jié)點(diǎn)

? ? ? ? for(target = *L; target->next!= *L; target = target->next) {


? ? ? ? }

? ? ? ? //首下一個(gè)結(jié)點(diǎn)改為首元結(jié)點(diǎn)

? ? ? ? *L = (*L)->next;

? ? ? ? //將尾結(jié)點(diǎn)指向新的首元結(jié)點(diǎn)

? ? ? ? target->next= *L;

? ? ? ? //釋放刪除的結(jié)點(diǎn)

? ? ? ? free(temp);

? ? }else{

? ? ? ? //找到目標(biāo)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)

? ? ? ? inti=0;

? ? ? ? target = *L;

? ? ? ? for(i=1; i!=index-1; i++) {

? ? ? ? ? ? if(target->next== *L) {

? ? ? ? ? ? ? ? //找到尾結(jié)點(diǎn),說(shuō)明尾結(jié)點(diǎn)就是目標(biāo)結(jié)點(diǎn)，結(jié)束

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? }

? ? ? ? ? ? target = target->next;

? ? ? ? }

? ? ? ? //如果找到目標(biāo)結(jié)點(diǎn)是尾結(jié)點(diǎn)，則說(shuō)明越界了

? ? ? ? if(target->next== *L) {

? ? ? ? ? ? printf("越界了\n");

? ? ? ? ? ? returnERROR;

? ? ? ? }

? ? ? ? //記錄要?jiǎng)h除的結(jié)點(diǎn)

? ? ? ? temp = target->next;

? ? ? ? //目標(biāo)結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)

? ? ? ? target->next= temp->next;

? ? ? ? free(temp);

? ? }

? ? returnOK;

}

循環(huán)鏈表的查詢(xún)

ElemType findValue(LinkList L,int index){

? ? if(L ==NULL|| index <=0) {

? ? ? ? returnERROR;

? ? }


? ? intvalue =0;

? ? //指向首元結(jié)點(diǎn)

? ? LinkListtarget = L;

? ? inti=0;

? ? for(i=1; i != index; i++) {


? ? ? ? if(target->next== L) {

? ? ? ? ? ? //找到尾結(jié)點(diǎn)了，越界了

? ? ? ? ? ? break;

? ? ? ? }

? ? ? ? target = target ->next;

? ? }

? ? value = target->data;

? ? returnvalue;

}

最后是調(diào)用

intmain(intargc,constchar* argv[]) {


? ? printf("單向循環(huán)鏈表\n");

? ? LinkListhead;

? ? intindex,value;

? ? CreateList2(&head);


? ? TraversalList(head);


? ? printf("輸入要插入的位置和數(shù)據(jù)用空格隔開(kāi)1：");

? ? scanf("%d %d",&index,&value);

? ? ListInsert(&head,index,value);

? ? TraversalList(head);


? ? printf("輸入要插入的位置和數(shù)據(jù)用空格隔開(kāi)2：");

? ? scanf("%d %d",&index,&value);

? ? ListInsert(&head,index,value);

? ? TraversalList(head);


? ? printf("輸入要插入的位置和數(shù)據(jù)用空格隔開(kāi)3：");

? ? scanf("%d %d",&index,&value);

? ? ListInsert(&head,index,value);

? ? TraversalList(head);


? ? printf("輸入要?jiǎng)h除的位置：");

? ? scanf("%d",&index);

? ? LinkListDelete(&head,index);

? ? TraversalList(head);


? ? printf("輸入要查找的位置1：");

? ? scanf("%d",&index);

? ? value =findValue(head, index);

? ? printf("查詢(xún)到的數(shù)據(jù) = %d\n",value);

? ? printf("輸入要查找的位置2：");

? ? scanf("%d",&index);

? ? value =findValue(head, index);

? ? printf("查詢(xún)到的數(shù)據(jù) = %d\n",value);


? ? printf("輸入要查找的位置3：");

? ? scanf("%d",&index);

? ? value =findValue(head, index);

? ? printf("查詢(xún)到的數(shù)據(jù) = %d\n",value);

? ? return0;

}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀(guān)點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容