Question

一道简单的数据结构问题

以链表作为文件的存储结构,对其实现起泡排序和直接选择排序,要准确的答案
这个也太多了,要简单点的如:
以数组为存储结构,实现其直接插入排序
INSERTSORT(R)
rectype R[];
{ int i,j;
for(i=2;i<n;i++)
{ R[0]=R[i];
j=i-1;
while(R[0].key<R[j].key)
R[j+1]=R[j--];
R[j+1]=R[0];
}
}

Answer 1

大哥，链表的操作有些时候比数组麻烦的多，我收藏的这两个算是写得比较好的程序了，代码应该精简不了多少
————————————————
刚好我有收藏

起泡排序：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef int DATA;
#define LINK_SIZE 20

struct node{
DATA data;
struct node *next;
};

struct node* head=NULL;

int init_link();
int output_link(struct node* head);
int clean_link(struct node* head);
int myrand(int seed);
struct node* bubble(struct node* lhead);

int main(void){
init_link();

output_link(head);

head = bubble(head);
printf("\nxxxxxxxxxxxx\n\n");
output_link(head);
/*clean memory*/
clean_link(head);

return 0;
}/*end of main*/

int init_link(){
int i=0;
struct node* tmp_node;
for(; i<LINK_SIZE; i++){
tmp_node=(struct node *)malloc(sizeof(struct node));
tmp_node->data = myrand((i+LINK_SIZE)+326547);
tmp_node->next = head;
head = tmp_node;
}/*end of for*/
return 0;
}/*end of init_link*/

int output_link(struct node* head){
struct node* tmp_node = head;
while(tmp_node){
printf("%d\n",tmp_node->data);
tmp_node = tmp_node->next;
}

return 0;
}/*end of output_link*/

int clean_link(struct node* head){
struct node* tmp_node;
while(head){
tmp_node = head;
head = head->next;
free(tmp_node);
}
return 0;
}/*end of clean_link*/

int myrand(seed){
seed = seed*1103515245 + 12345;
return (unsigned int)(seed/65536) % 32768;
}/*end myrand*/

struct node* bubble(struct node* lhead){
struct node *q,*tail,*p=(struct node*)malloc(sizeof(struct node));
p->next = lhead;
lhead = p;
tail = NULL;
while(tail != lhead->next){
p = lhead;
q = p->next;
while(tail != q->next){
if(p->next->data > q->next->data){
p->next = q->next;
q->next = q->next->next;
p->next->next = q;
}/*fi*/
p = p->next;
q = p->next;
}/*while in*/
tail = q;
}/*while out*/
p = lhead->next;
free(lhead);
return p;
}/*end of bubble*/

选择排序：
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}*Linklist,Node;
Linklist creat(int n)
{Linklist head,r,p;
int x,i;
head=(Node*)malloc(sizeof(Node));
r=head;
printf("输入数字:\n");
for(i=n;i>0;i--)
{scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;}
r->next=NULL;
return head;
} void output(Linklist head)
{Linklist p;
p=head->next;
do{
printf("%3d",p->data);p=p->next;
}while(p);
printf("\n");
} void paixu(Linklist head)
{Linklist p,q,small;int temp;

for(p=head->next;p->next!=NULL;p=p->next)
{small=p;
for(q=p->next;q;q=q->next)
if(q->data<small->data)
small=q;
if(small!=p)
{temp=p->data;
p->data=small->data;
small->data=temp;}
} printf("输出排序后的数字:\n");
output(head);
} void main()
{Linklist head;
int x,j,n;
printf("输入数字的个数(n):\n");
scanf("%d",&n);
head=creat(n);
printf("输出数字:\n");
output(head);
printf("已排序的数字:\n");
paixu(head);
}