初写--数据结构-->顺序表__01

时间：2023-03-18 07:11:14

对于什么是顺序表，我觉得还是简短做一下说明比较好！

顺训表:> 首先，它是一种结构，是用一段物理地址连续的存储单元依次有顺序的存储数据元素的线性结构！！

一般，也是绝大多数情况并普遍常用的背景下，数组便是发挥了不可替代的作用！！即是在数组上存储，也是在数组上对数据进行增删查改！！

如下图所示 :>

初写--数据结构-->顺序表__01

顺序表一般分为 :> 静态顺序表， 动态顺序表

(-) 静态顺序表 :> 使用定长数组来存储数据元素

// 静态顺序表

#define N 7         //自定义数组长度为7

typedef int SLDataType;    //此处的int类型是指要代创建的数组只能存储整形数据，也可以是其他类型，如，char, float, double等等

typedef struct SeqList
{
SLDataType arr[N];     //定长数组arr创建完成
int sz;               //有效数据元素的个数   
}SL;

初写--数据结构-->顺序表__01


如上所示，数组arr可以最大存储7个元素，其中有效元素的个数为6个。

但是，日常实际用途当中，不会用到静态的顺序表，有很大的不足之处 :> 

1.首先，开的空间大小太小，不够用！！

2.再者，开的空间大小太大了，容易造成浪费。比如说，我开了一个存放十万元素的数组，但是我只用了不到一百个，那么剩下的空间就会无端浪费掉了！！

所以说，日常生活中，我们使用的都是动态的顺序表---> 可以按需申请空间。（只针对线性表中的两种顺序表而言）

（二）动态顺序表 :> 按需申请空间

//动态顺序表

下面的部分是头文件 “Seqlist.h”

#include <stdio.h>
typedef int SLDataType;

typedef struct SeqList
{
SLDataType* a;    //SLDataType是typedef作用于int 的结果，自定义了整形类型叫做SLDataType
//同时a表示是数组a的首元素地址！！
int sz;            //sz是有效元素的个数，一定要理解有效两个字，此后涉及的删除需要“对她的理解”
int capcity;      //capcity是该数组a的容量大小。
}SL;

注意，此处的头文件对于实现顺序表中的增删查改操作还远远不够，不过为了使得初次阅读或者开始尝试写顺序表的小伙伴们来说，逻辑思考要一步一步进行，不然的的话，思维跳跃太快，你们会看不懂！！

接下来，是写测试环节“Test.c”

#include “Seqlist.h”

void test_01()
{
SL s;
SLInitial(&s);        //初始化
SLPushBack(&s, 1);    //尾部插入数据，简称“尾插”
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);

SLPrint(&s);          //打印

SLDestroy(&s);        //销毁

}

int main()
{
//此处的函数只进行尾插测试
test_01();
}

现在开始实现操作环节 “Seqlist.c”

#include “Seqlist.h”

//初始化
void SLInitial(SL* ps)
{
ps ->a = (SLDataType*)malloc(sizeof(SLDataType));    //malloc是C语言库中的一个函数，需要包含头文件<stdlib.h>
if(pc ->a == NULL)
  {
perror("malloc::fail");
return;
  }
pc ->sz = 0;
pc ->capcity = 3;    //此处容量最好用重定义#define进行赋值操作，便于后期维护和更改初始化容量
}

//打印
void SLPrint(SL* ps)
{
int i = 0;
for(i = 0; i < ps ->sz; i++)
  {
printf("%d ", ps ->a[i]);
  }
printf("\n");
}

//尾插数据
void SLPushBack(SL* ps, SLDataType x)
{
if(ps ->sz == ps ->capcity)
  {
SLDataType* tamp = (SLDataType*)realloc(pc ->a, sizeof(SLDataType) * ps ->capcity * 2);  //此处要特别注意 
if(tamp ==  NULL)
    {
perror("realloc fail");      //此处的perror是打印并展示出错误类型的
return;
    }

pc ->a = tamp;        //此处需要注意，对于tamp有两种情况：一是原地扩容，二是异地扩容
//原地扩容，如果要进行扩容的空间不是很大，此处可以不写，也不会报错！反之，最好写上！！
pc ->capcity *= 2;    //容量扩大原先的两倍
  }

//一种写法
//ps ->a[pc ->sz] = x;
//pc ->sz++;

//另一种写法
ps ->a[pc ->sz++] = x;
}

//销毁
void SLDestroy(SL* PS)
{
free(ps);
ps = NULL;  //释放ps申请的空间，归还给操作系统。同时防止ps成为野指针进行乱窜！！
pc ->sz = pc ->capcity = 0;
}

对于上述的操作循环，有几处代码需要进行特别注意 :>

SLDataType* tamp = (SLDataType*)realloc(pc ->a, ps ->capcity * 2);  //错误扩容空间

如果加上断言会有报错 :>

初写--数据结构-->顺序表__01

free报出警告，有两种情况 :>

1.ps指向的空间a成为了野指针，这种情况发生的概率太小

2.ps指向的空间a开辟的空间大小有问题，即开辟空间小了！！

显然此处是开辟空间小了，原因如下 :>

typedef int SLDataType;

