重温数据结构之单向链表

    虽然自己做了两年多的C开发了，但慢慢发现计算机理论知识是越来越重要了。我是一个半路出家的“和尚”（大学里所学专业是非计算机类的，只是有些与计算机相关而已），大学里除了C语言外，其它的那些计算机相关的课都是选修课。但我又对计算机编程很感兴趣，一直自学编程（从大二开始学习）。也一直认为自己的计算机理论知识不深，这可能限制我的个人发展，所以决定从现在开始慢慢的补习自己的计算机理论知识，让自己再从内功开始修炼，表面上的功能越来越显的无力可发了。

    这篇日志是我学习数据结构的第一篇，用来记下我的学习心得，一方面可以记下自己的成功之路，另一方面，提供给广大跟我一样需要修炼内功的朋友来参考学习和交流。并且，我会在以后对数据结构（表、队列、栈和树）的学习中继续连载下去。请看到此篇文章的朋友给个鼓励与支持，谢谢各位了。

 

以下是代码讲解：

///////////////////////////////////////////////////////////////////////////////////

/*
 * File : list_test.c
 * Author : Nie Jun
 * Date : 2009/09/08
 * Mail : [e-mail]
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

////////////////////////////////////////////////////////////////////////////////

#define TRUE 1
#define FALSE 0

#define MAX_NAME_SIZE 64

////////////////////////////////////////////////////////////////////////////////

//字节对齐方式

#pragma pack(1)

//定义表节点结构体

typedef struct __ListNode_ ListNode;
struct __ListNode_
{
    ListNode *next; //指向下一个节点

    unsigned long index; //一个常数,目前用于记录一个数字,可以不使用

    char Name[MAX_NAME_SIZE]; //存的重要数据,你可以定义自己的数据格式

};

//定义链表头的数据结构,我的设计是用一个链表头唯一表示一条链表,也可以不要

typedef struct __List_
{
    int size; //链表的大小

    int reserv; //为了字节对齐而保留的字段

    ListNode *head; //链表的头节点,即第一个节点


} List;

#pragma pack()
////////////////////////////////////////////////////////////////////////////////

List MyList;

////////////////////////////////////////////////////////////////////////////////


/*
 * 此函数用于给链表添加新项
 * pList -- 指向链表的指针
 * NewNode -- 需要添加的新节点指针
 */
int addNode(List *pList, ListNode *NewNode)
{
    ListNode *pNode = NULL;

    //做容错处理

    if (!NewNode || !pList)
        return FALSE;

#if 0
    //从链表头部进行添加新项,此方式应该效率会更高,不用遍历链表的每一项,直接从头添加

    pNode = NewNode;
    if (pList->head)
    {
        pNode->next = pList->head;
        pList->head = pNode;
    }
    else
    {
        pList->head = pNode;
    }
#endif

    //从链表尾部开始添加新项,此种方式效率会比较低

    if (!pList->head)
    {
        //如果表头为空,刚添加第一个节点

        pList->head = NewNode;
        pList->size++;
    }
    else
    {
        //否则从表的后面开始添加节点

        pNode = pList->head;
        while (pNode)
        {
            //用循环来遍历链表

            if (pNode->next == NULL)
            {
                //找到表尾后则进行添加操作

                pNode->next = NewNode;
                pList->size++;
                printf("Add a node name %s, index %d, list size %d\n", NewNode->Name, NewNode->index, pList->size);
                break;
            }

            //若没有到表尾刚继续找

            pNode = pNode->next;
        }
        
    }

    return TRUE;

}

/*
 * 此函数实现链表的插入操作
 * pSrc -- 需要插入的节点指针
 * pPosition -- 插入的位置,在其后进行插入操作
 * pList -- 需要进行插入操作的链表
 */
int insertList(ListNode *pSrc, ListNode *pPosition, List *pList)
{
    if (!pSrc || !pPosition)
        return FALSE;

    //进行插入操作,不太明白的朋友可以看一下数据结构里那张链表插入一项的示意图

    pSrc->next = pPosition->next;
    pPosition->next = pSrc;
    pList->size++;
    
    return TRUE;
}

/*
 * 此函数实现根据关键字查找相应的节点.
 * KeyWord -- 关键字
 * pList -- 需要查找的链表.
 */
