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;
}