C++ 构造双向链表的实现代码

构造双向链表,不足之处,还望指正! 


代码如下:

// DoubleLinkedList.cpp : 定义控制台应用程序的入口点。
//构造双向链表,实现从控制台输入,插入,删除,求大小size等操作
#include "stdafx.h"
#include <iostream>
using namespace std;
//定义双向链表的节点
template<class T>
struct NODE
{
 NODE<T>* pre;
 T data;
 NODE<T>* next;
};
//定义双向链表容器
template<class T>
class DoubleLinkedList
{
public:
 DoubleLinkedList()
 {
  NODE<T>* q = new NODE<T>;
  if (q == NULL)
  {
   cout << "Fail to malloc the head node." << endl;
   return;
  }
  phead = q;
  phead->pre = NULL;
  phead->data = NULL;
  phead->next = NULL;

T i;
  cout << "Please input several integer number, input ctrl+z to the end: " << endl;
  while (cin >> i)
  {
   NODE<T>* p = new NODE<T>;
   if (p == NULL)
   {
    cout << "Fail to malloc a new node." << endl;
    return;
   }
   p->data = i;
   q->next = p;
   p->pre = q;
   p->next = NULL;
   q = q->next;
  }
 }

//容器大小方法
 int size()
 {
  NODE<T>* p = phead->next;
  int count(0);
  while (p != NULL)
  {
   count++;
   p = p->next;
  }
  return count;
 }

//输出DoubleLinkedLIst中的元素
 void print_elements()
 {
  NODE<T>* p = phead->next;
  while (p != NULL)
  {
   cout << p->data << " ";
   p = p->next;
  }
  cout << endl;
 }
 //插入一个元素到DoubleLinkedList中,任意合法位置插入
 void insert_element(int i, T e)
 {
   if (i <= this->size())
  {
   NODE<T>* m = phead;
   for (int j = 1; j < i; j ++)
   {
    m = m->next;
   }
   NODE<T>* n = m->next;
   NODE<T>* p = new NODE<T>;
   if (p == NULL)
   {
    cout << "Failed to malloc the node." << endl;
   }
   m->next = p;
   p->pre = m;
   p->data = e;
   p->next = n;
   n->pre = p;
  }
  else if (i == (this->size()+1))
  {
   NODE<T>* m = phead;
   for (int j = 1; j < i; j++)
   {
    m = m->next;
   }
   NODE<T>* p = new NODE<T>;
   if (p == NULL)
   {
    cout << "Failed to malloc the node." << endl;
   }
   m->next = p;
   p->pre = m;
   p->data = e;
   p->next = NULL;
  }
  else
  {
   cout << "Please input the position number equals or smaller than " << size()+1 << endl;
  }
 }

//插入一个元素到DoubleLinkedList中,只在末尾插入
 void insert_element(T e)
 {
  NODE<T>* m = phead;
  for (int j = 1; j <= size(); j++)
  {
   m = m->next;
  }
  NODE<T>* p = new NODE<T>;
  if (p == NULL)
  {
   cout << "Failed to malloc the node." << endl;
  }
  m->next = p;
  p->pre = m;
  p->data = e;
  p->next = NULL;
 }

//删除DoubleLinkedList中的一个元素
 void delete_element(int i)
 {
  NODE<T>* p = phead;
  for (int j = 0; j < i; j ++)
  {
   p = p->next;
   if (p == NULL)
   {//所要删除的元素超过list的范围
    cout << "The size of the list is " << size() << " ,Please input the right number." << endl;
    return;
   }
  }
  if(p->next != NULL)
  {//删除除最后一个以外的元素
   NODE<T>* m = p->pre;
   NODE<T>* n = p->next;
   m->next = n;
   n->pre = m;
   delete p;
  }
  else
  {//删除元素为最后一个
   NODE<T>* m = p->pre;
   m->next = NULL;
   delete p;
  }
 }
private:
 NODE<T>* phead;
};
int _tmain(int argc, _TCHAR* argv[])
{
 //测试代码
  DoubleLinkedList<int> mylist;
 mylist.print_elements();
 cout << "The size of the double linked list is : " << mylist.size() << endl;
 mylist.insert_element(1, 50);
 mylist.print_elements();
 mylist.insert_element(6, 80);
 mylist.print_elements();
 mylist.insert_element(250);
 mylist.print_elements();
 mylist.delete_element(7);
 mylist.print_elements();
 return 0;
}

(0)

