harleydavidsons
20-04-2009, 23:10
Em đang học về Cấu trúc dữ liệu. Có bài tập dùng Shell Sort để sắp xếp danh sách liên kết. Em dùng ý tưởng cài đặt Shell Sort của mảng, áp dụng vào DSLK. Mấy huynh chỉ dùm em xem sai chỗ nào nhé, hoặc làm giúp em bài Shell Sort(DSLK) với . Em sắp thi môn CTDL rồi. Thanks mấy Huynh trước nhá!!
code:
#include<conio.h>
#include<stdio.h>
#include<alloc.h>
typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
};
//---------Ham tao Node-----------
Node *GetNode(int x)
{
Node *p;
p=(Node*) malloc( sizeof(Node) );
if(p==NULL)
printf("\nLoi cap phat!");
else
{
p->data=x;
p->left=NULL;
p->right=NULL;
}
return p;
}
//---------Khoi tao danh sach-----------
Node* Createlist()
{
return ((Node*) NULL);
}
//---------Kiem tra danh sach rong------
int Emptylist(Node *List)
{
if(List==NULL)
return 1;
else
return 0;
}
//---------Ham chen cuoi-----------
void Insertl(Node *&List,Node *&q,int x)
{
Node *p=GetNode(x);
if(Emptylist(List)==1)
{
List=p;
q=p;
}
else
{
q->right=p;
p->left=q;
q=p;
}
}
//---------Ham nhap--------------
void Input(Node *&List, int &n)
{
// List=Createlist();
Node *q=NULL;
int x;
printf("\nNhap du lieu(0 de dung):\n ");
do
{
printf("\nNhap ptu: ");
scanf("%d",&x);
if(x)
{
Insertl(List,q,x);
n++;
}
}while(x);
}
//-------Ham Duyet DS----------------
void Traverse(Node *List)
{
if(Emptylist(List)==1)
printf("\nDanh sach rong.");
else
{
do
{
printf("%3d",List->data);
List=List->right;
}while(List!= NULL);
}
}
//-------Ham lay node----------------
Node *Get(Node *List, int k)
{
int i=0;
while(List!=NULL&&i<k)
{
List=List->right;
i++;
}
return List;
}
//-------Ham Insert Sort-------------
void InsertionSort(Node *List, int k)
{
int i,j;
int x;
Node *p,*l,*q;
for(i=k,p=Get(List,k);p!=NULL;p=p->right,i++)
{
x=p->data;
for(j=i-k,l=Get(List,i-k);l!=NULL&&x<l->data;l=l->left,j=j-k)
{
q=Get(List,j+k);
q=l;
}
q->data=x;
}
}
//-------Ham Shell Sort--------------
void ShellSort(Node *&List,int n)
{
int k;
do{
k=n/3+1;
InsertionSort(List,k);
}while(k>0);
}
//-------Ham Main--------------------
void main()
{
clrscr();
int n=0;
Node *List=NULL;
Node *q=NULL;
Input(List,n);
ShellSort(List,n);
Traverse(List);
getch();
}
code:
#include<conio.h>
#include<stdio.h>
#include<alloc.h>
typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
};
//---------Ham tao Node-----------
Node *GetNode(int x)
{
Node *p;
p=(Node*) malloc( sizeof(Node) );
if(p==NULL)
printf("\nLoi cap phat!");
else
{
p->data=x;
p->left=NULL;
p->right=NULL;
}
return p;
}
//---------Khoi tao danh sach-----------
Node* Createlist()
{
return ((Node*) NULL);
}
//---------Kiem tra danh sach rong------
int Emptylist(Node *List)
{
if(List==NULL)
return 1;
else
return 0;
}
//---------Ham chen cuoi-----------
void Insertl(Node *&List,Node *&q,int x)
{
Node *p=GetNode(x);
if(Emptylist(List)==1)
{
List=p;
q=p;
}
else
{
q->right=p;
p->left=q;
q=p;
}
}
//---------Ham nhap--------------
void Input(Node *&List, int &n)
{
// List=Createlist();
Node *q=NULL;
int x;
printf("\nNhap du lieu(0 de dung):\n ");
do
{
printf("\nNhap ptu: ");
scanf("%d",&x);
if(x)
{
Insertl(List,q,x);
n++;
}
}while(x);
}
//-------Ham Duyet DS----------------
void Traverse(Node *List)
{
if(Emptylist(List)==1)
printf("\nDanh sach rong.");
else
{
do
{
printf("%3d",List->data);
List=List->right;
}while(List!= NULL);
}
}
//-------Ham lay node----------------
Node *Get(Node *List, int k)
{
int i=0;
while(List!=NULL&&i<k)
{
List=List->right;
i++;
}
return List;
}
//-------Ham Insert Sort-------------
void InsertionSort(Node *List, int k)
{
int i,j;
int x;
Node *p,*l,*q;
for(i=k,p=Get(List,k);p!=NULL;p=p->right,i++)
{
x=p->data;
for(j=i-k,l=Get(List,i-k);l!=NULL&&x<l->data;l=l->left,j=j-k)
{
q=Get(List,j+k);
q=l;
}
q->data=x;
}
}
//-------Ham Shell Sort--------------
void ShellSort(Node *&List,int n)
{
int k;
do{
k=n/3+1;
InsertionSort(List,k);
}while(k>0);
}
//-------Ham Main--------------------
void main()
{
clrscr();
int n=0;
Node *List=NULL;
Node *q=NULL;
Input(List,n);
ShellSort(List,n);
Traverse(List);
getch();
}