閱讀目錄

• 一、循環鏈表的介紹
• 二、循環鏈表基本操作的python代碼實現
• 三、循環鏈表基本操作的C語言實現

一、循環鏈表的介紹

　　上一篇我們已經講過單鏈表，本篇給大家講解循單鏈表的一個變形是單向循環鏈表，鏈表中最后一個節點的next域不再為None，而是指向鏈表的頭節點，其基本操作和單鏈表思路一樣。

常用的操作有

創建節點

創建循環鏈表

判斷是否為空

頭部插入

循環鏈表的遍歷

尾部插入

獲取鏈表長度

根據下標插入一個節點

根據下標刪除一個節點

查找是否包含一個節點，并返回其在鏈表中的位置

根據下標找節點

根據下標修改節點的值

對鏈表排序

二、循環鏈表基本操作的python代碼實現

class Node():def __init__(self,num):self.element = numself.next = Noneclass CricleLinkList(object):def __init__(self):self.head = Noneself.length = 0# 1、判斷是否為空def is_empty(self):if self.head == None:return Trueelse:return False# 2、頭部插入def add(self, num):# 創建要插入的節點node = Node(num)if self.is_empty()==True:# 如果為空直接插入self.head = node# 并且把自身的next執行頭結點node.next = self.headelse:# 將原來的頭結點作為插入節點的nextnode.next = self.headcurrent = self.head# 循壞找到最后一個節點while current.next != self.head:current = current.next# 將最后一個節點的next執行插入節點current.next = node# 將插入的節點設置為頭結點，完成循壞閉合self.head = node# 每次添加完成一次，長度加1self.length += 1# 3、遍歷def travel(self):if self.is_empty() == True:print("你要遍歷的循環鏈表為空")returnprint("你要遍歷的循環鏈表元素有：", end=" ")current = self.head# 先把第一個元素打印一下print("%d " % current.element, end=" ")# 打印只有一個元素的時候，第一個元素打印不出來，所以先把第一個打印出來while current.next != self.head:current = current.nextprint("%d " % current.element, end=" ")print("")# 4、尾部插入def append(self,num):node = Node(num)if self.is_empty() == True:self.add(num)else:current = self.headwhile current.next != self.head:current = current.nextnode.next = self.headcurrent.next = node# 每次添加完成一次，長度加1self.length += 1# 5、指定位置插入def insertAtIndex(self,num,index):if index<=0 or index>self.length+1:print("你要插入的位置不對，請重新選擇位置")returnelif self.is_empty() == True:self.add(num)elif index==1:self.add(num)elif index == self.length+1:self.append(num)else:current = self.headfor i in range(index-2):current = current.nextnode = Node(num)node.next = current.nextcurrent.next = node# 每次添加完成一次，長度加1self.length += 1# 6、按索引刪除def deleteByIndex(self,index):if index<=0 or index>self.length:print("你要插入的位置不對，請重新選擇位置")returnelif self.is_empty() == True:print("你要刪除的鏈表為空")returnelif index == 1:current = self.headfor i in range(1,self.length):current = current.nextcurrent.next = self.head.nextself.head = self.head.nextelse:current = self.headfor i in range(index-2):current = current.nextcurrent.next = current.next.next# 每次刪完長度減1self.length -= 1# 7、查找是否包含,并返回位置def isContain(self,num):if self.is_empty() == True:print("你要查詢的鏈表為空")returnelse:current = self.headfor i in range(self.length):if current.element == num:print("你要找到元素在第%d個節點"%(i+1))return i+1current = current.nextprint("沒有找到你要的元素")return -1# 8、根據下標找節點def searchNodeByIndex(self,index):if index<=0 or index>self.length:print("你要查詢的位置不對，請重新選擇位置")returnelif self.is_empty() == True:print("你要查詢的鏈表為空")else:current = self.headfor i in range(1,index):current = current.nextprint("你要查找%d位置上的節點的值是%d"%(index,current.element))# 9、根據下標修改節點的值def modifyByIndex(self,index,num):if index <= 0 or index > self.length:print("你要查詢的位置不對，請重新選擇位置")returnelif self.is_empty() == True:print("你要修改的鏈表為空")else:current = self.headfor i in range(1, index):current = current.nextcurrent.element = num# 10、排序def sort(self):if self.length<=0:returnfor i in (0,self.length-1):current = self.headfor j in range(0,self.length-i-1):if current.element>current.next.element:temp = current.elementcurrent.element = current.next.elementcurrent.next.element = tempcurrent = current.nextif __name__ == '__main__':print("======1、創建循環鏈表 ======")cricle_link_list = CricleLinkList()print("======2、驗證是否為空 ======")empty = cricle_link_list.is_empty()if empty == True:print("你查詢的鏈表為空")else:print("你查詢的鏈表不為空")print("\n======3、驗證頭插和遍歷 ======")cricle_link_list.add(1)cricle_link_list.travel()print("\n======4、繼續驗證頭插和遍歷 ======")cricle_link_list.add(2)cricle_link_list.travel()print("\n======5、驗證尾插 ======")cricle_link_list.append(3)cricle_link_list.travel()print("\n======6、驗證按位置插入 ======")cricle_link_list.insertAtIndex(0,2)cricle_link_list.travel()print("\n======7、驗證按位置刪除 ======")cricle_link_list.deleteByIndex(5)cricle_link_list.travel()print("\n======8、驗證查找是否包含元素 ======")cricle_link_list.isContain(2)print("\n======9、驗證根據下標查找元素 ======")cricle_link_list.searchNodeByIndex(3)print("\n======10、驗證修改 ======")cricle_link_list.modifyByIndex(3,5)cricle_link_list.travel()print("\n======11、驗證排序 ======")cricle_link_list.sort()cricle_link_list.travel()

