双向链表基本操作

一、工程源码

// d-linklist.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <malloc.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define OK 0
#define FAIL -1

typedef struct DLINKLIST
{
    DLINKLIST *pPrevNode;
    DLINKLIST* pNextNode;
    int data;
}List;

int g_data = 0;

List *Create_List()
{
    List *pHeadNode = NULL;
    pHeadNode = (List *) malloc(sizeof(List));
    if( pHeadNode == NULL )
        return NULL;

    pHeadNode->data = g_data++;
    pHeadNode->pPrevNode = NULL;
    pHeadNode->pNextNode =  NULL;

    return pHeadNode;
}

//****************************************************************************************
//        头插法添加链表节点
//****************************************************************************************
int Insert_Node_From_Head(List **ppHeadNode)
{
    List  *pNewNode = NULL;
    List  *p = (*ppHeadNode);

    int i = 0;
    do
    {
        pNewNode = (List *)malloc(sizeof(List));
        if(pNewNode == NULL)
            return FAIL;

        pNewNode->data = g_data--;
        p->pPrevNode = pNewNode;
        pNewNode->pNextNode = p;
        pNewNode->pPrevNode = NULL;
        p = pNewNode;
        i ++;
    }while(i < 3);

    (*ppHeadNode) = p;

    return OK;
}

//****************************************************************************************
//        尾插法添加链表节点
//****************************************************************************************
int Insert_Node_From_Tail(List **ppHeadNode)
{
    List *p = (*ppHeadNode);
    List *pNewNode = NULL;
    bool isCreateSuccess = false;

    while(p->pNextNode != NULL )
    {
        p = p->pNextNode;
    }

    for(int i = 0; i<3; i++)
    {
        pNewNode = (List *)malloc(sizeof(List));
        if( pNewNode == NULL)
        {
            isCreateSuccess = false;
            continue;
        }
        else
        {
            isCreateSuccess = true;
            pNewNode->data = g_data++;
        }

        p->pNextNode = pNewNode;
        pNewNode->pPrevNode = p;
        pNewNode->pNextNode = NULL;
        p = pNewNode;
    }

    if(isCreateSuccess)
        return OK;
    else
        return FAIL;
}

int Delete_Node(List **ppHeadNode,int data)
{
    List *p = *ppHeadNode;    // 取出双链表的首地址
    while(p->pNextNode != NULL)
    {
        if(p->data == data)
        {
            /* 如果是头结点 */
            if(p->pPrevNode == NULL)
            {
                p->pNextNode->pPrevNode = NULL;
                *ppHeadNode = p->pNextNode;
                free(p);
            }
            else
            {
                p->pNextNode->pPrevNode = p->pPrevNode;
                p->pPrevNode->pNextNode = p->pNextNode;
                free(p);
            }
            break;
        }
        else
        {
            p = p->pNextNode;
        }
    }
    return OK;
}

void Show_List_Data(List *pHeadNode)
{
    List *p = pHeadNode;
    printf("Current data in d-list is :\n");

    while(p->pNextNode != NULL)
    {
        printf("%5d,",p->data);
        p = p->pNextNode;
    }

    printf("\n\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    printf("===================D-LINK LIST OPERATION ================\n");
    List *L = NULL;
    int option = 0;
    int del_data = 0;
    bool isStopLoop = false;

    if( (L=Create_List()) == NULL)
    {
        printf("Create d link list fail \n");
        return FAIL;
    }

    while(true)
    {
        printf(" 0, insert d-node from head \n  1, insert d-node from tail \n  2,delete a d-node \n 3, show d-list  4, clear screen\n  5,exit\n");
        scanf("%d",&option);
        switch(option)
        {
        case 0:
            if(Insert_Node_From_Tail(&L) == FAIL)
                printf("insert  node fail");
            Show_List_Data(L);
            break;
        case 1:
            if(Insert_Node_From_Head(&L) == FAIL)
                printf("insert a node fail");
            Show_List_Data(L);
            break;
        case 2:
            printf("input data in node\n");
            scanf("%d",&del_data);
            if(Delete_Node(&L,del_data) == FAIL)
                printf("data isn't in d-list!\n");
            Show_List_Data(L);
            break;
        case 3:
            Show_List_Data(L);
            break;
        case 4:
            /* 系统清屏 */
            system("cls");
            break;

        case 5:
            isStopLoop = true;
            break;

        default:
            break;
        }

        if(isStopLoop)
            break;
    }

    return 0;
}

 

二、效果图

图 头插、尾插法添加节点

 

图 删除节点