鱼C论坛

 找回密码
 立即注册
查看: 308|回复: 1

[学习笔记] 学习笔记-----循环双链表

[复制链接]
最佳答案
11 
发表于 2018-4-14 21:02:51 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
最近在自学数据结构
下面的程序是《数据结构C++语言描述》任燕编著 清华大学出版中的范例程序
小弟只不过是改遍了一下,让程序可以正常运行,此外小弟还重载了输出运算符,想更加方便的输出链表中的每个结点的数据域,要是有什么错误的还请大神指针,
这个帖子就是一个学习笔记,没有什么技术含量,小弟也想写一些好的技术贴,但是爬爬妹子图啥的都被写烂了,最近在自学小甲鱼的Windows程序设计,希望以后可以有更多的想法和写出应用数据结构后更好的程序,到时候小弟希望也可以写出像其他大神一样的技术贴,可以更好的和鱼油们研讨技术。
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <stdbool.h>
  4. #include <cstdbool>
  5. #include <assert.h>
  6. using namespace std;

  7. template <typename elemtype>
  8. class DoubleLinkList{
  9. public:
  10.         class LinkNode{
  11.         public:
  12.                 elemtype data;
  13.                 LinkNode *next;//后继指针
  14.                 LinkNode *prior;//前驱指针
  15.         };
  16.         typedef LinkNode* NodePointer;

  17.         //置空
  18.         void clear();

  19.         //删除链表中数据域为e的第一个结点
  20.         void deleteElem(elemtype e);

  21.         //取循环双链表的第i个结点的数据域
  22.         elemtype getElem(int i);


  23.         //求链表的结点的个数
  24.         int getLength();

  25.         //在第i个结点前插入数据域为e的结点
  26.         void insert(int i, elemtype e);

  27.         //判断链表是否为空
  28.         bool isEmpty();

  29.         //返回数据域为e的第一个结点的指针
  30.         void locateElem(elemtype find_e, NodePointer& r);//NodePointer& r为引用变量

  31.         //返回结点后继的数据域
  32.         elemtype nextElem(elemtype e);

  33.         //从在赋值运算符
  34.         DoubleLinkList operator=(DoubleLinkList other);

  35.         //返回某结点的前驱的数据域
  36.         elemtype priorElem(elemtype e);

  37.         //构造函数
  38.         DoubleLinkList();

  39.         //拷贝构造函数
  40.         DoubleLinkList(DoubleLinkList<elemtype> &other);

  41.         //析构函数
  42.         virtual ~DoubleLinkList();

  43.         template <typename out_put>
  44.         friend ostream& operator <<(ostream& out, DoubleLinkList<out_put> &other);

  45. protected:
  46.         NodePointer head;
  47. };


  48. template <typename elemtype>
  49. void DoubleLinkList<elemtype>::clear(){
  50.         NodePointer r, p;//预分别指向待删除节点的前驱和待删除结点的指针
  51.         if (!head){
  52.                 return;//若列表为空,则不执行任何操作
  53.         }

  54.         //回收每个结点空间
  55.         //从最后一个节点开始,向前滑动
  56.         p = head->prior;//指向最后一个结点
  57.         while (p != head){
  58.                 r = p->prior;//指向待删除结点的前驱
  59.                 delete p;
  60.                 p = r;
  61.         }

  62.         delete p;
  63.         head = NULL;
  64. }


  65. template <typename elemtype>
  66. void DoubleLinkList<elemtype>::deleteElem(elemtype e){
  67.         NodePointer p;
  68.         locateElem(e, p);//使p指向第一个数据域为e的结点

  69.         if (head->next == head){
  70.                 head = NULL;
  71.         }
  72.         else{
  73.                 if (p == head){
  74.                         head = p->next;
  75.                 }
  76.                 p->prior->next = p->next;
  77.                 p->next->prior = p->prior;
  78.         }
  79.         delete p;
  80.         cout << "删除成功" << endl;
  81. }

  82. template <typename elemtype>
  83. elemtype DoubleLinkList<elemtype>::getElem(int i){
  84.         int j = 1;
  85.         NodePointer p = head;
  86.         while (p && p->next != head && j < i){//向后滑动
  87.                 p = p->next;
  88.                 j++;
  89.         }

  90.         if (j == i){
  91.                 return p->data;
  92.         }
  93. }


  94. template <typename elemtype>
  95. int DoubleLinkList<elemtype>::getLength(){
  96.         int length = 0;
  97.         NodePointer p = head;

  98.         while (p){
  99.                 lenght++;
  100.                 p = p->next;
  101.                 if (p == head){
  102.                         break;//循环双链表的终止方法
  103.                 }
  104.         }
  105.         return length;
  106. }


  107. template <typename elemtype>
  108. void DoubleLinkList<elemtype>::insert(int i, elemtype e){
  109.         int j = 1;
  110.         NodePointer p = head;//指向当前结点的指针,初始化指向head
  111.         NodePointer s;//指向带插入结点的指针

  112.         while (p&&(j < i)){
  113.                 p = p->next;
  114.                 j++;
  115.         }

  116.         s = new LinkNode;//动态申请空间
  117.         assert(s != 0);
  118.         s->data = e;

  119.         if (i == 1){//如果插入的是第一个结点
  120.                 if (!head){
  121.                         head = s->prior = s->next = s;
  122.                         cout << "首项插入成功" << endl;
  123.                         return;
  124.                 }
  125.                 head = s;
  126.                 cout << "首项替换成功" << endl;
  127.         }

  128.         //插入的基本功
  129.         p->prior->next = s;
  130.         s->prior = p->prior;
  131.         p->prior = s;
  132.         s->next = p;
  133.         cout << "插入成功" << endl;
  134. }

  135. template <typename elemtype>
  136. bool DoubleLinkList<elemtype>::isEmpty(){
  137.         return head ? false : true;
  138. }


  139. template <typename elemtype>
  140. void DoubleLinkList<elemtype>::locateElem(elemtype e, NodePointer &r){
  141.         NodePointer p = head;

  142.         while (p&&p->next &&p->data != e){
  143.                 p = p->next;
  144.         }
  145.         if (p->data == e){
  146.                 r = p;
  147.                 cout << "成功定位" << endl;
  148.                 return;
  149.         }
  150.         else{
  151.                 cout << "获取失败,该链表中可能没有这个指针" << endl;
  152.                 return;
  153.         }
  154. }

  155. template <typename elemtype>
  156. elemtype DoubleLinkList<elemtype>::nextElem(elemtype e){
  157.         NodePointer p = head;
  158.         if (locateElem(e, p)){
  159.                 return p->next->data;//返回后继的数据域
  160.         }
  161.         else{
  162.                 cout << "失败" << endl;
  163.                 return 0;
  164.         }
  165. }

  166. //重载赋值运算符
  167. template <typename elemtype>
  168. DoubleLinkList<elemtype> DoubleLinkList<elemtype>::operator =(DoubleLinkList<elemtype> other){
  169.         NodePointer p = NULL;
  170.         NodePointer rp = other.head;

  171.         NodePointer s;//预指向新节点

  172.         if (this != &other){
  173.                 clear();

  174.                 cout << "11111" << endl;
  175.                 while (1){
  176.                         s = new LinkNode;
  177.                         assert(s != 0);
  178.                         s->data = rp->data;

  179.                         if (!head){
  180.                                 head = p = s;
  181.                         }
  182.                         //进行链接
  183.                         p->next = s;
  184.                         s->prior = p;
  185.                         p = s;
  186.                         cout << "22222" << endl;
  187.                         //向下滑动
  188.                         rp = rp->next;
  189.                         if (rp == other.head){
  190.                                 break;
  191.                         }
  192.                 }
  193.                 if (head){
  194.                         head->prior = p;//形成循环链表
  195.                         p->next = head;
  196.                 }
  197.         }
  198.         return *this;
  199. }


  200. template <typename elemtype>
  201. elemtype DoubleLinkList<elemtype>::priorElem(elemtype e){
  202.         NodePointer p;
  203.         if (locateElem(e, p)){
  204.                 return p->prior->data;
  205.         }
  206. }


  207. template <typename elemtype>
  208. DoubleLinkList<elemtype>::DoubleLinkList(){
  209.         head = NULL;//默认的构造函数就是把头指针置空
  210. }

  211.        
  212. template <typename elemtype>
  213. DoubleLinkList<elemtype>::~DoubleLinkList(){
  214.         clear();
  215. }

  216. template<typename elemtype>
  217. DoubleLinkList<elemtype>::DoubleLinkList(DoubleLinkList<elemtype> &other){
  218.         NodePointer p;
  219.         NodePointer op = other.head;

  220.         NodePointer s;

  221.         head = p = NULL;

  222.         while (op){
  223.                 s = new LinkNode;//动态申请空间
  224.                 assert(s != 0);
  225.                 s->data = op->data;

  226.                 if (!head){
  227.                         head = p = s;
  228.                 }
  229.                 //常规操作(`_`!)
  230.                 p->next = s;
  231.                 s->prior = p;
  232.                 p = s;


  233.                 op = op->next;
  234.                 if (op == other.head){
  235.                         break;
  236.                 }
  237.         }

  238.         if (head)
  239.         {//形成循环链表
  240.                 head->prior = p;
  241.                 p->next = head;
  242.         }
  243. }

  244. //重载输出运算符
  245. template <typename out_put>
  246. ostream& operator <<(ostream& out, DoubleLinkList<out_put> &other){
  247.         DoubleLinkList<out_put>::NodePointer s = other.head;
  248.         while (1){
  249.                 out << s->data << "\t";
  250.                 s = s->next;
  251.                 if (s==other.head){
  252.                         return out;
  253.                 }
  254.         }
  255. }

  256. int main(void){
  257.         DoubleLinkList<int> d1;
  258.         d1.insert(1, 1);
  259.         d1.insert(2, 2);
  260.         d1.insert(3, 3);
  261.         cout << "d1为:";
  262.         cout << d1 << endl;

  263.         DoubleLinkList<int> d2;
  264.         for (int i = 1; i < 11; i++){
  265.                 d2.insert(i, i);
  266.         }
  267.         cout << "d2为:";
  268.         cout << d2 << endl;

  269.         d1 = d2;//检验赋值运算符的重载
  270.         cout << "d1:::::::" << endl;
  271.         cout << d1 << endl;

  272.         DoubleLinkList<int> d3(d2);//检验拷贝构造函数
  273.         cout << "d3::::::::" << endl;
  274.         cout << d3 << endl;
  275.         return 0;
  276. }

复制代码
最佳答案
11 
 楼主| 发表于 2018-4-14 21:06:26 | 显示全部楼层


by the way ,运行程序的时候会看到有一些什么111111 和222222之类的,那个是我在测试赋值运算符的时候写的,可以忽略
*滑块验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号 )

GMT+8, 2018-7-21 21:45

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表