武汉c培训
达内武汉中心

15271940953

热门课程

达内C++学员笔记:c++实现双链表

  • 时间:2016-06-30
  • 发布:武汉C++培训
  • 来源:c语言教程

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include "conio.h"
using namespace std;

struct _DOUBLE_LINK_NODE  //定义一个双链表结构
{
    char * data;
    struct _DOUBLE_LINK_NODE* prev; //双链表的前驱
    struct _DOUBLE_LINK_NODE* next;//双链表的后驱
} ;

class DoubleList
{
private:
public:
    struct _DOUBLE_LINK_NODE * Head;
    DoubleList()
    {
        Head = (struct _DOUBLE_LINK_NODE *) malloc (sizeof(_DOUBLE_LINK_NODE));
        memset(Head, 0, sizeof(_DOUBLE_LINK_NODE));
    }
    ~DoubleList()
    {
    }
    struct _DOUBLE_LINK_NODE * create_double_link_node(char * value)
    {
        struct _DOUBLE_LINK_NODE* pnode;
        pnode =(_DOUBLE_LINK_NODE *)malloc(sizeof(_DOUBLE_LINK_NODE));
        memset(pnode,0,sizeof(_DOUBLE_LINK_NODE));
        pnode->data=(char *)malloc(strlen(value)+1);
        memset(pnode->data,0,strlen(value)+1);
        memcpy(pnode->data,value,strlen(value));
        
        pnode->prev=(struct _DOUBLE_LINK_NODE *)malloc(sizeof(_DOUBLE_LINK_NODE));
        memset(pnode->prev,0,sizeof(_DOUBLE_LINK_NODE));
        memcpy(pnode->prev,pnode,sizeof(_DOUBLE_LINK_NODE));
        return pnode;
    }

    _DOUBLE_LINK_NODE* find_data_in_double_link(char  * data)
    {
        _DOUBLE_LINK_NODE* pNode = Head;
        int count=count_number_in_double_link();
        //for(;pNode && pNode->next;pNode = pNode->next)
        if (data==NULL)
        {
            return NULL;
        }
        else
        {
            for(int i=0;i<count;i++)
            {
                if (pNode->data && strcmp(pNode->data, data) == 0)
                {
                    return pNode;
                }
                else
                {
                    pNode = pNode->next;
                }
            }
        }
        return NULL;
    }

    bool insert_data_into_double_link(_DOUBLE_LINK_NODE *node,char * data)
    {
        _DOUBLE_LINK_NODE * pNode=Head;
        _DOUBLE_LINK_NODE * findNode= NULL;
        int count=count_number_in_double_link();
        if (find_data_in_double_link(data)!=NULL)
        {
            findNode=find_data_in_double_link(data);
        }
        else
        {
            for(int i=0;i<count;i++)
            {
                if (pNode->next==NULL)
                {
                    findNode=pNode;
                }
                else
                {
                    pNode = pNode->next;
                }
            }
        }
        if (pNode->data==NULL && pNode->next ==NULL)
        {
            pNode->next=node->prev;
            node->prev=pNode;
        }
        else
        {
            if (findNode->next==NULL)
            {
                pNode->next=node->prev;
                node->prev=pNode;
            }
            else
            {
                node->next=findNode->next->prev;
                findNode->next=node;
                node->prev=findNode->prev;
                node->next->prev=node;
            }
        }
        return true;
    }

    bool delete_data_from_double_link(char * data)
    {
        _DOUBLE_LINK_NODE* pNode;
        pNode=find_data_in_double_link(data);

        //*pNode->next->prev = *pNode->prev;
        if (pNode->next!=NULL)
        {
            pNode->next->prev=pNode->prev;
            pNode->prev->next = pNode->next;
        }
        else
        {
            pNode->prev->next = pNode->next;
        }
        free(pNode);
        return true;
    }
    
    void print_double_link_node()
    {
        _DOUBLE_LINK_NODE *DoubleList =Head;
        while(NULL != DoubleList){
            printf("%s\n", DoubleList->data);
            DoubleList = DoubleList ->next;
        }
    }

    int count_number_in_double_link()
    {
        int count = 0;
        _DOUBLE_LINK_NODE *DoubleList =Head;

        while(NULL != DoubleList){
            count ++;
            DoubleList = DoubleList->next;
        }
        return count;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    DoubleList *list=new DoubleList();
    char * str="Hello word!你好~~";
    char * dd="jsgw";
    _DOUBLE_LINK_NODE *node= list->create_double_link_node(str);
    _DOUBLE_LINK_NODE * node1=list->create_double_link_node(dd);
    list->insert_data_into_double_link(node,NULL);
    list->insert_data_into_double_link(node1,NULL);
    node= list->create_double_link_node("hello world!");

    list->insert_data_into_double_link(node,"adf");

    int d=list->count_number_in_double_link();
    list->print_double_link_node();
    printf("链表中共有%d条数据\n",d);

    printf("删除数据:");
    char * str1="hello world!";

    int a;
    cin>>a;
    if (a==0)
    {
        list->delete_data_from_double_link(str1);
        list->print_double_link_node();
    }
    cin.get();
}
上一篇:c++学习笔记_CDate类的实现
下一篇:C++虚函数、虚函数的作用
选择城市和中心
贵州省

广西省

海南省