链表线性表的操作填空题

Question

编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码，请补全内容。我的代码为什么溢出？要怎么修改才正确

```c
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define ElemType int

typedef struct LNode
{
 int data;
 struct LNode *next;
}LNode,*LinkList;

int CreateLink_L(LinkList &L,int n){
// 创建含有n个元素的单链表
  LinkList p,q;
  int i;
  ElemType e;                   //L是头结点
  L = new LNode;
  L->next = NULL;              // 先建立一个带头结点的单链表
  q = L;
  for (i=0; i<n; i++) {
    scanf("%d", &e);
    p = new LNode;  // 生成新结点
    // 请补全代码
    p->data=e;
    p->next=NULL;
    q->next=p;
    q=p;
  }
  return OK;
}

int LoadLink_L(LinkList &L){   //这个函数写错了
// 单链表遍历
 LinkList p = L;
 if(p->next==NULL)printf("The List is empty!"); // 请填空
 else
 {
     printf("The LinkList is:");
     while(p->next!=NULL)    // 请填空
     {

         p=p->next;
        printf("%d ",p->data);
            

     }
 }
 printf("\n");
 return OK;
}

int LinkInsert_L(LinkList &L,int i,ElemType e){
// 算法2.9
// 在带头结点的单链线性表L中第i个位置之前插入元素e
// 请补全代码
    LinkList p=L;  //p记录首节点
    LinkList q=new LNode;
    L->next=p;
    if(i<1) return ERROR;
    for(int j=0;j<i-1;j++)
    {
        p=p->next;
    }
        q->next=p->next;
        p->next=q;
        q->data=e;
        return OK;
}

int LinkDelete_L(LinkList &L,int i, ElemType &e){
// 算法2.10
// 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
// 请补全代码
  /*LinkList p=L,q=L;
   int j=0;
   while(q->next)
   {
   for( j=0;j<i-1;j++)
   {
       p=p->next;  //指向删除数据前一个节点
   }
   for(int k=0;k<i;k++)
   {
       q=q->next;   //指向删除数据的节点
   }
   }
   if(!(p->next)||(j>i-1)) return ERROR;
   e=q->data;
   p->next=q->next;
   delete q;
   return OK;
*/
   LinkList p=L,q;
   int j=0;
   while((p->next)&&(j<i-1))
   {
       p=p->next;
       ++j;
   }
   if(!(p->next)||(j>i-1))
    return ERROR;
   q=p->next;
   p->next=q->next;
   delete q;
   return OK;


}

int main()
{
 LinkList T;
 int a,n,i;
 ElemType x, e;
 printf("Please input the init size of the linklist:\n");
 scanf("%d",&n);
 printf("Please input the %d element of the linklist:\n", n);
 if((CreateLink_L(T,n))==OK)   // 判断链表是否创建成功，请填空
 {
     printf("A Link List Has Created.\n");
     LoadLink_L(T);
 }
 while(1)
    {
        printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
        scanf("%d",&a);
        switch(a)
        {
            case 1: scanf("%d%d",&i,&x);
                  if((LinkInsert_L(T,i,x))==ERROR) printf("Insert Error!\n"); // 判断i值是否合法，请填空
                  else printf("The Element %d is Successfully Inserted!\n", x);
                  break;
            case 2: scanf("%d",&i);
                  if((LinkDelete_L(T,i,e))==ERROR) printf("Delete Error!\n"); // 判断i值是否合法，请填空
                  else printf("The Element %d is Successfully Deleted!\n", e);
                  break;
            case 3: LoadLink_L(T);
                  break;
            case 0: return 1;
        }
    }
}

```

Answer 1

引自免费微信小程序：皆我百晓生

首先，针对您提供的代码片段，我们来逐个分析和修正其中的问题：

1. CreateLink_L 函数中创建链表的循环内没有错误，但是初始化头结点时有点问题。应当将 L->next = NULL; 放在分配内存之后立即执行。

