结构体与链表 --from imicola

8 结构体

自定义的数据类型，允许用户储存不同的数据类型

8.1 结构体的定义

语法：struct 结构体名{结构体成员列表};

有三种创建变量的方式:

struct 结构体名变量名
struct 结构体名变量名 = {成员1 ，成员2 ， ……}
定义结构体时顺便创建变量
例：

#include <bits/stdc++.h>
#define endl '
using namespace std;  
// 创建数据类型  
struct QAQ {  
    string s1;  
    int n1;  
    int n2;  
    // 下面是定义时候定义  
} k3;  
int main()  
{  
    // 定义结构体数据 1  
    QAQ k1;  
    k1.s1 = "aaa";  
    // 定义结构体数据 2  
    QAQ k2 = { "114", 5, 1 };  
    k3.s1 = "1919";  
    k3.n1 = 810;  
    return 0;  
}

8.2 结构体数组

定义结构体放入数组方便维护

语法：struct 结构体名数组名[元素个数] = {}

#include <bits/stdc++.h>
#define endl '
'
using namespace std;
// 创建数据类型
struct QAQ {
    string s1;
    int n1;
    int n2;
} s[10];
int main()
{
    s[1] = { "QAQ", 1, 2 };
    cout << s[1].s1;
    // 或者
    QAQ kk[5]; //第二种方法构建
    cin >> kk[3].s1;
    cout << kk[3].s1;
    return 0;
}

8.3 数组结构体

结构体可以用数组表示，数组当然也可以放在结构体中
int a[n]类型

struct test1
{
    string s;
    int a[9];
};
signed main()
{
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    cin >> t;
    test1 st[t];
    for (size_t i = 0; i < t; i++) {
        cin >> st[i].s;
        for (size_t j = 0; j < 9; j++) {
            cin >> st[i].a[j];
        }
    }
    return 0;
}

注意上述 int a[n]中的 n 为一个确定常数
vector<int>类型

struct test1
{
    string s;
    vector<int> a;
};
signed main()
{
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    cin >> t;
    test1 st[t];
    for (size_t i = 0; i < t; i++) {
        cin >> st[i].s;
        for (size_t j = 0; j < 3; j++) {
            int p;
            cin >> p;
            st[i].a.push_back(p);
        }
    }
    for (auto &&i : st) {
        cout << i.s << " ";
        for (auto &&j : i.a) {
            cout << j << " ";
        }
        cout << endl;
    }
    return 0;
}

在上述构造方法中都没有对结构体里的数组进行初始化，下面是初始化的方法
对 int a[n]而言：

直接结构体里int a[n] = {0};即可
对 vectior<int>而言：
采取显式调用即可

vector<int> a = vector<int>(n,0);

其中 $n$ 为常数

8.4结构体的构造函数

结构体构造函数的形式与用法

在 C++ 中，结构体（struct）的构造函数和类（class）的构造函数没有本质区别。构造函数是特殊的成员函数，用于在创建对象时初始化成员变量。构造函数的名称必须与结构体的名称相同。

构造函数的形式

1. 默认构造函数

不带参数的构造函数，用于初始化成员变量为默认值。

#include <iostream>
#include <string>
 
struct Person {
 std::string name;
 int age;
 
 // 默认构造函数
 Person() : name("unknown"), age(0) {}  // 使用初始化列表
};
 
int main() {
 Person p;  // 自动调用默认构造函数
 std::cout << "Name: " << p.name << ", Age: " << p.age << "
";
 return 0;
}

2. 带参数的构造函数

构造函数可以接受参数，用于动态初始化成员变量。

#include <iostream>
#include <string>
 
struct Person {
 std::string name;
 int age;
 
 // 带参数的构造函数
 Person(const std::string& n, int a) : name(n), age(a) {}
};
 
int main() {
 Person p("Alice", 25);  // 调用带参数的构造函数
 std::cout << "Name: " << p.name << ", Age: " << p.age << "
";
 return 0;
}

3. 构造函数重载

^9f688f
通过不同的参数列表定义多个构造函数，满足不同的初始化需求。

#include <iostream>
#include <string>
 
struct Person {
 std::string name;
 int age;
 
 // 默认构造函数
 Person() : name("unknown"), age(0) {}
 
 // 带参数的构造函数
 Person(const std::string& n, int a) : name(n), age(a) {}
 
 // 只初始化名字
 Person(const std::string& n) : name(n), age(18) {}  // 默认年龄为18
};
 
int main() {
 Person p1;                      // 默认构造
 Person p2("Bob", 30);           // 带参数
 Person p3("Charlie");           // 只提供名字
 
 std::cout << p1.name << ", " << p1.age << "
";
 std::cout << p2.name << ", " << p2.age << "
";
 std::cout << p3.name << ", " << p3.age << "
";
 
 return 0;
}

输出

unknown, 0
Bob, 30
Charlie, 18

4. 使用初始化列表

初始化列表用于直接初始化成员变量，避免在构造函数体内赋值。

#include <iostream>
#include <string>
 
struct Person {
 std::string name;
 int age;
 
 // 使用初始化列表
 Person(const std::string& n, int a) : name(n), age(a) {}
};
 
int main() {
 Person p("Diana", 22);  // 初始化时直接调用
 std::cout << "Name: " << p.name << ", Age: " << p.age << "
";
 return 0;
}

