[数据结构]双链表 - C语言论坛

楼主

问题点数：0 回复次数：0

[数据结构]双链表

Person.h

程序代码：

#ifndef PERSON_H
#define PERSON_H

typedef enum Sex_enum
{
    Male,
    Female
} Sex_t;

typedef struct Person_struct
{
    char m_Name[32];
    Sex_t m_Sex;
    int m_Age;
} Person_t;

static inline void Person_Print(const Person_t * person)
{
    if(!person)
    {
        printf("[ ]");
    }
    else
    {
        printf("[ Name: %s, Sex: %s, Age: %d ]",
            person->m_Name,
            person->m_Sex == Male ? "Male" : "Female",
            person->m_Age);
    }
}

#endif

DList.h

程序代码：

#ifndef DLIST_H
#define DLIST_H

#include <stddef.h>
#include "Person.h"

typedef struct DListNode_struct
{
    int m_ID;
    Person_t * m_Person;
    struct DListNode_struct * m_Prev;
    struct DListNode_struct * m_Next;
} DListNode_t;

typedef struct
{
    DListNode_t * m_Head;
    DListNode_t * m_Rear;
    size_t m_Count;
} DList_t;

bool DList_Init(DList_t * list);
bool DList_Insert(DList_t * list, int index, const Person_t * newPerson);
bool DList_Append(DList_t * list, const Person_t * newPerson);
bool DList_Delete(DList_t * list, int index);
bool DList_Update(DList_t * list, int index, const Person_t * newPerson);
void DList_Reverse(DList_t * list);
void DList_Empty(DList_t * list);
bool DList_Sort(DList_t * list);
int DList_IndexOf(const DList_t * list, const char * name);
Person_t * DList_GetData(const DList_t * list, int index);

void DList_Print(const DList_t * list);

static inline size_t DList_Count(const DList_t * list)
{
    return list->m_Count;
}

static inline bool DList_IsEmpty(const DList_t * list)
{
    return list->m_Count == 0;
}

#endif

DList.c

程序代码：

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "DList.h"

static int CurrentMaxID = 1;

