[数据结构]循环双链表 - 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

CDList.h

程序代码：

#ifndef CDLIST_H
#define CDLIST_H

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

typedef struct CDListNode_struct
{
    int m_ID;
    Person_t * m_Person;
    struct CDListNode_struct * m_Prev;
    struct CDListNode_struct * m_Next;
} CDListNode_t;

typedef struct
{
    CDListNode_t * m_Head;
    size_t m_Count;
} CDList_t;

bool CDList_Init(CDList_t * list);
bool CDList_Insert(CDList_t * list, int index, const Person_t * newPerson);
bool CDList_Append(CDList_t * list, const Person_t * newPerson);
bool CDList_Delete(CDList_t * list, int index);
bool CDList_Update(CDList_t * list, int index, const Person_t * newPerson);
void CDList_Reverse(CDList_t * list);
void CDList_Empty(CDList_t * list);
bool CDList_Sort(CDList_t * list);
int CDList_IndexOf(const CDList_t * list, const char * name);
Person_t * CDList_GetData(const CDList_t * list, int index);

void CDList_Print(const CDList_t * list);
void CDList_PrintReversely(const CDList_t * list);

static inline size_t CDList_Count(const CDList_t * list)
{
    return list->m_Count;
}

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

#endif

CDList.c

程序代码：

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

static int CurrentMaxID = 1;

static void SelectionSort(Person_t array[], int firstIndex, int lastIndex)
{
    Person_t temp;
    int minIndex = -1;

    for(int i = firstIndex; i < lastIndex; i++)
    {
        int j = -1;

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

        if(minIndex != i)
        {
            temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}

bool CDList_Init(CDList_t * list)
{
    CDListNode_t * node = NULL;

    if(!list)
        return false;

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

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

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

    return true;
}

bool CDList_Insert(CDList_t * list, int index, const Person_t * newPerson)
{
    CDListNode_t * node = NULL;
    Person_t * person = NULL;
    CDListNode_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(CDListNode_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->m_Prev = node;
    p->m_Next = node;
   

    list->m_Count++;
   

    return true;
}

bool CDList_Append(CDList_t * list, const Person_t * newPerson)
{
    return CDList_Insert(list, list->m_Count, newPerson);
}

bool CDList_Delete(CDList_t * list, int index)
{
    CDListNode_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;
    p->m_Next->m_Prev = p->m_Prev;
   

    list->m_Count--;

    return true;
}

bool CDList_Update(CDList_t * list, int index, const Person_t * newPerson)
{
    CDListNode_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 CDList_Reverse(CDList_t * list)
{
    CDListNode_t * p = NULL;
    CDListNode_t * q = NULL;
    CDListNode_t * r = NULL;

    if(!list)
        return;
   

    if(list->m_Count < 2)
        return;
   

    p = list->m_Head;
    q = p->m_Next;
    while(q != list->m_Head)
    {
        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 CDList_Empty(CDList_t * list)
{
    CDListNode_t * p = NULL;
    CDListNode_t * q = NULL;

    if(!list)
        return;
   

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

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

bool CDList_Sort(CDList_t * list)
{
    Person_t * array = NULL;
    CDListNode_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[]进行排序
    SelectionSort(array, 0, count - 1);

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

    return true;
}

int CDList_IndexOf(const CDList_t * list, const char * name)
{
    CDListNode_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 * CDList_GetData(const CDList_t * list, int index)
{
    CDListNode_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 CDList_Print(const CDList_t * list)
{
    CDListNode_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");
}

void CDList_PrintReversely(const CDList_t * list)
{
    CDListNode_t * p = NULL;

    if(!list)
        return;
   

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

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