初始化列表的优点：

提高效率：避免默认构造后再赋值。
支持 const 和引用类型的初始化。

特殊形式

1. 委托构造函数（C++11 起支持）

一个构造函数可以委托给另一个构造函数以复用初始化逻辑。

#include <iostream>
#include <string>
 
struct Person {
    std::string name;
    int age;
 
    // 默认构造函数
    Person() : Person("unknown", 0) {}  // 委托到另一个构造函数
 
    // 带参数的构造函数
    Person(const std::string& n, int a) : name(n), age(a) {}
};
 
int main() {
    Person p1;              // 默认构造
    Person p2("Eve", 28);   // 带参数构造
 
    std::cout << p1.name << ", " << p1.age << "
";
    std::cout << p2.name << ", " << p2.age << "
";
 
    return 0;
}

2. 删除的构造函数（C++11 起支持）

可以显式删除某些构造函数，防止被意外调用。

#include <iostream>
 
struct Person {
    int age;
 
    // 禁止隐式转换或默认构造
    Person() = delete;  // 删除默认构造函数
    Person(int a) : age(a) {}
};
 
int main() {
    // Person p1;  // 编译错误：默认构造函数被删除
    Person p2(30);  // 必须传入参数
    std::cout << "Age: " << p2.age << "
";
    return 0;
}

构造函数的应用场景

初始化成员变量
- 为结构体或类的成员变量赋初始值，避免对象处于未定义状态。
动态控制初始化
- 可以根据参数灵活地初始化不同状态的对象。
封装复杂逻辑
- 在构造函数中封装一些初始化逻辑，简化外部代码。
提高代码安全性
- 使用委托构造或删除某些构造函数可以避免意外使用。

总结

构造函数是结构体中用来初始化成员变量的核心工具。
通过默认构造、参数化构造、初始化列表等形式，可以满足多样化的初始化需求。
推荐使用 初始化列表，特别是在初始化复杂类型（如 std::vector、引用、const 变量）时，效率更高。

链表

什么是链表：
- 链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。
链表的优势：对数据的处理：插入，删除 ——> $O (1)$ 但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 $O (n)$

与数组相反的是，数组在随机访问数据下时间复杂度为 $O (1)$ ，但插入删除数据为 $O (n)$

单向链表与双向链表的创建

单向链表：单向链表包括两大数据类型，即数据域和指针域

struct Node
{
    int value;
    Node *next; // 定义了一个指向该结构体(链表单位)的一个指针
    Node(int val) : value(val), next(nullptr){}
};

这个结构体函数做了什么？

初始化了一个新创建的结点，这个结点传入的参数默认赋值给了value，同时将结构体指针域默认赋值为了nullptr,表示其暂时不指向任何其他结点
双向链表
双向链表：也同样是数据域+指针域，但不同的是，指针域有左右(或上下)之分，用来链接上一个结点，当前结点，下一个结点

struct Node {
    int value;
    Node *left;
    Node *right;
    Node(int val) : value(val) , left(nullptr) , right(nullptr){}
};

向链表里写入与删去数据

流程大致如下

初始化待插入的数据 node；
将 node 的 next 指针指向 p 的下一个结点；
将 p 的 next 指针指向 node。
但在这之前，我们要创建一个链表头
Node *head = nullptr
我们的操作都会在这个头链表上开始

在头部插入数据

时间复杂度O(1)

void insert_head_node(Node *newnode, Node *&head)
{
    newnode->next = head;
    head = newnode;
}

在某一个pos值上插入元素

void insert_pos_node(Node *newnode, int pos, Node *&head)
{
    if (pos == 0) {
        newnode->next = head;
        head = newnode;
        return;
    }
    Node *current = head;
    int currentposition = 0;
    while (current != nullptr && currentposition < pos - 1) {
        current = current->next;
        currentposition++;
    }
    newnode->next = current->next;
    current->next = newnode;
}

在尾部插入元素

在单向链表尾部插入元素，时间复杂的 $O (n)$

void insert_end_node(Node *Newnode, Node *&p)
{
    // Node *Newnode = new Node(i);
    if (p == nullptr) {
        p = Newnode;
        return;
    }
    Node *current = p;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = Newnode;
}

删除某一结点

删除某一特定值的结点

void delnode(int i, Node *&p)
{
    //链表为空
    if (p == nullptr) return;
    //头结点为目标值
    while (p != nullptr && p->val == i) {
        Node *temp = p;
        p = p->next;
        delete temp;
        t--;
    }
    //中间或尾部结点为目标
    Node *current = p;
    while (current != nullptr && current->next != nullptr) {
        if (current->next->val == i) {
            Node *temp = current->next;
            current->next = current->next->next;
            delete temp;
            t--;
        }
        else {
            current = current->next;
        }
    }
}

删除某一位置的结点

void posdel(int pos, Node *&head)
{
    if (head == nullptr || pos < 0) return;
    if (pos == 0) {
        Node *temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node *current = head;
    for (int i = 0; i < pos && current != nullptr; i++) {
        current = current->next;
    }
    if (current == nullptr || current->next == nullptr) return;
    Node *temp = current->next;
    current->next = current->next->next;
    delete temp;
}

imicola's Blog

探索

结构体与链表