我要成为嵌入式高手之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;
}