实验二、链式存储结构线性表的建立及操作

W1ndys Lv6
  2023-09-29 20:42 2023-09-29 20:42 创建   2025-10-27 19:25 2025-10-27 19:25 更新      2.7k 字  12 分钟  

声明：仅供留档查阅，仅用作起到提示引导性作用，仅用作学习交流，切勿直接照搬

代码主体

以下是一个简单的C++实现，用于维护单链表：

来自bing ai

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <iostream>
using namespace std;

template <typename DataType>
struct Node
{
    DataType data;        // 数据域
    Node<DataType>* next; // 指针域
};

template <typename DataType>
class LinkList
{
public:
    LinkList();                    // 无参构造函数，建立只有头结点的空链表
    LinkList(DataType a[], int n); // 有参构造函数，建立有n个元素的单链表
    ~LinkList();                   // 析构函数
    int Length();                  // 求单链表的长度
    int Empety();
    DataType Get(int i);            // 按位查找。查找第i个结点的元素值
    int Locate(DataType x);         // 按值查找。查找值为x的元素序号
    void Insert(int i, DataType x); // 插入操作，第i个位置插入值为x的结点
    DataType Delete(int i);         // 删除操作，删除第i个结点
    void PrintList();               // 遍历操作，按序号依次输出各元素
private:
    Node<DataType>* first; // 单链表的头指针
};

template <typename DataType>
LinkList<DataType>::LinkList()
{
    first = new Node<DataType>; // 生成头结点
    first->next = nullptr;      // 头结点的指针域置空
}

template <typename DataType>
int LinkList<DataType>::Empety()
{
    if (first->next == nullptr)
        return 1;
    else
        return 0;
}

template <typename DataType>
void LinkList<DataType>::PrintList()
{
    Node<DataType>* p = first->next; // 工作指针p初始化
    while (p != nullptr)
    {
        cout << p->data << "\t";
        p = p->next; // 工作指针p后移，注意不能写作p++
    }
}

template <typename DataType>
int LinkList<DataType>::Length()
{
    Node<DataType>* p = first->next; // 工作指针p初始化为开始接点
    int count = 0;                   // 累加器count初始化
    while (p != nullptr)
    {
        p = p->next;
        count++;
    }
    return count; // 注意count的初始化和返回值之间的关系
}

template <typename DataType>
DataType LinkList<DataType>::Get(int i)
{
    Node<DataType>* p = first->next; // 工作指针p初始化
    int count = 1;                   // 累加器count初始化
    while (p != nullptr && count < i)
    {
        p = p->next; // 工作指针p后移
        count++;
    }
    if (p == nullptr)
        throw "位置";
    else
        return p->data;
}

template <typename DataType>
int LinkList<DataType>::Locate(DataType x)
{
    Node<DataType>* p = first->next; // 工作指针p初始化
    int count = 1;                   // 累加器count初始化
    while (p != nullptr)
    {
        if (p->data == x)
            return count; // 查找成功，结束函数并返回序号
        p = p->next;
        count++;
    }
    return 0; // 退出循环表明查找失败
}

template <typename DataType>
void LinkList<DataType>::Insert(int i, DataType x)
{
    Node<DataType>* p = first, * s = nullptr; // 工作指针p初始化
    int count = 0;
    while (p != nullptr && count < i - 1) // 查找第i – 1个结点
    {
        p = p->next; // 工作指针p后移
        count++;
    }
    if (p == nullptr)
        throw "位置"; // 没有找到第i – 1个结点
    else
    {
        s = new Node<DataType>;
        s->data = x; // 申请结点s，数据域为x
        s->next = p->next;
        p->next = s; // 将结点s插入到结点p之后
    }
}

template <typename DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{
    first = new Node<DataType>;              // 生成头结点
    Node<DataType>* r = first, * s = nullptr; // 尾指针初始化
    for (int i = 0; i < n; i++)
    {
        s = new Node<DataType>;
        s->data = a[i];
        r->next = s;
        r = s; // 将结点s插入到终端结点之后
    }
    r->next = nullptr; // 单链表建立完毕，将终端结点的指针域置空
}

template <typename DataType>
DataType LinkList<DataType>::Delete(int i)
{
    DataType x;
    Node<DataType>* p = first, * q = nullptr; // 工作指针p指向头结点
    int count = 0;
    while (p != nullptr && count < i - 1) // 查找第i-1个结点
    {
        p = p->next;
        count++;
    }
    if (p == nullptr || p->next == nullptr) // 结点p不存在或p的后继结点不存在
        throw "位置";
    else
    {
        q = p->next;
        x = q->data;       // 暂存被删结点
        p->next = q->next; // 摘链
        delete q;
        return x;
    }
}

template <class DataType>
LinkList<DataType>::~LinkList()
{
    Node<DataType>* q = NULL;
    while (first != NULL) // 释放单链表的每一个结点的存储空间
    {
        q = first;           // 暂存被释放结点
        first = first->next; // first指向被释放结点的下一个结点
        delete q;
    }
}

