鱼C论坛

 找回密码
 立即注册
查看: 2909|回复: 1

[已解决]新人请教 单链表简单问题

[复制链接]
发表于 2017-9-17 13:52:26 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
int insert(Linklist L,int i,int x)
{
int k=1;
Linklist p=L,s;
whlie(k<i)
{
p=p->next;
k++:
}
s=(Linklist)malloc(sizeof(LNode));
s->data=x;
s->next=p->next;
p->next=s;
return 0;
}
在L中第i个位置之前插入新的数据元素e。在k=i时跳出循环,此时p所指的是第i个节点,再用s->next=p->next;p->next=s;
s所指的节点不就插到了i之后了吗。我觉得k应该在i-1的时候就该跳出循环,此时p才指向第i-1个节点,用s->next=p->next;p->next=s;
才可以查到i之前。我觉得还有一种情况符合原来的代码,就是链表是一个带有头结点的链表,当k=i时,p虽然指向的是第i个,但因为有头结点
实际上指向的是第i-1个数据元素,此时再插入才是在i之前插入。
    请大佬们指出是哪一种,还是我分析的是错的。
最佳答案
2017-9-22 17:20:19
本帖最后由 tttb 于 2017-9-22 18:42 编辑

第一:下次请把整个代码贴出来  标出问题所在处  不然C语言上来就是函数  很难受  这是我的看法。
第二:下面是解释(只是针对你上面的代码说出自己的理解):
        NO.1:首先你得代码在while(k<i)处不对,应该是i-1,(可以仔细在复习一下循环),因为你是想在第i个元素前面插入元素,所以因该是k<i-1跳出循环,
        NO.2: s=(Linklist)malloc(sizeof(LNode));
                s->data=x;
                s->next=p->next;
                p->next=s;
        这是你写的插入元素代码,我认为不太健壮,下面是我的思路:
                第一种方法:
                        初始化一个新变量 Linklist q;
                        q = p->next;
                        p->next = s;
                        s->next= q;
                你的代码中:s->next = p->next 这一步有误,因为p的指针域保存的是下一个元素的地址,如果直接s->next = p->next,那么,就无法寻找
                p->next 的元素了,这样链表会断开,因此 ,先定义一个同类型的变量保存p->next,在进行插入.这是一种由前向后的思路。
                第二种方法:
                        这是由后向前的思路:
                                s->next = p->next;
                                p->next = s;
                                顺序不可颠倒。
