数据结构-链表-代码

标签：node read 代码 list pos next 链表 single 数据结构

单链表 - 每个节点需要存储下一节点的地址

不要求大片连续的空间，改变容量方便 + 但是不能随机存储，要耗费一定空间存放指针

不带头结点
带头结点 - 更方便 —— 所以一般采用带头结点的方式

带头结点

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

typedef int ElemType;

struct SingleListNode   // 单链表节点定义
{
    ElemType data;  // 节点数据
    SingleListNode* next;   // 指向下一节点的指针
};
typedef SingleListNode* SingleList; // 指针类型的节点可以作为单链表的表头，此处只是为了使用时区分节点和链表
/*  // 链表也可如下定义，很多教材上也是这样定义的（只是我个人喜欢按上面那种方式）
typedef struct   // 单链表节点定义
{
    ElemType data;  // 节点数据
    SingleListNode* next;   // 指向下一节点的指针
}SingleListNode, * SingleList;  */

// 链表初始化
bool SingleListInit(SingleList* single_list)    // 使用指针做参数
{
    *single_list = (SingleListNode*)malloc(sizeof(SingleListNode)); // 参数以指针形式传入，因此使用*single_list
    if (*single_list == NULL)   // 分配空间失败
    {
        cout << "The request of space is fail" << endl;
        return false;
    }
    // (*single_list)表示取传入参数的指针，即取到SingleList*类型的变量
    // 如果使用*single_list->data，编译器会分不出*操作符的对象（single_list or data），因此报错
    (*single_list)->data = 0;
    (*single_list)->next = NULL;    // 表头的next置空
    return true;
}

// 链表数据初始化-头插法
void SingleListInitByHead(SingleList* single_list)
{
    cout << "Please cin the number of list element" << endl;
    int single_list_length = 0;
    cin >> single_list_length; // 输入初始化时链表中元素的个数
    cout << "Please cin the element of list" << endl;
    ElemType e;
    for (int temp = 0; temp < single_list_length; temp++)
    {
        cin >> e;
        SingleListNode* new_node = (SingleListNode*)malloc(sizeof(SingleListNode));
        if (new_node == NULL)   // 分配空间失败
        {
            cout << "The request of space is fail, and exit" << endl;
            return;
        }
        new_node->data = e;
        new_node->next = (*single_list)->next;  // 新结点的next指向表头的next
        (*single_list)->next = new_node;    // 表头的next更新为新结点
    }
}

// 链表数据初始化-尾插法
void SingleListInitByTail(SingleList* single_list)
{
    cout << "Please cin the number of list element" << endl;
    int single_list_length = 0;
    cin >> single_list_length; // 输入初始化时链表中元素的个数
    cout << "Please cin the element of list" << endl;
    SingleListNode* tail_node = *single_list;   // 记录链表的尾结点
    ElemType e;
    for (int temp = 0; temp < single_list_length; temp++)
    {
        cin >> e;
        SingleListNode* new_node = (SingleListNode*)malloc(sizeof(SingleListNode));
        if (new_node == NULL)   // 分配空间失败
        {
            cout << "The request of space is fail, and exit" << endl;
            return;
        }
        new_node->data = e;
        new_node->next = NULL;  // 新插入的节点会成为新的尾结点，尾结点的next为NULL
        tail_node->next = new_node; // 尾结点的next指向新结点
        tail_node = new_node;   // 新结点成为新的尾结点
    }
}

// 在位序pos的地方插入元素e
bool SingleListInsertAtPos(SingleList* single_list, int pos, ElemType e)
{
    SingleListNode* list_read = *single_list;   // 遍历链表
    int read_count = 0; // 记录当前的位序
    while (list_read != NULL)
    {
        if (read_count == pos - 1)  // 位序=pos-1时跳出
        {
            break;
        }
        list_read = list_read->next;    // 访问下一个节点
        read_count++;
    }
    if (read_count != pos - 1)  // 位序超范围
    {
        cout << "the position is illegal" << endl;
        return false;
    }
    SingleListNode* new_node = (SingleListNode*)malloc(sizeof(SingleListNode));
    if (new_node == NULL)   // 新节点请求空间失败
    {
        cout << "The request of space is fail, and exit" << endl;
        return false;
    }
    new_node->data = e;
    new_node->next = list_read->next;   // 新结点的next赋值为pos-1的next，如果插入的是尾节点，会直接置为NULL
    list_read->next = new_node; // pos-1的next更新为新结点，对于带头结点的链表，不需要额外处理
    return true;
}

// 删除位序pos上的元素
bool SingleListDeleteAtPos(SingleList* single_list, int pos, ElemType* e)
{
    SingleListNode* list_read = *single_list;   // 遍历链表
    int read_count = 0; // 记录当前的位序
    while (list_read != NULL)
    {
        if (read_count == pos - 1)  // 位序=pos-1时跳出
        {
            break;
        }
        list_read = list_read->next;    // 访问下一个节点
        read_count++;
    }
    if (read_count != pos - 1)  // 位序超范围
    {
        cout << "the position is illegal" << endl;
        return false;
    }
    SingleListNode* deleted_node = list_read->next; // 暂存将被删除的节点
    *e = deleted_node->data;
    list_read->next = deleted_node->next;   // pos-1的next指向被删除节点的next
    free(deleted_node); // 释放被删除节点的空间
    return true;
}

