Cai Dat Danh Sach Lien Ket Kep
// CaiDat_DSLK_Kep.cpp : Defines the entry point for the console application.
// DSLKK : o day la vi du ve doan tau, cac toa tau : hang khac va so ghe trong 1 toa
#include "stdafx.h"
#include <iostream>
#include <conio.h>
//Dinh nghia kieu toa tau
typedef struct {
int number_of_seats;// Tong so ghe ngoi
int number_of_passenger;// So hanh khach tren toa
} railroad_car;
typedef struct node{
railroad_car infor;
node *left;
node *right;
} *dlist;
//KHoi tao DSLK
void init(dlist *l){
*l= NULL;
}
//Nhap vao 1 toa tau
void inputRC(railroad_car &rc){
printf("\n\n Nhap vao so ghe ngoi: ");
scanf("%d",&rc.number_of_seats);
printf("\n Nhap vao so hanh khach: ");
scanf("%d",&rc.number_of_passenger);
fflush(stdin);
}
//Hien thi 1 toa tau
void show(railroad_car rc, int i){
printf("\n\n Toa thu %d: ",i);
printf("\n So ghe ngoi: %d",rc.number_of_seats);
printf("\n So hanh khach: %d",rc.number_of_passenger);
}
//Duyet sang trai
void travel_left(dlist *l){
dlist p= *l;
int i= 1;
while(p!= NULL){
show(p->infor,i);
i++;
p= p->left;
}
}
//Duyet sang phai
void travel_right(dlist *l){
dlist p= *l;
int i=1;
//Chuyen p toi cuoi danh sach
while(p->left!= NULL){
p= p->left;
i++;
}
while(p!= NULL){
show(p->infor,i);
i--;
p= p->right;
}
}
//=============== Them =================
//Them vao 1 node tren cung
void add_top(dlist *l){
railroad_car rc;
inputRC(rc);
dlist p= *l;//p o dau danh sach
dlist add = new node;//add la node can them vao
add->infor= rc;
add->left= p;
if(p!= NULL)
p->right= add;
add->right= NULL;
*l= add;//gan *l len dau danh sach
}
//Them 1 node vao cuoi
void add_bottom(dlist *l){
railroad_car rc;
inputRC(rc);//Nhap thong tin
dlist p= *l;//p o dau danh sach
dlist add = new node;//add la node can them vao
add->infor = rc;
//Neu danh sach rong
if(p== NULL){
add->left= NULL;
add->right= NULL;
*l= add;
}
else{
//Duyet toi cuoi danh sach
while(p->left!=NULL)
p= p->left;
//p dang o cuoi danh sach
add->left= NULL;
p->left= add;
add->right= p;
}
}
//Them 1 node vao giua
void add_before(dlist *l){
int n,i=1;
dlist p= *l;
printf("\n Nhap vi tri ban muon them vao truoc: ");
scanf("%d",&n);
while(p!= NULL && i<n ){
p= p->left;
i++;
}
if(p== NULL || n<1){//Neu ko ton tai vi tri
printf("\n Vi tri khong hop le ");
getch();
return;
}
//Neu ton tai vi tri do
railroad_car rc;
inputRC(rc);
dlist add = new node;//add la node can them vao
add->infor= rc;
//neu vi tri do la cuoi cung
if(p->left== NULL){
add->left= NULL;
add->right= p;
p->left= add;
}
else{
dlist q;
q= p->left;
//Can them vao giua p va q . p dang o truoc q
//Noi p voi add
p->left= add;
add->right= p;
//Noi add voi q
add->left= q;
q->right= add;
}
}
//=================Xoa===========================
//Xoa o dau danh sach
void del_top(dlist *l){
dlist p= *l;
if(p== NULL){
printf("\n Danh sach rong !");
return;
}
else{
if(p->left== NULL){
delete(p);
*l= NULL;
}
else{
dlist q= p->left;//q o ben phai p
delete(p);
q->right= NULL;
*l= q;
}
}
}
//Xoa o cuoi
void del_bottom(dlist *l){
dlist p= *l;
if(p== NULL){
printf("\n Danh sach rong !");
return;
}
else{
if(p->left== NULL){
delete(p);
*l= NULL;
}
else{
while((p->left)->left!= NULL)
p= p->left;
dlist q= p->left;
delete(q);
p->left= NULL;
}
}
}
//Xoa 1 node truoc 1 node
void del_before(dlist *l){
int n,i=1;
dlist p= *l;
printf("\n Nhap vi tri node ");
scanf("%d",&n);
if(p== NULL){
printf("\n Danh sach rong !");
return;
}
while((p->left)->left!= NULL && i<n){
p= p->left;
i++;
}
//Neu chi co 1 node
if(p->left== NULL || n<1){
printf("\n Vi tri khong chinh xac ");
return;
}
dlist del= p->left;//del la phan tu bi xoa
//Neu node phai xoa la cuoi cung
if(del->left== NULL){
delete(del);
p->left= NULL;
return;
}
//Sau khi del bi xoa can noi p voi q
p->left=del->left;printf("\n f gan ");
(del->left)->right= p;printf("\n f bat dau xoa");
delete(del);
}
void menu(){
printf("\n\n============= Danh sach lien ket kep =================\n");
printf("\n 1. Them vao dau danh sach");
printf("\n 2. Them vao cuoi danh sach");
printf("\n 3. Them vao truoc 1 node");
printf("\n 4. xoa dau danh sach");
printf("\n 5. Xoa cuoi danh sach");
printf("\n 6. Xoa 1 node dang truoc 1 node");
printf("\n 7. Duyet trai");
printf("\n 8. Duyet phai");
printf("\n 0. ----- Thoat -----\n");
}
// Ham thuc hien cac chuc nang
void execute(){
dlist l;
init(&l);
char choice;
do{
menu();
printf("\n Chon 1 trong cac chuc nang tren \n");
scanf("%c",&choice);
if(choice== '0') exit(0);
fflush(stdin);
switch(choice){
case '1':{
printf("\n 1. Them vao dau danh sach");
add_top(&l);
printf("\n THEM THANH CONG ");
getch();
}break;
case '2':{
printf("\n 2. Them vao cuoi danh sach");
add_bottom(&l);
printf("\n THEM THANH CONG ");
getch();
}break;
case '3':{
printf("\n 3. Them vao truoc 1 node");
add_before(&l);
printf("\n THEM THANH CONG ");
getch();
}break;
case '4':{
printf("\n 4. xoa dau danh sach");
del_top(&l);
printf("\n XOA THANH CONG ");
getch();
}break;
case '5':{
printf("\n 5. Xoa cuoi danh sach");
del_bottom(&l);
printf("\n XOA THANH CONG ");
getch();
}break;
case '6':{
printf("\n 6. Xoa 1 node");
del_before(&l);
printf("\n XOA THANH CONG ");
getch();
}break;
case '7':{
printf("\n DUYET TRAI ");
travel_left(&l);
getch();
}break;
case '8':{
printf("\n DUYET PHAI ");
travel_right(&l);
getch();
}break;
}
}while(true);
}
int main(){
execute();
return (0);
}
0 nhận xét:
Đăng nhận xét