实验一：实现顺序表各种基本运算的算法
一、实验目的与要求
目的:
领会顺序表存储结构和掌握顺序表中各种基本运算算法设计。
内容:
编写一个程序sqlist.cpp,实现顺序表的各种基本运算和整体建表算法(假设顺序表的元素类型ElemType为char),并在此基础上设计一个主程序,完成如下功能:
(1)初始化顺序表L。
(2)依次插入a、b、c、d、e元素。
(3)输出顺序表L。
(4)输出顺序表L长度
(5)判断顺序表工是否为空。
(6)输出顺序表工的第3个元素
(7)输出元素a的位置。
(8)在第4个元素位置上插入f元素
(9)输出顺序表工。
(10)删除顺序表L的第3个元素。
(11)输出顺序表工。
(12)释放顺序表工。
二、实验类型
C++算法编程
三、实验原理及说明
线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中，线性表的顺序存储结构简称为顺序表(sequentiallist)。
在C++语言中，数组可以满足顺序表的存储结构，所以我们使用C++语言进行编程，实现线性表的顺序存储结构
四、实验主要仪器设备和材料
| 序 号 | 名 称 | 主要用途 |
| 1 | 电脑 | 打开软件 |
| 2 | Dev c++ | 编写代码，运行代码 |
五、实验内容和步骤
根据《教程》中2.2节的算法得到sqlist.cpp程序,其中包含如下函数。
InitList(SqList *&L):初始化顺序表L。
DestroyList(SqList *L):释放顺序表。
ListEmpty(SqList *L):判断顺序表L是否为空表
ListLength(SqList *L):返回顺序表的元素个数。
DispList(SqList *L):输出顺序表L。
。GetElem(SqList *L,inti,ElemType&e):获取顺序表L中第i个元素LocateElem(SqList *L,ElemTypee):在顺序表L中查找元素e。
ListInsert(SqList *&L,inti,ElemTypee):在顺序表L中第i个位置上插入元素e。
ListDelete(SqList *&L,inti,ElemType &e):从顺序表L中删除第i个元素。
对应的程序代码如下(设计思路详见代码中的注释):
步骤：
创建一个sqList.cpp文件，将函数写入文件中
创建一个main.cpp文件，编写主函数，对函数进行验证
实验内容：
1.编写sqList.cpp
#include <iostream>
using namespace std;
#define MaxSize 50 //线性表最大长度
typedef char ElemType; //定义类型
typedef struct { //定义数据结构
ElemType data[MaxSize]; //存元素
int length; //长度
} SqList;
//整体建立顺序表
void CreateListR(SqList *&L, ElemType a[],int n) {
L = new SqList; //为L分配空间
for (int i = 0; i < n; i ++) {
L->data[i] = a[i];
}
L->length = n;
}
//初始化顺序表
void InitList(SqList *&L) {
L = new SqList;
L->length = 0;
}
//释放顺序表
void DestroyList(SqList *&L) {
delete L;
}
//判断顺序表是否为空
bool ListEmpty(SqList *L) {
return (L->length == 0);
}
//返回顺序表L的元素个数
int ListLength(SqList *L) {
return (L->length);
}
//输出顺序表L
void DispList(SqList *L) {
for (int i= 0; i < L->length; i++) {
cout << L->data[i] << " ";
}
cout << endl;
}
//求线性表中的第i个元素值
bool GetElem(SqList *L, int i , ElemType &e) {
if (i < 1 || i > L->length)
return false;
e = L->data[i - 1];
return true;
}
//在顺序表L中查找元素e
int LocateElem(SqList *L, ElemType e) {
int i = 0;
while (i < L->length && L->data[i] != e) {
i++;
}
if (i >= L->length) {
return 0;
}
else return i + 1;
}
//在顺序表L中第i个位置上插入元素e.
bool ListInsert(SqList *&L, int i, ElemType e) {
int j;
if (i < 1 || i > L->length + 1) {
return false;
}
i--;
for (j = L->length; j > i; j--) {
L->data[j] = L->data[j - 1];
}
L->data[i] = e;
L->length++;
return true;
}
//从顺序表L中删除第i个元素
bool ListDelete(SqList *&L, int i, ElemType &e) {
int j;
if (i < 1 || i > L->length) {
return false;
}
for (int j = i - 1; j < L->length; j++) {
L->data[j] = L->data[j + 1];
}
L->length--;
return true;
}2.编写main.cpp
#include "sqList.cpp"
int main() {
SqList *L;
ElemType e;
cout << "顺序表的基本运算如下：" << endl;
cout << " (1)初始化顺序表L" << endl;
InitList(L);
cout << " (2)依次插入a,b,c,d,e元素" << endl;
ListInsert(L, 1, 'a');
ListInsert(L, 2, 'b');
ListInsert(L, 3, 'c');
ListInsert(L, 4, 'd');
ListInsert(L, 5, 'e');
cout << " (3)输出顺序表L:";
DispList(L);
cout << " (4)顺序表L长度：" << ListLength(L) << endl;
cout << " (5)顺序表L为" << (ListEmpty(L) ? "空":"非空")<< endl;
GetElem(L, 3, e);
cout << " (6)顺序表L的第三个元素：" << e <<endl;
cout << " (7)元素a的位置：" << LocateElem(L,'a') << endl;
cout << " (8)在第四个元素位置上插入f元素" << endl;
ListInsert(L, 4, 'f');
cout << " (9)输出顺序表L:";
DispList(L);
cout << " (10)删除L的第三个元素" << endl;
ListDelete(L, 3, e);
cout << " (11)输出顺序表L:" ;
DispList(L);
cout << " (12)释放顺序表L" << endl;
DestroyList(L);
return 1;
}运行结果：
六、实验小结与分析
此次实验通过实践的方法，实现了使用编程语言对顺序表的实现，顺序表直接将线性表的逻辑结构映射到存储结构上，既便于理解，又容易实现。使我了解了线性表的顺序存储结构在C++中如何实现的，使我对线性表的顺序存储结构更加了解。
