线性表的C/C++实现（数据结构 严蔚敏版）

2024-02-03 01:32
文章标签 c++ 实现 数据结构 线性表 严蔚敏版

本文主要是介绍线性表的C/C++实现（数据结构 严蔚敏版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

下面的代码是项目文件：一个头文件、一个源文件、一个测试文件

1、头文件List.h：

#include<iostream>
using namespace std;
#include<malloc.h>/*定义数据的类型，可以通过修改这里的数据类型，来实现不同类型的线性表
下面的数据类型可以更改，const引用是限制被调用的函数，不能修改主程序的数据，但可以查看，达到保护主程序数据安全。
不需要执行修改操作，而只要查看数据的线性表就用const限制 引用 
*/
typedef int Status;
typedef int ElemType;#define LIST_INIT_SIZE 10  //初始化的空间分配容量 
#define LIST_ADD 10		//每次增加的分配空间增量 
#define ok 1
#define error 0
#define flow 0//定义一个线性表结构，结构内有分配空间的基地址，分配空间的总长度，当前使用空间的大小。 
typedef struct{ElemType* elem;   //空间基地址 int length;		//当前已经使用的空间的长度 int listsize;	//当前分配的空间长度 }SqList;//初始化线性表 
Status InitList(SqList& L); //打印线性表
Status Print(SqList L);//销毁线性表 
Status DestroyList(SqList& L);//将线性表清空 
Status ClearList(SqList& L);//判断线性表是否为空 
Status  ListEmpty(const SqList& L);//返回线性表中元素的个数
Status ListLength(const SqList& L);//获取线性表中的第i个元素的值 
Status Get(const SqList& L, int i, ElemType& e); //如果当前元素cur_e不是第一个数据，就pre_e返回它的前一个数据的值，否则返回error 
Status PriorElem(const SqList& L, ElemType cur_e, ElemType& pre_e);//如果当前元素不会最后一个，就用next_e返回它的后一个数值，否则返回error
Status NextElem(const SqList& L, ElemType cur_e, ElemType& next_e);//在第i个位置前插入数据e, 数据长度加一 
Status ListInsert(SqList& L, int i, ElemType e);// 删除i个位置的数据，数据长度减一,并返回数据 
Status ListDelete(SqList& L, int i, ElemType& e);//合并线性表LA和LB，将结果放入LA中 
Status Union(SqList& LA, const SqList& B); //合并线性表
Status MergeList(const SqList& LA, const SqList& LB, SqList& LC); //查询数据的位置 
int LocateElem(const SqList& L, ElemType e);//插入n个数据
Status Insert(SqList& L, int n);

2、源文件List.cpp:

#include "List.h" //这是功能实现源文件，其他程序可以通过头文件包含，使用这里的功能 //初始化线性表 
Status InitList(SqList& L){L.elem = (ElemType* )(malloc( LIST_INIT_SIZE * sizeof(ElemType)));//如果地址分配错误，就返回0 if(!L.elem) exit(error);//将当前长度设置为0，分配长度设置为初始长度 L.length = 0;L.listsize = LIST_INIT_SIZE;return ok;}//销毁线性表 
Status DestroyList(SqList& L){//如果地 if(!L.elem){cout<<"线性表不存在"<<endl;}else{free(L.elem);L.elem = NULL;}return ok;
} //打印线性表
Status Print(SqList L){cout<<"线性表的数据如下："<<endl;if(L.length == 0){cout<<"线性表为空表, 请插入数据后再来打印数据\n\n"<<endl;}for(int i=0; i<L.length; i++){cout<<L.elem[i]<<" ";}cout<<endl;
} //将线性表清空 
Status ClearList(SqList& L){//如果线性表的当前长度不为0，就将数据全部清空，当前长度设置为0 if(L.length != 0){for(int i=0; i<L.length; i++){L.elem[i] = 0;}L.length = 0;}return ok;
}//判断线性表是否为空 
Status  ListEmpty(const SqList& L){if(L.length != 0){//不为空表 return ok;}else{//为空表 return error;}
}//返回线性表中元素的个数
Status ListLength(const SqList& L){return L.length; 
} //获取线性表中的第i个元素的值 
Status Get(const SqList& L, int i, ElemType& e){if(i > L.length || i < 0){cout<<"输入有误，退出"<<endl;return error;}else{e = L.elem[i-1];return ok;}
}//如果当前元素cur_e不是第一个数据，就pre_e返回它的前一个数据的值，否则返回error 
Status PriorElem(const SqList& L, ElemType cur_e, ElemType& pre_e){int flag = LocateElem(L, cur_e);if(flag == -1){cout<<"找不到数据"<<endl; return error;}if(flag == 0){cout<<"数据不存在直接前驱"<<endl; }else{pre_e = L.elem[flag-1];}} //如果 当前元素不会最后一个，就用next_e返回它的后一个数值，否则返回error
Status NextElem(const SqList& L, ElemType cur_e, ElemType& next_e){int flag = LocateElem(L, cur_e);if(flag = -1){cout<<"数据不存在"<<endl; }else if(flag == L.length){cout<<"该数据不存在直接后继"<<endl;}else{next_e = L.elem[flag+1];}
} //在第i个位置前插入数据e, 数据长度加一 
Status ListInsert(SqList& L, int i, ElemType e){if(i<1 || i > L.length+1) {cout<<"输入的位置有问题"<<endl; return error;}if(L.length == L.listsize){//增加LIST_ADD长度的地址空间 L.elem = (ElemType*)(realloc(L.elem, (LIST_ADD) * sizeof(ElemType)));if(!L.elem) exit(flow); //更新分配的长度 L.listsize = L.listsize + LIST_ADD;//取要插入位置的地址 ElemType* q = &(L.elem[i-1]);//如果地址p比插入的地址q大或则等于，就将数据复制到后面一位空间里面，空出地址q的存储空间 for(ElemType* p = &(L.elem[L.length-1]); p>= q; p--){*(p+1) = *p;}	//给地址空间q赋值 *q = e;//当前长度+1 L.length++;}else{//如果分配空间没有使用完，执行下面操作//取要插入位置的地址 ElemType* q = &(L.elem[i-1]);//如果地址p比插入的地址q大或则等于，就将数据复制到后面一位空间里面，空出地址q的存储空间 for(ElemType* p = &(L.elem[L.length-1]); p>= q; p--){*(p+1) = *p;}	//给地址空间q复制 *q = e;//当前长度+1 L.length++;}return ok;} // 删除i个位置的数据，数据长度减一,并返回数据 
Status ListDelete(SqList& L, int i, ElemType& e){if(i > L.length || i<0){cout<<"你删除的数据不存在\n\n"<<endl;return error; }else{ElemType* q = &L.elem[i-1];e = *q;q = &L.elem[L.length-1];for(ElemType* p = &L.elem[i-1]; p<= q; p++){*p = *(p+1);}L.length--;cout<<"删除成功\n\n"<<endl;return ok;} 
} //合并线性表,将LA和LB合并后的结果替换为LA 
Status Union(SqList& LA, const SqList& LB){int LA_length = LA.length;int LB_length = LB.length;ElemType e;for(int i=0; i<= LB_length; i++){//获取LB的第i个位置的数据 Get(LB, i, e);for(int i=0; i<LB_length; i++){//在LA中查询数据e是否存在，不存在就返回i，存在就返回-1 int index = LocateElem(LA,  e);//不为-1就在LA中插入数据 e if(index != -1){ListInsert(LA, ++LA.length, e); }}	} cout<<"线性表合并完成, 查看第一个线性表可以查看合并后的数据"<<endl;return ok;
} //合并有序线性表,并排序，将结果放有序入LC中 
Status MergeList(const SqList& LA, const SqList& LB, SqList& LC){InitList(LC);int i, j, k;i = j = 1;k = 0;ElemType a, b;int la_length = LA.length; int lb_length = LB.length;while((i  <= la_length) && (j <= lb_length)){Get(LA, i, a); Get(LB, j, b);if(a <= b){{ListInsert(LC, ++k, a);i++;}}else{ListInsert(LC, ++k, b);j++;}}while(i <= la_length){Get(LA, i++, a);ListInsert(LC, ++k, a);}while(j <= lb_length){Get(LB, j++, b);ListInsert(LC, ++k, b);}} //查询某个数据e的位置
int LocateElem(const SqList& L, ElemType e){if(L.length == 0){return -1;}for(int i=0; i<L.length; i++){if(L.elem[i] == e){return i+1;}else{return -1;}}} //插入n个数据Status Insert(SqList& L, int n){ElemType e;if(n + L.length > L.listsize){L.elem = (ElemType*)(realloc(L.elem, (LIST_ADD) * sizeof(ElemType)));//如果地址分配失败，就返回错误 if(!L.elem)  return error;L.listsize = L.listsize + LIST_ADD;}cout<<"请输入你要插入的"<<n<<"数据"<<endl;for(int i=L.length; i<n; i++){cin>> L.elem[i];}cout<<"数据插入完成\n\n"<<endl; L.length = L.length + n;return ok;}

3、测试文件test.cpp：

#include <iostream>
#include "List.h"/* run this program using the console pauser or add your own getch, system("pause") or input loop *///测试一个线性表功能 
int main(int argc, char** argv) {SqList L;cout<<"请输入你的操作"<<endl;cout<<"		0-----退出\n"<<endl;cout<<"		1-----初始化线性表\n"<<endl;int n;int i;ElemType e;//初始化线性表 InitList(L);while(1){cout<<"请输入你的操作"<<endl;cin>>n;if(n>1 || n < 0){cout<<"你输入的有问题，请重新输入"<<endl;}else{break;}} if(n == 0){cout<<"你已退出"<<endl;exit(flow);}//进入操纵while(1){switch(n){case 0:	//销毁之后重新进行初始化,并退出 DestroyList(L);cout<<"线性表销毁成功\n\n"<<endl;cout<<"你已退出"<<endl;exit(flow);	case 1://重新初始化线性表 if(L.elem){free(L.elem);cout<<"重新初始化成功，原来数据被清空\n\n"<<endl;}InitList(L); break;case 2://查看线性表所有数据 Print(L); break;case 3://数据插入 cout<<"请输入你要插入的位置和数据\n"<<endl;cin>>i;cin>>e;if(ListInsert(L, i, e)){cout<<"插入成功\n\n"<<endl;} else{cout<<"插入失败\n\n"<<endl;}break;case 4://删除功能 cout<<"请输入你要删除的位置"<<endl;cin>>i;ListDelete(L, i, e);break;case 5://查询数据 cout<<"请输入你要查询的数据"<<endl;cin>>e;i = LocateElem(L, e);if(i != -1){cout<<"你查询的数据是第"<<i<<"个位置\n\n"<<endl;}else{cout<<"你查询的数据不存在\n\n"<<endl; }break;case 6://判断线性表是否为空 if(!ListEmpty(L)){cout<<"线性表为空表\n\n"<<endl;}else{cout<<"线性表不为空\n\n"<<endl;}break;}cout<<"		0-----退出,并销毁线性表\n"<<endl;cout<<"		1-----重新初始化线性表\n"<<endl;cout<<"		2-----打印线性表\n"<<endl;cout<<"		3-----插入数据\n"<<endl;cout<<"		4-----删除某个数据\n"<<endl;cout<<"		5-----查询数据的位置\n"<<endl;cout<<"		6-----判断线性表是否为空\n"<<endl;cout<<"请输入你的操作"<<endl;//控制操作输入 while(1){//输入操作方式 cin>>n;cout<<endl;if(n>6 || n < 0){cout<<"你输入的有问题，请重新输入"<<endl;}else{break;}} }return 0;
}


这篇关于线性表的C/C++实现（数据结构 严蔚敏版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/672608。

相关文章

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2