C++代碼實現(xiàn)雙向鏈表
本文實例為大家分享了C++實現(xiàn)雙向鏈表的具體代碼,供大家參考,具體內(nèi)容如下
雙向鏈表:兩個指針域,一個指向前結(jié)點,一個指向后結(jié)點
list.h
#pragma once #define OK ?? ??? ?1 #define ERROR ?? ?0 #define TRUE ?? ?1 #define FALSE ?? ?0 typedef int Status; typedef int ElemType; typedef struct DNode { ?? ?struct DNode *prior;?? ??? ?//前結(jié)點指針域 ?? ?ElemType data;?? ??? ??? ??? ?//數(shù)據(jù)域 ?? ?struct DNode *next;?? ??? ??? ?//后結(jié)點指針域 }DNode, *DLinkList;?? ??? ??? ??? ?//結(jié)點和指向結(jié)點的指針 bool InitDLinkList(DLinkList &L);?? ??? ??? ??? ??? ??? ?//雙鏈表初始化 Status CreatDLinkList(DLinkList &L);?? ??? ??? ??? ??? ?//尾插法創(chuàng)建鏈表,包含初始化功能 bool InsertNextDNode(DNode *p, DNode *s);?? ??? ??? ??? ?//結(jié)點s插入在結(jié)點p之后 Status DeleteNextDNode(DNode *p, ElemType &e);?? ??? ??? ?//刪除結(jié)點p的后繼節(jié)點?? ??? ??? ??? ? void ListTraverse(const DLinkList L);?? ??? ??? ??? ??? ?//雙鏈表的遍歷 Status ListInsert(DLinkList &L, int i, ElemType e);?? ??? ?//指定位置插入元素 Status ListDelete(DLinkList &L, int i, ElemType &e);?? ?//指定位置刪除元素 DNode* GetElem(DLinkList L, int i);?? ??? ??? ??? ??? ??? ?//查找鏈表指定位置節(jié)點,返回的是結(jié)點 void DestoryList(DLinkList &L);?? ??? ??? ??? ??? ??? ??? ?//銷毀雙鏈表,需要釋放頭結(jié)點
oper_func.cpp
#include <iostream> #include"list.h" bool InitDLinkList(DLinkList &L) { ?? ?//構(gòu)建空的雙鏈表,作為雙鏈表的頭結(jié)點,數(shù)據(jù)域為空 ?? ?L = new DNode; ?? ?if (L == NULL)?? ??? ??? ??? ?//內(nèi)存分配失敗 ?? ??? ?return FALSE; ?? ?L->prior = NULL;?? ??? ??? ?//頭結(jié)點的前驅(qū)指針始終指向NULL?? ? ?? ?L->next = NULL;?? ??? ??? ??? ?//暫時指向NULL ?? ?return TRUE; } Status CreatDLinkList(DLinkList &L) { ?? ?//利用InsertNextDNode函數(shù)來創(chuàng)建 ?? ?using std::cin; ?? ?using std::cout; ?? ?using std::endl; ?? ?if (InitDLinkList(L)) ?? ?{ ?? ??? ?DNode *s,*r = L;?? ??? ??? ??? ?//s為新建的新結(jié)點,用來存儲數(shù)據(jù),而r為尾指針,始終指向尾部節(jié)點 ?? ??? ?int num; ?? ??? ?cout << "輸入你需要創(chuàng)建的雙鏈表的個數(shù):"; ?? ??? ?cin >> num; ?? ??? ?for (int i = 1; i <= num; i++) ?? ??? ?{ ?? ??? ??? ?s = new DNode;?? ??? ??? ??? ?//創(chuàng)建的新結(jié)點 ?? ??? ??? ?cout << "輸入第" << i << "個元素:"; ?? ??? ??? ?cin >> s->data;?? ??? ??? ??? ?//輸入數(shù)據(jù) ?? ??? ??? ?s->next = NULL; ?? ??? ??? ?InsertNextDNode(r,s);?? ??? ?//結(jié)點s插在尾部節(jié)點之后 ?? ??? ??? ?r = s;?? ??? ??? ??? ??? ??? ?//尾指針指向新的尾結(jié)點 ?? ??? ?} ?? ??? ?return OK; ?? ?} ?? ?else ?? ?{ ?? ??? ?cout << "內(nèi)存不夠,單鏈表創(chuàng)建失?。? << endl; ?? ??? ?return ERROR; ?? ?} } //結(jié)點s插入在結(jié)點p之后 bool InsertNextDNode(DNode *p, DNode *s) { ?? ?if (p == NULL || s == NULL) ?? ??? ?return FALSE;?? ??? ??? ?//非法參數(shù) ?? ?s->next = p->next; ?? ?if (p->next != NULL)?? ??? ?//如果p不是最后一個結(jié)點 ?? ?{ ?? ??? ?p->next->prior = s; ?? ?} ?? ?s->prior = p; ?? ?p->next = s; ?? ?return TRUE; } Status DeleteNextDNode(DNode *p, ElemType &e) { ?? ?if(p == NULL) ?? ??? ?return FALSE;?? ??? ??? ?//非法參數(shù) ?? ?DNode *q = p->next;?? ??? ??? ?//找到p節(jié)點的后繼節(jié)點 ?? ?if (q == NULL)?? ??? ??? ??? ?//節(jié)點p沒有后繼節(jié)點 ?? ?{ ?? ??? ?return ERROR; ?? ?} ?? ?else ?? ?{ ?? ??? ?//有后繼節(jié)點,但是p的后繼節(jié)點為空 ?? ??? ?p->next = q->next; ?? ??? ?e = q->data; ?? ??? ?if (q->next != NULL) ?? ??? ?{ ?? ??? ??? ?q->next->prior = p; ?? ??? ?} ?? ??? ?delete q; ?? ??? ?return OK; ?? ?} } void ListTraverse(const DLinkList L) { ?? ?using std::cout; ?? ?using std::endl; ?? ?int i = 1; ?? ?DNode *p = L->next;?? ??? ??? ??? ??? ?//指向第一個元素 ?? ?if (p == NULL) ?? ?{ ?? ??? ?cout << "雙鏈表為空,無法輸出元素!" << endl; ?? ??? ?return; ?? ?} ?? ?while (p) ?? ?{ ?? ??? ?cout << "第" << i++ << "個元素為:" << p->data << endl; ?? ??? ?p = p->next; ?? ?} } Status ListDelete(DLinkList &L, int i, ElemType &e) { ?? ?if (i < 1)?? ??? ? ?? ??? ?//位置不合理 ?? ??? ?return ERROR; ?? ?//尋找第i-1個結(jié)點 ?? ?DNode *p = GetElem(L, i - 1); ?? ?//刪除i-1結(jié)點的后面結(jié)點 ?? ?return DeleteNextDNode(p,e); } DNode* GetElem(DLinkList L, int i) { ?? ?DNode *p = L; ?? ?int j = 0;?? ??? ??? ??? ?//表示p指向的當(dāng)前結(jié)點的位置,此時為頭結(jié)點 ?? ?while (p != NULL && j < i) ?? ?{ ?? ??? ?p = p->next;?? ??? ?//指向下一個結(jié)點 ?? ??? ?j++; ?? ?} ?? ?return p; } void DestoryList(DLinkList &L) { ?? ?using std::cout; ?? ?using std::endl; ?? ?ElemType temp; ?? ?int i = 1; ?? ?while (L->next != NULL) ?? ?{ ?? ??? ?DeleteNextDNode(L,temp); ?? ??? ?cout << "第" << i++ << "個刪除的元素為:" << temp << endl; ?? ?} ?? ?cout << "雙鏈表全部數(shù)據(jù)銷毀成功!" << endl; ?? ?delete L; ?? ?cout << "頭結(jié)點銷毀,整個雙鏈表銷毀成功!" << endl; ?? ?L = NULL;?? ??? ??? ??? ?//頭指針指向NULL } Status ListInsert(DLinkList &L, int i, ElemType e) { ?? ?if (i < 1) ?? ??? ?return FALSE; ?? ?//尋找第i-1個結(jié)點 ?? ?DNode *p = GetElem(L, i - 1); ?? ?//直接在i-1結(jié)點的后面插入元素即可 ?? ?DNode *s = new DNode;?? ??? ?//新建節(jié)點 ?? ?s->data = e; ?? ?s->next = NULL; ?? ?s->prior = NULL; ?? ?return InsertNextDNode(p,s); }
main.cpp
/* 雙向鏈表:帶頭結(jié)點,且頭結(jié)點的prior指針時鐘指向為NULL 1、雙鏈表的初始化 2、雙鏈表的創(chuàng)建 3、雙鏈表的結(jié)點插入(相當(dāng)于后插操作):(結(jié)點s插入結(jié)點p之后)需要考慮p結(jié)點是不是最后一個結(jié)點 ?? ?如果想前插操作,則找到該節(jié)點的i-1節(jié)點,然后實行后插操作也是一樣 4、雙鏈表的結(jié)點刪除(相當(dāng)于后刪操作):(刪除p節(jié)點的后序節(jié)點q)需要考慮p結(jié)點是不是最后一個結(jié)點 ?? ?也要考慮q節(jié)點是不是最后一個結(jié)點 5、雙鏈表的刪除: 6、雙鏈表的遍歷: 7、雙鏈表的銷毀:需要回收頭結(jié)點 */ #include <iostream> #include"list.h" void showMenu() { ?? ?using std::cout; ?? ?using std::cin; ?? ?using std::endl; ?? ?cout << "*********************************************************" << endl; ?? ?cout << "*** 1.指定位置插入元素?? ??? ??? ?2.刪除指定位置元素 ***" << endl; ?? ?cout << "*** 3.遍歷單鏈表?? ??? ??? ?0.銷毀雙鏈表并退出 ***" << endl; ?? ?cout << "*********************************************************" << endl; } int main() { ?? ?using std::cout; ?? ?using std::cin; ?? ?using std::endl; ?? ?int select = 0, flag = -1;?? ??? ??? ?//輸入的選擇 ?? ?DLinkList L;?? ??? ??? ??? ?//L表示頭指針,始終指向表頭 ?? ?if (CreatDLinkList(L))?? ??? ?//尾插法創(chuàng)建單鏈表 ?? ?{ ?? ??? ?cout << "雙鏈表創(chuàng)建成功!" << endl; ?? ?} ?? ?else ?? ??? ?cout << "雙鏈表創(chuàng)建失敗!" << endl; ?? ?while (true) ?? ?{ ?? ??? ?showMenu(); ?? ??? ?cout << "輸入你的選擇:"; ?? ??? ?cin >> select; ?? ??? ?switch (select) ?? ??? ?{ ?? ??? ?case 1: {?? ??? ?//指定位置插入元素 ?? ??? ??? ?int position = 0, elem = 0; ?? ??? ??? ?cout << "輸入插入的位置和元素:"; ?? ??? ??? ?cin >> position >> elem; ?? ??? ??? ?if (ListInsert(L, position, elem)) ?? ??? ??? ??? ?cout << "指定位置插入元素成功!" << endl; ?? ??? ??? ?else ?? ??? ??? ??? ?cout << "內(nèi)存分配失敗或者插入位置越界,插入失??!" << endl; ?? ??? ?} ?? ??? ??? ??? ?break; ?? ??? ?case 2: {?? ??? ?//刪除指定位置節(jié)點 ?? ??? ??? ?int position = 0, elem = 0; ?? ??? ??? ?cout << "輸入指定位置:"; ?? ??? ??? ?cin >> position; ?? ??? ??? ?if (ListDelete(L, position, elem)) ?? ??? ??? ?{ ?? ??? ??? ??? ?cout << "刪除指定位置元素成功!元素為:" << elem << endl; ?? ??? ??? ?} ?? ??? ??? ?else ?? ??? ??? ?{ ?? ??? ??? ??? ?cout << "單鏈表為空或者刪除位置不合理!" << endl; ?? ??? ??? ?} ?? ??? ?} ?? ??? ??? ??? ?break; ?? ??? ?case 3: { ?? ??? ??? ?ListTraverse(L); ?? ??? ?} ?? ??? ??? ??? ?break; ?? ??? ?case 0: { ?? ??? ??? ?DestoryList(L); ?? ??? ??? ?system("pause"); ?? ??? ??? ?return 0; ?? ??? ?} ?? ??? ?break; ?? ??? ?} ?? ?} ?? ?return 0; }
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
詳解C++中十六進制字符串轉(zhuǎn)數(shù)字(數(shù)值)
這篇文章主要介紹了詳解C++中十六進制字符串轉(zhuǎn)數(shù)字(數(shù)值)的相關(guān)資料,這里提供兩種實現(xiàn)方法,需要的朋友可以參考下2017-08-08C++11新特性中auto 和 decltype 區(qū)別和聯(lián)系
這篇文章主要介紹了C++11新特性中auto 和 decltype 區(qū)別和聯(lián)系的相關(guān)資料,需要的朋友可以參考下2017-01-01解析一個有關(guān)sizeof用法的題目--sizeof(i++)
本篇文章是對一個關(guān)于sizeof用法的題目進行了詳細的分析介紹,需要的朋友參考下2013-06-06C語言數(shù)據(jù)結(jié)構(gòu)中二分查找遞歸非遞歸實現(xiàn)并分析
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)中二分查找遞歸非遞歸實現(xiàn)并分析的相關(guān)資料,需要的朋友可以參考下2017-03-03QT Creator+OpenCV實現(xiàn)圖像灰度化的示例代碼
這篇文章主要為大家詳細介紹了QT如何利用Creator和OpenCV實現(xiàn)圖像灰度化效果,文中的示例代碼講解詳細,感興趣的小伙伴可以嘗試一下2022-12-12關(guān)于C++讀入數(shù)字按位取出與進制轉(zhuǎn)換問題(典型問題)
這篇文章主要介紹了關(guān)于C++讀入數(shù)字按位取出與進制轉(zhuǎn)換問題,是一個非常典型的問題,本文通過實例舉例給大家介紹的非常詳細,需要的朋友可以參考下2020-02-02C++11中跳轉(zhuǎn)initializer_list實現(xiàn)分析
這篇文章主要介紹了C++11中跳轉(zhuǎn)initializer_list實現(xiàn)分析,實例分析initializer_list<T>初體驗,結(jié)合示例代碼給大家介紹的非常詳細,需要的朋友可以參考下2022-04-04