Danh sách liên kết đơn trong C++

| Danh sách liên kết đơn trong C++

Khai báo struct NODE và LIST

// khai báo node

typedef struct node

{

    int data;

    struct node* pNext;

}NODE;

// khai báo danh sách các node

typedef struct list

{

    NODE* pHead;

    NODE* pTail;

}LIST;

Prototype

void init(LIST&);

NODE* getNODE(int);

void addHead(LIST&, NODE*);

void addTail(LIST&, NODE*);

void Input(LIST&);

void Output(LIST);

int Sum(LIST);

Hàm khởi tạo danh sách liên kết

void init(LIST& l)

{

    l.pHead = l.pTail = NULL;

    //l.pTail = NULL;

}

Hàm tạo ra một node

//tạo Node trong danh sách liên kết đơn các số nguyên

NODE* getNODE(int x)

{

    NODE* p = new NODE;

   // p = new NODE;

    if (p == NULL)

        return NULL;

    p->data = x;

    p->pNext = NULL;

    return p;

}

Thêm vào đầu danh sách liên kết đơn

//thêm vào đầu danh sách lk đơn số nguyên

void addHead(LIST& l, NODE* p)

{

    if (l.pHead == NULL)

    {

        l.pHead = p;

        l.pTail = l.pHead;

    }

    else

    {

        p->pNext = l.pHead;

        l.pHead = p;

    }

}

Thêm vào cuối danh sách liên kết đơn

//thêm vào cuối danh sách lk đơn số nguyên

void addTail(LIST& l, NODE* p)

{

    if (l.pHead == NULL)

    {

        l.pHead = p;

        l.pTail = l.pHead;

    }

    else

    {

        l.pTail->pNext = p;

        l.pTail = p;

    }

}

Hàm nhập

//hàm nhập dữ liệu danh sách liên kết đơn các số nguyên

void Input(LIST& l)

{

    int n;

    cout << "\nNhap vao so luong node: ";

    cin >> n;

    init(l);

   

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

    {

        int x;

        cout << "\nNhap gia tri cua node: ";

        cin >> x;

        NODE* p = getNODE(x);

        addHead(l, p);

    }

}

Hàm xuất

// hàm xuất dữ liệu danh sách liên kết đơn các số nguyên

void Output(LIST l)

{

    for (NODE* p = l.pHead; p != NULL; p = p->pNext)

    {

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

    }

}

Tính tổng giá trị các node trong danh sách liên kết đơn (Optional)

int Sum(LIST l)

{

    int sum = 0;

    for (NODE* p = l.pHead; p != NULL; p = p->pNext)

    {

         sum = sum + p->data;

    }

    return sum;

 }

Main.cpp

#include <iostream>

using namespace std;

int main()

{

    LIST l;

    Input(l);

    Output(l);

    int kq = Sum(l);

    cout << "\nTong cac so nguyen trong danh sach lien ket la " << kq << endl;

    system("pause");

    return 0;

}

Tobecontinued~