【数据结构】实验报告07线性表的合并
⼀、实验⽬的和要求
⽬的：两个表合并成⼀个有序表。要求设计两种以上储存⽅式、两种以上处理流程⽅式。分析各代码性能。
要求：
1. 抽象数据类型独⽴实现。
2. 其它要求同作业-01要求。
⼆、实验环境
软件环境：
visual stdio 2017
硬件环境：
①CPU：Intel（R）Core（TM）i7-8565U CPU @1.80Ghz
②内存：8.0GB
三、实验内容
设计2种不同存储⽅式的线性表，对于每种线性表，随机给定2个表，⽤2种⽅式合并成为⼀个有序表（⼀种是先合并再排序，⼀种是先排序再合并）。
四、实验过程
4.1 任务定义和问题分析
解决该问题的关键在于如何⾃⾏定义⼀个线性表，剩下的合并的核⼼操作只在于排序。
4.2 数据结构的选择和概要设计
第⼀种存储结构：数组
第⼆种存储结构：链表
第⼀种合并⽅法：创建⼀个空表，依次将两个表中元素加⼊其中，最后进⾏由⼩到⼤排序
第⼆种合并⽅法：先将2个表排序，再通过⽐较，每次取其中最⼩的元素加⼊到空表中，直到元素取完，这就类似于归并排序的操作。4.3 详细设计
线性表定义成⼀个模板类，其私有成员为T a【100】（Node<T>*front,rear） 以及长度int length。
公有成员为每种表对应的构造函数（以链表为存储结构的线性表多写⼀个析构函数），int getlength（）；void push（T element）;void insert(int index,T element),void pop()；void deleteelement(int index)；
这些函数在传⼊数据不合法和表为空删除元素时，会触发cstlib中的exit（）函数，使程序终⽌。
最后是定义⼀个运算符重载函数 T & operator [](int index)，⽤来返回线性表中第index个元素，这⾥需要注意的是返回值需要引⽤返回，否则⽆法进⾏后续的根据索引进⾏排序。
五、测试及结果分析
5.1 实验数据
为保证数据中有重复，且直接合并后不是有序，选取的数据为
线性表1线性表2合并之后的表
1,3,50,2,4,6,8,50,1,2,3,4,5,5,6,8
1,3,7,50,2,4,6,8,5,30,1,2,3,3,4,5,5,6,7
线性表1线性表2合并之后的表
5.2 结果及分析
经本数据的测验以及在编写代码过程的⼀些debug后，操作结果基本全呈现正确。
数组与链表相⽐，⼆者皆有优点。数组的优点在于其存储连续，可以直接获取某⼀位上的元素，但若进⾏删除或插⼊操作，则需要对元素整体进⾏移动，其时间开销较⼤。链表的优点在于其在进⾏删除或插⼊操作时，只需要创建⼀个新的空间加⼊节点即可。
对于两种排序⽅式，经过分析我认为第⼆种的时间复杂度较低.第⼀种就是合并后进⾏冒泡排序，其时间复杂度我们知道是O（n²）。
对于第⼆种排序，先进⾏两个⼩规模表的排序，这时间复杂度虽然也为O（n²），但输⼊规模却总⼩于第⼀种。即使我们考虑极端分布，⼀个表的长度为1，另⼀个表的长度为n-1，其计算得来的实际时间复杂度也是⼩于前者的，后⾯只有⽐较和加⼊表中这两种操作，每种操作的时间复杂度为O(1)，对于所有数据来说，时间复杂度仅为O（n）。
总的来说，第⼆种排序的所有操作加起来的时间开销是⼩于第⼀种排序的。
六、实验收获
通过本次实验，让我对链表的掌握更加熟悉，同时，对线性表有了⼀定的理解，可以⾃⼰构建⼀个线性表。此外，个⼈的编程能⼒得到了⼀定的提升，对数据结构的体会也不断丰富。
数组与链表相⽐，⼆者皆有优点。数组的优点在于其存储连续，可以直接获取某⼀位上的元素，但若进⾏删除或插⼊操作，则需要对元素整体进⾏移动，其时间开销较⼤。链表的优点在于其在进⾏删除或插⼊操作时，只需要创建⼀个新的空间加⼊节点即可。
七、参考⽂献
⼋、附录（源代码）
#include<iostream>
#include<cstdlib>
using namespace std;
template<typename T>
struct Node
{
T data;
Node<T>* next;
};
template<class T>
class ArrayList
{
public:
ArrayList() :length(0) {};
int getlength() { return length; }
void push(T element)
{
if (length >= 100)
{
cout << "您的操作将导致数据溢出，现抛出" << endl;
exit(7);
}
a[length++] = element;
}
void insert(int i, T element)
{
if (i <= 0 || i > length)
{
cout << "输⼊有误，抛出" << endl;
exit(7);
}
if (length >= 100)
{
cout << "您的操作将导致数据溢出，现抛出" << endl;
exit(7);
}
for (int j = length-2; j >=i-1; j--)
{
a[j + 1] = a[j];
}
a[i - 1] = element;
length++;
}
void pop()
{
if (length <= 0)
{
cout << "表为空，⽆法进⾏pop操作，抛出" << endl;  exit(7);
}
length--;
}
void deleteelement(int i)
{
if (i <= 0 || i > length)
{
cout << "输⼊有误，抛出" << endl;
exit(7);
}
for (int j = i - 1; j < length - 1; j++)
{
a[j] = a[j + 1];
}
length--;
}
T& operator [](int index)
{
if (index <= 0 || index > length)
{
cout << "输⼊有误，抛出" << endl;
exit(7);
}
return a[index - 1];
}
private:
T a[100];
int length;
};
template<class T>
class NodeList
{
public:
NodeList():length(0)
{
front = new Node<T>;
rear = front;
front->next = NULL;
}
~NodeList()
{
while (length != 0) pop();
delete front;
}
int getlength() { return length; }
void push(T element)
{
Node<T>* node = new Node<T>;
rear->next = node;
rear->data = element;
rear->next = NULL;
length++;
}
void insert(int index, T element)
数组和链表{
if (index > length||index<=0 )
{
cout << "输⼊错误，抛出" << endl;  exit(8);
}
int i = 0;
Node<T>*p = front;
while (i != index - 1&&p!=NULL)
{
p = p->next;
i++;
}
Node<T>* s = new Node<T>;
s->next = p->next;
s->data = element;
p->next = s;
length++;
}
void pop()
{
if (length == 0)
{
cout << "表为空，不可操作" << endl;  exit(8);
}
int i = 0;
Node<T>*p = front;
while (i != length - 1 && p != NULL) {
p = p->next;
i++;
}
Node<T>* s = new Node<T>;
s = rear;
rear = p;
rear->next = NULL;
delete s;
length--;
if (front->next == NULL) rear = front; }
void deleteelement(int index)
{
if (index <= 0 || index > length)
{
cout << "输⼊错误，抛出" << endl;  exit(8);
}
int i = 0;
Node<T>*p = front;
while (i != index - 1 && p != NULL)    {
p = p->next;
i++;
}
Node<T>* s = new Node<T>;
s = p->next;
p->next = s->next;
delete s;
if (front->next == NULL) rear = front;
}
T& operator[](int index)
{
if (index <= 0 || index > length)
{
cout << "输⼊错误，抛出" << endl;
exit(8);
}
int i = 0;
Node<T>* p = front;
while (i != index && p != NULL)
{
p = p->next;
i++;
}
return p->data;
}
private:
Node<T>* front;
Node<T>* rear;
int length;
};
template<typename T>
void ArrayListBubblesort(ArrayList<T>&a) {
for (int i = 1; i < a.getlength(); i++)
{
for (int j = 1; j <= a.getlength() - i; j++)
{
if (a[j] >= a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
template<typename T>
void NodeListBubblesort(NodeList<T>&a) {
for (int i = 1; i < a.getlength(); i++)
{
for (int j = 1; j <= a.getlength() - i; j++)
{
if (a[j] >= a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
int main()
{
cout << "数组版线性表测试:" << endl; ArrayList<int> a, b;
int lengtha, lengthb;
cout << "输⼊a表原始长度:";
cin >> lengtha;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。