登录以参加训练计划

存储方式的分类

分为顺序存储与链式存储。

顺序存储结构（静态存储）

在（子）程序的说明部分就必须加以说明，以便分配固定大小的存储单元，直到（子）程序结束，才释放空间。因此，这种存储方式又称为静态存储。所定义的变量相应的称为静态变量。

它的优缺点如下：

优点: 可以通过一个简单的公式随机存取表中的任一元素。 逻辑关系上相邻的两个元素在物理位置上也是相邻的，且很容易找到前趋与后继元素，例如我们常见的数组。

缺点: 1，在线性表的长度不确定时，必须分配最大存储空间，使存储空间得不到充分利用，浪费了宝贵的存储资源。

2，线性表的容量一经定义就难以扩充。

3，在插入和删除线性表的元素时，需要移动大量的元素，浪费了时间。

链式存储结构

在程序的执行过程中，通过两个命令向计算机随时申请存储空间或随时释放存储空间，以达到动态管理、使用计算机的存储空间，保证存储资源的充分利用。这样的存储方式称为动态存储。所定义的变量称为动态变量。 优点： 可以用一组任意的存储单元（这些存储单元可以是连续的，也可以是不连续的）存储线性表的数据元素，这样就可以充分利用存储器的零碎空间。

为了表示任意存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域、data）外，还要存储它的直接后继元素的存储位置（指针域、link 或 next）。我们把这两部分信息合在一起称为一个“结点（node）”。

N个结点链接在一起就构成了一个链表。N=0时，称为空链表。

为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储整个链表的第一个结点的物理位置，这个变量称为“头指针（H 或 head）”。 也可以把头指针定义成一个结点，称为“头结点”，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域（头指针）存储指向第一个结点的指针，若线性表为空表，则头结点的指针域为空（nullptr）。 由于最后一个元素没有后继，所以线性表中最后一个结点的指针域为空（nullptr）。 由于此链表中的每个结点都只包含一个指针域，故称为“线性链表或单链表”。

一、单链表的定义

1. 类型和变量的说明

struct Node {
    int data;
    Node* next;
};
Node* P;

2. 申请存储单元

   p = new Node;  // 动态申请，空间大小由指针变量的基类型决定
   

3. 指针变量的赋值 不同于简单变量（如 a = 0;），C++ 规定用“指针变量名->成员名”的形式引用指针变量（如 p->data = 0;）。

二，单链表的结构、建立、输出

由于单链表的每个结点都有一个数据域和一个指针域，所以，每个结点都可以定义成一个记录。比如，有如下一个单链表，

如何定义这种数据结构呢？ 下面给出建立并输出单链表的程序，大家可以把它改成过程用在以后的程序当中。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* head, *p, *r;  // r 指向链表的当前最后一个结点，可以称为尾指针
int x;

int main() {
    cin >> x;
    head = new Node;  // 申请头结点
    head->next = nullptr;  // 头结点的指针域初始化为 NULL
    r = head;  // 尾指针初始化为头结点

    while (x != -1) {  // 读入的数非 -1
        p = new Node;  // 否则，申请一个新结点
        p->data = x;
        p->next = nullptr;
        r->next = p;  // 把新结点链接到前面的链表中，实际上是 p 的直接前驱
        r = p;  // 尾指针后移一个
        cin >> x;  // 继续读入下一个数
    }

    // 输出链表
    Node* current = head->next;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;

    return 0;
}

改成函数后的代码：

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

// 函数：建立链表
Node* createList() {
    Node* head = new Node;  // 申请头结点
    head->next = nullptr;  // 头结点的指针域初始化为 NULL
    Node* r = head;  // 尾指针初始化为头结点
    int x;

    cout << "请输入链表元素（输入-1结束）：" << endl;
    while (true) {
        cin >> x;
        if (x == -1) break;  // 输入 -1 结束输入
        Node* p = new Node;  // 申请一个新结点
        p->data = x;
        p->next = nullptr;
        r->next = p;  // 把新结点链接到前面的链表中，实际上是 p 的直接前驱
        r = p;  // 尾指针后移一个
    }

    return head;
}

// 函数：输出链表
void printList(Node* head) {
    Node* current = head->next;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main() {
    Node* head = createList();  // 调用建立链表的函数
    printList(head);  // 调用输出链表的函数

    return 0;
}

三，单链表的操作

1.查找“数据域满足一定条件的结点”

  Node *p = head->next;
  while ((p->data != x) && (p->next != NULL)) 
    p = p->next;
 
  // 找到第一个就结束
    if (p->data == x) {
      // 找到了处理
    } else {
      // 输出不存在
    }
  

如果想找到所有满足条件的结点，则修改如下：

Node *p = head->next;
while (p->next != NULL) {  // 一个一个判断
    if (p->data == x) {  // 找到一个处理一个
        // 处理找到的结点
    }
    p = p->next;
}

2.查找“数据域满足一定条件的结点”

void get(Node *head, int i) {
   Node *p;
   int j;
   p = head->next;
   j = 1;

   while ((p != NULL) && (j < i)) {
       p = p->next;
       j = j + 1;
   }

   if ((p != NULL) && (j == i)) {
       // 找到第 i 个结点，处理 p->data
   } else {
       // 未找到第 i 个结点，处理未找到的情况
   }
}

3. 插入一个结点在单链表中 如图 插入结点前和后的链表变化

void insert(Node *head, int i, int x) {  // 插入 X 到第 i 个元素之前
    Node *p, *s;
    int j;
    p = head;
    j = 0;

    while ((p != NULL) && (j < i - 1)) {  // 寻找第 i-1 个结点，插在它的后面
        p = p->next;
        j = j + 1;
    }

    if (p == NULL) {
        cout << "no this position!";
    } else {![](/file/2/FeEsqZE-an3lz3J4J3iwG.png)

        // 插入
        s = new Node;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}

4. 删除单链表中的第 i 个结点 如图 删除一个结点前和后链表的变化

void deleteNode(Node *head, int i) {  // 删除第 i 个元素
    Node *p, *s;
    int j;
    p = head;
    j = 0;

    while ((p != NULL) && (j < i - 1)) {  // 寻找第 i-1 个结点
        p = p->next;
        j = j + 1;
    }

    if (p == NULL || p->next == NULL) {
        cout << "no this position!";
    } else {
        // 删除
        s = p->next;
        p->next = s->next;
        delete s;
    }
}