相关推荐

  • C++数据结构与算法之判断一个链表是否为回文结构的方法

    本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构

  • C++数据结构与算法之反转链表的方法详解

    本文实例讲述了C++数据结构与算法之反转链表的方法.分享给大家供大家参考,具体如下: 算法概述:要求实现将一条单向链表反转并考虑时间复杂度. 算法分析: 数组法(略): 将列表元素逐个保存进数组,之后再逆向重建列表 点评:实现逻辑最简单,需要额外的内存开销. 移动指针: 通过三个指针逐个从链表头开始逐一反转链表元素的指针 点评:不需要额外的内存开销,会改变原始链表. 递归: 以递归的方式首先找到链表尾部,再逐一反转指针 点评:不需要额外的内存开销,不会改变原始链表. 算法实现: 构建链表结构 /

  • C++中单链表的建立与基本操作

    准备数据 准备在链表操作中需要用到的变量及数据结构 示例代码如下: 复制代码 代码如下: struct Data   //数据结点类型 { string key;  //关键字  string name; int age;};struct CLType  //定义链表结构 { Data nodeData; Data *nextNode;}; 定义了链表数据元素的类型Data以及链表的数据结构CLType.结点的具体数据保存在一个结构Data中,而指针nextNode用来指向下一个结点. 我们可以

  • C++将二叉树转为双向链表及判断两个链表是否相交

    把二叉查找树转变成排序的双向链表 例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空

  • 用C++类实现单向链表的增删查和反转操作方法

    数据结构这东西,理解起来不算难,但是实现难度就不小了,虽然思路很清晰,但不知道从何下手还有语言的细节问题一直是阻碍初学者的主要障碍(比如我).今天用了一下午时间终于独立完成了链表操作. 找网上的代码,大多用了结构体,还有些并不适合刚学c++或者数据结构的人看,于是我是用类写的,代码比较符合学生的习惯和水平. 先看类定义 class node { public: int data; node *next; }; class linklist { node *h; --//一些函数 } 两个类,no

  • 关于双向链表的增删改查和排序的C++实现

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 由于双向链表可以方便地实现正序和逆序两个方向的插入.查找等功能,在很多算法中经常被使用, 这里用C++构造了一个双向链表,提供了对双向链表的插入.查找.删除节点.排序等功能,其中排序提供了插入排序和冒泡排序两种方式 #include<iostream> using namespace std;

  • 如何用C++实现双向循环链表

    双向循环链表,即每个节点都拥有一前一后两个指针且头尾互链的链表.各种链表的简单区别如下:单向链表:基本链表:单向循环链表:不同于单向链表以 NULL 判断链表的尾部,单向循环链表的尾部链接到表头,因此当迭代操作到表头前即是尾部:双向链表:比单向链表多出指向前一个节点的指针,但实际上使用双向链表时很少使用不循环的:双向循环链表:相对于单向循环链表,双向循环链表可从头部反向迭代,这在链表长度很大且需要获取.插入或删除靠近链表尾部元素的时候十分高效.单向循环列表只能从表头正向迭代,执行的时间大于从反向

  • C++ 双链表的基本操作(详解)

    1.概念 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 结构图如下所示: 2.基本操作实例 DoubleList.cpp #include "stdafx.h" #include "DoubleList.h" #include <stdio.h> #include <malloc.h>

  • C++数据结构与算法之双缓存队列实现方法详解

    本文实例讲述了C++数据结构与算法之双缓存队列实现方法.分享给大家供大家参考,具体如下: "双缓存队列"是我在一次开发任务中针对特殊场景设计出来的结构.使用场景为:发送端持续向接收端发送数据包--并且不理会接收端是否完成业务逻辑.由于接收端在任何情况下停止响应即可能产生数据丢失,因此无法简单的设计一条线程安全队列来对数据写入或读取(读取数据时将队列上锁视为对写入的停止响应). 鉴于此,我的设计思路如下: 接收端首先向A队列中写入数据,然后当数据处理请求到来的时候切换到B队列继续写入,之

  • 用C++实现单向循环链表的解决方法

    用C++实现一个单向循环链表,从控制台输入整型数字,存储在单项循环链表中,实现了求链表大小.不足之处,还望指正! 复制代码 代码如下: // TestSound.cpp : 定义控制台应用程序的入口点.//实现单向循环链表#include "stdafx.h"#include <iostream>#include <string>using namespace std;//定义链表一个节点的结构体template <class T>struct NO

  • c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. (1)定义双向链表的基本结构 复制代码 代码如下: typedef struct _DOUBLE_LINK_NODE  {      int data;      struct _DOUBLE_LINK_NODE* prev;      struct _DOUBLE_LINK_NODE* nex

  • 浅析C++中单链表的增、删、改、减

    首先是是一个简单的例子,单链表的建立和输出.程序1.1 复制代码 代码如下: #include<iostream>#include<string>using namespace std;struct Student{ string name; string score; Student *next;//定义了指向Candidate类型变量的指针};int main(){ int n;// cout<<"请输入学生的总数:"; cin>>n

随机推荐