c/c++语言开发共享C++代码实现双向链表

#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);                            //销毁双链表,需要释放头结点

#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);  }

/* 双向链表：带头结点，且头结点的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;  }