2.1线性表的定义和特点
线性结构：
- 若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
- 可表示为： (a1 , a2 , …, ai-1, ai, ai+1,…, an)
- 包括线性表、栈、队列、字符串和数组，其中，最典型、最常用的是线性表。
线性结构的特点：
在数据元素的非空有限集中
- 存在唯一的一个被称作“第一个”的数据元素；
- 存在唯一的一个被称作“最后一个”的数据元素；
- 除第一个外，集合中的每个数据元素均只有一个直接前驱；
- 除最后一个之外，集合中每个数据元素均只有一个直接后继。
线性表：
- n个具有相同特性的数据元素的有限序列
- eg：26 个英文字母组成的英文表，( A, B, C, D, … , Z)，数据元素都是字母，元素间关系是线性
2.2 线性表的顺序表示和实现
用一组地址连续的存储单元依次存储线性表中的数据元素。
代码用到文件： 刚发现上传的文件被人下载需要vip，百度网盘也挺麻烦，直接把内容放上去了，用的话可以cv到一个txt里！
ISBN 书名 定价
9787302257646 程序设计基础 25
9787302219972 单片机技术及应用 32
9787302203513 编译原理 46
9787811234923 汇编语言程序设计教程 21
9787512100831 计算机操作系统 17
9787302265436 计算机导论实验指导 18
9787302180630 实用数据结构 29
9787302225065 数据结构（C语言版） 38
9787302171676 C#面向对象程序设计 39
9787302250692 C语言程序设计 42
9787302150664 数据库原理 35
9787302260806 Java编程与实践 56
9787302252887 Java程序设计与应用教程 39
9787302198505 嵌入式操作系统及编程 25
9787302169666 软件测试 24
9787811231557 Eclipse基础与应用 35
代码如下：
/*
* 线性表的顺序表示和实现
* 以图书管理项目为例
*
* @Author: longbow_nice
* @CreatedTime: 2022/7/8
*/
#include<iostream>
#include<string>
#include<iomanip>
#include<fstream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2 //含义为运算过程中出现了上溢，即运算结果超出了运算变量所能存储的范围。
#define MAXSIZE 100 //顺序表最大长度
typedef int Status; //函数名返回值类型
typedef int ElemType; //数据类型
struct Book {
string id; //IBSN
string name; //书名
double price; //价格
};
typedef struct {
Book* elem; //存储空间机制
int length; //表长
}SqList;
//初始化顺序表L
Status InitList(SqList& L) {
L.elem = new Book[MAXSIZE];
if (!L.elem) {
exit(OVERFLOW);
}
L.length = 0;
return OK;
}
//销毁顺序表L
void DestroyList(SqList& L) {
if (L.elem) {
delete []L.elem;
}
L.length = 0;
L.elem = NULL;
cout << "销毁成功！" << endl;
}
//清空顺序表L
void ClearList(SqList &L) {
L.length = 0;
cout << "清空成功" << endl;
}
//求顺序表L的长度
int GetLength(SqList L) {
return L.length;
}
//判断顺序表L是否为空
bool ListEmpty(SqList L) {
return L.length == 0;
}
//取值
//获取顺序表L中的第i个元素内容
Status GetElem(SqList L, int i, Book &e) {
if (i<1 || i>L.length) {
return ERROR;
}
e = L.elem[i - 1];
return OK;
}
//检索（查找）
//查找价格为price的图书位置
Status LocateElem(SqList L, double price) {
for (int i = 0; i < L.length; i++) {
if (L.elem[i].price == price) {
return i + 1;
}
}
return 0;
}
//插入
//在第j个位置之前插入新的元素e
Status ListInsert(SqList& L, int j, Book e) {
if (j<1 || j>L.length+1) {
return ERROR;
}
if (L.length == MAXSIZE) {
return OVERFLOW;
}
for (int i = L.length-1; i >= j-1; i--) {
L.elem[i+1] = L.elem[i];
}
L.elem[j-1] = e;
L.length++;
return OK;
}
//删除
//删除顺序表L中第i个数据元素
Status ListDelete(SqList& L, int j) {
if (j<1 || j>L.length) {
return ERROR;
}
for (int i = j-1; i < L.length; i++) {
L.elem[i] = L.elem[i + 1];
}
L.length--;
return OK;
}
//读取文件建立顺序表
Status ListCreate(SqList &L) {
int i = 0;
string head1, head2, head3;
fstream file;
file.open("book.txt");
if (!file) {
cout << "打开文件失败！" << endl;
exit(ERROR);
}
file >> head1 >> head2 >> head3;
while (!file.eof()) {
file >> L.elem[i].id >> L.elem[i].name >> L.elem[i].price;
i++;
}
cout << "输入 book.txt 信息完毕" << endl;
L.length = i;
file.close();
return OK;
}
//输出顺序表
void ListPrint(SqList L) {
for (int i = 0; i < L.length; i++) {
cout << left << setw(15) << L.elem[i].id << "\t";
cout << left << setw(20) << L.elem[i].name << "\t";
cout << left << setw(10) << L.elem[i].price << endl;
}
}
int main() {
cout << "1. 初始化顺序表" << endl;
cout << "2. 读取文件建立顺序表" << endl;
cout << "3. 销毁顺序表" << endl;
cout << "4. 清空顺序表" << endl;
cout << "5. 顺序表长度" << endl;
cout << "6. 判断顺序表是否为空" << endl;
cout << "7. 获取元素" << endl;
cout << "8. 查找元素" << endl;
cout << "9. 插入一个元素" << endl;
cout << "10. 删除某一个元素 " << endl;
cout << "11. 输出顺序表" << endl;
cout << "0. 退出" << endl;
SqList L;
int temp,location =0,choice=-1;
Book e;
while (choice != 0) {
cout <<endl<< "请选择： ";
cin >> choice;
switch (choice) {
case 1: ;
if(InitList(L)){
cout << "顺序表初始化成功！" << endl;
}
else {
cout << "顺序表初始化！" << endl;
}
break;
case 2:
ListCreate(L);
break;
case 3:
DestroyList(L);
break;
case 4:
ClearList(L);
break;
case 5:
//在case里面定义变量，需要用括号括起来{}。
//否则length初始化操作由 case 标签跳过
{
int length = GetLength(L);
cout <<"顺序表长度："<< length << endl;
}
break;
case 6:
if (ListEmpty(L)) {
cout << "顺序表为空！" << endl;
}else {
cout << "顺序表不为空！" << endl;
}
break;
case 7:
cout << "请输入一个位置用来取值：";
cin >> location;
temp=GetElem(L, location, e);
if (temp != 0) {
cout << "获取成功，此图书信息：" << endl;
cout << left << setw(15) << L.elem[location-1].id << "\t";
cout << left << setw(20) << L.elem[location-1].name << "\t";
cout << left << setw(10) << L.elem[location-1].price << endl;
}
else {
cout << "查找失败！位置超出范围" << endl;
}
break;
case 8:
cout << "请输入所要查找价格：";
double price;
cin >> price;
location =LocateElem(L, price);
if (location != 0) {
cout << "查找成功，此图书信息：" << endl;
cout << left << setw(15) << L.elem[location-1].id << "\t";
cout << left << setw(20) << L.elem[location-1].name << "\t";
cout << left << setw(10) << L.elem[location-1].price << endl;
}else {
cout << "查找失败！没有这个价格对应的书籍" << endl;
}
break;
case 9:
cout << "插入位置：";
cin >> location;
cout << "插入图书id、名字、价格: ";
cin >> e.id >> e.name >> e.price;
temp = ListInsert(L, location, e);
if (temp == OK) {
cout << "插入成功！" << endl;
}
else if (temp == ERROR) {
cout << "插入位置超出范围！" << endl;
}
else {
cout<<"顺序表存储空间已满！";
}
break;
case 10:
cout << "删除图书的位置：";
cin >> location;
temp=ListDelete(L, location);
if (temp != 0) {
cout << "删除成功！" << endl;
}
else {
cout << "删除位置超出范围！";
}
break;
case 11:
ListPrint(L);
break;
}
}
return 0;
}
运行结果：
2.3，遇到问题
已在 Test2.1.exe 中执行断点指令(__debugbreak()语句或类似调用)。
2.4，插入和删除操作的性能分析
在顺序存储表示的线性表中插入或删除一个数据元素，平均约需移动表中一半元素。
2.5. 线性表顺序表示的优缺点
优点
- 可以随机存取表中任一元素;
- 无需为表示表中元素之间的逻辑关系而增加额外存储空间；
缺点
- 在插入、删除某一元素时，需要移动大量元素；
- 表的容量难以确定,浪费存储空间
版权声明：本文为longbow_nice原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。