運行結果為：

======1、創建循環鏈表 ====== ======2、驗證是否為空 ====== 你查詢的鏈表為空======3、驗證頭插和遍歷 ====== 你要遍歷的循環鏈表元素有： 1 ======4、繼續驗證頭插和遍歷 ====== 你要遍歷的循環鏈表元素有： 2 1 ======5、驗證尾插 ====== 你要遍歷的循環鏈表元素有： 2 1 3 ======6、驗證按位置插入 ====== 你要遍歷的循環鏈表元素有： 2 0 1 3 ======7、驗證按位置刪除 ====== 你要插入的位置不對，請重新選擇位置 你要遍歷的循環鏈表元素有： 2 0 1 3 ======8、驗證查找是否包含元素 ====== 你要找到元素在第1個節點======9、驗證根據下標查找元素 ====== 你要查找3位置上的節點的值是1======10、驗證修改 ====== 你要遍歷的循環鏈表元素有： 2 0 5 3 ======11、驗證排序 ====== 你要遍歷的循環鏈表元素有： 0 2 3 5

三、循環鏈表基本操作的C語言實現

// // main.m // 循環鏈表 // // Created by 侯壘 on 2019/6/27. // Copyright ? 2019 可愛的侯老師. All rights reserved. //#include <stdio.h> // 創建節點結構體 typedef struct N {int element;struct N *next; }Node;// 1、創建節點 Node *createNode(int num) {Node *node = (Node *)malloc(sizeof(Node));node->element = num;node->next = NULL;return node; }// 2、創建循環鏈表 Node *createCricleLinkList(int num) {Node *head = createNode(num);head->next = head;return head; }// 3、判斷是否為空 int is_empty(Node *head) {if (head == NULL){return 1;}return 0; }//4、頭部插入 Node *add(Node *head,int num) {Node* node = createNode(num);Node *current = head;if (is_empty(head)==1){head = node;node->next = head;}else{node->next = head;while (current->next != head){current = current->next;}current->next = node;head = node;}return head; }// 5、遍歷 void travel(Node *head) {if (is_empty(head) == 1){printf("你遍歷的鏈表為空\n");}else{printf("\n你要遍歷的循環鏈表元素有：");Node *current = head;printf("%d ",current->element);while (current->next != head){current = current->next;printf("%d ",current->element);}printf("\n");} }// 5、尾部插入 Node *append(Node *head,int num) {Node *node = createNode(num);if (is_empty(head)==1){add(head, num);}else{Node *current = head;while (current->next != head){current = current->next;}node->next = head;current->next = node;}return head; }// 6、獲取鏈表長度 int getLength(Node *head) {int count = 1;Node *current = head;if (is_empty(head)==1){return 0;}else{while (current->next !=head){current = current->next;count++;}return count;} }// 7、根據下標插入節點 Node * insertByIndex(Node *head,int num,int index) {int len = getLength(head);if (index<=0||index>len+1){printf("你要插入的位置不對，請重新選擇位置");}else if (index == 1){head = add(head, num);}else{Node *current = head;for (int i=1; i<index-1; i++){current = current->next;}Node *node = createNode(num);node->next = current->next;current->next = node;}return head; }// 8、根據下標刪除 Node *deleteByIndex(Node *head,int index) {int len = getLength(head);if (index<=0||index>len){printf("\n你要刪除的位置不對，請重新選擇位置");}else if (index == 1){Node *current = head;for (int i=1; i<len; i++){current = current->next;}current->next = head->next;head = head->next;}else{Node *current = head;for (int i=0; i<index-2; i++){current = current->next;}current->next = current->next->next;}return head; }// 9、查找是否包含，并返回位置 int isContain(Node *head,int num) {int len = getLength(head);Node *current = head;for (int i= 0; i<len; i++){if (current->element == num){return i+1;}current=current->next;}return 0; }// 10、根據下標找節點 Node *searchNodeByIndex(Node *head,int index) {Node *current = head;int len = getLength(head);if (index<=0||index>len){printf("\n你要查詢的位置不對，請重新選擇位置");}else{for (int i =1 ; i<index; i++){current = current->next;}printf("\n你要查找的%d位置上的值為%d",index,current->element);}return current; }// 11、根據下標修改節點的值 void modefyByIndex(Node *head,int index,int num) {Node *current = head;int len = getLength(head);if (index<=0||index>len){printf("\n你要修改的位置不對，請重新選擇位置");}else{for (int i =1 ; i<index; i++){current = current->next;}current->element = num;} }// 12、排序 void sort(Node *head) {int len = getLength(head);if (len<=0){return;}for (int i = 0; i<len-1; i++){Node *current = head;for (int j=0; j<len-i-1; j++){if (current->element >current->next->element){int temp = current->element;current->element = current->next->element;current->next->element = temp;}current = current->next;}} }int main(int argc, const char * argv[]) {printf("=====1、創建循環鏈表=====");Node *head = createCricleLinkList(1);printf("\n=====2、驗證是否為空=====\n");int empty = is_empty(head);if (empty == 1){printf("你創建的循環鏈表為空");}else{printf("你創建的循環鏈表不為空");}printf("\n=====3、驗證頭插和遍歷=====");travel(head);head = add(head, 0);travel(head);printf("\n=====4、驗證尾插=====");head = append(head, 2);travel(head);printf("\n=====5、驗證根據下表插入=====");head = insertByIndex(head, 3, 2);travel(head);printf("\n=====6、驗證根據下表刪除=====");head = deleteByIndex(head, 3);travel(head);printf("\n=====7、驗證是否包含=====");int num = 3;int index = isContain(head, num);if (index != 0){printf("\n你查找的數據%d在第%d個位置",num,index);}else{printf("\n沒有找到你要的數據\n");}printf("\n=====8、驗證根據下標找節點=====");searchNodeByIndex(head, 2);printf("\n=====9、驗證根據下標修改節點值=====");modefyByIndex(head,2,4);travel(head);printf("\n=====10、驗證排序=====");sort(head);travel(head);return 0; }

