Danh sách liên kết + Hàng đợi + Ngăn xếp

Anh em khởi động vài bài.

////////////////////////////////////

+ Danh sách liên kết:

Viết chương trình thực hiện những công việc sau:
- Khởii tạo một danh sach nối đơn chứa thông tin về các thành viên trong nhóm: ví dụ: họ tên, lớp, mssv.
- Thêm một thành viên mới, loại bỏ một thành viên
- Tìm kiếm thành viên theo tên.
- .............
Bác nào thích thì thêm các chức năng khác như là bạn đó là nam hay nữ, tình trạng hôn nhân,...

///////////////////////////////////////

+ Hàng đợi:

- Viết chương trình làm những công việc sau:
. Khởi tạo hàng đợi
. Nhập phần tử vào hàng đợi
. Thêm bớt phần tử vào hàng đợi
Lấy phần tử là số nguyên(hoặc các giá trị khác, tùy sở thích mọi người).

-Viết chương trình kiểm tra một chuỗi có là palindromes hay không, ví dụ chuỗi palindromes : RADAR, NOON là những chuỗi palindromes.

Cái này chỉ yêu cầu làm một bài thôi!!!

//////////////////////////////

+ Ngăn xếp:

- Viết chương trình kiểm tra ngoặc đúng, yêu cầu người dùng nhập vào một biểu thức, kiểm tra tính đúng đắn của việc sử dụng dấu ngoặc trong biểu thức đó, nếu ngoặc chưa đúng thì chỉ ra số ngoặc cần thêm cho đúng( Bác nào muốn làm ok hơn thì làm thêm vị trí thêm ngoặc, loại ngoặc cần thêm)
ví dụ: ( a + [c+b*d]})
=>Biểu thức sai, cần thêm 1 ngoặc.

Đây chỉ là bài tập nhằm ôn lại một số kiến thức cơ bản thao tác trên con trỏ và danh sách để phục vụ cho việc thao tác trên cây nhị phân trong thời gian tới, mọi người cố gắng nắm chắc, sau này code về cây nhị phân sẽ nhanh hơn.
Bài tập thì nhiều vô số nhưng mình làm vài bài thôi, chủ yếu để nắm giải thuật, cách tiếp cận, và cách cài đặt trực tiếp.

Do your best, the rest will come!!!

Đây là bản demo tôi mới viết xong để anh em tham khảo phát triển thuật toán
LIÊN KẾT ĐƠN

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>>
struct node
{
int item;
struct node *next;
};
typedef struct node *listnode;
void Init(listnode *p) { *p=NULL; }
int Empty(listnode p)
{
if(p==NULL) return 1;
else return 0;
}
void Insert_begin(listnode *p,int x)
{
listnode q;
q=(listnode)malloc(sizeof(struct node));
q->item=x;
q->next=NULL;
if(Empty(*p)) *p=q;
else
{
q->next=*p;
*p=q;}
}
void Insert_end(listnode *p,int x)
{
listnode r,q;
q=(listnode)malloc(sizeof(struct node));
q->item=x;
q->next=NULL;
if(Empty(*p)) *p=q;
else{
r=*p;
while(r->next!=NULL) r=r->next;
r->next=q;}
}
void Print(listnode p)
{
listnode q=p;
while(q){
printf("%d",q->item);
printf("\n");
q=q->next;
}
}
int main()
{
listnode p;
Init(&p);
int x[]={1,5,3,6,9,34,36,65,111};
Insert_begin(&p,x[0]);
for(int i=1;i<9;i++)
Insert_end(&p,x[i]);
Print(p);
getch();
}

STACK