// 查找元素e在链表中的位序
int SingleListFindE(SingleList single_list, ElemType e)
{
    SingleListNode* list_read = single_list->next;   // 遍历链表
    int read_count = 0; // 记录当前的位序
    while (list_read != NULL)
    {
        if (list_read->data == e)
        {
            return (read_count + 1);
        }
        read_count++;
        list_read = list_read->next;
    }
    cout << "the element is not find" << endl;
    return -1;
}

// 链表元素输出
void SingleListPrint(SingleList single_list)
{
    SingleListNode* list_read = single_list->next;  // 直接取链表的第一个数据，即头结点的next
    while (list_read != NULL)   // list_read==NULL时，表示到了尾结点之后的节点
    {
        cout << list_read->data << " ";
        list_read = list_read->next;
    }
    cout << endl;
}

int main()
{
    int pos;
    ElemType e;

    SingleList single_list;
    SingleListInit(&single_list);
    cout << "Please select a insertion method" << endl << "0: AtHead, 1: AtTail" << endl;
    int inser_method = 0;
    cin >> inser_method;
    if (inser_method == 0)
    {
        SingleListInitByHead(&single_list);
    }
    else
    {
        SingleListInitByTail(&single_list);
    }
    SingleListPrint(single_list);

    cout << "Please cin the location and element that will be inserted" << endl;
    cin >> pos >> e;
    SingleListInsertAtPos(&single_list, pos, e);
    SingleListPrint(single_list);

    cout << "Please cin the location of the element that will be deleted" << endl;
    cin >> pos;
    SingleListDeleteAtPos(&single_list, pos, &e);
    cout << "the deleted element: " << e << endl;
    SingleListPrint(single_list);

    cout << "Please cin the element that will be find" << endl;
    cin >> e;
    cout << "the element is at: " << SingleListFindE(single_list, e) << endl;

    return 0;
}

不带头结点

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

typedef int ElemType;   // 数据类型定义

struct SingleListNode
{
    ElemType data;  // 链表节点上的数据
    int length; // 不带头结点的链表，无法通过头结点的状态判断链表是否为空，因此新增一个属性标志链表是否为空
    SingleListNode* next;   // 指向下一个节点
};
typedef SingleListNode* SingleList; // 定义链表，和指向节点的指针做区分

// 链表初始化
bool SingleListInit(SingleList& single_list)    // 使用引用&声明参数，那么函数中对参数的操作会作用与参数本身
{
    SingleListNode* init_node = (SingleListNode*)malloc(sizeof(SingleListNode));
    if (init_node == NULL)  // 申请空间失败
    {
        cout << "The request of space is fail" << endl;
        return false;
    }
    init_node->data = 0; // data置0，避免脏数据
    init_node->next = NULL; // next置空，也表示当前节点为尾结点
    init_node->length = 0;  // 链表长度置0
    single_list = init_node;
    return true;
}

// 链表判空
bool SingleListIsEmpty(SingleList single_list)
{
    if (single_list->length == 0)
    {
        return true;
    }
    return false;
}

// 链表数据初始-头插法
void SingleListInitByHead(SingleList& single_list)
{
    cout << "Please cin the number of list element" << endl;
    int single_list_length = 0;
    cin >> single_list_length; // 输入初始化时链表中元素的个数
    cout << "Please cin the element of list" << endl;
    ElemType e;
    for (int temp = 0; temp < single_list_length; temp++)
    {
        cin >> e;
        if (SingleListIsEmpty(single_list)) // 插入的是第一个元素（会成为头结点）
        {
            single_list->data = e;
            single_list->next = NULL;   // 在头插法中，第一个节点会成为尾结点，因此next置空
        }
        else
        {
            SingleListNode* new_node = (SingleListNode*)malloc(sizeof(SingleListNode));
            if (new_node == NULL)   // 分配空间失败
            {
                cout << "The request of space is fail, and exit" << endl;
                return;
            }
            new_node->data = e;
            new_node->next = single_list;   // 新结点的next指向表头
            single_list = new_node; // 表头指向新结点
        }
        single_list->length++;
    }
}

// 链表初始化-尾插法
void SingleListInitByTail(SingleList& single_list)
{
    cout << "Please cin the number of list element" << endl;
    int single_list_length = 0;
    cin >> single_list_length; // 输入初始化时链表中元素的个数
    cout << "Please cin the element of list" << endl;
    ElemType e;
    SingleListNode* tail_node = single_list;
    for (int temp = 0; temp < single_list_length; temp++)
    {
        cin >> e;
        if (SingleListIsEmpty(single_list)) // 插入的是第一个元素（会成为头结点）
        {
            single_list->data = e;
            single_list->next = NULL;
        }
        else
        {
            SingleListNode* new_node = (SingleListNode*)malloc(sizeof(SingleListNode));
            if (new_node == NULL)   // 分配空间失败
            {
                cout << "The request of space is fail, and exit" << endl;
                return;
            }
            new_node->data = e;
            new_node->next = tail_node->next;   // 插入表头时，节点的next就已经置空，因此此处可以直接使用tail的next
            tail_node->next = new_node; // 将新结点连接到尾结点的next
            tail_node = new_node;   // 尾结点更新
        }
        single_list->length++;
    }
}

