Question

一道C语言有关链表的简单问题

随意输入5个数字，将它们由大到小排序并输出出来，要求使用链表的方法解决。最好把注释也写到每一步，详细的会有额外的加分，谢谢！

Answer 1

以下程序完全用C写的，希望能够满足你的要求，如果需要一边插入一边排序，可以参照插入排序的代码自行编写一个。当然，如果用C++，可以精简一些
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>/*微机版本可能需要加上这个头文件*/

typedef int datatype;
struct node /*链表结点类型定义*/
{
datatype data; /*链表数据域*/
struct node *next; /*链表指针域*/
};
typedef struct node * LinkList;
void Initial(LinkList *head)
{ /*构建有头结点的单链表*/
struct node *first;
first = (struct node *)malloc(sizeof(struct node));
first->next = NULL; /*尾标志*/
*head = first;
}
void Destroy(LinkList *head)
{ /*从头开始顺序释放链表所有结点空间*/
struct node *first, *p;
first = *head;
while (first != NULL)
{
p = first;
first = first->next;
free(p);
}
*head = NULL;
}
void InsertSort(LinkList first)
{ /*链表插入排序*/
struct node *p, *q, *r, *s;
if (first->next == NULL) /*空表不用排序*/
return;
r = first->next;
if (r->next == NULL)/*一个结点也不用排序*/
return;
p = r->next; /*从第二个结点开始插入排序*/
r->next = NULL; /*断掉链表*/
while (p != NULL) /*待排序链表还有结点*/
{
q = first->next; /*q为当前比较结点，r为其前驱*/
r = first;
while (q != NULL && q->data <= p->data)
{ /*寻找插入点，递减排序*/
r = q;
q = q->next;
}
s = p; /*摘下当前结点*/
p = p->next;
s->next= r->next; /*插入到链表中*/
r->next = s;
}
}
void Print(LinkList first)
{ /*输出链表数据*/
struct node *p;
p = first->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void InsertFront(LinkList first, int n)
{ /*输入n 个数据，插入链表中，表头插入*/
struct node *p;
datatype x;
int i;
for (i = 0; i < n; ++ i)
{
scanf("%d", &x);
p = (struct node *)malloc(sizeof(struct node));
p->data = x;
p->next = first->next;
first->next = p;
}
}
int main( ) /*主函数示意*/
{
LinkList list1;
Initial(&list1); /*初始化链表*/
InsertFront(list1, 5); /*插入5个结点*/
Print(list1); /*输出链表*/
InsertSort(list1); /*链表插入排序*/
Print(list1); /*再次输出链表*/
Destroy(&list1); /*销毁链表*/
return 0;
}