int main()
{
    int maxsize;
    cout << "请输入你要创建数组的大小" << endl;
    cin >> maxsize;
    int* a = new int[maxsize];
    for (int i = 0; i < maxsize; i++)
    {
        a[i] = i+1;
        cout << " " << endl;
    }
    cout << "已创建一个最大长度"<<maxsize<<"的随机数链表" << endl;
    LinkList<int> L{ a, maxsize };
    cout << "执行遍历链表" << endl;
    L.PrintList();
    cout << endl;
    cout << "请输入一个最大长度内的数字查找元素" << endl;
    int i;
    cin >> i;
    cout << L.Locate(i) << endl;
    cout << "请插入一个新数字元素，请依次输入位置和数据" << endl;
    int j, k;
    cin >> j >> k;
    L.Insert(j, k);
    cout << "执行遍历链表" << endl;
    L.PrintList();
    cout << endl;
    cout << "请删除一个新数字元素，请输入位置" << endl;
    int l;
    cin >> l;
    cout << "删除的元素位置是" << l << "数据是" << L.Get(l) << endl;
    L.Delete(l);
    cout << "执行遍历链表" << endl;
    L.PrintList();
    cout << endl;
    return 0;
}

这个程序首先创建了一个空的单链表，然后向其中添加了一些节点。然后，它遍历了整个列表，查找了一个元素，插入了一个新的元素，删除了一个元素，然后再次遍历了整个列表。希望这个示例能对你有所帮助！

两个有序单链表合并为一个有序单链表

当然，这是一个包含main函数的完整程序，它创建了两个有序链表，并将它们合并为一个有序链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>

// 定义链表节点
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

int main() {
    // 创建第一个有序链表：1 -> 3 -> 5
    ListNode *l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);

    // 创建第二个有序链表：2 -> 4 -> 6
    ListNode *l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);

    // 合并两个有序链表
    ListNode *merged = mergeTwoLists(l1, l2);

    // 打印合并后的链表
    while (merged != NULL) {
        std::cout << merged->val << " ";
        merged = merged->next;
    }

    return 0;
}

这个程序首先创建了两个有序链表l1和l2，然后调用mergeTwoLists函数将它们合并为一个新的有序链表。最后，它遍历新的链表并打印出每个节点的值。

请注意，这个程序没有释放分配给链表节点的内存。在实际使用中，你应该在不再需要节点时释放它们的内存，以防止内存泄漏。此外，这个程序假设输入的链表已经排序。如果输入的链表没有排序，你需要先对它们进行排序。

双链表

双链表是一种更复杂的线性数据结构，它的每个节点都有两个链接，一个指向前一个节点，另一个指向后一个节点。以下是一个使用C++实现的双链表的基本设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>

// 定义双链表节点
struct ListNode {
    int val;
    ListNode *prev;
    ListNode *next;
    ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

// 添加节点到双链表的末尾
void addNode(ListNode* &head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == NULL) {
        head = newNode;
    } else {
        ListNode* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

// 打印双链表
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != NULL) {
        std::cout << temp->val << " ";
        temp = temp->next;
    }
    std::cout << std::endl;
}

int main() {
    // 创建一个空的双链表
    ListNode* head = NULL;

    // 添加节点到双链表
    addNode(head, 1);
    addNode(head, 2);
    addNode(head, 3);

    // 打印双链表
    printList(head);

    return 0;
}

这个程序首先定义了一个双链表节点的结构，然后定义了两个函数：addNode用于向双链表的末尾添加新的节点，printList用于打印双链表的所有节点。在main函数中，它创建了一个空的双链表，然后添加了几个节点，并打印出了这个双链表。

请注意，这个程序没有释放分配给链表节点的内存。在实际使用中，你应该在不再需要节点时释放它们的内存，以防止内存泄漏。此外，你可能还需要实现其他操作，如删除节点、查找节点等。这取决于你的具体需求。如果你需要帮助实现这些操作，请随时向我询问！

循环链表

循环链表是一种特殊的链表，其中最后一个元素指向链表的第一个元素。这种类型的数据结构可以用于实现需要循环或重复的算法。以下是一个使用C++实现的循环链表的基本设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>

// 定义链表节点
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 添加节点到循环链表的末尾
void addNode(ListNode* &head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == NULL) {
        head = newNode;
        newNode->next = head;
    } else {
        ListNode* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = head;
    }
}

// 打印循环链表
void printList(ListNode* head) {
    if (head == NULL) return;
    ListNode* temp = head;
    do {
        std::cout << temp->val << " ";
        temp = temp->next;
    } while (temp != head);
    std::cout << std::endl;
}

int main() {
    // 创建一个空的循环链表
    ListNode* head = NULL;

    // 添加节点到循环链表
    addNode(head, 1);
    addNode(head, 2);
    addNode(head, 3);

    // 打印循环链表
    printList(head);

    return 0;
}

这个程序首先定义了一个链表节点的结构，然后定义了两个函数：addNode用于向循环链表的末尾添加新的节点，printList用于打印循环链表的所有节点。在main函数中，它创建了一个空的循环链表，然后添加了几个节点，并打印出了这个循环链表。

请注意，这个程序没有释放分配给链表节点的内存。在实际使用中，你应该在不再需要节点时释放它们的内存，以防止内存泄漏。此外，你可能还需要实现其他操作，如删除节点、查找节点等。这取决于你的具体需求。如果你需要帮助实现这些操作，请随时向我询问！

  • 标题: 实验二、链式存储结构线性表的建立及操作
  • 作者: W1ndys
  • 创建于 : 2023-09-29 20:42:00
  • 更新于 : 2025-10-27 19:25:00
  • 链接: https://blog.w1ndys.top/posts/50b4f37a.html
  • 版权声明: 版权所有 © W1ndys，禁止转载。
评论
目录
实验二、链式存储结构线性表的建立及操作
  1. 代码主体
  2. 两个有序单链表合并为一个有序单链表
  3. 双链表
  4. 循环链表