链表的基本操作
// struct.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "stdio.h" #include "stdlib.h" #include "string.h" #define RETURN_OK 0 #define RETURN_ERROR 1 #define MAX_LEN 11 #define MY_RAND_MAX 26 typedef struct tag_Info_S { int a; int b; int c; char name[MAX_LEN]; }Info_S; typedef struct tag_MyList_S { Info_S stInfo; struct tag_MyList_S *next; }MyList_S; MyList_S *g_pHead; int AllocOneNode(MyList_S **ppNewNode); void InitOneNode(MyList_S *pNode); int InitList(MyList_S **ppHead); int DelList(MyList_S **ppHead); int AllocOneNode(MyList_S **ppNewNode) { MyList_S *pTemp = (MyList_S *)malloc(sizeof(MyList_S)); if (NULL == pTemp) { *ppNewNode = NULL; return RETURN_ERROR; } *ppNewNode = pTemp; return RETURN_OK; } void InitOneNode(MyList_S *pNode) { int i = 0; int len = 0; pNode->stInfo.a = rand() % MY_RAND_MAX; //rand的使用不规范 pNode->stInfo.b = rand() % MY_RAND_MAX; pNode->stInfo.c = rand() % MY_RAND_MAX; len = (rand() % (MAX_LEN - 2)) + 1; //1---10 for (i = 0; i < len; i++) { pNode->stInfo.name[i] = rand() % MY_RAND_MAX + 'A'; } pNode->stInfo.name[len] = '\0'; pNode->next = NULL; return; } int InitList(MyList_S **ppHead) { int ret = RETURN_ERROR; MyList_S *pNew = NULL; if (NULL != *ppHead) //需要先销毁 { DelList(ppHead); } ret = AllocOneNode(&pNew); if (RETURN_OK != ret) { return RETURN_ERROR; } memset(pNew, 0, sizeof(MyList_S)); pNew->next = NULL; *ppHead = pNew; return RETURN_OK; } int DelList(MyList_S **ppHead) { MyList_S *pFreeNode = NULL; MyList_S *pTmpNode = NULL; if (NULL == *ppHead) { return RETURN_ERROR; } pTmpNode = *ppHead; while (pTmpNode) { pFreeNode = pTmpNode; pTmpNode = pTmpNode->next; free(pFreeNode); } *ppHead = NULL; return RETURN_OK; } int GetListLen(MyList_S *pHead, int *ListLen) { int len = 0; if (NULL == pHead) { return RETURN_ERROR; } pHead = pHead->next; while (pHead) { len++; pHead = pHead->next; } *ListLen = len; return RETURN_OK; } int AddNodeAtListTrail(MyList_S **ppHead, MyList_S *pNewNode) { MyList_S *pTemp = NULL; if (NULL == *ppHead) { return RETURN_ERROR; } //当前链表为空时,头节点的后面插入 if (NULL == (*ppHead)->next) { (*ppHead)->next = pNewNode; return RETURN_OK; } pTemp = (*ppHead)->next; while (pTemp->next) { pTemp = pTemp->next; } pTemp->next = pNewNode; pNewNode->next = NULL; return RETURN_OK; } int AddNodeAtListHead(MyList_S **ppHead, MyList_S *pNewNode) { if (NULL == *ppHead) { return RETURN_ERROR; } pNewNode->next = (*ppHead)->next; (*ppHead)->next = pNewNode; return RETURN_OK; } //链表从0开始编号,pNewNode插入后在第iLocal位置 int AddNodeAtListLocal(MyList_S **ppHead, MyList_S *pNewNode, int iLocal) { int len = 0; int i = 0; MyList_S *pTemp = NULL; if (NULL == *ppHead) { return RETURN_ERROR; } if (iLocal == 0) { AddNodeAtListHead(ppHead, pNewNode); return RETURN_OK; } GetListLen(*ppHead, &len); if (iLocal > len) //由于从0开始编号,所以iLocal最大为len { return RETURN_ERROR; } //查找第编号为ilocal - 1的有效节点的位置 pTemp = (*ppHead); while (i < iLocal) { pTemp = pTemp->next; i++; } pNewNode->next = pTemp->next; pTemp->next = pNewNode; return RETURN_OK; } int DelOneNodeAtListTrail(MyList_S **ppHead, MyList_S *pDelNode) { MyList_S *pPre = NULL; MyList_S *pCur = NULL; if (NULL == *ppHead || NULL == (*ppHead)->next) { return RETURN_ERROR; } pCur = (*ppHead)->next; if (NULL == pCur->next) //如果只有一个节点,可以使用DelOneNodeAtListHead删除 { memcpy_s(&(pDelNode->stInfo), sizeof(Info_S), &(pCur->stInfo), sizeof(Info_S)); (*ppHead)->next = NULL; free(pCur); pCur = NULL; } while (pCur->next) //pCur->next = NULL,pCur为最后一个有效节点 { pPre = pCur; pCur = pCur->next; } pPre->next = NULL; memcpy_s(&(pDelNode->stInfo), sizeof(Info_S), &(pCur->stInfo), sizeof(Info_S)); free(pCur); pCur = NULL; return RETURN_OK; } int DelOneNodeAtListHead(MyList_S **ppHead, MyList_S *pDelNode) { MyList_S *pCur = NULL; if (NULL == *ppHead || NULL == (*ppHead)->next) { return RETURN_ERROR; } pCur = (*ppHead)->next; (*ppHead)->next = pCur->next; memcpy_s(&(pDelNode->stInfo), sizeof(Info_S), &(pCur->stInfo), sizeof(Info_S)); free(pCur); return RETURN_OK; } int DelNodeAtListLocal(MyList_S **ppHead, MyList_S *pDelNode, int iLocal) { int i = 0; int len = 0; MyList_S *pTemp = NULL; MyList_S *pFreeNode = NULL; if (NULL == *ppHead || NULL == (*ppHead)->next) { return RETURN_ERROR; } if (iLocal == 0) { DelOneNodeAtListHead(ppHead, pDelNode); return RETURN_OK; } (void)GetListLen(*ppHead, &len); //不用判断返回值了,此处是内部调用,前面的判断可以保证此处可以获取到长度 if (iLocal >= len) { return RETURN_ERROR; //最大到len - 1 } pTemp = *ppHead; while (i < iLocal) { pTemp = pTemp->next; i++; } pFreeNode = pTemp->next; memcpy_s(&(pDelNode->stInfo), sizeof(Info_S), &(pFreeNode->stInfo), sizeof(Info_S)); pTemp->next = pFreeNode->next; free(pFreeNode); pFreeNode = NULL; return RETURN_OK; } int RevertList(MyList_S *pHead) //头指针的指向不发生变化,变化的是pHead->next { MyList_S *pPre = NULL; MyList_S *pCur = NULL; if (NULL == pHead || NULL == pHead->next) { return RETURN_ERROR; } pPre = pHead->next; pHead->next = NULL; while (pPre) { pCur = pPre->next; pPre->next = NULL; AddNodeAtListHead(&pHead, pPre); pPre = pCur; } return RETURN_OK; } /* 排序,先按a排序,a相同按照b排序,b相同按照c排序,c相同按照name排序 */ int SrcCopyInfoToDst(void *dst, void *src) { if (NULL == dst || NULL == src) { return RETURN_ERROR; } memcpy_s(dst, sizeof(Info_S), src, sizeof(Info_S)); return RETURN_OK; } int sort(MyList_S *pHead) { MyList_S *pCur = NULL; MyList_S *pNext = NULL; Info_S stInfo = { 0 }; if (NULL == pHead || NULL == pHead->next) { return RETURN_ERROR; } pCur = pHead->next; if (NULL == pCur) { return RETURN_OK; } //排序,比较搓考虑优化 while (pCur) { pNext = pCur; while (pNext) { if (pNext->stInfo.a > pCur->stInfo.a) { SrcCopyInfoToDst(&stInfo, &(pCur->stInfo)); SrcCopyInfoToDst(&(pCur->stInfo), &(pNext->stInfo)); SrcCopyInfoToDst(&(pNext->stInfo), &stInfo); } else if (pNext->stInfo.a == pCur->stInfo.a) { if (pNext->stInfo.b > pCur->stInfo.b) { SrcCopyInfoToDst(&stInfo, &(pCur->stInfo)); SrcCopyInfoToDst(&(pCur->stInfo), &(pNext->stInfo)); SrcCopyInfoToDst(&(pNext->stInfo), &stInfo); } else if (pNext->stInfo.b == pCur->stInfo.b) { if (pNext->stInfo.c > pCur->stInfo.c) { SrcCopyInfoToDst(&stInfo, &(pCur->stInfo)); SrcCopyInfoToDst(&(pCur->stInfo), &(pNext->stInfo)); SrcCopyInfoToDst(&(pNext->stInfo), &stInfo); } else if (pNext->stInfo.c == pCur->stInfo.c) { if (strcmp(pCur->stInfo.name, pNext->stInfo.name) > 0) { SrcCopyInfoToDst(&stInfo, &(pCur->stInfo)); SrcCopyInfoToDst(&(pCur->stInfo), &(pNext->stInfo)); SrcCopyInfoToDst(&(pNext->stInfo), &stInfo); } } } } pNext = pNext->next; } pCur = pCur->next; } return RETURN_OK; } void printList(MyList_S *pHead) { if (NULL == pHead) { return; } pHead = pHead->next; while (pHead) { printf("a = %d, b = %d, c = %d, name = %s\n", pHead->stInfo.a, pHead->stInfo.b, pHead->stInfo.c, pHead->stInfo.name); pHead = pHead->next; } printf("-----------------------------------------------------------------------------------\n"); return; } int _tmain(int argc, _TCHAR* argv[]) { int i = 0; int len = 0; int ret = RETURN_ERROR; MyList_S *pTemp = NULL; InitList(&g_pHead); for (i = 0; i < 10; i++) { ret = AllocOneNode(&pTemp); if (RETURN_OK != ret) { printf("alloc node failed!\n"); return RETURN_ERROR; } InitOneNode(pTemp); if (i % 2) { AddNodeAtListTrail(&g_pHead, pTemp); } else { AddNodeAtListHead(&g_pHead, pTemp); } } GetListLen(g_pHead, &len); printf("len = %d\n", len); printList(g_pHead); ret = AllocOneNode(&pTemp); if (RETURN_OK != ret) { printf("alloc node failed!\n"); return RETURN_ERROR; } InitOneNode(pTemp); AddNodeAtListLocal(&g_pHead, pTemp, 10); GetListLen(g_pHead, &len); printf("len = %d\n", len); printList(g_pHead); DelNodeAtListLocal(&g_pHead, pTemp, 10); GetListLen(g_pHead, &len); printf("len = %d\n", len); printList(g_pHead); RevertList(g_pHead); printList(g_pHead); sort(g_pHead); printList(g_pHead); return 0; }
网页标题:链表的基本操作
文章出自:http://pwwzsj.com/article/iidseo.html