// 在链表位序pos插入元素e
bool SingleListInsertAtPos(SingleList& single_list, int pos, ElemType e)
{
    SingleListNode* new_node = (SingleListNode*)malloc(sizeof(SingleListNode));
    if (new_node == NULL)   // 新节点请求空间失败
    {
        cout << "The request of space is fail, and exit" << endl;
        return false;
    }
    if (pos == 1)   // 向位序1插入元素，即插入表头，对于不带头结点的链表需要单独处理
    {
        new_node->data = e;
        new_node->next = single_list;   // 连接表头
        single_list = new_node; // 表头更新
        single_list->length++;  // 长度++
        return true;
    }
    SingleListNode* list_read = single_list;    // 遍历链表
    int pos_count = 1;  // 标记位序
    while (list_read != NULL)
    {
        if (pos_count == pos - 1)   // 位序=pos-1
        {
            break;
        }
        list_read = list_read->next;    // 访问下一个链表元素
        pos_count++;
    }
    if (pos_count != pos - 1)   // 输入的位序超范围
    {
        cout << "the position is illegal" << endl;
        return false;
    }
    new_node->data = e;
    new_node->next = list_read->next;   // 连接上一元素的next
    list_read->next = new_node; // 上一元素的next连接到新结点
    single_list->length++;
    return true;
}

// 删除位序pos上的元素
bool SingleListDeleteAtPos(SingleList& single_list, int pos, ElemType& e)
{
    SingleListNode* list_read = single_list;
    if (pos == 1)   // 删除位序1的节点，即删除头结点，需要单独处理
    {
        e = list_read->data;
        single_list = list_read->next;  // 头结点更新
        free(list_read);    // 释放节点
        single_list->length--;
        return true;
    }
    int pos_count = 1;  // 当前位序为1
    while (list_read != NULL)
    {
        if (pos_count == pos - 1)   // 找到位序为pos-1的元素
        {
            break;
        }
        list_read = list_read->next;    // 访问链表下一元素
        pos_count++;
    }
    if (pos_count != pos - 1)   // 位序超范围
    {
        cout << "the position is illegal" << endl;
        return false;
    }
    SingleListNode* deleted_node = list_read->next; // 被删除的节点暂存
    e = deleted_node->data;
    list_read->next = deleted_node->next;   // 上一节点的next更新
    free(deleted_node); // 释放
    single_list->length--;
    return true;
}

// 查找元素e在链表中的位序
int SingleListFindE(SingleList single_list, ElemType e)
{
    SingleListNode* list_read = single_list;    // 遍历链表
    int pos_count = 1;
    while (list_read != NULL)   // 链表尾
    {
        if (list_read->data == e)
        {
            return pos_count;
        }
        list_read = list_read->next;
        pos_count++;
    }
    cout << "the element is not find" << endl;
    return -1;
}

// 链表数据输出
void SingleListPrint(SingleList single_list)
{
    if (SingleListIsEmpty(single_list)) // 空链表
    {
        cout << "the list is empty" << endl;
        return;
    }
    SingleListNode* list_read = single_list;
    while (list_read != NULL)
    {
        cout << list_read->data << " ";
        list_read = list_read->next;
    }
    cout << endl;
}

int main()
{
    int pos;
    ElemType e;

    SingleList single_list;
    SingleListInit(single_list);
    cout << "Please select a insertion method" << endl << "0: AtHead, 1: AtTail" << endl;
    int inser_method = 0;
    cin >> inser_method;
    if (inser_method == 0)
    {
        SingleListInitByHead(single_list);
    }
    else
    {
        SingleListInitByTail(single_list);
    }
    SingleListPrint(single_list);

    cout << "Please cin the location and element that will be inserted" << endl;
    cin >> pos >> e;
    SingleListInsertAtPos(single_list, pos, e);
    SingleListPrint(single_list);

    cout << "Please cin the location of the element that will be deleted" << endl;
    cin >> pos;
    SingleListDeleteAtPos(single_list, pos, e);
    cout << "the deleted element: " << e << endl;
    SingleListPrint(single_list);

    cout << "Please cin the element that will be find" << endl;
    cin >> e;
    cout << "the element is at: " << SingleListFindE(single_list, e) << endl;
    SingleListPrint(single_list);

    return 0;
}

双链表

基础理解：双链表就是设计一个数据结构 DNode ，这个结构中含有数据项
数据
前驱节点指针
后继节点指针

双链表是一个多了前驱结点指针的单链表，指针双向，因此称为双链表

带头结点的双链表

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

typedef int ElemType;   // 定义数据类型

struct DoubleListNode
{
    ElemType data;  // 节点数据
    DoubleListNode* prior;  // 指向前驱节点
    DoubleListNode* next;   // 指向后继节点
};
typedef DoubleListNode* DoubleList; // 双链表声明

// 链表初始化
bool DoubleListInit(DoubleList& double_list)
{
    double_list = (DoubleListNode*)malloc(sizeof(DoubleListNode));  // 分配头结点空间
    if (double_list == NULL)    // 请求空间失败
    {
        cout << "The request of space is fail" << endl;
        return false;
    }
    double_list->data = 0;  // 数据初始化
    double_list->next = NULL;   // 前驱节点置空
    double_list->prior = NULL;  // 后继结点置空
    return true;
}

