高端定制网站建设制作,wordpress 底部按钮,qq安全网页版在线登录,jsp网站开发详解 赵增敏目录
1. 什么是数据结构#xff1a; 1.1 数据结构的研究内容#xff1a;
1.2 数据结构的基本概念#xff1a;
1.2.1 逻辑结构#xff1a; 1.2.2 存储结构#xff1a;
2. 线性表#xff1a;
2.1 线性表的基本定义#xff1a;
2.2 线性表的运用#xff1a;
3 .线性…目录
1. 什么是数据结构 1.1 数据结构的研究内容
1.2 数据结构的基本概念
1.2.1 逻辑结构 1.2.2 存储结构
2. 线性表
2.1 线性表的基本定义
2.2 线性表的运用
3 .线性表的顺序表示及实现顺序表 3.1 顺序表的概念及结构 3.2 顺序表的代码实现
3.2.1 顺序表的创建、初始化及销毁
3.3 顺序表的四个特殊操作头插、头删、尾插、尾删
3.3.1 尾插
3.3.2 尾删
3.3.3 头插
3.3.4 头删 3.4 对顺序表的随机位置进行增删操作
3.4.1 对顺序表的随机位置进行添加数据的操作
3.4.2 对顺序表的随机位置进行删除数据的操作
4. 代码总览
4.1 头文件Seqlist.h:
4.2 函数功能实现文件 Seqlist.c
4.3 测试函数功能文件 test.c: 上一篇文章中对数据结构中用于评判算法的两个标准即时间复杂度、空间复杂度进行简单的介绍及解释。本篇文章会对什么是数据结构数据结构的基本概念进行简单的介绍。着重介绍线性表和线性表的顺序实现。
1. 什么是数据结构 1.1 数据结构的研究内容 计算机主要是被用于进行数值计算这个过程可以分为以下几步
1.从具体问题中抽象出数学模型。
2.设计相应的算法
3.对程序进行测试调试等。
对于第一个步骤也可以分为分析问题、提取操作对象、找出操作对象之间的关系、用数学语言进行表述这四步。对于提取操作对象和找出操作对象之间的关系这两步就是数据结构研究的主要内容
1.2 数据结构的基本概念
首先给出数据结构的定义
数据结构是相互之间一种或多种特定关系的数据元素的集合。或者说数据结构是带“结构”的数据元素的集合结构“就是指数据元素之间存在的关系。对于数据结构包含了逻辑结构和存储结构两个层次。
(注本文只是对数据类型进行简单的介绍所以对于下面逻辑结构和存储结构只给出概念与分类其中包含的具体内容将会在后续的文章中进行介绍
1.2.1 逻辑结构
数据的逻辑结构是指从逻辑关系上描述数据 它与数据的存储无关是独立于计算机的。数据结构的类型如下图所示 1.2.2 存储结构
数据对象在计算机中的存储表示称为数据的存储结构也成为物理结构。数据元素在计算机中有两种基本的存储结构分别是顺序存储结构和链式存储结构 2. 线性表
2.1 线性表的基本定义
对于线性表一个很典型的例子就是26英文字母的字母表 从字母表中可以看出看出线性表的一些性质例如虽然线性表中的数据并不相同但是同一线性表中的元素必定具有相同的特性即属于同一数据对象。线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。
2.2 线性表的运用
对于线性表的运用文章给出两个例子
例1一元多项式的运算 在数学中一个一元多项通常可以写成下面的形式 在对一元多项式进行运算之前首先要知道如何在计算机表示一元多项式。表示一元多项式便是线性表的一个应用。
通过观察一元多项式可以发现一元多项式的系数下标与的指数相同。因此可以用线性表来存储一元多项式中各项系数即 这时对于一元多项式中各项中的指数便隐藏在各项的系数下标中。
此时假设还有一个一元多项式运算与这两个一元多项式的和便可以通过上面的思想用线性表来表示各项系数之和即 例子2稀疏多项式的表示
给定一个稀疏多项式 对于稀疏多项式如果再采用上面存储多项式中各项系数的方法则需要开辟个空间但是上面的多项式一共只有个非零元素所以采用上面介绍的存储方法会造成存储空间的极大浪费。
对于稀疏多项式的存储方法应该存储每一项的系数和指数。如果把稀疏多项式改写成一元多项式的形式即 运用线性表对每一项的系数和指数保存即 由于本文主要是通过例子来介绍线性表所以对于稀疏多项式的运算文章不展开介绍只给出运算方法及大体的运算规则
假设由两个稀疏多项式、。对两式进行相加时需要先创建一个新的数组假设为C,在运算时遵从以下规则
分别从头遍历并且比较两个稀疏多项式对于相同的项则两项系数相加若系数之和不为则在数组C中记录相加项的系数,对于不同的项则先将较小的项添加到C中。 3 .线性表的顺序表示及实现顺序表 3.1 顺序表的概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。这种表示也称作线性表的顺序存储结构或顺序映像。特点是逻辑上相邻的元素其物理此些许也是相邻的并且在顺序表中任一元素都可以随机存取。即 3.2 顺序表的代码实现
3.2.1 顺序表的创建、初始化及销毁
顺序表可以分为两种分别是静态顺序表、动态顺序表对于静态顺序表其代码表示为
#define N 100
typedef int SLDataType;
struct Seqlist
{SLDataType arr[N]; //定长数组int size; //有效数据个数
}Seqlist;
对于静态顺序表有一个极大的缺陷便是内存大小使用不够灵活。比如上面给出的代码如果需要存储的数据的个数只有几个则会造成极大的内存空间浪费如果需要存储的数据的个数大于100则超出了数组的最大存储范围。所以为了解决上述问题在创建顺序表时一般创建对于内存使用更加灵活的动态顺序表代码如下
typedef int SLDataType;typedef struct Seqlist
{SLDataType* a; //动态开辟数组的方式a表示数组首元素地址size_t size; //数组中有效的数据个数size_t capacity; //容量大小
}SL;
使用动态顺序表后对于内存空间的使用便灵活很多例如编写一个内存空间检查函数每次向顺序表中添加数据元素时先通过内存空间检查函数进行检查当内存空间不够用时可以通过动态内存管理函数对已有的内存空间进行增容。
对于顺序表的初始化将顺序表初始化函数命名为,函数内容如下
void SLInit(SL* ps)
{ps-a NULL;ps-size 0;ps-capacity 0;
}
上面的代码只是给了初始化函数的大体框架在实际使用中并不会把顺序表中的三项内容全都初始化为而是在初始化时开辟一定的空间。例如在初始化时给予字节大小的空间
void SLInit(SL* ps)
{ps-a (SLDataType*)malloc(sizeof(SLDataType)*4);if (ps-a NULL){perror(malloc);exit (-1);}ps-size 0;ps-capacity 4;
}
其中的是动态内存管理函数的一种对于动态内存管理函数的使用可以参考下面给出的文章链接中的内容C语言——动态内存管理_爱写代码的粉毛护理的博客-CSDN博客
语句用于判断是否成功的开辟了空间。
对于动态顺序表的销毁直接使用函数对动态开辟的空间进行释放即可。代码如下
void SLDestroy(SL* ps)
{free(ps);ps-a NULL;ps-size ps-capacity 0;
} 3.3 顺序表的四个特殊操作头插、头删、尾插、尾删
3.3.1 尾插
给出一个顺序表其中的数组中存储的元素如图所示 由上面对于顺序表的定义可知
capacity表示顺序表的数组的容量大小
a表示数组后面的数字表示这个数组中存储的元素
size表示数组中存储元素的个数
size-1用来表示数组下标
对上述数组进行尾插操作假设第一次插入数字则 进行尾插后令用来表示数组中存储元素个数的变量
此时再进行一次尾插插入数字则 进行尾插后同样令用来表示数组中存储元素格式的变量; 此时
。表示顺序表中的数组的空间已经被占满如果还需要进行尾插操作则需要对数组的空间进行扩容。因为为了避免上面的情况发生应该在每次进行尾插操作之前都对顺序表进行一次检查如果,则对数组的空间进行扩容对于扩容空间的大小一般扩为原来空间的倍代码如下
void SLPushBack(SL* ps, SLDataType x)
{if (ps-size ps-capacity){SLDataType* tmp (SLDataType*)realloc(ps-a, ps-capacity * 2 * (sizeof(SLDataType)));if(tmp NULL){perror(realloc);}ps-a tmp;ps-capacity ps-capacity * 2;}ps-a[ps-size] x;ps-size;
} 对于上面给出的尾插代码最核心的部分就是对内存空间进行扩容即 SLDataType* tmp (SLDataType*)realloc(ps-a, ps-capacity * 2 * (sizeof(SLDataType)));
对于理解用于扩容的代码需要将内存空间和的概念分清只是代表了已经开辟的内存空间的个数不会反应内存空间的大小因此在上面用于扩容的代码中只是表示将内存空间的数量扩大到倍想到达到对内存空间的大小扩容到倍需要再乘上存储的数据的类型即
注对于用于扩容的函数也可以在下面给出的文章中进行了解C语言——动态内存管理_爱写代码的粉毛护理的博客-CSDN博客
如果已经掌握了对动态内存管理函数的初步使用会发现尾插的代码中再对内存空间进行扩容后并没有用函数去释放内存空间。这是因为函数的返回值的特殊性质。这个性质同样也可以在上面给出的文章链接中进行了解在本文中会进行简要的解释
上面提到的函数的返回值的特殊性质即原地扩容、异地扩容。
对于原地扩容如果对内存进行扩容时后面有足够多的内存空间可以达到对已有内存空间进行扩容的目的则函数返回值返回已有空间的首地址。
对于异地扩容如果对内存进行扩容时后面没有足够多的内存空间可以达到对已有内存空间进行扩容的目的则函数会寻找一个新的空间这个空间的地址是随机的并且返回值返回这个新空间的首地址。这两个性质可以由下面的代码进行演示
int main()
{int* p1 (int*)malloc(12);int* p2 (int*)realloc(p1, 2);printf(%p %p\n,p1, p2);int* p3 (int*)malloc(10);int* p4 (int*)realloc(p3, 200);printf(%p %p,p3, p4);return 0;
}
结果如下 可以验证的地址表示此时是原地扩。 此时地址不同是异地扩。
所以函数对于扩容时不同情况的处理很灵活不需要在扩容后用函数释放内存空间。为了测试尾插的功能是否正常封装一个函数插入这几个数字
void test1()
{SL s1;SLInit(s1);SLPushBack(s1, 1);SLPushBack(s1, 2);SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushBack(s1, 5);SLPushBack(s1, 6);SLPrint(s1);
}
结果如下 3.3.2 尾删
尾删就是从末尾向前删除元素原理比较简单只需要让即可
//尾删
void SLPopBack(SL* ps)
{ps-size--;
}
利用下面的代码测试尾删的功能
void test1()
{SL s1;SLInit(s1);SLPushBack(s1, 1);SLPushBack(s1, 2);SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushBack(s1, 5);SLPushBack(s1, 6);SLPopBack(s1); SLPopBack(s1);SLPrint(s1);
}
结果如下 3.3.3 头插
在执行尾插操作时说到每次插入前需要检查以下数组的内存空间是否足够。在头插中同样需要对内存空间进行检查所以为了方便操作不如将尾插中用于检查数组内存空间的代码封装成一个函数。
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity){SLDataType* tmp (SLDataType*)realloc(ps-a, ps-capacity * 2 * (sizeof(SLDataType)));if (tmp NULL){perror(realloc);}ps-a tmp;ps-capacity ps-capacity * 2;}
}
对于头插只需要将已有的元素全部向后移动一位再把想要插入的元素插入到数组的首个位置。此时因为插入了一个元素所以顺序表中的1例如头插一个数字可以用图表示为
原数组 全部元素向后挪动一位 头插数字 将上述过程用代码表示
void SLPushFront(SL* ps, SLDataType x)
{SLCheckCapacity(ps);int end ps-size - 1;while (end 0){ps-a[end1] ps-a[end];end--;}ps-a[0] x;ps-size;
}
用下列函数对头插功能进行设置
void test2()
{SL s2;SLInit(s2);SLPushBack(s2, 1);SLPushBack(s2, 2);SLPushBack(s2, 3);SLPushBack(s2, 4);SLPushBack(s2, 5);SLPushFront(s2, 6);SLPrint(s2);
}
结果如下 注第一行的是测试尾插的结果头插的结果是第一行 3.3.4 头删
头删的过程与头插相反进行头插的操作时需要把元素整体向后移动且移动的顺序是从后向前对于头删则是需要从前向后一次覆盖前面的数据。
void SLPopFront(SL* ps)
{if (ps-size 0){return;}int start 0;int end ps-size - 1;while (start end){ps-a[start] ps-a[start1];start;}ps-size--;
}
用下面的函数测试头删的功能
void test3()
{SL s3;SLInit(s3);SLPushBack(s3, 1);SLPushBack(s3, 2);SLPushBack(s3, 3);SLPushBack(s3, 4);SLPushBack(s3, 5);SLPopFront(s3);printf(头删);SLPrint(s3);
}
结果如下 3.4 对顺序表的随机位置进行增删操作
3.4.1 对顺序表的随机位置进行添加数据的操作
对随机位置添加数据的操作与头插的操作流程相似。基本可以分为以下几步
1.判断这个位置对于数组下标而言是否合法即
2.将位置以及后面的元素整体后移动一位。
3.将新的元素插入到数组中下标为的位置
4.将
用图来表示上述过程及 将位置以及后续元素向后移动一位 最后向位置为的地方插入元素即可。因为多插入了一个元素最后需要
代码如下
void SLInsert(SL* ps, size_t i, SLDataType x)
{if (i 0 || i (ps-size - 1)){printf(坐标非法);exit(-1);}size_t end ps-size - 1;for (size_t end ps-size - 1; end i-1; end--){ps-a[end 1] ps-a[end];}ps-a[i - 1] x;ps-size;
}
用下面的代码验证随机位置插入功能是否正常
void test4()
{SL s4;SLInit(s4);SLPushBack(s4, 1);SLPushBack(s4, 2);SLPushBack(s4, 3);SLPushBack(s4, 4);SLPushBack(s4, 5);SLInsert(s4, 3, 6);SLPrint(s4);}
结果如下 注结果是最后一行数字所展示的效果 3.4.2 对顺序表的随机位置进行删除数据的操作
对于在顺序表的随机位置删除数据的操作可以分为以下几步
1.检查位置对于数组下标是否合理即
2.将位置后面的元素整体向前移动一位。
3. 因为删除了一个元素所以
将上述过程用图进行表示 将位置后面的元素整体向前移动一位 最后
将上述过程用代码表示
void SLErase(SL* ps, size_t i)
{if (i 0 || (i ps-size - 1)){printf(坐标非法);}size_t start i-1;while (start ps-size - 1){ps-a[start] ps-a[start 1];start;}ps-size--;
}
用下面的函数测试功能
void test5()
{SL s5;SLInit(s5);SLPushBack(s5, 1);SLPushBack(s5, 2);SLPushBack(s5, 3);SLPushBack(s5, 4);SLPushBack(s5, 5);SLErase(s5, 3);SLPrint(s5);}
结果如下 注最后一行的数字对应着测试的功能的结果 4. 代码总览
4.1 头文件Seqlist.h:
#includestdio.h
#includeassert.h
#includestdlib.h//#define N 100
//typedef int SLDataType;
//struct Seqlist
//{
// SLDataType arr[N];
// int size;
//}Seqlist;typedef int SLDataType;
typedef struct Seqlist
{SLDataType* a;size_t size;size_t capacity;
}SL;//用于打印测试
void SLPrint(SL* ps);
//用于初始化顺序表
void SLInit(SL* ps);//用于销毁顺序表
void SLDestroy(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//尾删
void SLPopBack(SL* ps);//检测内存空间
void SLCheckCapacity(SL* ps);//头插
void SLPushFront(SL* ps, SLDataType x);//头删
void SLPopFront(SL* ps);//随机位置插入
void SLInsert(SL* ps,size_t i ,SLDataType x);//随机位置删除
void SLErase(SL* ps, size_t i);4.2 函数功能实现文件 Seqlist.c
#includeSeqlist.h//初始化顺序表
void SLInit(SL* ps)
{ps-a (SLDataType*)malloc(sizeof(SLDataType)*4);if (ps-a NULL){perror(malloc);exit (-1);}ps-size 0;ps-capacity 4;
}//销毁顺序表void SLDestroy(SL* ps)
{free(ps-a);ps-a NULL;ps-size ps-capacity 0;
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{SLCheckCapacity(ps);ps-a[ps-size] x;ps-size;
}//用于打印数据
void SLPrint(SL* ps)
{int i 0;for (i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}//尾删
void SLPopBack(SL* ps)
{ps-size--;
}//检查内存空间
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity){SLDataType* tmp (SLDataType*)realloc(ps-a, ps-capacity * 2 * (sizeof(SLDataType)));if (tmp NULL){perror(realloc);}ps-a tmp;ps-capacity ps-capacity * 2;}
}//头插
void SLPushFront(SL* ps, SLDataType x)
{SLCheckCapacity(ps);int end ps-size - 1;while (end 0){ps-a[end1] ps-a[end];end--;}ps-a[0] x;ps-size;
}//头删
void SLPopFront(SL* ps)
{if (ps-size 0){return;}int start 0;int end ps-size - 1;while (start end){ps-a[start] ps-a[start1];start;}ps-size--;
}//随机位置插入
void SLInsert(SL* ps, size_t i, SLDataType x)
{if (i 0 || i (ps-size - 1)){printf(坐标非法);exit(-1);}size_t end ps-size - 1;for (size_t end ps-size - 1; end i-1; end--){ps-a[end 1] ps-a[end];}ps-a[i - 1] x;ps-size;
}//随机位置删除
void SLErase(SL* ps, size_t i)
{if (i 0 || (i ps-size - 1)){printf(坐标非法);}size_t start i-1;while (start ps-size - 1){ps-a[start] ps-a[start 1];start;}ps-size--;
}
4.3 测试函数功能文件 test.c:
#includeSeqlist.hvoid test1()
{SL s1;SLInit(s1);SLPushBack(s1, 1);SLPushBack(s1, 2);SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushBack(s1, 5);SLPushBack(s1, 6);SLPopBack(s1); SLPopBack(s1);SLPrint(s1);
}void test2()
{SL s2;SLInit(s2);SLPushBack(s2, 1);SLPushBack(s2, 2);SLPushBack(s2, 3);SLPushBack(s2, 4);SLPushBack(s2, 5);SLPushFront(s2, 6);SLPrint(s2);}void test3()
{SL s3;SLInit(s3);SLPushBack(s3, 1);SLPushBack(s3, 2);SLPushBack(s3, 3);SLPushBack(s3, 4);SLPushBack(s3, 5);SLPopFront(s3);printf(头删);SLPrint(s3);
}void test4()
{SL s4;SLInit(s4);SLPushBack(s4, 1);SLPushBack(s4, 2);SLPushBack(s4, 3);SLPushBack(s4, 4);SLPushBack(s4, 5);SLInsert(s4, 3, 6);SLPrint(s4);}
void test5()
{SL s5;SLInit(s5);SLPushBack(s5, 1);SLPushBack(s5, 2);SLPushBack(s5, 3);SLPushBack(s5, 4);SLPushBack(s5, 5);SLErase(s5, 3);SLPrint(s5);}
int main()
{test1();test2();test3();test4();test5();return 0;
}
