Mình gui them bai con tro nua ne.
CON TRỎ
#include<iostream>
#include<conio.h>
using namespace std;
typedef int ElementType; //kiểu của phần tử trong danh sách
struct Node
{
ElementType Element; //Chứa nội dung của phần tử
Node *Next; //con trỏ chỉ đến phần tử kế tiếp
};
typedef Node* Position; //Kiểu vị trí
typedef Position List;
//Tao list moi
void MakeNull_List(List *Header)
{
(*Header)=new Node[sizeof(Node)];
(*Header)->Next= NULL;
}
//Kiem tra list rong
int Empty_List(List L)
{
return (L->Next==NULL);
}
//Lay vi tri cua noi dung X trong list
Position Locate(ElementType X, List L)
{ Position P;
int Found = 0;
P = L;
while ((P->Next != NULL) && (Found == 0))
if (P->Next->Element == X)
Found = 1;
else P = P->Next;
return P;
}
//Lay noi dung cua vi tri P trong list
ElementType Retrieve(Position P, List L)
{
Position i;
i=new Node[sizeof(Node)];
if (P->Next!=NULL)
i->Element=P->Next->Element;
return i->Element ;
}
//Vi tri dau list
Position First(List L)
{
return L;
}
//Vi tri cuoi list
Position EndList(List L)
{
Position P;
P=First(L);
while (P->Next!=NULL)
P=P->Next;
return P;
}
//Vi tri ke tiep
Position Next(Position P, List L)
{
return P->Next;
}
//Them vao list
void Insert_List(ElementType X,int P, List *L)
{
Position i;
int vitri=1;
i=new Node[sizeof(Node)];
i=First(*L);
while ((i->Next!=NULL) && (vitri<P))
{
vitri+=1;
i=i->Next ;
}
if (vitri==P)
{
Position T;
T=new Node[sizeof(Node)];
T->Element=X;
T->Next=i->Next;
i->Next=T;
}
}
//Xoa phan tu tai vi tri P trong list
void Delete_List(int P, List *L)
{
Position i,Temp;
int vitri=1;
i=new Node[sizeof(Node)];
i=First(*L);
while ((i->Next!=NULL) && (vitri<P))
{
vitri+=1;
i=i->Next ;
}
if (vitri==P)
{
Temp=i->Next;
/*giữ ô chứa phần tử bị xoá để thu hồi vùng nhớ*/
i->Next=Temp->Next;
/*nối kết con trỏ trỏ tới phần tử ke tiep*/
free(Temp); //thu hồi vùng nhớ
}
}
//Xoa phan tu trung voi noi dung X
void DeleteX_List(ElementType X, List *L)
{
Position P,Temp;
int found=0;
P=new Node[sizeof(Node)];
P=First(*L);
while (P!=EndList(*L))
{
if (Retrieve(P,*L)==X)
{
Temp=P->Next;
/*giữ ô chứa phần tử bị xoá để thu hồi vùng nhớ*/
P->Next=Temp->Next;
/*nối kết con trỏ trỏ tới phần tử ke tiep*/
free(Temp); //thu hồi vùng nhớ
}
else
P = Next(P,*L);
}
}
//Ghi phan tu vao list
void WriteList(List *L)
{
int n,i;
ElementType X;
cout<<"Nhap so phan tu danh sach lien ket: ";cin>>n;
for (i=1;i<=n;i++)
{
cout<<"Nhap phan tu thu "<<i<<" : ";
cin>>X;
Insert_List(X,i,L);
}
}
//Hien thi ra man hinh
void PrintList(List L)
{
Position P;
P = First(L);
while (P != EndList(L))
{
cout<<Retrieve(P,L);
P = Next(P, L);
}
cout<<"\n";
}
// Dem so phan tu trong list
int count(List L)
{
int dem=0;
Position P;
P=First(L);
while (P!=EndList(L))
{
dem++;
P = Next(P, L);
}
return dem;
}
//Tong cac phan tu trong list
float sum(List L)
{
float s=0;
Position P;
P=First(L);
while (P!=EndList(L))
{
s+=Retrieve(P,L);
P = Next(P, L);
}
return s;
}
//Tong noi dung X trong list
float sumX1(ElementType X,List L)
{
float s=0;
Position P;
P=First(L);
while (P!=EndList(L))
{
if (Retrieve(P,L)==X)
s+=Retrieve(P,L);
P = Next(P, L);
}
return s;
}
//Tong noi dung X trong list
float sumX2(ElementType X,List L)
{
float dem=0;
Position P;
P=First(L);
while (P!=EndList(L))
{
if (Retrieve(P,L)==X)
dem++;
P = Next(P, L);
}
return X*dem;
}
//Dem noi dung X trong list
int countX(ElementType X,List L)
{
int dem=0;
Position P;
P=First(L);
while (P!=EndList(L))
{
if (Retrieve(P,L)==X)
dem++;
P = Next(P, L);
}
return dem;
}
//Sap xep list tang dan
void sort_asc(List *L)
{
Position p,q;
ElementType temp;
p=First(*L);
while (p!=EndList(*L))
{
q=Next(p,*L);
while (q!=EndList(*L))
{
if (Retrieve(p,*L)>Retrieve(q,*L))
{
temp = p->Next->Element;
p->Next->Element = q->Next->Element;
q->Next->Element = temp;
}
q=Next(q,*L);
}
p=Next(p,*L);
}
}
//Sap xep list giam dan
void sort_desc(List *L)
{
Position p,q;
ElementType temp;
p=First(*L);
while (p!=EndList(*L))
{
q=Next(p,*L);
while (q!=EndList(*L))
{
if (Retrieve(p,*L)<Retrieve(q,*L))
{
temp = p->Next->Element;
p->Next->Element = q->Next->Element;
q->Next->Element = temp;
}
q=Next(q,*L);
}
p=Next(p,*L);
}
}
//Them phan tu vao list van tang dan (giam dan)
void add_dontchange(ElementType X,List *L)
{
int vitri=1;
Position p;
p=First(*L);
while(p!=EndList(*L)&& Retrieve(p,*L)<=X)
{
vitri++;
p=Next(p,*L);
}
Insert_List(X,vitri,L);
}
// Tron 2 list thanh list moi tang dan
void connect(List *L1,List *L2,List *L3)
{
int vitri=1;
Position p,q;
p=First(*L1);
q=First(*L2);
while ((p!=EndList(*L1)) && (q!=EndList(*L2)))
{
if(Retrieve(p,*L1)>Retrieve(q,*L2))
{
Insert_List(Retrieve(q,*L2),vitri,L3);
q=Next(q,*L2);
}
else
{
Insert_List(Retrieve(p,*L1),vitri,L3);
p=Next(p,*L1);
}
vitri++;
}
while (q!=EndList(*L2))
{
Insert_List(Retrieve(q,*L2),vitri,L3);
vitri++;
q=Next(q,*L2);
}
while (p!=EndList(*L1))
{
Insert_List(Retrieve(p,*L1),vitri,L3);
vitri++;
p=Next(p,*L1);
}
PrintList(*L3);
}
void main()
{
List *L1,*L2,*L3;
//int n;
//ElementType X;
L1=new List[sizeof(List)];
MakeNull_List(L1);
L2=new List[sizeof(List)];
MakeNull_List(L2);
L3=new List[sizeof(List)];
MakeNull_List(L3);
WriteList(L1);
cout<<"Danh sach lien ket 1: ";
PrintList(*L1);
sort_asc(L1);
WriteList(L2);
cout<<"Danh sach lien ket 2: ";
PrintList(*L2);
sort_asc(L2);
cout<<"Danh sach lien ket 3: ";
connect(L1,L2,L3);
/*
cout<<"Nhap phan tu can xoa: ";cin>>X;
DeleteX_List(X,L);
PrintList(*L);
cout<<"Nhap vi tri phan tu can xoa: ";cin>>n;
Delete_List(n,L);
PrintList(*L);
cout<<"So phan tu trong danh sach lien ket: "<<count(*L)<<endl;
cout<<"Nhap phan tu can tim: ";cin>>X;
cout<<"So lan phan tu "<<X<<" xuat hien trong danh sach lien ket: "<<countX(X,*L)<<endl;
cout<<"Tong phan tu trong danh sach lien ket: "<<sum(*L)<<endl;
cout<<"Nhap phan tu can tinh tong: ";cin>>X;
cout<<"Tong phan tu "<<X<<" trong danh sach lien ket: "<<sumX2(X,*L)<<endl;
cout<<"Danh sach lien ket da duoc sap xep: \n";
sort_asc(L);
PrintList(*L);
cout<<"Nhap phan tu can them: ";cin>>X;
add_dontchange(X,L); //them phan tu ma list van khong doi
PrintList(*L);
*/
}