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

    2019-11-30 11:25:10
    C++双向链表 双向链表顾名思义就是每个结点具有两个指针,一个指向前一个结点,一个指向后一个结点,我们不必拘束与单链表的创建遍历操作等,这样大大减少了使用中存在的效率问题。 在单链表中,我们有一个数据...

    C++双向链表

    双向链表顾名思义就是每个结点具有两个指针,一个指向前一个结点,一个指向后一个结点,我们不必拘束与单链表的创建遍历操作等,这样大大减少了使用中存在的效率问题。

    在单链表中,我们有一个数据域还有一个指针域,数据域用来存储相关数据,而指针域负责链表之间的“联系”,双向链表具有两个指针域一个负责向后连接,一个负责向前连接

    //单链表结构
    template<class T>
    struct List{
        T data;
        struct List* next;
    };
    //双向链表结构
    template<class T>
    struct DNode{
    	public:
    		T value;
    		DNode *prev;
    		DNode *next;
    };

    同单链表一样,对双向链表的操作也有创建,插入,遍历,删除,销毁

    双向链表的创建

    struct DNode{
    	public:
    		T value;
    		DNode *prev;
    		DNode *next;
    	public:
    		DNode(){
    		}
    		DNode(T t,DNode *prev,DNode *next){
    			this->value=t;
    			this->prev=prev;
    			this->next=next;
    		}
    };

    在创建双向链表的时候,我们需要初始化的有两个指针。同单链表一样,我们需要一个头指针来标志链表的信息。因此我们可以写出该函数的定义:运用构造函数创建双向链表

    双向链表具体操作:

    template<class T>
    class DoubleCircleList{
    	public:
    		DoubleCircleList();  //构造函数 创建链表 
    		~DoubleCircleList();  //析构函数 销毁链表 	
    		int size();	//长度 
    		int is_empty();//判断是否为空 
    		T get(int index); //返回index值的位置 
    		T get_first();//返回第一个位置 
    		T get_last();//返回最后一个位置 
    		int insert(int index,T t);//在index位置后插入数值 
    		int insert_first(T t);//在头插入 
    		int append_last(T t);//在尾插入 
    		int Delete(int index);//删除index值 
    		int Delete_first();//删除头结点 
    		int Delete_last();//删除尾结点 
    	private:
    		int count;
    		DNode<T>* phead;
    		DNode<T>* get_node(int index);
    };

    1.计算链表的长度

    template<class T>
    DoubleCircleList<T>::DoubleCircleList():count(0){
    	//创建“表头 ,注意:表头没有存储数据! 
    	phead=new DNode<T>();
    	phead->prev=phead->next=phead;
    	//设置链表计数为0
    	//cout=0; 
    }

    2.销毁链表

    //析构函数   销毁链表
    template<class T>
    DoubleCircleList<T>::~DoubleCircleList(){
    	DNode<T>* ptmp;   
    	DNode<T>* pnode=phead->next;	
    	while(pnode!=phead){	//一直循环往后找 
    		ptmp=pnode;	//
    		pnode=pnode->next;
    		delete ptmp;
    	}
    	delete phead;
    	phead=NULL;
    }

    3.计算结点的数目

    //返回结点数目
    template<class T>
    int DoubleCircleList<T>::size(){
    	return count;
    }

    4.判断链表是否为空

    template<class T>
    int DoubleCircleList<T>::is_empty(){
    	return count==0;
    } 

    5.寻找结点位置

    template<class T>
    DNode<T>* DoubleCircleList<T>::get_node(int index){
    	//判断参数有效性
    	if(index<0||index>=count){
    		cout<<"get node failed! the index in out of bound!"<<endl;
    		return NULL;
    	} 
    	//正向查找 
    	if(index<=count/2){
    		int i=0;
    		DNode<T>* pindex=phead->next;
    		while(i++<index){
    			pindex=pindex->next;
    		}
    		return pindex;
    	}
    	//反向查找
    	 int j=0;
    	 int rindex=count-index-1;
    	 DNode<T>* prindex=phead->prev;
    	 while(j++<rindex){
    	 	prindex=prindex->prev;
    	 }
    	 return prindex;
    }

    6.返回结点位置的值

    template<class T>
    T DoubleCircleList<T>::get(int index){
    	return get_node(index)->value;
    }

    7.获取第一个结点的值

    template<class T>
    T DoubleCircleList<T>::get_first(){
    	return get_node(0)->value;
    } 

    8.获取最后一个结点的值

    template<class T>
    T DoubleCircleList<T>::get_last(){
    	return get_node(count-1)->value;
    } 

    9.将结点插入index之后

    template<class T>
    int DoubleCircleList<T>::insert(int index,T t){
    	if(index==0)
    		return insert_first(t);
    	DNode<T>* pindex=get_node(index);
    	DNode<T>* pnode=new DNode<T>(t,pindex->prev,pindex);
    	pindex->prev->next=pnode;
    	pindex->prev=pnode;
    	count++;
    	return 0;
    
    }

    10.结点插入到第一个位置

    //将结点插入到第一个结点处
    template<class T>
    int DoubleCircleList<T>::insert_first(T t){
    	DNode<T>* pnode=new DNode<T>(t,phead,phead->next);
    	phead->next->prev=pnode;
    	phead->next=pnode;
    	count++;
    	return 0;
    } 

    11.结点插入到最后一个位置

    template<class T>
    int DoubleCircleList<T>::append_last(T t){
    	DNode<T>* pnode=new DNode<T>(t,phead->prev,phead);
    	phead->prev->next=pnode;
    	phead->prev=pnode;
    	count++;
    	return 0;
    } 

    12.删除index结点.

    template<class T>
    int DoubleCircleList<T>::Delete(int index){
    	DNode<T>* pindex=get_node(index);
    	pindex->next->prev=pindex->prev;
    	pindex->prev->next=pindex->next;
    	delete pindex;
    	count--;
    	return 0;
    }

    13.删除第一个结点

    template<class T>
    int DoubleCircleList<T>::Delete_first(){
    	return Delete(0);
    } 

    14.删除最后一个结点

    template<class T>
    int DoubleCircleList<T>::Delete_last(){
    	return Delete(count-1);
    } 

    完整代码:

    //DoubleCircleList.h
    #include<iostream>
    using namespace std;
    template<class T>
    struct DNode{
    	public:
    		T value;
    		DNode *prev;
    		DNode *next;
    	public:
    		DNode(){
    		}
    		DNode(T t,DNode *prev,DNode *next){
    			this->value=t;
    			this->prev=prev;
    			this->next=next;
    		}
    };
    template<class T>
    class DoubleCircleList{
    	public:
    		DoubleCircleList();  //构造函数 创建链表 
    		~DoubleCircleList();  //析构函数 销毁链表 	
    		int size();	//长度 
    		int is_empty();//判断是否为空 
    		T get(int index); //返回index值的位置 
    		T get_first();//返回第一个位置 
    		T get_last();//返回最后一个位置 
    		int insert(int index,T t);//在index位置后插入数值 
    		int insert_first(T t);//在头插入 
    		int append_last(T t);//在尾插入 
    		int Delete(int index);//删除index值 
    		int Delete_first();//删除头结点 
    		int Delete_last();//删除尾结点 
    	private:
    		int count;
    		DNode<T>* phead;
    		DNode<T>* get_node(int index);
    };
    template<class T>
    DoubleCircleList<T>::DoubleCircleList():count(0){
    	//创建“表头 ,注意:表头没有存储数据! 
    	phead=new DNode<T>();
    	phead->prev=phead->next=phead;
    	//设置链表计数为0
    	//cout=0; 
    }
    //析构函数 
    template<class T>
    DoubleCircleList<T>::~DoubleCircleList(){
    	DNode<T>* ptmp;   
    	DNode<T>* pnode=phead->next;	
    	while(pnode!=phead){	//一直循环往后找 
    		ptmp=pnode;	//
    		pnode=pnode->next;
    		delete ptmp;
    	}
    	delete phead;
    	phead=NULL;
    }
    //返回结点数目
    template<class T>
    int DoubleCircleList<T>::size(){
    	return count;
    }
    template<class T>
    int DoubleCircleList<T>::is_empty(){
    	return count==0;
    } 
    template<class T>
    DNode<T>* DoubleCircleList<T>::get_node(int index){
    	//判断参数有效性
    	if(index<0||index>=count){
    		cout<<"get node failed! the index in out of bound!"<<endl;
    		return NULL;
    	} 
    	//正向查找 
    	if(index<=count/2){
    		int i=0;
    		DNode<T>* pindex=phead->next;
    		while(i++<index){
    			pindex=pindex->next;
    		}
    		return pindex;
    	}
    	//反向查找
    	 int j=0;
    	 int rindex=count-index-1;
    	 DNode<T>* prindex=phead->prev;
    	 while(j++<rindex){
    	 	prindex=prindex->prev;
    	 }
    	 return prindex;
    }
    template<class T>
    T DoubleCircleList<T>::get(int index){
    	return get_node(index)->value;
    }
    //获取第1个结点值
    template<class T>
    T DoubleCircleList<T>::get_first(){
    	return get_node(0)->value;
    } 
    //获取最后一个结点值
    template<class T>
    T DoubleCircleList<T>::get_last(){
    	return get_node(count-1)->value;
    } 
    //将结点插入到index位置之前
    template<class T>
    int DoubleCircleList<T>::insert(int index,T t){
    	if(index==0)
    		return insert_first(t);
    	DNode<T>* pindex=get_node(index);
    	DNode<T>* pnode=new DNode<T>(t,pindex->prev,pindex);
    	pindex->prev->next=pnode;
    	pindex->prev=pnode;
    	count++;
    	return 0;
    
    }
    //将结点插入到第一个结点处
    template<class T>
    int DoubleCircleList<T>::insert_first(T t){
    	DNode<T>* pnode=new DNode<T>(t,phead,phead->next);
    	phead->next->prev=pnode;
    	phead->next=pnode;
    	count++;
    	return 0;
    } 
    //结点追加到链表末尾
    template<class T>
    int DoubleCircleList<T>::append_last(T t){
    	DNode<T>* pnode=new DNode<T>(t,phead->prev,phead);
    	phead->prev->next=pnode;
    	phead->prev=pnode;
    	count++;
    	return 0;
    } 
    //删除index位置结点
    template<class T>
    int DoubleCircleList<T>::Delete(int index){
    	DNode<T>* pindex=get_node(index);
    	pindex->next->prev=pindex->prev;
    	pindex->prev->next=pindex->next;
    	delete pindex;
    	count--;
    	return 0;
    }
    //删除第一个结点
    template<class T>
    int DoubleCircleList<T>::Delete_first(){
    	return Delete(0);
    } 
    //删除最后一个结点
    template<class T>
    int DoubleCircleList<T>::Delete_last(){
    	return Delete(count-1);
    } 
    
    //DoubleCircleList.cpp
    #include <iostream>
    #include "DoubleCircleList.h"
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    using namespace std;
    void int_test()
    {
    	int iarr[4] = {10, 20, 30, 40};//定义一个数组
     
    	cout << "\n开始测试 int数据" << endl;
    	// 创建双向链表
    	DoubleCircleList<int>* pdlink = new DoubleCircleList<int>();
     
    	pdlink->insert(0, 20);        // 将 20 插入到第一个位置
    	pdlink->append_last(10);    // 将 10 追加到链表末尾
    	pdlink->insert_first(30);    // 将 30 插入到第一个位置
     
    	// 双向链表是否为空
    	cout << "is_empty()=" << pdlink->is_empty() <<endl;
    	// 双向链表的大小
    	cout << "size()=" << pdlink->size() <<endl;
     
    	// 打印双向链表中的全部数据
    	int sz = pdlink->size();
    	for (int i=0; i<sz; i++)
    		cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;
    }
    
    int main(int argc, char** argv) {
    	int_test();
    	return 0;
    }

    双向循环链表:

    #include<stdio.h>  
    #include<stdlib.h>  
    #include<malloc.h>  
    typedef struct DOUBLE_LIST  
    {  
        int data;  
        struct DOUBLE_LIST *prev;  
        struct DOUBLE_LIST *next;  
    }double_list;  
    double_list *createlist()       //创建有n个元素的双向链表 并输入元素  
    {  
        double_list *head, *p, *q;  
        int n,x;  
        head = (double_list *)malloc(sizeof(double_list));  
        head->prev = head;  
        head->next = head;  
        p = head;  
        printf("输入要创建双向链表的元素的个数:\n");  
        scanf("%d",&n);  
        for(int i=0;i<n;i++)  
        {  
            scanf("%d", &x);  
            q = (double_list *)malloc(sizeof(double_list));  
            q->data = x;  
            p->next = q;  
            head->prev = q;  
            q->prev = p;  
            q->next = head;  
            p = q;  
        }  
        return head;  
    }  
    //遍历并且输出这些元素  
    void printlist(double_list *head)  
    {  
        double_list *p;  
        p = head;  
        p = p->next;  
        while(p!=head)  
        {  
            printf("%d  ", p->data);  
            p = p->next;  
        }  
        printf("\n");  
    }  
    //得到现在双向链表中的元素的个数  
    int lengthlist(double_list *head)  
    {  
        double_list *p;  
        p = head;  
        p = p->next;  
        int coun = 0;  
        while(p!=head)  
        {  
            coun++;  
            p = p->next;  
        }  
        return coun;  
    }  
    //在第i个元素之前插入数据data  
    void insertlist_f(double_list *head, int i, int data)  
    {  
        double_list *p = head, *q;  
        p = p->next;  
        i--;  
        while(i--)  
            p = p->next;  
        q = (double_list *)malloc(sizeof(double_list));  
        q->data = data;  
        (p->prev)->next = q;  
        q->prev = p->prev;  
        q->next = p;  
        p->prev = q;  
    }  
    //删除第i个位置的元素  
    void deletelist_i(double_list *head, int i)  
    {  
        double_list *p = head;  
        p = p->next;  
        i--;  
        while(i--)  
            p = p->next;  
        (p->prev)->next = p->next;  
        (p->next)->prev = p->prev;  
        free(p);  
    }  
    //删除值为x的元素  
    void deletelist_x(double_list *head, int x)  
    {  
        double_list *p = head, *q;  
        p = p->next;  
        while(p!=head)  
            if(p->data == x)  
            {  
                q = p->next;  
                (p->prev)->next = p->next;  
                (p->next)->prev = p->prev;  
                free(p);  
                p = q;  
            }  
            else  
                p = p->next;  
    }  
    //对双向链表进行排序  
    void sortlist(double_list *head)  //升序  
    {  
        double_list *p = head, *q, *t;  
        p = p->next;  
        for(;p!=head;p=p->next)  
            for(t = p->next;t!=head;t=t->next)  
            {  
                if(p->data > t->data)  
                {  
                    int a = p->data;  
                    p->data = t->data;  
                    t->data = a;  
                }  
            }  
    }  
    int main()  
    {  
        double_list *head;  
        head = createlist();  
        deletelist_x(head, 2);  
        //sortlist(head);  
        printlist(head);  
        insertlist_f(head, 2, 2);  
        printlist(head);  
      
        return 0;  
    }  
    

    双向链表的遍历来说我只给出了前序遍历的代码,没有写后序遍历的代码,这其实是差不多的,但是因为双向链表可以进行两个方向的遍历,这给我们带来了很大的方便。

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

    2015-05-25 08:41:16
    c++课程设计的一个小题目,双向链表,该代码存储的node为姓名,电话,年龄。可根据需要进行修改。
  • C++ 双链表

    2018-10-23 11:16:43
    一、什么是双链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们...

    一、什么是双链表

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
    在这里插入图片描述
    在这里插入图片描述

    二、双链表的基本操作

    创建、遍历、测长、插入、删除

    #include <iostream>
    #include <stdio.h>
    using namespace std;
    
    
    //结点类
    class Node {
    public:
    	int data;
    	Node *pPre, *pNext;
    };
    
    //双向链表类
    class DoubleLinkList {
    public:
    	DoubleLinkList() {
    		head = new Node;
    		head->data = 0;
    		head->pNext = NULL;
    		head->pPre = NULL;
    	}
    	~DoubleLinkList() { delete head; }
    	void CreateLinkList(int n);				//创建链表
    	void InsertNode(int position, int d);	//在指定位置处插入结点
    	void TraverseLinkList();				//遍历链表
    	bool IsEmpty();							//判断链表是否为空
    	int GetLength();						//获得链表长度
    	void DeleteNode(int position);			//删除指定位置处结点
    	void DeleteLinkList();					//删除链表
    private:
    	Node *head;
    };
    
    void DoubleLinkList::CreateLinkList(int n) {
    	if (n < 0) {
    		cout << "输入结点个数错误!" << endl;
    		exit(EXIT_FAILURE);
    	}
    	else {
    		int i = 0;
    		Node *pnew, *ptemp;
    		ptemp = head;
    		i = n;
    		while (n-- > 0) {
    			cout << "请输入第" << i - n << "个结点值:";
    			pnew = new Node;
    			cin >> pnew->data;
    			pnew->pNext = NULL;   //也可以放while外,但需要初始化
    			pnew->pPre = ptemp;
    			ptemp->pNext = pnew;
    			ptemp = pnew;
    		}
    	}
    }
    
    void DoubleLinkList::InsertNode(int position, int d) {
    	if (position < 0 || position > GetLength() + 1) {
    		cout << "输入位置错误!" << endl;
    		exit(EXIT_FAILURE);
    	}
    	else {
    		Node *pnew, *ptemp;
    		pnew = new Node;
    		pnew->data = d;
    		ptemp = head;
    
    		while (position-- > 1)
    			ptemp = ptemp->pNext;
    
    		if (ptemp->pNext != NULL)
    			ptemp->pNext->pPre = pnew;
    		pnew->pNext = ptemp->pNext;
    		pnew->pPre = ptemp;
    		ptemp->pNext = pnew;
    		ptemp = pnew;
    	}
    }
    
    void DoubleLinkList::TraverseLinkList() {
    	Node *ptemp = head->pNext;
    	while (ptemp != NULL) {
    		cout << ptemp->data << " ";
    		ptemp = ptemp->pNext;
    	}
    	cout << endl;
    }
    
    bool DoubleLinkList::IsEmpty() {
    	if (head->pNext == NULL)
    		return true;
    	else
    		return false;
    }
    
    int DoubleLinkList::GetLength() {
    	int n = 0;
    	Node *ptemp = head->pNext;
    	while (ptemp != NULL) {
    		n++;
    		ptemp = ptemp->pNext;
    	}
    	return n;
    }
    
    void DoubleLinkList::DeleteNode(int position) {
    	if (position < 0 || position > GetLength()) {
    		cout << "输入数据错误!" << endl;
    		exit(EXIT_FAILURE);
    	}
    	else {
    		Node *pdelete, *ptemp;
    		ptemp = head;
    
    		while (position-- > 1)
    			ptemp = ptemp->pNext;
    		pdelete = ptemp->pNext;
    		if (pdelete->pNext != NULL)
    			pdelete->pNext->pPre = ptemp;
    		ptemp->pNext = pdelete->pNext;
    		delete pdelete;
    		pdelete = NULL;
    	}
    }
    
    void DoubleLinkList::DeleteLinkList() {
    	Node *pdelete, *ptemp;
    	pdelete = head->pNext;
    	while (pdelete != NULL) {
    		ptemp = pdelete->pNext;
    		head->pNext = ptemp;
    		if (ptemp != NULL)
    			ptemp->pPre = head;
    		delete pdelete;
    		pdelete = ptemp;
    	}
    }
    
    //测试函数
    int main() {
    	DoubleLinkList dl;
    	int position = 0, value = 0, n = 0;
    	bool flag = false;
    
    	cout << "请输入需要创建双向链表的结点个数:";
    	cin >> n;
    	dl.CreateLinkList(n);
    
    	cout << "打印链表值如下:";
    	dl.TraverseLinkList();
    
    	cout << "请输入插入结点的位置和值:";
    	cin >> position >> value;
    	dl.InsertNode(position, value);
    
    	cout << "打印链表值如下:";
    	dl.TraverseLinkList();
    
    	cout << "请输入要删除结点的位置:";
    	cin >> position;
    	dl.DeleteNode(position);
    
    	cout << "打印链表值如下:";
    	dl.TraverseLinkList();
    
    	dl.DeleteLinkList();
    	flag = dl.IsEmpty();
    	if (flag)
    		cout << "删除链表成功!" << endl;
    	else
    		cout << "删除链表失败!" << endl;
    
    	system("pause");
    	return 0;
    }
    

    参考:(C++版)链表(三)——实现双向链表的创建、插入、删除等简单操作(链表有从一到四的系列,都写的很好,单向循环和双向循环链表可直接参考)

    展开全文
  • C++双链表

    2020-07-11 12:18:47
    #include <iostream> using namespace std; template <class T> class DblList; template <class T> struct DblNode { friend class DblList<T>; public: DblNode(T &....
    #include <iostream>
    using namespace std;
    
    template <class T> class DblList;
    
    template <class T>
    struct DblNode
    {
    	friend class DblList<T>;
    public:
    	DblNode(T &dt) :data(dt) {}
    	DblNode() {}
    //private:
    	T data;
    	DblNode *lLink;
    	DblNode *rLink;
    };
    
    template <class T>
    class DblList
    {
    public:
    	DblList() 
    	{
    		first = new DblNode<T>();
    		first->lLink = first->rLink = first;
    	};
    	DblNode<T> * getFirst()
    	{
    		return first;
    	}
    	//在p1的右边插入p2
    	void Insert(DblNode<T> * p1, DblNode<T> * p2);
    	void Delete(DblNode<T> * p);
    
    private:
    	DblNode<T> *first;
    };
    
    template <class T>
    void DblList<T>::Insert(DblNode<T> * p1, DblNode<T> * p2)
    {
    	p2->lLink = p1;
    	p2->rLink = p1->rLink;
    
    	p1->rLink->lLink = p2;
    	p1->rLink = p2;
    }
    
    template <class T>
    void DblList<T>::Delete(DblNode<T> * p)
    {
    	if (p == first)
    		return;
    
    	p->lLink->rLink = p->rLink;
    	p->rLink->lLink = p->lLink;
    
    	delete p;
    }
    
    
    int main()
    {
    	DblList<int> iDl;
    
    	
    	int a1 = 10, a2 = 20, a3 = 30, a4 = 40;
    	DblNode<int> *node1 = new DblNode<int>(a1);
    	DblNode<int> *node2 = new DblNode<int>(a2);
    	DblNode<int> *node3 = new DblNode<int>(a3);
    	DblNode<int> *node4 = new DblNode<int>(a4);
    
    	iDl.Insert(iDl.getFirst(),node1);
    	iDl.Insert(iDl.getFirst(), node2);
    	iDl.Insert(iDl.getFirst(), node3);
    	iDl.Insert(iDl.getFirst(), node4);
    	
    
    	cout<< iDl.getFirst() ->rLink->data<<endl;
    	cout << iDl.getFirst()->rLink->rLink->data << endl;
    	cout << iDl.getFirst()->rLink->rLink->rLink->data << endl;
    	cout << iDl.getFirst()->rLink->rLink->rLink->rLink->data << endl;
    
    	cout << endl << endl;
    
    	iDl.Delete(node1);
    	iDl.Delete(node4);
    
    	cout << iDl.getFirst()->rLink->data << endl;
    	cout << iDl.getFirst()->rLink->rLink->data << endl;
    	//cout << iDl.getFirst()->rLink->rLink->rLink->data << endl;
    	
    	return 0;
    }

    运行结果:

     

    展开全文
  • C++ 双向链表

    2018-10-20 15:14:44
    偶尔当一条咸鱼,今天试一下用C++实现双向链表 --------------------------------------------------------include.h ---------------------------------------------------- -------- 有一些大佬说尽量避免...

    使用 VS2017 + Windows 7

    偶尔当一条咸鱼,今天试一下用C++实现双向链表

    --------------------------------------------------------include.h       ----------------------------------------------------

    -------- 有一些大佬说尽量避免头文件写到一个文件夹中,但是目前还没有找到好的书写方式
    #pragma once
    #ifndef __INCLUDE__
    #define __INCLUDE__
    
    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    #endif 
    

    ---------------------------------------------------------DoubleLink.h---------------------------------------------------

    -----DoubleLink.h
    #pragma once
    #include "include.h"
    #include "test.h"
    using namespace std;
    typedef struct Link  -- 节点
    {
    	int item;
    	Link* next;
    	Link* prev;
    };
    
    class DoubleLink
    {
    private:
    	int length;  -- 链表长度
    	Link* header;-- 第一个节点
    	Link* tail;  -- 最后一个节点
    public:
    	DoubleLink();
    	Link* CreateItem();                  --创建内存
    	bool Push(int item);                 -- 压入到链表最后一个位置
    	int Pop();                           -- 从取出最后一个
    	bool InsertItem(int index, int item);-- 插入到指定位置
    	int DeleteAt(int index);             -- 删除指定位置
    	void SelectAll();                    -- 打印所有节点
    };
    

    -------------------------------------------------------------DoubleLink.cpp------------------------------------------------------------

    #include "DoubleLink.h"
    
    DoubleLink::DoubleLink()
    {
        header = CreateItem();
        tail = header;
        length = 0;
    }
    
    bool DoubleLink::Push(int item) -- 压入到最后一个节点
    {
        Link* link = CreateItem();  -- 首先 创建一块相应的内存
        if (!link)                  -- 如果创建失败
        	return false;
        link->item = item;
        link->prev = tail;
        tail->next = link;
        tail = link;
        tail->next = header;
        header->prev = tail;
        length++;
        return true;
    }
    
    int DoubleLink::Pop()
    {
        Link* link = header->next;
        int item = 0;
        for (int i = 0; i < length - 1; i++)
        {
        	link = link->next;
        }
        item = link->item;
        tail = link->prev;
        tail->next = link->next;
        length--;
        free(link);                  -- 释放内存地址
        link = NULL;                 -- 让他指向0x000000地址
        return item;
    }
    
    Link* DoubleLink::CreateItem()
    {
        Link* item = (Link*)malloc(sizeof(Link)); -- 注意 我们是使用malloc创建的内存 所以应该是用free释放 而不是delete
        return item;
    }
    
    bool DoubleLink::InsertItem(int index, int item)
    {
        if (index > length)
        {
        	cout << "索引超出" << endl;
        	return false;
        }
        Link* link = CreateItem();
        link->item = item;
        Link* temp = header;
        for (int i = 0; i < index; i++)
        {
        	temp = temp->next;
        }
        link->prev = temp->prev;    -- 和冒泡的替换差不多
        link->next = temp;
        temp->prev->next = link;
        temp->prev = link;
        length++;
        return true;
    }
    
    int DoubleLink::DeleteAt(int index)
    {
        if (index > length || index < 1)
        {
        	cout << "索引超出" << endl;
        	return false;
        }
        Link* link;
        int data = 0;
        if (index > length / 2)            -- 为了节省 所以我们分为向前遍历和向后遍历
        {
        	link = header;
        	for (int i = 0; i < index; i++)
        	{
        		link = link->next;
        	}
        	link->prev->next = link->next;
        	link->next->prev = link->prev;
        	data = link->item;
        	free(link);
        	link = NULL;
        	cout << "" << endl;
        }
        else
        {
        	link = header->prev;
        	for (size_t i = 0; i < length - index; i++)
        	{
        	    link = link->prev;
    	    	cout << "Link->Prev:" << link->item << endl;
    	    }
    	    link->prev->next = link->next;
    	    link->next->prev = link->prev;
    	    data = link->item;
    	    free(link);
    	    link = NULL;
        }
        length--;
        return data;
    }
    
    void DoubleLink::SelectAll()
    {
        Link* link = header->next;
        for (int i = 0; i < length; i++)
        {
        	cout << link->item << endl;
        	link = link->next;
        }
    }

    ------------------------------------------------------------------main.cpp------------------------------------------------------------------------

    #include "DoubleLink.h"
    int main()
    {
        // 在这里 分清指针和地址的关系 地址是使用link.methodName(params object o) 访问
        // 指针是用过 link->methodName(params object o) 访问
        DoubleLink link; 
        for (int i = 0; i < 7; i++)
        {
        	link.Push(i);
        }
        link.InsertItem(1, 1002);
        link.SelectAll();
        cout << "Pop:" << link.Pop() << endl;  -- 因为我们DoubleLink.h 里面有Inclde.h的声明 所以可以直接使用 cout<<endl;
        link.SelectAll();
        cout << "DeleteAt:" << link.DeleteAt(7) << endl;
        link.SelectAll();
        
        system("pause");
        return 0;
    }
    

     

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

    2019-01-20 13:14:06
    #include &amp;lt;iostream&amp;gt; using std::cout; using std::endl; struct Node { ...一、创建双向链表 Node * createList() { Node * head = new Node; if (NULL == ...
  • c++ 双链表

    2018-09-28 11:28:24
    #include &lt;iostream&gt; template &lt;class T&gt; struct Node {  T data;  Node *pre;  Node *next; }; template &lt;class T&gt; class DoubleList ... ~DoubleList()...
  • c++双链表

    2016-05-26 10:07:24
    test.cpp// dlist.cpp : 定义控制台应用程序的入口点。 //#include "stdafx.h" #include #include "dlist.h"int main() { Dlist<int> dlist; int i = dlist.size(); std::cout ; dlist.
  • 主要介绍了c++双向链表操作示例,包括创建双向链、删除双向链表、双向链表中查找数据、插入数据等,需要的朋友可以参考下
  • 主要为大家详细介绍了C++双向链表实现简单通讯录,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,930
精华内容 1,572
关键字:

c++双链表

c++ 订阅