Code:
Kiem tra 1
Bài 1. Sử dụng Stack cài đặt bằng con trỏ cài đặt các thuật toán Bubble Sort, Insertion Sort, Selection Sort.
Insertion sort
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef unsigned int Position;
typedef int ElementType;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node * Stack;
Node * Make_Node(ElementType x) {
Node * temp = (Node*)malloc(sizeof(Node));
temp->Element = x;
return temp;
}
Stack MakeNull_Stack() {
Stack temp = (Stack)malloc(sizeof(Stack));
temp->Next = NULL;
return temp;
}
char Empty_Stack(Stack L) {
return L->Next == NULL;
}
void Insert(Stack L, Node * p) {
p->Next = L->Next;
L->Next = p;
}
void Insert(Stack L, Node * p, Position i) {
Stack temp = L;
Position j = 1;
while(j<i && temp!=NULL) {
temp = temp->Next;
j++;
}
if(i==j)
Insert(temp,p);
else
printf("\nThis position is not true.");
}
Stack Input_Stack(unsigned int n) {
Stack temp = MakeNull_Stack();
ElementType x;
unsigned int i = 1;
while(i<=n) {
printf("\tValue %d = ",i);
scanf("%d",&x);
Insert(temp,Make_Node(x));
i++;
}
return temp;
}
void Out_Stack(Stack L) {
if(!Empty_Stack(L)) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
else
printf("\tTbe Stack is null.");
}
//tong cac phan tu trong Stack
ElementType Sum(Stack L) {
Stack S = L;
ElementType temp = 0;
while(!Empty_Stack(S))
{
temp+=(S->Next->Element)*(S->Next->Element);
S = S->Next;
}
return temp;
}
void main() {
clrscr();
unsigned int n;
Position p;
ElementType x;
printf("Nhap n = ");
scanf("%d",&n);
Stack S = Input_Stack(n);
printf("This Stack: \n");
Out_Stack(S);
printf("\ntong gia tri trong Stack: %d", Sum(S));
getch();
}
Bubble sort
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef unsigned int Position;
typedef int ElementType;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node * Stack;
Node * Make_Node(ElementType x) {
Node * temp = (Node*)malloc(sizeof(Node));
temp->Element = x;
return temp;
}
Stack MakeNull_Stack() {
Stack temp = (Stack)malloc(sizeof(Stack));
temp->Next = NULL;
return temp;
}
char Empty_Stack(Stack L) {
return L->Next == NULL;
}
void Bubble_Sort(Stack L) {
Stack j, i = L->Next;
while(i->Next!=NULL) {
j = i->Next;
while(j!=NULL) {
if(i->Element>j->Element)
{
ElementType temp = i->Element;
i->Element = j->Element;
j->Element = temp;
}
j = j->Next;
}
i = i->Next;
}
}
Stack Input_Stack(unsigned int n) {
Stack temp = MakeNull_Stack();
ElementType x;
unsigned int i = 1;
while(i<=n) {
printf("\tValue %d = ",i);
scanf("%d",&x);
Bubble(temp,Make_Node(x));
i++;
}
return temp;
}
void Out_Stack(Stack L) {
if(!Empty_Stack(L)) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
else
printf("\tTbe Stack is null.");
}
//tong gia tri cac phan tu trong Stack
ElementType Sum(Stack L) {
Stack S = L;
ElementType temp = 0;
while(!Empty_Stack(S))
{
temp+=(S->Next->Element)*(S->Next->Element);
S = S->Next;
}
return temp;
}
void main() {
clrscr();
unsigned int n;
Position p;
ElementType x;
printf("Nhap n = ");
scanf("%d",&n);
Stack S = Input_Stack(n);
printf("This Stack: \n");
Out_Stack(S);
printf("\n tong gia tri cac phan tu trong Stack: %d", Sum(S));
getch();
}
Selection sort
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef unsigned int Position;
typedef int ElementType;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node * Stack;
Node * Make_Node(ElementType x) {
Node * temp = (Node*)malloc(sizeof(Node));
temp->Element = x;
return temp;
}
Stack MakeNull_Stack() {
Stack temp = (Stack)malloc(sizeof(Stack));
temp->Next = NULL;
return temp;
}
char Empty_Stack(Stack L) {
return L->Next == NULL;
}
void Selection_Sort(Stack L) {
Stack j, i = L->Next;
while(i->Next!=NULL) {
Stack min = i;
j = i->Next;
while(j!=NULL) {
if(min->Element>j->Element)
min = j;
j = j->Next;
}
ElementType temp = i->Element;
i->Element = min->Element;
min->Element = temp;
i = i->Next;
}
}
Stack Input_Stack(unsigned int n) {
Stack temp = MakeNull_Stack();
ElementType x;
unsigned int i = 1;
while(i<=n) {
printf("\tValue %d = ",i);
scanf("%d",&x);
Insert(temp,Make_Node(x));
i++;
}
return temp;
}
void Out_Stack(Stack L) {
if(!Empty_Stack(L)) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
else
printf("\tTbe Stack is null.");
}
//Sum of all square values in Stack
ElementType Sum(Stack L) {
Stack S = L;
ElementType temp = 0;
while(!Empty_Stack(S))
{
temp+=(S->Next->Element)*(S->Next->Element);
S = S->Next;
}
return temp;
}
void main() {
clrscr();
unsigned int n;
Position p;
ElementType x;
printf("Nhap n = ");
scanf("%d",&n);
Stack S = Input_Stack(n);
printf("This Stack: \n");
Out_Stack(S);
printf("\nSum of all values in Stack: %d", Sum(S));
getch();
}
Bài 2. Sử dụng Stack cài đặt bằng con trỏ cài đặt các thuật toán Bubble Sort, Insertion Sort, Selection Sort.
Bubble sort
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef int ElementType;
typedef struct Node {
ElementType Element;
Node *Next;
};
typedef Node *Stack;
//khoi tao danh sach rong
Stack MakeNull_Stack(){
Stack Header = (Node*)malloc(sizeof(Node));
(Header)->Next = NULL;
return Header;
}
//kiem tra danh sach rong
char Empty_Stack(Stack S) {
return S->Next == NULL;
}
//Khoi tao 1 node
Node *Make_Node(ElementType X) {
Node *temp = (Node*)malloc(sizeof(Node));
temp->Element = X;
return temp;
}
//xen mot phan tu vao Stack
void Push(ElementType X, Stack P) {
Node *Temp = Make_Node(X);
Temp->Next = P->Next;
P->Next = Temp;
}
//day 1 phan tu ra khoi Stack
void Pop(Stack P){
Stack Temp;
if (!Empty_Stack(P)){
Temp = P->Next;
P->Next = Temp->Next;
free(Temp);
}
}
Stack Input_Stack(int n) {
Stack L = MakeNull_Stack();
ElementType x;
for(int i = 1; i<=n; i++) {
printf("Phan tu %d = ",i);
scanf("%d",&x);
Push(x,L);
}
return L;
}
void Out_Stack(Stack L) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
void Bubble_Sort(Stack L) {
Stack j, i = L->Next;
while(i->Next!=NULL) {
j = i->Next;
while(j!=NULL) {
if(i->Element>j->Element)
{
ElementType temp = i->Element;
i->Element = j->Element;
j->Element = temp;
}
j = j->Next;
}
i = i->Next;
}
}
void main() {
clrscr();
int n;
printf("Nhap n = ");
scanf("%d",&n);
Stack L = Input_Stack(n);
printf("Danh sach chua sap xep: \n");
Out_Stack(L);
printf("\n Bubble Sort: \n");
Bubble_Sort(L);
Out_Stack(L);
getch();
}
Insertion sort
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef int ElementType;
typedef struct Node {
ElementType Element;
Node *Next;
};
typedef Node *Stack;
//khoi tao danh sach rong
Stack MakeNull_Stack(){
Stack Header = (Node*)malloc(sizeof(Node));
(Header)->Next = NULL;
return Header;
}
//kiem tra danh sach rong
char Empty_Stack(Stack S) {
return S->Next == NULL;
}
//Khoi tao 1 node
Node *Make_Node(ElementType X) {
Node *temp = (Node*)malloc(sizeof(Node));
temp->Element = X;
return temp;
}
//xen mot phan tu vao Stack
void Push(ElementType X, Stack P) {
Node *Temp = Make_Node(X);
Temp->Next = P->Next;
P->Next = Temp;
}
//day 1 phan tu ra khoi Stack
void Pop(Stack P){
Stack Temp;
if (!Empty_Stack(P)){
Temp = P->Next;
P->Next = Temp->Next;
free(Temp);
}
}
Stack Input_Stack(int n) {
Stack L = MakeNull_Stack();
ElementType x;
for(int i = 1; i<=n; i++) {
printf("Phan tu %d = ",i);
scanf("%d",&x);
Push(x,L);
}
return L;
}
void Out_Stack(Stack L) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
void Insertion_Sort(Stack L) {
Stack j, i = L->Next;
while(i->Next!=NULL) {
j = i->Next;
while(j!=NULL) {
if(i->Element>j->Element)
{
ElementType temp = i->Element;
i->Element = j->Element;
j->Element = temp;
}
j = j->Next;
}
i = i->Next;
}
}
void main() {
clrscr();
int n;
printf("Nhap n = ");
scanf("%d",&n);
Stack L = Input_Stack(n);
printf("Danh sach chua sap xep: \n");
Out_Stack(L);
printf("\n Insertion Sort: \n");
Insertion_Sort(L);
Out_Stack(L);
getch();
}
Selection sort
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef int ElementType;
typedef struct Node {
ElementType Element;
Node *Next;
};
typedef Node *Stack;
//khoi tao danh sach rong
Stack MakeNull_Stack(){
Stack Header = (Node*)malloc(sizeof(Node));
(Header)->Next = NULL;
return Header;
}
//kiem tra danh sach rong
char Empty_Stack(Stack S) {
return S->Next == NULL;
}
//Khoi tao 1 node
Node *Make_Node(ElementType X) {
Node *temp = (Node*)malloc(sizeof(Node));
temp->Element = X;
return temp;
}
//xem mot phan tu vao Stack
void Push(ElementType X, Stack P) {
Node *Temp = Make_Node(X);
Temp->Next = P->Next;
P->Next = Temp;
}
//day 1 phan tu ra khoi Stack
void Pop(Stack P){
Stack Temp;
if (!Empty_Stack(P)){
Temp = P->Next;
P->Next = Temp->Next;
free(Temp);
}
}
Stack Input_Stack(int n) {
Stack L = MakeNull_Stack();
ElementType x;
for(int i = 1; i<=n; i++) {
printf("Phan tu %d = ",i);
scanf("%d",&x);
Push(x,L);
}
return L;
}
void Out_Stack(Stack L) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
void Selection_Sort(Stack L) {
Stack j, i = L->Next;
while(i->Next!=NULL) {
Stack min = i;
j = i->Next;
while(j!=NULL) {
if(min->Element>j->Element)
min = j;
j = j->Next;
}
ElementType temp = i->Element;
i->Element = min->Element;
min->Element = temp;
i = i->Next;
}
}
void main() {
clrscr();
int n;
printf("Nhap n = ");
scanf("%d",&n);
Stack L = Input_Stack(n);
printf("Danh sach chua sap xep:\n");
Out_Stack(L);
printf("\nSelection Sort:\n");
Selection_Sort(L);
Out_Stack(L);
getch();
}
Bài 3. Sử dụng Stack cài đặt bằng con trỏ cài đặt các thuật toán Bubble Sort, Insertion Sort, Selection Sort
. Bubble sort
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef int ElementType;
typedef struct Node {
ElementType Element;
Node *Next;
};
typedef Node *Stack;
//khoi tao danh sach rong
Stack MakeNull_Stack(){
Stack Header = (Node*)malloc(sizeof(Node));
(Header)->Next = NULL;
return Header;
}
//kiem tra danh sach rong
char Empty_Stack(Stack P) {
return P->Next == NULL;
}
//xen mot phan tu vao Stack
void Push(ElementType X, Stack P) {
Node *Temp = Make_Node(X);
Temp->Next = P->Next;
P->Next = Temp;
}
//day 1 phan tu ra khoi Stack
void Pop(Stack P){
Stack Temp;
if (!Empty_Stack(P)){
Temp = P->Next;
P->Next = Temp->Next;
free(Temp);
}
}
Stack Input_Stack(int n) {
Stack L = MakeNull_Stack();
ElementType x;
for(int i = 1; i<=n; i++) {
printf("Phan tu %d = ",i);
scanf("%d",&x);
Push(x,L);
}
return L;
}
void Out_Stack(Stack L) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
void Bubble_Sort(Stack L) {
Stack j, i = L->Next;
while(i->Next!=NULL) {
j = i->Next;
while(j!=NULL) {
if(i->Element>j->Element)
{
ElementType temp = i->Element;
i->Element = j->Element;
j->Element = temp;
}
j = j->Next;
}
i = i->Next;
}
}
void main() {
clrscr();
int n;
printf("Nhap n = ");
scanf("%d",&n);
Stack L = Input_Stack(n);
printf("Danh sach chua sap xep: \n");
Out_Stack(L);
printf("\n Bubble Sort: \n");
Bubble_Sort(L);
Out_Stack(L);
getch();
}
Insertion sort
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef int ElementType;
typedef struct Node {
ElementType Element;
Node *Next;
};
typedef Node *Stack;
//khoi tao danh sach rong
Stack MakeNull_Stack(){
Stack Header = (Node*)malloc(sizeof(Node));
(Header)->Next = NULL;
return Header;
}
//kiem tra danh sach rong
char Empty_Stack(Stack P) {
return P->Next == NULL;
}
//xen mot phan tu vao Stack
void Push(ElementType X, Stack P) {
Node *Temp = Make_Node(X);
Temp->Next = P->Next;
P->Next = Temp;
}
//day 1 phan tu ra khoi Stack
void Pop(Stack P){
Stack Temp;
if (!Empty_Stack(P)){
Temp = P->Next;
P->Next = Temp->Next;
free(Temp);
}
}
Stack Input_Stack(int n) {
Stack L = MakeNull_Stack();
ElementType x;
for(int i = 1; i<=n; i++) {
printf("Phan tu %d = ",i);
scanf("%d",&x);
Push(x,L);
}
return L;
}
void Out_Stack(Stack L) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
void Insertion_Sort(Stack L) {
Stack j, i = L->Next;
while(i->Next!=NULL) {
j = i->Next;
while(j!=NULL) {
if(i->Element>j->Element)
{
ElementType temp = i->Element;
i->Element = j->Element;
j->Element = temp;
}
j = j->Next;
}
i = i->Next;
}
}
void main() {
clrscr();
int n;
printf("Nhap n = ");
scanf("%d",&n);
Stack L = Input_Stack(n);
printf("Danh sach chua sap xep: \n");
Out_Stack(L);
printf("\n Insertion Sort: \n");
Insertion_Sort(L);
Out_Stack(L);
getch();
}
Selection sort
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef int ElementType;
typedef struct Node {
ElementType Element;
Node *Next;
};
typedef Node *Stack;
//khoi tao danh sach rong
Stack MakeNull_Stack(){
Stack Header = (Node*)malloc(sizeof(Node));
(Header)->Next = NULL;
return Header;
}
//kiem tra danh sach rong
char Empty_Stack(Stack P) {
return P->Next == NULL;
}
//xen mot phan tu vao Stack
void Push(ElementType X, Stack P) {
Node *Temp = Make_Node(X);
Temp->Next = P->Next;
P->Next = Temp;
}
//day 1 phan tu ra khoi Stack
void Pop(Stack P){
Stack Temp;
if (!Empty_Stack(P)){
Temp = P->Next;
P->Next = Temp->Next;
free(Temp);
}
}
Stack Input_Stack(int n) {
Stack L = MakeNull_Stack();
ElementType x;
for(int i = 1; i<=n; i++) {
printf("Phan tu %d = ",i);
scanf("%d",&x);
Push(x,L);
}
return L;
}
void Out_Stack(Stack L) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
void Selection_Sort(Stack L) {
Stack j, i = L->Next;
while(i->Next!=NULL) {
j = i->Next;
while(j!=NULL) {
if(i->Element>j->Element)
{
ElementType temp = i->Element;
i->Element = j->Element;
j->Element = temp;
}
j = j->Next;
}
i = i->Next;
}
}
void main() {
clrscr();
int n;
printf("Nhap n = ");
scanf("%d",&n);
Stack L = Input_Stack(n);
printf("Danh sach chua sap xep: \n");
Out_Stack(L);
printf("\n Selection Sort: \n");
Selection_Sort(L);
Out_Stack(L);
getch();
}
Bài 4. Sử dụng Stack, Stack cài đặt thuật toán Merge Sort cho 2 danh sách đã có thứ tự (tăng dần hoặc giảm dần).
Stack
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef unsigned int Position;
typedef int ElementType;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node * Stack;
Node * Make_Node(ElementType x) {
Node * temp = (Node*)malloc(sizeof(Node));
temp->Element = x;
return temp;
}
Stack MakeNull_Stack() {
Stack temp = (Stack)malloc(sizeof(Stack));
temp->Next = NULL;
return temp;
}
char Empty_Stack(Stack L) {
return L->Next == NULL;
}
void Insert(Stack L, Node * p) {
p->Next = L->Next;
L->Next = p;
}
void Insert(Stack L, Node * p, Position i) {
Stack temp = L;
Position j = 1;
while(j<i && temp!=NULL) {
temp = temp->Next;
j++;
}
if(i==j)
Insert(temp,p);
else
printf("\nThis position is not true.");
}
Stack Input_Stack(unsigned int n) {
Stack temp = MakeNull_Stack();
ElementType x;
unsigned int i = 1;
while(i<=n) {
printf("\tValue %d = ",i);
scanf("%d",&x);
Insert(temp,Make_Node(x));
i++;
}
return temp;
}
void Out_Stack(Stack L) {
Stack temp = L;
while(!Empty_Stack(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
//Sort Stack
void MergeSort(int m, int n, int &k, int A[], int B[], int C[]) {
int i = 0, j = 0;
k = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
if (i < m) {
for (int p = i; p < m; p++) {
C[k] = A[p];
k++;
}
} else {
for (int p = j; p < n; p++) {
C[k] = B[p];
k++;
}
}
}
void main() {
clrscr();
unsigned int n;
Position p;
ElementType x;
printf("Nhap n = ");
scanf("%d",&n);
Stack S = Input_Stack(n);
printf("This Stack: \n");
Out_Stack(S);
Bubble_Sort(S);
printf("\nThe new Stack: \n");
Out_Stack(S);
getch();
}
Queue
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef unsigned int Position;
typedef int ElementType;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node * Queue;
Node * Make_Node(ElementType x) {
Node * temp = (Node*)malloc(sizeof(Node));
temp->Element = x;
return temp;
}
Queue MakeNull_Queue() {
Queue temp = (Queue)malloc(sizeof(Queue));
temp->Next = NULL;
return temp;
}
char Empty_Queue(Queue L) {
return L->Next == NULL;
}
void Insert(Queue L, Node * p) {
p->Next = L->Next;
L->Next = p;
}
void Insert(Queue L, Node * p, Position i) {
Queue temp = L;
Position j = 1;
while(j<i && temp!=NULL) {
temp = temp->Next;
j++;
}
if(i==j)
Insert(temp,p);
else
printf("\nThis position is not true.");
}
Queue Input_Queue(unsigned int n) {
Queue temp = MakeNull_Queue();
ElementType x;
unsigned int i = 1;
while(i<=n) {
printf("\tValue %d = ",i);
scanf("%d",&x);
Insert(temp,Make_Node(x));
i++;
}
return temp;
}
void Out_Queue(Queue L) {
Queue temp = L;
while(!Empty_Queue(temp)) {
printf("%d\t",temp->Next->Element);
temp = temp->Next;
}
}
//Sort Queue
void MergeSort(int m, int n, int &k, int A[], int B[], int C[]) {
int i = 0, j = 0;
k = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
if (i < m) {
for (int p = i; p < m; p++) {
C[k] = A[p];
k++;
}
} else {
for (int p = j; p < n; p++) {
C[k] = B[p];
k++;
}
}
}
void main() {
clrscr();
unsigned int n;
Position p;
ElementType x;
printf("Nhap n = ");
scanf("%d",&n);
Queue S = Input_Queue(n);
printf("This Queue: \n");
Out_Queue(S);
Bubble_Sort(S);
printf("\nThe new Queue: \n");
Out_Queue(S);
getch();
}
Bài 5. Cho hai danh sách sử dụng Stack, List, Queue tiến hành nối hai danh sách thành 1 danh sách mới
STACK
.#include<conio.h>
#include<stdio.h>
#include<alloc.h>
typedef int ElementType;
typedef int Position;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node*Stack;
Stack MakeNull_Stack(){
Stack temp=(Stack)malloc(sizeof(Node));
temp->Next=NULL;
return temp;
}
Node*Make_Node(ElementType X){
Node*temp=(Node*)malloc(sizeof(Node));
temp->Element=X;
return temp;
}
char Empty_Stack(Stack L){
return L->Next==NULL;
}
void Insert_Stack(Stack &L,Node*P){
Stack temp=L;
while(!Empty_Stack(temp))
temp=temp->Next;
P->Next=temp->Next;
temp->Next=P;
}
Stack Insert_Po(Stack &L,Position i,ElementType X){
Position j=1;
Stack temp=L;
while(j<i){
j++;
temp=temp->Next;
}
if(j==i)
Insert_Stack(temp,Make_Node(X));
return L;
}
//Input n element in the Stack
Stack Input(unsigned int n){
Stack L=MakeNull_Stack();
ElementType X;
printf("\n");
for(int i=0;i<n;i++){
printf("Phan tu %d:\t",i);
scanf("%d",&X);
Insert_Stack(L,Make_Node(X));
}
return L;
}
//Insert a element in the first Stack
Stack Connect_Stack(Stack &L,Stack P){
if(P==NULL){
P=L;
return L;
}
if(L==NULL){
L=P;
return L;
}else
while(P->Next!=NULL){
Insert_Stack(L,Make_Node(P->Next->Element));
P=P->Next;
}
return L;
}
void Out_Stack(Stack L){
Stack temp=L->Next;
while(temp!=NULL){
printf("%d\t",temp->Element);
temp=temp->Next;
}
}
void main(){
clrscr();
unsigned int n,m;
printf("Nhap Stack L co n phan tu= ");
scanf("%d",&n);
Stack L=Input(n);
printf("\nThis Stack:");
Out_Stack(L);
//Insert_Po(L,2,6);
printf("\nNew Stack:");
Out_Stack(L);
printf("\nNhap Stack P co m phan tu= ");
scanf("%d",&m);
Stack P=Input(m);
printf("\nHai Stack sau khi duoc noi:\n\t");
Out_Stack(Connect_Stack(L,P));
getch();
}
LIST
#include<conio.h>
#include<stdio.h>
#include<alloc.h>
typedef int ElementType;
typedef int Position;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node*List;
List MakeNull_List(){
List temp=(List)malloc(sizeof(Node));
temp->Next=NULL;
return temp;
}
Node*Make_Node(ElementType X){
Node*temp=(Node*)malloc(sizeof(Node));
temp->Element=X;
return temp;
}
char Empty_List(List L){
return L->Next==NULL;
}
void Insert_List(List &L,Node*P){
List temp=L;
while(!Empty_List(temp))
temp=temp->Next;
P->Next=temp->Next;
temp->Next=P;
}
List Insert_Po(List &L,Position i,ElementType X){
Position j=1;
List temp=L;
while(j<i){
j++;
temp=temp->Next;
}
if(j==i)
Insert_List(temp,Make_Node(X));
return L;
}
//Input n element in List
List Input(unsigned int n){
List L=MakeNull_List();
ElementType X;
printf("\n");
for(int i=0;i<n;i++){
printf("Phan tu %d:\t",i);
scanf("%d",&X);
Insert_List(L,Make_Node(X));
}
return L;
}
//Insert a element in the first List
List Connect_List(List &L,List P){
if(P==NULL){
P=L;
return L;
}
if(L==NULL){
L=P;
return L;
}else
while(P->Next!=NULL){
Insert_List(L,Make_Node(P->Next->Element));
P=P->Next;
}
return L;
}
void Out_List(List L){
List temp=L->Next;
while(temp!=NULL){
printf("%d\t",temp->Element);
temp=temp->Next;
}
}
void main(){
clrscr();
unsigned int n,m;
printf("Nhap List L co n phan tu= ");
scanf("%d",&n);
List L=Input(n);
printf("\n This List: ");
Out_List(L);
//Insert_Po(L,2,6);
printf("\n New List: ");
Out_List(L);
printf("\nNhap List P co m phan tu= ");
scanf("%d",&m);
List P=Input(m);
printf("\n Hai List sau khi duoc noi:\n\t");
Out_List(Connect_List(L,P));
getch();
}
Queue
#include<conio.h>
#include<stdio.h>
#include<alloc.h>
typedef int ElementType;
typedef int Position;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node*Queue;
Queue MakeNull_Queue(){
Queue temp=(Queue)malloc(sizeof(Node));
temp->Next=NULL;
return temp;
}
Node*Make_Node(ElementType X){
Node*temp=(Node*)malloc(sizeof(Node));
temp->Element=X;
return temp;
}
char Empty_Queue(Queue L){
return L->Next==NULL;
}
void Insert_Queue(Queue &L,Node*P){
Queue temp=L;
while(!Empty_Queue(temp))
temp=temp->Next;
P->Next=temp->Next;
temp->Next=P;
}
Queue Insert_Po(Queue &L,Position i,ElementType X){
Position j=1;
Queue temp=L;
while(j<i){
j++;
temp=temp->Next;
}
if(j==i)
Insert_Queue(temp,Make_Node(X));
return L;
}
//Input n element in the Queue
Queue Input(unsigned int n){
Queue L=MakeNull_Queue();
ElementType X;
printf("\n");
for(int i=0;i<n;i++){
printf("Phan tu %d:\t",i);
scanf("%d",&X);
Insert_Queue(L,Make_Node(X));
}
return L;
}
//Insert a element in the first Queue
Queue Connect_Queue(Queue &L,Queue P){
if(P==NULL){
P=L;
return L;
}
if(L==NULL){
L=P;
return L;
}else
while(P->Next!=NULL){
Insert_Queue(L,Make_Node(P->Next->Element));
P=P->Next;
}
return L;
}
void Out_Queue(Queue L){
Queue temp=L->Next;
while(temp!=NULL){
printf("%d\t",temp->Element);
temp=temp->Next;
}
}
void main(){
clrscr();
unsigned int n,m;
printf("Nhap Queue L co n phan tu= ");
scanf("%d",&n);
Queue L=Input(n);
printf("\nThis Queue:");
Out_Queue(L);
//Insert_Po(L,2,6);
printf("\nNew Queue:");
Out_Queue(L);
printf("\nNhap Queue P co m phan tu= ");
scanf("%d",&m);
Queue P=Input(m);
printf("\nHai Queue sau khi duoc noi:\n\t");
Out_Queue(Connect_Queue(L,P));
getch();
}
Bài 6. Cho Stack L gồm n số nguyên nhập từ bàn phím. Thực hiện các yêu cầu sau:
- Tính tổng các số nguyên trong Stack.
- Kiểm tra phần tử x có tồn tại trong Stack.
- Tìm phần tử có giá trị lớn nhất trong Stack.
- Tính tổng các số nguyên tố trong Stack.
#include <stdio.h>
#include <conio.h>
#define maxlength 100
typedef int elementtype;
//typedef float elementtype;
typedef struct
{
elementtype elements[maxlength];
int top_idx;
}Stack;
/*=== tao ngan xep rong ===*/
void makenull_Stack(Stack *s)
{
s ->top_idx = 0;
}
/*=== kiem tra ngan xep rong ===*/
int empty_Stack(Stack s)
{
return (s.top_idx == 0);
}
/*=== kiem tra ngan xep day ===*/
int full_Stack(Stack s)
{
return (s.top_idx == maxlength);
}
/*=== lay noi dung phan tu tai vi tri dinh cua ngan xep ===*/
elementtype top(Stack s)
{
if(!empty_Stack(s))
return s.elements[s.top_idx];
else {
printf("\nLoi ! Stack rong");
return NULL;
}
}
/*=== them phan tu vao ngan xep ===*/
void push(elementtype x, Stack *s)
{
if(full_Stack(*s))
printf("\nLoi ! Stack day khong the them");
else{
s -> top_idx=s->top_idx+1;
/* giam top 1 don vi ( cho top chi den phan tu ke)*/
s -> elements[s->top_idx]=x;
/* bo phan tu moi voi dau ngan xep */
}
}
/* === xoa phan tu ra khoi ngan xep ===*/
void pop (Stack *S)
{
if(empty_Stack(*S))
printf("\nLoi ! Stack rong ");
else{
S ->top_idx=(S -> top_idx-1);
/* tang top 1 don vi (cho top chi lui xuong phan tu sau)*/
}
}
//in ngan xep
void Out_Stack(Stack s){
Stack temp =s;
while(!empty_Stack(temp)){
printf("%d",top(temp));
pop(&temp);
}
}
/* chuong trinh chinh*/
void main()
{
int n,m;
Stack s;
clrscr();
makenull_Stack(&s);
while(m!=-1){
scanf("%d",&m);
if(m!=-1)
push(m,&s);
}
printf("\n Stack vua nhap la:");
Out_Stack(s);
getch();
}
Bài 7. Cho Stack gồm n số thực nhập từ bàn phím (cài đặt bằng mảng và con trỏ). Thực hiện các yêu cầu sau:
- Thêm 1 phần tử có giá trị x vào vị trí p trong danh sách.
- Xoá 1 phần tử tại vị trí p trong danh sách.
- Tính tích các phần tử trong danh sách.
- Tính tổng bình phương các phần tử trong danh sách.
- Sắp xếp danh sách theo thứ tự tăng dần.
- Sử dụng thuật toán tìm kiếm nhị phân tìm kiếm phần tử có giá trị x trong danh sách.
- Thực hiện việc đảo các giá trị trong Stack.
- Thực hiện việc xoá các phần tử trùng trong Stack.
#include<conio.h>
#include<stdio.h>
#include<alloc.h>
typedef char elementtype;
typedef struct node{
elementtype element;
node*next;
};
typedef node * Stack;
typedef Stack position;
node * make_node(elementtype x){
node *temp=(node*)malloc(sizeof(node));
temp->element=x;
return temp;
}
Stack makenull_Stack(){
Stack temp=(Stack)malloc (sizeof(Stack));
temp->next=NULL;
return temp;
}
char empty_Stack(Stack s){
return s->next==NULL;
}
void insert_Stack(elementtype x,position p,Stack*l){
position t;
t = (node*)malloc(sizeof(node));
t->element = x;
t->next = p->next;
p->next = t;
}
void delete_Stack(position p,Stack*l){
position t;
if(p->next !=NULL){
t->next = p->next;
p->next = p->next->next;
free(t);
}
else printf("\nloi! danh sach rong khong the xoa ");
}
void insert_endStack(Stack s, elementtype x){
node *p=make_node(x);
p->next=s->next;
s->next=p;
}
void pop(Stack s){
if(!empty_Stack(s))
{
printf("\n loi! Stack rong");
node *temp=s->next;
s->next=temp->next;
free(temp);
}
}
void out_Stack(Stack s){
Stack temp=s->next;
while(temp!=NULL){
printf("%d\t", temp->element);
temp = temp->next;
}
}
Stack input_Stack(unsigned int n){
Stack temp = makenull_Stack();
unsigned int i=0;
elementtype x;
while(i<n)
{
printf("element %d=",i);
scanf("%d", &x);
insert_endStack(temp, x);
i ++;
}
return temp;
}
elementtype sum(Stack s){
elementtype temp=0;
Stack p=s->next;
while(p!=NULL)
{
temp+=p->element;
p=p->next;
}
return temp;
}
int test(Stack s, elementtype x){
Stack temp = s->next;
while(temp!=NULL)
{
if(temp->element ==x){
return 1;
}
temp = temp->next;
}
return 0;
}
void main(){
clrscr();
unsigned int n;
elementtype x;
printf("n=");
scanf("%d",&n);
Stack s = input_Stack(n);
printf("this Stack:\n");
out_Stack(s);
printf("\n\n danh sach sau khi khoi tao rong la ");
if(empty_Stack(l)) printf ("\n\n danh sach rong ");
else printf("\n\n danh sach khong rong ");
for(int i=1; i<=5; i++)
insert_Stack (i+10,endStack(l),&l);
printf("\n\n danh sach sau khi dua cac so tu 11-15 vao theo thu tu la \n\n ");
print_Stack(l);
printf("\sum of all values in Stack: %d", sum(s));
printf("\n input value to find:");
scanf("%d", &x);
if(test (s,x))
printf("this value has in Stack ");
else
printf("this value don't have int Stack");
getch();
}
Bài 8. Cho Stack gồm n số nguyên được nhập từ bàn phím (cài đặt bằng mảng và con trỏ). Thực hiện các yêu cầu sau:
- Thêm 1 phần tử vào Stack.
- Xoá phần tử ra khỏi Stack.
- Sắp xếp Stack theo thứ tự giảm dần.
- Đảo các giá trị của các phần tử trong Stack.
#include "conio.h"
#include "stdio.h"
#define MaxLength 100
#define Null -1
typedef int ElementType;
typedef struct {
ElementType Elements[MaxLength];
unsigned int Front, Rear;
}Stack;
//Make null a Stack
Stack MakeNull_Stack() {
Stack temp;
temp.Front = 0;
temp.Rear = 0;
return temp;
}
//Result 1 if Stack is null else result 0
char Empty_Stack(Stack S){
return S.Rear==0;
}
//Result 1 if Stack is full else result 0
char Full_Stack(Stack S){
return (S.Rear-S.Front+1)==MaxLength;
}
//Get a value from top Stack
ElementType Top(Stack S){
if (!Empty_Stack(S))
return S.Elements[S.Front-1];
else {
printf("\tEmpty Stack!");
return Null;
}
}
//Delete a value from top Stack
void Pop(Stack &S){
if (!Empty_Stack(S))
{
S.Front++;
if(S.Front>S.Rear)
S = MakeNull_Stack();
}
else
printf("\tEmpty Stack!");
}
//Insert a value on end Stack
void Push(ElementType X, Stack &S){
if (Full_Stack(S))
printf("Full Stack!");
else {
if(Empty_Stack(S))
S.Front = 1;
if(S.Rear == MaxLength)
{
S.Rear = S.Rear-S.Front + 1;
for(unsigned int i = 0; i<S.Rear; i++)
S.Elements[i] = S.Elements[i+S.Front-1];
S.Front = 1;
}
S.Elements[S.Rear] = X;
S.Rear++;
}
}
//Print a Stack to screen
void Out_Stack(Stack S) {
Stack temp = S;
while(!Empty_Stack(temp)) {
printf("%d\t",Top(temp));
Pop(temp);
}
}
//Input a Stack with n elements from keyboard
Stack Input_Stack(unsigned int n) {
Stack S = MakeNull_Stack();
ElementType x;
for(int i = 0; i<n; i++) {
printf("\tValue %d :",i);
scanf("%d",&x);
Push(x,S);
}
return S;
}
//the main programming
void main() {
clrscr();
unsigned int n;
printf("Input n = ");
scanf("%d",&n);
Stack S = Input_Stack(n);
printf("This Stack:\n");
Out_Stack(S);
getch();
}
Kiem tra 2
Cho Stack gồm n số nguyên được nhập từ bàn phím. Thực hiện việc nhập xuất Stack ra màn hinh. Với các hình thức cài đặt sau:
1.Cài đặt bằng mảng theo phương pháp tịnh tuyến.
#include "conio.h"
#include "stdio.h"
#define MaxLength 100
#define Null -1
typedef int ElementType;
typedef struct {
ElementType Elements[MaxLength];
unsigned int Front, Rear;
}Stack;
//Make null a Stack
Stack MakeNull_Stack() {
Stack temp;
temp.Front = 0;
temp.Rear = 0;
return temp;
}
//Result 1 if Stack is null else result 0
char Empty_Stack(Stack S){
return S.Rear==0;
}
//Result 1 if Stack is full else result 0
char Full_Stack(Stack S){
return (S.Rear-S.Front+1)==MaxLength;
}
//Get a value from top Stack
ElementType Top(Stack S){
if (!Empty_Stack(S))
return S.Elements[S.Front-1];
else {
printf("\tEmpty Stack!");
return Null;
}
}
//Delete a value from top Stack
void Pop(Stack &S){
if (!Empty_Stack(S))
{
S.Front++;
if(S.Front>S.Rear)
S = MakeNull_Stack();
}
else
printf("\tEmpty Stack!");
}
//Insert a value on end Stack
void Push(ElementType X, Stack &S){
if (Full_Stack(S))
printf("Full Stack!");
else {
if(Empty_Stack(S))
S.Front = 1;
if(S.Rear == MaxLength)
{
S.Rear = S.Rear-S.Front + 1;
for(unsigned int i = 0; i<S.Rear; i++)
S.Elements[i] = S.Elements[i+S.Front-1];
S.Front = 1;
}
S.Elements[S.Rear] = X;
S.Rear++;
}
}
//Print a Stack to screen
void Out_Stack(Stack S) {
Stack temp = S;
while(!Empty_Stack(temp)) {
printf("%d\t",Top(temp));
Pop(temp);
}
}
//Input a Stack with n elements from keyboard
Stack Input_Stack(unsigned int n) {
Stack S = MakeNull_Stack();
ElementType x;
for(int i = 0; i<n; i++) {
printf("\tValue %d :",i);
scanf("%d",&x);
Push(x,S);
}
return S;
}
//the main programming
void main() {
clrscr();
unsigned int n;
printf("Input n = ");
scanf("%d",&n);
Stack S = Input_Stack(n);
printf("This Stack:\n");
Out_Stack(S);
getch();
}
2. Cài đặt bằng mảng theo phương pháp xoay.
#include "conio.h"
#include "stdio.h"
#define MaxLength 100
#define Null -1
typedef int ElementType;
typedef struct {
ElementType Elements[MaxLength];
unsigned int Front, Rear;
}Stack;
//Make null a Stack
Stack MakeNull_Stack() {
Stack temp;
temp.Front = 0;
temp.Rear = 0;
return temp;
}
//Result 1 if Stack is null else result 0
char Empty_Stack(Stack S){
return S.Rear==0;
}
//Result 1 if Stack is full else result 0
char Full_Stack(Stack S){
return (S.Rear-S.Front+1 % MaxLength)==0;
}
//Get a value from top Stack
ElementType Top(Stack S){
if (!Empty_Stack(S))
return S.Elements[S.Front-1];
else {
printf("\tEmpty Stack!");
return Null;
}
}
//Delete a value from top Stack
void Pop(Stack &S){
if (!Empty_Stack(S))
{
if (S.Front == S.Rear)
S = MakeNull_Stack();
else
if(S.Front == MaxLength)
S.Front = 1;
else
S.Front++;
}
else
printf("\tEmpty Stack!");
}
//Insert a value on bottom Stack
void Push(ElementType X, Stack &S){
if (Full_Stack(S))
printf("Full Stack!");
else {
if(Empty_Stack(S))
S.Front = 1;
if(S.Rear == MaxLength)
S.Rear = 0;
S.Elements[S.Rear] = X;
S.Rear++;
}
}
//Print a Stack to Dos screen
void Output_Stack(Stack S) {
Stack temp = S;
while(!Empty_Stack(temp)) {
printf("%d\t",Top(temp));
Pop(temp);
}
}
//Input a Stack with n elements from keyboard
Stack Input_Stack(unsigned int n) {
Stack S = MakeNull_Stack();
ElementType x;
for(int i = 0; i<n; i++) {
printf("\tValue %d :",i);
scanf("%d",&x);
Push(x,S);
}
return S;
}
//the main programming
void main() {
clrscr();
unsigned int n;
printf("Input n = ");
scanf("%d",&n);
Stack S = Input_Stack(n);
printf("This Stack:\n");
Output_Stack(S);
getch();
}
3. Cài đặt bằng con trỏ.
#include "conio.h"
#include "stdio.h"
#include "alloc.h"
typedef int ElementType;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef struct{
Node* Front;
Node* Rear;
}Stack;
//Make null a Stack
Stack MakeNull_Stack(){
Stack temp;
Node* Header = (Node*)malloc(sizeof(Node));
Header->Next = NULL;
temp.Front = Header;
temp.Rear = Header;
return temp;
}
//Result 0 if Stack is null else result 1
char Empty_Stack(Stack Q){
return (Q.Front==Q.Rear);
}
//Insert a element on bottom Stack
void Push(ElementType X, Stack &Q){
Q.Rear->Next = (Node*)malloc(sizeof(Node));
Q.Rear = Q.Rear->Next;
Q.Rear->Element = X;
Q.Rear->Next = NULL;
}
//Delete a element out Stack
void Pop(Stack &Q){
if (!Empty_Stack(Q)){
Node* temp = Q.Front->Next;
Q.Front->Next = temp->Next;
free(temp);
}
else
printf("\tStack is empty");
}
//Input n elements from keyboard and save on a Stack
Stack Input_Stack(unsigned int n){
Stack temp = MakeNull_Stack();
ElementType x;
for(unsigned int i = 1; i<=n; i++){
printf("Value %d = ",i);
scanf("%d",&x);
Push(x,temp);
}
return temp;
}
//Print a Stack out screen
void Output_Stack(Stack Q){
if(!Empty_Stack(Q)){
Stack temp = Q;
while(!Empty_Stack(temp)){
printf("\t%d", temp.Front->Next->Element);
temp.Front = temp.Front->Next;
}
}
}
//the main programming
void main(){
clrscr();
Stack Q;
unsigned int n;
printf("\nInput n = ");
scanf("%d",&n);
Q = Input_Stack(n);
printf("This Stack:\n");
Output_Stack(Q);
getch();
}
