夢凡 程式設計學習基地 2020-04-04
點選藍字 關注我們
循環雙連結清單
目錄
雙向循環連結清單結構體初始化函數添加資料頭插删除資料顯示函數示例程式一(簡易版本)：運作結果：示例程式二輸出結果：
雙向循環連結清單
結構圖示：
結構體
typedef struct node
{
int data;
struct node* pre; //指向前驅
struct node* next; //指向後繼
}NODE;
雙連結清單是連結清單的一種，由節點組成，每個資料結點中都有兩個指針，分别指向直接後繼和直接前驅。
初始化函數
NODE * Init()
{
NODE* head = (NODE*)malloc(sizeof(NODE));
head->pre = head->next = head; //不循環雙連結清單的head->pre=head->next=NULL;
return head;
}
添加資料
頭插
void insert(NODE * head, int data)
{
//申請節點
NODE* pNew = (NODE*)malloc(sizeof(NODE));
//NODE* pNew = Init(); //和上面等效
//初始化節點
pNew->data = data;
//插入節點
#if 1//頭插
pNew->pre = head; //①
pNew->next = head->next;//②
pNew->pre->next = pNew; //③
pNew->next->pre = pNew; //④
#elif 0//尾插
//插入的是head的前面
pNew->pre = head->pre;
pNew->next = head;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#else //中間插入 插入到條件節點的後面
//條件 插入到...條件 data==3
NODE *temp = head->next; //第一個結點沒有資料
while (temp != head) //循環連結清單
{
if (temp->data == 3) //插入到q的後面
{
break;
}
temp = temp->next;
}
//插入
pNew->next = temp->next;
pNew->pre = temp;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#endif
}
删除資料
void deleteData(NODE * head, int data)
{
NODE*temp = head->next;
while (temp != head)
{
if (temp->data == data)
{
//删除資料
temp->next->pre = temp->pre; //①
temp->pre->next = temp->next; //②
free(temp);
break;
}
temp = temp->next;
}
}
顯示函數
void showLinked(NODE * head)
{
NODE*temp = head->next;
int number = 1;
while (temp != head)
{
printf("%d\t%d\n", number++, temp->data);
temp = temp->next;
}
}
示例程式一(簡易版本)：
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node* pre; //指向前驅
struct node* next; //指向後繼
}NODE;
NODE* Init(); //初始化
void insert(NODE* head, int data);
void deleteData(NODE* head, int data);
void showLinked(NODE* head);
int main()
{
NODE* head = Init();
insert(head, 1);
insert(head, 3);
insert(head, 5);
printf("---插入後---\n");
showLinked(head);
printf("---删除後---\n");
deleteData(head, 3);
showLinked(head);
getchar();
}
NODE * Init()
{
NODE* head = (NODE*)malloc(sizeof(NODE));
head->pre = head->next = head;
return head;
}
void insert(NODE * head, int data)
{
//申請節點
NODE* pNew = (NODE*)malloc(sizeof(NODE));
//初始化節點
pNew->data = data;
//插入節點
#if 0//頭插
pNew->pre = head;
pNew->next = head->next;
pNew->pre->next = pNew;
pNew->next->pre = pNew;
#elif 1//尾插
//插入的是head的前面
pNew->pre = head->pre;
pNew->next = head;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#else //中間插入 插入到條件節點的後面
//條件 插入到...條件 data==3
NODE *temp = head->next; //第一個結點沒有資料
while (temp != head) //循環連結清單
{
if (temp->data == 3) //插入到q的後面
{
break;
}
temp = temp->next;
}
//插入
pNew->next = temp->next;
pNew->pre = temp;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#endif
}
void deleteData(NODE * head, int data)
{
NODE*temp = head->next;
while (temp != head)
{
if (temp->data == data)
{
//删除資料
temp->next->pre = temp->pre;
temp->pre->next = temp->next;
free(temp);
break;
}
temp = temp->next;
}
}
void showLinked(NODE * head)
{
NODE*temp = head->next;
int number = 1;
printf("id\tdata\n");
while (temp != head)
{
printf(" %d\t %d\n", number++, temp->data);
temp = temp->next;
}
}
運作結果：
---插入後---
id data
1 1
2 3
3 5
---删除後---
id data
1 1
2 5
示例程式二
//mian.c
#include"Double_Linked.h"
int main()
{
NODE* head;
head = Init(); //初始化表頭
/****準備資料****/
NODE data;
data.m_id = 1001;
data.m_score = 100;
strcpy(data.m_name, "小明");
//插入data
insert(head, data);
/****準備資料****/
data.m_id = 1002;
data.m_score = 98;
strcpy(data.m_name, "小紅");
//插入data
insert(head, data);
showData(head);
printf("-----删除資料之後-----\n");
deleteData(head, 1001);
showData(head);
getchar();
}
//Double_Linked.h
#pragma once
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
typedef struct node
{
int m_id;
char m_name[20];
int m_score;
struct node* pre; //指向前驅
struct node* next; //指向後繼
}NODE;
NODE* Init(); //初始化
void insert(NODE* head, NODE data); //插入資料
void deleteData(NODE*head, int id); //删除資料
void showData(NODE*head);
//Double_Linked.c
#include"Double_Linked.h"
NODE * Init()
{
NODE* head = (NODE*)malloc(sizeof(NODE));
head->pre = head->next = head;
return head;
}
void insert(NODE * head, NODE data)
{
//申請節點
NODE* pNew = (NODE*)malloc(sizeof(NODE));
pNew->m_id = data.m_id;
pNew->m_score = data.m_score;
strcpy(pNew->m_name, data.m_name);
//插入節點
#if 0//頭插
pNew->pre = head;
pNew->next = head->next;
pNew->pre->next = pNew;
pNew->next->pre = pNew;
#elif 1//尾插
//插入的是head的前面
pNew->pre = head->pre;
pNew->next = head;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#else //中間插入 插入到條件節點的後面
//條件 插入到...條件 m_id==3
NODE *temp = head->next; //第一個結點沒有資料
while (temp != head) //循環連結清單
{
if (temp->m_id == 3) //插入到q的後面
{
break;
}
temp = temp->next;
}
/***如果沒有找到3這個資料那麼，相當于頭插***/
//插入
pNew->next = temp->next;
pNew->pre = temp;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#endif
}
void deleteData(NODE * head, int id)
{
NODE*temp = head->next;
while (temp != head)
{
if (temp->m_id == id)
{
//删除資料
temp->next->pre = temp->pre;
temp->pre->next = temp->next;
free(temp);
break;
}
temp = temp->next;
}
}
void showData(NODE * head)
{
NODE*temp = head->next;
printf("id\tname\tscore\n");
while (temp != head)
{
printf("%d\t%s\t%d\n", temp->m_id, temp->m_name, temp->m_score);
temp = temp->next;
}
}
輸出結果：
id name score
1001 小明 100
1002 小紅 98
-----删除資料之後-----
id name score
1002 小紅 98