#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<dos.h>
#include<string.h>
#include <math.h>
#include<alloc.h>
#include<ctype.h>
#define TRUE 1
#define FALSE 0
/* Cau truc thong tin ve doan tau */
typedef struct {
char gatruoc[20];
char gasau[20];
int chieudai;
int thoigian;
} doan;
/* cau truc 1 nut trong danh sach lien ket kep*/
typedef struct node{
doan infor;
struct node *left,*right;
};
typedef struct node *NODEPTR;
/* cap phat 1 nut*/
NODEPTR Getnode(void){
NODEPTR p;
p
=(NODEPTR
) malloc(sizeof(struct node
)); return(p);
}
/* giai phong 1 nut*/
void Freenode( NODEPTR p){
}
/* khoi dong danh sach*/
void Initialize(NODEPTR *plist){
*plist=NULL;
}
/* kiem tra tinh rong*/
int Empty(NODEPTR *plist){
if (*plist==NULL)
return(TRUE);
return(FALSE);
}
/* xac dinh so nut*/
int Listsize(NODEPTR *plist){
NODEPTR p;int n;
p=*plist;n=0;
while(p!=NULL){
p=p->right;
n++;
}
return(n);
}
/* xac dinh vi tri con tro dang o vi tri thu i trong danh sach*/
NODEPTR Nodepointer(NODEPTR *plist,int i){
NODEPTR p;int vitri;
p=*plist;vitri=0;
while (p!=NULL && vitri<i){
p=p->right;
vitri++;
}
return(p);
}
/* xax dinh vi tri nut p trong danh sach*/
int Position(NODEPTR *plist, NODEPTR p){
int vitri; NODEPTR q;
q = *plist;vitri=0;
while (q!=NULL && q!=p){
q = q->right;
vitri++;
}
if (q==NULL)
return(-1);
return(vitri);
}
/* them 1 nut moi vao dau danh sach*/
void Push(NODEPTR *plist, doan x){
NODEPTR p;p = Getnode();
p ->infor = x;
if(*plist==NULL){
p->left=NULL;
p->right=NULL;
*plist=p;
}
else {
p->right = *plist;
(*plist)->left=p;
p->left=NULL;
*plist=p;
}
}
/* them nut moi vao sau nut p */
void Insertright(NODEPTR p, doan x){
NODEPTR q,r;
if (p==NULL){
printf("\n Nut khong co thuc"); delay(2000);return;
}
else {
q=Getnode();
q->infor=x;
r=p->right;
r->left=q;
q->right=r;
q->left=p;
p->right=q;
}
}
/* them nut moi vao truoc nut p*/
void Insertleft(NODEPTR *plist, NODEPTR p, doan x){
NODEPTR q, r;
if (p==NULL) {
printf("\n Node khong co thuc"); delay(2000); return;
}
if (p==*plist)
Push(plist,x);
else {
q=Getnode();
q->infor=x;
r=p->left;
r->right=q;
q->left=r;
q->right=p;
p->left=q;
}
}
/* xao nut o dau danh sach*/
doan Pop(NODEPTR *plist){
NODEPTR p;doan x;
if (Empty(plist)){
delay(2000);
}
else {
p = *plist;
x=p->infor;
if ((*plist)->right==NULL)
*plist=NULL;
else{
*plist=p->right;
(*plist)->left=NULL;
}
Freenode(p);
}
return(x);
}
/* xoa nut co con tro la p trong danh sach*/
doan Delnode(NODEPTR *plist, NODEPTR p) {
NODEPTR q, r;doan x;
if (p==NULL){
printf("\n Node khong co thuc"); delay(2000);return(x);
}
if (*plist==NULL){
delay(2000);
}
else {
x=p->infor;
q = p->left;
r = p->right;
r ->left = q;
q ->right=r;
Freenode(p);
}
return(x);
}
/* duyet danh sach tu trai sang phai */
void Righttraverse(NODEPTR *plist){
NODEPTR p; int stt;
if (Empty(plist)){
printf("\n Khong cos doan nao"); delay(2000); return;
}
p = *plist; stt=0;
while (p!=NULL){
printf ("\n %5d %20s %20s %7d%7d", stt
++,p
->infor.
gatruoc, p->infor.gasau,p->infor.chieudai,p->infor.thoigian);
p=p->right;
}
}
/* duyet danh sach tu phai sang trai*/
void Lefttraverse(NODEPTR *plist){
NODEPTR p;int stt;
if (Empty(plist)){
printf("\n Khong co doan nao"); delay(2000); return;
}
stt =0;p = Nodepointer(plist,Listsize(plist)-1);
while (p!=NULL){
printf("\n %5d %20s%20s%7d%7d", stt
++, p
->infor.
gasau, p->infor.gatruoc, p->infor.chieudai, p->infor.thoigian);
p = p->left;
}
}
/* thong tin ve ga truoc */
NODEPTR Search1(NODEPTR *plist, char x[]){
NODEPTR p=*plist;
while (strcmp(p
->infor.
gatruoc,x
)!=0 && p
!=NULL) p = p->right;
return(p);
}
/* thong tin ve ga sau */
NODEPTR Search2(NODEPTR *plist, char x[]){
NODEPTR p=*plist;
while (strcmp(p
->infor.
gasau,x
)!=0 && p
!=NULL) p = p->right;
return(p);
}
/* loai bo toan bo cac nut cua danh sach*/
void Clearlist(NODEPTR *plist){
while (*plist!=NULL){
Pop(plist);
}
}
/* Bao lo trinh cac tuyen */
void Message(NODEPTR *plist, char noidi[], char noiden[], char c){
NODEPTR p, p1;int kc, tg;
if (c=='x'){
p=Search1(plist, noidi);
if (p==NULL){
printf("\n Khong co lo trinh"); delay(2000);return;
}
if (strcmp(noidi
, noiden
)==0){ printf("\n Noi di trung noi den"); delay(2000); return;
}
p1= Search2(plist, noiden);
if (p1==NULL){
printf("\n Noi den khong co thuc"); delay(2000); return;
}
if (Position(plist,p)<=Position(plist,p1) ) {
kc=tg=0;
while(p!=p1){
kc = kc + p->infor.chieudai;
tg = tg + p->infor.thoigian;
printf("\n %20s ->%20s: %7d km %7d gio",p
->infor.
gatruoc,p
->infor.
gasau, p
->infor.
chieudai,p
->infor.
thoigian); p = p->right;
}
kc= kc + p1->infor.chieudai;
tg=tg + p1 ->infor.thoigian;
printf("\n %20s ->%20s: %7d km %7d gio",p1
->infor.
gatruoc, p1->infor.gasau, p1->infor.chieudai, p1->infor.thoigian);
printf("\n Tong chieu dai:% 7d Thoi gian:%7d", kc
, tg
); delay(2000);
}
}
else{
printf("\n Khong di xuoi duoc"); delay(2000); return;
}
if (c=='n'){
p=Search2(plist, noidi);
if (p==NULL){
printf("\n Khong co lo trinh"); delay(2000);return;
}
if (strcmp(noidi
, noiden
)==0){ printf("\n Noi di trung noi den"); delay(2000); return;
}
p1= Search1(plist, noiden);
if (p1==NULL){
printf("\n Noi den khong co thuc"); delay(2000); return;
}
if (Position(plist,p)<=Position(plist,p1) ) {
kc=tg=0;
while(p!=p1){
kc = kc + p->infor.chieudai;
tg = tg + p->infor.thoigian;
printf("\n %20s ->%20s: %7d km %7d gio",p
->infor.
gatruoc,p
->infor.
gasau, p
->infor.
chieudai,p
->infor.
thoigian); p = p->right;
}
kc= kc + p1->infor.chieudai;
tg=tg + p1 ->infor.thoigian;
printf("\n %20s ->%20s: %7d km %7d gio",p1
->infor.
gatruoc,p1
->infor.
gasau, p1
->infor.
chieudai, p1
->infor.
thoigian); printf("\n Tong chieu dai:% 7d Thoi gian:%7d", kc
, tg
); delay(2000);
}
}
else{
printf("\n Khong di nguoc duoc"); delay(2000); return;
}
}
//=============================================================
void main (void){
NODEPTR plist,p, p1;
doan ga;
char c, noidi[20], noiden[20];
int vitri;
Initialize(&plist);
clrscr();
textmode(C80);
textcolor(YELLOW);
textbackground(BLUE);
window(1,1,80,25);
while(1)
{
clrscr();
printf("\n Thao tac tren Double link_list"); printf("\n ÞÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÝ"); printf("\n QUAN SAT TREN TAU");
printf("\n 1. Them mot doan"); printf("\n 2. Loai bo mot doan"); printf("\n 3. Xem lo trinh xuoi"); printf("\n 4. Xem lo trinh nguoc"); printf("\n 5. Xem thong tin doan i"); printf("\n 6. Hieu chinh thong tin doan i"); printf("\n Z. Ket thuc chuong trinh"); printf("\n Lua chon chuc nang tu 1->Z:"); if(ch=='Z') break;
switch(ch)
{
case '1':
if (vitri==0)
Push(&plist,ga);
else
Insertright(Nodepointer(&plist,vitri-1),ga);
break;
case '2':
p=Nodepointer(&plist,vitri);
if (p==NULL){
printf("\n Vi tri khong hop le"); }
else {
if (vitri==0) Pop(&plist);
else Delnode(&plist,p);
}
delay(2000); break;
case '3':
printf("\n LO TRINH DUYET XUOI"); Righttraverse(&plist);delay(2000);break;
case '4':
printf("\n LO TRINH DUYET NGUOC"); Lefttraverse(&plist);delay(2000);break;
case '5':
p = Nodepointer(&plist,vitri);
if(p==NULL)
printf("\n Vi tri khong hop le"); else {
printf("\n DOAN:%d Tu:%s Den:%s Chieu dai:%d Thoigian :%d",vitri
, p
->infor.
gatruoc, p
->infor.
gasau,p
->infor.
chieudai,p
->infor.
thoigian); }
delay(2000); break;
case '6':
p=Nodepointer(&plist, vitri);
if(p==NULL)
printf("\n Vi tri khong hop le"); else {
printf("\n DOAN:%d Tu:%s Den:%s Chieu dai:%d Thoigian :%d",vitri
, p
->infor.
gatruoc, p
->infor.
gasau,p
->infor.
chieudai,p
->infor.
thoigian); }
delay(2000); break;
case '7':
printf("\n Di xuoi:x Di nguoc: n:");c
=getche
(); Message(&plist, noidi, noiden, c);
delay(2000); break;
}
}
}