设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › C语言数据结构与算法之链表
返回列表 发新帖
查看: 1723|回复: 1

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

[复制链接]
Lycoriswu
发表于 2020-9-21 11:08:27 From FishC Mobile | 显示全部楼层 |阅读模式
50鱼币
小组初学数据结构与算法，希望得到大佬们的优异代码参考。
最佳答案
月排行榜 / 总排行榜
xieglt
2020-9-21 11:08:28
本帖最后由 xieglt 于 2020-9-21 13:08 编辑
  1. #include<stdio.h>
  2. #include<stdlib.h>

  4. typedef struct tagLinkList
  5. {
  6.         int data;
  7.         struct tagLinkList * pNext;
  8. }LL,* LPLL;

  10. //增加一个节点
  11. LPLL AddNode(int data)
  12. {
  13.         LPLL p = (LPLL)malloc(sizeof(LL));
  14.         if(p != NULL)
  15.         {
  16.               p->data = data;
  17.             p->pNext = NULL;
  18.         }
  19.         return p;
  20. }

  22. //建立链表
  23. LPLL CreateList(int maxData)
  24. {
  25.         LPLL lpHead = AddNode(0);
  26.         LPLL lpNode = lpHead;
  27.        
  28.         for(int i = 1 ; i <= maxData ; i++)
  29.         {
  30.                 lpNode->pNext = AddNode(i);
  31.                 lpNode = lpNode->pNext;
  32.                 if(lpNode == NULL)
  33.                 {
  34.                         break;
  35.                 }
  36.         }

  38.         return lpHead;
  39. }

  41. //删除链表
  42. void DestoryList(LPLL lpHead)
  43. {
  44.         while(lpHead != NULL)
  45.         {
  46.                 LPLL lpNode = lpHead->pNext;
  47.                 free(lpHead);
  48.                 lpHead =lpNode;
  49.         }
  50. }

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

  56.         LPLL fast = lpHead->pNext;
  57.         long nRet = 0;
  58.        
  59.         do
  60.         {       
  61.                 //链表为空，返回
  62.                 if(fast == NULL)
  63.                 {
  64.                         break;
  65.                 }
  66.                
  67.                 //k<=0 退出，倒数计数从1开始，如果想从0开始的话，if(k < 0)
  68.                 if(k <= 0)
  69.                 {
  70.                         break;
  71.                 }
  72.                
  73.                 //倒数计数从1开始，如果想从0开始的话，long i = 0;
  74.                 long i = 1;
  75.                
  76.                 //定义一个快指针，定位到顺数第K个元素，此时fast - head = k
  77.                 while(fast != NULL && i++ < k)
  78.                 {
  79.                         fast = fast->pNext;
  80.                 }
  81.                
  82.                 //如果fast == NULL，说明链表中不足k个元素
  83.                 if(fast == NULL)
  84.                 {
  85.                         break;
  86.                 }
  87.                
  88.                 //定义一个慢指针，slow = head ，所以 fast - slow = K
  89.                 LPLL slow = lpHead->pNext;
  90.                 LPLL lastK = NULL;
  91.                
  92.                 //让fast 指针移动到链表尾部，同时slow指针跟着向后移动
  93.                 //以保证 fast - slow == K
  94.                 //当fast到达链表尾部(NULL)时,slow刚好到达K+1,故而slow之前的节点即为倒数第K个节点
  95.                 while(fast != NULL)
  96.                 {
  97.                         fast = fast->pNext;
  98.                         lastK = slow;
  99.                         slow = slow->pNext;
  100.                 }
  101.                
  102.                 printf("The last %d element is : %d\n",k,lastK->data);
  103.                
  104.                 nRet = 1;
  105.         }while(0);
  106.        
  107.         return nRet;
  108. }

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

  114.         LPLL lpHead = CreateList(5);
  115.        
  116.         for(int i = 0 ; i < 3 ; i ++)
  117.         {
  118.                 if(FindLastK(lpHead,test[i]) == 0)
  119.                 {
  120.                         printf("can't find the last %d element in list\n",test[i]);
  121.                 }
  122.         }

  124.         DestoryList(lpHead);

  126.         return 0;
  127. }
