C++ 单链表(带头结点)

2021年09月15日 阅读数:2
这篇文章主要向大家介绍C++ 单链表(带头结点),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

文章目录

总结概括

  1. 头结点能够没有,头指针必须有。访问整个链表,是用过遍历头指针来进行的。
  2. 这里没有特别的设置一个头指针,由于当指针指向整个链表 L 时,该指针的实现效果就是头指针。
  3. 不带头结点的单链表,即单链表的第一个结点就存储数据,头指针也指向第一个结点;带头结点的单链表,第一个结点是头结点,不存储数据,从头结点的 next 开始存储,头指针能够从头结点的 next 开始遍历。
  4. 对于结点的前插操做,找到对应位置的结点,设新结点为该节点的后继结点,将该结点的 data 后移至新结点的 data,以此来模拟结点的后移,而且时间复杂度为 O(1),我愿称之为“偷天换日”。
  5. 若是采用尾插法建立单链表,能够设置一个尾指针,指向单链表末尾,这样就不用每次都经过遍历找到最后一个结点,但每插入一个都要更新尾指针。这样的时间复杂度为O(1)。
  6. 在 DeleteNode 函数中(删除指定结点),存在一处 bug ,当删除结点为最后一个结点时,因为该结点没有后继结点,该函数会报错,初步认为只能经过 DeleteNextLNode函数(删除p结点的后继结点)来实现删除最后一个结点的操做。
  7. 大多数状况下,单链表的查询、插入、删除的平均时间复杂度都是O(n),由于要遍历头结点开始查找。但若是对指定结点进行插入和删除,则时间复杂度为O(1),由于不须要再经过遍历找到指定的结点。要具体分析。
  8. 若是不带头结点的单链表,则对表头的操做(插入和删除)要特殊处理,例如 List_HeadInsert(头插法建立单链表)、ListInsert(按位序插入)。每次插入后都要更新头指针,而对于带头结点的单链表,它的头指针指向永远是头结点,只须要修改头结点的后继就能够完成插入。

代码实现

#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

// 单链表结点
struct LNode {
    int data;    // 数据域
    LNode *next; // 指针域
};

typedef LNode LNode;     // LNode表示单链表的一个结点
typedef LNode *LinkList; // LinkList表示一个单链表

// 初始化单链表
void InitList(LinkList &L) {
    L = new LNode;
    // L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
}

// 判断单链表是否为空
bool Empty(LinkList &L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}

// 获取单链表长度
int GetLength(LinkList &L) {
    LNode *p = L->next;
    int length = 0;
    while (p != NULL) {
        p = p->next;
        length++;
    }
    return length;
}

// 按位查找:查找第i个结点
LNode *GetElem(LinkList &L, int i) {
    if (i < 0) {
        return NULL; // i值不合法
    }
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

// 按值查找:查找数据域为e的结点
LNode *GetLNode(LinkList &L, int e) {
    LNode *p = L->next;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

// 头插法创建单链表
LinkList List_HeadInsert(LinkList &L) {
    int e;
    cin >> e;
    while (e != 9999) {
        LNode *s = new LNode;
        s->data = e;
        s->next = L->next;
        L->next = s;
        cin >> e;
    }
    return L;
}

// 尾插法创建单链表
LinkList List_TailInsert(LinkList &L) {
    LNode *r = L; // r为尾指针
    int e;
    cin >> e;
    while (e != 9999) {
        LNode *s = new LNode;
        s->next = r->next;
        s->data = e;
        r->next = s;
        r = s; // 将r置为新的尾指针
        cin >> e;
    }
    r->next = NULL; // 尾指针的next置为NULL
    return L;
}

// 前插操做:在p结点以前插入数据e
bool InsertPriorNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = new LNode;
    s->next = p->next;
    s->data = p->data; // 数据后移,模拟结点后移
    p->next = s;
    p->data = e; // 将前结点置为新插入的结点
    return true;
}

// 后插操做:在p结点以后插入数据e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *q = new LNode;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return true;
}

// 按位序插入
bool InserstList(LinkList &L, int i, int e) {
    if (i < 1) { // i值不合法
        return false;
    }
    LNode *p = GetElem(L, i - 1); // 遍历查找i-1个结点
    InsertNextNode(p, 5244);      // 使用后插法
    /*  // 使用前插法,达到一样效果
    LNode *p = GetElem(L, i);
    InsertPriorNode(p, 5244);
    */
    return true;
}

// 删除p结点的后继结点
bool DeleteNextDNode(LNode *p) {
    if (p == NULL || p->next == NULL) {
        return false;
    }
    LNode *s = new LNode;
    s = p->next;
    p->next = s->next;
    delete s;
    return true;
}

// 删除指定结点
bool DeleteNode(LNode *p) {
    if (p == NULL) {
        return false;
    }
    LNode *s = new LNode;
    s = p->next;       // q指向被删除结点
    p->data = s->data; // 数据前移,模拟结点前移
    p->next = s->next; // 断开与被删除结点的联系
    delete s;
    return true;
}

// 按位序删除
bool ListDelte(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    /*  // 按结点删除,实现一样效果
    LNode *p = GetElem(L, i);  // 被删除结点
    e = p->data;
    DeleteNode(p);
    */
    LNode *p = GetElem(L, i - 1);
    e = p->next->data;
    DeleteNextDNode(p);  // 删除前一结点的后继结点
    return true;
}

// 遍历单链表
void TraverseList(LinkList &L) {
    if (L->next == NULL) {
        return;
    }
    LNode *p = L->next; // 指向头指针
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkList L;
    InitList(L);

    L = List_TailInsert(L); // 尾插法
    // L = List_HeadInsert(L);  // 头插法
    TraverseList(L);

    InserstList(L, 1, 5244);
    TraverseList(L);

    int e = -1;
    ListDelte(L, 3, e);
    cout << "被删除的值:" << e << endl;
    TraverseList(L);
    cout << "长度:" << GetLength(L) << endl;
    return 0;
}