本文主要是介绍线性表的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++实现（数据结构 严蔚敏版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
