究内容

上一篇文章中对数据结构中用于评判算法的两个标准即时间复杂度、空间复杂度进行简单的介绍及解释。

本篇文章会对什么是数据结构数据结构的基本概念进行简单的介绍。

着重介绍线性表和线性表的顺序实现。

1.1

对于第一个步骤也可以分为分析问题、提取操作对象、找出操作对象之间的关系、用数学语言进行表述这四步。

对于提取操作对象和找出操作对象之间的关系这两步就是数据结构研究的主要内容

1.2

数据结构是相互之间一种或多种特定关系的数据元素的集合。

或者说数据结构是带“结构”的数据元素的集合结构“就是指数据元素之间存在的关系。

对于数据结构包含了逻辑结构和存储结构两个层次。

(注本文只是对数据类型进行简单的介绍所以对于下面逻辑结构和存储结构只给出概念与分类其中包含的具体内容将会在后续的文章中进行介绍

1.2.1

数据对象在计算机中的存储表示称为数据的存储结构也成为物理结构。

数据元素在计算机中有两种基本的存储结构分别是顺序存储结构和链式存储结构

线性表

从字母表中可以看出看出线性表的一些性质例如虽然线性表中的数据并不相同但是同一线性表中的元素必定具有相同的特性即属于同一数据对象。

线性表在逻辑上是线性结构也就说是连续的一条直线。

但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。

2.2

在对一元多项式进行运算之前首先要知道如何在计算机表示一元多项式。

表示一元多项式便是线性表的一个应用。

通过观察一元多项式可以发现一元多项式的系数下标与的指数相同。

因此可以用线性表来存储一元多项式中各项系数即

此时假设还有一个一元多项式运算与这两个一元多项式的和便可以通过上面的思想用线性表来表示各项系数之和即

给定一个稀疏多项式

对于稀疏多项式如果再采用上面存储多项式中各项系数的方法则需要开辟个空间但是上面的多项式一共只有个非零元素所以采用上面介绍的存储方法会造成存储空间的极大浪费。

对于稀疏多项式的存储方法应该存储每一项的系数和指数。

如果把稀疏多项式改写成一元多项式的形式即

由于本文主要是通过例子来介绍线性表所以对于稀疏多项式的运算文章不展开介绍只给出运算方法及大体的运算规则

假设由两个稀疏多项式、。

对两式进行相加时需要先创建一个新的数组假设为C,在运算时遵从以下规则

分别从头遍历并且比较两个稀疏多项式对于相同的项则两项系数相加若系数之和不为则在数组C中记录相加项的系数,对于不同的项则先将较小的项添加到C中。

3.1

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。

这种表示也称作线性表的顺序存储结构或顺序映像。

特点是逻辑上相邻的元素其物理此些许也是相邻的并且在顺序表中任一元素都可以随机存取。

即

3.2

顺序表可以分为两种分别是静态顺序表、动态顺序表对于静态顺序表其代码表示为

#define

对于静态顺序表有一个极大的缺陷便是内存大小使用不够灵活。

比如上面给出的代码如果需要存储的数据的个数只有几个则会造成极大的内存空间浪费如果需要存储的数据的个数大于100则超出了数组的最大存储范围。

所以为了解决上述问题在创建顺序表时一般创建对于内存使用更加灵活的动态顺序表代码如下

typedef

使用动态顺序表后对于内存空间的使用便灵活很多例如编写一个内存空间检查函数每次向顺序表中添加数据元素时先通过内存空间检查函数进行检查当内存空间不够用时可以通过动态内存管理函数对已有的内存空间进行增容。

void

上面的代码只是给了初始化函数的大体框架在实际使用中并不会把顺序表中的三项内容全都初始化为而是在初始化时开辟一定的空间。

例如在初始化时给予字节大小的空间

void

(SLDataType*)malloc(sizeof(SLDataType)*4);if

(ps-a

其中的是动态内存管理函数的一种对于动态内存管理函数的使用可以参考下面给出的文章链接中的内容C语言——动态内存管理_爱写代码的粉毛护理的博客-CSDN博客

对于动态顺序表的销毁直接使用函数对动态开辟的空间进行释放即可。

代码如下

void

。

表示顺序表中的数组的空间已经被占满如果还需要进行尾插操作则需要对数组的空间进行扩容。

因为为了避免上面的情况发生应该在每次进行尾插操作之前都对顺序表进行一次检查如果,则对数组的空间进行扩容对于扩容空间的大小一般扩为原来空间的倍代码如下

void

对于理解用于扩容的代码需要将内存空间和的概念分清只是代表了已经开辟的内存空间的个数不会反应内存空间的大小因此在上面用于扩容的代码中只是表示将内存空间的数量扩大到倍想到达到对内存空间的大小扩容到倍需要再乘上存储的数据的类型即

注对于用于扩容的函数也可以在下面给出的文章中进行了解C语言——动态内存管理_爱写代码的粉毛护理的博客-CSDN博客

如果已经掌握了对动态内存管理函数的初步使用会发现尾插的代码中再对内存空间进行扩容后并没有用函数去释放内存空间。

这是因为函数的返回值的特殊性质。

这个性质同样也可以在上面给出的文章链接中进行了解在本文中会进行简要的解释

对于原地扩容如果对内存进行扩容时后面有足够多的内存空间可以达到对已有内存空间进行扩容的目的则函数返回值返回已有空间的首地址。

对于异地扩容如果对内存进行扩容时后面没有足够多的内存空间可以达到对已有内存空间进行扩容的目的则函数会寻找一个新的空间这个空间的地址是随机的并且返回值返回这个新空间的首地址。

这两个性质可以由下面的代码进行演示

int

所以函数对于扩容时不同情况的处理很灵活不需要在扩容后用函数释放内存空间。

为了测试尾插的功能是否正常封装一个函数插入这几个数字

void

在执行尾插操作时说到每次插入前需要检查以下数组的内存空间是否足够。

在头插中同样需要对内存空间进行检查所以为了方便操作不如将尾插中用于检查数组内存空间的代码封装成一个函数。

void

对于头插只需要将已有的元素全部向后移动一位再把想要插入的元素插入到数组的首个位置。

此时因为插入了一个元素所以顺序表中的1例如头插一个数字可以用图表示为

原数组

头删的过程与头插相反进行头插的操作时需要把元素整体向后移动且移动的顺序是从后向前对于头删则是需要从前向后一次覆盖前面的数据。

void

5);SLPopFront(s3);printf(头删);SLPrint(s3);

结果如下

对随机位置添加数据的操作与头插的操作流程相似。

基本可以分为以下几步

4.将

1)){printf(坐标非法);exit(-1);}size_t

end

(SLDataType*)malloc(sizeof(SLDataType)*4);if

(ps-a

{SLCheckCapacity(ps);ps-a[ps-size]

x;ps-size;

1)){printf(坐标非法);exit(-1);}size_t

end

5);SLPopFront(s3);printf(头删);SLPrint(s3);

}void

{test1();test2();test3();test4();test5();return