欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言實(shí)現(xiàn)帶頭雙向環(huán)形鏈表

 更新時(shí)間:2021年11月26日 17:29:07   作者:aiyubaobei  
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)帶頭雙向環(huán)形鏈表,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

雙向循環(huán)鏈表

上一次我們講了單向無頭非循環(huán)鏈表的實(shí)現(xiàn),單向無頭非循環(huán)鏈表的特點(diǎn)是:結(jié)構(gòu)簡單,一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)。而帶頭雙向循環(huán)鏈表則恰恰與無頭單向非循環(huán)鏈表相反,它的結(jié)構(gòu)最復(fù)雜,一般用來單獨(dú)存儲(chǔ)數(shù)據(jù)。這個(gè)結(jié)構(gòu)雖然復(fù)雜,但是使用單嗎實(shí)現(xiàn)后會(huì)發(fā)現(xiàn),這個(gè)結(jié)構(gòu)用起來很簡單。

結(jié)構(gòu)示意圖

帶頭雙向循環(huán)鏈表在邏輯上大概就是這樣的一個(gè)樣子,鏈表的最后一個(gè)節(jié)點(diǎn)的后繼指向的是頭結(jié)點(diǎn)。而頭結(jié)點(diǎn)的前驅(qū)則是指向鏈表的最后一個(gè)結(jié)點(diǎn)。所以,一個(gè)空的帶頭雙向循環(huán)鏈表的邏輯結(jié)構(gòu)應(yīng)該是這樣的:

它的前驅(qū)和后繼都是指向的頭結(jié)點(diǎn)。

實(shí)現(xiàn)帶頭雙向循環(huán)鏈表

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
// 定義鏈表的節(jié)點(diǎn)
typedef struct ListNode {
 LTDataType data;
 struct ListNode* prev;
 struct ListNode* next;
}LTNode;

// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn).
LTNode* ListCreate();
// 雙向鏈表銷毀
void ListDestory(LTNode* pHead);
// 雙向鏈表打印
void ListPrint(LTNode* pHead);
// 雙向鏈表尾插
void ListPushBack(LTNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(LTNode* pHead);
// 雙向鏈表頭插
void ListPushFront(LTNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(LTNode* pHead);
// 雙向鏈表查找
LTNode* ListFind(LTNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(LTNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(LTNode* pos);

首先我們得定義一個(gè)結(jié)點(diǎn)的結(jié)構(gòu),它由前驅(qū)指針、后繼指針和數(shù)據(jù)這三部分組成。

// 定義鏈表的節(jié)點(diǎn)
typedef struct ListNode {
 LTDataType data;
 struct ListNode* prev;
 struct ListNode* next;
}LTNode;

定義好之后,我們要?jiǎng)?chuàng)建一個(gè)頭結(jié)點(diǎn)。我們把創(chuàng)建頭結(jié)點(diǎn)的過程也封裝成一個(gè)函數(shù),這個(gè)函數(shù)的返回值就是頭結(jié)點(diǎn)的指針。我們在使用的時(shí)候就創(chuàng)建一個(gè)變量來接收這個(gè)指針。

**注意:**頭結(jié)點(diǎn)創(chuàng)建的時(shí)候,它的data部分是不存數(shù)據(jù)的,它的前驅(qū)和后繼都是指向它自己

LTNode* ListCreate() {
 LTNode* head = (LTNode*)malloc(sizeof(LTNode));
 head->next = head;
 head->prev = head;
 return head;
}
// 在main函數(shù)中是這樣使用的
int main(){
    LTNode* head = ListCreate();
    return 0;
}

創(chuàng)建好頭結(jié)點(diǎn)之后就可以向鏈表中插入數(shù)據(jù)了,首先實(shí)現(xiàn)尾插,就是在鏈表的最后一個(gè)結(jié)點(diǎn)后面再插入一個(gè)結(jié)點(diǎn)。然后就是頭插法,頭插法就是在頭結(jié)點(diǎn)的后面插入一個(gè)新節(jié)點(diǎn)。

// 雙向鏈表尾插
void ListPushBack(LTNode* pHead, LTDataType x) {
 assert(pHead);
 LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); // 創(chuàng)建的新節(jié)點(diǎn)
 newnode->data = x;
    // 將新節(jié)點(diǎn)插入到鏈表中
 LTNode* prev = pHead->prev;
 prev->next = newnode;
 newnode->prev = prev;
 newnode->next = pHead;
 pHead->prev = newnode;

}
// 雙向鏈表頭插
void ListPushFront(LTNode* pHead, LTDataType x) {
 assert(pHead);
    // 創(chuàng)建新節(jié)點(diǎn)
 LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
 newnode->data = x;
    //將新節(jié)點(diǎn)插入鏈表
 LTNode* next = pHead->next;
 pHead->next = newnode;
 newnode->prev = pHead;
 newnode->next = next;
 next->prev = newnode;
}

有插入數(shù)據(jù)就有刪除數(shù)據(jù),同樣的刪除數(shù)據(jù)也有兩種,一個(gè)是頭刪一個(gè)是尾刪。頭刪就是將頭結(jié)點(diǎn)的next指向的那個(gè)結(jié)點(diǎn)刪除。尾刪,就是將最后一個(gè)節(jié)點(diǎn)刪掉。帶頭雙向循環(huán)鏈表,在我們尾刪的時(shí)候就很方便。因?yàn)轭^結(jié)點(diǎn)的前驅(qū)指向的節(jié)點(diǎn)就是鏈表的最后一個(gè)節(jié)點(diǎn),就不需要我們再遍歷鏈表去找最后一個(gè)節(jié)點(diǎn)的地址。

