数据结构-线性表_顺序表
roseying 2019-12-09
进入大学一年了，今日终于有勇气写写随笔并展示出来了。
如有不足之处，请大家指正。
今日我想写的就是我对数据结构-线性表_顺序表的理解。
不BB了，进入正题!!!!!
数据结构中的逻辑结构分为线性结构和非线性结构，而线性表就属于线性结构。
线性结构是 n 个数据元素的有序（次序）集合，它有下列几个特征：
- 集合中必存在唯一的一个 "第一个元素"；
- 集合中必存在唯一的一个 "最后的元素"；
- 除最后元素之外，其它数据元素均有唯一的 "后继"；
- 除第一元素之外，其它数据元素均有唯一的 "前驱"。
根据存储方式不同，线性表可以分为顺序表和链表：
- 数据元素在内存中集中存储，采用顺序表示结构，简称 “顺序存储”；（类似于数组）
- 数据元素在内存中分散存储，采用链式表示结构，简称 “链式存储”。（类似于C语言中的单链表）
枯燥的文字，读来索然无味，上张图看看。。。
一般线性表包含下列基本操作：
- 初始化
- 销毁
- 重置为空表
- 判断是否为空
- 获取长度
- 根据位置获取对应元素
- 查找元素
- 获取指定元素的前驱和后继元素
- 插入元素
- 删除元素
- 遍历元素
接下来就用线性表来实现这些基本操作。
首先，我们需要定义一个线性表。
用宏INIT_SIZE定义线性表的初始长度，当存储空间不足时，用INCREMENT_SIZE来定义空间增量
#define INIT_SIZE 10 //初始化表长
#define INCREMENT_SIZE 5 //分配增
接下来定义结构体来作为存储结构，储存类型由Elemtype指定，这我就将其设为int类型
指针elem表示第一个元素存储位置，length表示当前储存元素个数，size表示表长
typedef int Elemtype;
/*
* 存储结构
*/
typedef struct
{
Elemtype *elem; //存储空间基址
int length; //当前长度
int size; //当前分配的表长大小
}SqList;
TRUE和FALSE两个宏表示判断结果是否为真，返回TRUE则为真，返回FALSE则为假。
OK 和 ERROR 两个宏是定义函数的执行结果，返回 OK 说明操作成功，返回 ERROR 说明函数执行失败。
Status 定义后，函数的返回值就不必写为 int，而是写成更容易让人理解程序含义的 Status。
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;
基本定义结束，就开始具体的来实现这些功能函数吧》》》》》》
初始化
使用 malloc 函数申请一个初始大小 INIT_SIZE 的线性表，如果未申请成功则返回NULL
/*
* 初始化一个空的线性表
*/
Status InitList(SqList *L)
{
L->elem = (Elemtype *) malloc(INIT_SIZE * sizeof(Elemtype));
if (!L->elem)
{
return ERROR; }
L->length = 0;
L->size = INIT_SIZE;
return OK;
}
销毁
直接将储存空间释放掉，结构体其他两项置为0。
/*
* 销毁线性表
*/
Status DestroyList(SqList *L)
{
free(L->elem);
L->length = 0;
L->size = 0;
return OK;
}
重置为空表
将length置为0，则表示没有储存元素。
/*
* 清空线性表
*/
Status ClearList(SqList* L)
{
L->length = 0;
return OK;
}
判断是否为空
若length为0则无元素为空
/*
* 判断线性表是否为空
*/
Status isEmpty(const SqList L)
{
if (0 == L.length) //为空则length为0
{
return TRUE;
}
else
{
return FALSE;
}
}
获取长度
length即代表长度
/*
* 获取长度
*/
Status getLength(const SqList L)
{
return L.length;
}
根据位置获取对应元素
先判断查询位置是否在序列范围内，如果在，则直接取值
/*
* 根据位置获取元素
*/
Status GetElem(const SqList L, int i, Elemtype* e)
{
if (i < 1 || i > L.length) //输入位置在序列外界
{
return ERROR;
}
*e = L.elem[i - 1];
return OK;
}
查找元素
先封装一个函数判断两元素是否相等，再遍历比较，如果找到则直接返回位置退出循环，如果完全循环也没找到，则返回ERROR
（其实封装与不封装也没多大差别）
/*
* 比较两个元素是否相等
*/
Status compare(Elemtype e1, Elemtype e2)
{
if (e1 == e2)
{
return 0;
}
else if (e1 < e2)
{
return -1;
}
else
{
return 1;
}
}
/*
* 查找元素
*/
Status FindElem(const SqList L, Elemtype e)
{
int i;
for (i = 0; i < L.length; i++)
{
if (!(*compare)(L.elem[i], e))
{
return i + 1;
}
}
if (i >= L.length)
{
return ERROR;
}
}
获取指定元素的前驱和后继元素
与查询大致一样，只是第一个元素无前驱，最后一个元素无后继，循环时加入判断即可
/*
* 查找前驱元素
*/
Status PreElem(const SqList L, Elemtype cur_e, Elemtype* pre_e)
{
int i;
for (i = 0; i < L.length; i++)
{
if (cur_e == L.elem[i])
{
if (i != 0) //若是第一个则无前驱
{
*pre_e = L.elem[i - 1];
}
else
{
return ERROR;
}
}
}
if (i >= L.length) //完全遍历也没找到
{
return ERROR;
}
}
/*
* 查找后继元素
*/
Status NextElem(const SqList L, Elemtype cur_e, Elemtype* next_e)
{
int i;
for (i = 0; i < L.length; i++)
{
if (cur_e == L.elem[i])
{
if (i < L.length - 1) //若是最后一个则无后驱
{
*next_e = L.elem[i + 1];
return OK;
}
else
{
return ERROR;
}
}
}
if (i >= L.length) //完全遍历也没找到
{
return ERROR;
}
}
插入元素
先判断插入位置是否在1-length+1范围内，再判断当前空间是否已满，是否需要扩容
如果是最后一个位置插入则直接插入，否则设定两个指针，第一个指针指向需要插入位置，第二个位置指向末尾，不断将元素向后移动，最后插入并记录当前长度。
/*
* 插入元素
*/
Status InsertElem(SqList* L, int i, Elemtype e)
{
Elemtype* nuw;
if (i < 1 || i > L->length + 1) //只能在序列区域及后一个插入
{
return ERROR;
}
if (L->length >= L->size) //判断当前空间是否已满
{
nuw = (Elemtype*)realloc(L->elem, (L->size + INCREMENT_SIZE) * sizeof(Elemtype)); //追加空间
if (!nuw) //追加成功为不为NIULL
{
return ERROR;
}
L->elem = nuw;
L->size += INCREMENT_SIZE;
}
if (i - 1 == L->length) {
L->elem[L->length] = e;
}
else {
Elemtype* p = &L->elem[i - 1];
Elemtype* q = &L->elem[L->length - 1];
for (; q >= p; q--)
{
*(q + 1) = *(q);
}
*p = e;
}
++L->length;
return OK;
}
删除元素
先判断想要删除元素，是否在序列范围内，如果在则记录值，再将后面元素依次向前移动
/*
* 删除元素并返回其值
*/
Status DeleteElem(SqList* L, int i, Elemtype* e)
{
if (i < 1 || i > L->length) //不在范围之内
{
return ERROR;
}
Elemtype* p = &L->elem[i - 1];
*e = *p;
for (++p; p < &L->elem[L->length]; p++)
{
*(p - 1) = *(p);
}
--L->length;
return OK;
}
遍历元素
不断循环遍历元素。
* 访问元素
*/
void visit(Elemtype e)
{
cout << e << " ";
}
* 遍历线性表
*/
Status TraverseList(const SqList L)
{
int i;
for (i = 0; i < L.length; i++)
{
visit(L.elem[i]);
}
return OK;
}
最后直接上代码，整体感受一下
#include<iostream>
#include<cstdlib>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INIT_SIZE 10 //初始化表长
#define INCREMENT_SIZE 5 //分配增量
typedef int Status;
typedef int Elemtype;
/*
* 存储结构
*/
typedef struct
{
Elemtype* elem; //存储空间基址
int length; //当前长度
int size; //当前分配的表长大小
}SqList;
/*
* 初始化一个空的线性表
*/
Status InitList(SqList* L)
{
L->elem = (Elemtype*)malloc(INIT_SIZE * sizeof(Elemtype)); //分配空间
if (!L->elem) //分配成功不为空
{
return ERROR;
}
L->length = 0;
L->size = INIT_SIZE;
return OK;
}
/*
* 销毁线性表
*/
Status DestroyList(SqList* L)
{
free(L->elem); //c语言释放空间
L->length = 0;
L->size = 0;
return OK;
}
/*
* 清空线性表
*/
Status ClearList(SqList* L)
{
L->length = 0;
return OK;
}
/*
* 判断线性表是否为空
*/
Status isEmpty(const SqList L)
{
if (0 == L.length) //为空则length为0
{
return TRUE;
}
else
{
return FALSE;
}
}
/*
* 获取长度
*/
Status getLength(const SqList L)
{
return L.length;
}
/*
* 根据位置获取元素
*/
Status GetElem(const SqList L, int i, Elemtype* e)
{
if (i < 1 || i > L.length) //输入位置在序列外界
{
return ERROR;
}
*e = L.elem[i - 1];
return OK;
}
/*
* 比较两个元素是否相等
*/
Status compare(Elemtype e1, Elemtype e2)
{
if (e1 == e2)
{
return 0;
}
else if (e1 < e2)
{
return -1;
}
else
{
return 1;
}
}
/*
* 查找元素
*/
Status FindElem(const SqList L, Elemtype e)
{
int i;
for (i = 0; i < L.length; i++)
{
if (!(*compare)(L.elem[i], e))
{
return i + 1;
}
}
if (i >= L.length)
{
return ERROR;
}
}
/*
* 查找前驱元素
*/
Status PreElem(const SqList L, Elemtype cur_e, Elemtype* pre_e)
{
int i;
for (i = 0; i < L.length; i++)
{
if (cur_e == L.elem[i])
{
if (i != 0) //若是第一个则无前驱
{
*pre_e = L.elem[i - 1];
}
else
{
return ERROR;
}
}
}
if (i >= L.length) //完全遍历也没找到
{
return ERROR;
}
}
/*
* 查找后继元素
*/
Status NextElem(const SqList L, Elemtype cur_e, Elemtype* next_e)
{
int i;
for (i = 0; i < L.length; i++)
{
if (cur_e == L.elem[i])
{
if (i < L.length - 1) //若是最后一个则无后驱
{
*next_e = L.elem[i + 1];
return OK;
}
else
{
return ERROR;
}
}
}
if (i >= L.length) //完全遍历也没找到
{
return ERROR;
}
}
/*
* 插入元素
*/
Status InsertElem(SqList* L, int i, Elemtype e)
{
Elemtype* nuw;
if (i < 1 || i > L->length + 1) //只能在序列区域及后一个插入
{
return ERROR;
}
if (L->length >= L->size) //判断当前空间是否已满
{
nuw = (Elemtype*)realloc(L->elem, (L->size + INCREMENT_SIZE) * sizeof(Elemtype)); //追加空间
if (!nuw) //追加成功为不为NIULL
{
return ERROR;
}
L->elem = nuw;
L->size += INCREMENT_SIZE;
}
if (i - 1 == L->length) {
L->elem[L->length] = e;
}
else {
Elemtype* p = &L->elem[i - 1];
Elemtype* q = &L->elem[L->length - 1];
for (; q >= p; q--)
{
*(q + 1) = *(q);
}
*p = e;
}
++L->length;
return OK;
}
/*
* 删除元素并返回其值
*/
Status DeleteElem(SqList* L, int i, Elemtype* e)
{
if (i < 1 || i > L->length) //不在范围之内
{
return ERROR;
}
Elemtype* p = &L->elem[i - 1];
*e = *p;
for (++p; p < &L->elem[L->length]; p++)
{
*(p - 1) = *(p);
}
--L->length;
return OK;
}
/*
* 访问元素
*/
void visit(Elemtype e)
{
cout << e << " ";
}
/*
* 遍历线性表
*/
Status TraverseList(const SqList L)
{
int i;
for (i = 0; i < L.length; i++)
{
visit(L.elem[i]);
}
return OK;
}
/*
* 主函数测试
*/
int main()
{
SqList L;
if (InitList(&L))
{
Elemtype e;
cout << "init_success" << endl;
int i;
for (i = 0; i < 10; i++)
{
InsertElem(&L, i + 1, i);
}
TraverseList(L/*, visit*/);
cout << "length is " << getLength(L) << endl;
if (GetElem(L, 1, &e)) {
cout << "The first element is " << e << endl;
}
else
{
cout << "element is not exist" << endl;
}
if (isEmpty(L))
{
cout << "list is empty" << endl;
}
else
{
cout << "list is not empty" << endl;
}
cout << "The 5 at " << FindElem(L, 5) << endl;
PreElem(L, 6, &e);
cout << "The 6‘s previous element is " << e << endl;
NextElem(L, 6, &e);
cout << "The 6‘s next element is " << e << endl;
DeleteElem(&L, 1, &e);
cout << "delete first element is " << e << endl;
cout << "list:";
TraverseList(L);
if (DestroyList(&L))
{
cout << endl << "destroy_success" << endl;
}
}
}今日分享到此结束，感觉及其之好，期待下一次。。。fighting!!!!
