Interval tree

Đề bài:

Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0.

Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị.

Cho q câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất thuộc đoạn [u, v]

Giới hạn

n, m, q <= 50000

k > 0

Giá trị của một phần tử luôn không vượt quá 231-1

Input

Dòng 1: n, m

m dòng tiếp theo, mỗi dòng chứa u, v, k cho biết một phép biến đổi

Dòng thứ m+2: p

p dòng tiếp theo, mỗi dòng chứa u, v cho biết một phép biến đổi

Output

Gồm p dòng chứa kết quả tương ứng cho từng câu hỏi.

Example

Input:

6 2

1 3 2

4 6 3

1

3 4

Output:

3

Gợi ý: Sử dụng interval tree

https://nguyenvanquan7826.wordpress.com/2013/11/09/spoj-qmax/

code:

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <fstream>

#include <algorithm>

#include <cmath>

//#define INP "QMAX.INP"

//#define OUT "QMAX.OUT"

using namespace std;

int ans = 0, *a, *T, n, m, q, u, v, k;

// trong do a la mang luu thong tin

// T la cay interval tree

// n la so phan tu

// m la so phep bien doi

// q la so cau hoi

// u la gia tri phan tu dau

// v la gia tri phan tu cuoi

// k gia tri trong khoang u v se duoc tang k don vi

void updateTree(int k, int l, int r){

    int c;

    if (l > r) return;

    if (l == r) {

        T[k] = a[l];

        return;

    }

    c = (l + r) / 2;

    updateTree(k*2, l, c);

    updateTree(k*2 + 1, c + 1, r);

    T[k] = max(T[k*2], T[k*2+1]);

    return;

}

void findMax(int k, int l, int r, int i, int j){

    int c;

    if (l > j || r < i) return;

    if (i <= l && j >= r){

        ans = max(ans, T[k]);

        return;

    }

    c = (l + r) / 2;

    findMax(k*2, l, c, i, j);

    findMax(k*2 + 1, c + 1, r, i, j);

    return;

}

int main(){

    //freopen(INP, "r", stdin);

    //freopen(OUT, "w", stdout);

    cout<<"Nhap hai gia tri n , m"<<endl;

    scanf("%d %d", &n, &m);//cin >> n >> m;

    a = new int[n+2];

    T = new int[4*n]; // interval tree su dung mang co so phan tu toi da la 4*n -5

    for (int i = 0; i < n+2; i++)

        a[i] = 0;

    for (int i = 0; i < 4*n; i++)

        T[i] = 0;

    for (int i = 1; i <= m; i++){

        scanf("%d %d %d", &u, &v, &k); //cin >> u >> v >> k;

        a[u] += k;

        a[v+1] -= k;

    }

    for (int i = 2; i < n + 1; i++)

        a[i] = a[i] + a[i-1];

    updateTree(1, 1, n);

    scanf("%d", &q);//cin >> q;

    ans = 0;

    for (int i = 0; i < q; i++){

        scanf("%d %d", &u, &v);//cin >> u >> v;

        ans = 0;

        findMax(1, 1, n, u, v);

        cout << ans << endl;

    }

    return 0;

}

Read More

Thuật toán QuickSort trong danh sách liên kết đơn

#include<iostream>

using namespace std;

int n;

struct Node{

int data;

Node *next;// chua dia chi node ke tiep ma no tro toi

};

struct List{

Node *head;

Node *tail;

};

void Init(List &l){ // k tao List rong

l.head = l.tail = NULL;

}

Node *creatNode(int x ){ //tao thong tin cho node

Node *p = new Node;

if(p == NULL) return NULL;

p->next = NULL;

p->data = x;

return p;

}

bool isEmpty(List l ){ // k tr a xem lieu List co rong hay k.

if(l.head == NULL ) return true;

return false;

}

// chen vao dau List:

void addHead(List &l, int x ){

Node *p = creatNode(x);

if(isEmpty(l)) l.head = l.tail = p;

else{

p->next = l.head; // con tro next cua p tro toi dia chi cua node head(ban dau)

l.head = p; // cap nhat node head( luc sau )

}

}

// ham chen vao cuoi List

void addTail(List &l, int x ){

Node *p = creatNode(x);

if(isEmpty(l)) addHead(l,x);

else{

l.tail->next = p;

l.tail = p;

}

}

// tim kiem

Node *search(List l, int k ){

Node *p = l.head;

while(p!=NULL) {

if(p->data == k ) return p;

else p = p->next;

}

return NULL;

}

void addMid(List &l, int x, int k ){ // chen node co data = x vao sau node co data  = k;

Node *p = search(l,k);

if(p!=NULL){

Node *q= creatNode(x);

Node *r = p->next;

p->next = q;

q->next = r;

}

else cout<<"\nKhong tim thay node co data = k.";

}

void addAtK(List &l, int x, int k ){ // chen vi tri bat ki;

if(isEmpty(l) || k<= 1 ) addHead(l,x);

else if(k>= n) addTail(l,x);

else{

Node *p = creatNode(x);

Node *q = new Node, *w = new Node;

Node *r = l.head;

int dem = 0;

while(r!=NULL){

dem++;

q = r;

if(dem == k ) break;

else r = r->next;

}

w = l.head;

while(w->next!= q) w = w->next;

w->next = p;

p->next = r;

}

}

// nhap vao mot list bat ki

void nhap(List &l){

cout<<"\nnhap so ptu ban dau cua List: "; cin>> n;

for(int i = 1; i<= n; i++ ) addTail(l,i);

}

// xuat thong tin ra man hinh

void xuat(List l ){

Node *p = l.head;

while(p!=NULL){

cout<<" " << p->data;

p = p->next;

}

}

void delHead(List &l ){ // xoa node o dau List

if(!isEmpty(l)){

Node *p = l.head;

l.head = l.head->next; // cap nhat l.head

delete p; // xoa bo node head ban dau

}

}

void delTail(List &l ){

if(!isEmpty(l)){

Node *p = l.head;

Node *q = new Node;

while(p->next != l.tail ) p = p->next; // tim node ngay truoc tail

q = p; // gan node nay cho node q

p = p->next; // p chinh la node tail can xoa

l.tail = q; // cap nhat l.tail

l.tail->next = NULL; // cap nhat node next cho l.tail

delete p;

}

}

