[已解决]C语言数据结构与算法之链表

Lycoriswu

小组初学数据结构与算法，希望得到大佬们的优异代码参考。

最佳答案

月排行榜 / 总排行榜

xieglt

2020-9-21 11:08:28

#include<stdio.h>
#include<stdlib.h>

typedef struct tagLinkList
{
        int data;
        struct tagLinkList * pNext;
}LL,* LPLL;

//增加一个节点
LPLL AddNode(int data)
{
        LPLL p = (LPLL)malloc(sizeof(LL));
        if(p != NULL)
        {
              p->data = data;
            p->pNext = NULL;
        }
        return p;
}

//建立链表
LPLL CreateList(int maxData)
{
        LPLL lpHead = AddNode(0);
        LPLL lpNode = lpHead;
        
        for(int i = 1 ; i <= maxData ; i++)
        {
                lpNode->pNext = AddNode(i);
                lpNode = lpNode->pNext;
                if(lpNode == NULL)
                {
                        break;
                }
        }

        return lpHead;
}

//删除链表
void DestoryList(LPLL lpHead)
{
        while(lpHead != NULL)
        {
                LPLL lpNode = lpHead->pNext;
                free(lpHead);
                lpHead =lpNode;
        }
}

//寻找到数第k个元素
long FindLastK(LPLL lpHead,int k)
{

        LPLL fast = lpHead->pNext;
        long nRet = 0;
        
        do 
        {        
                //链表为空，返回
                if(fast == NULL)
                {
                        break;
                }
                
                //k<=0 退出，倒数计数从1开始，如果想从0开始的话，if(k < 0) 
                if(k <= 0)
                {
                        break;
                }
                
                //倒数计数从1开始，如果想从0开始的话，long i = 0; 
                long i = 1;
                
                //定义一个快指针，定位到顺数第K个元素，此时fast - head = k
                while(fast != NULL && i++ < k)
                {
                        fast = fast->pNext;
                }
                
                //如果fast == NULL，说明链表中不足k个元素
                if(fast == NULL)
                {
                        break;
                }
                
                //定义一个慢指针，slow = head ，所以 fast - slow = K
                LPLL slow = lpHead->pNext;
                LPLL lastK = NULL;
                
                //让fast 指针移动到链表尾部，同时slow指针跟着向后移动
                //以保证 fast - slow == K
                //当fast到达链表尾部(NULL)时,slow刚好到达K+1,故而slow之前的节点即为倒数第K个节点
                while(fast != NULL)
                {
                        fast = fast->pNext;
                        lastK = slow;
                        slow = slow->pNext;
                }
                
                printf("The last %d element is : %d\n",k,lastK->data);
                
                nRet = 1;
        }while(0);
        
        return nRet;
}

int main()
{
        int test[3] = {6,5,1};

        LPLL lpHead = CreateList(5);
        
        for(int i = 0 ; i < 3 ; i ++)
        {
                if(FindLastK(lpHead,test[i]) == 0)
                {
                        printf("can't find the last %d element in list\n",test[i]);
                }
        }

        DestoryList(lpHead);

        return 0;
}

跳转到最佳答案楼层

xieglt

#include<stdio.h>
#include<stdlib.h>

typedef struct tagLinkList
{
        int data;
        struct tagLinkList * pNext;
}LL,* LPLL;

//增加一个节点
LPLL AddNode(int data)
{
        LPLL p = (LPLL)malloc(sizeof(LL));
        if(p != NULL)
        {
              p->data = data;
            p->pNext = NULL;
        }
        return p;
}

//建立链表
LPLL CreateList(int maxData)
{
        LPLL lpHead = AddNode(0);
        LPLL lpNode = lpHead;
        
        for(int i = 1 ; i <= maxData ; i++)
        {
                lpNode->pNext = AddNode(i);
                lpNode = lpNode->pNext;
                if(lpNode == NULL)
                {
                        break;
                }
        }

        return lpHead;
}

//删除链表
void DestoryList(LPLL lpHead)
{
        while(lpHead != NULL)
        {
                LPLL lpNode = lpHead->pNext;
                free(lpHead);
                lpHead =lpNode;
        }
}

//寻找到数第k个元素
long FindLastK(LPLL lpHead,int k)
{

        LPLL fast = lpHead->pNext;
        long nRet = 0;
        
        do 
        {        
                //链表为空，返回
                if(fast == NULL)
                {
                        break;
                }
                
                //k<=0 退出，倒数计数从1开始，如果想从0开始的话，if(k < 0) 
                if(k <= 0)
                {
                        break;
                }
                
                //倒数计数从1开始，如果想从0开始的话，long i = 0; 
                long i = 1;
                
                //定义一个快指针，定位到顺数第K个元素，此时fast - head = k
                while(fast != NULL && i++ < k)
                {
                        fast = fast->pNext;
                }
                
                //如果fast == NULL，说明链表中不足k个元素
                if(fast == NULL)
                {
                        break;
                }
                
                //定义一个慢指针，slow = head ，所以 fast - slow = K
                LPLL slow = lpHead->pNext;
                LPLL lastK = NULL;
                
                //让fast 指针移动到链表尾部，同时slow指针跟着向后移动
                //以保证 fast - slow == K
                //当fast到达链表尾部(NULL)时,slow刚好到达K+1,故而slow之前的节点即为倒数第K个节点
                while(fast != NULL)
                {
                        fast = fast->pNext;
                        lastK = slow;
                        slow = slow->pNext;
                }
                
                printf("The last %d element is : %d\n",k,lastK->data);
                
                nRet = 1;
        }while(0);
        
        return nRet;
}

int main()
{
        int test[3] = {6,5,1};

        LPLL lpHead = CreateList(5);
        
        for(int i = 0 ; i < 3 ; i ++)
        {
                if(FindLastK(lpHead,test[i]) == 0)
                {
                        printf("can't find the last %d element in list\n",test[i]);
                }
        }

        DestoryList(lpHead);

        return 0;
}