欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态单向链表的C++实现

程序员文章站 2024-03-06 22:09:26
...

一.概念

链表是一种特殊的数组,它的每个元素称为节点,每个节点包括两个部分:

  • 数据域:存放数据,此部分与数组相同
  • 指针域:存放了下一个节点的地址(单向链表)、存放上一个和下一个节点的地址(双向链表)

其结构如下图所示

动态单向链表的C++实现

链表比数组多了指针域,因为链表结构是通过上一个节点的指针域去找下一个数据,比如有一个链表ABCD四个节点,其中A节点是链表的第一个节点,如果要访问D节点里边的数据。操作如下:

  1. 先通过A节点的指针域找到B节点
  2. 再通过B节点的指针域找到C节点
  3. 再通过C节点的指针域找到D节点
  4. 获取D节点数据域的数据

当遍历链表中的数据时,这种方法相比数组一般更加耗时,但是他的好处在于当插入和删除数据时非常方便,数组的插入和删除需要调整之后的每个数据,而链表则只需要调整结点的指针即可,如下图所示,删除同理

动态单向链表的C++实现

二.头指针和头结点

      头指针用来唯一确定单链表的身份,头指针指向链表的第一个结点,若第一个结点不存放数据,则为头结点。链表可以没有头结点,但必须有头指针,没有头指针的话链表也就不存在了。头结点的数据域可以不存放任何信息,也可以存放链表的长度等信息。

动态单向链表的C++实现

总结:

     头指针:

  • 在线性表的链式存储结构中,头指针是指链表指向第一个结点的指针,若链表有头结点,则头指针就是指向链表头结点的指针。
  • 头指针具有标识作用,常用头指针冠以链表的名字。
  • 无论链表是否为空,头指针均不为空。头指针是链表的必要元素。

头结点:

  • 头结点是为了操作的统一与方便而设立的,放在第一个元素结点之前,其数据域一般无意义(有些情况下也可存放链表的长度等等)。
  • 有了头结点后,对在第一个元素结点前插入结点和删除第一个结点,其操作与对其它结点的操作统一了。即操作任何位置时代码相同,更加方便。
  • 头结点不是链表所必需的。

三.实践

声明: LinkList.h

//
// Created by 开机烫手 on 2018/3/11.
//
#ifndef LINEARLIST_LINKLIST_H
#define LINEARLIST_LINKLIST_H

namespace xq {

    typedef struct node {
        int data;
        struct node *next;
    } NODE;

    class LinkList {
    private:
        NODE* head;
        int len;
        LinkList(const LinkList&);
    public:
        LinkList();

        ~LinkList();

        bool clearList();

        bool isEmpty();

        int length();

        void getElem(int, int *);

        int locateElem(int);

        bool insert(int, int);

        bool delete_(int,int*);

        void sort();

        void print();

        bool push_back(int);
    };

}
#endif //LINEARLIST_LINKLIST_H

类实现:LinkList.cpp

//
// Created by 开机烫手 on 2018/3/11.
//
#include <iostream>
#include "LinkList.h"

using namespace xq;
using namespace std;

LinkList::LinkList() {
    head = new NODE;    // 创建头结点
    head->next = nullptr;
    len = 0;
}

LinkList::~LinkList() {
    NODE *p = head->next;
    NODE *q;
    while (p) {
        q = p->next;
        delete p;
        p = q;
    }
}

bool LinkList::clearList() {
    NODE *p = head->next;
    NODE *q;
    while (p) {
        q = p->next;
        delete p;
        p = q;
    }
    len = 0;
    head->next = nullptr;

    return true;
}

bool LinkList::isEmpty() {
    return len == 0;
}

int LinkList::length() {
    return len;
}

void LinkList::getElem(int i, int *e) {

    if (i <= 0 || i > len || len == 0) {
        *e = -999;
        return;
    }

    int j = 1;
    NODE *p = head->next;
    while (j < i && p) {
        p = p->next;
        j++;
    }

    *e = p->data;
}

int LinkList::locateElem(int e) {

    int i = 1;

    NODE *p = head->next;
    while (p) {
        if (p->data == e)
            return i;
        p = p->next;
        i++;
    }

    return -1;
}

bool LinkList::insert(int i, int e) {

    if (i <= 0 || i-1 > len)
        return false;

    int j = 1;
    NODE *p = head;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    NODE *s = new NODE;
    s->data = e;
    s->next = p->next;
    p->next = s;
    len++;

    return true;
}

void LinkList::print() {
    if (len == 0) {
        cout << "list is empty!" << endl;
        return;
    }
    NODE *p = head->next;
    while (p) {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
}

bool LinkList::delete_(int i, int *e) {
    if (i <= 0 || i > len)
        return false;

    NODE *q = head;
    int j = 1;
    NODE *p = head->next;
    while (j < i) {
        q = p;
        p = p->next;
        j++;
    }

    *e = p->data;

    q->next = p->next;
    len--;
    delete p;
    return true;
}

bool LinkList::push_back(int e) {

    NODE *p = head->next;
    while (p->next) {
        p = p->next;
    }
    NODE *s = new NODE;
    s->data = e;
    p->next = s;
    s->next = nullptr;
    len++;

    return true;
}

void LinkList::sort() {
    if (len <= 1)
        return;

    int temp;
    NODE *p, *q;
    for (int i = 0; i < len - 1; i++) {
        p = head->next;
        q = head->next->next;
        for (int j = 0; j < len - 1 - i; j++) {
            if ((p->data) > (q->data)) {
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
            p = p->next;
            q = q->next;
        }
    }
}

代码测试:main.cpp

#include <iostream>
#include "LinkList.h"

using namespace std;
using namespace xq;

int main() {

    cout << "----------List test programe!---------- " << endl;
    LinkList list1;
    cout << "is empty " << list1.isEmpty() << endl;
    list1.insert(1, 1);
    cout << "is empty " << list1.isEmpty() << endl;
    list1.clearList();
    cout << "is empty " << list1.isEmpty() << endl;

    list1.insert(1, 1);
    list1.insert(2, 2);
    list1.insert(3, 3);
    list1.insert(4, 5);
    list1.insert(5, 6);
    list1.print();
    list1.insert(4, 4);
    list1.print();

    int c;
    list1.delete_(5, &c);
    list1.print();
    int location = list1.locateElem(3);
    cout << "location is " << location << endl;
    int num2;
    list1.getElem(4, &num2);
    cout << "num2 = " << num2 << endl;
    list1.push_back(10);
    list1.push_back(5);
    list1.push_back(7);
    list1.push_back(2);
    list1.print();
    list1.sort();
    cout << "sort " ;
    list1.print();

    return 0;
}

程序输出为:

----------List test programe!----------
is empty 1
is empty 0
is empty 1
1 2 3 5 6
1 2 3 4 5 6
1 2 3 4 6
location is 3
num2 = 4
1 2 3 4 6 10 5 7 2
sort 1 2 2 3 4 5 6 7 10