// 数据初始化-头插法
void DoubleListInitByHead(DoubleList& double_list)
{
    cout << "Please cin the number of list element" << endl;
    int single_list_length = 0;
    cin >> single_list_length; // 输入初始化时链表中元素的个数
    cout << "Please cin the element of list" << endl;
    ElemType e;
    for (int temp = 0; temp < single_list_length; temp++)
    {
        cin >> e;
        DoubleListNode* new_node = (DoubleListNode*)malloc(sizeof(DoubleListNode)); // 申请新结点的空间
        if (new_node == NULL)   // 申请空间失败
        {
            cout << "The request of space is fail, and exit" << endl;
            return;
        }
        new_node->data = e; // 数据赋值
        DoubleListNode* the_next = double_list->next;   // 暂存原来的第一个数据节点
        new_node->next = the_next;  // 新结点的后继指向原来的数据节点
        double_list->next = new_node;   // 链表的头结点指向新结点
        new_node->prior = double_list;  // 新结点的前驱指向表头
        if (the_next != NULL)   // the_next == NULL 表示这是插入的第一个节点
        {
            the_next->prior = new_node; // 原节点的前驱指向新结点
        }
    }
}

//  数据初始化-尾插法
void DoubleListInitByTail(DoubleList& double_list)
{
    cout << "Please cin the number of list element" << endl;
    int single_list_length = 0;
    cin >> single_list_length; // 输入初始化时链表中元素的个数
    cout << "Please cin the element of list" << endl;
    ElemType e;
    DoubleListNode* tail_node = double_list;    // 记录尾结点
    for (int temp = 0; temp < single_list_length; temp++)
    {
        cin >> e;
        DoubleListNode* new_node = (DoubleListNode*)malloc(sizeof(DoubleListNode));
        if (new_node == NULL)   // 请求空间失败
        {
            cout << "The request of space is fail, and exit" << endl;
            return;
        }
        new_node->data = e;
        new_node->next = NULL;  // 新插入的节点会成为尾结点，因此next置空
        tail_node->next = new_node; // 新结点连接到尾结点上
        new_node->prior = tail_node;    // 新结点的前驱连接到原来的尾结点
        tail_node = new_node;   // 尾结点标志更新
    }
}

// 向位序pos插入元素e
bool DoubleListInsertAtPos(DoubleList& double_list, int pos, ElemType e)
{
    DoubleListNode* list_read = double_list;  // 遍历链表
    int pos_count = 0;  // 位序
    while (list_read != NULL)
    {
        if (pos_count == pos - 1)   // 找到位序为pos-1的节点
        {
            break;
        }
        list_read = list_read->next;
        pos_count++;
    }
    if (pos_count != pos - 1)   // 没找到相应节点
    {
        cout << "the position is illegal" << endl;
        return false;
    }
    DoubleListNode* new_node = (DoubleListNode*)malloc(sizeof(DoubleListNode)); // 分配空间给新结点
    if (new_node == NULL)   //请求空间失败
    {
        cout << "The request of space is fail" << endl;
        return false;
    }
    new_node->data = e;
    new_node->next = list_read->next;   // 后继结点连接pos-1的后继
    list_read->next = new_node; // pos-1的后继更新为新结点
    new_node->prior = list_read;    // 前驱节点更新为pos-1
    if (list_read->next != NULL)    // 如果pos-1的后继节点不为空，那么需要将pos-1的后继节点的前驱节点更新为新结点
    {
        list_read->next->prior = new_node;
    }
    return true;
}

// 查找元素e，并返回e所在的节点
DoubleListNode* DoubleListFindE(DoubleList double_list, ElemType e, int& e_pos)
{
    DoubleListNode* list_read = double_list->next;  // 遍历链表
    e_pos = 1;  // 位序
    while (list_read != NULL)
    {
        if (list_read->data == e)
        {
            return list_read;
        }
        e_pos++;    // 位序++
        list_read = list_read->next;
    }
    e_pos = -1;
    cout << "the element is not find" << endl;
    return NULL;
}

// 在指定节点前插入数据
bool DoubleListInsertForwardNode(DoubleListNode*& node, ElemType e)
{
    DoubleListNode* new_node = (DoubleListNode*)malloc(sizeof(DoubleListNode));
    if (new_node == NULL)   // 请求空间失败
    {
        cout << "The request of space is fail" << endl;
        return false;
    }
    new_node->data = e;
    DoubleListNode* prior_node = node->prior;   // 暂存指定节点的前驱
    new_node->next = node;  // 新结点的后继指向新结点
    new_node->prior = prior_node;   // 新结点的前驱指向指定节点的前驱
    node->prior = new_node; // 指定节点的前驱指向新结点
    if (prior_node != NULL) // 如果指定节点的前驱节点不为空（即指定节点不是头结点）
    {
        prior_node->next = new_node;    // 新结点连接到指定节点的前驱
    }
    return true;
}

// 在指定节点后插入数据
bool DoubleListInsertBackwardNode(DoubleListNode*& node, ElemType e)
{
    DoubleListNode* new_node = (DoubleListNode*)malloc(sizeof(DoubleListNode));
    if (new_node == NULL)   // 请求空间失败
    {
        cout << "The request of space is fail" << endl;
        return false;
    }
    new_node->data = e;
    DoubleListNode* next_node = node->next; // 暂存后继节点
    new_node->next = next_node; // 新结点的后继指向node的后继
    new_node->prior = node; // 新结点的前驱指向node
    node->next = new_node;  // node的后继指向新结点
    if (next_node != NULL)  // next_node不为空，即指定节点不为表尾
    {
        next_node->prior = new_node;    // 新结点连接到指定节点的后继
    }
    return true;
}