void delAtK(List &l, int k ){

if(k<= 1) delHead(l);

else if(k>=n) delTail(l);

else{

int dem = 0;

if(!isEmpty(l)){

Node *p = l.head;

Node *q = new Node;

while(p != NULL){ // tim node thu k.

dem++;

q = p;

if(dem == k ) break; // tim thay thi break

else p= p->next; // k thi tim tiep

}

Node *r = l.head;

while(r->next != q ) r = r->next; // tim node k-1

r->next = q->next; // cho node next cua node k-1 tro toi node k+1;

delete q;

}

}

}

void QuickSort(List &l ){

List l1, l2;

Node *tag, *p;

if(l.head == l.tail ) return;

Init(l1); Init(l2);

tag = l.head;

l.head = l.head->next; // cap nhat lai l.head

tag->next = NULL;// co lap tag

while( l.head!= NULL ){

p = l.head;

l.head = l.head->next;

p->next = NULL;

if(p->data <= tag->data ) addHead(l1,p->data);

else addHead(l2,p->data);

}

QuickSort(l1); // goi de qui sap xep l1, l2

QuickSort(l2);

if(l1.head != NULL ){ // l1 k rong

l.head = l1.head; // lay head cua l1 gan cho head cua l;

l1.tail->next = tag;

} // l1 rong

else l.head = tag;

tag->next = l2.head;

if(l2.head!= NULL ) l.tail = l2.tail;

else l.tail = tag;

}

void menu(){

List l;

Init(l);

nhap(l);

xuat(l);

int k, x, lc;

do{

cout<<"\n______MENU______\n1_Chen dau.\n2_chen cuoi."

<<"\n3_Chen sau vi tri node data = k.\n4_Chen vao vi tri bat ki."

<<"\n5_Xuat Thong tin List.\n6_Xoa phan tu dau List."

<<"\n7_Xoa phan tu o cuoi List.\n8_Xoa node o vi tri k."

<<"\n9_Sap xep QuickSort."

<<"\n0_Thoat.\n_Ban chon ? ";

cin>> lc;

switch(lc){

case 0: break;

case 1: cout<<"\nNhap x: "; cin>> x; addHead(l,x); n++; break;

case 2: cout<<"\nNhap x: "; cin>> x; addTail(l,x); n++; break;

case 3: cout<<"\nNhap x, k: "; cin>> x >> k; addMid(l,x, k);n++; break;

case 4: cout<<"\nNhap x, vi tri k: "; cin>> x >> k; addAtK(l,x,k); n++; break;

case 5: xuat(l); break;

case 6: delHead(l); n--; break;

case 7: delTail(l); n--; break;

case 8: cout<<"\nNhap vi tri k: "; cin>> k; delAtK(l,k); n--; break;

case 9: QuickSort(l); break;

}

}while(lc != 0 );

}

int main(){

menu();

return 0;

}

Read More

Danh sách liên kết vòng

// Danh sach lien ket don vong.

#include<iostream>
using namespace std;
int n;
struct Node{
int data;
Node *next;// chua dia chi node ke tiep ma no tro toi
};

struct List{
Node *head;
Node *tail;
};

void Init(List &l){ // k tao List rong
l.head = l.tail = NULL;
}

Node *creatNode(int x ){ //tao thong tin cho node
Node *p = new Node;
if(p == NULL) exit(1);
p->next = NULL;
p->data = x;
return p;
}

bool isEmpty(List l ){ // k tr a xem lieu List co rong hay k.
if(l.head == NULL ) return true;
return false;
}

// chen vao dau List:
void addHead(List &l, int x ){
Node *p = creatNode(x);
if(isEmpty(l)) l.head = l.tail = p;
else{
p->next = l.head; // con tro next cua p tro toi dia chi cua node head(ban dau)
l.head = p; // cap nhat node head( luc sau )
}
l.tail->next = l.head; // khep vong don.
}
// ham chen vao cuoi List
void addTail(List &l, int x ){
Node *p = creatNode(x);
if(isEmpty(l)) addHead(l,x);
else{
l.tail->next = p;
l.tail = p;
}
l.tail->next = l.head; // khep vong don
}
// tim kiem
Node *search(List l, int k ){
Node *p = l.head;
do {
if( p->data == k ) return p;
else p = p->next;
} while( p != l.head );
return NULL;
}

void addMid(List &l, int x, int k ){ // chen node co data = x vao sau node co data  = k;
Node *p = search(l,k);
if(p!=NULL){
Node *q= creatNode(x);
Node *r = p->next;
p->next = q;
q->next = r;
}
else cout<<"\nKhong tim thay node co data = k.";
}
/*
void addAtK(List &l, int x, int k ){ // chen vi tri bat ki;
if(isEmpty(l) || k<= 1 ) addHead(l,x);
else if(k>= n) addTail(l,x);
else{
Node *p = creatNode(x);
Node *q = new Node, *w = new Node;
Node *r = l.head;
int dem = 0;
while(r!=NULL){
dem++;
q = r;
if(dem == k ) break;
else r = r->next;
}
w = l.head;
while(w->next!= q) w = w->next;
w->next = p;
p->next = r;
}
} */
// nhap vao mot list bat ki
void nhap(List &l){
cout<<"\nnhap so ptu ban dau cua List: "; cin>> n;
for(int i = 1; i<= n; i++ ) addTail(l,i);
}
// xuat thong tin ra man hinh
void xuat(List l ){
if(l.head){
cout<< "\nDanh sach cac phan tu: \n";
Node *p = l.head;
do{
cout<<" " << p->data;
p = p->next;
}while( p != l.head );
}
else cout<< "\nDanh Sach Rong";
cout<< endl;
}

void delHead(List &l ){ // xoa node o dau List
if(!isEmpty(l)){
if(l.head != l.tail ){
Node *p = l.head;
l.head = l.head->next; // cap nhat l.head
delete p; // xoa bo node head ban dau
l.tail->next = l.head;
}
else l.head = NULL;
}
else return;
}

void delTail(List &l ){
if(!isEmpty(l)){
if(l.head != l.tail ){
Node *p = l.head;
Node *q = new Node;
while(p->next != l.tail ) p = p->next; // tim node ngay truoc tail
q = p; // gan node nay cho node q
p = p->next; // p chinh la node tail can xoa
l.tail = q; // cap nhat l.tail
l.tail->next = l.head;
delete p;
} else l.head = NULL;
}
else return;
}

void delAtK(List &l, int k ){
if( k <= 1) delHead(l);
else if( k >= n ) delTail(l);
else{
int dem = 0;
if(!isEmpty(l)){
Node *p = l.head;
Node *q = new Node;
while(p != NULL){ // tim node thu k.
dem++;
q = p;
if(dem == k ) break; // tim thay thi break
else p= p->next; // k thi tim tiep
}
Node *r = l.head;
while(r->next != q ) r = r->next; // tim node k-1
r->next = q->next; // cho node next cua node k-1 tro toi node k+1;
delete q;
}
}
}

