最近参考Linux实现的通用双向链表时，因typeof并不是标准c规定的关键字，除GCC编译器外其他编译器未必支持typeof关键字，所以在使用上并不能想Linux所实现的链表哪样灵活，它要求将连接器即链表结构作为用户自定义结构体的第一个元素使用，话不多说，直接上代码，内嵌详细注释。
IList.h
1 #ifndef _I_LIST_H_2012_11_23_ 2 #define _I_LIST_H_2012_11_23_ 3 4 #ifdef __cplusplus 5 extern "C" { 6 #endif 7 8 /** \brief 双向链表连接器 9 * \details 实现用户自定义结构链表的连接器的结构定义，使用注意事项： 10 1. 务必将其嵌入到用户自定义结构体元素的顶端； 11 2. 务必使用结构类型而非其指针类型嵌入到用户自定义结构体 12 * \typedef typedef struct _IList IList,*pIList 13 */ 14 typedef struct _IList 15 { 16 struct _IList *_prev; 17 struct _IList *_next; 18 }IList, *pIList; 19 20 /** 21 \brief 遍历链表所有节点 22 \details 遍历链表所有节点，在遍历过程中，请勿执行添加、删除操作 23 24 \param[in] pList 链表对象 25 \param[out] pLink 节点 26 */ 27 #define IList_Foreach(pList, pos) \ 28 for ( \ 29 pos = pos = (pList)->_next; \ 30 pos != (pList); \ 31 pos = pos->_next \ 32 ) 33 34 /** 35 \brief 遍历链表所有节点 36 \details 安全遍历链表所有节点，在遍历过程中，可以删除节点 37 38 \param[in] pList 链表对象 39 \param[out] pLink 节点 40 */ 41 #define IList_Foreach_Salf(pList, temp, pos) \ 42 for ( \ 43 pos = (pList)->_next, temp = pos->_next; \ 44 pos != (pList); \ 45 pos = temp, temp = pos->_next\ 46 ) 47 48 /** 49 \brief 链表初始化 50 51 \param[in] pList 链表对象 52 */ 53 void IList_Init(pIList pList); 54 55 /** 56 \brief 插入新节点 57 \details 将新节点插入链表指定节点之前 58 59 \param[in] pList 链表对象 60 \param[in] pLink 指定节点 61 \param[in] pNewLink 带插入节点 62 */ 63 void IList_Insert(pIList pLink, pIList pNewLink); 64 65 /** 66 \brief 插入新节点至链表尾部 67 68 \param[in] pList 链表对象 69 \param[in] pLink 指定节点 70 \param[in] pNewLink 带插入节点 71 */ 72 void IList_Append(pIList pList, pIList pNewLink); 73 74 /** 75 \brief 插入新节点至链表尾头部 76 77 \param[in] pList 链表对象 78 \param[in] pLink 指定节点 79 \param[in] pNewLink 带插入节点 80 */ 81 void IList_Prepend(pIList pList, pIList pNewLink); 82 83 /** 84 \brief 删除指定节点 85 86 \param[in] pList 链表对象 87 \param[in] pLink 带删除的节点 88 */ 89 void IList_Remove(pIList pLink); 90 91 /** 92 \brief 获取表头节点 93 94 \param[in] pList 链表对象 95 96 \return NULL: 链表为空 97 其他: 表头节点地址 98 */ 99 pIList IList_Head(pIList pList);100 101 /**102 \brief 获取表尾节点103 104 \param[in] pList 链表对象105 106 \return NULL: 链表为空107 其他: 表尾节点地址108 */109 pIList IList_Tail(pIList pList);110 111 /**112 \brief 检测链表是否为空113 114 \param[in] pList 链表对象115 116 \return 0: 链表非空117 1: 链表为空118 */119 int IList_IsEmpty(pIList pList);120 /**121 \brief 获取链表节点数122 123 \param[in] pList 链表对象124 125 \return 链表节点数126 */127 int IList_Size(pIList pList);128 129 /**130 \brief 获取指定节点的后一节点131 132 \param[in] pList 链表对象133 \param[in] pLink 指定的节点134 135 \return NULL: 指定节点为尾节点136 其他: 指定节点后一节点地址137 */138 pIList IList_Next(pIList pList, pIList pLink);139 140 /**141 \brief 获取指定节点的前一节点142 143 \param[in] pList 链表对象144 \param[in] pLink 指定的节点145 146 \return NULL: 指定节点为头节点147 其他: 指定节点前一节点地址148 */149 pIList IList_Prev(pIList pList, pIList pLink);150 151 /**152 \brief 获取链表中第index个节点153 154 \param[in] pList 链表对象155 \param[in] index 节点序号,从1计数156 157 \return NULL: 指定序号无节点158 其他: 链表中第index所对应的节点159 */160 pIList IList_Nth(pIList pList, int index);161 162 /**163 \brief 获取链表中指定节点的序号164 165 \param[in] pList 链表对象166 \param[in] pLink 指定节点167 168 \return NULL: 指定序号无节点169 其他: 链表中第index所对应的节点170 */171 int IList_Find(pIList pList, pIList pLink);172 173 #ifdef __cplusplus174 }175 #endif176 177 #endif//_I_LIST_H_2012_11_23_ IList.c
1 #include2 #include "iList.h" 3 4 void IList_Init(pIList pList) 5 { 6 pList->_prev = pList; 7 pList->_next = pList; 8 } 9 10 void IList_Insert(pIList pLink, pIList pNewLink) 11 { 12 pNewLink->_prev = pLink->_prev; 13 pNewLink->_next = pLink; 14 pNewLink->_prev->_next = pNewLink; 15 pNewLink->_next->_prev = pNewLink; 16 } 17 18 void IList_Append(pIList pList, pIList pNewLink) 19 { 20 IList_Insert(pList, pNewLink); 21 } 22 23 void IList_Prepend(pIList pList, pIList pNewLink) 24 { 25 IList_Insert(pList->_next, pNewLink); 26 } 27 28 void IList_Remove(pIList pLink) 29 { 30 pLink->_prev->_next = pLink->_next; 31 pLink->_next->_prev = pLink->_prev; 32 } 33 34 pIList IList_Head(pIList pList) 35 { 36 return pList->_next != pList ? pList->_next : NULL; 37 } 38 39 pIList IList_Tail(pIList pList) 40 { 41 return pList->_prev != pList ? pList->_prev : NULL; 42 } 43 44 int IList_IsEmpty(pIList pList) 45 { 46 return pList->_next == pList; 47 } 48 49 int IList_Size(pIList pList) 50 { 51 int count = 0; 52 pIList temp = NULL; 53 54 if (pList->_next == pList) 55 return 0; 56 57 IList_Foreach(pList, temp) 58 { 59 count ++; 60 } 61 62 return count; 63 } 64 65 pIList IList_Next(pIList pList, pIList pLink) 66 { 67 return pLink->_next != pList ? pLink->_next : NULL; 68 } 69 70 pIList IList_Prev(pIList pList, pIList pLink) 71 { 72 return pLink->_prev != pList ? pLink->_prev : NULL; 73 } 74 75 pIList IList_Nth(pIList pList, int index) 76 { 77 pIList pLink = NULL; 78 int count = 0; 79 80 IList_Foreach(pList, pLink) 81 { 82 count ++; 83 if (count == index) 84 return pLink; 85 } 86 87 return NULL; 88 } 89 90 int IList_Find(pIList pList, pIList pLink) 91 { 92 pIList pTemp = NULL; 93 int index = 1; 94 95 pTemp = IList_Head(pList); 96 97 while ((pTemp != NULL) && (pTemp != pLink)) 98 { 99 index++;100 pTemp = IList_Next(pList, pTemp);101 }102 103 if (pTemp == NULL)104 return (-1);105 else106 return (index);107 }
IListTest.c
#include#include #include #include "iList.h"typedef struct _Student{ IList _list; int _id; char *name;}Student, *pStudent;int main(int argc, char *argv[]){ int i = 0; int num = 10; int count = 0; pStudent temp= NULL; pIList list, link; if (argc > 1) num = atoi(argv[1]); list = (IList *)malloc(sizeof(IList)); if (!list) { printf("Error in malloc.\n"); return -1; } memset(list, 0, sizeof(IList)); IList_Init(list); for (i = 0; i < num; i ++) { temp = malloc(sizeof(Student)); if (!temp) return -1; memset(temp, 0, sizeof(Student)); temp->_id = i + 1; IList_Append(list, &temp->_list); //IList_Prepend(list, &temp->_list); } IList_Foreach(list, link) { temp = (pStudent)link; printf("%d\t", temp->_id); } printf("\n"); printf("Input the num(1 ~ %d) that you want to:\n", IList_Size(list)); scanf("%d", &count); link = IList_Nth(list, count); printf("Num %d id: %d\n", count, ((pStudent)link)->_id); printf("Id %d num: %d\n", ((pStudent)link)->_id, IList_Find(list, link)); printf("List count: %d\n", IList_Size(list)); /*for (link = IList_Head(list);!IList_IsEmpty(list);) { pIList tLink = link; link = IList_Next(list, link); IList_Remove(tLink); free(tLink); }*/ do { pIList n, pos; IList_Foreach_Salf(list, n, pos) { IList_Remove(pos); free(pos); } } while (0); printf("List count: %d\n", IList_Size(list)); free(list); return 0;}