// 删除位序pos的元素
bool DoubleListDeleteAtPos(DoubleList& double_list, int pos, ElemType& e)
{
    DoubleListNode* list_read = double_list;    // 遍历链表
    int pos_count = 0;  // 位序
    while (list_read != NULL)
    {
        if (pos_count == pos - 1)   // 位序为pos-1
        {
            break;
        }
        pos_count++;
        list_read = list_read->next;
    }
    if (pos_count != pos - 1)   // 位序超范围
    {
        cout << "the position is illegal" << endl;
        return false;
    }
    DoubleListNode* deleted_node = list_read->next; // 暂存要被删除的节点
    e = deleted_node->data;
    list_read->next = deleted_node->next;   // 前驱的next直接指向后继
    if ((deleted_node->next) != NULL)   // 后继不为NULL，后继为NULL即被删除的是表尾
    {
        (deleted_node->next)->prior = list_read;
    }
    free(deleted_node); // 释放空间
    return true;
}

// 链表数据输出-顺序输出
void DoubleListPrint(DoubleList double_list)
{
    DoubleListNode* list_read = double_list->next;
    while (list_read != NULL)
    {
        cout << list_read->data << " ";
        list_read = list_read->next;
    }
    cout << endl;
}

int main()
{
    int pos;
    ElemType e;
    DoubleListNode* node;

    DoubleList double_list;
    DoubleListInit(double_list);
    cout << "Please select a insertion method" << endl << "0: AtHead, 1: AtTail" << endl;
    int inser_method = 0;
    cin >> inser_method;
    if (inser_method == 0)
    {
        DoubleListInitByHead(double_list);
    }
    else
    {
        DoubleListInitByTail(double_list);
    }
    DoubleListPrint(double_list);

    cout << "Please cin the location and element that will be inserted" << endl;
    cin >> pos >> e;
    DoubleListInsertAtPos(double_list, pos, e);
    DoubleListPrint(double_list);

    cout << "Please cin the element that will be find" << endl;
    cin >> e;
    node = DoubleListFindE(double_list, e, pos);
    cout << "the element is at: " << pos << endl;

    cout << "input the element that will be insert before e: " << endl;
    cin >> e;
    DoubleListInsertForwardNode(node, e);
    cout << "insert element before e, and the result is: " << endl;
    DoubleListPrint(double_list);
    cout << "input the element that will be insert backward e: " << endl;
    cin >> e;
    DoubleListInsertBackwardNode(node, e);
    cout << "insert element backward e, and the result is: " << endl;
    DoubleListPrint(double_list);

    cout << "Please cin the location of the element that will be deleted" << endl;
    cin >> pos;
    DoubleListDeleteAtPos(double_list, pos, e);
    cout << "the deleted element: " << e << endl;
    DoubleListPrint(double_list);

    return 0;
}

循环链表

循环链表是一个首位相连的单链表或者双链表

虽然循环链表与普通的单链表、双链表没太大的差距，但是循环链表有其特殊的应用场景：
对于需要频繁操作表头、表尾的链表，可以使用循环链表

|| 利用 尾结点 -> next == 头结点的特性，可以将头尾操作控制在时间复杂度 O(1) ，即每次操作都针对尾结点
|| 需要注意 == 链表指针指向尾结点，这样才能每次直接通过链表指针找到尾结点
|| 需要注意 == 当链表尾结点发生变化时，也要同步链表指针的变化

对于循环链表的定义与操作和单链表、双链表相似，只是需要特殊注意头结点和尾结点的处理

循环单链表

首尾相接的单链表：尾结点 -> next = 头结点

链表初始状态为 L -> next = L;

循环双链表

首尾相接的双链表：尾结点 ->next = 头结点 && 头结点 -> prior = 尾结点

链表初始状态为 L -> next = L; 此时也有 L -> prior = L;
但是判断循环双链表是否为空可以只需要一个条件 L -> next = L;

循环单链表

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

typedef int ElemType;   // 数据类型初始化

struct LoopListNode
{
    ElemType data;  // 链表数据
    LoopListNode* next; // 下一节点
};
typedef LoopListNode* LoopList;

// 链表初始化
bool LoopListInit(LoopList& loop_list)
{
    loop_list = (LoopListNode*)malloc(sizeof(LoopListNode));
    if (loop_list == NULL)  // 申请空间失败
    {
        cout << "The request of space is fail" << endl;
        return false;
    }
    loop_list->data = 0;    // 数据初始化
    loop_list->next = loop_list;    // 初始化时头结点的next指向头结点
    return true;
}

// 数据初始化-头插法
bool LoopListInitByHead(LoopList& loop_list)
{
    cout << "Please cin the number of list element" << endl;
    int list_length = 0;
    cin >> list_length; // 输入初始化时链表中元素的个数
    cout << "Please cin the element of list" << endl;
    ElemType e;
    for (int temp = 0; temp < list_length; temp++)
    {
        cin >> e;
        LoopListNode* new_node = (LoopListNode*)malloc(sizeof(LoopListNode));
        if (new_node == NULL)   // 申请空间失败
        {
            cout << "The request of space is fail" << endl;
            return false;
        }
        new_node->data = e; // 赋值
        new_node->next = loop_list->next;   // 循环链表初始化时，头结点的next指向头结点，因此不用单独处理第一个插入的元素
        loop_list->next = new_node;
    }
    return true;
}

