Bài tập danh sách liên kết đơn

10/02/1994


	tvt-12cth1 Admin

posts : 114

Points : 10236

avatar-dulieu : 57,11757|50,11908|49,10855|64,12636|51,11463|48,12290|58,12220|66,11458

Thanked : 12

Birthday : 10/02/1994

Age : 30

Bài 1

Code:: #include <iostream.h> #include <conio.h> struct node { int data; node *next; }; typedef struct node* List; //gan List bang node* //****************************************************************************** List CreateNewNode(int data) { List temp=new node(); if(temp==NULL) { cout<<"Khong du bo nho"; exit(0); } temp->data=data; temp->next=NULL; return temp; } //****************************************************************************** void InsertNewNodeAtFirst(List newnode,List &pHead) { if(pHead==NULL) pHead=newnode; else { newnode->next=pHead; pHead=newnode; } } //****************************************************************************** void InsertNewNodeAtLast(List newnode,List pHead) { if(pHead==NULL) pHead=newnode; else { List temp=pHead; while(temp->next!=NULL) temp=temp->next; temp->next=newnode; } } //****************************************************************************** void InsertNewNodeAtAfter(node *newnode,node *nodetimthay,List pHead) { if(pHead==NULL) cout<<"Danh sach rong"; else { newnode->next=nodetimthay->next; nodetimthay->next=newnode; } } //****************************************************************************** void display(List pHead) { if(pHead==NULL) cout<<"Danh sach rong"; else { while(pHead!=NULL) { cout<<pHead->data<<" "; pHead=pHead->next; } } } //****************************************************************************** node *Find(int data,List pHead) { if(pHead==NULL) cout<<"Danh sach rong"; else { node *t=pHead; while(t!=NULL && t->data!=data) t=t->next; return t; } } //****************************************************************************** void DeleteNodeAtFirst(List &pHead) { if(pHead==NULL) cout<<"Danh sach rong"; else { node *p=pHead; pHead=pHead->next; delete p; } } //****************************************************************************** void DeleteNodeAtLast(List pHead) { if(pHead==NULL) cout<<"Danh sach rong"; else { node *p=pHead; node *t=NULL; while(p->next!=NULL) { t=p; p=p->next; } t->next=NULL; delete p; } } //****************************************************************************** void DeleteAll(List &pHead) { if(pHead==NULL) cout<<"Danh dach rong"; else { while(pHead!=NULL) DeleteNodeAtFirst(pHead); } } //****************************************************************************** int main() { int chon,n; List pHead=NULL; do { system("cls"); cout<<"1.Hien thi danh sach\n"; cout<<"2.Tim Node dau tien\n"; cout<<"3.Them mot Node vao dau danh sach\n"; cout<<"4.Them mot Node vao cuoi danh sach\n"; cout<<"5.Them mot Node sau Node nao do\n"; cout<<"6.Huy Node dau tien\n"; cout<<"7.Huy Node cuoi cung\n"; cout<<"8.Huy Node bat ki\n"; cout<<"9.Huy toan bo danh sach\n"; cout<<"10.Exit\n"; cout<<"Chon: "; cin>>chon; system("cls"); switch(chon) { case 1: display(pHead); getch(); break; case 2: cout<<"Nhap Vao 1 So Tim: "; cin>>n; if(Find(n,pHead)==NULL) cout<<"Khong Tim Thay"; else cout<<"So Can Tim Ton Tai Trong Danh Sach"; getch(); break; case 3: cout<<"Nhap Vao 1 so: "; cin>>n; InsertNewNodeAtFirst(CreateNewNode(n),pHead); display(pHead); getch(); break; case 4: cout<<"Nhap Vao 1 so: "; cin>>n; InsertNewNodeAtLast(CreateNewNode(n),pHead); display(pHead); getch(); break; case 5: display(pHead); int x; cout<<"\nNhap Vi Tri Muon Add: "; cin>>x; List nodetimthay=Find(x,pHead); if(nodetimthay==NULL) cout<<"Khong Tim Thay, Khong The Add"; else { cout<<"\nNhap Vao 1 So: "; cin>>n; InsertNewNodeAtAfter(CreateNewNode(n),nodetimthay,pHead); display(pHead); } getch(); break; case 6: DeleteNodeAtFirst(pHead); display(pHead); getch(); break; case 7: DeleteNodeAtLast(pHead); display(pHead); getch(); break; /*case 8: display(pHead); cout<<"\nNhap So Muon Xoa: "; cin>>n; if(Find(pHead,n)==NULL) cout<<"Khong Tim Thay, Khong The Xoa"; else { DeleteNodeAny(pHead,n); display(pHead); } getch(); break;*/ case 9: DeleteAll(pHead); break; } }while(chon!=10); }

Bài 2