SLDataType是一个整形，而一个整形是4个字节，所开辟的初始化数组a的容量，又被指定是3个整形，故此初始化空间可以存放12个字节！现在呢！由于扩容的是 “ps ->capcity * 2” 即仅仅扩容了3 * 2 = 6个字节的空间，却用来当做24个字节（4 * 3 * 2）来使用，显然开辟空间太小了！！此处是难点理解之一。

应该修改为“sizeof(SLDataType) * ps ->capcity * 2”即不能忽视整形大小的字节--->4

还有一处要注意 :>

ps ->a[pc ->sz] = x;
pc ->sz++;

有关于尾插逻辑的代码理解 :>

如下图所示：

初写--数据结构-->顺序表__01

此处注意对"sz"的理解，pc ->sz 是有效元素个数，sz也是元素下标的下一个位置，请看绿色箭头所指向的位置，是一个未被元素填充的空间的起始点。。因此尾插数据时，既可在此处赋值即可！！

现在对以上代码模块进行优化 :>

头部文件需要声明一些在操作环节中的函数，如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define INC_CAPCITY 3   //容量大小
#define INC_MAX  2      //扩大倍率，通常往往都是两倍，比较适中。此处并无特别要求，随心而定！！

typedef int SLDataType;

typedef struct SeqList
{
SLDataType* a;    //SLDataType是typedef作用于int 的结果，自定义了整形类型叫做SLDataType
//同时a表示是数组a的首元素地址！！
int sz;            //sz是有效元素的个数，一定要理解有效两个字，此后涉及的删除需要“对她的理解”
int capcity;      //capcity是该数组a的容量大小。
}SL;

//初始化
void SLInitial(SL* ps);

//打印
void SLPrint(SL* ps);

//销毁
void SLDestroy(SL* PS);

//尾插数据
void SLPushBack(SL* ps, SLDataType x);

操作环节的部分代码需要修改并进行断言补充  :>

#include “Seqlist.h”

//初始化
void SLInitial(SL* ps)
{
ps ->a = (SLDataType*)malloc(sizeof(SLDataType));    //malloc是C语言库中的一个函数，需要包含头文件<stdlib.h>
if(pc ->a == NULL)
  {
perror("malloc::fail");        //此处的perror是打印并展示出错误类型的
return;
  }
pc ->sz = 0;
pc ->capcity = INC_CAPCITY;    //此处容量最好用重定义#define进行赋值操作，便于后期维护和更改初始化容量
}

//打印
void SLPrint(SL* ps)
{
assert(ps);
int i = 0;
for(i = 0; i < ps ->sz; i++)
  {
printf("%d ", ps ->a[i]);
  }
printf("\n");
}

//尾插数据
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
if(ps ->sz == ps ->capcity)
  {
SLDataType* tamp = (SLDataType*)realloc(pc ->a, sizeof(SLDataType) * ps ->capcity * INC_MAX);  //此处要特别注意 
if(tamp ==  NULL)
    {
perror("realloc fail");
return;
    }

pc ->a = tamp;        //此处需要注意，对于tamp有两种情况：一是原地扩容，二是异地扩容
//原地扩容，如果要进行扩容的空间不是很大，此处可以不写，也不会报错！反之，最好写上！！
pc ->capcity *= INC_MAX;    //容量扩大原先的两倍
  }

//一种写法
//ps ->a[pc ->sz] = x;
//pc ->sz++;

//另一种写法
ps ->a[pc ->sz++] = x;
}

//销毁
void SLDestroy(SL* PS)
{
free(ps);
ps = NULL;  //释放ps申请的空间，归还给操作系统。同时防止ps成为野指针进行乱窜！！
pc ->sz = pc ->capcity = 0;
}

有关测试环节的传值行为，进行分析 :>

#include “Seqlist.h”

void test_01()
{
SL s;
SLInitial(&s);        //初始化
SLPushBack(&s, 1);    //尾部插入数据，简称“尾插”
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);

SLPrint(&s);          //打印

SLDestroy(&s);        //销毁

}

int main()
{
//此处的函数只进行尾插测试
test_01();
}

如果不是传值，那么代码如下 :>

void test_01()
{
SL s;
SLInitial(s);        //初始化 
}
void SLInitial(SL ps)
{
ps.a = (SLDataType*)malloc(sizeof(SLDataType));
if(ps.a == NULL)
  {
perror("malloc::fail");        //此处的perror是打印并展示出错误类型的
return;
  }
ps.sz = 0;
ps.capcity = INC_CAPCITY;
}

请看下面的分析 :>

初写--数据结构-->顺序表__01

这里稍微简单提及一下栈区，形参的创建是在栈区当中创建的，而形参只是实参的一份临时拷贝，出了栈区就会被销毁！！因此无论形参如何改变，都无法影响到实参的值！！可是话又说回来，该如何改变实参的值呢？

答案是将实参的地址传过去，就可以改变相对应的值了！！

如下所示 :>

初写--数据结构-->顺序表__01

最终尾插打印的结果如下 :>

初写--数据结构-->顺序表__01

如此该顺序表一部分工作已经实现了，即可无错误地打印出尾插的数值。










标签：

相关文章