ListNode *findNode(char *KeyWord, List *pList)
{
    ListNode *pNode = NULL;

    if (!KeyWord || !pList)
        return NULL;

    //从链表头开始

    pNode = pList->head;

    //大循环进行查找节点

    while (pNode)
    {
        if (!strcmp(KeyWord, pNode->Name))
        {
            //找到后返回当前项的指针

            printf("Find a list node key [%s]\n", KeyWord);
            return pNode;
        }
        pNode = pNode->next;
    }
    
    return NULL;
}


/*
 * 查找指定关键字前一项节点
 * KeyWord -- 关键字
 * pList -- 需要查找的链表.
 */
ListNode *findPrev(char *KeyWord, List *pList)
{
    ListNode *pPrev = NULL;
    
    if (!KeyWord || !pList)
        return NULL;

    //从链表头开始

    pPrev = pList->head;

    //大循环进行查找节点,如果下一项存在则返回上一项

    while (pPrev->next)
    {
        if (!strcmp(KeyWord, pPrev->next->Name))
        {
            return pPrev;
        }
        pPrev = pPrev->next;
    }

    return NULL;

}

/*
 * 此函数实现根据关键字删除链表中的一个节点
 * KeyWord -- 关键字
 * pList -- 需要查找的链表.
 */
int deleteNode(char *KeyWord, List *pList)
{
    ListNode *tmpNode = NULL;
    ListNode *tmpPrev = NULL;
    
    if (!KeyWord || !pList)
        return FALSE;

    //查找指定关键节节点的前驱项

    tmpPrev = findPrev(KeyWord, pList);

    if (!tmpPrev)
    {
        //没有找到前驱则说明表头,继续查找表头

        tmpNode = findNode(KeyWord, pList);
        if (!tmpNode)
            return FALSE;
            
        //找到表头后则进行删除节点操作

        pList->head = tmpNode->next;

        tmpNode->next = NULL;
        //释放节点内存空间

        free(tmpNode);
        tmpNode = NULL;

        //更新链表大小

        pList->size--;

    }
    else
    {
        //找到了前驱,则说明是链表中间项,进行删除操作

        tmpNode = tmpPrev->next;
        tmpPrev->next = tmpNode->next;
        tmpNode->next = NULL;
        free(tmpNode);
        pList->size--;
    }

    return TRUE;
}

/*
 * 此函数实现测试一个链表是否为空
 * pList -- 需要测试的链表
 */
int isEmpty(List *pList)
{
    return pList->head == NULL;
}


/*
 * 此函数实现检查是否为链表最后一个节点
 * pNode -- 需要测试的节点
 */

int isLast(ListNode *pNode)
{
    return pNode->next == NULL;
}


int main(int argc, char **argv)
{
    ListNode *pNode = NULL;
    ListNode *pNew = NULL;
    int i;

    //初始化链表

    memset(&MyList, 0, sizeof(List));

    if (isEmpty(&MyList))
    {
        printf("This is a empty list\n");
        //return -1;

    }

    //Add new list node

    for (i=0; i<20; i++)
    {
        pNode = (ListNode *)malloc(sizeof(ListNode));

        //printf("Node size %d\n", sizeof(ListNode));


        if (pNode == NULL)
            break;

        sprintf(pNode->Name, "niejun_%d", i);
        pNode->index = i;

        //向链表里添加新节点

        addNode(&MyList, pNode);
        
    }

    pNode = NULL;

    if ((pNode = findPrev("niejun_5", &MyList)))
    {
        printf("Get the prev node index %d, name %s\n", pNode->index, pNode->Name);
    }

    //删除某一节点

    deleteNode("niejun_0", &MyList);

    //插入一个节点

    //Insert into a new node

    pNew = (ListNode *)malloc(sizeof(ListNode));
    if (pNew == NULL)
    {
        printf("Malloc error\n");
        return -1;
    }
    sprintf(pNew->Name, "kenken_520");
    pNew->index = 520;

    insertList(pNew, pNode, &MyList);
    
    //打印显示信息

    while (TRUE)
    {
        ListNode *ptrNode = NULL;

        printf("This is main thread\n");

        if (MyList.head)
            ptrNode = MyList.head;

        if (isEmpty(&MyList))
            printf("MyList is empty\n");

        while (ptrNode)
        {
            printf("Node %d, name [%s], size %d\n", ptrNode->index, ptrNode->Name, MyList.size);
            ptrNode = ptrNode->next;
        }
        
        sleep(1);
    }

    
    
    printf("List test \n");
    return 0;
}