【数据结构】顺序表的定义及实现方式

文章目录

• 顺序表的定义
• 顺序表的实现
• • 静态分配
  • 动态分配
  • 动态申请内存空间，动态释放内存空间（malloc，free）
  • 顺序表的特点
  • 总结

    ---

    顺序表的定义

    顺序表也就是用顺序存储的方式实现线性表。

    顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

    

    ---

    顺序表的实现

    

    静态分配

    在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

    在使用静态存储时，首先定义一个最大长度，然后声明顺序表，在声明的顺序表中使用数组存放数据元素，定义当前长度length，代码如下。

    Sq：sequence（顺序，序列）

    #include 
     // 静态存储
    // 定义最大长度,最大为10个,所以只能存放10个
    #define MaxSize 10
    // 声明顺序表
    typedef struct {
    	// 用静态的数组存放数据元素
    	int data[MaxSize];
    	// 顺序表的当前长度
    	int length;
    }SqList; // 顺序表的类型定义
    

    初始化顺序表

    声明顺序表后，需要初始化顺序表，将所有数据元素设置为默认初始值，顺序表的初试长度设置为0（这一步必须做！！！）

    如果没有初始化顺序表，则内存中会有遗留的脏数据，所以将length的值设置为0这一步必须做！！！

    初始化代码如下：

    #include 
     // 静态存储
    // 定义最大长度,最大为10个,所以只能存放10个
    #define MaxSize 10
    // 声明顺序表
    typedef struct {
    	// 用静态的数组存放数据元素
    	int data[MaxSize];
    	// 顺序表的当前长度
    	int length;
    }SqList; // 顺序表的类型定义
    // 初始化顺序表
    void InitList(SqList& L){
    	for (int i = 0; i  
    注意：
     
    

    • 使用静态分配时，如果数组存满了，就“放弃治疗”，因为顺序表的表长刚开始确定后就无法更改（存储空间是静态的）。
    • 如果刚开始就声明一个很大的内存空间是没有必要的，这样会浪费存储资源。

      动态分配

      使用动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数组空间占满，就另外开辟一块更大的存储空间，替换原来的存储空间，而不需要为线性表一次性地划分所有空间。

      动态分配使用“动态数组”实现，先定义一个初始长度，然后定义顺序表，在顺序表中用指针来动态分配数组，定义顺序表的最大容量和当前长度。

      #include 
      // 初始长度
      #define InitSize 10
      typedef struct {
      	// 动态分配数组的指针
      	ElemType *data;
      	// 顺序表的最大容量
      	int MaxSize;
      	// 顺序表的当前长度
      	int length;
      }SeqList;
      

      动态申请内存空间，动态释放内存空间（malloc，free）

      初始动态分配内存语句： L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize)

      • L.data：指向一整片连续的存储空间的起始地址。
      • (ElemType *)：malloc 函数返回一个指针， 需要强制转型为你定义的数据元素类型指针。
      • malloc：动态申请内存空间。
      • InitSize：malloc 函数的参数，指明要分配多大的连续内存空间。

        注意：使用malloc和free函数需要引入头文件 #include

        #include 
        #include 
        // 初始长度
        #define InitSize 10
        typedef struct {
        	// 动态分配数组的指针
        	int *data;
        	// 顺序表的最大容量
        	int MaxSize;
        	// 顺序表的当前长度
        	int length;
        }SqList;
        // 初始化顺序表
        void InitList(SqList& L) {
        	//申请一片连续的存储空间
        	L.data = (int *)malloc(sizeof(int) * InitSize);
        		// 设置顺序表初试长度为0
        		L.length = 0;
        		L.MaxSize = InitSize;
        }
        //动态插入数据，增加长度
        void IncreaseSize(SqList& L, int len) {
        	int* p = L.data;
        	L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
        	for (int i = 0; i  
        顺序表的特点
         
        顺序表的特点有随机访问，存储密度高，拓展容量不方便，插入和删除数据元素不方便。
         
        总结
         
        以上就是今天的学习内容啦~
        如果有兴趣的话可以订阅专栏，持续更新呢~
        咱们下期再见~