void menu(){
List l;
Init(l);
nhap(l);
xuat(l);
int k, x, lc;
do{
cout<<"\n______MENU______\n1_Chen dau.\n2_chen cuoi."
<<"\n3_Chen sau vi tri node data = k.\n4_Chen vao vi tri bat ki."
<<"\n5_Xuat Thong tin List.\n6_Xoa phan tu dau List."
<<"\n7_Xoa phan tu o cuoi List.\n8_Xoa node o vi tri k."
// <<"\n9_Sap xep QuickSort."
<<"\n0_Thoat.\n_Ban chon ? ";
cin>> lc;
switch(lc){
case 0: break;
case 1: cout<<"\nNhap x: "; cin>> x; addHead(l,x); n++; break;
case 2: cout<<"\nNhap x: "; cin>> x; addTail(l,x); n++; break;
case 3: cout<<"\nNhap x, k: "; cin>> x >> k; addMid(l,x, k);n++; break;
// case 4: cout<<"\nNhap x, vi tri k: "; cin>> x >> k; addAtK(l,x,k); n++; break;
case 5: xuat(l); break;
case 6: delHead(l); n--; break;
case 7: delTail(l); n--; break;
case 8: cout<<"\nNhap vi tri k: "; cin>> k; delAtK(l,k); n--; break;
// case 9: QuickSort(l); break;
}
}while(lc != 0 );
}

int main(){
menu();
return 0;
}

Read More

Tạo queue bằng danh sách liên kết đơn

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   main.cpp
 * Author: KHOA
 *
 * Created on August 26, 2016, 9:10 AM
 */

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

struct Node {
    int data;
    Node *next;
};

struct List {
    Node *head;
    Node *tail;
};

// khoi tao queue

void Init(List &q) {
    q.head = q.tail = NULL; // gan con tro head va tail cua queue bang NULL
}

// tao Node trong queue

Node *creat_Node(int x) {
    Node *p = new Node;
    if (p != NULL) {
        p->data = x; // dua gia tri cua x vao trong data
        p->next = NULL; // gan phan tu ke tiep bang NULL
        return p; // tra ve con tro p trong queue
    } else {
        return NULL; // neu cap phat khong thanh cong thi tra ve NULL
    }

}

// kiem tra xem queue co rong khong

bool isEmpty(List &q) {
    Node *p = q.head;
    if (p == NULL) return true; // neu phan tu dau bang NULL thi queue rong
    else return false; // neu khong thi khong phai rong
}

// push Node vao trong queue

void push(List &q, int x) {
    Node *r = creat_Node(x);
    if (isEmpty(q)) q.head = q.tail = r;
    else {
        r->next = q.head; // đưa phần tử mới vào trỏ tới next là phần tử đầu
        q.head = r; // cập nhật phần tử mới đưa vào đó là phần tử đầu
    }
}

// pop Node ra khoi queue

void pop(List &q) {
    Node *p = q.head;
    while (p->next->next != NULL) { // tim vi tri phan tu thu 2 tu duoi len
        p = p->next;
    }
    // p la phan tu o vi tri 2 tu duoi len
    Node *r = p->next; // r la phan tu cuoi cung cua queue
    p->next = NULL;
    delete r; // xoa phan tu r
}

// nhap phan tu vao trong queue

void nhap(List &q) {
    int n;
    cout << "Nhap so luong Node trong queue: ";
    cin>>n;
    for (int i = 1; i <= n; i++) {
        int x;
        cout << "Phan tu thu " << i << ": ";
        cin>>x;
        push(q, x); // dua phan tu vao trong queue
    }
}

// xuat cac phan tu ra man hinh

void xuat(List &q) {
    Node *p = q.head;
    while (p != NULL) {
        cout << " " << p->data;
        p = p->next;
    }
}

// tim Node trong queue

Node *search_Node(List &q, int x) {
    Node *p = q.head;
    while (!isEmpty(q)) {
        if (p->data == x) return p; // tra ve con tro p khi tim thay phan tu trong queue
        else p = p->next; // khong thi tim tiep
    }
    return NULL; // neu khong tim duoc tra ve NULL
}

int main() {
    List q;
    Init(q);
    nhap(q);
    xuat(q);
    int lc, x;

    do {
        cout << "\n _ _ _CHUONG TRINH QUEUE_ _ _"
                << "\n 1. Push queue "
                << "\n 2. Pop queue "
                << "\n 3. Tim phan tu trong queue "
                << "\n 0. Thoat ";
        cout << endl;
        cout << "Nhap lua chon: ";
        cin>>lc;
        switch (lc) {
            case 1:
            {
                cout << "Nhap phan tu can push: ";
                cin>>x;
                push(q, x);
                break;
            }
            case 2:
            {
                cout << "Ban da dua 1 phan tu ra khoi queue! ";
                pop(q);
                break;
            }
            case 3:
            {
                cout << "Nhap phan tu can tim kiem: ";
                cin>>x;
                if (search_Node(q, x) != NULL) cout << "Tim thay phan tu trong queue! ";
                else cout << "Khong tim thay phan tu do trong queue! ";
            }
            case 0: break;
        }
        xuat(q);
        cout << "\n";
    } while (lc != 0);

    return 0;
}

Read More

Tạo Stack bằng danh sách liên kết đơn

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   khoa.cpp
 * Author: KHOA
 *
 * Created on August 26, 2016, 9:16 AM
 */

#include <iostream>
#include<stdio.h>
#include<stdio.h>
using namespace std;

struct Node {
    int data;
    Node *next;
};

struct List {
    Node *head;
    Node *tail;
};

// khoi tao stack

void Init(List &s) {
    s.head = s.tail = NULL;
}

// kiem tra stack co rong khong

bool isEmpty(List &s) {
    if (s.head == NULL) return true;
    else return false;
}

// tao Node

Node *creat_Node(int x) {
    Node *p = new Node;
    if (p != NULL) {
        p->data = x;
        p->next = NULL;
    } else return NULL;
}

// Push vao stack

void push(List &s, int x) {
    Node *p = creat_Node(x);
    if (isEmpty(s)) {
        s.head = s.tail = p; // neu stack rong thi ta gan p la phan tu dau va cuoi
    } else {
        p->next = s.head; // cho phan tu ke tiep bang phan tu dau
        s.head = p; // cap nhat phan tu dau la phan tu moi them vao
    }
}

// Pop phan tu ra khoi stack