int CreateLink_L(LinkList &L, int n){
    // 创建含有n个元素的单链表
    L = new LNode;
    L->next = NULL;  // 先建立一个带头结点的单链表
    ...
}

1. 在 LoadLink_L 函数中遍历链表的部分，应当检查当前结点而非下一个结点是否为空：

int LoadLink_L(LinkList &L){   
    LinkList p = L;
    if(p == NULL) printf("The List is empty!"); // 修改为检查头结点是否为空
    else
    {
        printf("The LinkList is:");
        while(p != NULL)    // 遍历时应检查当前结点是否为空
        {
            printf("%d ", p->data);
            p = p->next;
        }
    }
    printf("\n");
    return OK;
}

1. LinkInsert_L 函数插入元素时，需要确保不会在第一次循环就结束（当 i=1 时）。同时，不需要为新节点 q 指向自身，应指向头结点。

int LinkInsert_L(LinkList &L, int i, ElemType e){
    LinkList p = L, q = new LNode;
    q->data = e;
    q->next = NULL;

    if(i < 1) return ERROR;
    
    for(int j = 0; j < i - 1 && p->next != NULL; ++j)
    {
        p = p->next;
    }

    q->next = p->next;
    p->next = q;

    return OK;
}

1. LinkDelete_L 函数中的删除操作已经实现正确，但注释部分有旧版未修改的代码，请移除注释或删除旧版代码。

下面是整个修改后的完整代码：

#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define ElemType int

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;

int CreateLink_L(LinkList &L, int n){
    // 创建含有n个元素的单链表
    L = new LNode;
    L->next = NULL;  
    int i;
    ElemType e;                   //L是头结点
    LinkList q = L;
    for (i=0; i<n; i++) {
        scanf("%d", &e);
        LinkList p = new LNode;  // 生成新结点
        p->data=e;
        p->next=NULL;
        q->next=p;
        q=p;
    }
    return OK;
}

int LoadLink_L(LinkList &L){   
    // 单链表遍历
    LinkList p = L;
    if(p == NULL) printf("The List is empty!"); 
    else
    {
        printf("The LinkList is:");
        while(p != NULL)    
        {
            printf("%d ",p->data);
            p = p->next;
        }
    }
    printf("\n");
    return OK;
}

int LinkInsert_L(LinkList &L, int i, ElemType e){
    LinkList p=L, q=new LNode;
    q->data=e;
    q->next=NULL;

    if(i<1) return ERROR;
    
    for(int j=0; j<i-1 && p->next!=NULL; ++j)
    {
        p=p->next;
    }

    q->next=p->next;
    p->next=q;

    return OK;
}

int LinkDelete_L(LinkList &L, int i, ElemType &e){
    LinkList p=L,q;
    int j=0;
    while((p->next)&&(j<i-1))
    {
        p=p->next;
        ++j;
    }
    if(!(p->next)||(j>i-1))
        return ERROR;
    q=p->next;
    p->next=q->next;
    e=q->data;
    delete q;
    return OK;
}

int main()
{
    LinkList T;
    int a,n,i;
    ElemType x, e;
    printf("Please input the init size of the linklist:\n");
    scanf("%d",&n);
    printf("Please input the %d element of the linklist:\n", n);
    if((CreateLink_L(T,n))==OK)   
    {
        printf("A Link List Has Created.\n");
        LoadLink_L(T);
    }
    while(1)
    {
        printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
        scanf("%d",&a);
        switch(a)
        {
            case 1: scanf("%d%d",&i,&x);
                  if((LinkInsert_L(T,i,x))==ERROR) printf("Insert Error!\n"); 
                  else printf("The Element %d is Successfully Inserted!\n", x);
                  break;
            case 2: scanf("%d",&i);
                  if((LinkDelete_L(T,i,e))==ERROR) printf("Delete Error!\n"); 
                  else printf("The Element %d is Successfully Deleted!\n", e);
                  break;
            case 3: LoadLink_L(T);
                  break;
            case 0: return 1;
        }
    }
}

现在这个程序应该可以正常创建、遍历、插入和删除带头结点的单链表了。