C++代碼實現雙向鏈表
更新時間:2022年05月26日 16:23:43 作者:追夢的小年青
這篇文章主要為大家詳細介紹了C++代碼實現雙向鏈表,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
本文實例為大家分享了C++實現雙向鏈表的具體代碼,供大家參考,具體內容如下
雙向鏈表:兩個指針域,一個指向前結點,一個指向后結點
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;?? ??? ?//前結點指針域 ?? ?ElemType data;?? ??? ??? ??? ?//數據域 ?? ?struct DNode *next;?? ??? ??? ?//后結點指針域 }DNode, *DLinkList;?? ??? ??? ??? ?//結點和指向結點的指針 bool InitDLinkList(DLinkList &L);?? ??? ??? ??? ??? ??? ?//雙鏈表初始化 Status CreatDLinkList(DLinkList &L);?? ??? ??? ??? ??? ?//尾插法創(chuàng)建鏈表,包含初始化功能 bool InsertNextDNode(DNode *p, DNode *s);?? ??? ??? ??? ?//結點s插入在結點p之后 Status DeleteNextDNode(DNode *p, ElemType &e);?? ??? ??? ?//刪除結點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é)點,返回的是結點 void DestoryList(DLinkList &L);?? ??? ??? ??? ??? ??? ??? ?//銷毀雙鏈表,需要釋放頭結點
oper_func.cpp
#include <iostream> #include"list.h" bool InitDLinkList(DLinkList &L) { ?? ?//構建空的雙鏈表,作為雙鏈表的頭結點,數據域為空 ?? ?L = new DNode; ?? ?if (L == NULL)?? ??? ??? ??? ?//內存分配失敗 ?? ??? ?return FALSE; ?? ?L->prior = NULL;?? ??? ??? ?//頭結點的前驅指針始終指向NULL?? ? ?? ?L->next = NULL;?? ??? ??? ??? ?//暫時指向NULL ?? ?return TRUE; } Status CreatDLinkList(DLinkList &L) { ?? ?//利用InsertNextDNode函數來創(chuàng)建 ?? ?using std::cin; ?? ?using std::cout; ?? ?using std::endl; ?? ?if (InitDLinkList(L)) ?? ?{ ?? ??? ?DNode *s,*r = L;?? ??? ??? ??? ?//s為新建的新結點,用來存儲數據,而r為尾指針,始終指向尾部節(jié)點 ?? ??? ?int num; ?? ??? ?cout << "輸入你需要創(chuàng)建的雙鏈表的個數:"; ?? ??? ?cin >> num; ?? ??? ?for (int i = 1; i <= num; i++) ?? ??? ?{ ?? ??? ??? ?s = new DNode;?? ??? ??? ??? ?//創(chuàng)建的新結點 ?? ??? ??? ?cout << "輸入第" << i << "個元素:"; ?? ??? ??? ?cin >> s->data;?? ??? ??? ??? ?//輸入數據 ?? ??? ??? ?s->next = NULL; ?? ??? ??? ?InsertNextDNode(r,s);?? ??? ?//結點s插在尾部節(jié)點之后 ?? ??? ??? ?r = s;?? ??? ??? ??? ??? ??? ?//尾指針指向新的尾結點 ?? ??? ?} ?? ??? ?return OK; ?? ?} ?? ?else ?? ?{ ?? ??? ?cout << "內存不夠,單鏈表創(chuàng)建失敗!" << endl; ?? ??? ?return ERROR; ?? ?} } //結點s插入在結點p之后 bool InsertNextDNode(DNode *p, DNode *s) { ?? ?if (p == NULL || s == NULL) ?? ??? ?return FALSE;?? ??? ??? ?//非法參數 ?? ?s->next = p->next; ?? ?if (p->next != NULL)?? ??? ?//如果p不是最后一個結點 ?? ?{ ?? ??? ?p->next->prior = s; ?? ?} ?? ?s->prior = p; ?? ?p->next = s; ?? ?return TRUE; } Status DeleteNextDNode(DNode *p, ElemType &e) { ?? ?if(p == NULL) ?? ??? ?return FALSE;?? ??? ??? ?//非法參數 ?? ?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個結點 ?? ?DNode *p = GetElem(L, i - 1); ?? ?//刪除i-1結點的后面結點 ?? ?return DeleteNextDNode(p,e); } DNode* GetElem(DLinkList L, int i) { ?? ?DNode *p = L; ?? ?int j = 0;?? ??? ??? ??? ?//表示p指向的當前結點的位置,此時為頭結點 ?? ?while (p != NULL && j < i) ?? ?{ ?? ??? ?p = p->next;?? ??? ?//指向下一個結點 ?? ??? ?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 << "雙鏈表全部數據銷毀成功!" << endl; ?? ?delete L; ?? ?cout << "頭結點銷毀,整個雙鏈表銷毀成功!" << endl; ?? ?L = NULL;?? ??? ??? ??? ?//頭指針指向NULL } Status ListInsert(DLinkList &L, int i, ElemType e) { ?? ?if (i < 1) ?? ??? ?return FALSE; ?? ?//尋找第i-1個結點 ?? ?DNode *p = GetElem(L, i - 1); ?? ?//直接在i-1結點的后面插入元素即可 ?? ?DNode *s = new DNode;?? ??? ?//新建節(jié)點 ?? ?s->data = e; ?? ?s->next = NULL; ?? ?s->prior = NULL; ?? ?return InsertNextDNode(p,s); }
main.cpp
/* 雙向鏈表:帶頭結點,且頭結點的prior指針時鐘指向為NULL 1、雙鏈表的初始化 2、雙鏈表的創(chuàng)建 3、雙鏈表的結點插入(相當于后插操作):(結點s插入結點p之后)需要考慮p結點是不是最后一個結點 ?? ?如果想前插操作,則找到該節(jié)點的i-1節(jié)點,然后實行后插操作也是一樣 4、雙鏈表的結點刪除(相當于后刪操作):(刪除p節(jié)點的后序節(jié)點q)需要考慮p結點是不是最后一個結點 ?? ?也要考慮q節(jié)點是不是最后一個結點 5、雙鏈表的刪除: 6、雙鏈表的遍歷: 7、雙鏈表的銷毀:需要回收頭結點 */ #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 << "內存分配失敗或者插入位置越界,插入失?。? << 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; }
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關文章
C++11新特性中auto 和 decltype 區(qū)別和聯系
這篇文章主要介紹了C++11新特性中auto 和 decltype 區(qū)別和聯系的相關資料,需要的朋友可以參考下2017-01-01解析一個有關sizeof用法的題目--sizeof(i++)
本篇文章是對一個關于sizeof用法的題目進行了詳細的分析介紹,需要的朋友參考下2013-06-06