void pop(List &s) {
    Node *p = s.head;
    if (!isEmpty(s)) {
        s.head = p->next;
        delete p;
    } else {
        cout << "\nDanh sach da rong! ";
    }
}

// tim kiem phan tu trong stack

Node *search_Node(List &s, int x) {
    Node *q = s.head;
    while (q != NULL) {
        if (q->data == x) {
            return q;
        } else {
            q = q->next;
        }
    }
    return NULL;
}
// Nhap du lieu cho Stack

void nhap(List &s) {
    int n;
    cout << "nhap so luong phan tu cho stack: ";
    cin>>n;
    for (int i = 1; i <= n; i++) {
        int x;
        cout << "Phan tu " << i << ": ";
        cin>>x;
        push(s, x);
    }
}

// xuat cac phan tu trong stack

void xuat(List &s) {
    Node *p = s.head;
    while (p != NULL) {
        cout << " " << p->data;
        p = p->next;
    }
}

int main() {
    List s;
    Init(s);
    nhap(s);
    xuat(s);
    int x;
    int lc;
    do {
        cout << "\n_ _ _CHUONG TRINH STACK_ _ _";
        cout << endl;
        cout << " 1.Push Stack"
                << "\n 2.Pop Stack"
                << "\n 3.Tim phan tu"
                << "\n 4.Thoat";
        cout << "\nNhap thong tin can kiem tra: ";

        cin>>lc;
        switch (lc) {
            case 1: cout << "Nhap phan tu can Push: ";
                cin>>x;
                push(s, x);
                break;
            case 2: cout << "Pop phan tu trong Stack ";
                pop(s);
                cout << "\n";
                break;
            case 3: cout << "Nhap phan tu can tim kiem: ";
                cin>>x;
                if (search_Node(s, x) != NULL) cout << "Tim thay phan tu!\n";
                else cout << "khong tim thay!\n";
                break;
            case 4: break;
            default: cout << "Ban nhap sai ";
        }
        xuat(s);
        cout << "\n";
    } while (lc != 4);
    return 0;
}

Read More

Đếm số lần lặp

Cho trước n số nguyên không âm a1, a2, …, an. Mỗi lần lặp, bạn thay đổi dãy này thành một dãy mới theo cách: phần tử thứ k trong dãy mới bằng trị tuyệt đối của ak –  ak+1. Phần tử cuối cùng sẽ là an – a1. Quá trình lặp sẽ dừng lại khi được một dãy bằng nhau.

Ví dụ với n=4 và bắt đầu với dãy 0  2  5  11 ta sẽ có các lần lặp là:

2  3  6  11

1  3  5  9

2  2  4  8

0  2  4  6

2  2  2  6

0  0  4  4

0  4  0  4

4  4  4  4

Như vậy trong ví dụ này ta sẽ có 8 lần lặp. Hãy viết chương trình các định số lần lặp của một dãy ban đầu

Input

Gồm nhiều bộ test, mỗi bộ test gồm 2 dòng:

• Dòng 1 ghi số n (2<=n<=20)
• Dòng 2 ghi n số của dãy ban đầu

Input kết thúc khi n=0

Output

Với mỗi bộ test ghi trên một dòng là số lần lặp theo mẫu dưới đây. Nếu dãy không bằng nhau được sau 1000 lần lặp thì ghi ra dòng “not attained”

#include <iostream>
#include<stdio.h>
using namespace std;

// khai bao ham thuc hien lap
int x1(int n){
    int i, j;
    bool ok;
    long *a=new long[n+5];
    for(i=1; i<=n; i++) cin>>a[i];
    for(j=1; j<=1001; j++){
        ok=true;
        a[n+1] = a[1];
        for(i=1;i<=n;i++){
            a[i] = a[i+1]-a[i];
            if(a[i]<0) a[i] = -a[i];
            if(a[i]!=0) ok = false;
        }
        if(ok) return j-1;
    }
    return 1001;
}
int main()
{
    int T=0;
    int A[30005];
    int n;
    do{
        cout<<"Nhap gia tri cua n: ";
        cin>>n;
        if(n==0) break;
        T++;
        A[T] = x1(n);
    }while(1);
    for(int i=1;i<=T;i++){
        if(A[i]==1001) cout<<"Case "<<i<<" not attained"<<endl;
        else cout<<"Case "<<i<<": "<<A[i]<<" iterations "<<endl;
    }
    return 0;
}

Read More

Binary Search Tree

#include <iostream>
#include<cctype>
#include <stdlib.h>
#include <conio.h>

using namespace std;

struct node
{
 int element;
 node *left;
 node *right;
 int height;
};
typedef struct node *nodeptr;
class bstree
{
 public:
  void insert(int,nodeptr &);
  void del(int, nodeptr &);
  int deletemin(nodeptr &);
  void find(int,nodeptr &);
  nodeptr findmin(nodeptr);
  nodeptr findmax(nodeptr);
  void makeempty(nodeptr &);
  void copy(nodeptr &,nodeptr &);
  nodeptr nodecopy(nodeptr &);
  void preorder(nodeptr);
  void inorder(nodeptr);
  void postorder(nodeptr);
  int bsheight(nodeptr);
  nodeptr srl(nodeptr &);
  nodeptr drl(nodeptr &);
  nodeptr srr(nodeptr &);
  nodeptr drr(nodeptr &);
  int max(int,int);
  int nonodes(nodeptr);
};
// Inserting a node
void bstree::insert(int x,nodeptr &p)
{
 if (p == NULL)
 {
  p = new node;
  p->element = x;
  p->left=NULL;
  p->right = NULL;
  p->height=0;
  if (p==NULL)
  {
   cout<<"Out of Space\n"<<endl;
  }
 }
 else
 {
  if (x<p->element)
  {
   insert(x,p->left);
   if ((bsheight(p->left) - bsheight(p->right))==2)
   {
    if (x < p->left->element)
    {
     p=srl(p);
    }
    else
    {
     p = drl(p);
    }
   }
  }
  else if (x>p->element)
  {
   insert(x,p->right);
   if ((bsheight(p->right) - bsheight(p->left))==2)
   {
    if (x > p->right->element)
    {
     p=srr(p);
    }
    else
    {
     p = drr(p);
    }
   }
  }
  else
  {
   cout<<"Element Exists\n"<<endl;
  }
}
int m,n,d;
m=bsheight(p->left);
n=bsheight(p->right);
d=max(m,n);
p->height = d + 1;
}
// Finding the Smallest
nodeptr bstree::findmin(nodeptr p)
{
 if (p==NULL)
 {
  cout<<"The tree is empty\n"<<endl;
  return p;
 }
 else
 {
  while(p->left !=NULL)
  {
   p=p->left;
   //return p;
  }
  return p;
 }
}
// Finding the Largest node
nodeptr bstree::findmax(nodeptr p)
{
 if (p==NULL)
 {
  cout<<"The tree is empty\n"<<endl;
  return p;
 }
 else
 {
  while(p->right !=NULL)
  {
   p=p->right;
   //return p;
  }
  return p;
 }
}
// Finding an element
void bstree::find(int x,nodeptr &p)
{
 if (p==NULL)
 {
  cout<<"Sorry! element not found\n"<<endl;
 }
 else
 {
  if (x < p->element)
  {
   find(x,p->left);
  }
  else
  {
   if (x>p->element)
   {
    find(x,p->right);
   }
   else
   {
    cout<<"Element found!\n"<<endl;
   }
  }
 }
}
// Copy a tree
void bstree::copy(nodeptr &p,nodeptr &p1)
{
 makeempty(p1);
 p1 = nodecopy(p);
}
// Make a tree empty
void bstree::makeempty(nodeptr &p)
{
 nodeptr d;
 if (p != NULL)
 {
  makeempty(p->left);
  makeempty(p->right);
  d=p;
  free(d);
  p=NULL;
 }
}
// Copy the nodes
nodeptr bstree::nodecopy(nodeptr &p)
{
 nodeptr temp;
 if (p==NULL)
 {
  return p;
 }
 else
 {
  temp = new node;
  temp->element = p->element;
  temp->left = nodecopy(p->left);
  temp->right = nodecopy(p->right);
  return temp;
 }
}

