【数据结构】回顾表、栈、队列

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】回顾表、栈、队列，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

1.如何通过调整链而不是数据来交换两个相邻的元素？

  1. // 单向链表
  2.     Node *p,*afterp;
  3.     p=beforep->next;
  4.     afterp=p->next;
  5.  
  6.     p->next=afterp->next;
  7.     beforep->next=afterp;
  8.     afterp->next=p;
  9.  
  10.     // 双向链表
  11.     Node *beforep,*afterp;
  12.     beforep=p->prev;
  13.     afterp=p->next;
  14.  
  15.     p->next=afterp->next;
  16.     beforep->next=afterp;
  17.     afterp->next=p;
  18.     p->next->prev=p;
  19.     p->prev=afterp;
  20.     afterp->prev=beforep;

2.如何求出两个已排序的表L1和L2的交集和并集。

  1. // 交集
  2. template <typename Object>
  3. list<Object> intersection( const list<Object> & L1,const list<Object> & L2)
  4. {
  5.     list<Object> intersect;
  6.     typename list<Object>:: const_iterator iterL1 = L1.begin();
  7.     typename list<Object>:: const_iterator iterL2 = L2.begin();
  8.     while(iterL1 != L1.end() && iterL2 != L2.end())
  9.     {
  10.         if (*iterL1 == *iterL2)
  11.         {
  12.             intersect.push_back(*iterL1);
  13.             iterL1++;
  14.             iterL2++;
  15.         }
  16.         else if (*iterL1 < *iterL2)
  17.             iterL1++;
  18.         else
  19.             iterL2++;
  20.     }
  21.     return intersect;
  22. }
  1. // 并集
  2. // Assumes both input lists are sorted
  3. template <typename Object>
  4. list<Object> listUnion( const list<Object> & L1,const list<Object> & L2)
  5. {
  6.     list<Object> result;
  7.     typename list<Object>:: const_iterator iterL1 = L1.begin();
  8.     typename list<Object>:: const_iterator iterL2= L2.begin();
  9.     while(iterL1 != L1.end() && iterL2 != L2.end())
  10.     {
  11.         if (*iterL1 == *iterL2)
  12.         {
  13.             result.push_back(*iterL1);
  14.             iterL1++;
  15.             iterL2++;
  16.         }
  17.         else if (*iterL1 < *iterL2)
  18.         {
  19.             result.push_back(*iterL1);
  20.             iterL1++;
  21.         }
  22.         else
  23.         {
  24.             result.push_back(*iterL2);
  25.             iterL2++;
  26.         }
  27.     }
  28.     return result;
  29. }

3.一个有表头结点，没有尾结点，还有一个指向表头结点的指针的单向链表，写一个类包括以下函数：
返回链表的大小，
打印链表，
检测值x是否在链表中，
如果x不在链表中则加入链表，
如果x在链表中则删除它。

  1. template <typename Object>
  2. struct Node
  3. {
  4.     Object data;
  5.     Node *next;
  6.     Node (const Object & d = Object(),Node *n=NULL)
  7.         :data(d),next(n){}
  8. };
  9.  
  10. template <typename Object>
  11. class singleList {
  12. public:
  13.     singleList(){init();}
  14.     ~singleList()
  15.     {
  16.         eraseList(head);
  17.     }
  18.  
  19.     singleList(const singleList & rhs)
  20.     {
  21.         eraseList(head);
  22.         init();
  23.         *this=rhs;
  24.     }
  25.  
  26.     bool add(Object x)
  27.     {
  28.         if(contains(x))
  29.         {
  30.             return false;
  31.         }
  32.         else
  33.         {
  34.             Node<Object> *ptr =new Node<Object>(x);
  35.             ptr->next=head->next;
  36.             head->next=ptr;
  37.             theSize++;
  38.         }
  39.         return true;
  40.     }
  41.  
  42.     bool remove(Object x)
  43.     {
  44.         if(!contains(x))
  45.             return false;
  46.         else 
  47.         {
  48.             Node<Object>*ptr=head->next;
  49.             Node<Object>*trailer;
  50.             while(ptr->data!=x)
  51.             {
  52.                 trailer=ptr;
  53.                 ptr=ptr->next;
  54.             }
  55.             trailer->next=ptr->next;
  56.             delete ptr;
  57.             theSize--;
  58.         }
  59.         return true;
  60.     }
  61.  
  62.     int size()
  63.     {
  64.         return theSize;
  65.     }
  66.  
  67.     void print()
  68.     {
  69.         Node<Object> *ptr=head->next;
  70.         while(ptr!=NULL)
  71.         {
  72.             count<<ptr->data<<" ";
  73.             ptr=ptr->next;
  74.         }
  75.         count<<endl;
  76.     }
  77.  
  78.     bool contains(const Object & x)
  79.     {
  80.         Node<Object> * ptr=head->next;
  81.         while(ptr!=NULL)
  82.         {
  83.             if(x==ptr->data)
  84.                 return true;
  85.             else 
  86.                 ptr=ptr->next;
  87.         }
  88.         return false;
  89.     }
  90.  
  91.     void init()
  92.     {
  93.         theSize=0;
  94.         head=new Node<Object>;
  95.         head->next=NULL;
  96.     }
  97.  
  98.     void eraseList(Node<Object> * h)
  99.     {
  100.         Node<Object> *ptr=h;
  101.         Node<Object> *nextPtr;
  102.         while(ptr!=NULL)
  103.         {
  104.             nextPtr=ptr->next;
  105.             delete ptr;
  106.             ptr=nextPtr;
  107.         }
  108.     }
  109.  
  110. private:
  111.     Node<Object> *head;
  112.     int theSize;
  113. };

