Question

跪求c语言高手 一道关于单链表尾插法的问题

以下是一个头插法的单链表程序
#include <stdio.h>
#include <stdlib.h>

#define MAX
5

typedef struct data Data;
typedef struct data *DataP;

struct
data{
int val;
DataP prev;
};

DataP add_data(int i,DataP
last);
void print_data(DataP last);
void free_list(DataP last);

int
main()
{
int i;
DataP last =
NULL;

for(i=0;i<MAX;++i){
last =
add_data(i,last);
}

print_data(last);
free_list(last);
exit(0);
}

DataP
add_data(int i,DataP last)
{
DataP new;
if((new =
(DataP)malloc(sizeof(Data))) == NULL){
fprintf(stderr,"data allocation error
!\n");
exit(1);
}
new -> val = i;
new -> prev =
last;
return new;
}

void print_data(DataP last)
{
while(last
!= NULL){
printf("output data %d\n",last -> val);
last = last ->
prev;
}
}

void free_list(DataP last)
{
DataP
olast;

while(last != NULL){
olast = last;
last = last ->
prev;
free(olast);
}
}

这个程序的运行结果如下
output data 4
output data 3
output data 2
output data 1
output data 0
问题：如何改动以上程序，让运行的结果从小到大输出，我也知道是将add函数那一块改成尾插法插入，但改了几次，运行时程序总停止，得不到正确结果，希望有好心人帮我改动一下，保证正常运行，万分感激！

Answer 1

last = last -> prev;你这是尾插法吗？
感觉应该是头插法吧
你把new的节点放到last的最前面了吧
尾插法，应该有个循环，判断一下是否到尾部吧
加入代码
while(last->prev!=NULL)
last=last->prev;
这样last就是指向最后一个节点的指针了

再让new肤质给last-prev

还有一个问题，new是不是c的保留字啊，你就让他当变量来用

追问

原来的程序是头插法，现再就是想请教改称尾插法的方法

我把new已经改成newp了，还有除了add函数那一块，主函数main也要改动吧

追答

我已经说得很清楚了，非要我给你全部代码啊，呵呵
DataP add_data(int i,DataP last)
{
DataP new,p;
p=last;
if((new = (DataP)malloc(sizeof(Data))) == NULL)
{
fprintf(stderr,"data allocation error !\n");
exit(1);
}
new -> val = i;
while(last->prev!=NULL)
last=last->prev;
last -> prev = new;
return p; //其实这个完全可以不要
}
子函数完全可以用void不返回值得，因为尾插法，head不变

追问

谢谢大侠

大侠照你说的改了 可运行时出现以下错误：
Segmentation fault（core dumped）
还望指教

追答

你以前代码没问题，这个应该也没有问题的
这个错误说是内存访问越界，你屏蔽几个函数看看

Answer 2

最简单的方法就是把你main里面的for循环改成for(i=MAX;i>0;i--)。
如果想从0开始输出的话就改成for(i=MAX-1;i>=0;i--)

追问

这样改的确可以，但还是想请教下改成尾插法的方法

追答

要是想改成尾插法的话，可以这样改
DataP add_data(int i,DataP last)
{
DataP Pnew;
if((Pnew = (DataP)malloc(sizeof(Data))) == NULL)
{
fprintf(stderr,"data allocation error !\n");
exit(1);
}
Pnew -> val = i;
if(last!=NULL)/////////添加这两句
last->prev=Pnew;////////////添加这两句
Pnew -> prev = NULL;////////////修改这一句
return Pnew;
}
但是改完之后，他只会输出一个4，原因是在你主函数里面，last指针一直是变动的，当完成for循环之后，他就在4这个位置，所以输出值能输出一个4。这就是你头节点的问题了。
你可以在主函数里面这样改：
int main()
{
int i;
DataP last = NULL;
DataP head;//定义一个头结点；
for(i=0;i<MAX;i++)
{
last = add_data(i,last);
if(!i)//这个地方就是当for循环第一次的时候，把获得的这第一个链表节点赋给头节点
head=last;//这个地方就是当for循环第一次的时候，把获得的这第一个链表节点赋给头节点

}
print_data(head);/*然后接下来就是输出传入头结点，然后就会从第一个节点开始往后遍历，就可以全部输出出来了*/
free_list(head);//释放节点也是一样的，从第一个头结点开始释放
return 0;
}
这样基本上就正常了

追问

谢谢 待会儿运行一下

追答

还有一个问题是你add_data这个函数里面，new好像不能直接当做变量来用，所以我就给你改了一下，改成Pnew了，编译正确，不影响结果

追问

谢谢

刚才请教的尾插法已经运行过了，输出顺序的确与之前相反，不愧是高手，在这儿我还有个问题，就是想请教下基于之前的程序用单链表尾插法找质数的方法，以下是头插法找质数的方法，按照你之前的回复改了下add和main的部分，可这回却不能正确输出结果，所以想请教下，如何改动，输出质数的顺序是从小到大

追答

单链表尾插法找质数？额。。不太理解，举个例子，该怎么输入输出，输出什么数据之类的，刚刚关电脑了。

追问

等一下 手机不太好发 我用下电脑

追答

没事

追问

能告诉下你的邮箱吗？我现在提问不了，想通过邮件发过去

拜托了，感激不尽，困扰我好久了

以上是程序
结果
比如输入9，打印出来的质数就是7532的顺序

后面两张清楚些

追答

额。。不好意思了，我刚刚一直在看教学视频，然后没有上知道，我的qq就是我的百度知道的用户名。。。- -！
不好意思
如果你是按照你一开始的程序运行找质数的话，那输出是从大到小就是正常的，因为你的last指针循环玩之后就是最大的那个，然后输出就会是从大到小。把主函数里面的for改成从大到小循环的就可以了。如果要换成尾插法的话等一会啊，我运行试试。
好了，你可以这样改，在前面改成尾插法的基础上吧这个for循环里面改成这样，其实就是把if里面的last改成head。然后加上大括号。。。最开始定义head的时候把它初始化为NULL，要不会出错
for(i=2;i<n;i++)
{
if(check(i,head))//这个地方last改成head
{///
last = add_data(i,last);//
if(i==2)///////////这个地方改成这个i==2
head=last;
}
}

追问

不愧是大侠 超级感谢

追答

- -！额。。这也是错很多次才改好的。。。