数据结构 C/C++(实验一:线性表)
（大家好，今天分享的是数据结构的相关知识，大家可以在评论区进行互动答疑哦~加油！💕）
目录
提要：实验题目
一、实验目的
二、实验内容及要求
三、算法思想
实验1
实验2
四、源程序及注释
实验1代码（顺序存储结构）
实验2代码（链式存储结构）
五、实验结果
实验1结果
实验2结果
提要：实验题目
1. 线性表顺序存储结构下基本操作的实现
2. 线性表链式存储结构下基本操作的实现
一、实验目的
- 1．掌握线性表的顺序存储表示和链式存储表示。
- 2．掌握顺序表和链表的基本操作算法，包括创建、取值、查找、插入、删除等基本操作的实现。
- 3．了解线性表两种不同存储结构的特点，会灵活运用线性表解决某些实际问题。
二、实验内容及要求
- 1．线性表顺序存储结构下基本操作的实现（初始化、建表、取值、查找、插入、删除、两个非递减有序链表的归并等）。
- 2．线性表链式存储结构下基本操作的实现（初始化、建表、取值、查找、插入、删除、两个非递减有序链表的归并等）。
三、算法思想
实验1
（1.）初始化
初始化操作主要涉及到为顺序表分配内存空间，并设置其初始状态。通过定义一个顺序表的结构体，并为其动态分配一个足够大小的数组来完成。算法上，是内存分配的过程。
（2.）建表
建表操作是在初始化后的顺序表中填充数据元素。这是通过遍历一个给定的数据集合（如数组），并将每个元素依次存入顺序表的数组中来实现。算法上，这是一个简单的遍历过程。
（3.）取值
取值操作是根据给定的位置索引，从顺序表中获取对应位置上的数据元素。由于顺序表的数据元素在内存中连续存放，因此可以通过直接计算偏移地址来获取所需元素。算法上，这是一个简单的数组访问操作。
（4.）查找
查找操作是在顺序表中搜索具有给定值的元素，并返回其位置索引。通过遍历整个顺序表来查找元素
（5.）插入
插入操作是在顺序表的指定位置插入一个新的数据元素。这涉及到将指定位置及其之后的所有元素向后移动一个位置，为新元素腾出空间。算法上，这涉及到元素的移动操作。
（6.）删除
删除操作是从顺序表的指定位置移除一个数据元素。这涉及到将指定位置之后的所有元素向前移动一个位置，以填补被删除元素留下的空白。算法上，这涉及到元素的移动操作。
（7.）两个非递减有序链表的归并
归并算法通过遍历两个链表，比较当前节点的值，选择较小的节点接入新链表中，并移动指针继续比较，直到所有节点都被遍历完。这涉及到创建一个新的顺序表或数组来存储归并后的结果，并通过双指针技术来遍历两个原顺序表或数组。
实验2
基本算法思想一致
四、源程序及注释
实验1代码（顺序存储结构）
#include <iostream> // 输入输出流头文件
#include <fstream> // 文件操作头文件
#include <string> // 字符串操作头文件
#include <iomanip> // 输入输出操纵运算头文件
using namespace std; // 调用命名空间std中所有标识符，简化标准库函数的调用
#define MAXSIZE 1000 // 定义数组的最大容量
// 预定义常量及预定义类型
#define OK 1 // 操作成功时的返回值
#define ERROR 0 // 操作失败时的返回值
#define OVERFLOW -2 // 内存溢出错误的返回值
typedef int Status; // 定义Status为返回值类型，用于表示函数的执行状态
// 定义Book结构体来存储书籍的信息
typedef struct
{
int id; // 书籍的ISBN编号
double price; // 书籍的价格
} Book;
// 定义顺序表（顺序存储的线性表）结构体，用于存储一组书籍
typedef struct
{
Book *elem; // 指向存储书籍的动态数组
int length; // 顺序表的当前长度
} SqList;
// 1.初始化
Status initList(SqList &L)
{
L.elem = new Book[MAXSIZE]; // 动态分配最大容量的数组空间
if (!L.elem) // 如果内存分配失败
exit(OVERFLOW); // 退出程序并返回溢出错误
L.length = 0; // 初始化顺序表长度为0
return OK; // 返回成功状态
}
// 3.取值
Status GetElem(SqList L, int i, Book &e)
{
if (i < 1 || i > L.length) // 检查i是否超出有效范围
return ERROR; // 返回错误状态
e = L.elem[i - 1]; // 获取第i个元素（数组下标从0开始）
return OK; // 返回成功状态
}
// 4.查找
int LocateElem(SqList L, Book e)
{
for (int i = 0; i < L.length; i++) // 遍历顺序表中的每本书
{
if (L.elem[i].id == e.id) // 如果找到匹配的ISBN编号
return i + 1; // 返回位置（从1开始）
}
return 0; // 未找到，返回0
}
//5.插入
Status ListInsert(SqList &L, int i, Book e)
{
if ((i < 1) || (i > L.length + 1)) // 判断要插入的位置是否合法。
return ERROR;
if (L.length == MAXSIZE) // 判断当前列表是否已经满了，如果满了就返回ERROR
return ERROR;
for (int j = L.length - 1; j >= i - 1; j--)
{
L.elem[j + 1] = L.elem[j];
}
L.elem[i - 1] = e;
++L.length;
return OK;
}
//6. 删除
Status ListDelete(SqList &L, int i)
{
// 在顺序表中删除第i个元素, i值的合法范围是1<=i<=L.length
if ((i < 1) || (i > L.length))
return ERROR; // 不合法，返回错误状态
// 从位置 i 开始，将后面的元素依次向前移动
for (int j = i; j < L.length; j++)
{
L.elem[j - 1] = L.elem[j]; // 将位置 j 的元素赋值给位置 j-1
}
--L.length; // 顺序表长度减少 1
return OK; // 返回成功状态
}
//7. 归并
/*给定两个非递减有序的顺序表 A 和 B，将它们合并成一个新的非递减有序的顺序表 C。
合并步骤：
创建一个新的顺序表 C，它的长度是 A 和 B 的长度之和。
设置两个指针 i 和 j，分别指向顺序表 A 和 B 的起始位置。
比较 A[i] 和 B[j]：
如果 A[i] <= B[j]，将 A[i] 放入 C，然后指针 i 右移。
否则，将 B[j] 放入 C，然后指针 j 右移。
当其中一个顺序表（A 或 B）的所有元素都被处理完后，将另一个顺序表剩余的元素直接放入 C。
返回合并后的顺序表 C。 */
// 归并两个非递减有序的顺序表L和A到B
Status MergeList(SqList L, SqList A, SqList &B)
{
int i = 0, j = 0, k = 0; // 初始化指针
B.length = A.length + L.length; // B的长度为A和L之和
B.elem = new Book[B.length]; // 为B分配空间
if (!B.elem) // 检查内存分配
return OVERFLOW;
// 归并过程：当L和A都还有元素时进行比较
while (i < L.length && j < A.length)
{
if (L.elem[i].id <= A.elem[j].id)
{
B.elem[k++] = L.elem[i++]; // L的元素较小，放入B
}
else
{
B.elem[k++] = A.elem[j++]; // A的元素较小，放入B
}
}
// 如果L还有剩余元素，直接放入B
while (i < L.length)
{
B.elem[k++] = L.elem[i++];
}
// 如果A还有剩余元素，直接放入B
while (j < A.length)
{
B.elem[k++] = A.elem[j++];
}
return OK; // 返回成功状态
}
// 9. 清空数据表
// 功能：释放顺序表的动态数组并将其长度重置为0
Status ClearList(SqList &L)
{
if (L.elem) // 如果顺序表已经有元素
{
delete[] L.elem; // 释放动态分配的内存
L.elem = nullptr; // 将指针设为nullptr，防止悬空指针
}
L.length = 0; // 将顺序表长度重置为0
return OK;
}
// 函数：将顺序表B的值赋给L
// 功能：清空L后，将B的值复制到L中
Status AssignList(SqList &L, SqList B)
{
ClearList(L); // 先清空L
L.elem = new Book[B.length]; // 为L分配与B相同长度的内存
if (!L.elem) // 检查内存分配是否成功
return OVERFLOW;
for (int i = 0; i < B.length; i++) // 复制B中的每个元素到L
{
L.elem[i] = B.elem[i];
}
L.length = B.length; // 更新L的长度
return OK;
}
// 函数：显示菜单
// 功能：输出用户可执行的操作菜单
void showMenu()
{
cout << "****************************\n";
cout << "**** 1. 初始化 ****\n";
cout << "**** 2. 赋值 ****\n";
cout << "**** 3. 取值 ****\n";
cout << "**** 4. 查找 ****\n";
cout << "**** 5. 插入 ****\n";
cout << "**** 6. 删除 ****\n";
cout << "**** 7. 归并 ****\n";
cout << "**** 8. 输出 ****\n";
cout << "**** 9. 清空数据表 ****\n";
cout << "**** 0. 退出 ****\n";
cout << "****************************\n";
}
// 主函数
int main()
{
SqList L, A, B; // 定义顺序表L A B
Book e; // 定义书籍e
int count, i, ps; // count用于存储书籍的数量，i用于索引,ps为元素的位置
int choose = -1; // 用户选择的操作，初始化为-1
showMenu(); // 显示操作菜单
while (choose != 0) // 当用户选择不是0（退出）时，继续操作
{
cout << "请选择操作（0-8）:"; // 提示用户输入操作
cin >> choose; // 读取用户选择
switch (choose) // 根据选择执行对应的操作
{
case 1: // 初始化顺序表
initList(L); // 调用初始化函数
cout << "初始化顺序表成功：\n"; // 输出提示
break;
case 2: // 赋值
cout << "请输入图书的个数："; // 提示用户输入书籍数量
cin >> count; // 读取书籍数量
cout << "请输入图书的信息（ISBN编号 价格）：\n"; // 提示用户输入书籍信息
for (i = 0; i < count; i++) // 循环输入每本书籍的信息
cin >> L.elem[i].id >> L.elem[i].price; // 输入书籍的ISBN编号和价格
L.length = count; // 更新顺序表的长度
break;
case 3: // 取值
cout << "请输入位置："; // 提示用户输入位置
cin >> i; // 读取位置
GetElem(L, i, e); // 调用取值函数
cout << e.id << "\t" << e.price << endl; // 输出书籍的ISBN编号和价格
break;
case 4: // 查找
cout << "请输入ISBN号码："; // 提示用户输入要查找的ISBN编号
cin >> e.id; // 读取ISBN编号
cout << LocateElem(L, e) << endl; // 调用查找函数并输出结果
break;
case 5:
// 插入
cout << "请输入要插入的位置\n";
cin >> ps; // 读取插入位置
cout << "请输入图书的信息（ISBN编号 价格）："; // 提示用户输入书籍信息
cin >> e.id >> e.price; // 读取书籍的ISBN编号和价格
if (ListInsert(L, ps, e) == OK)
{
cout << "插入成功!\n";
}
else
cout << "插入失败!\n";
break;
case 6:
cout << "请输入要删除的元素的位置\n";
cin >> ps;
ListDelete(L, ps);
break;
case 7: // 归并
initList(A); // 调用初始化函数
initList(B);
cout << "请输入要与L归并的顺序表A\n";
cout << "请输入图书的个数："; // 提示用户输入书籍数量
cin >> count; // 读取书籍数量
cout << "请输入图书的信息（ISBN编号 价格）：\n"; // 提示用户输入书籍信息
for (i = 0; i < count; i++) // 循环输入每本书籍的信息
cin >> A.elem[i].id >> A.elem[i].price; // 输入书籍的ISBN编号和价格
A.length = count;
if (MergeList(L, A, B) == OK)
{
AssignList(L, B); // 将归并后的B赋给L
cout << "归并成功，并将B的值赋给L!\n";
}
else
{
cout << "归并失败!\n";
}
break;
case 8: // 输出
cout << "输出顺序表内容：\n"; // 提示即将输出顺序表内容
for (i = 0; i < L.length; i++) // 遍历顺序表中的每本书
cout << left << setw(15) << L.elem[i].id << "\t" << left << setw(5) << L.elem[i].price << endl; // 输出每本书的ISBN编号和价格，格式化对齐
break;
case 9:
ClearList(L);
if (ClearList(L) == OK)
{
cout << "清空顺序表成功\n";
}
else
cout << "清楚数据成功";
}
}
return 0; // 程序正常结束
}
实验2代码（链式存储结构）
#include <iostream> //输入输出流头文件
#include <fstream> //文件操作头文件
#include <string> //字符串操作头文件
#include <iomanip> //输入输出操纵运算头文件
using namespace std; // 调用命名空间std中所有标识符
// 预定义常量及预定义类型
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; // Status 是函数返回值类型，其值是函数结果状态代码。
// 表示部分：
typedef struct LNode
{
int data; // 结点的数据域
struct LNode *next; // 结点的指针域
} LNode, *LinkList; // LinkList为指向结构体LNode的指针类型
// 实现部分：
// 1.初始化
Status InitList_L(LinkList &L)
{
// 构造一个空的单链表L
L = new LNode; // 生成新结点作为头结点，用头指针L指向头结点
L->next = NULL; // 头结点的指针域置空
return OK;
}
// 2.头插法创建链表
void CreateList_H(LinkList &L, int n)
{ // 逆位序输入n个元素的值，建立到头结点的单链表L
LinkList p;
// LNode *p;
for (int i = 0; i < n; ++i)
{
p = new LNode; // 生成新结点*p
cout << "Please input the data：" << i + 1 << endl;
cin >> p->data; // 输入元素值赋给新结点*p的数据域
p->next = L->next;
L->next = p; // 将新结点*p插入到头结点之后
}
} // CreateList_H
// 3.尾插法创建链表
int CreateList_T(LinkList &L, int n)
{
LNode *p, *tail = L; // 尾指针
for (int i = 0; i < n; i++)
{
p = new LNode;
cout << "请输入数据：" << i + 1 << ": ";
cin >> p->data;
p->next = NULL;
tail->next = p; // 将新节点加入尾部
tail = p; // 更新尾指针
}
return OK;
}
// 4. 取值（获取链表中的第i个元素）
Status GetElem(LinkList L, int i, int &e)
{
LNode *p = L->next; // 指向第一个节点
int j = 1;
while (p && j < i) // 查找第i个节点
{
p = p->next;
j++;
}
if (!p || j > i)
return ERROR; // 第i个元素不存在
e = p->data; // 取出元素
return OK;
}
// 5.查找链表中指定元素的位置
Status LocateElem(LinkList L, int e)
{
LNode *p = L->next; // 指向第一个节点
int j = 1;
while (p)
{
if (p->data == e) // 如果找到匹配的元素
return j;
p = p->next;
j++;
}
return ERROR; // 未找到，返回0
}
//6.插入
Status ListInsert_L(LinkList &L, int i, int e)
{ // 在带头结点的单链线性表L的第i个元素之前插入元素e
LinkList p, s;
p = L;
int j = 0;
while (p && j < i - 1)
{ // 寻找第i-1个结点
p = p->next;
++j;
}
if (!p || j > i - 1)
return ERROR; // i小于1或者大于表长
s = (LinkList)malloc(sizeof(LNode)); // 生成新结点
s->data = e;
s->next = p->next; // 插入L中
p->next = s;
return OK;
} // LinstInsert_L
//7. 删除元素
Status ListDelete(LinkList &L, int i)
{
LNode *p = L; // 指向头节点
int j = 0;
while (p->next && j < i - 1) // 查找第i-1个节点
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)
return ERROR; // 删除位置不合法
LNode *q = p->next; // 要删除的节点
p->next = q->next; // 将q节点从链表中断开
delete q; // 释放q节点的内存
return OK;
}
// 8.遍历
void TraverseList_L(LinkList L)
{
LNode *p;
p = L->next;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//9.归并
Status MergeList_L(LinkList La, LinkList Lb, LinkList &Lc)
{
// 已知单链线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
LinkList pa, pb, pc;
pa = La->next;
pb = Lb->next;
Lc = pc = La; // 用La的头结点作为Lc的头结点
while (pa && pb)
{
if (pa->data <= pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb; // 插入剩余段
free(Lb); // 释放Lb的头结点
return OK;
} // MergeList_L
// 清空链表
Status AssignList(LinkList &L)
{
LNode *p = L->next;
while (p)
{
LNode *temp = p;
p = p->next;
delete temp; // 释放节点内存
}
L->next = NULL; // 重新初始化链表为空
cout << "链表已清空！\n";
return OK;
}
void showMenu()
{
cout << "****************************\n";
cout << "**** 1. 初始化 ****\n";
cout << "**** 2. 头插法创建 ****\n";
cout << "**** 3. 尾插法创建 ****\n";
cout << "**** 4. 取值 ****\n";
cout << "**** 5. 查找 ****\n";
cout << "**** 6. 插入 ****\n";
cout << "**** 7. 删除 ****\n";
cout << "**** 8. 遍历 ****\n";
cout << "**** 9. 归并 ****\n";
cout << "**** 0. 退出 ****\n";
cout << "****************************\n";
}
int main()
{
LinkList L,La,Lb;
int n,ps,count1,count2,i,i1,i2,e;
int choose = -1;
showMenu();
while (choose != 0)
{
cout << "Please select（0-9）:";
cin >> choose;
switch (choose)
{
case 1: // 1.初始化
InitList_L(L);
cout << "Init successfully：\n";
break;
case 2: // 2.头插法创建单链表
cout << "Please input the number of LNode：";
cin >> n;
CreateList_H(L, n);
break;
case 3: // 3.尾插法创建单链表
cout << "Please input the number of LNode：";
cin >> n;
CreateList_T(L, n);
break;
case 4: // 4.取值
cout << "请输入位置：";
cin >> i ; // 读取位置
GetElem(L, i, e); // 调用取值函数
cout << e << endl;
break;
case 5: // 5.查找
cout << "请输入元素："; // 提示用户输入查找
cin >> e; // 读取
cout << LocateElem(L, e) << endl; // 调用查找函数并输出结果
break;
case 6: // 6.插入
cout << "请输入要插入的位置\n";
cin >> ps; // 读取插入位置
cout << "请输入信息："; // 提示用户输入书籍信息
cin >> e; // 读取
if (ListInsert_L(L, ps, e) == OK)
{
cout << "插入成功!\n";
}
else
cout << "插入失败!\n";
break;
case 7: // 7.删除
cout << "请输入要删除的元素的位置\n";
cin >> ps;
ListDelete(L, ps);
break;
case 8: // 8.遍历
TraverseList_L(L);
break;
case 9: // 9.归并
InitList_L(La); // 初始化La
InitList_L(Lb); // 初始化Lb
cout << "请输入La链表的元素个数：";
cin >> count1;
cout << "请输入La链表的元素：\n";
CreateList_T(La, count1); // 使用尾插法创建La链表
cout << "请输入Lb链表的元素个数：";
cin >> count2;
cout << "请输入Lb链表的元素：\n";
CreateList_T(Lb, count2); // 使用尾插法创建Lb链表
// 合并两个链表，Lc 存储合并结果
if (MergeList_L(La, Lb, L) == OK)
{
cout << "归并成功，结果链表为：\n";
TraverseList_L(L); // 遍历输出归并后的结果链表
}
else
{
cout << "归并失败！\n";
}
break;
}
}
return 0;
}五、实验结果
实验1结果
实验2结果
（今日分享暂时到此为止啦！为不断努力的自己鼓鼓掌吧🥳。今日文案分享：心平能愈三千疾。）