精华内容
下载资源
问答
  • C++双向循环链表

    2018-03-14 21:52:42
    一.概念双向链表和单向链表相比,每一个结点都多了一个指针域,即共有两个...当双向循环链表为空时,其头结点的两个指针域均指向自己,不为空时,形成循环链表的具体做法是:最后一个结点的后继指针指向头结点后的第...

    一.概念

    双向链表和单向链表相比,每一个结点都多了一个指针域,即共有两个指针域,一个指向后继结点,另一个指向前驱结点,如图


    因此双向链表可以向两个方向移动,不像单向链表那样只能从头到尾进行查找,双向链表相当于牺牲空间换取时间的做法。当双向链表的头尾相连时,形成了双向循环链表。当双向循环链表为空时,其头结点的两个指针域均指向自己,不为空时,形成循环链表的具体做法是:最后一个结点的后继指针指向头结点后的第一个结点,即第一个存放元素的结点;第一个存放元素的结点的前驱指针指向最后一个结点,形成闭环,即所有存放有效数据的结点形成闭环。

    二.实践

    声明:DouLinkList.h

    //
    // Created by 开机烫手 on 2018/3/13.
    //
    
    #ifndef LINEARLIST_DOULINKLIST_H
    #define LINEARLIST_DOULINKLIST_H
    
    namespace xq {
    
        typedef struct douNode {
            int data;
            struct douNode *prior;
            struct douNode *next;
        } NODE;
    
        class DouLinkList {
        private:
            NODE *head;
            int len;
        public:
            DouLinkList(int n = 0);
    
            ~DouLinkList();
    
            void print();
    
            void printReverse();
    
            int getLength();
    
            int getElem(int);
    
            bool insert(int, int);
    
            bool delete_(int, int *);
    
            bool isEmpty();
    
            bool clearList();
        };
    
    }
    
    #endif //LINEARLIST_DOULINKLIST_H

    定义:DouLinkList.cpp

    //
    // Created by 开机烫手 on 2018/3/13.
    //
    
    #include "DouLinkList.h"
    #include <iostream>
    using namespace std;
    using namespace xq;
    
    DouLinkList::DouLinkList(int n) {
    
        if (n == 0) {
            head = new NODE;
            head->next = head;
            head->prior = head;
            len = 0;
            return;
        }
    
        len = 0;
        head = new NODE;
        NODE *p = head, *q;
        for (int i = 0; i < n; i++) {
            q = new NODE;
            p->next = q;
            q->data = i + 1;
            q->prior = p;
            p = q;
            len++;
        }
        p->next = head->next;
        head->next->prior = p;
    }
    
    DouLinkList::~DouLinkList() {
    
    }
    
    void DouLinkList::print() {
        if (head->next == head) {
            cout << "list is empty !!!" << endl;
            return;
        }
    
        NODE *p = head->next;
        while (p->next != head->next) {
            cout << p->data << ' ';
            p = p->next;
        }
        cout << p->data;
        cout << endl;
    }
    
    void DouLinkList::printReverse() {
    
        if (head->next == head) {
            cout << "list if empty !!!" << endl;
            return;
        }
    
        NODE *p = head->next->prior;
        while (p->prior != head->next->prior) {
            cout << p->data << ' ';
            p = p->prior;
        }
        cout << p->data;
        cout << endl;
    }
    
    int DouLinkList::getLength() {
        return len;
    }
    
    int DouLinkList::getElem(int i) {
        if (len == 0 || i <= 0 || i > len)
            return -999;
    
        if (i <= len / 2) {
            NODE *p = head->next;
            int j = 1;
            while (p->next && j < i) {
                p = p->next;
                j++;
            }
            return p->data;
        } else {
            NODE *p = head->next->prior;
            int j = i;
            while (p->prior && (len - j)) {
                p = p->prior;
                j++;
            }
            return p->data;
        }
    }
    
    bool DouLinkList::insert(int i, int e) {
        if (i - len > 1 || i <= 0)
            return false;
    
        if (len == 0) {
            NODE *q = new NODE;
            head->next = q;
            q->data = e;
            q->next = q;
            q->prior = q;
            len++;
            return true;
        } else {
            if (i <= len+1 / 2) {
                NODE *p = head->next;
                int j = 1;
                while (p->next && j < i) {
                    p = p->next;
                    j++;
                }
                NODE *q = new NODE;
                q->data = e;
                q->next = p->prior->next;
                q->prior = p->prior;
                p->prior->next = q;
                p->prior = q;
                if (i == 1)
                    head->next = q;
                len++;
    
                return true;
            } else {
                NODE *p = head->next->prior;
                int j = i;
                while (p->prior && (len - j + 1)) {
                    p = p->prior;
                    j++;
                }
                NODE *q = new NODE;
                q->data = e;
                q->next = p->next;
                q->prior = p;
                p->next->prior = q;
                p->next = q;
                len++;
    
                return true;
            }
        }
    }
    
    bool DouLinkList::delete_(int i, int *e) {
        if (i <= 0 || i > len)
            return false;
    
        if (i <= len / 2) {
            NODE *p = head->next;
            int j = 1;
            while (p->next && j < i) {
                p = p->next;
                j++;
            }
            *e = p->data;
            p->prior->next = p->next;
            p->next->prior = p->prior;
            if (i == 1)
                head->next = p->next;
            delete p;
            len--;
    
            return true;
        } else {
            NODE *p = head->next->prior;
            int j = i;
            while (p->prior && (len - j)) {
                p = p->prior;
                j++;
            }
            *e = p->data;
            p->prior->next = p->next;
            p->next->prior = p->prior;
            delete p;
            len--;
    
            return true;
        }
    }
    
    bool DouLinkList::isEmpty() {
        return len == 0;
    }
    
    bool DouLinkList::clearList() {
        NODE *p = head->next;
        NODE *q;
        while (p->next != head->next) {
            q = p->next;
            delete p;
            p = q;
        }
        delete p;
        head->next = head;
        head->prior = head;
        len = 0;
        return true;
    }
    

    测试代码:main.cpp

    #include <iostream>
    //#include "LinkList.h"
    #include "DouLinkList.h"
    
    using namespace std;
    using namespace xq;
    
    int main() {
    
        cout << "----------List test programe!---------- " << endl;
        DouLinkList list2(6);
        list2.printReverse();
        list2.print();
        cout << "list length is " << list2.getLength() << endl;
        cout << list2.getElem(1) << endl;
        list2.insert(7, 10);
        list2.insert(4, 11);
        list2.print();
        int num = 0;
        list2.delete_(1, &num);
        list2.print();
        cout << "num = " << num << endl;
        cout << "list is empty? " << list2.isEmpty() << endl;
        list2.clearList();
        cout << "list is empty? " << list2.isEmpty() << endl;
        list2.insert(1, 3);
        list2.insert(1, 4);
        list2.insert(1, 5);
        list2.print();
    
        return 0;
    }

    程序输出为:

    ----------List test programe!----------
    6 5 4 3 2 1
    1 2 3 4 5 6
    list length is 6
    1
    1 2 3 11 4 5 6 10
    2 3 11 4 5 6 10
    num = 1
    list is empty? 0
    list is empty? 1

    5 4 3

    切记!最重要的是链表生成结束形成闭环时的步骤:最后一个结点p的后继指向第一个存放数据的结点,即p->next = head->next;第一个存放数据的结点的前驱指向最后一个结点,即head->next->prior = p。

    展开全文
  • c++ 双向循环链表

    2016-12-07 10:48:00
    教学内容: ...循环链表里插入结点 遍历循环链表 双向链表结构定义 struct stu_data { char name[256];//学生名字 struct mytime stuTime;//签到时间 struct stu_data* front; ...
    
    教学内容:  
    循环双链表
    建立循环双链表
    循环链表里插入结点
    遍历循环链表
    
    双向链表结构定义
         struct  stu_data
         {
             char name[256];//学生名字
             struct mytime stuTime;//签到时间
             struct  stu_data* front;  //指向前一个结点
             struct  stu_data* back;  //指向后一个结点
    
         }  ;
    建立双向链表
    头指针Head
    尾部指针Tail
    插入结点
     
     //建立头结点
        Head=tail=p= malloc(sizeof( struct stu_data)); //
         memset(stu,0,sizeof( struct stu_data)); //初始化内存区域
    
    //尾部插入新结点 操作
           stu= malloc(sizeof( struct stu_data)); //分配结点内存空间
           memset(stu,0,sizeof( struct stu_data)); //初始化内存区域
       //结点数据填充。。。
             stu->front=p; //新结点指向前驱
             stu->back=NULL; //新结点尾指针置空
             p->back=stu; //前驱结点back指针指向新结点
             p=stu; //重要移动标志指针
             tail=stu;//可有可无的
      //循环链表
              Head->front=tail;
            tail->back=Head;
    A= Head      front                 back
    0    0    0    NULL    B
    B
    0    0    0    A    C
    C
    0    0    0    B    NULL
    //
    
    A= Head      front                 back
    0    0    0    D    B
    B
    0    0    0    A    C
    C
    0    0    0    B    D
    D
    0    0    0    C    A
    
    遍历链表
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    #include <stdarg.h> 
    #include <time.h>
    
     
     
     
     int main(int argn,char* argv[])// int a[1]//a[0]
     {       
        
    
         struct mytime
         {   
             //char name[256];
             int hour;//
             int min; //
             int sec; //
         };
    
         struct  stu_data
         {
             char name[256];//学生名字
             struct mytime stuTime;//签到时间
             struct  stu_data* front; //指向前一个结点
             struct  stu_data* back;  //指向后一个结点
    
         }  ;
         struct mytime t2;
         struct stu_data *stu,*p,*Head,*tail;
         
         time_t t;// long int
         struct tm * timfo;
         int i;
     
         //建立Head头结点
         Head=p=tail=malloc(sizeof( struct stu_data)); //256+12=268
         memset(p,0,sizeof( struct stu_data));
         strcpy(Head->name,"头结点");
        
         
         
         do
         {//插入新的结点
             stu= malloc(sizeof( struct stu_data)); //
             memset(stu,0,sizeof( struct stu_data)); //初始化内存区域
    
             //stu->back=NULL; //新结点尾指针置空
             //p->back=stu; //前驱结点back指针指向新结点
             //p=stu; //重要移动标志指针
    
             stu->front=p; //新结点指向前驱 2
             stu->back=NULL; //新结点尾指针置空
             p->back=stu; //前驱结点back指针指向新结点
             p=stu; //重要移动标志指针
             tail=stu;//可有可无的 2
    
             scanf("%s",&stu->name);
             time(&t);
             timfo= localtime(&t); //取当前系统时间
             stu->stuTime.hour=timfo->tm_hour;//
             stu->stuTime.min=timfo->tm_min;//
             stu->stuTime.sec=timfo->tm_sec;////构建循环链表
             Head->front=stu;
             tail->back=Head;
    
         } while(strcmpi(stu->name,"exit")!=0);
     
         //初始指针p 使他头结点Head
         stu=Head->back;
         do 
         {
              printf("%s,到校时间:%d时%d分%d秒\n",stu->name, stu->stuTime.hour, stu->stuTime.min, stu->stuTime.sec);
    
             stu=stu->back;
         } while (strcmpi(stu->name,"exit"));
    
    
         //初始指针p 使他尾部结点tail
         stu=tail->front;
         do 
         {
             printf("%s,到校时间:%d时%d分%d秒\n",stu->name, stu->stuTime.hour, stu->stuTime.min, stu->stuTime.sec);
    
             stu=stu->front;
         } while ( stu!=Head);
     
        getchar();
        getchar();
        
        return 0;
    }
    
     

     

    转载于:https://www.cnblogs.com/whzym111/p/6140268.html

    展开全文
  • C++双向循环链表实现

    2015-12-15 00:39:00
    双向循环链表C++实现 1.单链表: 结构图: 2.双向链表: 3.双向循环链表: 对于本程序中,则是给定一个_head 头结点,而不是指针,因为这样更加方便避免一些空判断问题 /* 版权信息:狼 文件...

    双向循环链表C++实现

     

    1.单链表:

    结构图:

    2.双向链表:

    3.双向循环链表:

    对于本程序中,则是给定一个_head  头结点,而不是指针,因为这样更加方便避免一些空判断问题

     

    /*
    版权信息:狼
    文件名称:BidCirList.h
    文件标识:
    文件摘要:
        利用C++实现简单的双向链表功能。增,删,查,改
        //太烦了。。我直接给个 带头结点的  表
        //swap 移花接木已经是个给力的方法。。just try
    当前版本:1.1
    作    者:狼
    完成时间:2015-12-13
    
    */
    #ifndef _BIDCIRLIST_H
    #define _BIDCIRLIST_H
    
    #include"afxstd.h"
    
    typedef int DataType;
    typedef struct ListNode
    {
        ListNode(DataType x=0)
        : _data(x)
        //默认初始化是自环而非  NULL
        , _prev(this)
        , _late(this)
        {}
    
        DataType _data;
        struct ListNode* _prev;
        struct ListNode* _late;
    }ListNode;
    
    class BidCirList
    {
    public:
        BidCirList()
            :_head(0)
        {}
    
        BidCirList(DataType *array, size_t n = 0)
            :_head(0)
        {
            size_t i = 0;
            while (n--)
            {
                InsertAter(array[i++]);
            }
        }
    
        BidCirList(BidCirList & list)
            :_head()
        {
            ListNode* cur = list._head._prev;
            while (cur)
            {
                InsertAter(cur->_data);
                cur = cur->_prev;
                if (cur == &list._head)
                    break;
            }
        }
    
        ~BidCirList()
        {
            Destoty();
        }
        
        BidCirList operator+(BidCirList& list)
        {
            BidCirList tmp(*this);
            ListNode* cur = list._head._prev;
    
            while (cur != &list._head)
            {
                tmp.InsertAter(cur->_data);
                cur = cur->_prev;
            }
            return tmp;
        }
    
        BidCirList& operator = (BidCirList& list)
        {
            if (this != &list)
            {
                BidCirList S(list);
    
                Swap(S);
            }
            return *this;
        }
    
        //清空空间
        void Destoty()
        {
            ListNode*cur = &_head;
            while (cur->_prev != &_head)
            {
                DelPrev();
            }
        }
    
        //删除结点之前的结点。默认为头
        void DelPrev(ListNode *del = NULL)
        {
            if (_head._prev == &_head)
                return;
            if (del == NULL)
            {
                //删除头之前
                _head._prev = _head._prev->_prev;
                delete _head._prev->_late;
    
                _head._prev->_late = &_head;
            }
            else
            {
                del->_prev = del->_prev->_prev;
                delete del->_prev->_late;
    
                del->_prev->_late = del;
            }
        }
    
        //删除结点之后一个,,默认为头
        void DelLate(ListNode *del = NULL)
        {
            if (_head._prev == &_head)
                return;
            if (del == NULL)
            {
                _head._late = _head._late->_late;
                delete _head._late->_prev;
    
                _head._late->_prev = &_head;
            }
            else
            {
                del->_late = del->_late->_late;
                delete del->_late->_prev;
    
                del->_late->_prev = del;
            }
        }
    
        //在结点之前插入,默认为头
        void InsertAter(DataType x ,ListNode* ins= NULL)
        {
            ListNode* tmp = new ListNode(x);
    
            if (ins == NULL)
            {
                tmp->_prev = &_head;
                tmp->_late = _head._late;
    
                tmp->_late->_prev = tmp;
                tmp->_prev->_late = tmp;
            }
            else
            {
                tmp->_prev = ins;
                tmp->_late = ins->_late;
    
                tmp->_late->_prev = tmp;
                tmp->_prev->_late = tmp;
            }
        }
    
        ListNode* Find(DataType x)
        {
            ListNode* cur = _head._prev;
            while (cur)
            {
                if (cur == &_head)
                    return NULL;
                if (cur->_data == x)
                {
                    return cur;
                }
                cur = cur->_prev;
            }
        }
    
        void Erase(ListNode * node)
        {
            if (node == &_head)
            {
                return;
            }
            else
            {
                ListNode* tmp = node;
                node->_prev->_late = node->_late;
                node->_late->_prev = node->_prev;
                delete tmp;
                tmp = NULL;
            }
        }
    
        //反向打印
        void PrintPrev()
        {
            ListNode* cur = _head._prev;
            while (cur)
            {
                if (cur == &_head)
                    break;
                cout << cur->_data << " -> ";
                cur = cur->_prev;
            }
            cout << " Over! " << endl;
        }
        //正向打印
        void PrintLate()
        {
            ListNode* cur = _head._late;
    
            while (cur)
            {
                if (cur == &_head)
                    break;
                cout << cur->_data << " -> ";
                cur = cur->_late;
            }
            cout << " Over! " << endl;
        }
    
        void Swap(BidCirList &list)
        {
            ::swap(_head._prev->_late, list._head._prev->_late);
            ::swap(_head._prev, list._head._prev);
    
            ::swap(_head._late->_prev, list._head._late->_prev);
            ::swap(_head._late, list._head._late);
    
        }
        
    private:
        ListNode _head;
    };
    
    #endif

     

    转载于:https://www.cnblogs.com/lang5230/p/5046960.html

    展开全文
  • 这是使用VC6.0实现的双向循环链表操作的程序,实现了查找元素,查找前驱后继等功能,并在MFC界面下实现了链表操作的具体过程。
  • C++双向循环链表实现约瑟夫环

    千次阅读 2018-12-20 23:23:01
    C++双向链表实现约瑟夫环 欢迎使用Markdown编辑器 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。 新的...

    C++双向链表实现约瑟夫环

    约瑟夫环问题描述:已知num个小孩(以编号1,2,3…num分别表示)围坐在一张圆桌周围。从编号为k的人开始从1顺次报数,数到T的那个人出列;他的下一个人又从1开始报数,后面顺次数到T的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列,试计算最后出列的那个小孩的编号。

    要求:基于双向循环链表(下图)和面向对象的程序设计方法完成本题。【提示:可以对小孩和圆桌游戏进行合理抽象,设计小孩类和圆桌类,然后基于小孩child类和圆桌circle类(包含child类的对象数组,循环链表搭建函数build(),圆圈游戏运行函数run()完成问题求解。】

    在这里插入图片描述
    代码如下:

    #include <iostream>
    using namespace  std;
    
    //1.定义小朋友节点类
    class Child
    {
    
    public:
    	int childNo;         //当前小孩的编号
    	Child* leftchild;    //记录小孩对象的左邻居
    	Child* rightchild;   //记录小孩对象的右邻居
    
    
    public:
    	//构造函数
    	Child(int num = 0)
    	{
    		childNo = num;
    		leftchild = NULL;
    		rightchild = NULL;
    	}
    
    };
    
    //2.定义圆圈游戏类
    class Circle
    {
    public:
    	int scale;  //当前正在参与游戏的人数
    	Child children[1000];
    
    public:
    	// 构造函数:初始化每个小孩对象节点的编号
    	Circle(int num = 1000)
    	{
    		scale = num;
    
    
    		for (int i = 0; i < num; i++)
    		{
    			children[i] = Child(i);
    		}
    	};
    
    	//构建节点的循环链表函数:确立每个小孩的左右邻居
    	void Build()
    	{
    		for (int i = 0; i < scale; i++)
    		{
    			if (i == 0)
    			{
    				children[i].rightchild = &children[1];
    				children[i].leftchild = &children[scale - 1];
    			}
    			else if (i == (scale - 1))
    			{
    				children[i].rightchild = &children[0];
    				children[i].leftchild = &children[scale - 2];
    			}
    			else
    			{
    				children[i].rightchild = &children[i + 1];
    				children[i].leftchild = &children[i - 1];
    			}
    		}
    
    	}
    	//游戏运行函数:从当前节点顺时针循环开始数num个数
    	void Run(int T)
    	{
    		int count = 1;
    		Child* current = &children[0];
    		while (scale > 1)
    		{
    			//quit the circle
    			if (count == T)
    			{
    				// 当前数到T的小孩退出游戏,参与游戏人数减少1个
    				scale = scale - 1;
    
    				//把当前的这个小孩的左右邻居用链表连接起来
    				current->leftchild->rightchild = current->rightchild;
    				current->rightchild->leftchild = current->leftchild;
    				current = current->rightchild;
    				count = 1;
    			}
    			else  //count the next	            		
    			{
    				count = count + 1;
    				current = current->rightchild;
    			}
    
    		}
    
    		cout << "The last child id is " << current->childNo << endl;
    	}
    };
    
    int main()
    {
    
    	Circle nodes(5); // 圆圈类内有100个节点对象(小孩)
    
    	nodes.Build();
    
    	nodes.Run(3);     // 开始循环运行数“7”的游戏,输出最后的获胜者
    
    	system("pause");
    	return 0;
    
    }
    
    
    
    
    展开全文
  • 一、概念  1.在双链表中的每个结点应有两个链接指针:  lLink -&gt;...双链表常采用带附加头结点的循环链表方式:  first:头指针,不存放数据,或者存放特殊要求的数据。它的lLink指向...
  • 先找到第pos个节点(不用pos-1),因为该链表双向的,可以指向前一个节点。 删除: void DeleteByPos(pNode pHead,int pos){ pNode p=pHead->pNext; int i=0; while(p!=pHead){ i++; if(i==pos) ...
  • ) //删除非极点的点,for循环的第一部分是起始值,第二部分是判断 { prrx = prx->next; //如果x,rx,rrx的逆时针夹角小于或等于180度,则删除rx. 向量叉乘积结果可以判断是顺时针还是逆时针。这里要把向量...
  • C++双向循环链表实现基数排序算法

    千次阅读 2015-04-21 21:26:40
    文件: baseSort.h baseSort.cpp 命令: g++ baseSort.cpp -o baseSort /*baseSort.h*/ /* * the head file of baseSort * */ #include #include #include #include using namespace std;... s
  • //在链表中定位序号为i的结点,d=0按前驱方向,反之按后继方向 { if(IsEmpty() || i ) { return NULL; } if(d != 0) { DblNode<T> * current = first->rLink; int k = 0; while(current !=...
  • 之前也写过一篇C语言实现简单的双向循环链表,现在使用C++再来扩展一下内容。除了节点的插入、删除,还增加了一些链表的其他操作,包括节点修改、节点替换、节点查找、值查找、值排序等等。内容还是挺丰富的,废话不...
  • // 双向循环链表的操作与实现...// 网上关于这方面的挺多,由于自己以前上课没好好学数据结构,现在重新认识数据结构,// 以下是自己写的基于C++双向循环链表的创建及其一些操作与实现(于VC下通过),没用模板,//...
  • C++实现双向循环链表

    2020-02-07 20:50:49
    本次博文是关于利用C++模板的方式实现的双向循环链表以及双向循环链表的基本操作,在之前的博文C++语言实现双向链表中,已经给大家分析了双向循环链表的结构,并以图示的方式给大家解释了双向循环链表的基本操作。...
  • 双向循环链表,即每个节点都拥有一前一后两个指针且头尾互链的链表。各种链表的简单区别如下:单向链表:基本链表;单向循环链表:不同于单向链表以 NULL 判断链表的尾部,单向循环链表的尾部链接到表头,因此当迭代...
  • 双向循环链表 C++实现

    2011-04-12 16:07:52
    双向循环链表 C++实现 双向循环链表 C++实现 双向循环链表 C++实现 双向循环链表 C++实现 双向循环链表 C++实现
  • 主要介绍了C++循环链表双向链表设计的API实现,文中的示例对于链表结点的操作起到了很好的说明作用,需要的朋友可以参考下
  • 该代码用C++语言。实现排序的双向循环链表。 请用Eclipse 导入查看代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 748
精华内容 299
关键字:

c++双向循环链表

c++ 订阅