/*---------------------------------------------------
-Thuat Toan: Bubble Sort (Sap Xep Noi Bot)
-Kieu: Pointer (Dung con tro).
----------------------------------------------------*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <dos.h>
struct Node
{
int Value;
Node *Next;
};
typedef Node *List;
typedef Node *Position;
// Tao DS Rong
void MakeNullList(List L)
{
L->Next=NULL;
}
//Nhap DS
void InsertList(List L)
{
Node *newnode=new Node;
Position P;
L->Next=newnode;
P=newnode;
int Sophantu=2;
printf("Nhap phan tu thu 1:");
scanf("%d",&newnode->Value);
// cac phan tu tiep theo
while(1)
{
Node *newnode=new Node;
newnode->Next=NULL;
printf("Phan tu thu %d: ",Sophantu);
Sophantu+=1;
scanf("%d",&newnode->Value);
if(newnode->Value==0)
{
free(newnode);
break;
}
P->Next=newnode;
P=newnode;
}
}
//In DS
void ShowList(List L)
{
Position P=L->Next;
while(P!=NULL)
{
printf("|%d|",P->Value);
P=P->Next;
}
}
// Vi tri con tro cua phan tu cuoi DS
Position LastList(List L)
{
Position P=L->Next;
while(P->Next!=NULL)
{
P=P->Next;
}
return P;
}
// Vitri con tro truoc vi tri P0 trong DS L
Position TruocP(List L,Position P0)
{
Position P1=L;
while(P1->Next!=P0&&P1!=NULL)
{
P1=P1->Next;
}
return P1;
}
//Doi cho 2 phan tu co vi dia chi con tro la P1,P2 trong DS L
void Swap(List L,Position P1,Position P2)
{
Node *newnode1=new Node;
Node *newnode2=new Node;
newnode1->Value=P1->Value;
newnode2->Value=P2->Value;
newnode1->Next=P2->Next;
TruocP(L,P2)->Next=newnode1;
newnode2->Next=P1->Next;
TruocP(L,P1)->Next=newnode2;
free(P1);
free(P2);
}
// So Phan tu trong DS
int LengthList(List L)
{
int len=0;
Position P=L;
while(P->Next!=NULL)
{
len+=1;
P=P->Next;
}
return len;
}
//Lay dia chi con tro cua phan tu co thu tu "vitri" trong DS
Position ConverntXToP(List L,int vitri)
{
Position P=L;
for(int index=1;index<=vitri;index++)
{
P=P->Next;
}
return P;
}
// Sap xep noi bot
void BubbleSort(List L)
{
for(int index1=1;index1<LengthList(L);index1++)
{
for(int index2=LengthList(L);index2>index1;index2--)
{
Position P1=ConverntXToP(L,index2-1);
Position P2=ConverntXToP(L,index2);
if(P1->Value>P2->Value)
{
Swap(L,P1,P2);
}
}
}
}
void main()
{
clrscr();
List L1;
MakeNullList(L1);
InsertList(L1);
ShowList(L1);
BubbleSort(L1);
printf("\n");
ShowList(L1);
getch();
}
nosomovo
