数据结构 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;				// 初始化顺序表长度为0return 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) // 判断当前列表是否已经满了，如果满了就返回ERRORreturn 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.lengthif ((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; // 顺序表长度减少 1return 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还有剩余元素，直接放入Bwhile (i < L.length){B.elem[k++] = L.elem[i++];}// 如果A还有剩余元素，直接放入Bwhile (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; // 将顺序表长度重置为0return OK;
}// 函数：将顺序表B的值赋给L
// 功能：清空L后，将B的值复制到L中
Status AssignList(SqList &L, SqList B)
{ClearList(L);				 // 先清空LL.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 BBook e;			   // 定义书籍eint count, i, ps; // count用于存储书籍的数量，i用于索引,ps为元素的位置int choose = -1;   // 用户选择的操作，初始化为-1showMenu();		   // 显示操作菜单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";}elsecout << "插入失败!\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赋给Lcout << "归并成功，并将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";}elsecout << "清楚数据成功";}}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)
{// 构造一个空的单链表LL = new LNode;	// 生成新结点作为头结点，用头指针L指向头结点L->next = NULL; // 头结点的指针域置空return OK;
}// 2.头插法创建链表
void CreateList_H(LinkList &L, int n)
{	// 逆位序输入n个元素的值，建立到头结点的单链表LLinkList p;// LNode *p;for (int i = 0; i < n; ++i){p = new LNode; // 生成新结点*pcout << "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个元素之前插入元素eLinkList 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";}elsecout << "插入失败!\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); // 初始化LaInitList_L(Lb); // 初始化Lbcout << "请输入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; 
}