论坛 › 数据结构与算法 › 新人请教 单链表简单问题

深于黑 发表于 2017-9-17 13:52:26

新人请教 单链表简单问题

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之前插入。
    请大佬们指出是哪一种，还是我分析的是错的。

tttb 发表于 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;
                                顺序不可颠倒。
下面是我的代码：
#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
#include<stddef.h>
#include<stdbool.h>

typedef struct Node
{
    int data;/*数据域*/
    struct Node * pNext;/*指针域*/
}NODE,* PNODE;

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

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

    traverse_list(pHead);/*遍历*/
    if(is_empty_list(pHead))
    {
      printf("The list is empty!\n");
      exit(-1);/*用户输入0，终止程序*/
    }
    else
    {
      printf("The list is existent!\n");
    }

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

    /*遍历链表*/
    sort_list(pHead);
    traverse_list(pHead);

    /*插入元素*/
    printf("Input the num:");/*val*/
    scanf("%d",&a);
    printf("选择位置:");/*pos*/
    scanf("%d",&b);
    inser_list(pHead,a,b);
    printf("插入新元素后:");
    traverse_list(pHead);

    /*删除元素*/
    printf("Input the num which you what to delete:");
    scanf("%d",&val);
    if(delete_list(pHead,2,&val))
    {
      printf("删除成功\n");
    }
    else
    {
      printf("删除失败！你查找的元素不存在\n");
    }
    traverse_list(pHead);
    return 0;
}

/*构造链表*/
PNODE create_list()
{
    int len,val;
    PNODE pHead = (PNODE)malloc(sizeof(NODE));/*分配一个不存放数据的头节点*/
    if(NULL == pHead)
    {
      printf("Failed!\n");
      exit(-1);
    }
    PNODE pNULL = pHead;
    pNULL->pNext = NULL;
    printf("Input the num of linked list nodes:");
    scanf("%d",&len);
    printf("\n");
    for(int i=0;i<len;i++)
    {
      printf("input the num of %d node:",i+1);
      scanf("%d",&val);
      PNODE pNew = (PNODE)malloc(sizeof(NODE));/*动态分配内存*/
      if(pNew == NULL)
      {
            printf("Failed!\n");
            exit(-1);/*终止程序*/
      }
      else
      {
            pNew->data = val;
            pNULL->pNext = pNew;
            pNew->pNext = NULL;
            pNULL = pNew;
      }
    }
    return pHead;
}

/*遍历*/
void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    while(NULL != p)
    {
      printf("%d ",p->data);
      p = p->pNext;
    }
    printf("\n");
    return;
}

/*判断是否为空*/
bool is_empty_list(PNODE pHead)
{
    if(NULL == pHead->pNext)
    {
      return true;
    }
    else
    {
      return false;
    }
}

/*链表长度*/
int len_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    int len = 0;
    while(NULL != p)
    {
       ++len;
       p = p->pNext;
    }
    printf("\n");
    return len;
}

/*冒泡排序*/
void sort_list(PNODE pHead)
{
    int r;/*交换数据*/
    int i,j;/*控制循环，避免指针越界问题*/
    int len = len_list(pHead);
    PNODE p,q;
    for(i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext)
    {
      for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext)
      {
            if(p->data > q->data)
            {
                r = p->data;
                p->data = q->data;
                q->data = r;
            }
      }
    }
    return;
}

/*插入元素*/
/*在pHead所指向的链表的第pos个节点出插入一个新节点，该节点的值为val，并且pos的值是从1开始的*/
bool inser_list(PNODE pHead,int pos,int val)
{
    int i = 0;
    PNODE p = pHead;
    while(NULL != p && i<pos-1)
    {
      p = p->pNext;
      ++i;
    }
    if(i>pos-1 || NULL == p)
    {
      return false;
    }
    /*此时完成p指向pos-1个节点*/
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
      printf("Error:动态分配内存失败！\n");
      exit(-1);
    }
    else
    {
      pNew->data = val;
      PNODE q = p->pNext;
      p->pNext = pNew;
      pNew->pNext = q;
    }
    return true;
}

bool delete_list(PNODE pHead,int pos,int* pVal)
{
    int i = 0;
    PNODE p = pHead;
    while(NULL != p->pNext && i<pos-1)
    {
      p = p->pNext;
      ++i;
    }
    if(i>pos-1 || NULL == p->pNext)
    {
      return false;
    }

    PNODE q = p->pNext;
    *pVal = q->data;
    /*删除p节点后面的节点*/
    p->pNext = p->pNext->pNext;
    free(q);
    q = NULL;
    return true;
}

代码大致功能基本实现，可能存在些错误和不足，互相学习吧！
                       
                       
                       

查看完整版本: 新人请教 单链表简单问题