數據結構中雙向回圈鏈表的常用函數原始碼：
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
/*
雙向回圈鏈表(頭結點不帶數據)：
雙向回圈鏈表包括數據域和指針域
其中指針域包含兩個指針，分別指向前一個結點和後一個結點
*/
typedef int DATATYPE; //爲整型數據起別名爲 DATATYPE
typedef struct STUDENT //定義雙向回圈鏈表的結構體型別
{
int number; //定義雙向鏈表的數據域 可以是其它或多種型別 也可以是結構體型別
struct STUDENT *prev; //定義雙向鏈表的指針域 指向前一個結點的指針
struct STUDENT *next; //定義雙向鏈表的指針域 指向後一個結點的指針
}Student, *Double_link; //爲雙向鏈表的結構體和結構體指針起別名 爲了後面寫起來更加的簡單
// 函數宣告部分：
Double_link init_head(); // 1.初始化雙向鏈表頭結點
Double_link create_node(DATATYPE number); // 2.建立新結點
bool insert_any(Double_link new_node,Double_link a,Double_link b);// 3.0插入任意結點
bool insert_head(Double_link head, Double_link new_node); // 3.頭插法插入結點
bool insert_tail(Double_link head, Double_link new_node); // 4.尾插法插入結點
bool insert_min_max(Double_link head, Double_link new_node);// 5.根據元素從小到大依次插入結點
bool is_empty(Double_link head); // 6.判斷鏈表是否爲空
void display(Double_link head); // 7.遍歷雙向鏈表
Double_link found_node(Double_link head ,DATATYPE n); // 8.根據元素查詢某一個結點
bool update_node(Double_link head, DATATYPE old, DATATYPE new);// 9.根據元素修改結點值
bool deleate_node(Double_link head, DATATYPE number); // 10.根據元素刪除某一個結點
Double_link remove_node(Double_link head, DATATYPE number); // 11.根據元素取出某一個結點
bool move_node(Double_link head, DATATYPE a, DATATYPE b); // 12.根據元素移動結點
void clean_link(Double_link head); // 13.清空鏈表
int main(int argc, char const *argv[])
{
/*Double_link head = init_head(); //初始化頭結點
// 函數測試 初始值爲1-10的新結點作爲雙向回圈鏈表
for (int i = 0; i < 10; i++)
{
Double_link node = create_node(i+1);
insert_tail(head, node);
}
display(head);
insert_min_max(head,create_node(8));
display(head);
update_node(head,10,100);
display(head);
deleate_node(head,7);
display(head);
remove_node(head,9);
display(head);
move_node(head,6,8);
display(head);
printf("清空後\n");
clean_link(head);*/
printf("cai_Grass的部落格，所有函數都經過測試，可執行，如若不對，請指正！！\n");
return 0;
}
// 函數定義部分：
// 1.初始化雙向鏈表頭結點
Double_link init_head()
{
Double_link head = malloc(sizeof(Student));//爲雙向鏈表的頭結點申請空間
if (head != NULL) //申請成功
{
head->next = head;
head->prev = head; //頭結點前一個結點和後一個結點指向自己
return head; //返回頭結點
}
else
{
return; //空間申請失敗 結束
}
}
// 2.建立新結點
Double_link create_node(DATATYPE number)
{
Double_link new_node = malloc(sizeof(Student));//爲新結點申請空間
if(new_node != NULL)
{
new_node->number = number;
new_node->prev = NULL;
new_node->next = NULL; //申請成功，初始化數據域和指針域
return new_node; //返回新的結點
}
else
{
return; //申請失敗，結束
}
}
// 3.0雙向鏈表的萬能插入法
/*
將一個新結點插入任意兩個結點之間
如果寫了這個函數，我們後面的頭插法，尾插法可以得到簡化
當然，也不一定要有這個函數，沒有一樣可以完成頭插法和尾插法
這裏只是爲了方便
*/
bool insert_any(Double_link new_node,Double_link a,Double_link b)
{
if (new_node == NULL || a == NULL || b == NULL)
{
return false;
}
new_node->next = b;
new_node->prev = a;
a->next = new_node;
b->prev = new_node;
return true; //這種插入方法顯得十分簡單，邏輯也非常的清晰
}
// 3.頭插法插入結點
bool insert_head(Double_link head, Double_link new_node)
{
if (head == NULL || new_node == NULL)
{
return false;
}
insert_any(new_node,head,head->next);//頭插法即將新結點插入頭結點和頭結點後一個結點
return true; //返回true 表示插入成功
}
// 4.尾插法插入結點
bool insert_tail(Double_link head, Double_link new_node)
{
if (head == NULL || new_node == NULL)
{
return false;
}
insert_any(new_node,head->prev,head);
return true; //尾插法即將新結點插入尾結點和頭結點之間
}
/*
如果我們要按照結點元素從小到大的去插入
那麼我們就要去遍歷這個雙向鏈表
符合條件才插入
*/
// 5.根據元素從小到大依次插入結點
bool insert_min_max(Double_link head, Double_link new_node)
{
if (head == NULL || new_node == NULL)
{
return false;
}
Double_link p = head; //遍歷鏈表 用指針p指向頭結點 依次往下遍歷
while(p->next != head) //條件
{
p = p->next;
if (new_node->number <= p->number) //插入的條件
{
insert_any(new_node,p->prev,p); //用萬能插入法插入到p的前面一個結點
return true;
}
} //如果遍歷到最後一個結點還不符合條件 就插入到最後結點
insert_tail(head,new_node);
return true;
}
// 6.判斷鏈表是否爲空
bool is_empty(Double_link head)
{
return head->next == head; //爲空的條件就是頭結點的下一個結點是本身
}
// 7.遍歷雙向鏈表
void display(Double_link head)
{
if (head == NULL)
{
return;
}
Double_link p = head; //定義臨時指針p,指向頭結點
while(p->next != head) //遍歷的條件
{
p = p->next;
printf("%d\t", p->number); //輸出即可
}
printf("\n");
}
// 8.根據元素查詢某一個結點
Double_link found_node(Double_link head ,DATATYPE n)
{
if (head == NULL)
{
return NULL;
}
Double_link p = head;
while(p->next != head)
{
p = p->next;
if (p->number == n) //遍歷鏈表，若符合條件，返回該節點即可
{
// printf("成功查到該結點\n");
return p;
}
}
// printf("不存在該結點\n");
return NULL;
}
// 9.根據元素修改結點值
bool update_node(Double_link head, DATATYPE old, DATATYPE new)
{
if (head == NULL)
{
return false;
}
Double_link old_node = found_node(head, old);//找到舊結點,更改即可
old_node->number = new;
return true;
}
// 10.根據元素刪除某一個結點
bool deleate_node(Double_link head, DATATYPE number)
{
if (head == NULL)
{
return false;
}
Double_link deleate = found_node(head, number);//先找到要刪除的結點
Double_link PREV = deleate->prev; //找到待刪結點的前一個結點
Double_link NEXT = deleate->next; //找到待刪結點的後一個結點
PREV->next = NEXT;
NEXT->prev = PREV; //建立前一個結點和後一個結點的聯繫
free(deleate); //釋放要刪除的結點即可
return true;
}
// 11.根據元素取出某一個結點
/*
取出結點和刪除結點的操作相差不大 只是多了一個返回值，但不刪除
*/
Double_link remove_node(Double_link head, DATATYPE number)
{
if (head == NULL)
{
return NULL;
}
Double_link deleate = found_node(head, number);
Double_link PREV = deleate->prev;
Double_link NEXT = deleate->next;
PREV->next = NEXT;
NEXT->prev = PREV;
// free(deleate);
deleate->next == NULL;
deleate->prev == NULL; //最好是置爲空，更加符合邏輯
return deleate;
}
// 12.根據元素移動結點
/*
藉助取出結點和插入結點的方法即可，十分簡便
功能：將a結點放到b結點的後面
*/
bool move_node(Double_link head, DATATYPE a, DATATYPE b)
{
if (head == NULL)
{
return false;
}
Double_link a1 = remove_node(head,a); //先將a結點取出
Double_link b1 = found_node(head,b); //然後找到b結點
insert_any(a1,b1,b1->next); //將a結點插入到b結點後面
return true;
}
// 13.清空鏈表
/*
先刪除後面的所有
在刪除頭結點
*/
void clean_link(Double_link head)
{
if (head == NULL)
{
return ;
}
Double_link p = head;
while(p->next != head)
{
p = p->next;
deleate_node(head,p->number); //遍歷依次刪除結點
}
free(head); //釋放頭結點
}