构建链表并排序
建立一个链表。将链表排序并输出。#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
}LNode;
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
int i;
int input;
LNode *L;
L = (LNode *)malloc(sizeof(LNode));
L -> next = NULL;
LNode *pre = L;
LNode *p;
for(i = 0; i < n; i++)
{
scanf("%d ", &input);
p = (LNode *)malloc(sizeof(LNode));
p -> next = NULL;
p -> data = input;
pre -> next = p;
pre = p;
}//创建链表
//直接插入排序
pre = L -> next;p = pre -> next;//pre指向p的前面
LNode *ppre = L;//插入时与pre用于定位
while(p != NULL)
{
if(p -> data >= pre -> data)
{
pre = p; p = p -> next;
}
else
{
LNode *t = pre;
pre = ppre -> next;
while(p -> data >= pre -> data)
{
ppre = pre; pre = pre -> next;
}
t -> next = p -> next;
p -> next = pre;
ppre -> next = p;
p = t -> next;
pre = t;
ppre = L;
}
}
p = L -> next;
for(i = 0; i < n; i++)
{
printf("%d ", p -> data);
p = p -> next;
}
printf("\n");
}
}
一定要给头结点也分配一个空间，否则会有非法访问的问题。
页:
[1]