4.如何给List迭代器类添加对operator–的支持。

  1. const_iterator & operator-- ()
  2. {
  3.     current=current->prev;
  4.     return *this;
  5. }
  6.  
  7. const_iterator operator-- (int)
  8. {
  9.     const_iterator old=*this;
  10.     --(*this);
  11.     return old;
  12. }

5.前面谈到过的双端队列（deque），给它添加以下功能：

函数 备注
push(x) 将项x插入到双端队列的前段
pop() 从双端队列删除前段项并返回
inject(x) 将项x插入到双端队列的尾端
eject() 从双端队列中删除尾端项并将其返回 
  1. template <typename Object>
  2. class deque
  3. {
  4. public:
  5.     deque(){ l();}
  6.     void push (Object obj) {l.push_front(obj);}
  7.     Object pop () {Object obj=l.front();pop_front();return obj;}
  8.     void inject (Object obj) {l.push_back(obj);}
  9.     Object eject() {pop_back(obj);}
  10. private:
  11.     list<Object> l;
  12. }

6.不包含表头结点和尾结点，用单向链表高效地实现栈类。

  1. template<typename @H_426_403@Object>
  2. struct node
  3. {
  4.     node() {next=@H_426_403@NULL;}
  5.     node(@H_426_403@Object obj):data(obj){}
  6.     node(@H_426_403@Object obj,node * ptr):data(obj),next(ptr){}
  7.     @H_426_403@Object data;
  8.     node *next;
  9. };
  10.  
  11. template<typename @H_426_403@Object>
  12. class stack { public: stack(){head=@H_426_403@NULL;} ~stack(){while(head) pop();} void push(@H_426_403@Object obj) { node<object> *ptr=new node<@H_426_403@Object>(obj,head); head=ptr; } @H_426_403@Object top() { return (head->data); } void pop() { node<@H_426_403@Object> *ptr=head->next; delete head; head=ptr; } private: node<@H_426_403@Object> *head; }

7.不包含表头结点和尾结点，用单向链表高效地实现队列类。

  1. template<typename Object>
  2. class queue
  3. {
  4. public:
  5.     queue(){front=NULL;rear=NULL;}
  6.     ~queue(){while(front)deque();}
  7.     void deque(Object obj)
  8.     {
  9.         node<Object> *ptr=new node<Object>(obj,NULL);
  10.         if(rear)
  11.             rear=rear->next=ptr;
  12.         else
  13.             front=rear=ptr;
  14.     }
  15.     Object deque()
  16.     {
  17.         Object temp=front->data;
  18.         node<Object> *ptr=front;
  19.         if(front->next==NULL)
  20.             front=rear=NULL;
  21.         else
  22.             front=front->next;
  23.         delete ptr;
  24.         return temp;
  25.     }
  26. private:
  27.     node<Object> *front;
  28.     node<Object> *rear;
  29. }

8.使用由vector作为基本的数据结构的循环数组高效地实现队列类。

  1. template<typename Object>
  2. class queue
  3. {
  4. public:
  5.     queue(int s):maxSize(s),front(0),rear(0){elements.resize(maxSize);}
  6.     queue(){maxSize=100;front=0;rear=0;elements.resize(maxSize);}
  7.     ~queue(){while(front!=rear) deque();}
  8.     void enque(Object obj)
  9.     {
  10.         if(!full())
  11.         {
  12.             elements[rear]=obj;
  13.             rear=(rear+1)%maxSize;
  14.         }
  15.     }
  16.     Object deque()
  17.     {
  18.         Object temp;
  19.         if(!empty())
  20.         {
  21.             temp=elements[front];
  22.             front=(front+1)%maxSize;
  23.             return temp;
  24.         }
  25.     }
  26.     bool empty(){return front==rear;}
  27.     bool full(){return (rear+1)%maxSize==front;}
  28. private:
  29.     int front,rear;
  30.     int maxSize;
  31.     vector<Object> elements;
  32. }

感谢您的访问，希望对您有所帮助。

欢迎大家关注或收藏、评论或点赞。

为使本文得到斧正和提问，转载请注明出处：
http://blog.csdn.net/nomasp

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test