Code:: #include <iostream.h> #include <conio.h> struct Node { int data; Node *next; }; typedef struct Node* List; //****************************************************************** List CreateNewNode(int data) { List temp=new Node(); if(temp!=NULL) { temp->data=data; temp->next=NULL; } return temp; } //****************************************************************** void InsertNewNodeAtFirst(List newnode, List &pHead,List &pTail) { if(pHead==NULL) pHead=pTail=newnode; else { newnode->next=pHead; pHead=newnode; } } //****************************************************************** void InsertNewNodeAtLast(List newnode, List &pHead,List &pTail) { if(pHead==NULL) pHead=pTail=newnode; else { pTail->next=newnode; pTail=newnode; } } //****************************************************************** void InsertNewNodeAtAfter(List nodetimthay,List newnode,List pTail,List pHead) { if(pTail->data==nodetimthay->data) InsertNewNodeAtLast(newnode,pHead,pTail); else { newnode->next=nodetimthay->next; nodetimthay->next=newnode; } } //****************************************************************** int Count(List pHead) { int count=0; while(pHead!=NULL) { count++; pHead=pHead->next; } return count; } //****************************************************************** int Sum(List pHead) { int sum=0; while(pHead!=NULL) { sum+=pHead->data; pHead=pHead->next; } return sum; } //****************************************************************** int Min(List pHead) { int min=pHead->data; while(pHead!=NULL) { if(pHead->data<min) min=pHead->data; pHead=pHead->next; } return min; } //****************************************************************** int Max(List pHead) { int max=0; while(pHead!=NULL) { if(pHead->data>max) max=pHead->data; pHead=pHead->next; } return max; } //****************************************************************** int DisplayNode(List pHead,int n) { int count=0; List temp=NULL; while(pHead!=NULL && count!=n) { count++; temp=pHead; pHead=pHead->next; } return temp->data; } //****************************************************************** void swap(int &a,int &b) { int temp=a; a=b; b=temp; } //****************************************************************** void Sort(List pHead,List pTail) { if(pHead==NULL) cout<<"Danh Sach Rong"; else { List min; for(List i=pHead;i!=pTail->next;i=i->next) { min=i; for(List j=i->next;j!=pTail->next;j=j->next) if(min->data>j->data) min=j; swap(i->data,min->data); } } } //****************************************************************** List Find(List pHead,int data) { List temp=pHead; while(temp!=NULL && temp->data!=data) temp=temp->next; return temp; } //*************************************************** void Display(List pHead) { if(pHead==NULL) cout<<"Danh Sach Rong"; else { while(pHead!=NULL) { cout<<pHead->data<<" "; pHead=pHead->next; } } } //**************************************************** void DeleteNodeAtFirst(List &pHead) { if(pHead==NULL) cout<<"Danh Sach Rong"; else { List temp=pHead; pHead=pHead->next; delete temp; } } //******************************************************* void DeleteNodeAtLast(List &pHead) { if(pHead==NULL) cout<<"Danh Sach Rong"; else { List temp=pHead; List Truoc; while(temp->next!=NULL) { Truoc=temp; temp=temp->next; } Truoc->next=NULL; delete temp; } } //*************************************************** void DeleteNodeRandom(List &pHead,int vitrixoa) { List temp=pHead; List Truoc; while(temp!=NULL && temp->data!=vitrixoa) { Truoc=temp; temp=temp->next; } Truoc->next=Truoc->next->next; delete temp; } //****************************************************** void DeleteList(List &pHead) { if(pHead==NULL) cout<<"Danh sach rong"; else { while(pHead!=NULL) DeleteNodeAtFirst(pHead); cout<<"Da Xoa Toan Bo Danh Sach"; } } //Out Menu //***************************************************************** void menu(List &pHead,List &pTail) { int chon,n; cout<<"1.Hien thi danh sach\n"; cout<<"2.Dem so phan tu trong List\n"; cout<<"3.Tong Tat ca phan tu trong danh sach\n"; cout<<"4.Tim Max Min\n"; cout<<"5.Tim Node dau tien bang gia tri nhap vao\n"; cout<<"6.Them mot Node vao dau danh sach\n"; cout<<"7.Them mot Node vao cuoi danh sach\n"; cout<<"8.Them mot Node sau Node nao do\n"; cout<<"9.Hien thi gia tri Node thu n\n"; cout<<"10.Huy Node dau tien\n"; cout<<"11.Huy Node cuoi cung\n"; cout<<"12.Huy Node bat ki\n"; cout<<"13.Huy toan bo danh sach\n"; cout<<"14.Sap xep danh sach voi gia tri tang dan\n"; cout<<"15.Exit\n"; cout<<"Chon: "; cin>>chon; system("cls"); switch(chon) { case 1: Display(pHead); getch(); break; case 2: if(pHead==NULL) cout<<"Danh Sach Rong"; else cout<<"Co "<<Count(pHead)<<" Node Trong List"; getch(); break; case 3: if(pHead==NULL) cout<<"Danh Sach Rong"; else cout<<"Tong Bang "<<Sum(pHead); getch(); break; case 4: if(pHead==NULL) cout<<"Danh sach rong"; else cout<<"Min="<<Min(pHead)<<" Max="<<Max(pHead); getch(); break; case 5: cout<<"Nhap Vao 1 So Tim: "; cin>>n; if(Find(pHead,n)==NULL) cout<<"Khong Tim Thay"; else cout<<"So Can Tim Ton Tai Trong Danh Sach"; getch(); break; case 6: cout<<"Nhap Vao 1 So : "; cin>>n; InsertNewNodeAtFirst(CreateNewNode(n),pHead,pTail); Display(pHead); getch(); break; case 7: cout<<"Nhap Vao 1 So: "; cin>>n; InsertNewNodeAtLast(CreateNewNode(n),pHead,pTail); Display(pHead); getch(); break; case 8: Display(pHead); int x; cout<<"\nNhap Vi Tri: "; cin>>x; List nodetimthay=Find(pHead,x); if(nodetimthay==NULL) cout<<"Khong Tim Thay, Khong The Add"; else { cout<<"\nNhap Vao 1 So Insert: "; cin>>n; InsertNewNodeAtAfter(nodetimthay,CreateNewNode(n),pTail,pHead); Display(pHead); } getch(); break; case 9: cout<<"Nhap vao vi tri Node muon xem: "; cin>>n; if(n>Count(pHead) || n==0) cout<<"Vi tri khong co thuc"; else cout<<"Node Vi tri "<<n<<" co gia tri la: "<<DisplayNode(pHead,n); getch(); break; case 10: DeleteNodeAtFirst(pHead); Display(pHead); getch(); break; case 11: DeleteNodeAtLast(pHead); Display(pHead); getch(); break; case 12: Display(pHead); cout<<"\nNhap So Muon Xoa: "; cin>>n; if(Find(pHead,n)==NULL) cout<<"Khong Tim Thay, Khong The Xoa"; else { DeleteNodeRandom(pHead,n); Display(pHead); } getch(); break; case 13: DeleteList(pHead); getch(); break; case 14: Sort(pHead,pTail); Display(pHead); getch(); break; case 15: exit(0); } } //************************************************ int main() { List pHead=NULL,pTail=NULL; while(true) { system("cls"); menu(pHead,pTail); } }