// 数据初始化-尾插法
bool LoopListInitByTail(LoopList& loop_list)
{
    cout << "Please cin the number of list element" << endl;
    int list_length = 0;
    cin >> list_length; // 输入初始化时链表中元素的个数
    cout << "Please cin the element of list" << endl;
    ElemType e;
    LoopListNode* tail_node = loop_list;    // 记录尾结点
    for (int temp = 0; temp < list_length; temp++)
    {
        cin >> e;
        LoopListNode* new_node = (LoopListNode*)malloc(sizeof(LoopListNode));
        if (new_node == NULL)   // 申请空间失败
        {
            cout << "The request of space is fail" << endl;
            return false;
        }
        new_node->data = e; // 赋值
        new_node->next = tail_node->next;   // 循环链表初始化时，头结点的next指向头结点，因此不用处理尾结点
        tail_node->next = new_node; // 尾结点更新
        tail_node = new_node;
    }
    return true;
}

// 查找元素e，并返回e所在的节点
LoopListNode* LoopListFindE(LoopList& loop_list, ElemType e, int& e_pos)
{
    LoopListNode* list_read = loop_list->next;  // 直接从第一个元素开始遍历
    e_pos = 1;  // 位序
    while (list_read != loop_list)
    {
        if (list_read->data == e)
        {
            return list_read;
        }
        list_read = list_read->next;
        e_pos++;
    }
    e_pos = -1; // 未找到该元素
    cout << "the element is not find" << endl;
    return NULL;
}

// 在节点node后插入元素
bool LoopListInsertBackwardNode(LoopListNode* node, ElemType e)
{
    LoopListNode* new_node = (LoopListNode*)malloc(sizeof(LoopListNode));
    if (new_node == NULL)   // 申请空间失败
    {
        cout << "The request of space is fail" << endl;
        return false;
    }
    new_node->data = e; // 赋值
    new_node->next = node->next;    // 新结点的next指向指定节点的next
    node->next = new_node;  // 指定节点的next指向新结点
    return true;
}

// 删除位序pos的元素
bool LoopListDeleteAtPos(LoopList& loop_list, int pos, ElemType& e)
{
    LoopListNode* list_read = NULL; // while的判断是list_read != loop_list，因此遍历链表需要从NULL开始
    int pos_count = 0;  // 位序
    while (list_read != loop_list)
    {
        if (pos_count == pos - 1)   // 找到位序为pos-1的元素
        {
            break;
        }
        if (list_read == NULL)  // 当前还是位序为0的元素
        {
            list_read = loop_list->next;    // 访问位序为1的元素
        }
        else
        {
            list_read = list_read->next;    // 访问下一个元素
        }
        pos_count++;
    }
    if (pos_count != pos - 1)   // 位序超范围
    {
        cout << "the position is illegal" << endl;
        return false;
    }
    LoopListNode* deleted_node = list_read->next;   // 暂存被删除的节点
    e = deleted_node->data;
    list_read->next = deleted_node->next;   // 前驱节点的next指向被删除节点的后继
    free(deleted_node); // 释放空间
    return true;
}

// 链表输出
void LoopListPrint(LoopList loop_list)
{
    LoopListNode* list_read = loop_list->next;  // 从第一个有数据的节点开始访问
    while (list_read != loop_list)
    {
        cout << list_read->data << " ";
        list_read = list_read->next;
    }
    cout << endl;
}

int main()
{
    int pos;
    ElemType e;
    LoopListNode* node;

    LoopList loop_list;
    LoopListInit(loop_list);
    cout << "Please select a insertion method" << endl << "0: AtHead, 1: AtTail" << endl;
    int inser_method = 0;
    cin >> inser_method;
    if (inser_method == 0)
    {
        LoopListInitByHead(loop_list);
    }
    else
    {
        LoopListInitByTail(loop_list);
    }
    LoopListPrint(loop_list);

    cout << "Please cin the element that will be find" << endl;
    cin >> e;
    node = LoopListFindE(loop_list, e, pos);
    cout << "the element is at: " << pos << endl;

    cout << "input the element that will be insert backward e: " << endl;
    cin >> e;
    LoopListInsertBackwardNode(node, e);
    cout << "insert element backward e, and the result is: " << endl;
    LoopListPrint(loop_list);

    cout << "Please cin the location of the element that will be deleted" << endl;
    cin >> pos;
    LoopListDeleteAtPos(loop_list, pos, e);
    cout << "the deleted element: " << e << endl;
    LoopListPrint(loop_list);

    return 0;
}

静态链表

静态链表物理结构上其实是一个数组

因此，这个链表在内存中分配到的是一整片位置
同时具有数组的性质：只要知道数组的0下标指针，那么其余下标的元素的地址可计算，数组的元素平均分配一整片空间，每个元素分配到的大小为 sizeof(StaticNode)
代码的逻辑关系是：数据项 data 对应结点的值，next 对应本结点的后继结点的数组下标
实现逻辑比较灵活，如：StaticLinkList[0]为头结点，
StaticLinkList[0].next=2; 表示头结点的下一个结点（后继结点）在数组下标为2的地方，
即 StaticLinkList[2]，这个结点的下一个结点可能是数组任意一个位置

