// 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://bjjierui.cn/article/iidseo.html
