Question

关于链表的一段错误程序 运行时到一半时会出错

#include<stdio.h>
#include<stdlib.h>

#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//增强语言描述功能

typedef int Status;

typedef struct ElemType{

float coef;

int expn;
}ElemType;

typedef struct LNode{

ElemType data;

struct LNode *next;
}LinkList,*Polynomial;

//构造一个空链表
Status InitList(Polynomial L){

L = (Polynomial)malloc(sizeof(LNode));

if (!L) exit(OVERFLOW);

(*L).next = NULL;

return OK;
}

//在链表尾加入节点
Status MakeNode(Polynomial L, ElemType e){

Polynomial q;

Polynomial p = L;

q = (Polynomial)malloc(sizeof(LNode));

if (!q) exit(OVERFLOW);

(*q).data = e;

(*q).next = NULL;

while (NULL != (*L).next)

{

L = (*L).next;

}

(*L).next = q;

return OK;
}

//销毁线性表L，L不再存在
Status DestroyList(Polynomial L){

Polynomial q;

q = L;

while (NULL != (*L).next)

{

L = (*q).next;

free(q);

q = L;

}

return OK;
}

//判断e是否在L中，是则返回OK，否则返回ERROR
Status LocateElem(Polynomial L, ElemType e){

ElemType temp;

while (NULL != (*L).next)

{

temp = (*L).data;

if (e.coef == temp.coef && e.expn == temp.expn) return OK;

L = (*L).next;

}

return ERROR;
}

//建立一个多项式链表
void CreatPolyn(Polynomial L,int n){

int m=0,i=0;

Polynomial p=L;

ElemType e;

InitList(L);

e.coef = 0.0; e.expn = -1;

(*L).data = e;

printf("The number of %d List:", n);

scanf_s("%d", &m);//scanf可能会造成内在泄露

for (i = 1; i <= m; i++)

{

printf("number %d", i);

printf("\ncoef is: "); scanf_s("%d", &e.coef);

printf("expn is: "); scanf_s("%d", &e.expn);

MakeNode(L, e);

p = (*p).next;

}
}

void main()
{

LinkList PA, PB;

Polynomial A=&PA,B=&PB;

CreatPolyn(A, 1);

CreatPolyn(B, 2);
}

Answer 1

上述程序中，求倒数第k个结点的第一个方法：ListNode* KthNodeFromEnd(ListNode* pHead,int k)。
这个方法看似满足了我们的题目要求，但是当我们仔细分析，发现有3中方法让程序崩溃
1.输入的pListHead为空指针，由于代码会尝试访问空指针指向的内存，程序崩溃
2.输入的以pListHead为头结点的链表的结点少于k。这样在while(k-1>0)的循环中，又会出现尝试访问空指针指向的内存。
3.输入的参数k小于等于0。根据题意k的最小值应为1。
考虑上述因素，我们给出了第二个方法：ListNode* KthNodeFromEnd2(ListNode* pHead,int k)。