C语言 创建一个排序的链表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16043709/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Create a sorted linked list
提问by NewUser
After almost 3 years, I've started relearning C.
将近3年后，我开始重新学习C。
I've created a Linked list, and would like to extend this to creating a sorted linked list. Here is my code:
我已经创建了一个Linked list，并希望将其扩展为创建一个排序的链表。这是我的代码：
typedef struct node{
int data;
struct node *ptr;
}node;
node* insert(node* head, int num){
node *temp,*prev,*next;
temp = (node*)malloc(sizeof(node));
temp->data = num;
temp->ptr = 'while(next->data<=num)
';
if(head=='while(next!='#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *ptr;
} node;
node* insert(node* head, int num) {
node *temp, *prev, *next;
temp = (node*)malloc(sizeof(node));
temp->data = num;
temp->ptr = NULL;
if(!head){
head=temp;
} else{
prev = NULL;
next = head;
while(next && next->data<=num){
prev = next;
next = next->ptr;
}
if(!next){
prev->ptr = temp;
} else{
if(prev) {
temp->ptr = prev->ptr;
prev-> ptr = temp;
} else {
temp->ptr = head;
head = temp;
}
}
}
return head;
}
void free_list(node *head) {
node *prev = head;
node *cur = head;
while(cur) {
prev = cur;
cur = prev->ptr;
free(prev);
}
}
int main(){
int num;
node *head, *p;
head = NULL;
do {
printf("Enter a number");
scanf("%d",&num);
if(num) {
head = insert(head, num);
}
} while(num);
p = head;
printf("\nThe numbers are:\n");
while(p) {
printf("%d ", p->data);
p = p->ptr;
}
free_list(head);
return 0;
}
' && next->data<=num)
'){
head=temp;
}else{
next = head;
prev = next;
while(next->data<=num){
prev = next;
next = next->ptr;
}
if(next==NULL){
prev->ptr = temp;
}else{
temp->ptr = prev->ptr;
prev-> ptr = temp;
}
}
return head;
}
void main(){
int num;
node *head, *p;
head = '##代码##';
do{
printf("Enter a number");
scanf("%d",&num);
if(num!=0)
head = insert(head,num);
}while(num!=0);
p = head;
printf("\nThe numbers are:\n");
while(p!='##代码##'){
printf("%d ",p->data);
p = p->ptr;
}
}
This is my idea. I traverse the list till I find a number >=the input. I store the previous node in prevand nextnode contains the current value. If next is null, then the list is ended and the number is the highest among the list so it is to be inserted in the last place, if the number is some where in the middle then, prev node's address part is stored in temp nodes address part now temp node pointer holds address of next node.
这是我的想法。我遍历列表，直到找到一个数字>=作为输入。我存储前一个节点prev，next节点包含当前值。如果 next 是null，则列表结束，并且列表中的数字是最高的，所以它会被插入到最后一个位置，如果数字是中间的某个位置，则 prev 节点的地址部分存储在临时节点地址中现在部分临时节点指针保存下一个节点的地址。
Edit:Problem with my code is if I enter 1,2 I get error message as a.exe has stopped working. I am using MinGW for compiling. I am breaking the loop when user inputs 0.
编辑：我的代码的问题是，如果我输入 1,2，我会收到错误消息a.exe has stopped working。我正在使用 MinGW 进行编译。当用户输入 0 时，我正在打破循环。
回答by halex
You have to change the line
你必须改变线路
##代码##to
到
##代码##When you insert the second element nextwill be '\0'at the second iteration and trying to get the field datawith next->datawill lead to a segmentation fault.
当您插入第二个元素next将'\0'在第二次迭代，并试图让现场data用next->data会导致分段错误。
With the changed condition in the while if next!='\0'will be false (hence next=='\0') the while is aborted and because of &&'s shortcircuiting next->datais not computed.
随着 while if 中条件的改变next!='\0'为假（因此next=='\0'） while 被中止并且由于&&的短路next->data不被计算。
EDIT
编辑
You have more problems in your code.
您的代码中存在更多问题。
If you look at the input 2 1 0then the output with a correctly working program should be 1 2but it's 2 1instead. Teh problem is that in your insertfunction you do not consider the case where you insert the current smallest element that will be the new head.
如果您查看输入，2 1 0那么具有正确工作程序的输出应该是1 2但它是2 1相反的。问题是，在您的insert函数中，您没有考虑插入将成为新头的当前最小元素的情况。
Another problem is that you do not free the malloced memory at the end, which leads to memory leaks.
另一个问题是你最后没有释放malloced内存，这会导致内存泄漏。
I changed your code to behave correctly:
我更改了您的代码以使其行为正确：
##代码##See https://ideone.com/wT5iQ8for my code on a testinput together with the correct output.
请参阅https://ideone.com/wT5iQ8，了解我在 testinput 上的代码以及正确的输出。