運行結果為：

=====1、創建循環鏈表===== =====2、驗證是否為空===== 你創建的循環鏈表不為空 =====3、驗證頭插和遍歷===== 你要遍歷的循環鏈表元素有：1 你要遍歷的循環鏈表元素有：0 1 =====4、驗證尾插===== 你要遍歷的循環鏈表元素有：0 1 2 =====5、驗證根據下表插入===== 你要遍歷的循環鏈表元素有：0 3 1 2 =====6、驗證根據下表刪除===== 你要遍歷的循環鏈表元素有：0 3 2 =====7、驗證是否包含===== 你查找的數據3在第2個位置 =====8、驗證根據下標找節點===== 你要查找的2位置上的值為3 =====9、驗證根據下標修改節點值===== 你要遍歷的循環鏈表元素有：0 4 2 =====10、驗證排序===== 你要遍歷的循環鏈表元素有：0 2 4

?

---

侯哥語錄：我曾經是一個職業教育者，現在是一個自由開發者。我希望我的分享可以和更多人一起進步。分享一段我喜歡的話給大家："我所理解的自由不是想干什么就干什么，而是想不干什么就不干什么。當你還沒有能力說不得時候，就努力讓自己變得強大，擁有說不得權利。"

來源:https://www.cnblogs.com/Se7eN-HOU/p/11099974.html

總結

以上是生活随笔為你收集整理的python算法与数据结构-循环链表(41)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。