静态链表

#include <iostream>
using namespace std;

#define MAX_SIZE 6  // 初始化链表的长度

typedef int ElemType;

struct SingleListNode
{
    ElemType data;  // 当前节点上的值
    int next;   // 下一节点的游标
};

struct SingleList
{
    SingleListNode node[MAX_SIZE];  // 静态链表是一个结构体数组
    int free_head;  // 空闲链表的表头游标，当游标值为-1时，表示没有空闲节点
    int value_head; // 被使用的节点的表头游标，当链表中没有元素时，游标值为-1
};

// 初始化
void SingleListInit(SingleList* single_list)
{
    for (int temp = 0; temp < MAX_SIZE; temp++)
    {
        single_list->node[temp].next = temp + 1;    // 空闲链表节点按顺序组织，即节点n的next=n+1节点
        single_list->node[temp].data = 0;   // 数据初始化
    }
    single_list->node[MAX_SIZE - 1].next = -1;   // 最后一个元素的游标指向-1表示表尾
    single_list->free_head = 0; // 初始化时，所有节点都在空闲链表上，以arr[0]为表头
    single_list->value_head = -1;   // 无数据节点
}

// 头插法初始化链表
bool SingleListInitByHead(SingleList* single_list)
{
    cout << "Please cin the number of sing_list element" << endl;
    int sing_list_len = 0;  // 初始化输入时，元素的个数
    cin >> sing_list_len;
    if (sing_list_len > MAX_SIZE)
    {
        cout << "too many element" << endl; // 元素个数超范围
        return false;
    }
    cout << "Please cin the element of single list" << endl;
    ElemType e;
    for (int temp = 0; temp < sing_list_len; temp++)    // 插入链表元素
    {
        cin >> e;
        int node_pos = single_list->free_head;  // 得到当前空闲的节点下标，直接取下空闲节点的表头，时间复杂度O(1)
        if (node_pos == -1) // 无空闲节点
        {
            cout << "the sequence is full" << endl;
            return false;
        }
        single_list->free_head = single_list->node[single_list->free_head].next;    // 空闲链表表头更新
        single_list->node[node_pos].data = e;   // 赋值
        if (single_list->value_head != -1)  // 当前不是第一次插入数据，因此需要连接原有的链表
        {
            single_list->node[node_pos].next = single_list->value_head; // 连接之前的数据表头
        }
        else    // 第一次插入数据，由于是使用的头插法，这个数据最后会变成表尾，表尾的next设为-1
        {
            single_list->node[node_pos].next = -1;
        }
        single_list->value_head = node_pos; // 数据表表头更新
    }
    return true;
}

// 尾插法初始化链表
bool SingleListInitByTail(SingleList* single_list)
{
    cout << "Please cin the number of sing_list element" << endl;
    int sing_list_len = 0;  // 初始化输入时，元素的个数
    cin >> sing_list_len;
    if (sing_list_len > MAX_SIZE)
    {
        cout << "too many element" << endl; // 元素个数超范围
        return false;
    }
    cout << "Please cin the element of single list" << endl;
    ElemType e;
    int tail_node = single_list->value_head;    // 记录链表的表尾，这样每次插入时不用遍历链表，时间复杂度O(1)
    for (int temp = 0; temp < sing_list_len; temp++)    // 插入链表元素
    {
        cin >> e;
        int node_pos = single_list->free_head;  // 得到当前空闲的节点下标，直接取下空闲节点的表头，时间复杂度O(1)
        if (node_pos == -1) // 无空闲节点
        {
            cout << "the sequence is full" << endl;
            return false;
        }
        single_list->free_head = single_list->node[single_list->free_head].next;    // 空闲链表表头更新
        single_list->node[node_pos].data = e;   // 赋值
        single_list->node[node_pos].next = -1;  // 使用尾插法，每次插入的都是表尾，表尾的next游标赋值
        if (tail_node == -1)    // 第一次插入数据
        {
            single_list->value_head = node_pos; // 数据表表头更新
        }
        else
        {
            single_list->node[tail_node].next = node_pos;   // 将新节点连接到之前的表尾
        }
        tail_node = node_pos;   // 表尾更新
    }
    return true;
}

// 向位序pos插入一个元素
bool SingleListInsertAtPos(SingleList* single_list, int pos, ElemType e)
{
    int list_read = -2; // 遍历链表游标，初始化为-2，标志当前是否为头结点，应对在位序1插入元素的情况
    int pos_count = 0;  // 记录当前被访问元素的位序，位序从0开始，0表示表头的前一个元素（是虚构的元素）
    while (list_read != -1) // list_read没有访问到表尾之后的元素
    {
        if (pos_count == pos - 1)   // 位序为pos-1的时候
        {
            break;  // 当需要在表头插入元素时，位序就为pos-1=0，直接break
        }
        pos_count++;    // 位序++，表示当前即将访问的元素的位序
        if (list_read == -2)    // 标志还未访问表头，因此访问位序1的元素
        {
            list_read = single_list->value_head;    // 访问表头
        }
        else
        {
            list_read = single_list->node[list_read].next;  // 访问下一位序的元素
        }
    }
    if (pos_count != pos - 1)   // 遍历全表也没有位序为pos的，表示pos超范围
    {
        cout << "the position is illegal" << endl;
        return false;
    }
    if (single_list->free_head == -1)   // 没有空闲节点了
    {
        cout << "the list is full" << endl;
        return false;
    }
    int new_node = single_list->free_head;  // 取一个空闲节点
    // 空闲节点更新为原节点的next，当取到最后一个空闲节点，这个next就会被更新为-1
    single_list->free_head = single_list->node[new_node].next;
    single_list->node[new_node].data = e;   // 赋值
    if (pos_count != 0) // 非头结点
    {
        single_list->node[new_node].next = single_list->node[list_read].next;   // 新结点的next指向pos-1位序节点的下一节点
        single_list->node[list_read].next = new_node;   // pos-1位序节点的next指向新结点
    }
    else    // 向头结点前插入数据
    {
        single_list->node[new_node].next = single_list->value_head; // 新结点的next指向原链表的表头
        single_list->value_head = new_node; // 表头更新为新结点
    }
    return true;
}