// Deleting a node
void bstree::del(int x,nodeptr &p)
{
 nodeptr d;
 if (p==NULL)
 {
  cout<<"Sorry! element not found\n"<<endl;
 }
 else if ( x < p->element)
 {
  del(x,p->left);
 }
 else if (x > p->element)
 {
  del(x,p->right);
 }
 else if ((p->left == NULL) && (p->right == NULL))
 {
  d=p;
  free(d);
  p=NULL;
  cout<<"Element deleted successfully\n"<<endl;
 }
 else if (p->left == NULL)
 {
  d=p;
  free(d);
  p=p->right;
  cout<<"Element deleted successfully\n"<<endl;
 }
 else if (p->right == NULL)
 {
  d=p;
  p=p->left;
  free(d);
  cout<<"Element deleted successfully\n"<<endl;
 }
 else
 {
  p->element = deletemin(p->right);
 }
}

int bstree::deletemin(nodeptr &p)
{
 int c;
 cout<<"inside deltemin\n"<<endl;
 if (p->left == NULL)
 {
  c=p->element;
  p=p->right;
  return c;
 }
 else
 {
  c=deletemin(p->left);
  return c;
 }
}
void bstree::preorder(nodeptr p)
{
 if (p!=NULL)
 {
  cout<<p->element<<"\t";
  preorder(p->left);
  preorder(p->right);
 }
}

// Inorder Printing
void bstree::inorder(nodeptr p)
{
 if (p!=NULL)
 {
  inorder(p->left);
  cout<<p->element<<"\t";
  inorder(p->right);
 }
}

// PostOrder Printing
void bstree::postorder(nodeptr p)
{
 if (p!=NULL)
 {
  postorder(p->left);
  postorder(p->right);
  cout<<p->element<<"\t";
 }
}

int bstree::max(int value1, int value2)
{
 return ((value1 > value2) ? value1 : value2);
}
int bstree::bsheight(nodeptr p)
{
 int t;
 if (p == NULL)
 {
  return -1;
 }
 else
 {
  t = p->height;
  return t;
 }
}

nodeptr bstree:: srl(nodeptr &p1)
{
 nodeptr p2;
 p2 = p1->left;
 p1->left = p2->right;
 p2->right = p1;
 p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
 p2->height = max(bsheight(p2->left),p1->height) + 1;
 return p2;
}
nodeptr bstree:: srr(nodeptr &p1)
{
 nodeptr p2;
 p2 = p1->right;
 p1->right = p2->left;
 p2->left = p1;
 p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
 p2->height = max(p1->height,bsheight(p2->right)) + 1;
 return p2;
}
nodeptr bstree:: drl(nodeptr &p1)
{
 p1->left=srr(p1->left);
 return srl(p1);
}
nodeptr bstree::drr(nodeptr &p1)
{
 p1->right = srl(p1->right);
 return srr(p1);
}

int bstree::nonodes(nodeptr p)
{
 int count=0;
 if (p!=NULL)
 {
  nonodes(p->left);
  nonodes(p->right);
  count++;
 }
 return count;
}

int main()
{
 //clrscr();
 nodeptr root,root1,min,max;//,flag;
 int a,choice,findele,delele;
 char ch='y';
 bstree bst;

 //system("clear");
 root = NULL;
 root1=NULL;
 cout<<"\n\t\t\t\tWELCOME TO AVL TREE"<<endl;
 cout<<"\t\t\t\t:::::::::::::::::::\n"<<endl;

 do
 {
  cout<<"\t\t::::::::::::::::::::::::::::::::::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 1 to insert a new node::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 2 to find the minimum value:::::::::::"<<endl;
  cout<<"\t\t::::Enter 3 to find the max value:::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 4 to search a value:::::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 5 to delete a value:::::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 6 to display Preorder:::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 7 to display Inorder::::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 8 to display Postorder::::::::::::::::"<<endl;
  cout<<"\t\t::::Enter 9 to display the height of the tree:::"<<endl;
  cout<<"\t\t::::Enter 0 to exit:::::::::::::::::::::::::::::"<<endl;
  cout<<"\t\t::::::::::::::::::::::::::::::::::::::::::::::::\n"<<endl;

  cout<<"\nEnter the choice: ";
  cin>>choice;

  switch(choice)
  {
   case 1:
    cout<<"\n\t\tADDING NEW NODE"<<endl;
    cout<<"\t\t:::::::::::::\n"<<endl;
    cout<<"Enter a new value: ";
    cin>>a;
    bst.insert(a,root);
    cout<<"\nThe new value have been added to your tree successfully\n"<<endl;
    break;
   case 2:
    if (root !=NULL)
    {
     min=bst.findmin(root);
     cout<<"\nThe minimum element in the tree is: "<<min->element<<endl;
    }
    break;
   case 3:
    if (root !=NULL)
    {
     max=bst.findmax(root);
     cout<<"\nThe maximum element in the tree is: "<<max->element<<endl;
    }
    break;
   case 4:
    cout<<"\nEnter node to search: ";
    cin>>findele;
    if (root != NULL)
    {
     bst.find(findele,root);
    }
    break;
   case 5:
    cout<<"\nEnter node to delete: ";
    cin>>delele;
    bst.del(delele,root);
    bst.inorder(root);
    cout<<endl;
    break;
   case 6:
    cout<<"\n\t\tPRE-ORDER TRAVERSAL"<<endl;
    bst.preorder(root);
    cout<<endl;
    break;
   case 7:
    cout<<"\n\t\tIN-ORDER TRAVERSAL"<<endl;
    bst.inorder(root);
    cout<<endl;
    break;
   case 8:
    cout<<"\n\t\tPOST ORDER TRAVERSAL"<<endl;
    bst.postorder(root);
    cout<<endl;
    break;
   case 9:
    cout<<"\n\t\tHEIGHT\n"<<endl;
    cout<<"The height of the tree is: "<<bst.bsheight(root)<<endl;

    break;
   case 0:
    cout<<"\n\tThank your for using AVL tree program\n"<<endl;
    break;
   default:
    cout<<"Sorry! wrong input\n"<<endl;
    break;
  }
  //system("pause");
  //system("cls");
 }while(choice != 0);
 return 0;
}