下面是我的代码:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include<malloc.h>
  4. #include<stddef.h>
  5. #include<stdbool.h>

  6. typedef struct Node
  7. {
  8.     int data;/*数据域*/
  9.     struct Node * pNext;/*指针域*/
  10. }NODE,* PNODE;

  11. PNODE create_list();/*创建链表*/
  12. void traverse_list(PNODE pHEad);/*遍历*/
  13. bool delete_list(PNODE pHead,int,int*);/*删除*/
  14. void sort_list(PNODE);/*排序*/
  15. bool is_empty_list(PNODE pHead);/*判断是否为空*/
  16. int len_list(PNODE pHead);/*链表长度*/
  17. bool inser_list(PNODE pHead,int pos,int val);/*插入元素*/

  18. int main()
  19. {
  20.     int a,b;/*方便insert_list函数插入数据*/
  21.     int val;/*方便后面删除元素实验*/
  22.     PNODE pHead = NULL; /*等价于 struct Node* pHead = NULL*/
  23.     pHead = create_list();/*创建一个非循环单链表,并将该链表的头节点的地址赋给pHead*/

  24.     traverse_list(pHead);/*遍历*/
  25.     if(is_empty_list(pHead))
  26.     {
  27.         printf("The list is empty!\n");
  28.         exit(-1);/*用户输入0,终止程序*/
  29.     }
  30.     else
  31.     {
  32.         printf("The list is existent!\n");
  33.     }

  34.     /*输出长度*/
  35.     int len = len_list(pHead);
  36.     printf("The list'length is %d\n",len);

  37.     /*遍历链表*/
  38.     sort_list(pHead);
  39.     traverse_list(pHead);

  40.     /*插入元素*/
  41.     printf("Input the num:");/*val*/
  42.     scanf("%d",&a);
  43.     printf("选择位置:");/*pos*/
  44.     scanf("%d",&b);
  45.     inser_list(pHead,a,b);
  46.     printf("插入新元素后:");
  47.     traverse_list(pHead);

  48.     /*删除元素*/
  49.     printf("Input the num which you what to delete:");
  50.     scanf("%d",&val);
  51.     if(delete_list(pHead,2,&val))
  52.     {
  53.         printf("删除成功\n");
  54.     }
  55.     else
  56.     {
  57.         printf("删除失败!你查找的元素不存在\n");
  58.     }
  59.     traverse_list(pHead);
  60.     return 0;
  61. }

  62. /*构造链表*/
  63. PNODE create_list()
  64. {
  65.     int len,val;
  66.     PNODE pHead = (PNODE)malloc(sizeof(NODE));/*分配一个不存放数据的头节点*/
  67.     if(NULL == pHead)
  68.     {
  69.         printf("Failed!\n");
  70.         exit(-1);
  71.     }
  72.     PNODE pNULL = pHead;
  73.     pNULL->pNext = NULL;
  74.     printf("Input the num of linked list nodes:");
  75.     scanf("%d",&len);
  76.     printf("\n");
  77.     for(int i=0;i<len;i++)
  78.     {
  79.         printf("input the num of %d node:",i+1);
  80.         scanf("%d",&val);
  81.         PNODE pNew = (PNODE)malloc(sizeof(NODE));/*动态分配内存*/
  82.         if(pNew == NULL)
  83.         {
  84.             printf("Failed!\n");
  85.             exit(-1);/*终止程序*/
  86.         }
  87.         else
  88.         {
  89.             pNew->data = val;
  90.             pNULL->pNext = pNew;
  91.             pNew->pNext = NULL;
  92.             pNULL = pNew;
  93.         }
  94.     }
  95.     return pHead;
  96. }

  97. /*遍历*/
  98. void traverse_list(PNODE pHead)
  99. {
  100.     PNODE p = pHead->pNext;
  101.     while(NULL != p)
  102.     {
  103.         printf("%d ",p->data);
  104.         p = p->pNext;
  105.     }
  106.     printf("\n");
  107.     return;
  108. }

  109. /*判断是否为空*/
  110. bool is_empty_list(PNODE pHead)
  111. {
  112.     if(NULL == pHead->pNext)
  113.     {
  114.         return true;
  115.     }
  116.     else
  117.     {
  118.         return false;
  119.     }
  120. }

  121. /*链表长度*/
  122. int len_list(PNODE pHead)
  123. {
  124.     PNODE p = pHead->pNext;
  125.     int len = 0;
  126.     while(NULL != p)
  127.     {
  128.        ++len;
  129.        p = p->pNext;
  130.     }
  131.     printf("\n");
  132.     return len;
  133. }

  134. /*冒泡排序*/
  135. void sort_list(PNODE pHead)
  136. {
  137.     int r;/*交换数据*/
  138.     int i,j;/*控制循环,避免指针越界问题*/
  139.     int len = len_list(pHead);
  140.     PNODE p,q;
  141.     for(i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext)
  142.     {
  143.         for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext)
  144.         {
  145.             if(p->data > q->data)
  146.             {
  147.                 r = p->data;
  148.                 p->data = q->data;
  149.                 q->data = r;
  150.             }
  151.         }
  152.     }
  153.     return;
  154. }

  155. /*插入元素*/
  156. /*在pHead所指向的链表的第pos个节点出插入一个新节点,该节点的值为val,并且pos的值是从1开始的*/
  157. bool inser_list(PNODE pHead,int pos,int val)
  158. {
  159.     int i = 0;
  160.     PNODE p = pHead;
  161.     while(NULL != p && i<pos-1)
  162.     {
  163.         p = p->pNext;
  164.         ++i;
  165.     }
  166.     if(i>pos-1 || NULL == p)
  167.     {
  168.         return false;
  169.     }
  170.     /*此时完成p指向pos-1个节点*/
  171.     PNODE pNew = (PNODE)malloc(sizeof(NODE));
  172.     if (NULL == pNew)
  173.     {
  174.         printf("Error:动态分配内存失败!\n");
  175.         exit(-1);
  176.     }
  177.     else
  178.     {
  179.         pNew->data = val;
  180.         PNODE q = p->pNext;
  181.         p->pNext = pNew;
  182.         pNew->pNext = q;
  183.     }
  184.     return true;
  185. }

  186. bool delete_list(PNODE pHead,int pos,int* pVal)
  187. {
  188.     int i = 0;
  189.     PNODE p = pHead;
  190.     while(NULL != p->pNext && i<pos-1)
  191.     {
  192.         p = p->pNext;
  193.         ++i;
  194.     }
  195.     if(i>pos-1 || NULL == p->pNext)
  196.     {
  197.         return false;
  198.     }

  199.     PNODE q = p->pNext;
  200.     *pVal = q->data;
  201.     /*删除p节点后面的节点*/
  202.     p->pNext = p->pNext->pNext;
  203.     free(q);
  204.     q = NULL;
  205.     return true;
  206. }