#include<conio.h>
#include<stdio.h>
#include<stdlib.h>>
struct node
{
int item;
struct node *next;
};
typedef struct node *stacknode;
typedef struct
{
stacknode top;
}stack;
void StackInit(stack *s){s->top=NULL;}
int EmptyStack(stack s)
{
if(s.top==NULL) return 1;
else return 0;
}
void push(stack *s,int x)
{
stacknode p;
p=(stacknode)malloc(sizeof(struct node));
p->item=x;
p->next=s->top;
s->top=p;
}
void pop(stack *s)
{
stacknode p;
if(EmptyStack(*s)) printf("ngan xep rong");
p=s->top;
s->top=s->top->next;
printf("%d\n",p->item);
free(p);
}
int main()
{
int x[]={1,2,3,4,5,6,7,8,9};
stack s;
StackInit(&s);
for(int i=0;i<9;i++)
push(&s,x[i]);
while(!EmptyStack(s)) pop(&s);
getch();
}


còn bây h thì đi ngủ mai còn đi học sớm.oải (

anh em dao nay luoi ghe
the nay vao giai doan sau chien dau sao day

Khởi động bài 1 nha:


///////////////////////////////////////////////////
/// Danh sach lien ket don
// Quan li danh sach thanh vien cua nhom
////////////////////////////////////////////////////

#include<iostream.h>
#include<string.h>
#include<conio.h>
#define SIZE_NAME 30
#define SIZE_CLASS 50
#define SIZE_CODE 10
typedef struct SINH_VIEN
{
char cTen[SIZE_NAME];
char cMaso[SIZE_CODE];
char cLop[SIZE_CLASS];
int iGioitinh; // 1 : boy, 0 : girl
SINH_VIEN *pnext;
}Danhsach;
Danhsach *ptr;

//////////////////////////////////////////////////////
/// KHAI BAO CAC HAM SU DUNG TRONG CHUONG TRINH

Danhsach *Khoitao();
Danhsach *Themthanhvien(Danhsach *, Danhsach *); // Them vao cuoi danh sach
int Timkiem(Danhsach *, char cMaso[]);
void Hienthi(Danhsach*);
Danhsach *Menu(Danhsach *);
/////////////////////////////////////////////////////

int main()
{
ptr = (Danhsach*)malloc(sizeof(Danhsach));
ptr = Khoitao();
do
{
ptr = Menu(ptr);
if(ptr == NULL)
{
break;
}
}while( ptr!= NULL);
cout<<"\nAn mot phim bat ki de ket thuc chuong trinh... ";
getch();
return 0;
}
/////////////////////////////
// XAY DUNG CAC HAM

/////////////////////////////
/// HAM KHOI TAO DANH SACH
/////////////////////////////
Danhsach *Khoitao()
{
return NULL;
}

//////////////////////////////////////////
// Them thanh vien vao cuoi danh sach
// Input : Cac thong tin ve sinh vien
/////////////////////////////////////////
Danhsach *Themthanhvien(Danhsach *First_Member, Danhsach *New_Member )
{
New_Member -> pnext = NULL;
if(First_Member == NULL)
{
cout<<"\nDay la thanh vien dau tien cua nhom.";
New_Member -> pnext = First_Member;
First_Member = New_Member;
}
else
{
while( First_Member->pnext != NULL)
{
First_Member = First_Member -> pnext;
}
First_Member -> pnext = New_Member;
cout<<"\nDa them thanh vien vao cuoi danh sach";
}
return First_Member;
}

//////////////////////////////////////////////
// TIM KIEM THANH VIEN TRONG DANH SACH
// Tim kiem thanh vien nho khoa la ma so
////////////////////////////////////////////

int Timkiem(Danhsach *Member, char cMaso[10])
{
while(Member != NULL)
{
if(strcmp(Member -> cMaso, cMaso) == 0)
{
cout<<"\nCO THANH VIEN NAY TRONG NHOM.";
cout<<"\nHo ten : "<<Member -> cTen;
cout<<"\nMa so : "<<Member -> cMaso;
cout<<"\nLop : "<<Member -> cLop;
cout<<"\nGioi tinh:";
if(Member -> iGioitinh == 1)
{
cout<<" A boy!!!";
}
else
{
cout<<" A girl!!!";
}
return 1;
}
Member = Member -> pnext;
}
return 0;
}

/////////////////////////////////////////
// HIEN THI DANH SACH THANH VIEN
////////////////////////////////////////
void Hienthi(Danhsach *Member)
{
Danhsach *pTemp;
int iCount=0;
pTemp = Member;
cout<<"\n DANH SACH THANH VIEN\n\n";
while(Member != NULL)
{
cout<<"\n|"<<Member->cTen<<"|"<<Member -> cMaso<<"|"<< Member -> cLop<<"|";
if( Member->iGioitinh == 1)
{
cout<<" A boy";
}
else
{
cout<<" A girl";
}
Member = Member ->pnext;
iCount++;
}
if(iCount ==0)
{
cout<<"\n CHUA CO THANH VIEN NAO CUA NHOM";
}
}


//////////////////////////////
// TAO LAP MENU SU DUNG
//////////////////////////////

Danhsach *Menu(Danhsach *ptr)
{
int iChoice, iFind;
char cName[SIZE_NAME];
char cCode[SIZE_CODE];
char cClass[SIZE_CLASS];
int iGender;
cout<<"\n MENU";
cout<<"\n1. Xem thanh vien";
cout<<"\n2. Tim kiem thanhvien";
cout<<"\n3. Them thanh vien";
cout<<"\n4. Exit";
cout<<"\n\nHay chon mot chua nang(1->4): ";
cin>>iChoice;
switch(iChoice)
{
case 1:
Hienthi(ptr);
break;
case 2:
cout<<"\n CHUC NANG TIM KIEM THANH VIEN\n";
cout<<"\nNhap vao ma so cua thanh vien muon tim kiem: ";
fflush(stdin);
cin.get(cName, SIZE_NAME);
iFind = Timkiem(ptr,cName);
if(iFind == 0)
{
cout<<"\nKHONG CO THANH VIEN NAY TRONG NHOM.";
}
break;
case 3:
cout<<"\n CHUC NANG THEM THANH VIEN\n";
cout<<"\n\nNgung them thanh vien nhap ten: exit ";
do
{
Danhsach *pTemp;
pTemp = (Danhsach*)malloc(sizeof(Danhsach));
cout<<"\n\nHo va ten: ";
fflush(stdin);
cin.get(cName,SIZE_NAME);
if(strcmp(cName,"exit") == 0)
{
break;
}
strcpy(pTemp -> cTen,cName);
cout<<"\nMa so: ";
fflush(stdin);
cin.get(cCode,SIZE_CODE);
strcpy(pTemp -> cMaso,cCode);
cout<<"\nLop: ";
fflush(stdin);
cin.get(cClass,SIZE_CLASS);
strcpy(pTemp -> cLop,cClass);
cout<<"\nGioi tinh(1: boy, 0: girl)";
cin>>iGender;
pTemp -> iGioitinh = iGender;
ptr = Themthanhvien(ptr,pTemp);
}while(strcmp(cName,"exit")!=0);
break;
case 4:
return NULL;
default:
cout<<"\n CHON NHAM CHUC NANG";
break;
}
return ptr;
}



Mọi người tích cực làm bài tập đi, phải chăm chỉ mới được chứ.

P/s: Bài này còn một điểm chưa hoàn chỉnh đâu, mọi người tìm mà sửa nha!!
Do your best, the rest will come!

Bài stack lam trên cơ sở bài của mrmax, về thuật toán bài này chưa triệt để, chỉ làm để sử dụng stack thôi


////////////////////////////////////////
#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>

struct node
{
char item;
struct node *next;
};

typedef struct node *stacknode;

typedef struct
{
stacknode top;
}stack;
void StackInit(stack *s)
{
s->top=NULL;
}
int EmptyStack(stack s)
{
if(s.top==NULL) return 1;
else return 0;
}
void push(stack *s,char x)
{
stacknode p;
p=(stacknode)malloc(sizeof(struct node));
p->item = x;
p->next=s->top;
s->top=p;
}
char pop(stack *s)
{
stacknode p;
p=s->top;
s->top=s->top->next;
return (p->item);
free(p);
}
/////////////////////////////////
///// MAIN
int main()
{

char cKitu[100], cTest;
int iCount1=0, iCount2 = 0, iCount3 =0;
int iC,i;
stack s;
StackInit(&s);
cout<<"\n Nhap vao bieu thuc can kiem tra(ngung nhap an enter): \n";
fflush(stdin);
cin.get(cKitu,100);
iC=strlen(cKitu);
for(i=0;i<iC;i++)
{
if( (cKitu[i] == '(') || (cKitu[i] == '{')|| (cKitu[i] == '[') )
{
push(&s,cKitu[i]);
}
if( cKitu[i] == ')' ) // Gap ngoac dong ')'
{
iCount1--;
if(!EmptyStack(s))
{
cTest = pop(&s);
if(cTest=='{')
iCount2++;
if(cTest=='[')
iCount3++;
if(cTest=='(')
iCount1++;
}
}
if((cKitu[i] == '}')) // Gap ngoac dong ')'
{
iCount2--;
if(!EmptyStack(s))
{
cTest = pop(&s);
if(cTest=='(')
iCount1++;
if(cTest=='[')
iCount3++;
if(cTest=='{')
iCount2++;
}
}
if((cKitu[i] == ']')) // Gap ngoac dong ')'
{
iCount3--;
if(!EmptyStack(s))
{
cTest = pop(&s);
if(cTest=='{')
iCount2++;
if(cTest=='(')
iCount1++;
if(cTest=='[')
iCount3++;
}
}
}
while(!EmptyStack(s))
{
cTest = pop(&s);
if(cTest=='{')
iCount2++;
if(cTest=='(')
iCount1++;
if(cTest=='[')
iCount3++;
}
if(iCount1 < 0)
{
cout<<"\nDa thieu ngoac '(', so luong: ";
cout<<(-iCount1);
}
else if(iCount1 >0)
{
cout<<"\nDa thieu ngoac ')', so luong: ";
cout<<iCount1;
}
if(iCount2 < 0)
{
cout<<"\nDa thieu ngoac '{', so luong: ";
cout<<(-iCount2);
}
else if(iCount2 >0)
{
cout<<"\nDa thieu ngoac '}', so luong: ";
cout<<iCount1;
}
if(iCount3 < 0)
{
cout<<"\nDa thieu ngoac '[', so luong: ";
cout<<(-iCount3);
}
else if(iCount3 >0)
{
cout<<"\nDa thieu ngoac ']', so luong: ";
cout<<iCount3;
}
if(iCount1 == 0 && iCount2 == 0 && iCount3 == 0)
{
cout<<"\n Bieu thuc dung.";
}
cout<<"\n Press any key to finish";
getch();
return 0;
}

P/s: ví dụ trường hợp nhập vào ngoặc như sau:
)( thì chương trình vẫn sẽ báo ngoặc đúng.
Do your best, the rest will come!

í tưởng của cường là tốt nhưng thuật toán này sai khi số dấu đóng ngoặc và mở ngoắc cùng kiểu là bằng nhau
VD: )( ; )))((( ; )())(( v.v
sai lầm nằm ở chỗ không xác định ngăn xếp rỗng khi gặp dấu đóng ngoặc để xử lý
VD: )( khi gặp dấu ) thì iCout1=-1; nhưng sau đó ( vẫn đc đưa vào ngăn xếp và sau đó trong thần vòng lặp while iCout1++=0 dó đó biểu thức vẫn đúng

Giải phấp tạm thời có thể là thế này(Nhưng không hay)Bà con cùng nhau sửa

#include
#include
#include
#include

struct node
{
char item;
struct node *next;
};

typedef struct node *stacknode;

typedef struct
{
stacknode top;
}stack;
void StackInit(stack *s)
{
s->top=NULL;
}
int EmptyStack(stack s)
{
if(s.top==NULL) return 1;
else return 0;
}
void push(stack *s,char x)
{
stacknode p;
p=(stacknode)malloc(sizeof(struct node));
p->item = x;
p->next=s->top;
s->top=p;
}
char pop(stack *s)
{
stacknode p;
p=s->top;
s->top=s->top->next;
return (p->item);
free(p);
}
/////////////////////////////////
///// MAIN
int main()
{

char cKitu[100], cTest;
int iCount1=0, iCount2 = 0, iCount3 =0;
int iC,i;
stack s;
StackInit(&s);
cout<<"\n Nhap vao bieu thuc can kiem tra(ngung nhap an enter): \n";
fflush(stdin);
cin.get(cKitu,100);
iC=strlen(cKitu);
for(i=0;i
{
if( (cKitu[i] == '(') || (cKitu[i] == '{')|| (cKitu[i] == '[') )
{
push(&s,cKitu[i]);
}
if( cKitu[i] == ')' ) // Gap ngoac dong ')'
{
iCount1--;
if(EmptyStack(s))
{
cout<<"thieu ( "; //y tuong co ban la dat lai iCount=0;
iCount1=0;
}
if(!EmptyStack(s))
{
cTest = pop(&s);
if(cTest=='{')
iCount2++;
if(cTest=='[')
iCount3++;
if(cTest=='(')
iCount1++;
}
}
if((cKitu[i] == '}')) // Gap ngoac dong ')'
{
iCount2--;
if(EmptyStack(s))
{
cout<<"thieu { ";
iCount2=0;
}
if(!EmptyStack(s))
{
cTest = pop(&s);
if(cTest=='(')
iCount1++;
if(cTest=='[')
iCount3++;
if(cTest=='{')
iCount2++;
}
}
if((cKitu[i] == ']')) // Gap ngoac dong ')'
{
iCount3--;
if(EmptyStack(s))
{
cout<<"thieu [ ";
iCount3=0;
}
if(!EmptyStack(s))
{
cTest = pop(&s);
if(cTest=='{')
iCount2++;
if(cTest=='(')
iCount1++;
if(cTest=='[')
iCount3++;
}
}
}

while(!EmptyStack(s))
{
cTest = pop(&s);
if(cTest=='{')
iCount2++;
if(cTest=='(')
iCount1++;
if(cTest=='[')
iCount3++;
}
if(iCount1 < 0)
{
cout<<"\nDa thieu ngoac '(', so luong: ";
cout<<(-iCount1);
}
else if(iCount1 >0)
{
cout<<"\nDa thieu ngoac ')', so luong: ";
cout<
}
if(iCount2 < 0)
{
cout<<"\nDa thieu ngoac '{', so luong: ";
cout<<(-iCount2);
}
else if(iCount2 >0)
{
cout<<"\nDa thieu ngoac '}', so luong: ";
cout<
}
if(iCount3 < 0)
{
cout<<"\nDa thieu ngoac '[', so luong: ";
cout<<(-iCount3);
}
else if(iCount3 >0)
{
cout<<"\nDa thieu ngoac ']', so luong: ";
cout<
}
if(iCount1 == 0 && iCount2 == 0 && iCount3 == 0)
{
cout<<"\n Bieu thuc dung.";
}
cout<<"\n Press any key to finish";
getch();
return 0;
}

uhm thì mình chỉ demo thôi, đã P/s rồi mà, cả bài danh sách nhóm cũng vẫn còn sai, mọi người tìm chỗ sai rồi sửa cho hoàn chỉnh

Thực ra dùng class để kiểm soát bài này sẽ hay hơn, phần danh sách liên kết ko dùng nhiều lắm, sau này có thiên về lập trình thì cũng không dùng loại này đâu. :D:D:D:D Vì thế mọi người mà thấy nó khó thì cũng ko phải lo lắng nhiều đâu.

cac pro da lam het cac bai kho roi minh danh phai lam bai con laj ve cac hang doi thoi.cacbac de phan em bai do nha

voi ca? minh muon hoi? bai chuoi palindromes dung hang doi se giai quyet duoc j
neu ko dung hang doi

int lg=0;
int i,j;
i=1;
j=strlen(s)-1;
while( a[i] == a[j] )
{
i++;
j--;
if (i>=j)
{
lg=1;
break;
}
}
if(lg) cout<<"day la day palin.."<<endl;
else cout<<"ko phai"<<endl;

nham (s[i]==s[j])

uhm
mình thấy phần hàng đợi hay đó
Chiến code đi, dùng danh sách liên kết nha

ok

Vấn đề không phải là dùng hàng đợi để giải quyết được gì mà dùng cái đó để làm quen với hàng sử dụng hàng đợi thôi mà

Chỗ hưng sửa đúng rồi, nếu chỉ dùng ngay con trỏ FirstMember thì chỉ chứa được 2 phần tử thôi.
mọi người có biết tại sao lại chỉ chứa được hai phần tử không??????????



Do your best, the rest will come!!!

#include<conio.h>
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<iomanip.h>
struct HD
{
int iTuoi;
char chTen[20];
HD *pNext;
};
void Tao_Menu(HD*);
void Loai_Bo(HD**,HD**);
void Hien_Thi(HD*);
int main (void)
{
HD *p = NULL ;
Tao_Menu(p);
getch();
return(0);
}
void Tao_Menu(HD* p)
{
char ch,name[21];
HD *last = NULL;
HD *first = NULL;

do
{
clrscr();
cout<<"1.them vao hang doi"<<endl;
cout<<"2.loai bo 1 nguoi khoi hang doi"<<endl;
cout<<"3.hien thi hang doi"<<endl;
cout<<"4.exit"<<endl;
cout<<"nhap lua chon cua ban ......"<<endl;
if ((ch = getch()) == '1')
{
clrscr();
cout<<"them nguoi vao hang doi,khi ko muon nhap nua nhap ten rong~"<<endl;
do
{
cout<<"nhap ten"<<endl;
fflush(stdin);
gets(name);
if(name[0] != '\0')
{
p = new(HD);
strcpy(p->chTen,name);
cout<<"nhap tuoi "<<endl;
cin>>p->iTuoi;
p->pNext = NULL;
if(first != NULL) last->pNext=p;
else first = p;
last = p;
}
clrscr();
}
while ( name[0] != '\0' );
}
if(ch == '2') Loai_Bo(&first,&last);
if(ch == '3') Hien_Thi(first);
}
while ( ch != '4');
clrscr();
cout<<"press enter to exit"<<endl;
}
void Loai_Bo(HD** first,HD** last)
{
HD *p,*q;
int tuoi,dd;
char name[21];
clrscr();
q = NULL;
if (*first == NULL) {
cout<<"danh sach dang rong~ "<<endl;
getch();
}
else
{
cout<<"nhap ten nguoi can loai"<<endl;
fflush(stdin);
gets(name);
cout<<"nhap tuoi \n";
cin>>tuoi;
int lg;
do
{
lg = 0;
p = (*first);
while (( p != NULL) && (( strcmp(p->chTen,name))||( p->iTuoi != tuoi)))
{
q = p;
p = p->pNext;
}
dd = 1;
if(p !=NULL ) lg = 1;
if(p == (*first))
{
(*first) = p->pNext;
dd = 0;
}
if(p == (*last))
{
(*last) = q;
(*last)->pNext = NULL;
}
else if((dd)&&lg) q->pNext = p->pNext;
}
while (lg);
}
}
void Hien_Thi(HD* first)
{
clrscr();
if (first == NULL) cout<<"danh sach rong~"<<endl;
else
{
cout<<"danh sach gom"<<endl;
while( first != NULL)
{
cout<<setw(20)<<first->chTen<<" "<<first->iTuoi<<endl;
first=first->pNext;
}
}
getch();
}

bai demo ve hang doi do thoi gian co han ko bit co j ko on? ko co j cac ban xem ho nha