Read More

MergeSort

#include <iostream>
using namespace std;
class sort1{
public: void mergelist(int Data[], int first, int mid, int last);
        void mergeSort(int A[], int ledt, int right);
};

// trien khai cac ham trong class
void sort1::mergelist(int Data[], int first, int mid, int last){
    int tmp[100];
    int first1 = first;
    int last1 = mid;
    int first2 = mid+1;
    int last2 = last;
    int index = first1;
    while((first1<=last1)&&(first2<=last2)){
        if(Data[first1]<Data[first2]){
            tmp[index] = Data[first1];
            first1++;
        }
        else{
            tmp[index] = Data[first2];
            first2++;
        }
        ++index;
    }
    while(first1<=last1){
        tmp[index] = Data[first1]; // sao not cac phan tu con lai vao mang nho
        ++index;
        ++first1;
    }
    while(first2<=last2){
        tmp[index] = Data[first2]; // sao not cac phan tu con lai vao mang nho
        ++index;
        ++first2;
    }
    for(index = first;index<=last; index++){
        Data[index] = tmp[index];
    }
}

// goi ham mergeSort
void sort1::mergeSort(int A[], int left, int right){
    if(left>=right) return;
    else{
        int mid=(left+right)/2;
        mergeSort(A, left, mid);
        mergeSort(A, mid+1, right);
        mergelist(A, left, mid, right);
    }
}
int main()
{
    sort1 srt;
    int A[100];
    int n;
    cout<<"Nhap so phan tu cua mang: "<<endl;
    cin>>n;
    for(int i=1; i<=n; i++){
        cout<<"Phan tu thu "<<i<<" la: ";
        cin>>A[i];
    }
    srt.mergeSort(A,1,n);
    for(int i=1; i<=n; i++){
        cout<<" "<<A[i];
    }
    return 0;
}

Read More

Code tìm kiếm và xóa phần tử trên cây nhị phân

#include <iostream>
#include <stdlib.h>
using namespace std;
// khai bao cau truc
struct node{
    int Data;
    struct node *pLeft;
    struct node *pRight;
};
typedef struct node NODE;
typedef NODE *Tree;

// khoi tao cay
void Init(Tree &t){
    t=NULL;
}

// Tao Node tren cay
NODE *makeNode(int x){
    NODE *p = new NODE;
    if(p==NULL) return NULL;
    else{
        p->Data = x;
        p->pLeft = p->pRight = NULL;
    }
    return p;
}

// Insert Node vao cay
void insertNode(Tree &t, int x){

    if(t==NULL){ // cay rong => x la Node goc
        NODE *p = new NODE;
        p=makeNode(x);
        t=p;
    }
    else {
        if(t->Data > x){
            insertNode(t->pLeft,x);
        }
        else if(t->Data < x){
         insertNode(t->pRight,x);
        }
    }
}

// Nhap du lieu cho cay
void inputTree(Tree &t){
    Init(t);// phai khoi tao cay truoc thi moi co the nhap du lieu cho cay
    cout<<"Nhap du lieu cho cay\n";
    cout<<"An phim 0 de det thuc \n";
    int x;
    do{
        //int x;
        cout<<"Nhap Node: ";
        cin>>x;
        if(x!=0) {
            insertNode(t,x);
        }
       // else break;
    }while(x!=0);
}

// Xuat su lieu
void output(Tree &t){
    if(t!=NULL){
        cout<<t->Data<<" ";
        output(t->pLeft);
        output(t->pRight);
    }
}

// tim phan tu trong cay
NODE *searchTree(Tree &t, int x){
    if(t==NULL) return NULL;
    else if(t->Data<x) searchTree(t->pRight,x);
    else if(t->Data>x) searchTree(t->pLeft,x);
    else return t;
}

// Tim phan tu q bi xoa, cho phan tu p len thay the
void thaythe(Tree &q, Tree &p){
    // tim phan tu trai nhat cua cay ben phai
    //if(t==NULL) return;
    if(p->pLeft!=NULL){
        thaythe(q,p->pLeft);
    }
    else {
        q->Data = p->Data;
        q=p;
        p=p->pRight;
    }

}

// xoa phan tu
void delTree(Tree &t, int x){
    if(t==NULL) return;
    if(t->Data > x) delTree(t->pLeft,x);
    if(t->Data < x) delTree(t->pRight,x);
    if(t->Data == x) { // khi tim ra phan tu do roi
        // xoa Node la hoac Node co 1 phan tu
        NODE *q = t;// xoa phan tu bang con tro
        if(t->pLeft==NULL) { // neu ma ben traiphan tu do bang NULL
            t=t->pRight; // cho t tro toi t->pRight
        }
        else if(t->pRight==NULL){
            t=t->pLeft;
        }
        // xoa Node co 2 phan tu Trai va Phai
       else thaythe(q,t->pRight);
        delete q;
    }
}
int main()
{
    Tree t;
    int k,x;
    inputTree(t);
    output(t);

    cout<<endl<<"Nhap so ban muon tim:";
    cin>>x;
    NODE *p = searchTree(t,x);
    if(p==NULL) cout<<"Khong tim thay";
    else cout<<"Co tim thay";

    cout<<endl<<"Nhap phan tu can xoa:";
    cin>>k;
    delTree(t,k);
    output(t);
    return 0;
}

Read More

3 thuật toán sắp xếp InsertSort, selectSort, bublleSort

