C語言實現通用數據結構之通用鏈表
本文實例為大傢分享瞭c語言實現通用數據結構之通用鏈表的具體代碼,供大傢參考,具體內容如下
忽然想起來,大概在兩年之前學習C語言的時候,曾經用C語言寫過一些通用的數據結構。主要也就實現瞭鏈表、隊列、椎、HashSet,還有HashMap。當時隻是知道標準的C語言中沒有這方面的類庫,後來才知道有很多第三方的類似這樣的類庫。廢話不多說,先把代碼粘過來。
下面實現的是通用鏈表,註意鏈表中隻存儲瞭指針,沒有儲存實際的數據。
頭文件
/************************* *** File myList.h **************************/ #ifndef MYLIST_H_INCLUDED #define MYLIST_H_INCLUDED #include <stdio.h> typedef struct myNode { void * data; struct myNode *next; } MyNode; typedef struct myList { MyNode * first; MyNode * last; int count; int (*equal)(void * a, void * b); } MyList; typedef struct myListIterator { MyNode * p; int count; int allSize; } MyListIterator; //創建鏈表 MyList * createMyList(); //創建鏈表,帶有相等參數,用於查找 MyList * createMySearchList(int(*equal)(void * a, void * b)); //釋放鏈表 void freeMyList(MyList * list); //插入在尾部 void myListInsertDataAtLast(MyList* const list, void* const data); //插入在首部 void myListInsertDataAtFirst(MyList * const list, void* const data); //插入 void myListInsertDataAt(MyList * const list, void* const data, int index); //刪除在尾部 void* myListRemoveDataAtLast(MyList* const list); //刪除在首部 void* myListRemoveDataAtFirst(MyList * const list); //刪除 void* myListRemoveDataAt(MyList* const list, int index); //刪除對象,返回是否刪除成功 int myListRemoveDataObject(MyList* const list, void * data); //長度 int myListGetSize(const MyList * const list); //打印 void myListOutput(const MyList * const list, void(*pt)(const void * const)); //取得數據 void* myListGetDataAt(const MyList * const list, int index); //取得第一個數據 void* myListGetDataAtFirst(const MyList * const list); //取得最後一個數據 void* myListGetDataAtLast(const MyList * const list); //查找某個數據的位置,如果equal方法為空,比較地址,否則調用equal方法 //如果不存在返回-1,如果存在,返回出現的第一個位置 int myListFindDataIndex(const MyList * const list, void * data); //創建遍歷器 MyListIterator* createMyListIterator(const MyList * const list); //釋放遍歷器 void freeMyListIterator(MyListIterator* iterator); //遍歷器是否有下一個元素 int myListIteratorHasNext(const MyListIterator* const iterator); //返回遍歷器的下一個元素 void * myListIteratorNext(MyListIterator* const iterator); #endif // MYLIST_H_INCLUDED
源文件
/************************* *** File myList.c **************************/ #include "myList.h" #include <stdlib.h> //創建鏈表 MyList * createMyList() { MyList * re = (MyList *) malloc(sizeof(MyList)); re->count = 0; re->first = NULL; re->last = NULL; re->equal = NULL; return re; } //釋放鏈表 void freeMyList(MyList * list) { MyNode * p; while (list->first) { p = list->first->next; free(list->first); list->first = p; } free(list); } //插入在尾部 void myListInsertDataAtLast(MyList * const list, void* const data) { MyNode * node = (MyNode *) malloc(sizeof(MyNode)); node->data = data; node->next = NULL; if (list->count) { list->last->next = node; list->last = node; } else { list->first = node; list->last = node; } (list->count)++; } //插入在首部 void myListInsertDataAtFirst(MyList * const list, void* const data) { MyNode * node = (MyNode *) malloc(sizeof(MyNode)); node->data = data; node->next = NULL; if (list->count) { node->next = list->first; list->first = node; } else { list->first = node; list->last = node; } (list->count)++; } //長度 int myListGetSize(const MyList * const list) { return list->count; } //打印 void myListOutput(const MyList * const list, void(*pt)(const void * const)) { MyNode * p = list->first; while (p) { (*pt)(p->data); p = p->next; } } //刪除在尾部 void* myListRemoveDataAtLast(MyList* const list) { if (list->count == 1) { return myListRemoveDataAtFirst(list); } MyNode * p = list->first; while (p->next != list->last) { p = p->next; } void *re = list->last->data; free(list->last); p->next = NULL; list->last = p; (list->count)--; return re; } //刪除在首部 void* myListRemoveDataAtFirst(MyList * const list) { MyNode *p = list->first; list->first = p->next; void * re = p->data; free(p); (list->count)--; if (list->count == 0) { list->last = NULL; } return re; } //插入 void myListInsertDataAt(MyList * const list, void* const data, int index) { if (index == 0) { myListInsertDataAtFirst(list, data); return; } if (index == list->count) { myListInsertDataAtLast(list, data); return; } MyNode * node = (MyNode *) malloc(sizeof(MyNode)); node->data = data; node->next = NULL; MyNode * p = list->first; for (int i = 0; i < index - 1; i++) { p = p->next; } node->next = p->next; p->next = node; (list->count)++; } //刪除 void* myListRemoveDataAt(MyList* const list, int index) { if (index == 0) { return myListRemoveDataAtFirst(list); } if (index == list->count - 1) { return myListRemoveDataAtLast(list); } MyNode * p = list->first; for (int i = 0; i < index - 1; i++) { p = p->next; } MyNode *tp = p->next; p->next = p->next->next; void * re = tp->data; free(tp); (list->count)--; return re; } //取得數據 void* myListGetDataAt(const MyList * const list, int index) { if (index == list->count - 1) { return myListGetDataAtLast(list); } MyNode * p = list->first; for (int i = 0; i < index; i++) { p = p->next; } return p->data; } //取得第一個數據 void* myListGetDataAtFirst(const MyList * const list) { return list->first->data; } //取得最後一個數據 void* myListGetDataAtLast(const MyList * const list) { return list->last->data; } //查找某個數據的位置,如果equal方法為空,比較地址,否則調用equal方法 //如果不存在返回-1,如果存在,返回出現的第一個位置 int myListFindDataIndex(const MyList * const list, void * data) { MyNode * p = list->first; int re = 0; if (list->equal) { while (p) { if (p->data == data || (*(list->equal))(p->data, data)) { return re; } re++; p = p->next; } } else { while (p) { if (p->data == data) { return re; } re++; p = p->next; } } return -1; } //創建鏈表,帶有相等參數,用於查找 MyList * createMySearchList(int(*equal)(void * a, void * b)) { MyList * re = createMyList(); re->equal = equal; return re; } //創建遍歷器 MyListIterator* createMyListIterator(const MyList * const list) { MyListIterator * re = (MyListIterator *) malloc(sizeof(MyListIterator)); re->p = list->first; re->allSize = list->count; re->count = 0; return re; } //釋放遍歷器 void freeMyListIterator(MyListIterator* iterator) { free(iterator); } //遍歷器是否有下一個元素 int myListIteratorHasNext(const MyListIterator* const iterator) { return iterator->count < iterator->allSize; } //返回遍歷器的下一個元素 void * myListIteratorNext(MyListIterator* const iterator) { void * re = iterator->p->data; iterator->p = iterator->p->next; (iterator->count)++; return re; } //刪除對象,返回是否刪除成功 int myListRemoveDataObject(MyList* const list, void * data) { MyListIterator * it = createMyListIterator(list); int a = 0; while (myListIteratorHasNext(it)) { void * ld = myListIteratorNext(it); if (data == ld || (list->equal != NULL && (*(list->equal))(ld, data))) { a = 1; break; } } if (a) { myListRemoveDataAt(list, it->count - 1); } return a; }
測試文件
/************************* *** File main.c *** test for MyList **************************/ #include <stdio.h> #include <stdlib.h> #include "myList.h" typedef struct a { int i; char c; } A; void ppt(const void* const p) { A * pp= p; printf("%d(%c) ", pp->i, pp->c); } int main() { const int S =10; //創建並初始化數據 A * data= malloc(sizeof(A)*S); for (int i=0; i< S; i++) { data[i].i=i; data[i].c=(char)('A'+0); } //創建鏈表 MyList * list= createMyList(); //測試三種插入方法 myListInsertDataAtLast( list, &data[0]); myListInsertDataAtFirst( list, &data[4]); myListInsertDataAt(list, &data[1], 1 ); //測試查找 int index = myListFindDataIndex(list, &data[2]); printf("%d\n", index); index = myListFindDataIndex(list, &data[4]); printf("%d\n", index); //輸出 myListOutput(list, ppt ); puts(""); //測試使用迭代器輸出 MyListIterator * it = createMyListIterator(list); while(myListIteratorHasNext(it)) { A * pp = myListIteratorNext(it); printf("%d[%c] ", pp->i, pp->c); } puts(""); //釋放迭代器 freeMyListIterator(it); //釋放鏈表 freeMyList(list); //釋放數據 free(data); return 0; }
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。