目录
写在前面
课程采用教材《数据结构(C语言版)》严蔚敏，吴伟民，清华大学出版社。
本系列博文用于自我学习总结和期末复习使用，同时也希望能够帮助到有需要的同学。如果有知识性的错误，麻烦评论指出。
抽象数据类型（ADT）
ADT定义
抽象数据类型定义的格式：
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：
基本操作名（参数表）
初始条件：<初始条件描述>
操作结果：<操作结果描述>
基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。
ADT表示和实现
需要载入一些函数库，预定义常量和类型，数据结构的表示（存储结构）用类型定义（typedef）描述，基本操作的算法采用函数描述，赋值语句，选择语句，循环语句，结束语句，输入输出语句，注释，基本函数，逻辑运算。
特别说明函数描述的形式：
函数类型 函数名（函数参数表）{
// 算法说明
语句序列
} // 函数名
三元组Triplet的定义与实现
定义ADT
ADT Triplet{
数据对象：D = {e1,e2,e3 | e1,e2,e3∈ElemSet（定义了关系运算的某个集合）}
数据关系：R1={<e1,e2>,<e2,e3>}（包含三个元素的三元组，可用数组表示）
基本操作：
InitTriplet(&T,v1,v2,v3)
操作结果：构造了三元组T，元素e1,e2,e3分别被赋以v1,v2,v3的值。
DestroyTriplet(&T)
操作结果：三元组T被销毁。
Get(T,i,&e)
初始条件：三元组T已存在，1≤i≤3。
操作结果：用e返回T的第i元的值。
Put(&T,i,e)
初始条件：三元组T已存在，1≤i≤3。
操作结果：改变T的第i元的值为e。
IsAscending(T)
初始条件：三元组T已存在。
操作结果：如果T的3个元素按升序排列则返回1，否则返回0。
IsDescending(T)
初始条件：三元组T已存在。
操作结果：如果T的3个元素按降序排列，则返回1，否则返回0。
Max(T,&e)
初始条件：三元组T已存在。
操作结果：用e返回T的3个元素中最大值。
Min(T,&e)
初始条件：三元组T已存在。
操作结果：用e返回T的3个元素中最小值。
}ADT Triplet
今后定义ADT每行起始不再增加缩进和空格，请读者自行脑补。Ψ(￣∀￣)Ψ
实现三元组Triplet
用到的函数库、头文件和命名空间
-
#include <iostream>
-
using
namespace
std;
-
#include <stdio.h>
-
#include <malloc.h>
函数执行结果状态代码
-
//函数结果状态代码
-
#define TRUE 1
-
#define FALSE 0
-
#define OK 1
-
#define ERROR 0
-
#define INFEASIBLE -1
-
#define OVERFLOW -2
-
//Status是函数的类型，其值是函数结果状况代码
-
typedef
int Status;
-
typedef
int ElemType;
//将ElemType定义为int类型
采用的存储结构
-
//-----采用动态分配的顺序存储结构-----
-
typedef ElemType* Triplet;
//由IniTriplet函数分配3个元素存储空间
基本操作的函数原型说明
-
//-----基本操作的函数原型说明-----
-
Status IniTriplet(Triplet& T, ElemType v1, ElemType v2, ElemType v3);
-
// 操作结果：构造了三元组T，元素e1,e2,e3分别被赋以v1,v2,v3的值。
-
Status DestoryTriplet(Triplet& T);
-
// 操作结果：三元组T被销毁。
-
Status Get(Triplet& T, int i, ElemType& e);
-
// 初始条件：三元组T已存在，1≤i≤3。
-
// 操作结果：用e返回T的第i元的值。
-
Status Put(Triplet& T, int i, ElemType e);
-
// 初始条件：三元组T已存在，1≤i≤3。
-
// 操作结果：改变T的第i元的值为e。
-
Status IsAscending(Triplet T);
-
// 初始条件：三元组T已存在。
-
// 操作结果：如果T的3个元素按升序排列，则返回1，否则返回0。
-
Status IsDescending(Triplet T);
-
// 初始条件：三元组T已存在。
-
// 操作结果：如果T的3个元素按降序排列，则返回1，否则返回0。
-
Status Max(Triplet T, ElemType& e);
-
// 初始条件：三元组T已存在。
-
// 操作结果：用e返回T的3个元素中最大值。
-
Status Min(Triplet T, ElemType& e);
-
// 初始条件：三元组T已存在。
-
// 操作结果：用e返回T的3个元素中最小值。
-
void PrintT(Triplet T);
-
// 初始条件：三元组T已存在。
-
// 操作结果：输出三元组T中的元素。
基本操作的实现
-
//-----基本操作的实现-----
-
Status IniTriplet(Triplet& T, ElemType v1, ElemType v2, ElemType v3){
-
// 构造三元组T,依次置T的3个元素初值为v1,v2,v3。
-
T = (ElemType*)
malloc(
3 *
sizeof(ElemType));
// 分配3个元素的存储空间
-
if (!T)
exit(OVERFLOW);
// 分配存储空间失败
-
T[
0] = v1; T[
1] = v2; T[
2] = v3;
-
return OK;
-
}
// IniTriplet
-
Status DestoryTriplet(Triplet& T){
-
// 销毁三元组T。
-
free(T);
-
T =
NULL;
-
return OK;
-
}
// DestoryTriplet
-
Status Get(Triplet& T, int i, ElemType& e){
-
// 1≤i≤3,用e返回T的第i元的值。
-
if ((i <
1 || i>
3) || T ==
NULL)
return INFEASIBLE;
-
e = T[i -
1];
-
return OK;
-
}
// Get
-
Status Put(Triplet& T, int i, ElemType e){
-
// 1≤i≤3,置T的第i元的值为e。
-
if ((i <
1 || i>
3) || T ==
NULL)
return INFEASIBLE;
-
T[i -
1] = e;
-
return OK;
-
}
// Put
-
Status IsAscending(Triplet T){
-
// 如果T的3个元素按升序排列，则返回1，否则返回0。
-
if (T ==
NULL)
return INFEASIBLE;
-
return (T[
0] <= T[
1] && T[
1] <= T[
2]);
-
}
// IsAscending
-
Status IsDescending(Triplet T) {
-
// 如果T的3个元素按降序排列，则返回1，否则返回0。
-
if (T ==
NULL)
return INFEASIBLE;
-
return (T[
0] >= T[
1] && T[
1] >= T[
2]);
-
}
// IsDescending
-
Status Max(Triplet T, ElemType& e){
-
// 用e返回指向T的最大元素的值。
-
if (T ==
NULL)
return INFEASIBLE;
-
e = (T[
0] >= T[
1]) ? (T[
0] >= T[
2] ? T[
2] : T[
1]) : (T[
1] >= T[
2] ? T[
1] : T[
2]);
-
return OK;
-
}
// Max
-
Status Min(Triplet T, ElemType& e) {
-
// 用e返回指向T的最小元素的值。
-
if (T ==
NULL)
return INFEASIBLE;
-
e = (T[
0] <= T[
1]) ? (T[
0] <= T[
2] ? T[
0] : T[
2]) : (T[
1] <= T[
2] ? T[
1] : T[
2]);
-
return OK;
-
}
// Min
-
void PrintT(Triplet T){
-
// 顺序输出三元组T中的元素。
-
if (T !=
NULL)
cout <<
"T中元素有：" << T[
0] <<
" " << T[
1] <<
" " << T[
2] <<
endl;
-
else
cout <<
"三元组不存在！\n";
-
}
// PrintT
编写主函数
-
int main()
-
{
-
Triplet T;
-
int e;
-
Status flag;
// 状态标志
-
// 构造三元组T,并赋值
-
flag = IniTriplet(T,
90,
95,
100);
-
PrintT(T);
-
// 返回T的第2元的值
-
flag = Get(T,
2, e);
-
if (flag >
0)
cout <<
"T中第2个元素为：" << e <<
endl;
-
else
cout <<
"ErrorType:" << flag <<
endl;
-
// 置T的第3元的值为80
-
flag = Put(T,
3,
80);
-
if(flag >
0) PrintT(T);
-
else
cout <<
"ErrorType:" << flag <<
endl;
-
// 判断T的3个元素是否按升序排列，是则返回1，否则返回0。
-
flag = IsAscending(T);
-
if (flag >
0)
cout <<
"T中字符是升序。\n";
-
else
if (IsDescending(T) >
0)
// 判断T的3个元素是否按降序排列，是则返回1，否则返回0。
-
cout <<
"T中字符是降序。\n";
-
else
if (flag <
0)
-
cout <<
"ErrorType:" << flag <<
endl;
-
else
cout <<
"T中字符无序。\n";
-
// 获取T的最大元素的值。
-
flag = Max(T, e);
-
if (flag >
0)
cout <<
"T中最大的元素为：" << e <<
endl;
-
else
cout <<
"ErrorType:" << flag <<
endl;
-
// 获取T的最小元素的值。
-
flag = Min(T, e);
-
if (flag >
0)
cout <<
"T中最小的元素为：" << e <<
endl;
-
else
cout <<
"ErrorType:" << flag <<
endl;
-
// 销毁三元组T
-
DestoryTriplet(T);
-
PrintT(T);
// 验证三元组已销毁
-
return
0;
-
}
测试结果
顺序表List（创建，销毁，重置，插入，删除）
顺序表List定义
1、线性结构特点
线性结构的特点是：在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继。
2、线性表的类型定义
线性表是最常用的且最简单的一种数据结构，它的长度可根据需要增长或缩短，对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等。
本次实验中抽象数据类型线性表的定义如下：
ADT List{
数据对象：D={ai| ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：R1={<ai-1,ai>| ai-1,ai ∈D,i=1,2,…,n }
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L。
DestroyList(&L)
初始条件：线性表L已存在。
操作结果：销毁线性表L。
ClearList(&L)
初始条件：线性表L已存在。
操作结果：将L重置为空表。
ListInsert(&L,i,e)
初始条件：线性表L已存在，1≤i≤ListLength(L)+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
ListDelete(&L,i,&e)
初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。
操作结果：删除L第i个数据元素，并用e返回其值，L的长度减1。
PrintList(L)
初始条件：线性表L已存在。
操作结果：输出线性表信息。
}ADT List
3、线性表的顺序表示和实现
顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
顺序存储的线性表的特点：（1）线性表的逻辑顺序与物理顺序一致；（2）数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
这里采用数组来描述数据结构中的顺序存储结构，并采用malloc函数申请空间，来实现顺序表的长度可变。
顺序表List实现
-
//1、用到的库函数、头文件和命名空间
-
#include <iostream>
-
using
namespace
std;
-
#include <stdio.h>
-
#include <malloc.h>
-
//2、函数结果状态代码
-
#define TRUE 1
-
#define FALSE 0
-
#define OK 1
-
#define ERROR 0
-
#define INFEASIBLE -1
-
#define OVERFLOW -2
-
//Status是函数的类型，其值是函数结果状况代码
-
typedef
int Status;
-
typedef
int ElemType;
//将ElemType定义为int类型
-
//3、采用的存储结构
-
//-----线性表的动态分配顺序存储结构-----
-
#define LIST_INIT_SIZE 100// 线性表存储空间的初始分配量
-
#define LISTINCREMENT 10// 线性表存储空间的分配增量
-
typedef
struct {
-
ElemType* elem;
// 存储空间基址
-
int length;
// 当前长度
-
int listsize;
// 当前分配的存储容量（以sizeof（ElemType）为单位）
-
}SqList;
-
//4、基本操作的函数原型说明及实现
-
//-----基本操作的函数原型说明-----
-
Status InitList(SqList& L);
-
// 操作结果：构造一个空的线性表L。
-
Status DestoryList(SqList& L);
-
// 初始条件：线性表L已存在。
-
// 操作结果：销毁线性表L。
-
Status ListInsert(SqList& L, int i, ElemType e);
-
// 初始条件：线性表L已存在，1≤i≤ListLength（L)+1。
-
// 操作结果：在线性表L中第i个位置之前插入新的元素e。
-
Status ListDelete(SqList& L, int i, ElemType& e);
-
// 初始条件：线性表L已存在且非空，1≤i≤ListLength（L)。
-
// 操作结果：在顺序线性表中删除第i个元素，并用e返回其值
-
void PrintList(SqList L);
-
// 初始条件：线性表L已存在。
-
// 操作结果：输出线性表信息。
-
Status ClearList(SqList& L);
-
// 初始条件：线性表L已存在。
-
// 操作结果：将L重置为空表。
-
Status ListEmpty(SqList L);
-
// 初始条件：线性表L已存在。
-
// 操作结果：若L为空表，则返回TURE，否则返回FALSE。
-
-
Status InitList(SqList& L) {
-
// 构造一个空的线性表L。
-
L.elem = (ElemType*)
malloc(LIST_INIT_SIZE *
sizeof(ElemType));
-
if (!L.elem)
exit(OVERFLOW);
// 存储分配失败
-
L.length =
0;
// 空表长度为0
-
L.listsize = LIST_INIT_SIZE;
// 初始存储容量
-
return OK;
-
}
// IntiList
-
Status DestoryList(SqList& L) {
-
// 销毁线性表L。
-
if (!L.elem)
return INFEASIBLE;
// 判断elem是否已空
-
free(L.elem);
// 销毁线性表
-
L.elem =
NULL;
// 指针指空
-
return OK;
-
}
-
Status ListInsert(SqList& L, int i, ElemType e) {
-
// 在顺序线性表L中第i个位置之前插入新的元素e。
-
// i的合法值为1≤i≤ListLength（L)+1。
-
if (i<
1 || i>L.length+
1 || L.elem ==
NULL)
return ERROR;
// 参数合法
-
if (L.length == L.listsize)
// 当前存储空间已满，增加分配
-
{
-
L.listsize += LISTINCREMENT;
// 增加存储容量
-
ElemType* elem_tmp;
// 临时存放原空间元素
-
elem_tmp = (ElemType*)
malloc(
sizeof(ElemType) * L.listsize);
-
if (!elem_tmp)
exit(OVERFLOW);
// 存储空间分配失败
-
for (
int j =
0; j < L.length; j++)
// 向扩容后的空间复制原空间元素
-
elem_tmp[j] = L.elem[j];
-
free(L.elem);
// 释放原空间
-
L.elem = elem_tmp;
// 完成扩容
-
}
-
for (
int j = L.length; j >= i
-1 ; j--)
// 插入位置之后的元素右移
-
L.elem[j] = L.elem[j -
1];
-
L.elem[i -
1] = e;
// 插入e
-
L.length++;
// 表长加1
-
return OK;
-
}
// ListInsert
-
Status ListDelete(SqList& L, int i, ElemType& e) {
-
// 在顺序线性表中删除第i个元素，并用e返回其值
-
// i的合法值为1≤i≤ListLength（L)
-
if (i<
1 || i>L.length || L.elem ==
NULL || L.length ==
0)
return ERROR;
// 不合法情况
-
e = L.elem[i -
1];
// 被删除元素赋给e
-
for (
int j = i
-1; j < L.length
-1; j++)
// 被删除元素之后的元素左移
-
L.elem[j] = L.elem[j +
1];
-
L.length--;
// 表长减1
-
return OK;
-
}
// ListDelet
-
void PrintList(SqList L) {
-
// 输出线性表信息
-
if (!L.elem)
exit(INFEASIBLE);
// 判断elem是否已空
-
cout <<
"线性表元素有：";
-
for (
int i =
0; i < L.length; i++)
-
cout << L.elem[i] <<
" ";
-
cout <<
endl <<
"线性表长度：" << L.length
-
<<
endl <<
"线性表容量：" << L.listsize <<
endl <<
endl;
-
}
// PrintList
-
Status ClearList(SqList& L) {
-
// 重置线性表L。
-
if (!L.elem)
return INFEASIBLE;
// 判断elem是否已空
-
free(L.elem);
// 释放指针
-
if (InitList(L))
return OK;
-
}
-
Status ListEmpty(SqList L) {
-
if (!L.elem)
return INFEASIBLE;
// 判断elem是否已空
-
if (L.length ==
0)
return TRUE;
-
return FALSE;
-
}
-
//5、主函数
-
int main()
-
{
-
// 初始化测试
-
SqList L;
-
InitList(L);
-
PrintList(L);
-
// 插入测试
-
for (
int i =
1; i <=
100; i++)
// i=1时测试表头插入，
-
ListInsert(L, i , i );
// i＞1时测试表尾连续插入LIST_INIT_SIZE-1个元素
-
PrintList(L);
-
ListInsert(L,
101,
101);
// 测试扩容
-
PrintList(L);
-
ListInsert(L,
89,
0);
// 测试中间位置插入
-
PrintList(L);
-
// 删除测试
-
ElemType e;
-
ListDelete(L,
89, e);
// 测试中间位置删除
-
PrintList(L);
-
cout <<
"删除的元素为：" << e <<
endl <<
endl;
-
ListDelete(L,
1, e);
// 测试表头位置删除
-
PrintList(L);
-
cout <<
"删除的元素为：" << e <<
endl <<
endl;
-
ListDelete(L, L.length, e);
// 测试表尾位置删除
-
PrintList(L);
-
cout <<
"删除的元素为：" << e <<
endl <<
endl;
-
// 重置测试
-
ClearList(L);
-
PrintList(L);
-
// 销毁测试
-
DestoryList(L);
-
PrintList(L);
// 表销毁会以INFEASIBLE值退出
-
return
0;
-
}
测试结果
实验总结
本次实验实现了线性表的顺序存储结构，以及顺序表的创建，插入，删除，重置，销毁功能。
创建时，采用malloc函数申请LIST_INIT_SIZE * sizeof(ElemType)个空间，并使L.length = 0，L.listsize = LIST_INIT_SIZE，完成顺序表L的初始化。销毁时，释放L.elem并使其指空，再对顺序表L操作时，L.elem为空，不可操作。重置时，如果L.elem不空，就再调用一次初始化函数InitList(L)，重置顺序表L。
插入时，满足初始条件后，先判断顺序表长度L.length与容量L.listsize是否相等，一般情况下，不会出现长度大于容量的情况，故判断是否等于即可。如果等于，则表明当前容量已满，需要再申请LISTINCREMENT个空间。具体操作是：
（1）先扩充容量，L.listsize += LISTINCREMENT
（2）用临时指针elem_tmp指向比原来多LISTINCREMENT个空间的首地址
（3）将原空间的数据元素复制到新申请的空间中，这里采用for循环，一次一个赋值。
（4）释放原空间，让L.elem指向存有原数据元素的新空间。
之后，先将插入位置以后的元素都往后移一位，把插入数据元素放入插入位置，最后L.length++。
删除时，将删除位置的元素先通过e传出，再把删除位置之后的元素依次往前移一位，执行删除操作前的最后一位元素和已占用的多余空间可以不用处理。如果需要处理，可以采用插入时申请新空间一样的方法，不过新空间要比原来的空间少LISTINCREMENT。最后L.length--。
最后采用for循环逐个输出顺序表中的数据元素及当前元素个数和存储容量。
通过本次实验，可以明显感受到对顺序表执行插入和删除操作有诸多的不便，占用额外的空间，插入删除操作不考虑改变存储空间时，时间复杂度为O（n）。但是采用顺序存储结构，可以与逻辑结构更好地对应，便于理解。
转载：https://blog.csdn.net/sbdsj_0111/article/details/106410461