复制代码

代码大致功能基本实现,可能存在些错误和不足,互相学习吧!
                       
                       
                       
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-9-22 17:20:19 | 显示全部楼层    本楼为最佳答案   
本帖最后由 tttb 于 2017-9-22 18:42 编辑

第一:下次请把整个代码贴出来  标出问题所在处  不然C语言上来就是函数  很难受  这是我的看法。
第二:下面是解释(只是针对你上面的代码说出自己的理解):
        NO.1:首先你得代码在while(k<i)处不对,应该是i-1,(可以仔细在复习一下循环),因为你是想在第i个元素前面插入元素,所以因该是k<i-1跳出循环,
        NO.2: s=(Linklist)malloc(sizeof(LNode));
                s->data=x;
                s->next=p->next;
                p->next=s;
        这是你写的插入元素代码,我认为不太健壮,下面是我的思路:
                第一种方法:
                        初始化一个新变量 Linklist q;
                        q = p->next;
                        p->next = s;
                        s->next= q;
                你的代码中:s->next = p->next 这一步有误,因为p的指针域保存的是下一个元素的地址,如果直接s->next = p->next,那么,就无法寻找
                p->next 的元素了,这样链表会断开,因此 ,先定义一个同类型的变量保存p->next,在进行插入.这是一种由前向后的思路。
                第二种方法:
                        这是由后向前的思路:
                                s->next = p->next;
                                p->next = s;
                                顺序不可颠倒。