======================================================================
Name        : sort.cpp
Author      : CTK
Version     :
Copyright   : Your copyright notice
Description : Hello World in C++, Ansi-style
=======================================================================

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
using namespace std;
// thuat toan insertSort
void insertSort(int A[], int n) { // khai bao ham insertSort
for (int i = 0; i < n; i++) { //cho bien i lam bien chay
int j = i - 1; // gan gia tri i cho j-1, j la bien lui ve
int tmp = A[i]; // gan gia tri i cho tmp
while (tmp < A[j] && j >= 0) {
A[j + 1] = A[j];
j--;
}
A[j + 1] = tmp;
}
}
// doi cho
void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}
//thuat toan selectSort
void selectSort(int A[], int n) {
for (int i = 0; i < n - 1; i++) {
int count = i;
for (int j = i + 1; j < n; j++) {
if (A[count] > A[j]) {
swap(A[count], A[j]);
}

}
if (i != count) {
swap(A[count], A[i]);
}
}
}
// thuat toan sap xep bubble sort
void bubbleSort(int A[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (A[i] > A[j])
swap(A[i], A[j]);
}
}
}
int findMax(int A[], int n) {
int max = A[0], i;
for (int i = 0; i < n; i++) {
if (A[i] > max) {
max = A[i];
}
}
return max;
}
int findMin(int A[], int n) {
int min = A[0], i;
for (int i = 0; i < n; i++) {
if (A[i] < min) {
min = A[i];
}
}
return min;
}

// tinh gia tri trung binh trong mang
float trungBinh(int A[], int n) {
float s = 0;
float avg = 0;
for (int i = 0; i < n; i++) {
s += A[i];
}
avg = (float) (s / n);
return avg;
}

// tim do lech giua hai gia tri trong mang
void chenhLech(int A[], int n) {
int i, j;
cout << "nhap phan tu thu nhat:";
cin >> i;
cout << "nhap phan tu thu hai:";
cin >> j;
cout<<"do chenh lech giua hai phan tu la:";
if(A[i-1]>=A[j-1])cout<<(A[i-1]-A[j-1]);
else cout<<(A[j-1]-A[i-1]);
}
void check(int A[], int n){
for(int i=0; i<n;i++){
cout<<"do lech trung binh so thu "<<i+1<<" la: ";
if((float)A[i]>=trungBinh(A,n)) cout<<((float)A[i]-trungBinh(A,n));
else cout<<(trungBinh(A,n)-(float)A[i]);
cout<<endl;
}
}
// tim kiem mot phan tu trong mang
void search(int A[], int n, int x){
for(int i=0; i<n; i++){
if(A[i]==x) cout<<i<<"\t";
}
}
int main() {
int n;
int A[10];
cout << "nhap gia tri n:";
cin >> n;
for (int i = 0; i < n; i++) {
cout << "so thu " << i + 1 << " la: ";
cin >> A[i];
}
// 3 thuat toan sap xep
insertSort(A, n);
//selectSort(A,n);
//bubbleSort(A, n);

// phan tu lon nhat va vi tri
for (int i = 0; i < n; i++)
cout << "\t" << A[i];
cout << "gia tri lon nhat la: ";
cout << findMax(A, n);
cout << endl << "vi tri phan tu lon nhat trong mang la: ";
for (int i = 0; i < n; i++) {
if (A[i] == findMax(A, n))
cout << i;
}
// phan tu nho nhat va vi tri
cout << endl << "gia tri nho nhat la: ";
cout << findMin(A, n);
cout << endl << "vi tri phan tu nho nhat trong mang la: ";
for (int i = 0; i < n; i++) {
if (A[i] == findMin(A, n))
cout << i;
}
// gia tri trung binh
cout << endl << "gia tri trung binh cac phan tu trong mang la:";
cout << trungBinh(A, n);
cout<<endl;
//chenhLech(A,n);
check(A,n);
cout<<"nhap so ban can tim";
int k;
cin>>k;
cout<<"vi tri ban can tim la :";
search(A,n,k);
}

Read More

Code Danh Sách Liên Kết

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   main.cpp
 * Author: KHOA
 *
 * Created on August 26, 2016, 9:10 AM
 */

#include <iostream>
#include<stdio.h>
using namespace std;

struct Node {
    int data;
    Node *next; // chua dia chi node ke tiep ma no tro toi
};

struct List {
    Node *head; // phan tu dau danh sach
    Node *tail; // phan tu cuoi danh sach
};

// khoi tao

void Init(List &l) {
    l.head = l.tail = NULL; // gan cac phan tu dau va cuoi deu bang NULL
}

// khoi tao Node

Node *creatNode(int x) {
    Node *p = new Node;
    if (p == NULL) return NULL;
    else {
        p->data = x; // gan gia tri data cua p bang x
        p->next = NULL; // phan tu ke tiep bang NULL
    }
    return p; // tra ve phan tu p
}

// kiem tra danh sach rong

bool isEmpty(List &l) {
    // neu phan tu dau danh sach la NULL thi danh sach rong
    if (l.head == NULL) return true;
        // con khong thi danh sach khong trong
    else return false;
}

// chen vao dau danh sach;

void addHead(List &l, int x) {
    Node *p = creatNode(x); // khoi tao Node p co gia tri bang phan tu x
    if (isEmpty(l)) { // kiem tra xem danh sach co rong khong
        l.head = l.tail = p; // neu rong thi chen luon phan tu p vao danh sach
    } else { // neu khong thi
        p->next = l.head; // gan phan tu ke tiep cua p la phan tu dau
        l.head = p; // cap nhat lai phan tu dau
    }
}

// them vao cuoi danh sach

void addTail(List &l, int x) {
    // neu danh sach rong thi giong nhu la chen vao dau
    Node *p = creatNode(x);
    if (isEmpty(l)) l.head = l.tail = p;
    else {
        l.tail->next = p; //ta se gan phan tu cuoi ke tiep la phan tu p
        l.tail = p; //cap nhat lai phan tu cuoi la p
    }
}

// tim kiem tren danh sach

Node *search_Node(List &l, int k) {
    Node *p = l.head; // gan phan tu p la phan tu dau danh sach
    while (p != NULL) { // neu p khac NULL thi tim
        if (p->data == k) return p; // khi tim ra thi se tra ve phan tu p
        else p = p->next; // chua tim ra thi tiep tuc tim
    }
    return NULL; // khong tim thay phan tu doi trong danh sach
}

// chen vao giua cua danh sach
// chen phan tu x dang sau phan tu k

