c/c++开发分享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); //尾插法创建链表,包含初始化功能 bool insertnextdnode(dnode *p, dnode *s); //结点s插入在结点p之后 status deletenextdnode(dnode *p, elemtype &e); //删除结点p的后继节点 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); //查找链表指定位置节点,返回的是结点 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函数来创建 using std::cin; using std::cout; using std::endl; if (initdlinklist(l)) { dnode *s,*r = l; //s为新建的新结点,用来存储数据,而r为尾指针,始终指向尾部节点 int num; cout << "输入你需要创建的双链表的个数:"; cin >> num; for (int i = 1; i <= num; i++) { s = new dnode; //创建的新结点 cout << "输入第" << i << "个元素:"; cin >> s->data; //输入数据 s->next = null; insertnextdnode(r,s); //结点s插在尾部节点之后 r = s; //尾指针指向新的尾结点 } return ok; } else { cout << "内存不够,单链表创建失败!" << 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节点的后继节点 if (q == null) //节点p没有后继节点 { return error; } else { //有后继节点,但是p的后继节点为空 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; //新建节点 s->data = e; s->next = null; s->prior = null; return insertnextdnode(p,s); }
main.cpp
/* 双向链表:带头结点,且头结点的prior指针时钟指向为null 1、双链表的初始化 2、双链表的创建 3、双链表的结点插入(相当于后插操作):(结点s插入结点p之后)需要考虑p结点是不是最后一个结点 如果想前插操作,则找到该节点的i-1节点,然后实行后插操作也是一样 4、双链表的结点删除(相当于后删操作):(删除p节点的后序节点q)需要考虑p结点是不是最后一个结点 也要考虑q节点是不是最后一个结点 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)) //尾插法创建单链表 { cout << "双链表创建成功!" << endl; } else cout << "双链表创建失败!" << 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: { //删除指定位置节点 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/c++开发分享C++代码实现双向链表的全部内容,希望对大家的学习有所帮助,也希望大家多多支持<计算机技术网(www.ctvol.com)!!>。
需要了解更多c/c++开发分享C++代码实现双向链表,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/1240201.html