下面是我的代码:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include<malloc.h>
  4. #include<stddef.h>
  5. #include<stdbool.h>

  6. typedef struct Node
  7. {
  8.     int data;/*数据域*/
  9.     struct Node * pNext;/*指针域*/
  10. }NODE,* PNODE;

  11. PNODE create_list();/*创建链表*/
  12. void traverse_list(PNODE pHEad);/*遍历*/
  13. bool delete_list(PNODE pHead,int,int*);/*删除*/
  14. void sort_list(PNODE);/*排序*/
  15. bool is_empty_list(PNODE pHead);/*判断是否为空*/
  16. int len_list(PNODE pHead);/*链表长度*/
  17. bool inser_list(PNODE pHead,int pos,int val);/*插入元素*/

  18. int main()
  19. {
  20.     int a,b;/*方便insert_list函数插入数据*/
  21.     int val;/*方便后面删除元素实验*/
  22.     PNODE pHead = NULL; /*等价于 struct Node* pHead = NULL*/
  23.     pHead = create_list();/*创建一个非循环单链表,并将该链表的头节点的地址赋给pHead*/

  24.     traverse_list(pHead);/*遍历*/
  25.     if(is_empty_list(pHead))
  26.     {
  27.         printf("The list is empty!\n");
  28.         exit(-1);/*用户输入0,终止程序*/
  29.     }
  30.     else
  31.     {
  32.         printf("The list is existent!\n");
  33.     }

  34.     /*输出长度*/
  35.     int len = len_list(pHead);
  36.     printf("The list'length is %d\n",len);

  37.     /*遍历链表*/
  38.     sort_list(pHead);
  39.     traverse_list(pHead);

  40.     /*插入元素*/
  41.     printf("Input the num:");/*val*/
  42.     scanf("%d",&a);
  43.     printf("选择位置:");/*pos*/
  44.     scanf("%d",&b);
  45.     inser_list(pHead,a,b);
  46.     printf("插入新元素后:");
  47.     traverse_list(pHead);

  48.     /*删除元素*/
  49.     printf("Input the num which you what to delete:");
  50.     scanf("%d",&val);
  51.     if(delete_list(pHead,2,&val))
  52.     {
  53.         printf("删除成功\n");
  54.     }
  55.     else
  56.     {
  57.         printf("删除失败!你查找的元素不存在\n");
  58.     }
  59.     traverse_list(pHead);
  60.     return 0;
  61. }

  62. /*构造链表*/
  63. PNODE create_list()
  64. {
  65.     int len,val;
  66.     PNODE pHead = (PNODE)malloc(sizeof(NODE));/*分配一个不存放数据的头节点*/
  67.     if(NULL == pHead)
  68.     {
  69.         printf("Failed!\n");
  70.         exit(-1);
  71.     }
  72.     PNODE pNULL = pHead;
  73.     pNULL->pNext = NULL;
  74.     printf("Input the num of linked list nodes:");
  75.     scanf("%d",&len);
  76.     printf("\n");
  77.     for(int i=0;i<len;i++)
  78.     {
  79.         printf("input the num of %d node:",i+1);
  80.         scanf("%d",&val);
  81.         PNODE pNew = (PNODE)malloc(sizeof(NODE));/*动态分配内存*/
  82.         if(pNew == NULL)
  83.         {
  84.             printf("Failed!\n");
  85.             exit(-1);/*终止程序*/
  86.         }
  87.         else
  88.         {
  89.             pNew->data = val;
  90.             pNULL->pNext = pNew;
  91.             pNew->pNext = NULL;
  92.             pNULL = pNew;
  93.         }
  94.     }
  95.     return pHead;
  96. }

  97. /*遍历*/
  98. void traverse_list(PNODE pHead)
  99. {
  100.     PNODE p = pHead->pNext;
  101.     while(NULL != p)
  102.     {
  103.         printf("%d ",p->data);
  104.         p = p->pNext;
  105.     }
  106.     printf("\n");
  107.     return;
  108. }

  109. /*判断是否为空*/
  110. bool is_empty_list(PNODE pHead)
  111. {
  112.     if(NULL == pHead->pNext)
  113.     {
  114.         return true;
  115.     }
  116.     else
  117.     {
  118.         return false;
  119.     }
  120. }

  121. /*链表长度*/
  122. int len_list(PNODE pHead)
  123. {
  124.     PNODE p = pHead->pNext;
  125.     int len = 0;
  126.     while(NULL != p)
  127.     {
  128.        ++len;
  129.        p = p->pNext;
  130.     }
  131.     printf("\n");
  132.     return len;
  133. }

  134. /*冒泡排序*/
  135. void sort_list(PNODE pHead)
  136. {
  137.     int r;/*交换数据*/
  138.     int i,j;/*控制循环,避免指针越界问题*/
  139.     int len = len_list(pHead);
  140.     PNODE p,q;
  141.     for(i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext)
  142.     {
  143.         for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext)
  144.         {
  145.             if(p->data > q->data)
  146.             {
  147.                 r = p->data;
  148.                 p->data = q->data;
  149.                 q->data = r;
  150.             }
  151.         }
  152.     }
  153.     return;
  154. }

  155. /*插入元素*/
  156. /*在pHead所指向的链表的第pos个节点出插入一个新节点,该节点的值为val,并且pos的值是从1开始的*/
  157. bool inser_list(PNODE pHead,int pos,int val)
  158. {
  159.     int i = 0;
  160.     PNODE p = pHead;
  161.     while(NULL != p && i<pos-1)
  162.     {
  163.         p = p->pNext;
  164.         ++i;
  165.     }
  166.     if(i>pos-1 || NULL == p)
  167.     {
  168.         return false;
  169.     }
  170.     /*此时完成p指向pos-1个节点*/
  171.     PNODE pNew = (PNODE)malloc(sizeof(NODE));
  172.     if (NULL == pNew)
  173.     {
  174.         printf("Error:动态分配内存失败!\n");
  175.         exit(-1);
  176.     }
  177.     else
  178.     {
  179.         pNew->data = val;
  180.         PNODE q = p->pNext;
  181.         p->pNext = pNew;
  182.         pNew->pNext = q;
  183.     }
  184.     return true;
  185. }

  186. bool delete_list(PNODE pHead,int pos,int* pVal)
  187. {
  188.     int i = 0;
  189.     PNODE p = pHead;
  190.     while(NULL != p->pNext && i<pos-1)
  191.     {
  192.         p = p->pNext;
  193.         ++i;
  194.     }
  195.     if(i>pos-1 || NULL == p->pNext)
  196.     {
  197.         return false;
  198.     }

  199.     PNODE q = p->pNext;
  200.     *pVal = q->data;
  201.     /*删除p节点后面的节点*/
  202.     p->pNext = p->pNext->pNext;
  203.     free(q);
  204.     q = NULL;
  205.     return true;
  206. }
复制代码

代码大致功能基本实现,可能存在些错误和不足,互相学习吧!
                       
                       
                       
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2024-3-29 01:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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