论坛 › C\C++交流 › C语言数据结构与算法之链表

Lycoriswu 发表于 2020-9-21 11:08:27

C语言数据结构与算法之链表

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

xieglt 发表于 2020-9-21 11:08:28

本帖最后由 xieglt 于 2020-9-21 13:08 编辑

#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 = {6,5,1};

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

        DestoryList(lpHead);

        return 0;
}

查看完整版本: C语言数据结构与算法之链表