前言
相信經(jīng)過前面的學(xué)習(xí)，大家已經(jīng)了解的單鏈表的缺陷和用途，今天我們學(xué)習(xí)雙鏈表，和以前不同，今天雙鏈表的實(shí)現(xiàn)我們?cè)黾右稽c(diǎn)點(diǎn)的難度，但我相信這些難度對(duì)大家都沒有問題。和之前單鏈表的實(shí)現(xiàn)，我們的數(shù)據(jù)類型是固定的，主函數(shù)中傳什么我們的單鏈表結(jié)構(gòu)體中就需要相應(yīng)的數(shù)據(jù)類型， 今天雙鏈表的實(shí)現(xiàn)我們將改為主函數(shù)（用戶）傳任何的數(shù)據(jù)類型我們都可以接收并且實(shí)現(xiàn)。
本章涉及函數(shù)指針，回調(diào)函數(shù)，柔性數(shù)組的知識(shí)點(diǎn)，忘記的小伙伴們可以在本章復(fù)習(xí)一下喲。
鏈表在空間上的存儲(chǔ)方式：
一、雙鏈表的思路
在實(shí)現(xiàn)之前我們先來認(rèn)識(shí)雙鏈表：
什么是雙鏈表： 雙鏈表的結(jié)點(diǎn)中有兩個(gè)指針prev和next，分別指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。
雙鏈表的優(yōu)點(diǎn)： 解決了單鏈表要訪問某個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)時(shí)，只能從頭開始遍歷，訪問后繼結(jié)點(diǎn)的復(fù)雜度為O（1），訪問前驅(qū)結(jié)點(diǎn)的復(fù)雜度為O（n）的問題。
雙鏈表的結(jié)構(gòu)：
不循環(huán)的雙鏈表中，頭節(jié)點(diǎn)或雙鏈表中的第一個(gè)節(jié)點(diǎn)無前驅(qū)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)無后繼節(jié)點(diǎn)。頭節(jié)點(diǎn)是不存儲(chǔ)有效數(shù)據(jù)的?。。?/font>
在循環(huán)的雙鏈表中，頭節(jié)點(diǎn)或雙鏈表中的第一個(gè)節(jié)點(diǎn)前驅(qū)節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)后繼節(jié)點(diǎn)為頭節(jié)點(diǎn)或雙鏈表中的第一個(gè)節(jié)點(diǎn)。頭節(jié)點(diǎn)是不存儲(chǔ)有效數(shù)據(jù)的?。?！
相信經(jīng)過結(jié)構(gòu)我們已經(jīng)有了大體的實(shí)現(xiàn)思路了，而我們今天要實(shí)現(xiàn)的是雙鏈表中最完美的結(jié)構(gòu)，帶頭循環(huán)的雙鏈表，也是日后我們常用的結(jié)構(gòu)。
二、帶頭循環(huán)雙鏈表的實(shí)現(xiàn)分析
我們要實(shí)現(xiàn)用戶（主函數(shù)）所傳的任何數(shù)據(jù)類型都可以構(gòu)成我們的雙鏈表，所以用戶構(gòu)成雙鏈表數(shù)據(jù)域的類型是未知的，那么我們要構(gòu)建什么類型的數(shù)據(jù)呢？ 我們選擇char類型的指針，又會(huì)有一個(gè)新問題，用戶傳入的是整形或者結(jié)構(gòu)體char類型的指針又要如何應(yīng)對(duì)呢？針對(duì)上述問題我們?cè)O(shè)計(jì)兩個(gè)結(jié)構(gòu)體：
這是我們?cè)O(shè)計(jì)的結(jié)構(gòu)體，由于我們頭節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，又和其他節(jié)點(diǎn)不太一樣，那又該如何指向呢？
我們指針指向的是位置，我們把尾節(jié)點(diǎn)和第一個(gè)有效節(jié)點(diǎn)的指針都指向頭節(jié)點(diǎn)的鏈表節(jié)點(diǎn)成員的位置。這樣我們的鏈表就實(shí)現(xiàn)循環(huán)了。
二、帶頭循環(huán)雙鏈表的實(shí)現(xiàn)1
1.帶頭循環(huán)雙鏈表實(shí)現(xiàn)頭文件總覽
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<time.h>
#define HEADINSERTION 1 //頭插選項(xiàng)
#define BACKINSERTION 2 //尾插選項(xiàng)
typedef struct ListNode//鏈表的節(jié)點(diǎn)
{
char* data;//傳入的數(shù)據(jù)
struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)的指針
struct ListNode* prev;//指向上一個(gè)節(jié)點(diǎn)的指針
}ListNode;
typedef struct ListHead //不一樣的頭節(jié)點(diǎn)
{
int size;//用來存儲(chǔ)傳入數(shù)據(jù)的大小
ListNode list;//用來存儲(chǔ)頭節(jié)點(diǎn)的數(shù)據(jù)
}ListHead;
typedef void Printf(const void* );//對(duì)用戶傳遞的打印函數(shù)進(jìn)行重命名
typedef int Cmp(const void*, const void*);//對(duì)用戶傳遞的打印函數(shù)進(jìn)行重命名
ListHead* ListCreate(int datasize);//用來創(chuàng)建特殊的頭節(jié)點(diǎn)
void Destory(ListHead* pHead);// 雙向鏈表銷毀
void ListPrint(ListHead* pHead, Printf* print);// 雙向鏈表打印
int ListInsert(ListHead* pHead, const void* pos, int Optional);//雙向鏈表的插入
void* ListFind(ListHead* pHead, const void* key,Cmp* cmp);//雙向鏈表查找
int Listdestroy(ListHead* pHead, const void* key, Cmp* cmp);//雙向鏈表刪除
int Listtravel(ListHead* pHead, const void* key, Cmp* cmp,void* retu);//雙向鏈表刪除,并把刪除節(jié)點(diǎn)返回
我們先看頭文件里的函數(shù)，至于為什么這樣設(shè)計(jì)。我們?cè)谙旅嬉灰唤獯稹?/font>
2.帶頭循環(huán)雙鏈表的初始化
ListHead* ListCreate(int datasize)//用來創(chuàng)建特殊的頭節(jié)點(diǎn)
{
ListHead* pHead = (ListHead*)malloc(sizeof(ListHead));
if (pHead == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("pHead malloc");
exit(-1);
}
pHead->size = datasize;//用來接收用戶要構(gòu)建鏈表的數(shù)據(jù)區(qū)的大小
pHead->list.data = NULL;//頭節(jié)點(diǎn)不存儲(chǔ)有效數(shù)據(jù)，所以置為NULL
pHead->list.next = &pHead->list;//后繼節(jié)點(diǎn)指向自己
pHead->list.prev = &pHead->list;//前驅(qū)節(jié)點(diǎn)指向自己
return pHead;
}
我們初始化時(shí)要構(gòu)建我們特殊的頭節(jié)點(diǎn)，我們只有知道用戶要構(gòu)建數(shù)據(jù)區(qū)的大小，才可以為后面的插入開辟空間。
3.帶頭循環(huán)雙鏈表的插入
//pos：用來接收用戶所傳數(shù)據(jù)，由于用戶所傳數(shù)據(jù)未知，所以我們用void指針進(jìn)行接收
//Optional：插入選擇，接收用戶是頭插還是尾插
//#define HEADINSERTION 1 //頭插選項(xiàng)，在我們的頭文件中定義的
//#define BACKINSERTION 2 //尾插選項(xiàng)，在我們的頭文件中定義的
int ListInsert(ListHead* pHead, const void* pos, int Optional)//雙向鏈表的插入
{
assert(pHead);
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("node malloc");//節(jié)點(diǎn)開辟失敗
return 1;//返回值為1代表節(jié)點(diǎn)開辟失敗
}
node->data = (char*)malloc(sizeof(char) * pHead->size);//數(shù)據(jù)區(qū)的開辟，開辟的大小為用戶所傳的大小
if (node->data == NULL)
{
free(node);//釋放開辟好的節(jié)點(diǎn)，防止內(nèi)存泄露
perror("node->data malloc");//數(shù)據(jù)域開辟失敗，進(jìn)行報(bào)錯(cuò)
return 2;//返回值為2代表節(jié)點(diǎn)開辟成功，但數(shù)據(jù)區(qū)開辟失敗
}
memcpy(node->data, (char*)pos,pHead->size);//把數(shù)據(jù)拷貝到我們開的節(jié)點(diǎn)中
if (HEADINSERTION == Optional)//判斷是否為頭插
{
node->next = (pHead->list).next;
node->prev = &(pHead->list);//取頭節(jié)點(diǎn)中的鏈表節(jié)點(diǎn)地址
}
else if (BACKINSERTION == Optional)//判斷是否為尾插
{
node->next = &pHead->list;
node->prev = pHead->list.prev;
}
else
{
free(node->data);//釋放開辟好的數(shù)據(jù)區(qū)
free(node);//釋放開辟好的節(jié)點(diǎn)，防止內(nèi)存泄露
return 3;//返回值為3代表插入位置不符合要求
}
node->prev->next = node;
node->next->prev = node;
return 0;//代表此函數(shù)正常結(jié)束
}
在工程中我們隨便指定位置插入是不合法的行為，因?yàn)殒湵碓貎?nèi)容未知，隨便插入容易破壞結(jié)構(gòu)，所以我們這里就實(shí)現(xiàn)尾插和頭插。我們插入指向頭節(jié)點(diǎn)都是指向頭節(jié)點(diǎn)中雙鏈表節(jié)點(diǎn)的位置，而不是指向從size開始的位置！?。?/font>
我們實(shí)現(xiàn)頭插和尾插是根據(jù)用戶選擇實(shí)現(xiàn)的，這里不必在分為兩個(gè)函數(shù)來進(jìn)行實(shí)現(xiàn)。
在工程中我們要在函數(shù)中少使用打印函數(shù)，這里我們通過返回值返回，用戶可以通過返回值來判斷是什么原因出錯(cuò)。保證了我們函數(shù)的單一性。
用戶所傳的數(shù)據(jù)區(qū)是未知的，所以我們要用庫函數(shù)memcpy或者strcpy函數(shù)進(jìn)行拷貝。
這里頭插和尾插實(shí)現(xiàn)思路相同，大家可以畫一畫。我們要注意當(dāng)我們雙鏈表節(jié)點(diǎn)開辟成功時(shí)，但數(shù)據(jù)區(qū)為開辟失敗時(shí)要對(duì)開辟的節(jié)點(diǎn)進(jìn)行釋放，否則造成內(nèi)存泄露。
4.帶頭循環(huán)雙鏈表的打印和銷毀
void Destory(ListHead* pHead)// 雙向鏈表銷毀
{
assert(pHead);
ListNode* pos = (&pHead->list)->next;//從頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始
while (pos != &pHead->list)
{
ListNode* del = pos;//要釋放的節(jié)點(diǎn)
pos = pos->next;//保存下一個(gè)節(jié)點(diǎn)
free(del->data);//data數(shù)據(jù)也是動(dòng)態(tài)開辟的
free(del);//釋放節(jié)點(diǎn)
}
}
void ListPrint(ListHead* pHead, Printf * print)// 雙向鏈表打印，使用回調(diào)函數(shù)
{
assert(pHead);
ListNode* pos = pHead->list.next;
while (pos != &pHead->list)//判斷是否走到頭節(jié)點(diǎn)
{
print(pos->data);//調(diào)用用戶提供的打印函數(shù)
pos = pos->next;
}
}
這里判斷是否是頭節(jié)點(diǎn)都是通過雙鏈表節(jié)點(diǎn)和頭節(jié)點(diǎn)中的雙鏈表節(jié)點(diǎn)的地址進(jìn)行比較。
我們未知用戶類型的情況下如何進(jìn)行打??？
這里通過回調(diào)函數(shù)進(jìn)行，由于我們未知用戶數(shù)據(jù)類型，但是用戶知道，所以我們可以設(shè)置函數(shù)類型，讓用戶自己實(shí)現(xiàn)，然后我們通過回調(diào)函數(shù)調(diào)用。
我們頭文件的這個(gè)重命名函數(shù)就在這里起作用了
typedef void Printf(const void* );//對(duì)用戶傳遞的打印函數(shù)進(jìn)行重命名
//void Printf(const void* );//用戶需要實(shí)現(xiàn)的函數(shù)
//typedef對(duì)該函數(shù)進(jìn)行重命名
下面是測試函數(shù)：
#define NAME_SIZE 32
typedef struct Stu
{
int id;
char name[NAME_SIZE];
int math;
int chinese;
}Stu;
void Printf_s(const void* print)//用戶寫的打印函數(shù)
{
Stu* prin = (Stu*)print;//把void類型轉(zhuǎn)換為用戶的類型
printf("id:%2d name:%s math:%2d chinese:%2d\n",prin->id, prin->name, prin->math, prin->chinese);
}
void test1()
{
ListHead* pHead = ListCreate(sizeof(Stu));
Stu stu;
int i = 0;
for (i = 0; i < 5; i++)
{
stu.id = i;
snprintf(stu.name, NAME_SIZE, "stu%d:", i);
stu.math = rand()%100;
stu.chinese = rand()%100;
ListInsert(pHead, &stu, 1);//傳入1，進(jìn)行頭插
//ListInsert(pHead, &stu, 2);//傳入2，進(jìn)行尾插
}
ListPrint(pHead, Printf_s);// 雙向鏈表打印
Destory(pHead);// 雙向鏈表銷毀
}
int main()
{
srand((unsigned)time(NULL));
test1();
return 0;
}
頭插：
尾插：
我們對(duì)成績是隨機(jī)取值的，所以兩次結(jié)果不同，我們這里的給字符串?dāng)?shù)組賦值用的方法和單鏈表的方法相同。這里就不多介紹了。
5.帶頭循環(huán)雙鏈表的查找和刪除
ListNode* find(ListHead* pHead, const void* key, Cmp* cmp)//雙向鏈表查找
{
assert(pHead);
ListNode* pos = pHead->list.next;
while (pos != &pHead->list)//判斷是否走到頭節(jié)點(diǎn)
{
if (cmp(key, pos->data) == 0)//調(diào)用用戶提供的比較函數(shù)
{
break;
}
pos = pos->next;
}
return pos;//如果找到時(shí)，循環(huán)終止，返回值為找到的節(jié)點(diǎn)，如果找不到，則返回pos為頭節(jié)點(diǎn)。
}
void* ListFind(ListHead* pHead, const void* key, Cmp* cmp)//雙向鏈表查找
{
assert(pHead);
return (void*)find(pHead, key, cmp)->data;//返會(huì)我們的數(shù)據(jù)區(qū)。如果返回的頭節(jié)點(diǎn)，頭節(jié)點(diǎn)的值為NULL。不影響我們正常判斷
}
int Listdestroy(ListHead* pHead, const void* key, Cmp* cmp)//雙向鏈表刪除
{
assert(pHead);
ListNode* del = find(pHead, key, cmp);
if (del == &pHead->list)
{
return 1;//代表未找到我們要?jiǎng)h除的節(jié)點(diǎn)
}
//刪除節(jié)點(diǎn)
del->prev->next = del->next;
del->next->prev = del->prev;
free(del->data);//我們的數(shù)據(jù)區(qū)也是動(dòng)態(tài)開辟的，所以也要內(nèi)存釋放
free(del);
return 0;
}
int Listtravel(ListHead* pHead, const void* key, Cmp* cmp, void* retu)//雙向鏈表刪除,并把刪除節(jié)點(diǎn)返回
{
assert(pHead);
ListNode* del = find(pHead, key, cmp);
if (del == &pHead->list)
{
return 1;//代表未找到我們要?jiǎng)h除的節(jié)點(diǎn)
}
if (del->data != NULL)
{
memcpy(retu, del->data, pHead->size);//通過函數(shù)參數(shù)返回
}
//刪除節(jié)點(diǎn)
del->prev->next = del->next;
del->next->prev = del->prev;
free(del->data);
free(del);
return 0;
}
我們要實(shí)現(xiàn)查找和刪除，都需要先找到節(jié)點(diǎn)，所以我們單獨(dú)創(chuàng)建一個(gè)函數(shù)，用來返回查找的節(jié)點(diǎn)。因?yàn)槲覀兾粗容^的類型，所以需要接收用戶要比較的類型和用戶所提供的比較函數(shù)，來實(shí)現(xiàn)我們的查找。
我們頭節(jié)點(diǎn)是不含有效數(shù)據(jù)的，我們把頭節(jié)點(diǎn)的數(shù)據(jù)設(shè)置為空，所以查找是如果找不到，我們返回的數(shù)據(jù)就是頭節(jié)點(diǎn)的數(shù)據(jù)（NULL）。
我們刪除函數(shù)設(shè)置了兩個(gè)，一個(gè)是直接刪除，一個(gè)是刪除并把刪除的值返回給用戶，這兩實(shí)現(xiàn)思路相同，只是一個(gè)多加了一個(gè)參數(shù)。
typedef int Cmp(const void*, const void*);//對(duì)用戶傳遞的比較函數(shù)進(jìn)行重命名
測試函數(shù)：
#define NAME_SIZE 32
typedef struct Stu
{
int id;
char name[NAME_SIZE];
int math;
int chinese;
}Stu;
void Printf_s(const void* print)//用戶寫的打印函數(shù)
{
Stu* prin = (Stu*)print;
printf("id:%2d name:%s math:%2d chinese:%2d\n",prin->id, prin->name, prin->math, prin->chinese);
}
int cmp_id(const void* s1, const void*s2)//用戶寫的比較函數(shù)
{
int *key = (int*)s1;
Stu *stu = (Stu*)s2;
return (*key - stu->id);
}
int cmp_name(const void* s1, const void* s2)//用戶寫的name比較函數(shù)
{
char* key = (char*)s1;
Stu* stu = (Stu*)s2;
return strcmp(key, stu->name);
}
void test1()
{
ListHead* pHead = ListCreate(sizeof(Stu));
Stu stu;
int i = 0;
for (i = 0; i < 5; i++)
{
stu.id = i;
snprintf(stu.name, NAME_SIZE, "stu%d:", i);
stu.math = rand()%100;
stu.chinese = rand()%100;
ListInsert(pHead, &stu, 1);//傳入1，進(jìn)行頭插
//ListInsert(pHead, &stu, 2);//傳入2，進(jìn)行尾插
}
ListPrint(pHead, Printf_s);// 雙向鏈表打印
printf("\n\n");
//鏈表元素的查找，通過id查找
int id = 3;
Stu *st = ListFind(pHead, &id, cmp_id);
if (st == NULL)
{
printf("can not find\n");
}
else
{
Printf_s(st);
}
//鏈表元素的刪除，通過id刪除
printf("\n\n");
Listdestroy(pHead, &id, cmp_id);
ListPrint(pHead, Printf_s);
//鏈表元素的刪除并且返回，通過姓名刪除
printf("\n\n");
char* p = "stu2:";//不要忘了加分號(hào)
Stu *s = &stu;
Listtravel(pHead, p, cmp_name, s);
if (s == NULL)
{
printf("can not find\n");
}
else
{
Printf_s(s);
}
printf("\n\n");
ListPrint(pHead, Printf_s);
Destory(pHead);// 雙向鏈表銷毀
}
int main()
{
srand((unsigned)time(NULL));
test1();
return 0;
}
為了驗(yàn)證我們可以首任何類型，這里我們分別用id刪除和姓名刪除，這里的實(shí)現(xiàn)思路和qsort庫函數(shù)相同。
三、帶頭循環(huán)雙鏈表的實(shí)現(xiàn)2
第一種方法我們是通過動(dòng)態(tài)內(nèi)存開辟的空間。能否不動(dòng)態(tài)開辟我們的數(shù)據(jù)區(qū)的空間呢，答案是肯定的，我們第二種思路就是通過不動(dòng)態(tài)開辟數(shù)據(jù)區(qū)來實(shí)現(xiàn)我們的雙鏈表。
我們第二種的思路基于第一種函數(shù)實(shí)現(xiàn)進(jìn)行改動(dòng)，測試函數(shù)和為改動(dòng)的函數(shù)保持不變就可以了?。?！
1.帶頭循環(huán)雙鏈表實(shí)現(xiàn)2的結(jié)構(gòu)體
typedef struct ListNode//鏈表的節(jié)點(diǎn)
{
struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)的指針
struct ListNode* prev;//指向上一個(gè)節(jié)點(diǎn)的指針
char data[];//傳入的數(shù)據(jù)
//char data[1];//傳入的數(shù)據(jù)
}ListNode;
typedef struct ListHead //不一樣的頭節(jié)點(diǎn)
{
int size;//用來存儲(chǔ)傳入數(shù)據(jù)的大小
ListNode list;//用來存儲(chǔ)頭節(jié)點(diǎn)的數(shù)據(jù)
}ListHead;
這里我們通過柔性數(shù)組實(shí)現(xiàn)，如果編譯器不支持柔性數(shù)組，可以把數(shù)組中的元素個(gè)數(shù)賦值為1。
在這里，我們data的目的是為了站一個(gè)位置，方便我們尋找數(shù)據(jù)區(qū)的地址。
2.帶頭循環(huán)雙鏈表實(shí)現(xiàn)函數(shù)改動(dòng)
ListHead* ListCreate(int datasize)//用來創(chuàng)建特殊的頭節(jié)點(diǎn)
{
ListHead* pHead = (ListHead*)malloc(sizeof(ListHead));
if (pHead == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("pHead malloc");
exit(-1);
}
pHead->size = datasize;
pHead->list.next = &pHead->list;//后繼節(jié)點(diǎn)指向自己
pHead->list.prev = &pHead->list;//前驅(qū)節(jié)點(diǎn)指向自己
return pHead;
}
在這里我們的數(shù)據(jù)區(qū)已經(jīng)不需要?jiǎng)討B(tài)開辟空間了，所以這里不需要賦值了。
void Destory(ListHead* pHead)// 雙向鏈表銷毀
{
assert(pHead);
ListNode* pos = (&pHead->list)->next;//從頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始
while (pos != &pHead->list)
{
ListNode* del = pos;//要釋放的節(jié)點(diǎn)
pos = pos->next;//保存下一個(gè)節(jié)點(diǎn)
free(del);
}
}
int ListInsert(ListHead* pHead, const void* pos, int Optional)//雙向鏈表的插入
{
assert(pHead);
ListNode* node = (ListNode*)malloc(sizeof(ListNode)+pHead->size);//申請(qǐng)一個(gè)節(jié)點(diǎn)結(jié)構(gòu)體的大小加上用戶所傳數(shù)據(jù)大小
if (node == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("node malloc");//節(jié)點(diǎn)開辟失敗
return 1;//返回值為1代表節(jié)點(diǎn)開辟失敗
}
memcpy(node->data, (char*)pos,pHead->size);//把數(shù)據(jù)拷貝到我們開的節(jié)點(diǎn)中
if (HEADINSERTION == Optional)//判斷是否為頭插
{
node->next = (pHead->list).next;
node->prev = &(pHead->list);
}
else if (BACKINSERTION == Optional)//判斷是否為尾插
{
node->next = &pHead->list;
node->prev = pHead->list.prev;
}
else
{
return 2;//返回值為3代表插入位置不符合要求
}
node->prev->next = node;
node->next->prev = node;
return 0;//代表此函數(shù)正常結(jié)束
}
這里我們要把釋放開辟空間的函數(shù)刪除，我們只需要為雙鏈表結(jié)構(gòu)體開辟兩個(gè)指針的空間和用戶傳入數(shù)據(jù)的空間大小就可以了。
我們拷貝的數(shù)據(jù)就是放入到data區(qū)域里。
void* ListFind(ListHead* pHead, const void* key, Cmp* cmp)//雙向鏈表查找
{
assert(pHead);
ListNode* pos = find(pHead, key, cmp);
if (pos == &pHead->list)//如果是頭節(jié)點(diǎn)，則證明沒找到
{
return NULL;
}
return pos->data;//返會(huì)我們的數(shù)據(jù)區(qū)。
}
int Listdestroy(ListHead* pHead, const void* key, Cmp* cmp)//雙向鏈表刪除
{
assert(pHead);
ListNode* del = find(pHead, key, cmp);
if (del == &pHead->list)
{
return 1;//代表未找到我們要?jiǎng)h除的節(jié)點(diǎn)
}
//刪除節(jié)點(diǎn)
del->prev->next = del->next;
del->next->prev = del->prev;
free(del);
return 0;
}
int Listtravel(ListHead* pHead, const void* key, Cmp* cmp, void* retu)//雙向鏈表刪除,并把刪除節(jié)點(diǎn)返回
{
assert(pHead);
ListNode* del = find(pHead, key, cmp);
if (del == &pHead->list)
{
return 1;//代表未找到我們要?jiǎng)h除的節(jié)點(diǎn)
}
if (del->data != NULL)
{
memcpy(retu, del->data, pHead->size);//通過函數(shù)參數(shù)返回
}
//刪除節(jié)點(diǎn)
del->prev->next = del->next;
del->next->prev = del->prev;
free(del);
return 0;
}
這里我們刪除釋放數(shù)據(jù)區(qū)開辟內(nèi)存和釋放內(nèi)存的函數(shù)，且要加上是否是頭節(jié)點(diǎn)的判斷，因?yàn)槲覀冾^節(jié)點(diǎn)沒有data區(qū)的內(nèi)存。
運(yùn)行測試：
四、帶頭循環(huán)雙鏈表的隱藏封裝
我們隱藏封裝是在實(shí)現(xiàn)二的基礎(chǔ)上進(jìn)行改動(dòng)！??！
1.帶頭循環(huán)雙鏈表隱藏封裝的頭文件預(yù)覽
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<time.h>
#define HEADINSERTION 1 //頭插選項(xiàng)
#define BACKINSERTION 2 //尾插選項(xiàng)
typedef void Printf(const void*);//對(duì)用戶傳遞的打印函數(shù)進(jìn)行重命名
typedef int Cmp(const void*, const void*);//對(duì)用戶傳遞的打印函數(shù)進(jìn)行重命名
typedef struct ListNode//鏈表的節(jié)點(diǎn)
{
struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)的指針
struct ListNode* prev;//指向上一個(gè)節(jié)點(diǎn)的指針
char data[];//傳入的數(shù)據(jù)
}ListNode;
typedef struct ListHead //不一樣的頭節(jié)點(diǎn)
{
int size;//用來存儲(chǔ)傳入數(shù)據(jù)的大小
void (*destory)(struct ListHead* pHead);//雙向鏈表銷毀
void (*listprint)(struct ListHead* pHead, Printf* print);//雙向鏈表打印
int (*listinsert)(struct ListHead* pHead, const void* pos, int Optional);//雙向鏈表的插入
void* (*listfind)(struct ListHead* pHead, const void* key, Cmp* cmp);//雙向鏈表查找
int (*listdestroy)(struct ListHead* pHead, const void* key, Cmp* cmp);//雙向鏈表刪除
int (*listtravel)(struct ListHead* pHead, const void* key, Cmp* cmp, void* retu);//雙向鏈表刪除,并把刪除節(jié)點(diǎn)返回
ListNode list;//用來存儲(chǔ)頭節(jié)點(diǎn)的數(shù)據(jù),柔性數(shù)組，這個(gè)必須放在最下方
}ListHead;
ListHead* ListCreate(int datasize);//用來創(chuàng)建特殊的頭節(jié)點(diǎn)
在這里我們把我們要實(shí)現(xiàn)的函數(shù)全部設(shè)置為函數(shù)指針，這樣函數(shù)用戶可以通過結(jié)構(gòu)體直接調(diào)用，而不知道我們函數(shù)具體如何實(shí)現(xiàn)的
2.帶頭循環(huán)雙鏈表函數(shù)改動(dòng)
我們是在二的基礎(chǔ)上進(jìn)行改動(dòng)，所以我們這里只展示改動(dòng)的代碼。
//提前聲明
void Destory(struct ListHead* pHead);// 雙向鏈表銷毀
void ListPrint(struct ListHead* pHead, Printf* print);// 雙向鏈表打印
int ListInsert(struct ListHead* pHead, const void* pos, int Optional);//雙向鏈表的插入
void* ListFind(struct ListHead* pHead, const void* key,Cmp* cmp);//雙向鏈表查找
int Listdestroy(struct ListHead* pHead, const void* key, Cmp* cmp);//雙向鏈表刪除
int Listtravel(struct ListHead* pHead, const void* key, Cmp* cmp,void* retu);//雙向鏈表刪除,并把刪除節(jié)點(diǎn)返回
ListHead* ListCreate(int datasize)//用來創(chuàng)建特殊的頭節(jié)點(diǎn)
{
ListHead* pHead = (ListHead*)malloc(sizeof(ListHead));
if (pHead == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("pHead malloc");
exit(-1);
}
pHead->size = datasize;
pHead->list.next = &pHead->list;//后繼節(jié)點(diǎn)指向自己
pHead->list.prev = &pHead->list;//前驅(qū)節(jié)點(diǎn)指向自己
pHead->destory = Destory;//把我們封裝函數(shù)指針指向相應(yīng)的函數(shù)
pHead->listprint = ListPrint;
pHead->listinsert = ListInsert;
pHead->listfind = ListFind;
pHead->listdestroy = Listdestroy;
pHead->listtravel = Listtravel;
return pHead;
}
我們對(duì)函數(shù)指針進(jìn)行賦值時(shí)，要先對(duì)我們要指向的函數(shù)進(jìn)行聲明，這樣不會(huì)進(jìn)行報(bào)錯(cuò)。
測試函數(shù)的修改：
#define NAME_SIZE 32
typedef struct Stu
{
int id;
char name[NAME_SIZE];
int math;
int chinese;
}Stu;
void Printf_s(const void* print)//用戶寫的打印函數(shù)
{
Stu* prin = (Stu*)print;
printf("id:%2d name:%s math:%2d chinese:%2d\n",prin->id, prin->name, prin->math, prin->chinese);
}
int cmp_id(const void* s1, const void*s2)//用戶寫的id比較函數(shù)
{
int *key = (int*)s1;
Stu *stu = (Stu*)s2;
return (*key - stu->id);
}
int cmp_name(const void* s1, const void* s2)//用戶寫的name比較函數(shù)
{
char* key = (char*)s1;
Stu* stu = (Stu*)s2;
return strcmp(key,stu->name);
}
void test1()
{
ListHead* pHead = ListCreate(sizeof(Stu));
Stu stu;
int i = 0;
for (i = 0; i < 5; i++)
{
stu.id = i;
snprintf(stu.name, NAME_SIZE, "stu%d:", i);
stu.math = rand()%100;
stu.chinese = rand()%100;
pHead->listinsert(pHead, &stu, 2);
}
pHead->listprint(pHead, Printf_s);// 雙向鏈表打印
//鏈表元素的查找，通過id查找
printf("\n\n");
int id = 3;
Stu *st = pHead->listfind(pHead, &id, cmp_id);
if (st == NULL)
{
printf("can not find\n");
}
else
{
Printf_s(st);
}
//鏈表元素的刪除，通過id刪除
printf("\n\n");
pHead->listdestroy(pHead, &id, cmp_id);
pHead->listprint(pHead, Printf_s);
//鏈表元素的刪除，通過姓名刪除
printf("\n\n");
char* p = "stu2:";//不要忘了加分號(hào)
Stu *s = &stu;
pHead->listtravel(pHead, p, cmp_name, s);
if (s == NULL)
{
printf("can not find\n");
}
else
{
Printf_s(s);
}
printf("\n\n");
pHead->listprint(pHead, Printf_s);
pHead->destory(pHead);// 雙向鏈表銷毀
}
int main()
{
srand((unsigned)time(NULL));
test1();
return 0;
}
我們需要把我們通過函數(shù)實(shí)現(xiàn)的部分換位結(jié)構(gòu)體的調(diào)用。
五、帶頭循環(huán)雙鏈表封裝為庫
我們封裝為庫也是在實(shí)現(xiàn)二的基礎(chǔ)上進(jìn)行改動(dòng)的?。?！
1.帶頭循環(huán)雙鏈表封裝為庫的頭文件預(yù)覽
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<time.h>
#define HEADINSERTION 1 //頭插選項(xiàng)
#define BACKINSERTION 2 //尾插選項(xiàng)
//可以做出成一個(gè)動(dòng)態(tài)庫或靜態(tài)庫，不需要知道我們的結(jié)構(gòu)體類型就可以操作構(gòu)建一個(gè)結(jié)構(gòu)體
typedef void ListHead;// 把void類型改為ListHead，我們函數(shù)進(jìn)行傳參都是用的void
typedef void Printf(const void* );//對(duì)用戶傳遞的打印函數(shù)進(jìn)行重命名
typedef int Cmp(const void*, const void*);//對(duì)用戶傳遞的打印函數(shù)進(jìn)行重命名
ListHead* ListCreate(int datasize);//用來創(chuàng)建特殊的頭節(jié)點(diǎn)
void Destory(ListHead* pHead);// 雙向鏈表銷毀
void ListPrint(ListHead* pHead, Printf* print);// 雙向鏈表打印
int ListInsert(ListHead* pHead, const void* pos, int Optional);//雙向鏈表的插入
void* ListFind(ListHead* pHead, const void* key,Cmp* cmp);//雙向鏈表查找
int Listdestroy(ListHead* pHead, const void* key, Cmp* cmp);//雙向鏈表刪除
int Listtravel(ListHead* pHead, const void* key, Cmp* cmp,void* retu);//雙向鏈表刪除,并把刪除節(jié)點(diǎn)返回
這里我們實(shí)現(xiàn)了我們結(jié)構(gòu)體的隱藏，用戶不知道我們的結(jié)構(gòu)體類型，只知道我們函數(shù)可以實(shí)現(xiàn)什么的功能，且傳入的參數(shù)都是void指針類型。這里避免用戶知道我們的結(jié)構(gòu)體類型進(jìn)而進(jìn)行改動(dòng)。我們把結(jié)構(gòu)體類型放入到我們實(shí)現(xiàn)函數(shù)的源文件中。
2.帶頭循環(huán)雙鏈表函數(shù)實(shí)現(xiàn)的源文件
typedef struct ListNode//鏈表的節(jié)點(diǎn)
{
struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)的指針
struct ListNode* prev;//指向上一個(gè)節(jié)點(diǎn)的指針
char data[];//傳入的數(shù)據(jù)
}ListNode;
struct ListHead //不一樣的頭節(jié)點(diǎn)
{
int size;//用來存儲(chǔ)傳入數(shù)據(jù)的大小
ListNode list;//用來存儲(chǔ)頭節(jié)點(diǎn)的數(shù)據(jù)
};
ListHead* ListCreate(int datasize)//用來創(chuàng)建特殊的頭節(jié)點(diǎn)
{
struct ListHead* pHead = (struct ListHead*)malloc(sizeof(struct ListHead));
if (pHead == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("pHead malloc");
exit(-1);
}
pHead->size = datasize;
pHead->list.next = &pHead->list;//后繼節(jié)點(diǎn)指向自己
pHead->list.prev = &pHead->list;//前驅(qū)節(jié)點(diǎn)指向自己
return pHead;
}
void Destory(ListHead* p)// 雙向鏈表銷毀
{
assert(p);
struct ListHead *pHead = p;
ListNode* pos = (&pHead->list)->next;//從頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始
while (pos != &pHead->list)
{
ListNode* del = pos;//要釋放的節(jié)點(diǎn)
pos = pos->next;//保存下一個(gè)節(jié)點(diǎn)
free(del);
}
}
void ListPrint(ListHead* p, Printf * print)// 雙向鏈表打印，使用回調(diào)函數(shù)
{
assert(p);
struct ListHead* pHead = p;
ListNode* pos = pHead->list.next;
while (pos != &pHead->list)//判斷是否走到頭節(jié)點(diǎn)
{
print(pos->data);//調(diào)用用戶提供的打印函數(shù)
pos = pos->next;
}
}
int ListInsert(ListHead* p, const void* pos, int Optional)//雙向鏈表的插入
{
assert(p);
struct ListHead* pHead = p;
ListNode* node = (ListNode*)malloc(sizeof(ListNode)+pHead->size);//申請(qǐng)一個(gè)節(jié)點(diǎn)結(jié)構(gòu)體的大小加上用戶所傳數(shù)據(jù)大小
if (node == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("node malloc");//節(jié)點(diǎn)開辟失敗
return 1;//返回值為1代表節(jié)點(diǎn)開辟失敗
}
memcpy(node->data, (char*)pos,pHead->size);//把數(shù)據(jù)拷貝到我們開的節(jié)點(diǎn)中
if (HEADINSERTION == Optional)//判斷是否為頭插
{
node->next = (pHead->list).next;
node->prev = &(pHead->list);
}
else if (BACKINSERTION == Optional)//判斷是否為尾插
{
node->next = &pHead->list;
node->prev = pHead->list.prev;
}
else
{
return 2;//返回值為3代表插入位置不符合要求
}
node->prev->next = node;
node->next->prev = node;
return 0;//代表此函數(shù)正常結(jié)束
}
ListNode* find(ListHead* p, const void* key, Cmp* cmp)//雙向鏈表查找
{
assert(p);
struct ListHead* pHead = p;
ListNode* pos = pHead->list.next;
while (pos != &pHead->list)//判斷是否走到頭節(jié)點(diǎn)
{
if (cmp(key, pos->data) == 0)//調(diào)用用戶提供的比較函數(shù)
{
break;
}
pos = pos->next;
}
return pos;//如果找到時(shí)，循環(huán)終止，返回值為找到的節(jié)點(diǎn)，如果找不到，則返回pos為頭節(jié)點(diǎn)。
}
void* ListFind(ListHead* p, const void* key, Cmp* cmp)//雙向鏈表查找
{
assert(p);
struct ListHead* pHead = p;
ListNode* pos = find(pHead, key, cmp);
if (pos == &pHead->list)//如果是頭節(jié)點(diǎn)，則證明沒找到
{
return NULL;
}
return pos->data;//返會(huì)我們的數(shù)據(jù)區(qū)。
}
int Listdestroy(ListHead* p, const void* key, Cmp* cmp)//雙向鏈表刪除
{
assert(p);
struct ListHead* pHead = p;
ListNode* del = find(pHead, key, cmp);
if (del == &pHead->list)
{
return 1;//代表未找到我們要?jiǎng)h除的節(jié)點(diǎn)
}
//刪除節(jié)點(diǎn)
del->prev->next = del->next;
del->next->prev = del->prev;
free(del);
return 0;
}
int Listtravel(ListHead* p, const void* key, Cmp* cmp, void* retu)//雙向鏈表刪除,并把刪除節(jié)點(diǎn)返回
{
assert(p);
struct ListHead* pHead = p;
ListNode* del = find(pHead, key, cmp);
if (del == &pHead->list)
{
return 1;//代表未找到我們要?jiǎng)h除的節(jié)點(diǎn)
}
if (del->data != NULL)
{
memcpy(retu, del->data, pHead->size);//通過函數(shù)參數(shù)返回
}
//刪除節(jié)點(diǎn)
del->prev->next = del->next;
del->next->prev = del->prev;
free(del);
return 0;
}
我們改動(dòng)的地方就是在我們實(shí)現(xiàn)的函數(shù)中把void類型指針轉(zhuǎn)換位我們自己結(jié)構(gòu)體的類型。
我們測試函數(shù)用的和我們實(shí)現(xiàn)2一樣。
3.帶頭循環(huán)雙鏈表封裝成庫
1、找到項(xiàng)目，選擇屬性，在配置屬性里，將配置類型改為靜態(tài)庫 (.lib)。
2、生成
3、在我們這個(gè)項(xiàng)目文件中找到我們的.lib文件，即為生成的靜態(tài)庫。
六、對(duì)內(nèi)核雙鏈表部分分析來快速實(shí)現(xiàn)一個(gè)雙鏈表
1.對(duì)內(nèi)核雙鏈表部分分析
在鏈表中最重要的時(shí)節(jié)點(diǎn)指針，我們看內(nèi)核中的鏈表結(jié)構(gòu)，里面沒有數(shù)據(jù)區(qū)，我們要?jiǎng)?chuàng)建雙鏈表需要我們把他的結(jié)構(gòu)體包含在我們的結(jié)構(gòu)體中?？梢猿霈F(xiàn)在我們結(jié)構(gòu)體中的任何位置。
在這里實(shí)現(xiàn)的頭插和尾插都是定義的一個(gè)函數(shù)，然后調(diào)用這個(gè)函數(shù)實(shí)現(xiàn)我們插入刪除
2.快速來實(shí)現(xiàn)一個(gè)簡單的帶頭循環(huán)雙鏈表
typedef struct ListNode//鏈表的節(jié)點(diǎn)
{
int data;
struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)的指針
struct ListNode* prev;//指向上一個(gè)節(jié)點(diǎn)的指針
}ListNode;
ListNode* ListCreate()//用來創(chuàng)建頭節(jié)點(diǎn)
{
ListNode* pHead = (ListNode*)malloc(sizeof(ListNode));
if (pHead == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("pHead malloc");
exit(-1);
}
pHead->data = 0;
pHead->next = pHead;//后繼節(jié)點(diǎn)指向自己
pHead->prev = pHead;//前驅(qū)節(jié)點(diǎn)指向自己
return pHead;
}
void Destory(ListNode* pHead)// 雙向鏈表銷毀
{
assert(pHead);
ListNode* pos = pHead->next;//從頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始
while (pos != pHead)
{
ListNode* del = pos;//要釋放的節(jié)點(diǎn)
pos = pos->next;//保存下一個(gè)節(jié)點(diǎn)
free(del);//釋放節(jié)點(diǎn)
}
}
void ListPrint(ListNode* pHead)// 雙向鏈表打印
{
assert(pHead);
ListNode* pos = pHead->next;//從頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始
while (pos != pHead)
{
printf("%d->", pos->data);
pos = pos->next;
}
printf("\n");
}
void ListInsert(ListNode* pos, int key)//雙向鏈表的插入
{
assert(pos);
ListNode* init = (ListNode*)malloc(sizeof(ListNode));
if (init == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("pHead malloc");
exit(-1);
}
init->data = key;
init->next = pos->next;
init->prev = pos;
pos->next->prev = init;
pos->next = init;
}
void Listdestroy(ListNode* pHead,ListNode* pos)//雙向鏈表刪除
{
assert(pos);
if (pos == pHead)
{
return;
}
ListNode* del = pos;
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(del);
}
void SListPushBack(ListNode* pHead, int x)//單鏈表尾插
{
assert(pHead);
ListInsert(pHead->prev, x);
}
void SListPushFront(ListNode* pHead, int x)//單鏈表的頭插
{
assert(pHead);
ListInsert(pHead, x);
}
void SListPopBack(ListNode* pHead)// 單鏈表的尾刪
{
assert(pHead);
Listdestroy(pHead,pHead->prev);
}
void SListPopFront(ListNode* pHead)// 單鏈表頭刪
{
assert(pHead);
Listdestroy(pHead,pHead->next);
}
ListNode* ListFind(ListNode* pHead, int key)//雙向鏈表查找
{
assert(pos);
ListNode* pos = pHead->next;
while (pos != pHead)
{
if (pos->data == key)
{
return pos;
}
pos = pos->next;
}
return NULL;
}
根據(jù)上面的代碼我們可以看出我們只需要實(shí)現(xiàn)雙鏈表的插入和刪除就把雙鏈表的大部分功能實(shí)現(xiàn)了。
相信通過這么多的案例和練習(xí)，大家對(duì)雙鏈表的實(shí)現(xiàn)和用途都有了解了，自己動(dòng)手實(shí)現(xiàn)一下吧。
七、雙鏈表實(shí)現(xiàn)2的代碼
由于我們的后面封裝和構(gòu)成庫都是通過2來進(jìn)行改變的，我們把實(shí)現(xiàn)2的代碼來具體看看一下把文章來源：http://www.zghlxwxcb.cn/news/detail-638542.html
1.雙鏈表實(shí)現(xiàn)2的代碼的頭文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<time.h>
#define HEADINSERTION 1 //頭插選項(xiàng)
#define BACKINSERTION 2 //尾插選項(xiàng)
typedef struct ListNode//鏈表的節(jié)點(diǎn)
{
struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)的指針
struct ListNode* prev;//指向上一個(gè)節(jié)點(diǎn)的指針
char data[];//傳入的數(shù)據(jù)
//char data[1];//傳入的數(shù)據(jù)
}ListNode;
typedef struct ListHead //不一樣的頭節(jié)點(diǎn)
{
int size;//用來存儲(chǔ)傳入數(shù)據(jù)的大小
ListNode list;//用來存儲(chǔ)頭節(jié)點(diǎn)的數(shù)據(jù)
}ListHead;
typedef void Printf(const void* );//對(duì)用戶傳遞的打印函數(shù)進(jìn)行重命名
typedef int Cmp(const void*, const void*);//對(duì)用戶傳遞的打印函數(shù)進(jìn)行重命名
ListHead* ListCreate(int datasize);//用來創(chuàng)建特殊的頭節(jié)點(diǎn)
void Destory(ListHead* pHead);// 雙向鏈表銷毀
void ListPrint(ListHead* pHead, Printf* print);// 雙向鏈表打印
int ListInsert(ListHead* pHead, const void* pos, int Optional);//雙向鏈表的插入
void* ListFind(ListHead* pHead, const void* key,Cmp* cmp);//雙向鏈表查找
int Listdestroy(ListHead* pHead, const void* key, Cmp* cmp);//雙向鏈表刪除
int Listtravel(ListHead* pHead, const void* key, Cmp* cmp,void* retu);//雙向鏈表刪除,并把刪除節(jié)點(diǎn)返回
2.雙鏈表實(shí)現(xiàn)2的函數(shù)實(shí)現(xiàn)源文件
#include"main2.h"
ListHead* ListCreate(int datasize)//用來創(chuàng)建特殊的頭節(jié)點(diǎn)
{
ListHead* pHead = (ListHead*)malloc(sizeof(ListHead));
if (pHead == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("pHead malloc");
exit(-1);
}
pHead->size = datasize;
pHead->list.next = &pHead->list;//后繼節(jié)點(diǎn)指向自己
pHead->list.prev = &pHead->list;//前驅(qū)節(jié)點(diǎn)指向自己
return pHead;
}
void Destory(ListHead* pHead)// 雙向鏈表銷毀
{
assert(pHead);
ListNode* pos = (&pHead->list)->next;//從頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始
while (pos != &pHead->list)
{
ListNode* del = pos;//要釋放的節(jié)點(diǎn)
pos = pos->next;//保存下一個(gè)節(jié)點(diǎn)
free(del);
}
}
void ListPrint(ListHead* pHead, Printf * print)// 雙向鏈表打印，使用回調(diào)函數(shù)
{
assert(pHead);
ListNode* pos = pHead->list.next;
while (pos != &pHead->list)//判斷是否走到頭節(jié)點(diǎn)
{
print(pos->data);//調(diào)用用戶提供的打印函數(shù)
pos = pos->next;
}
}
int ListInsert(ListHead* pHead, const void* pos, int Optional)//雙向鏈表的插入
{
assert(pHead);
ListNode* node = (ListNode*)malloc(sizeof(ListNode)+pHead->size);//申請(qǐng)一個(gè)節(jié)點(diǎn)結(jié)構(gòu)體的大小加上用戶所傳數(shù)據(jù)大小
if (node == NULL)//開辟空間失敗就報(bào)錯(cuò)結(jié)束
{
perror("node malloc");//節(jié)點(diǎn)開辟失敗
return 1;//返回值為1代表節(jié)點(diǎn)開辟失敗
}
memcpy(node->data, (char*)pos,pHead->size);//把數(shù)據(jù)拷貝到我們開的節(jié)點(diǎn)中
if (HEADINSERTION == Optional)//判斷是否為頭插
{
node->next = (pHead->list).next;
node->prev = &(pHead->list);
}
else if (BACKINSERTION == Optional)//判斷是否為尾插
{
node->next = &pHead->list;
node->prev = pHead->list.prev;
}
else
{
return 2;//返回值為3代表插入位置不符合要求
}
node->prev->next = node;
node->next->prev = node;
return 0;//代表此函數(shù)正常結(jié)束
}
ListNode* find(ListHead* pHead, const void* key, Cmp* cmp)//雙向鏈表查找
{
assert(pHead);
ListNode* pos = pHead->list.next;
while (pos != &pHead->list)//判斷是否走到頭節(jié)點(diǎn)
{
if (cmp(key, pos->data) == 0)//調(diào)用用戶提供的比較函數(shù)
{
break;
}
pos = pos->next;
}
return pos;//如果找到時(shí)，循環(huán)終止，返回值為找到的節(jié)點(diǎn)，如果找不到，則返回pos為頭節(jié)點(diǎn)。
}
void* ListFind(ListHead* pHead, const void* key, Cmp* cmp)//雙向鏈表查找
{
assert(pHead);
ListNode* pos = find(pHead, key, cmp);
if (pos == &pHead->list)//如果是頭節(jié)點(diǎn)，則證明沒找到
{
return NULL;
}
return pos->data;//返會(huì)我們的數(shù)據(jù)區(qū)。
}
int Listdestroy(ListHead* pHead, const void* key, Cmp* cmp)//雙向鏈表刪除
{
assert(pHead);
ListNode* del = find(pHead, key, cmp);
if (del == &pHead->list)
{
return 1;//代表未找到我們要?jiǎng)h除的節(jié)點(diǎn)
}
//刪除節(jié)點(diǎn)
del->prev->next = del->next;
del->next->prev = del->prev;
free(del);
return 0;
}
int Listtravel(ListHead* pHead, const void* key, Cmp* cmp, void* retu)//雙向鏈表刪除,并把刪除節(jié)點(diǎn)返回
{
assert(pHead);
ListNode* del = find(pHead, key, cmp);
if (del == &pHead->list)
{
return 1;//代表未找到我們要?jiǎng)h除的節(jié)點(diǎn)
}
if (del->data != NULL)
{
memcpy(retu, del->data, pHead->size);//通過函數(shù)參數(shù)返回
}
//刪除節(jié)點(diǎn)
del->prev->next = del->next;
del->next->prev = del->prev;
free(del);
return 0;
}
3.雙鏈表實(shí)現(xiàn)2的主函數(shù)源文件
#include"main2.h"
#define NAME_SIZE 32
typedef struct Stu
{
int id;
char name[NAME_SIZE];
int math;
int chinese;
}Stu;
void Printf_s(const void* print)//用戶寫的打印函數(shù)
{
Stu* prin = (Stu*)print;
printf("id:%2d name:%s math:%2d chinese:%2d\n",prin->id, prin->name, prin->math, prin->chinese);
}
int cmp_id(const void* s1, const void*s2)//用戶寫的比較函數(shù)
{
int *key = (int*)s1;
Stu *stu = (Stu*)s2;
return (*key - stu->id);
}
int cmp_name(const void* s1, const void* s2)//用戶寫的name比較函數(shù)
{
char* key = (char*)s1;
Stu* stu = (Stu*)s2;
return strcmp(key, stu->name);
}
void test1()
{
ListHead* pHead = ListCreate(sizeof(Stu));
Stu stu;
int i = 0;
for (i = 0; i < 5; i++)
{
stu.id = i;
snprintf(stu.name, NAME_SIZE, "stu%d:", i);
stu.math = rand()%100;
stu.chinese = rand()%100;
ListInsert(pHead, &stu, 1);//傳入1，進(jìn)行頭插
//ListInsert(pHead, &stu, 2);//傳入2，進(jìn)行尾插
}
ListPrint(pHead, Printf_s);// 雙向鏈表打印
//鏈表元素的查找，通過id查找
printf("\n\n");
int id = 3;
Stu *st = ListFind(pHead, &id, cmp_id);
if (st == NULL)
{
printf("can not find\n");
}
else
{
Printf_s(st);
}
//鏈表元素的刪除，通過id刪除
printf("\n\n");
Listdestroy(pHead, &id, cmp_id);
ListPrint(pHead, Printf_s);
//鏈表元素的刪除并且返回，通過姓名刪除
printf("\n\n");
char* p = "stu2:";//不要忘了加分號(hào)
Stu *s = &stu;
Listtravel(pHead, p, cmp_name, s);
if (s == NULL)
{
printf("can not find\n");
}
else
{
Printf_s(s);
}
printf("\n\n");
ListPrint(pHead, Printf_s);
Destory(pHead);// 雙向鏈表銷毀
}
int main()
{
srand((unsigned)time(NULL));
test1();
return 0;
}
總結(jié)
相信大家對(duì)我們雙鏈表已經(jīng)有了很深的了解，這個(gè)帶頭循環(huán)鏈表將是我們使用最多的結(jié)構(gòu)，所以這個(gè)需要我們深刻理解掌握。歡迎大家留言。感謝支持呀。文章來源地址http://www.zghlxwxcb.cn/news/detail-638542.html
到了這里，關(guān)于帶你玩轉(zhuǎn)雙鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[阿里云] 10分鐘帶你玩轉(zhuǎn)阿里云ECS和云盤 (大數(shù)據(jù)上云必備)](https://imgs.yssmx.com/Uploads/2024/02/787568-1.png)
