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