复制代码
Screenshot_20200920_111556.jpg

最佳答案

xieglt

查看完整内容

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

xieglt
发表于 2020-9-21 11:08:28 | 显示全部楼层    本楼为最佳答案   
本帖最后由 xieglt 于 2020-9-21 13:08 编辑
  1. #include<stdio.h>
  2. #include<stdlib.h>

  4. typedef struct tagLinkList
  5. {
  6.         int data;
  7.         struct tagLinkList * pNext;
  8. }LL,* LPLL;

  10. //增加一个节点
  11. LPLL AddNode(int data)
  12. {
  13.         LPLL p = (LPLL)malloc(sizeof(LL));
  14.         if(p != NULL)
  15.         {
  16.               p->data = data;
  17.             p->pNext = NULL;
  18.         }
  19.         return p;
  20. }

  22. //建立链表
  23. LPLL CreateList(int maxData)
  24. {
  25.         LPLL lpHead = AddNode(0);
  26.         LPLL lpNode = lpHead;
  27.        
  28.         for(int i = 1 ; i <= maxData ; i++)
  29.         {
  30.                 lpNode->pNext = AddNode(i);
  31.                 lpNode = lpNode->pNext;
  32.                 if(lpNode == NULL)
  33.                 {
  34.                         break;
  35.                 }
  36.         }

  38.         return lpHead;
  39. }

  41. //删除链表
  42. void DestoryList(LPLL lpHead)
  43. {
  44.         while(lpHead != NULL)
  45.         {
  46.                 LPLL lpNode = lpHead->pNext;
  47.                 free(lpHead);
  48.                 lpHead =lpNode;
  49.         }
  50. }

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

  56.         LPLL fast = lpHead->pNext;
  57.         long nRet = 0;
  58.        
  59.         do
  60.         {       
  61.                 //链表为空，返回
  62.                 if(fast == NULL)
  63.                 {
  64.                         break;
  65.                 }
  66.                
  67.                 //k<=0 退出，倒数计数从1开始，如果想从0开始的话，if(k < 0)
  68.                 if(k <= 0)
  69.                 {
  70.                         break;
  71.                 }
  72.                
  73.                 //倒数计数从1开始，如果想从0开始的话，long i = 0;
  74.                 long i = 1;
  75.                
  76.                 //定义一个快指针，定位到顺数第K个元素，此时fast - head = k
  77.                 while(fast != NULL && i++ < k)
  78.                 {
  79.                         fast = fast->pNext;
  80.                 }
  81.                
  82.                 //如果fast == NULL，说明链表中不足k个元素
  83.                 if(fast == NULL)
  84.                 {
  85.                         break;
  86.                 }
  87.                
  88.                 //定义一个慢指针，slow = head ，所以 fast - slow = K
  89.                 LPLL slow = lpHead->pNext;
  90.                 LPLL lastK = NULL;
  91.                
  92.                 //让fast 指针移动到链表尾部，同时slow指针跟着向后移动
  93.                 //以保证 fast - slow == K
  94.                 //当fast到达链表尾部(NULL)时,slow刚好到达K+1,故而slow之前的节点即为倒数第K个节点
  95.                 while(fast != NULL)
  96.                 {
  97.                         fast = fast->pNext;
  98.                         lastK = slow;
  99.                         slow = slow->pNext;
  100.                 }
  101.                
  102.                 printf("The last %d element is : %d\n",k,lastK->data);
  103.                
  104.                 nRet = 1;
  105.         }while(0);
  106.        
  107.         return nRet;
  108. }

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

  114.         LPLL lpHead = CreateList(5);
  115.        
  116.         for(int i = 0 ; i < 3 ; i ++)
  117.         {
  118.                 if(FindLastK(lpHead,test[i]) == 0)
  119.                 {
  120.                         printf("can't find the last %d element in list\n",test[i]);
  121.                 }
  122.         }

  124.         DestoryList(lpHead);

  126.         return 0;
  127. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-1 06:48

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表