精华内容
下载资源
问答
  • 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++ 双向链表

    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 == ...

    在这里插入图片描述

    #include <iostream>
    using std::cout;
    using std::endl;
    struct Node
    {
    	int data;
    	struct Node * next;
    	struct Node * pre;
    };
    

    一、创建双向链表

    Node * createList()
    {
    	Node * head = new Node;
    	if (NULL == head)
    		exit(-1);
    	head->next = head;
    	head->pre = head;
    	return head;
    }
    

    二、插入元素(头插法)
    让新来的节点先有所指
    在这里插入图片描述

    void insertList(Node * head,int n)
    {
    	Node * cur = new Node;
    	if (NULL == cur)
    		exit(-1);
    	cur->next = head->next;
    	cur->pre = head;
    	head->next = cur;
    	cur->next->pre = cur;
    	
    	cur->data = n;
    }
    

    三、链表长度

    int lenList(Node * head)
    {
    	int i = 0;
    	Node * t = head->next;
    	while (t != head)
    	{
    		i++;
    		t = t->next;
    	}
    	return i;
    }
    

    四、查找遍历
    在这里插入图片描述

    Node * findList(Node * head,int fn)
    {
    	Node * forward = head->next;
    	Node * back = head->pre;
    	while (forward != back->next)
    	{
    		if (forward->data == fn)
    			return forward;
    		if (back->data == fn)
    			return back;
    		if (forward == back)
    			break;
    		forward = forward->next;
    		back = back->pre;
    	}
    	return NULL;
    }
    

    五、删除其中元素

    void deleteList(Node * pFind)
    {
    	pFind->pre->next = pFind->next;
    	pFind->next->pre = pFind->pre;
    	delete pFind;
    }
    

    六、排序
    (类似于先删除 再插入)
    在这里插入图片描述

    void sortDlist(Node * head)
    {
    	int len = lenList(head);
    	Node *prep = NULL;
    	Node *p = NULL;
    	Node *q = NULL;
    	Node *t = NULL;
    	for (int i = 0;i < len - 1;i++)
    	{
    		p = head->next;
    		q = p->next;
    		for (int j = 0;j < len - 1 - i;j++)
    		{
    			if ((p->data)<(q->data))
    			{
    				p->pre->next = q;
    				q->pre = p->pre;
    
    				p->next = q->next;
    				p->pre = q;
    
    				q->next = p;
    				p->next->pre = p;
    
    				t = p;
    				p = q;
    				q = t;
    			}
    			p = p->next;
    			q = q->next;
    		}
    	}
    }
    

    七、销毁链表

    void desList(Node * head)
    {
    	head->pre->next = NULL;
    	Node *t = NULL;
    	while (head != NULL)
    	{
    		t = head;
    		head = head->next;
    		delete t;
    	}
    }
    
    展开全文
  • 主要介绍了c++双向链表操作示例,包括创建双向链、删除双向链表、双向链表中查找数据、插入数据等,需要的朋友可以参考下
  • 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-03-03 21:54:40
    #include<iostream> using namespace std; struct Note { Note *Prev; Note *Next; int m_iData; }; class MyListNote { public: Note *m_pHead;... //判断链表是不是空 bool isEmpty() { return...
    #include<iostream>
    using namespace std;
    struct Note
    {
    	Note *Prev;
    	Note *Next;
    	int m_iData;
    };
    
    class MyListNote
    {
    public:
    	Note *m_pHead;
    	Note *m_pTail;
    	//判断链表是不是空
    	bool isEmpty() { return !m_pHead; };	
    	int m_iCount;
    	//插入数据,包括头插,尾插,及任意位置插入
    	void insertDataAtNote(int index, int iData);
    	//随机删除一个数	
    	void DeleteDataRandomNote(int index);	
    	//改变任意链表上的数据
    	void ChangeDataAtNote(int index, int iData);
    	//寻找某个数出现的位置,及该数出现的次数
    	int FindDataAtNote(int iData,int & Num);	
    	//从头到尾遍历输出
    	void showHeadToTailNote();	
    	//从尾到头遍历输出
    	void showTailToHeadNote();			
    	MyListNote() { m_pHead = m_pTail = nullptr; m_iCount = 0; };
    };
    
    void MyListNote::insertDataAtNote(int index, int iData)
    {
    	if (isEmpty())
    	{
    		Note *pNote = new Note();
    		pNote->m_iData = iData;
    		pNote->Next = NULL;
    
    		m_pHead = m_pTail = pNote;
    		m_iCount++;
    		return;
    	}
    
    	 if (index <= 1)
    	{
    		Note *pNote = new Note();
    		pNote->m_iData = iData;
    		pNote->Next = NULL;
    
    		pNote->Next = m_pHead;
    		m_pHead->Prev = pNote;
    
    		m_pHead = pNote;
    		m_iCount++;
    	}
    	else if (index >= m_iCount)
    	{
    		Note *pNote = new Note();
    		pNote->m_iData = iData;
    		pNote->Next = NULL;
    
    		m_pTail->Next = pNote;
    		pNote->Prev = m_pTail;
    
    		m_pTail = pNote;
    		m_iCount++;		
    	}
    	else
    	{
    		Note *pNote = new Note();
    		pNote->m_iData = iData;
    		pNote->Next = NULL;
    		Note *tempNote = m_pHead;
    		for (int i = 0; i < index-2; i++)
    		{
    			tempNote = tempNote->Next;		//找到需要插入的前一个
    		}
    		tempNote->Next->Prev = pNote;
    		pNote->Next = tempNote->Next;
    		tempNote->Next = pNote;
    		pNote->Prev = tempNote;
    		m_iCount++;
    	}
    }
    
    void MyListNote::DeleteDataRandomNote(int index)
    {
    	if (isEmpty())
    	{
    		cout << "空链" << endl;
    	}
    	if (index <= 1)
    	{
    		m_pHead = m_pHead->Next;
    		delete m_pHead->Prev;
    		m_pHead->Prev = NULL;
    		m_iCount--;
    	}
    	else if (index >= m_iCount)
    	{	
    		m_pTail = m_pTail->Prev;
    		delete m_pTail->Next;
    		m_pTail->Next = NULL;
    		m_iCount--;
    	}
    	else
    	{
    		Note *tempNote = m_pHead;
    		for (int i = 0; i < index - 1; i++)
    		{
    			tempNote = tempNote->Next;
    		}
    		tempNote->Next->Prev = tempNote->Prev;
    		tempNote->Prev->Next = tempNote->Next;
    		delete tempNote;
    		m_iCount--;
    	}
    	
    }
    
    void MyListNote::ChangeDataAtNote(int index, int iData)
    {
    	if (isEmpty())
    	{
    		cout << "这是个空链" << endl;
    	}
    	if (index <= 1)
    	{
    		m_pHead->m_iData = iData;
    	}
    	else if(index>=m_iCount)
    	{
    		m_pTail->m_iData = iData;
    	}
    	else
    	{
    		Note *tempNote = m_pHead;
    		for (int i = 0; i < index-1; i++)
    		{
    			tempNote = tempNote->Next;
    		}
    		tempNote->m_iData = iData;
    	}
    }
    
    int MyListNote::FindDataAtNote(int iData, int & Num)
    {
    	int firstPos = 0;
    	firstPos = m_iCount-1;
    	int Tally = 0;
    	if (isEmpty())
    	{
    		cout << "这是个空链" << endl;
    	}
    	Note *tempNote = m_pHead;
    
    	while (tempNote)
    	{
    		++Tally;
    		if (tempNote->m_iData == iData)
    		{
    			if (firstPos == m_iCount - 1)
    				firstPos=Tally;				//第一次找到的位置	
    			++Num;						//找到iData的个数
    		}
    		tempNote = tempNote->Next;	
    	}
    	return firstPos;
    }
    
    void MyListNote::showHeadToTailNote()
    {
    	if (isEmpty())
    	{
    		cout << "这是个空链表" << endl;
    	}
    	else
    	{
    		Note *pNote = m_pHead;
    		while (pNote)
    		{
    			cout << pNote->m_iData << endl;
    			pNote = pNote->Next;
    		}	
    	}
    }
    
    void MyListNote::showTailToHeadNote()
    {
    	if (isEmpty())
    	{
    		cout << "这是个空链表" << endl;
    	}
    	else
    	{
    		Note *pNote = m_pTail;
    		while (pNote)
    		{
    			cout << pNote->m_iData << endl;
    			pNote = pNote->Prev;
    		}
    	}
    }
    
    void main()
    {
    	MyListNote note;
    	for (int i = 0; i < 10; i++)
    	{
    		note.insertDataAtNote(0, i);
    	}
    	note.showHeadToTailNote();
    	cout << "-------------" << endl;
    	note.insertDataAtNote(5, 100);
    
    	note.DeleteDataRandomNote(1);
    	note.DeleteDataRandomNote(12);
    	note.DeleteDataRandomNote(5);
    	note.showHeadToTailNote();
    	cout << "---------------" << endl;
    	note.ChangeDataAtNote(5,5000);
    	cout << "--------------" << endl;
    	int a = 0;		//寻找函数的个数引用
    	cout << "第一次出现的位置:"<<note.FindDataAtNote(4, a)<< endl;
    	cout <<"这个数一共出现"<<a<<"次" << endl;
    	note.showHeadToTailNote();
    }

     

    展开全文
  • 主要为大家详细介绍了C++双向链表实现简单通讯录,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • C++双向链表删除,修改,插入,排序,全面,界面人性化
  • c++双向链表源代码

    2016-08-10 14:11:24
    c++双向链表源代码 数据结构
  • c++双向链表的实现

    2010-12-19 18:16:52
    自己写的实现c++双向链表的功能,包括InsertAtHead,Append,RemoveHead,RemoveTail,InsertAfter, DeleteAt,Reset,GetPre,GetNext等函数 压缩包里包含CMyList.h和CMyList.cpp两个文件
  • (四)C++双向链表排序

    2018-11-09 16:40:10
    C++双向链表排序 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成,数据类型为整型。) 输入 第一行:双向表的长度; 第二行:链表中的数据元素。 输出 ...
  • C++ 双向链表的建立与遍历

    千次阅读 2019-05-27 19:49:16
    C++ 双向链表的建立与遍历 开发工具与关键技术:C++、VisualStudio 作者:何任贤 撰写时间:2019年05月20日 链表是以struct或class数据结构为基础的动态数据结构,它的存储方式是以节点形式存储,节点分为两部分,...

空空如也

空空如也

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

c++双向链表

c++ 订阅