// 雙向鏈表頭刪
void ListPopFront(LTNode* pHead) {
 assert(pHead);
 assert(pHead->next != pHead);
    // 定義一個(gè)臨時(shí)變量來保存我們要?jiǎng)h掉的節(jié)點(diǎn)的位置
 LTNode* popnode = pHead->next;
    // 將要?jiǎng)h除節(jié)點(diǎn)的鏈都斷掉
 LTNode* next = popnode->next;
 pHead->next = popnode->next;
 next->prev = pHead;
    // free掉那個(gè)節(jié)點(diǎn)
 free(popnode);
 popnode = NULL;
}
// 雙向鏈表尾刪
void ListPopBack(LTNode* pHead) {
 assert(pHead);
 assert(pHead->prev != pHead);
 LTNode* popnode = pHead->prev;
 LTNode* prev = popnode->prev;
 prev->next = pHead;
 pHead->prev = prev;
 free(popnode);
 popnode = NULL;
}

在實(shí)現(xiàn)了增加和刪除節(jié)點(diǎn)之后,我們就實(shí)現(xiàn)查找結(jié)點(diǎn)。方法也是遍歷整個(gè)鏈表,如果有一個(gè)節(jié)點(diǎn)的data的值和x相同就返回這個(gè)節(jié)點(diǎn)的地址。如果沒找到就返回空。

// 雙向鏈表查找
LTNode* ListFind(LTNode* pHead, LTDataType x) {
 if (pHead->next == pHead) {
  return NULL;
 }
 LTNode* find = pHead->next;
 while (find != pHead) {
  if (find->data == x) {
   return find;
  }
  find = find->next;
 }
 return NULL;
}

實(shí)現(xiàn)隨機(jī)插入數(shù)據(jù),這里的隨機(jī)插入的意思是,我們把新節(jié)點(diǎn)插入到我們指定的節(jié)點(diǎn)的后面一個(gè)或前面一個(gè)。這個(gè)節(jié)點(diǎn)可以是在鏈表的任何一個(gè)地方。我們這個(gè)函數(shù)會(huì)傳入一個(gè)節(jié)點(diǎn)的地址,通過那個(gè)地址可以找到要出入的那個(gè)節(jié)點(diǎn),把新節(jié)點(diǎn)連接到那個(gè)節(jié)點(diǎn)后面就可以了

// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(LTNode* pos) {
 assert(pos);
 LTNode* prev = pos->prev;
 LTNode* next = pos->next;
 prev->next = next;
 next->prev = prev;
 free(pos);
 pos = NULL;
}