// 删除pos位序的元素
bool SingleListDeleteAtPos(SingleList* single_list, int pos, ElemType* e)
{
    int list_read = -2; // 遍历链表游标
    int pos_count = 0;  // 记录当前被访问元素的位序
    while (list_read != -1)
    {
        if (pos_count == pos - 1)   // 位序为pos-1的时候
        {
            break;
        }
        pos_count++;
        if (list_read == -2)    // 访问头结点
        {
            list_read = single_list->value_head;
        }
        else    // 访问下一节点
        {
            list_read = single_list->node[list_read].next;
        }
    }
    if (pos_count != pos - 1)   // 遍历全表也没有位序为pos的，表示pos超范围
    {
        cout << "the position is illegal" << endl;
        return false;
    }
    int deleted_node = single_list->node[list_read].next;   // 暂存需要被删除的节点
    *e = single_list->node[deleted_node].data;  // 取值
    if (pos_count != 0) // 非头结点
    {
        single_list->node[list_read].next = single_list->node[deleted_node].next;   // 直接将pos-1节点的next指向pos的next
    }
    else    // 被删除的是头结点
    {
        single_list->value_head = single_list->node[deleted_node].next; // 直接将头结点游标指向pos的next
    }
    single_list->node[deleted_node].next = single_list->free_head;  // 头插法进空闲链表
    single_list->free_head = deleted_node;  // 空闲链表头节点更新
    return true;
}

// 查找元素e在链表中的位序
int SingleListFindE(SingleList single_list, ElemType e)
{
    int list_read = single_list.value_head; // 遍历链表游标
    int pos_count = 0;  // 记录当前被访问元素的位序
    while (list_read != -1)
    {
        pos_count++;
        if (single_list.node[list_read].data == e)  // 找到
        {
            return pos_count;
        }
        list_read = single_list.node[list_read].next;
    }
    cout << "the element is not find" << endl;
    return -1;
}

// 链表输出
void SingleListPrint(SingleList single_list)
{
    int list_read = single_list.value_head; // 遍历链表游标
    while (list_read != -1)
    {
        cout << single_list.node[list_read].data << " ";
        list_read = single_list.node[list_read].next;
    }
    cout << endl;
}

// 全数组输出
void SingleListPrintAll(SingleList single_list)
{
    cout << "free_node: " << single_list.free_head << endl;
    cout << "value_node: " << single_list.value_head << endl;
    for (int temp = 0; temp < MAX_SIZE; temp++)
    {
        cout << "arr" << temp << ": " << single_list.node[temp].data << " " << single_list.node[temp].next << endl;
    }
}

int main()
{
    int pos;
    ElemType e;

    SingleList single_list;
    SingleListInit(&single_list);
    cout << "Please select a insertion method" << endl << "0: AtHead, 1: AtTail" << endl;
    int inser_method = 0;
    cin >> inser_method;
    if (inser_method == 0)
    {
        SingleListInitByHead(&single_list);
    }
    else
    {
        SingleListInitByTail(&single_list);
    }
    SingleListPrint(single_list);

    cout << "Please cin the location and element that will be inserted" << endl;
    cin >> pos >> e;
    SingleListInsertAtPos(&single_list, pos, e);
    SingleListPrint(single_list);

    cout << "Please cin the location of the element that will be deleted" << endl;
    cin >> pos;
    SingleListDeleteAtPos(&single_list, pos, &e);
    cout << "the deleted element: " << e << endl;
    SingleListPrint(single_list);

    cout << "Please cin the element that will be find" << endl;
    cin >> e;
    cout << "the element is at: " << SingleListFindE(single_list, e) << endl;

    SingleListPrintAll(single_list);

    return 0;
}

静态链表的代码说明

以上代码实现的是不带头结点的单链表
静态链表实际上是两个链表，即空闲链表和数据链表，使用两个游标分别指向两个链表的表头下标
每次需要插入数据时，则先从空闲链表上取下一个节点，为该结点赋值后，将该结点插入数据链表

每次从空闲链表的表头取节点，时间复杂度 O(1)

标签：node,read,代码,list,pos,next,链表,single,数据结构
From： https://www.cnblogs.com/Muhuai/p/18620539

单链表 - 每个节点需要存储下一节点的地址

带头结点

不带头结点

双链表

带头结点的双链表

循环链表

循环单链表

静态链表

静态链表

静态链表的代码说明

相关文章

赞助商

阅读排行