我要成为嵌入式高手之3月19日数据结构第二天！！
————————————————————————————

valgrind内存测试工具

让虚拟机上网、在虚拟机上下载软件，参考笔记：

我要成为嵌入式高手之2月3日Linux高编第一天！！-CSDN博客

上图表示申请了10个空间，释放了10个空间，没有内存泄漏

上图申请了11个空间，释放了10个空间，存在内存泄漏（leaked memory） 

 单向链表逆序

#include "head.h"LINK_LIST *CreateLink()
{LINK_LIST *plist = malloc(sizeof(LINK_LIST));if (NULL == plist){perror("fail to malloc");return NULL;}plist->phead = NULL;plist->clen = 0;return plist;
}int LinkSearch(LINK_LIST *plist)
{LINK_NODE *ptmp = plist->phead;while (ptmp != NULL){printf("%d\n", ptmp->data);ptmp = ptmp->pnext;}printf("len = %d\n", plist->clen);return 0;
}int PushTailLink(LINK_LIST *plist, DATA_TYPE data)
{LINK_NODE *ptmp = plist->phead;LINK_NODE *pnode = malloc(sizeof(LINK_NODE));if (NULL == pnode){perror("fail to malloc pnode");return -1;}pnode->data = data;pnode->pnext = NULL;if (plist->phead == NULL){plist->phead = pnode;}else{while (ptmp->pnext != NULL){ptmp = ptmp->pnext;}ptmp->pnext = pnode;plist->clen++;}return 0;
}int ReverseLink(LINK_LIST *plist)
{if (plist->phead == NULL){return -1;}LINK_NODE *ptmp = plist->phead;plist->phead = NULL;LINK_NODE *pinsert = NULL;while (ptmp != NULL){pinsert = ptmp;ptmp = ptmp->pnext;pinsert->pnext = plist->phead;plist->phead = pinsert;}return 0;
}int main()
{LINK_LIST *plist = NULL;plist = CreateLink();if (NULL == plist){return -1;}PushTailLink(plist, 1);PushTailLink(plist, 2);PushTailLink(plist, 3);PushTailLink(plist, 4);PushTailLink(plist, 5);LinkSearch(plist);ReverseLink(plist);printf("=========================\n");LinkSearch(plist);return 0;
}

找单向链表的中间节点

 

LINK_NODE *SearchMidNode(LINK_LIST *plist)
{LINK_NODE *pfast = plist->phead;LINK_NODE *pslow = plist->phead;while (pfast != NULL){pfast = pfast->pnext;if (NULL == pfast){break;}pfast = pfast->pnext;pslow = pslow->pnext;}return pslow;
}

寻找链表倒数第K个结点

LINK_NODE *SearchReNoKNode(LINK_LIST *plist, int k)
{LINK_NODE *pfast = plist->phead;LINK_NODE *pslow = pfast;int i = 0;for (i = 0; i < k; i++){if (NULL == pfast){return NULL;}pfast = pfast->pnext;}while (pfast != NULL){pfast = pfast->pnext;pslow = pslow->pnext;}return pslow;
}

删除指定数据的结点

int DeleteKNode(LINK_LIST *plist, int k)
{LINK_NODE *pfree = NULL;LINK_NODE *ptmp = NULL;pfree = plist->phead;ptmp = pfree;while (pfree != NULL){if (pfree->data == k){if (plist->phead == pfree){plist->phead = pfree->pnext;free(pfree);plist->clen--;break;}else{ptmp->pnext = pfree->pnext;free(pfree);plist->clen--;break;}}else{ptmp = pfree;pfree = pfree->pnext;}}return 0;
}

 链表的插入排序

int InsertSort(LINK_LIST *plist)
{LINK_NODE *ptmp = NULL;LINK_NODE *pinsert = NULL;LINK_NODE *p = NULL;if (p == NULL || p->pnext == NULL){return -1;}ptmp = plist->phead->pnext;plist->phead->pnext = NULL;pinsert = ptmp;while (ptmp != NULL){pinsert = ptmp;ptmp = ptmp->pnext;if (pinsert->data <= plist->phead->data){pinsert->pnext = plist->phead;plist->phead = pinsert;}else{LINK_NODE *p = plist->phead;while (p->pnext != NULL && p->pnext->data < pinsert->data){p = p->pnext;}pinsert->pnext = p->pnext;p->pnext = pinsert;}}return 0;
}