void addMid_value(List &l, int x, int k) {
    Node *p = search_Node(l, k); // gan phan tu k vao Node p can xet
    if (p != NULL) { // neu tim duoc gia tri cua k trong danh sach thi ta lam nhu sau
        Node *q = p->next;// giả sử phần tử kế tiếp của p la q
        Node *r = creatNode(x);// tạo ra phần tử r chứa giá trị của x cần chèn vào
        r->next = q; // gán phần tử kế tiếp của r là phần tử q
        p->next = r; // gán phần tử kế tiếp của p là q
    }
    // neu khong tim duoc gia tri k trong danh sach thi dua ra thong bao
    else cout << "\nKhong tim thay node co data = " << k;
}

// dem so phan tu co trong danh sach lien ket

int count_Node(List &l) {
    int dem = 0;
    for (Node *p = l.head; p != NULL; p = p->next) {
        dem++; // tang bien dem len khi p->next
    }
    return dem; // tra về giá trị của biến đếm
}
// chen phan tu x vao mot vi tri bat ky trong danh sach lien ket

void addMid_index(List &l, int x, int k) {
    // nếu giá trị nhập vào <=1 thì chèn vào đầu danh sách
    if (k <= 1 || isEmpty(l)) addHead(l, x);

    // Nếu giá trị nhập vào lớn hơn tổng số phần tử thì chèn vào cuối danh sách
    else if (k >= count_Node(l)) addTail(l, x);

    // Nếu không thì
    else {
        int dem = 2;
        Node *p = creatNode(x);
        // for(Node *r = l.head; r!=NULL; r=r->next){

        Node *r = l.head;
        while (r != NULL) {
            if (dem == k) {
                // bước này thực hiện như chèn phần tử vào danh sách
                Node *q = r->next;
                p->next = q;
                r->next = p;
                // Hoặc cách 2 của phần này là code 1dòng dưới
                //addMid_value(l,x,dem-1);
                break;
            } else dem++;
            r = r->next;// nếu chưa tìm ra vị trí cần chèn thì tăng r trong danh sách
        }
    }

    // Hoặc cách 2 là phần command dưới
    /*if(isEmpty(l) || k<= 1 ) addHead(l,x);
        else if(k>= n) addTail(l,x);
        else{
                Node *p = creatNode(x);
                Node *q = new Node, *w = new Node;
                Node *r = l.head;
                int dem = 0;
                while(r!=NULL){
                        dem++;
                        q = r;
                        if(dem == k ) break;
                        else r = r->next;
                }
                w = l.head;
                while(w->next!= q) w = w->next;
                w->next = p;
                p->next = r;
        }*/

}

// xoa mot phan tu cua danh sach lien ket
// xoa phan tu dau tien

void delHead(List &l) {
    Node *p = l.head;
    if (p != NULL) {
        l.head = l.head->next; // gan phan tu dau tien thanh phan tu ke tiep
    }
    delete p; // xoa phan tu dau tien
}

// xoa Node cuoi cung trong danh sach lien ket don

void delTail(List &l) {
    // can tim ra phan tu cuoi cung
    Node *p = l.head;
    while (p->next != l.tail) p = p->next; // tiep tuc tim neu phan tu do chua la phan tu cuoi cung
    // da tim ra phan tu p la phan tu truoc phan tu cuoi cung
    Node *q = p->next; // luc nay q la Node cuoi cung cua danh sach
    l.tail = p; // sai o cho nay
    p->next = NULL;
    delete q;
}

// xoa tai mot vi tri bat ky co trong danh sach

void delNode_index(List &l, int k) {
    // xoa Node tai vi tri k trong danh sach lien ket
    Node *p = l.head;
    Node *q = search_Node(l, k); // tim kiem vi tri cua Node can xoa
    while (p->next != q) {
        p = p->next;
    }
    // da tim ra vi tri cua Node truoc Node can xoa
    Node *r = q->next; // r la Node sau Node can xoa
    p->next = r; // gán phần tử r cho phần tử kế tiếp của p
    delete q; // xóa phần tử q
}

// xóa phần tử có giá trị x trong danh sách
void delNode_value(List &l, int x){
    Node *q = search_Node(l,x);
    if(q!=NULL){
        Node *p = l.head;
        while(p->next!=q){
            p=p->next;
        }
        // tim ra vi tri cua p truoc phan tu can xoa
        Node *r = q->next;
        p->next = r;
        delete q;
    }
    else{
        cout<<"Khong ton tai phan tu "<<x<<" trong danh sach lien ket";
    }
}


// nhap phan tu cho danh sach lien ket
void nhap(List &l) {
    int n;
    Init(l); // khởi tạo danh sách
    cout << "Nhap so phan tu cho danh sach lien ket: ";
    cin>>n;
    for (int i = 1; i <= n; i++) addTail(l, i); // chèn vào cuối danh sách
}

// Ham xuat cac phan tu

void xuat(List &l) {
    for (Node *p = l.head; p != NULL; p = p->next) {
        cout << p->data << " ";
    }
}

int main() {
    List l;
    Init(l);
    nhap(l);
    xuat(l);
    int k, x, lc;
    do {
        cout << "\n______MENU______\n1_Chen dau.\n2_chen cuoi."
                << "\n3_Chen sau vi tri node data = k.\n4_Chen vao vi tri bat ki."
                << "\n5_Xuat Thong tin List.\n6_Xoa phan tu dau List."
                << "\n7_Xoa phan tu o cuoi List.\n8_Xoa node o vi tri k."
                <<"\n9_Xoa phan tu co gia tri = k trong danh sach."
                << "\n0_Thoat.\n_Ban chon ? ";
        cin>> lc;
        switch (lc) {
            case 0: break;
            case 1: cout << "\nNhap x: ";
                cin>> x;
                addHead(l, x);
                break;
            case 2: cout << "\nNhap x: ";
                cin>> x;
                addTail(l, x);
                break;
            case 3: cout << "\nNhap x, k: ";
                cin >> x >> k;
                addMid_value(l, x, k);
                break;
            case 4: cout << "\nNhap x, vi tri k: ";
                cin >> x >> k;
                addMid_index(l, x, k);
                break;
                //case 5: xuat(l); break;
            case 6: delHead(l);
                break;
            case 7: delTail(l);
                break;
            case 8: cout << "\nNhap vi tri k: ";
                cin>> k;
                delNode_index(l, k);
                break;
            case 9: cout<<"\nNhap phan tu can xoa:";
            cin>>k;
            delNode_value(l,k);
            break;
        }
        xuat(l);
    } while (lc != 0);
    return 0;
}

Read More