打印雙向循環(huán)鏈表,也是通過遍歷鏈表來打印

// 雙向鏈表打印
void ListPrint(LTNode* pHead) {
 assert(pHead);
 LTNode* tail = pHead->next;
 while (tail != pHead) {
  printf("%d->", tail->data);
  tail = tail->next;
 }
}

在我們使用完鏈表后,要記得銷毀鏈表,防止內(nèi)存泄漏

// 雙向鏈表銷毀
void ListDestory(LTNode* pHead) {
 assert(pHead);
 LTNode* tail = pHead->next;
 while (tail != pHead) {
  LTNode* tmp = tail->next;
  free(tail);
  tail = tmp;
 }
 free(pHead);
 pHead = NULL;
}

以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • C語言 遞歸解決青蛙跳臺(tái)階問題

    C語言 遞歸解決青蛙跳臺(tái)階問題

    遞歸做為一種算法在程序設(shè)計(jì)語言中廣泛應(yīng)用?;竞x&#8203;是指函數(shù)/過程/子程序在運(yùn)行過程序中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)象。在計(jì)算機(jī)編程里,遞歸指的是一個(gè)過程:函數(shù)不斷引用自身,直到引用的對象已知
    2021-11-11
  • 詳解C++ 拷貝構(gòu)造函數(shù)

    詳解C++ 拷貝構(gòu)造函數(shù)

    這篇文章主要介紹了C++ 拷貝構(gòu)造函數(shù)的相關(guān)資料,文中示例代碼非常詳細(xì),幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下
    2020-07-07
  • C++ 迭代器失效問題解決

    C++ 迭代器失效問題解決

    在C++中,當(dāng)一個(gè)vector進(jìn)行了插入或刪除操作時(shí),其迭代器可能會(huì)失效,本文就來介紹一下C++ 迭代器失效問題解決,具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-01-01
  • C++11互斥量的具體使用

    C++11互斥量的具體使用

    互斥量是一種同步原語,是一種線程同步的手段,用來保護(hù)多線程同時(shí)訪問的共享數(shù)據(jù),本文主要介紹了C++11互斥量的具體使用,感興趣的可以了解一下
    2023-11-11
  • 深入探討C語言中局部變量與全局變量在內(nèi)存中的存放位置

    深入探討C語言中局部變量與全局變量在內(nèi)存中的存放位置

    本篇文章是對在C語言中局部變量與全局變量在內(nèi)存中的存放位置進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • Qt網(wǎng)絡(luò)編程實(shí)現(xiàn)TCP通信

    Qt網(wǎng)絡(luò)編程實(shí)現(xiàn)TCP通信

    這篇文章主要為大家詳細(xì)介紹了Qt網(wǎng)絡(luò)編程實(shí)現(xiàn)TCP通信,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-08-08
  • C語言中的指針新手初階指南

    C語言中的指針新手初階指南

    指針是C語言的靈魂,精華之所在,指針強(qiáng)大而危險(xiǎn),用得好是一大利器,用得不好是一大潛在危害,下面這篇文章主要給大家介紹了C語言中指針的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2021-10-10
  • OpenCV實(shí)現(xiàn)馬賽克功能

    OpenCV實(shí)現(xiàn)馬賽克功能

    這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)馬賽克功能,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • C語言全面講解順序表使用操作

    C語言全面講解順序表使用操作

    線性表是最簡單的數(shù)據(jù)結(jié)構(gòu),而順序表又是最簡單的線性表,其基本思想是用一段地址連續(xù)的儲(chǔ)存單元依次存儲(chǔ)線性表的數(shù)據(jù)元素,比如我們常用的一維數(shù)組,下面代碼實(shí)現(xiàn)了順序表的定義以及基本操作
    2022-04-04
  • C語言巧用二分查找實(shí)現(xiàn)猜數(shù)游戲

    C語言巧用二分查找實(shí)現(xiàn)猜數(shù)游戲

    二分查找也稱折半查找(Binary?Search),它是一種效率較高的查找方法。但是,折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu),而且表中元素按關(guān)鍵字有序排列,本篇文章教你用二分查找編寫猜數(shù)字游戲
    2022-02-02

最新評論