【@.1 简介】
数据结构与内存管理是不可分割的，特别是在C语言中，对于指针的处理必须非常小心。通常我们在用动态内存分配时会调用malloc()函数为指针分配内存，但是在嵌入式编程时我并不喜欢使用malloc系列函数，宁可自己建立一个数组，需要使用时从数组里面分配空间。我曾经的博客《uCOS-II中的内存管理–C语言构建完整的微型动态内存管理机制》一文中介绍了在uCOS中的动态内存管理机制，那种方法的确十分好用，而且实际上我们也经常这样用。现在考虑自己构建一个简单的内存管理，主要用于对链表进行内存分配。下面循序渐进地介绍了几种方法来实现设计双向链表时的内存分配。
【方法一：简单的数组】
最简单的方法就是在全局声明一个数组，将所有链表所需涉及到的内存分配全部放在这里面。这种方法并没有深化到内存管理的地步，没有内存回收、内存分配的完整机制，仅仅是简单的将双向链表与数组链接在一起，可以实现比较初级的功能.
/************************************************************/#include <stdio.h>#include <stdlib.h>void memclr(unsigned char* pdest, int size){while(size>0){*pdest++=(unsigned char)0;size–;}}#define MAX_SIZE 10typedef struct {void* previous;void* next;int value;}A_Type;static A_Type array[MAX_SIZE];void Init_Q(void* start, int size){A_Type* ptr1, *ptr2;memclr((unsigned char*)start,sizeof(A_Type)*size);ptr1 = (A_Type*)start;ptr2 = ptr1+1;while(size>1){ptr1->next = ptr2;ptr2->previous = ptr1;ptr1++;ptr2++;size–;}}int main(void) {A_Type *ptr;Init_Q(array,MAX_SIZE);ptr = &array[0];while(ptr != (void*)0){printf(“%d, “,ptr->value);ptr=(A_Type*)ptr->next;}ptr = &array[5];printf(“\n”);while(ptr != (void*)0){printf(“%d, “,ptr->value);ptr = (A_Type*)ptr->previous;}return EXIT_SUCCESS;}/************************************************************/
【方法二：使用malloc动态分配内存】
这种方法是很多人比较喜欢用的。虽然我并不喜欢用它，但是还是写了些这种方法。最大的好处就是，香港服务器，没有了全局变量，可以让程序变得很干净。所有链表中需要用到的内存都是动态分配申请的。
/************************************************************/#include <stdio.h>#include <stdlib.h>typedef struct{void * previous;void * next;int value;}List_Type;void MemClr(unsigned char * pdest, int size){while(size>0){*pdest++ = (unsigned char)0;size–;}}void Add_Node(List_Type * preNode, int newValue){List_Type * newNode = (List_Type*)malloc(sizeof(List_Type));List_Type * nextNode ;if(preNode == (void*)0)return ;nextNode = (List_Type*)preNode->next;MemClr((unsigned char*)newNode, sizeof(List_Type));newNode->value = newValue;preNode->next = newNode;newNode->previous = preNode;newNode->next = nextNode;if(nextNode != (void*)0)//if Not the end of the listnextNode->previous = newNode;//free(newNode); NEVER, EVER free this pointer!!!}List_Type * CreateList_Add(int nodeNum){List_Type * entry = (List_Type*)malloc(sizeof(List_Type));List_Type * ptr1;ptr1 = entry;MemClr((unsigned char*)entry,sizeof(List_Type));while(nodeNum>1){Add_Node(ptr1, 0);ptr1 = (List_Type*)ptr1->next;nodeNum–;}return entry;}List_Type * FindIndex_Front(List_Type *entry, int index_f){List_Type * ptr = entry;while(index_f>0){ptr = (List_Type* )ptr->next;if(ptr == (void*)0)return (void*)0; //index_f overflowindex_f–;}return ptr;}void Print_ToEnd(List_Type * ptr){while(ptr != (void*)0){printf(“%d, “,ptr->value);ptr = (List_Type*)ptr->next;}}void Print_ToStart(List_Type * ptr){while(ptr != (void*)0){printf(“%d, “, ptr->value);ptr = (List_Type*)ptr->previous;}}int main(void) {List_Type *pList = CreateList_Add(10);List_Type *ptr = pList;Print_ToEnd(ptr);printf(“\n”);ptr = FindIndex_Front(pList, 4);Print_ToStart(ptr);printf(“\n”);ptr = FindIndex_Front(pList, 7);Add_Node(ptr,3);Print_ToEnd(ptr);printf(“\n”);return EXIT_SUCCESS;}/************************************************************/【方法三：自己搭建一个内存管理机制进行“动态”分配】最后一种也是我比较喜欢的一种方法，即，使用内存管理的思想对链表进行插入，删除操作。这样的最大好处就是，所有使用的内存都是程序中自己动手建立的，方便自己估计程序大小.#include <stdio.h>#include <stdlib.h>#define MAX_PARTIONS 100utypedef struct{void * previous;void * next;int value;}List_Type;List_TypeListPartion[MAX_PARTIONS];List_Type*pFreeList;unsigned intFreeNum;void MemClr(unsigned char * pdest, int size){while(size>0){*pdest++ = (unsigned char)0;size–;}}List_Type * ListNode_Malloc(){List_Type* ptr;if(pFreeList != (List_Type *)0){ptr = pFreeList;//MemClr((unsigned char*)ptr,sizeof(ptr)); //You Can NOT do clear here, or will lost Free list informationFreeNum–;pFreeList=(List_Type*)pFreeList->next; //To the next node in ListPartion[MAX_PARTIONS]ptr->next = (void*)0;pFreeList->previous = (void*)0;}elseptr = (List_Type *)0;return ptr;}void ListNode_Free(List_Type * node){if(node != (List_Type*)0){FreeNum++;node->next = pFreeList;node->previous = (void*)0;pFreeList->previous = node;pFreeList = (List_Type*)pFreeList->previous;}}void ListInit(){List_Type *ptr1, *ptr2;int i;MemClr((unsigned char*)&ListPartion[0], sizeof(ListPartion));ptr1 = &ListPartion[0];ptr2 = &ListPartion[1];for (i=0;i<MAX_PARTIONS-1;i++){ptr1->next = ptr2;ptr2->previous = ptr1;ptr1++;ptr2++;}pFreeList = &ListPartion[0];FreeNum = MAX_PARTIONS;// pListPar->pList= &ListPartion[0];// pListPar->pFreeNode = pListPar->pList;printf(“ListInit Success!\n”);}void Add_Node(List_Type * preNode, int newValue){List_Type * newNode ;List_Type * nextNode ;if(preNode == (void*)0)return ;newNode = ListNode_Malloc();nextNode = (List_Type*)preNode ->next;MemClr((unsigned char*)newNode, sizeof(List_Type)); //Explicit clear memorynewNode->value = newValue;preNode->next = newNode;newNode->previous = preNode;newNode->next = nextNode;if(nextNode != (void*)0)//if Not the end of the listnextNode->previous = newNode;}void Delete_Node(List_Type *pNode){List_Type * preNode;List_Type * nextNode;if(pNode == (List_Type*)0)return;preNode = (List_Type*)pNode->previous;nextNode = (List_Type*)pNode -> next;if(preNode != (List_Type*)0){preNode->next = nextNode;}if(nextNode != (List_Type*)0){nextNode->previous = preNode;}ListNode_Free(pNode);}List_Type * CreateList_Add(int nodeNum){List_Type * entry;List_Type * ptr1;entry = ListNode_Malloc();ptr1 = entry;MemClr((unsigned char*)entry,sizeof(List_Type));while(nodeNum>1){Add_Node(ptr1, 1);if(ptr1 == (List_Type*)0) //The List Partion is full{entry = (List_Type*)0; //Create fail, will return a NULL pointerbreak;}ptr1 = (List_Type*)ptr1->next;nodeNum–;}return entry;}List_Type * FindIndex_Front(List_Type *entry, int index_f){List_Type * ptr = entry;while(index_f>0){ptr = (List_Type* )ptr->next;if(ptr == (void*)0)return (void*)0; //index_f overflowindex_f–;}return ptr;}void Print_ToEnd(List_Type * ptr){while(ptr != (void*)0){printf(“%d, “,ptr->value);ptr = (List_Type*)ptr->next;}}void Print_ToStart(List_Type * ptr){while(ptr != (void*)0){printf(“%d, “, ptr->value);ptr = (List_Type*)ptr->previous;}}int main(void) {List_Type *pList;List_Type *ptr;//initialte List PartionListInit();pList = CreateList_Add(10);ptr = pList;Print_ToEnd(ptr);printf(“\n”);ptr = FindIndex_Front(pList, 4);Print_ToStart(ptr);printf(“\n”);ptr = FindIndex_Front(pList, 7);Add_Node(ptr,3);Print_ToEnd(pList);printf(“\n”);printf(“FreeNumber: %d\n”,FreeNum);ptr = FindIndex_Front(pList, 0);pList++; //If you want delete the first note, you must move the pList to the next one.Delete_Node(ptr);Print_ToEnd(pList);printf(“\n”);printf(“FreeNumber: %d\n”,FreeNum);ptr = FindIndex_Front(pList,7);Delete_Node(ptr);Print_ToEnd(pList);printf(“\n”);printf(“FreeNumber: %d\n”,FreeNum);ptr = FindIndex_Front(pList,8);Add_Node(ptr,89);Print_ToEnd(pList);printf(“\n”);printf(“FreeNumber: %d\n”,FreeNum);return EXIT_SUCCESS;}/************************************************************/『 不可能 』只存在於蠢人的字典里