static void BubbleSort(Person_t array[], int firstIndex, int lastIndex)
{
    Person_t temp;

    for(int i = firstIndex; i < lastIndex; i++)
    {
        for(int j = firstIndex; j < lastIndex - i; j++)
        {
            if(array[j].m_Age > array[j + 1].m_Age)
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

bool DList_Init(DList_t * list)
{
    DListNode_t * node = NULL;

    if(!list)
        return false;

    node = malloc(sizeof(DListNode_t));
    if(!node)
        return false;
   

    node->m_ID = -1;
    node->m_Prev = NULL;
    node->m_Next = NULL;
    node->m_Person = NULL;

    list->m_Head = node;
    list->m_Rear = node;
    list->m_Count = 0;

    return true;
}

bool DList_Insert(DList_t * list, int index, const Person_t * newPerson)
{
    DListNode_t * node = NULL;
    Person_t * person = NULL;
    DListNode_t * p = NULL;

    if(!list || !newPerson)
        return false;
   

    if(index < 0)
        index = 0;
    if(index > list->m_Count)
        index = list->m_Count;
   

    node = malloc(sizeof(DListNode_t));
    if(!node)
        return false;
   

    person = malloc(sizeof(Person_t));
    if(!person)
    {
        free(node);
        return false;
    }
    *person = *newPerson;

    p = list->m_Head;
    for(int i = 0; i < index; i++, p = p->m_Next)
        ;

    node->m_ID = CurrentMaxID++;
    node->m_Person = person;
    node->m_Prev = p;
    node->m_Next = p->m_Next;
    p->m_Next = node;

    if(node->m_Next)
        node->m_Next->m_Prev = node;
    else
        list->m_Rear = node;
   

    list->m_Count++;
   

    return true;
}

bool DList_Append(DList_t * list, const Person_t * newPerson)
{
    return DList_Insert(list, list->m_Count, newPerson);
}

bool DList_Delete(DList_t * list, int index)
{
    DListNode_t * p = NULL;

    if(!list)
        return false;
    if(index < 0 || index >= list->m_Count)
        return false;
    if(list->m_Count == 0)
        return false;

    p = list->m_Head->m_Next;
    for(int i = 0; i < index; i++, p = p->m_Next)
        ;
   

    p->m_Prev->m_Next = p->m_Next;
    if(p->m_Next)
        p->m_Next->m_Prev = p->m_Prev;
    else
        list->m_Rear = p->m_Prev;
   

    list->m_Count--;

    return true;
}

bool DList_Update(DList_t * list, int index, const Person_t * newPerson)
{
    DListNode_t * p = NULL;

    if(!list || !newPerson)
        return false;
    if(index < 0 || index >= list->m_Count)
        return false;
   

    p = list->m_Head->m_Next;
    for(int i = 0; i < index; i++, p = p->m_Next)
        ;
   

    *p->m_Person = *newPerson;
    return true;
}

void DList_Reverse(DList_t * list)
{
    DListNode_t * p = NULL;
    DListNode_t * q = NULL;
    DListNode_t * r = NULL;

    if(!list)
        return;
   

    if(list->m_Count < 2)
        return;
   

    p = list->m_Head->m_Next;
    q = p->m_Next;
    p->m_Next = NULL;
    list->m_Rear = p;
    while(q)
    {
        r = q->m_Next;
       

        q->m_Next = p;
        q->m_Prev = r;
        p->m_Prev = q;

        p = q;
        q = r;
    }
    list->m_Head->m_Next = p;
}

void DList_Empty(DList_t * list)
{
    DListNode_t * p = NULL;
    DListNode_t * q = NULL;

    if(!list)
        return;
   

    p = list->m_Head->m_Next;
    while(p)
    {
        q = p->m_Next;
        free(p);
        p = q;
    }

    list->m_Head->m_Next = NULL;
    list->m_Rear = list->m_Head;
    list->m_Count = 0;
}

bool DList_Sort(DList_t * list)
{
    Person_t * array = NULL;
    DListNode_t * p = NULL;
    size_t count = 0;

    count = list->m_Count;
    array = malloc(sizeof(Person_t) * count);
    if(!array)
        return false;
   

    p = list->m_Head->m_Next;
    for(int i = 0; i < count; i++, p = p->m_Next)
        array[i] = *p->m_Person;
   

    // 下面用冒泡排序法对array[]进行排序
    BubbleSort(array, 0, count - 1);

    DList_Empty(list);
    for(int i = 0; i < count; i++)
    {
        DList_Insert(list, list->m_Count, &array[i]);
    }

    return true;
}

int DList_IndexOf(const DList_t * list, const char * name)
{
    DListNode_t * p = NULL;
    int i = 0;
    size_t nameLength = 0;

    if(!list)
        return -1;
   

    if(list->m_Count == 0)
        return -1;
   

    p = list->m_Head->m_Next;
    nameLength = strlen(name);
    for(i = 0; i < list->m_Count; i++, p = p->m_Next)
    {
        size_t currentNameLength = 0;
        size_t maxNameLength = 0;
       

        currentNameLength = strlen(p->m_Person->m_Name);
        maxNameLength = nameLength >= currentNameLength ? nameLength : currentNameLength;

        if(strncmp(name, p->m_Person->m_Name, maxNameLength) == 0)
            break;
    }

    return i != list->m_Count ? i : -1;
}

Person_t * DList_GetData(const DList_t * list, int index)
{
    DListNode_t * p = NULL;

    if(!list)
        return NULL;
   

    if(index < 0 || index >= list->m_Count)
        return NULL;
   

    p = list->m_Head->m_Next;
    for(int i = 0; i < index; i++, p = p->m_Next)
        ;
   

    return p->m_Person;
}

void DList_Print(const DList_t * list)
{
    DListNode_t * p = NULL;

    if(!list)
        return;
   

    p = list->m_Head->m_Next;
    printf("{\n");
    for(int i = 0; i < list->m_Count; i++, p = p->m_Next)
    {
        printf("  [ ID: %d, Person: ", p->m_ID);
        Person_Print(p->m_Person);
        printf(" ]\n");
    }
    printf("}\n");
}

搜索更多相关主题的帖子: int　list　index　return　NULL　