网站建设gongsi一家专门做印刷的网站

当前位置： 首页 > news >正文

网站建设gongsi,一家专门做印刷的网站,最好的开发网站建设,域名 就一个网站#xff08;大家好#xff0c;今天分享的是数据结构的相关知识#xff0c;大家可以在评论区进行互动答疑哦~加油#xff01;#x1f495;#xff09; 目录 提要#xff1a;实验题目 一、实验目的 二、实验内容及要求 三、算法思想 实验1 实验2 四、源程序及注释 …大家好今天分享的是数据结构的相关知识大家可以在评论区进行互动答疑哦~加油 目录 提要实验题目 一、实验目的 二、实验内容及要求 三、算法思想 实验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值的合法范围是1iL.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得到新的单链线性表LcLc的元素也按值非递减排列。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 select0-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; } 五、实验结果 实验1结果 实验2结果  今日分享暂时到此为止啦为不断努力的自己鼓鼓掌吧。今日文案分享心平能愈三千疾。