个人主页：
想转码的电筒人
专栏：
手把手教数据结构与算法
文章目录
有序线性表
概念
结构
问题描述
输入
输出
样例
解题步骤
结点类
链表类
insert函数
printAll函数
merge函数
test函数
完整代码
有序线性表
概念
单链表是一种物理存储结构上非连续、非顺序的存储结构，但链表在逻辑上是连续的，顺序的，而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
结构
单链表是由一个个结点组成的，结点如下图所示：
注意：单链表中的最后一个结点的next指向空，next=NULL，一个个结点串联组成了链表。
上图是为了方便大家理解，才用线条连接了结点，实际上在内存中，每个结点可能会隔得很远，每个结点右半部分就是这个结点的地址，很明显能看到这两个结点的地址并不是相邻的，因此也验证了顺序表在逻辑结构上确实是连续的，但在物理存储结构上确实是不连续的。
链表的基本操作
1.插入操作（Insert）： 在指定节点之后插入新节点
2.删除操作（Delete）： 删除指定位置的节点
3.访问操作（Access）：获取链表中指定位置的节点值
4.获取长度（GetLength）：获取链表的长度
5.搜索操作（Search）： 判断链表中是否包含指定的值，搜索指定值在链表中的位置（索引）。
6.其他操作：
反转链表（Reverse）：将链表中的节点顺序颠倒过来。
合并链表（MergeLists）：将两个链表合并成一个链表。
切分链表（SplitList）：将链表从指定位置切分成两个链表。
环检测（HasCycle）：检测链表中是否存在环。 找出链表中点（FindMiddle）：返回链表的中间节点
有序线性表（Ordered Linear List）也是一种链表，其中的元素按照某种顺序排列。通常，这种顺序是指元素按照某个关键字的大小进行排序，下面让我们一起实现它。
问题描述
设计一个有序线性表类，要求完成初始化，插入和遍历功能，使得表内元素实现有序排列（从小到大）。同时实现合并功能，使得两个线性表能够合并为一个线性表（可能存在重复元素）。
- 要求使用链表和泛型编程。
- 注：不要忘了回收指针。
输入
第一行输入字符串 dtype(“int”或者”float”)表示数据存储类型。
第二行输入 int 型数据 N1（N1≥0），代表第一个线性表元素数量；
第三行输入 N1 个 dtype 型数据，每个数据由空格隔开；
第四行输入 int 型数据 N2（N2≥0），代表第二个线性表元素数量；
第五行输入 N2 个 dtype 型数据，每个数据由空格隔开；
输出
遍历第一个线性表，第一行输出其遍历结果，每个数据由空格隔开。
遍历第二个线性表，第二行输出其遍历结果，每个数据由空格隔开。
第三行输出第一个线性表和第二个线性表合并后的遍历结果，每个数据由空格隔开。
- 注：线性表为空时仅输出换行符，每行输出的末尾没有空格。
样例
输入：
int
7 15 24 0 13 7 15 8
3 15 1 2输出：
0 7 8 13 15 15 24
1 2 15
0 1 2 7 8 13 15 15 15 24
解题步骤
结点类
首先是链表的结点设计，可以设计出结构体 Node 表示结点，其中包含有 data 域和 next 指针，如下图：
其中 data 表示数据，其可以是简单的类型，也可以是复杂的结构体，故采用泛型编程template<typename T>。next 指针表示，下一个的指针，其指向下一个结点，通过 next 指针将各个结点链接。结点类还有构造函数，在创建结点时可以进行初始化，
template <typename T>
struct Node
{
Node* next;
T value;
};链表类
链表只需要头指针用来指向链表的起点，构造函数只需让head指向空结点，析构函数则用来删除链表中所有的结点
class List
{
public:
Node<T>* head;
List() : head(nullptr) {
head = new Node<T>;
head->next = nullptr;
};
~List()
{
Node<T>* p;
while (head != nullptr)
{
p = head;
head = head->next;
delete p;
}
}
};insert函数
向队列中插入一个节点，值为value，使得表内元素实现有序排列（从小到大）
在链表中插入结点时，若链表为空，则将该新结点作为空结点，若链表不为空，题目要求该链表为有序线性表，故需要先通过比较新插入的结点值与链表结点值，找到结点插入的位置再进行插入
void insert(T value)
{
Node<T>* p = head; //获得头节点指针
Node<T>* node = new Node<T>; //创建新的节点
node->value = value;
node->next = nullptr;
Node<T>* tem = head;
if (p == nullptr) p->value = value;
for (; p != nullptr;)
{
if (node->value > p->value)
{
tem = p;
p = p->next;
}
else
{
node->next = tem->next;
tem->next = node;
break;
}
}
if (tem && tem->next != node)
{
tem->next = node;
}
}printAll函数
遍历并输出线性表
从头指针开始遍历即可。通过一个指针从链表的第一个元素开始，依次遍历每个节点，并输出节点的值。最终在打印完成后输出换行符。
void printAll()
/*
函数名：printAll
输入值：无
功 能：遍历并输出线性表
*/
{
Node<T>* p = head->next;
if (p == nullptr)
{
cout << endl;
return;
}
for (; p->next != nullptr;)
{
cout << p->value << " ";
p = p->next;
}
cout << p->value;
cout << endl;
}merge函数
合并两个线性表
遍历线性表2，使用insert函数将表2的结点插入表1，即可实现表1和表2的合并
void merge(List<T>* l2)
{
Node<T>* p = l2->head->next;
for (; p != nullptr;)
{
insert(p->value);
p = p->next;
}
}test函数
调用链表函数完成题目要求
void test()
{
int N1, N2;
T value;
List<T> l1, l2;
cin >> N1;
for (; N1 > 0; N1--)
{
cin >> value;
l1.insert(value);
}
l1.printAll();
cin >> N2;
for (; N2 > 0; N2--)
{
cin >> value;
l2.insert(value);
}
l2.printAll();
l1.merge(&l2);
l1.printAll();
}完整代码
#include <iostream>
using namespace std;
template <typename T>
struct Node
{
Node* next;
T value;
};
template <typename T>
class List
{
public:
Node<T>* head;
List() : head(nullptr) {
head = new Node<T>;
head->next = nullptr;
};
~List()
{
Node<T>* p;
while (head != nullptr)
{
p = head;
head = head->next;
delete p;
}
}
void insert(T value)
{
Node<T>* p = head; //获得头节点指针
Node<T>* node = new Node<T>; //创建新的节点
node->value = value;
node->next = nullptr;
Node<T>* tem = head;
if (p == nullptr) p->value = value;
for (; p != nullptr;)
{
if (node->value > p->value)
{
tem = p;
p = p->next;
}
else
{
node->next = tem->next;
tem->next = node;
break;
}
}
if (tem && tem->next != node)
{
tem->next = node;
}
}
void printAll()
{
Node<T>* p = head->next;
if (p == nullptr)
{
cout << endl;
return;
}
for (; p->next != nullptr;)
{
cout << p->value << " ";
p = p->next;
}
cout << p->value;
cout << endl;
}
void merge(List<T>* l2)
{
Node<T>* p = l2->head->next;
for (; p != nullptr;)
{
insert(p->value);
p = p->next;
}
}
};
template <typename T>
void test()
{
int N1, N2;
T value;
List<T> l1, l2;
cin >> N1;
for (; N1 > 0; N1--)
{
cin >> value;
l1.insert(value);
}
l1.printAll();
cin >> N2;
for (; N2 > 0; N2--)
{
cin >> value;
l2.insert(value);
}
l2.printAll();
l1.merge(&l2);
l1.printAll();
}
int main()
{
string dtype;
cin >> dtype;
if (dtype == "int")
test<int>();
else
test<float>();
return 0;
}
