网站首页广告图片伸缩代码又关闭,保健品做哪个网站好,深圳市建设工程交易服,从化定制型网站建设本文的所有代码均由C编写 如果你已经看完这篇杂谈#xff0c;可以前往下一篇→数据结构杂谈#xff08;三#xff09;_尘鱼好美的小屋-CSDN博客 文章目录2 顺序表2.1 线性表的类型定义2.2 类C语言有关操作补充2.2.1 ElemType的解释2.2.2 数组定义2.2.3 建立链表可能会用到的… 本文的所有代码均由C编写 如果你已经看完这篇杂谈可以前往下一篇→数据结构杂谈三_尘鱼好美的小屋-CSDN博客 文章目录2 顺序表2.1 线性表的类型定义2.2 类C语言有关操作补充2.2.1 ElemType的解释2.2.2 数组定义2.2.3 建立链表可能会用到的函数2.2.4 参数传递问题2.2.4.1 地址传递2.2.4.2 值传递2.2.4.3 数组名为参2.3 顺序表2.3.1 顺序表的定义2.3.1.1 顺序存储方式2.3.1.2 静态分配方法2.3.1.3 数据长度和线性表长度区别2.3.1.4 动态分配方法2.3.1.5 顺序表的特点2.3.2 顺序表的基本操作2.3.2.1 初始化2.3.2.2 顺序表的插入2.3.2.3 顺序表的删除2.3.2.4 顺序表的按位查找2.3.2.5 顺序表的按值查找2 顺序表
下面开始我们要学习一种最常用也是最简单也是最不简单的逻辑结构也就是线性表。 为了更直观地体现线性表我们举几个生活中的例子。 第一个例子是食堂排队打饭这种排队通常都是一个接着一个第一个同学打完就轮到下一个同学打饭如果队伍中间一个人有事走了那么其他人都会前进一步而如果前面有人仗着有朋友而插队那么所有人都得后退一步这种情况在线性表中的体现即为顺序表。 第二个例子是医院挂号这种挂号一般是按顺序挂号挂完号的人就去等待区候着而不用在那里排队到了你的号数就去看病与前一种方式不同它不会因为你站的位置来决定你的看病的先后顺序而是看你手中的挂号牌这种情况在线性表中的体现即为单链表。 2.1 线性表的类型定义
接下来我们要讲的东西是针对线性表即单链表和顺序表都属于此范畴。
线性表是具有相同数据类型的n个数据元素的有限序列。其中n为表长当n0的时候线性表是一个空表。若用L命名线性表即L(a1,a2,a3….,an)L (a_1,a_2,a_3….,a_n)L(a1,a2,a3….,an)。 关于上面的L表示法其中有几个术语是需要我们知道的。 a2相对于a1来说排在后面所以我们叫做直接后继。a1相对于a2来说排在前面所以我们叫他直接前驱。很显然倒数第二个元素只有一个直接后继第二个元素只有一个直接前驱。在非空表里每个数据元素都有自己对应的位置我们叫做位序。比如在线性表中a1排在第一位我们说a1排在线性表中的第一位序。 位序和索引要明确线性表中第一个元素即为第一位序且为第0个元素。 2.2 类C语言有关操作补充
在考研必备教材《数据结构C语言版》严蔚敏版中为了方便同学的学习采用了类C语言即C语言C混用不在意语法意在让同学理解内在逻辑而不过分追究编译语法。
2.2.1 ElemType的解释
我们给出一个线性表中顺序表的定义这里我们只是简单了解下看不懂没关系。
typedf struct{ElemType data[];int length;
}SqList;//顺序表类型这时候我们会觉得很奇怪从来没有看过ElemType这种类型。实际上我们从英文上可以看出这里的意思是元素类型即数据元素类型比如说你要用什么数组如果你的数组打算放int那么你可以把ElemType的位置换成int。
2.2.2 数组定义
typedf struct{ElemType data[MaxSize];int length;
}SqList;//顺序表类型从上面的代码来看很明显使用数组来表示顺序表用长度来记录表长。但是它确有另外一种表示方法。
typedf struct{ElemType *data;int length;
}SqList;//顺序表类型实际上如果是data[MaxSize]那么我们会发现一旦MaxSize确定下来了那么我们的数组长度也就确定下来了。
但是如果我们用的是* data那么data是一个指针变量我们可以通过new函数来申请一片内存的地址然后把地址赋给data数组这样数组的长度由数组元素的字节长度和数组的最大容纳量来确定了。这实际上就是静态数组分配和动态数组分配的区别后面会讲到。
2.2.3 建立链表可能会用到的函数
在C语言中我们常用的是 malloc函数用于开辟m字节长度的地址空间并且返回这段空间的首地址。 sizeof函数计算变量x的长度 free§函数释放指针p所指变量的存储空间即彻底删除一个变量。 需要注意的是如果要用到以上的函数需要加载头文件stdlib.h 而在C中我们用的是
new函数delete函数sizeof函数
2.2.4 参数传递问题
2.2.4.1 地址传递
地址传递实际上就是传地址给函数函数通过指针的解引用互换对应地址中的值但是这里有个问题地址不能互换只有地址上的值能换这是需要注意的一点。
对于C语言来说通常喜欢用指针来修改传入的参数并返回对应的结果而对于C来说用引用会更方便一些。 在C中引用相当于一个别名比如说int a 1此时你用引用可以给1再起一个别名比如起个别名叫b那么对b中的1修改为2后a的1也会编程2这样相当于是用两个名字去操纵同一个数据。 引用类型作形参在内存中并没有产生实参的副本他直接对实参操作而一般变量作参数形参与实参就占用不同的存储单元所以形参变量的值是实参变量的副本。因此当参数传递的数据量较大时用引用比用一般变量传递参数的时间和空间效率都好。 指针参数虽然能达到和使用引用类型的效果但在被调函数中需要重复使用“指针变量名”的形式进行计算这很任意产生错误且程序的阅读性较差另一方面在主调函数的调用点处必须用变量的地址作为实参。 2.2.4.2 值传递
值传递是把数值传进函数这样的做法在函数里面的确能够实现应有的功能但是当函数运行结束时变量不会做任何改变因为变量传给函数的是数值变量所在的地址的数值仍未发生变化。
2.2.4.3 数组名为参
我们都知道数组的名字实际上代表着数组中首元素的地址所以对形参数组所做的任何改变都会反映到实参数组中。
我们都知道数组的名字实际上代表着数组中首元素的地址所以对形参数组所做的任何改变都会反映到实参数组中。
#include iostream
using namespace std;
void change(char a[])
{a[0] a;
}int main()
{char arr[] { 1,2,3,4 };cout 改变前的arr[0]: arr[0]endl;change(arr);cout 改变后的arr[0]: arr[0] endl;system(pause);return 0;}结果
改变前的arr[0]:1
改变后的arr[0]:a2.3 顺序表
说那么多线性表我们接下来来看看线性表的两种物理结构其中之一顺序存储结构。
2.3.1 顺序表的定义
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
其示意图如下 这种表示一般被我们叫做顺序存储结构或者叫做顺序映像。拥有这种结构的线性表我们叫顺序表。
2.3.1.1 顺序存储方式
线性表的顺序存储结构说白了就是在内存中随便找块地通过占位的形式把一定内存空间给占了然后把相同数据类型的数据元素依次存放到这块空地中。这里我们想到这有点类似于一维数组吧一维数组也是这个定义。 这里实际上隐含着另外一个意思既然线性表的数据元素都是相同数据类型那么我们知道一个数据元素占几个字节数据元素的大小那么线性表连续就必定有LOC(ai1)LOC(ai)lLOC(a_ {i1}) LOC(a_i)lLOC(ai1)LOC(ai)l这里的loc指的是内存地址即location这种情况其中lll代表他们一个数据元素的大小。比如一维数组a[1],a[2]。如果是整型数组那么就有如下结果 至于lll所代表的数据元素的大小我们从何而知呢就是利用我们在2.2.3讲到的sizeof函数。 2.3.1.2 静态分配方法
在2.2.2时我们曾经提到两种顺序表的实现方法即动态分配和静态分配在下面我们会依次讲解这两种方法。
我们前面说过可以用一维数组来表示线性表但是这里要注意一点线性表长可变而数组长度是不可动态定义。这时候我们用一个变量(length)来表示顺序表的长度属性。所以单纯用一个数组还不行还要加一个长度属性。
那如何用C语言去定义顺序表呢线性表每个节点中都有数据可是没有说是什么数据类型可以是基本数据类型也可以是复合数据类型可以是结构化数据类型也可以是半结构化数据类型所以我们通常利用结构体来创建一个线性表其中线性表包含数据元素和长度。所以如果写成代码如下
#define MAXSIZE 100 //定义数组的最大长度
typedef struct{ElemType data [MAXSIZE]; //用静态的数组存放数据元素int length; //顺序表当前长度
}SeqList; 在以上的定义中我们可以发现一件事。如果我们过早的指定一维数组中的MAXSIZE那么我们很难担保后面能够提供足够多的数据元素。 就拿占位的例子来说一个人占了九个位置给舍友这只是一个估计是死的、理想状态的而实际上九个人并不是那么好学里面有一些人没来放鸽子还有一种情况就是九个人有几个还带了女朋友单身狗留下了泪水那占的位置不够坐的情况也有可能发生。 在上一段话中提到线性表数据元素不足和数据元素存满的情况数据元素不足只是浪费了内存如果是存满这时候就可以放弃治疗了。
2.3.1.3 数据长度和线性表长度区别
对于上面的讲解可能还有些人会有疑惑length和MAXSIZE的区别不是很清楚在这一小节我们详细阐述一下。
静态分配如下所示
#define MAXSIZE 100
typedef struct{ElemType data [MAXSIZE];int length;
}SeqList;我们在这里发现定义顺序表需要三个属性
存储空间的起始位置数组data线性表的最大存储容量数组长度MaxSize线性表的当前长度length
也就是说你确定了数组长度是吧数组开辟空间了是吧最后数组上面选一段作为线性表有点套娃如图所示 也就是说如果你数组开辟的空间不够多就会导致顺序表用的空间不够多也就会导致顺序表的数据元素填不进去。
所以综上所述我们得出如下结论
数组长度是指存放线性表的存储空间的长度存储分配后这个值是不变的。线性表的长度是线性表中数据元素的个数随着线性表的插入与删除这个值是在变换的。
2.3.1.4 动态分配方法
讲完了静态分配方法我们来说说动态分配方法。
由于线性表强调元素在逻辑上紧密相邻所以我们最开始想到用数组存储。但是普通数组有着无法克服的容量限制在不知道输入有多少的情况下很难确定出一个合适的容量。对此一个较好的解决方案就是使用动态分配即动态数组。
使用动态数组的方法是用new申请一块拥有指定初始容量的内存这块内存用作存储线性表元素当录入的内容不断增加以至于超出了初始容量时就用new扩展内存容量这样就做到了既无浪费内存也可以让线性表容量随输入的增加而自适应大小。
在这里我们先给出动态分配的定义至于怎么扩充我们后面会讲。动态分配方法如下
#include iostream
using namespace std;
#define InitSize 10 //默认的最大长度//顺序表结构体定义
typedef struct
{//指示动态分配数组的指针int* data;//顺序表的最大容量int Maxsize;//顺序表的当前长度int length;
}SeqList;//初始化顺序表
void InitList(SeqList L)
{L.data new int[InitSize * sizeof(int)];L.length 0;L.Maxsize InitSize;
}如果想要增加动态数组的长度可以编写如下函数
void IncreaseSize(SeqList L, int len)
{int* p L.data;L.data new int[(L.Maxsize len) * sizeof(int)];for (int i 0; i L.length; i){L.data[i] p[i]; //将数据复制到新区域}L.Maxsize L.Maxsize len; //顺序表最大长度增加lendelete(p); //释放老数组的内存空间
}原来老数组是在内存中开辟了一块内存空间而我们在增加动态数组的长度时实际上是在内存的其他地方开了一块更大的空间然后把老数组上面的数组复制过去新数组。
既然如此我们就应该把定义一个新指针p把老数组的指针移交给p后把data指针指向新数组。此时p指老data指新通过循环把p中的每一个元素移交给data即可移交完成后要记得把顺序表的最大容量也修改一下即老顺序表的最大容量加上扩充容量。 经过上面的代码讲解我们可以知道一件事就是由于要把数据从老数组复制到新数组实际上时间开销是非常大的这也对应了我们2.3.1.3讲解的一般来说在一些书上是不会讲这个动态分配的事的只有在考研中才会涉及到这个知识点。 2.3.1.5 顺序表的特点
结果上面的讲解我们可以总结顺序表具有如下特点
随机访问即可以在O(1)时间内找到第i个元素存储密度高每个节点只存储数据元素拓展容量不方便即便采用动态分配的方式实现拓展长度的时间复杂度也比较高插入、删除操作不方便需要移动大量元素
2.3.2 顺序表的基本操作
实际上顺序表和单链表的操作基本都是这几个原理。在这里我们先讲顺序表的基本操作。
在这之前我们需要介绍一下操作算法中用到的预定义常量和类型在后面的代码中你经常会看见这些字眼。
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型其值是函数结果状态代码
typedef int Status;
typedef char ElemType;2.3.2.1 初始化
这里的初始化其实包含了两个动作对顺序表的初始化和对数组的初始化。在前面我们知道顺序表是用数组表示的这就意味着数组确定了空间大小后如果顺序表没用满数组中的内存就势必有一些内存有脏数据。所有在使用顺序表之前你需要先把数组内所有元素设为0并且把顺序表长度设为0。
#include iostream
using namespace std;
#define MaxSize 10//定义数组最大长度typedef struct
{int data[MaxSize];int lenght;
}SqList;//初始化
void InitList(SqList L)
{for (int i 0; i MaxSize; i){L.data[i] 0; //将所有数据元素设置为默认初始值0}L.lenght 0; //顺序表初始长度为0
}int main()
{SqList L;InitList(L);for (int i 0; i MaxSize; i)cout L.data[i] endl;return 0;
}实际上上面的操作具有一定的违规因为我们是在用顺序表而不是在用数组所以上面打印的条件应该是iL.length。所以这里我们又可以发现我们只是用顺序表而不用数组的话实际上是不会访问到脏数据的所以初始化一般都是初始化顺序表的长度而不用去初始化数组的值。
然而抛开上面不谈实际上我们访问数据的方式也不够好在测试阶段我们的确可以用这种方式但是实际做题或者其他应用中我们还是得用基本操作去访问数据元素。在下一小节我们就会讲到这个问题。
2.3.2.2 顺序表的插入
插入删除在顺序表中其实很简单你可以想象这么一个场景你们在买火车票有个人想插队到你前面一旦你同意你后面排队的人都得退一步而如果你们在排队有个人有事突然走了那么所有排队的人都可以前进一步。这就是顺序表的插入删除。其中插入的操作有些人俗称加塞示意图如下: ListInsert(L,I,e):插入操作。在表L中的第i个位置上插入指定元素e。 bool ListInsert(SeqList L, int i, int e)
{if (i1 || iL.length 1)//判断i的范围是否有效return false;if (L.length MAXSIZE)//当前存储空间已满不能插入return false;for (int j L.length; j i; j--)L.data[j] L.data[j - 1];L.data[i - 1] e;L.length;return true;
}注意在增加元素的时候一定要检查插入之前是否存满了为此我们在上面的代码合理性判断。 说明检查i的合法性判断。好的算法应该具有“健壮性”。能处理异常情况并且给使用者反馈。 关于插入操作的时间复杂度通常都是直接看最内层循环。 如果考虑最好情况新元素插入到表尾不需要移动元素i n1循环0次最好时间复杂度为O(1) 最坏情况新元素插入到表头需要将原有的n个元素全都向后移动i 1循环n次最坏时间复杂度 为O(n) 平均情况假设新元素插入每个位置的概率都相等即p 1/(n1)i 1循环n次i 2循环n-1次也就是123…n根据等差数列求和公式也就是n(n1)/2 平均循环概率 平均复杂度 np n/2 O(n)
2.3.2.3 顺序表的删除 ListDelete(L,I,e)删除操作。删除表中第i个位置的元素并用e返回删除元素的值。 bool ListDelete(SeqList L, int i, int e)
{if (i1 || iL.length 1)//判断i的范围是否有效return false;e L.data[i - 1];for (int j i; j L.length; j)L.data[j - 1] L.data[j];L.length--;return true;
}说明删除方法有L同理带入L顺序表进去操作后返回最开始先检查i的合理性检查成功后将要删除的值赋给e然后开始把e这个i位置的元素往前移把要删除的元素挤掉然后线性表长度减一返回成功字样。 关于插入操作的时间复杂度就不细说了实际上和插入的时间复杂度一模一样计算方法也大同小异。
2.3.2.4 顺序表的按位查找 GetElem(L, i)按位查找操作获取表L中第i个位置的元素的值。 int GetElem(SeqList L, int i)
{//初始条件顺序线性表L已存在if (L.length 0 || i1 || iL.length)return 0;return L.data[i - 1];
}实际上动态数组也可以用这种方式访问。 2.3.2.5 顺序表的按值查找 LocateElem(L ,e )按值查找操作。在表L中查找具有给定值的元素并返回其所在的位序。 //按值查找
int LocateElem(SeqList L, int e)
{for (int i 0; i L.length; i)if (L.data[i] e)return i 1; //找到值退出循环返回位序return 0; //退出循环说明查找失败
}需要注意的是当我们的顺序表里面的元素不是基本类型而是结构类型的时候按值查找的判定条件就不能再用了。
对于结构体类型的数据元素我们可以采用来判定结构体中每个数据类型是否相等。最好的做法是能做成一个函数来使用。如果是C的话我们还可以对进行重载。
不过幸运的是在考研当中目标学校更侧重的是你对算法的理解而不在代码的细节。所以在手写代码的时候无论是基本数据类型还是结构数据类型都是可以直接使用。
对于按值查找的时间复杂度来说和插入操作一样稍加思考一下就能理解这里就不过多讲述了。
需要提到的是按值查找也有技巧可言并不一定要按照顺序扫描的方式比如二分查找等查找方法都能提高时间效率在后面会有更深层次的讲解。