Bài 3:

Code:: #include <iostream.h> #include <conio.h> struct node { int data; node *next; }; typedef struct node* List; //gan List bang node* //****************************************************************************** List CreateNewNode(int data) { List temp=new node(); if(temp==NULL) { cout<<"Khong du bo nho"; exit(0); } temp->data=data; temp->next=NULL; return temp; } //****************************************************************************** void InsertNewNodeAtFirst(List newnode,List &pHead) { newnode->next=pHead; pHead=newnode; } //****************************************************************************** void InsertNewNodeAtLast(List newnode,List &pTail) { pTail->next=newnode; pTail=newnode; } //****************************************************************************** void InsertNewNodeAtAfter(node *nodetimthay,node *newnode) { newnode->next=nodetimthay->next; nodetimthay->next=newnode; } //****************************************************************************** void display(List pHead) { if(pHead==NULL) cout<<"Danh sach rong"; else { while(pHead!=NULL) { cout<<pHead->data<<" "; pHead=pHead->next; } } } //****************************************************************************** node *Find(int data,List pHead) { node *t=pHead; while(t!=NULL && t->data!=data) t=t->next; return t; } //****************************************************************************** void InsertNode(List &pHead, List &pTail,node *newnode) { if(pHead==NULL) pHead=pTail=newnode; else { if(newnode->data<pHead->data) InsertNewNodeAtFirst(newnode,pHead); else if(newnode->data>pTail->data) InsertNewNodeAtLast(newnode,pTail); else { List temp=pHead; while(temp!=NULL) { if(temp->next->data>newnode->data) { InsertNewNodeAtAfter(temp,newnode); break; } temp=temp->next; } } } } int main() { node *pHead=NULL; node *pTail=NULL; int chon; do { system("cls"); cout<<"1.Hien thi danh sach\n"; cout<<"2.Them Node\n"; cout<<"3.Exit\n"; cout<<"Chon: "; cin>>chon; system("cls"); switch(chon) { case 1: display(pHead); getch(); break; case 2: int n; cout<<"Nhap vao 1 so: "; cin>>n; if(Find(n,pHead)!=NULL) cout<<"So Nay Da Ton Tai"; else { InsertNode(pHead, pTail,CreateNewNode(n)); display(pHead); } getch(); break; } }while(chon!=3); }

1 Bài tập danh sách liên kết đơn Fri Jun 14, 2013 11:30 am