带头结点的单链表实现
LinkList.h
1 /********************************************************************* 2 *: 3 *: Author: dspeeding 4 *: Copyright (c) 2013, dspeeding 5 *: 6 *: Created at: 2013.08.06 7 *: Last modified: 2013.08.06 8 *: 9 *: Introduction: 线性表链式实现 10 *： 11 *: 注：ElemType类型 不能进行深拷贝，请留意 12 *: 如使用 TraverseList 函数 则需要自己实现Visit函数 13 *: 如使用 SortList 函数 则需要自己实现Compare函数 14 *: SortList 使用简单冒泡排序算法实现 15 *: 16 *:*********************************************************************/ 17 #include18 #include 19 #include 20 21 //定义数据类型为int型 22 typedef int ElemType; 23 24 25 typedef struct LNode{ 26 ElemType data; //数据 27 struct LNode *next; //下一指针 28 }LNode; 29 30 typedef LNode* LinkList; 31 typedef LinkList* PLinkList; 32 33 //定义数据类型的打印函数 34 typedef void (*Visit)(ElemType*); 35 36 //定义数据类型的比较函数 37 typedef int (*Compare)(ElemType*, ElemType*); 38 39 /**************************************** 40 Purpose : 初始化线性表 41 Input : L -- 线性表指针 42 Return : 0 --OK 43 -1 --FAIL 44 *****************************************/ 45 int InitList(PLinkList L); 46 47 48 /**************************************** 49 Purpose : 清空链表 50 Input : L -- 线性表指针 51 Return : None 52 *****************************************/ 53 void ClearList(PLinkList L); 54 55 /**************************************** 56 Purpose : 线性表长度 57 Input : L -- 线性表指针 58 Return : 线性表长度 如果是-1，则表示出错 59 *****************************************/ 60 int ListLength(PLinkList L); 61 62 /**************************************** 63 Purpose : 取链表中第nPos个元素 64 Input : L -- 线性表指针 65 nPos -- 位置 66 val -- 要取到的元素 67 Return : 0 --OK 68 -1 --FAIL 69 *****************************************/ 70 int GetElem(PLinkList L, int nPos, ElemType *val); 71 72 /**************************************** 73 Purpose : 在线性表中第nPos个位置插入新元素 74 Input : L -- 线性表指针 75 nPos -- 位置[1,ListLength(L)+1] 76 val -- 要插入的元素 77 Return : 0 --OK 78 -1 --FAIL 79 *****************************************/ 80 int InsertList(PLinkList L, int nPos, ElemType *val); 81 82 /**************************************** 83 Purpose : 在线性表中第nPos个位置删除元素 84 Input : L -- 线性表指针 85 nPos -- 位置[1,ListLength(L)] 86 val -- 数据 87 Return : 0 --OK 88 -1 --FAIL 89 *****************************************/ 90 int DeleteList(PLinkList L, int nPos, ElemType *val); 91 92 /**************************************** 93 Purpose : 返回线性表中第一个与e相等的数据元素的位序 94 Input : L -- 线性表指针 95 val -- 数据 96 compare -- 比较函数的函数指针 97 Return : 索引值，如果没有找到则返回-1 98 *****************************************/ 99 int LocateElem(PLinkList L, ElemType *val, Compare compare);100 101 102 /****************************************103 Purpose : 遍历输出线性表中每个元素104 Input : L -- 线性表指针105 visit -- 遍历函数指针106 Return : None107 *****************************************/108 void TraverseList(PLinkList L, Visit visit);109 110 /****************************************111 Purpose : 更新第nPos个位置元素112 Input : L -- 线性表指针113 nPos -- 元素的位置 [1, ListLength[L]]114 data -- 要更新的元素115 Return : 0 --OK116 -1 --FAIL117 *****************************************/118 int UpdateList(PLinkList L, int nPos, ElemType* val);119 120 121 /****************************************122 Purpose : 对线性表进行排序123 Input : L -- 线性表指针124 compare -- 比较函数125 Return : 0 --OK126 -1 --FAIL127 *****************************************/128 int SortList(PLinkList L, Compare compare);129 130 /****************************************131 Purpose : 对线性表进行逆置132 Input : L -- 线性表指针133 compare -- 比较函数134 Return : 0 --OK135 -1 --FAIL136 *****************************************/137 int ReverseList(PLinkList L);
LinkList.c
1 #include "LinkList.h" 2 3 4 /**************************************** 5 Purpose : 初始化线性表 6 Input : L -- 线性表指针 7 Return : 0 --OK 8 -1 --FAIL 9 *****************************************/ 10 int InitList(PLinkList L) 11 { 12 //带头结点的单链表 13 *L = (LinkList)malloc(sizeof(LNode)); 14 if(!*L) 15 { 16 return -1; 17 } 18 (*L)->next = NULL; 19 return 0; 20 } 21 22 /**************************************** 23 Purpose : 清空链表 24 Input : L -- 线性表指针 25 Return : None 26 *****************************************/ 27 void ClearList(PLinkList L) 28 { 29 LinkList p = *L; 30 while((*L)->next) 31 { 32 p=p->next; 33 free(*L); 34 *L = p; 35 } 36 (*L)->next = NULL; 37 } 38 39 /**************************************** 40 Purpose : 线性表长度 41 Input : L -- 线性表指针 42 Return : 线性表长度 如果是-1，则表示出错 43 *****************************************/ 44 int ListLength(PLinkList L) 45 { 46 LinkList p = NULL; 47 int nLen = 0; 48 if(*L == NULL) 49 { 50 return -1; 51 } 52 p = (*L)->next; 53 while(p) 54 { 55 p = p->next; 56 nLen++; 57 } 58 return nLen; 59 } 60 61 /**************************************** 62 Purpose : 取链表中第nPos个元素 63 Input : L -- 线性表指针 64 nPos -- 位置 65 val -- 要取到的元素 66 Return : 0 --OK 67 -1 --FAIL 68 *****************************************/ 69 int GetElem(PLinkList L, int nPos, ElemType *val) 70 { 71 LinkList p = *L; 72 int i = 0; 73 if(nPos > ListLength(L) || nPos < 0) 74 { 75 return -1; 76 } 77 while(i < nPos && p) 78 { 79 p = p->next; 80 i++; 81 } 82 memcpy(val, &p->data, sizeof(ElemType)); 83 return 0; 84 } 85 86 /**************************************** 87 Purpose : 在线性表中第nPos个位置插入新元素 88 Input : L -- 线性表指针 89 nPos -- 位置 [1,ListLength(L)+1] 90 val -- 要插入的元素 91 Return : 0 --OK 92 -1 --FAIL 93 *****************************************/ 94 int InsertList(PLinkList L, int nPos, ElemType *val) 95 { 96 LinkList p = *L; 97 LinkList q = NULL; 98 int i = 0; 99 int nLen = ListLength(L);100 if(nPos < 1|| nPos > nLen+1)101 {102 return -1;103 }104 q = (LinkList)malloc(sizeof(LNode));105 if(q == NULL)106 {107 return -1;108 }109 while(i < nPos - 1)110 {111 p = p->next;112 i++;113 }114 115 memcpy(&q->data, val, sizeof(ElemType));116 q->next = p->next;117 p->next = q;118 return 0;119 }120 121 /****************************************122 Purpose : 在线性表中第nPos个位置删除元素123 Input : L -- 线性表指针124 nPos -- 位置[1,ListLength(L)]125 val -- 数据126 Return : 0 --OK127 -1 --FAIL128 *****************************************/129 int DeleteList(PLinkList L, int nPos, ElemType *val)130 {131 LinkList p = *L;132 LinkList q = NULL;133 int i;134 if(nPos < 1 || nPos > ListLength(L))135 {136 return -1;137 }138 while(i < nPos -1)139 {140 p = p->next;141 i++;142 }143 q = p->next;144 p->next = q->next;145 memcpy(val, &q->data, sizeof(ElemType));146 free(q);147 q = NULL;148 return 0;149 }150 151 152 /****************************************153 Purpose : 返回线性表中第一个与e相等的数据元素的位序154 Input : L -- 线性表指针155 val -- 数据156 compare -- 比较函数的函数指针157 Return : 索引值，如果没有找到则返回-1158 *****************************************/159 int LocateElem(LinkList *L, ElemType *val, Compare compare)160 {161 LinkList p = NULL;162 int i = 1;163 if(*L == NULL)164 {165 return -1;166 }167 p = (*L)->next;168 while(p && compare(val, &p->data) != 0)169 {170 p = p->next;171 i++;172 }173 if(p == NULL)174 {175 return -1;176 }177 return i;178 }179 180 181 /****************************************182 Purpose : 遍历输出线性表中每个元素183 Input : L -- 线性表指针184 visit -- 遍历函数指针185 Return : None186 *****************************************/187 void TraverseList(PLinkList L, Visit visit)188 {189 LinkList p = NULL;190 if(*L != NULL)191 {192 p = (*L)->next;193 while(p != NULL)194 {195 visit(&p->data);196 p = p->next;197 }198 }199 }200 201 /****************************************202 Purpose : 更新第nPos个位置元素203 Input : L -- 线性表指针204 nPos -- 元素的位置 [1, ListLength[L]]205 data -- 要更新的元素206 Return : 0 --OK207 -1 --FAIL208 *****************************************/209 int UpdateList(PLinkList L, int nPos, ElemType* val)210 {211 int i = 0;212 LinkList p = NULL;213 if(nPos < 1 && nPos > ListLength(L))214 {215 return -1;216 }217 p = *L;218 while(i < nPos)219 {220 p = p->next;221 i++;222 }223 224 memcpy(&p->data, val, sizeof(ElemType));225 return 0;226 }227 228 229 230 /****************************************231 Purpose : 对线性表进行排序232 Input : L -- 线性表指针233 compare -- 比较函数234 Return : 0 --OK235 -1 --FAIL236 *****************************************/237 int SortList(PLinkList L, Compare compare)238 {239 LinkList p = NULL;240 LinkList q = NULL;241 ElemType tmp;242 if(*L == NULL)243 {244 return -1;245 }246 for(p = (*L)->next;p!=NULL;p=p->next)247 {248 for(q=p->next;q!=NULL;q=q->next)249 {250 if(compare(&q->data, &p->data) < 0)251 {252 memcpy(&tmp, &q->data, sizeof(ElemType));253 memcpy(&q->data, &p->data, sizeof(ElemType));254 memcpy(&p->data, &tmp, sizeof(ElemType));255 }256 }257 }258 return 0;259 }260 261 /****************************************262 Purpose : 对线性表进行逆置263 Input : L -- 线性表指针264 compare -- 比较函数265 Return : 0 --OK266 -1 --FAIL267 *****************************************/268 int ReverseList(PLinkList L)269 {270 LinkList p = NULL;271 LinkList q = NULL;272 LinkList s = NULL;273 if(*L == NULL)274 {275 return -1;276 }277 p = (*L)->next;278 if(p == NULL)279 {280 //没有数据则返回正确281 return 0;282 }283 q = p->next;284 while(q->next != NULL)285 {286 s = q->next;287 q->next = p;288 p = q;289 q = s;290 }291 q->next = p; //最后一个节点的next调整下292 (*L)->next->next = NULL; //保留头结点293 (*L)->next = q;294 return 0;295 } testmain.c
1 #include2 #include "LinkList.h" 3 4 void visit(ElemType *val) 5 { 6 printf("%3d ", *val); 7 } 8 int compare(ElemType* e1, ElemType* e2) 9 {10 return *e1 - *e2;11 }12 int main(int argc, char* argv[])13 {14 LinkList L;15 int i;16 ElemType val;17 printf("初始化线性表\n");18 if(InitList(&L))19 {20 printf("初始化线性表失败\n");21 return -1;22 }23 printf("插入数据1\n");24 val = 3;25 if(InsertList(&L, 1, &val))26 {27 printf("插入线性表数据失败\n");28 }29 printf("插入数据2\n");30 val = 200;31 if(InsertList(&L, 1, &val))32 {33 printf("插入线性表数据失败\n");34 }35 val = -1;36 if(InsertList(&L, 1, &val))37 {38 printf("插入线性表数据失败\n");39 }40 for(i=0;i<8;i++)41 {42 val = i;43 if(InsertList(&L, 1, &val))44 {45 printf("插入线性表数据失败\n");46 }47 }48 TraverseList(&L, visit);49 /*val = 555;50 if(InsertList(&L, ListLength(&L), &val))51 {52 printf("插入线性表数据失败\n");53 }54 TraverseList(&L, visit);55 printf("排序数据\n");56 SortList(&L, compare);57 TraverseList(&L, visit);58 printf("获取数据\n");59 if(GetElem(&L, 1, &val))60 {61 printf("获取数据失败\n");62 }63 visit(&val);*/64 /*int nLen = ListLength(&L);65 printf("线性表长度[%d]\n", nLen);66 printf("删除数据\n");67 if(DeleteList(&L, nLen, &val))68 {69 printf("删除数据失败\n");70 }71 TraverseList(&L, visit);72 printf("删除的数据为\n");73 visit(&val);74 printf("更新数据\n");75 val = 1000;76 if(UpdateList(&L, 2, &val))77 {78 printf("更新数据失败\n");79 }80 TraverseList(&L, visit);81 82 val = 555;83 int nIndex = LocateElem(&L, &val, compare);84 printf("定位数据位置为[%d]\n", nIndex);85 */86 printf("\n逆置链表\n");87 if(ReverseList(&L))88 {89 printf("逆置失败\n");90 }91 TraverseList(&L, visit);92 printf("\n");93 ClearList(&L);94 return 0;95 }