当前位置：首页 > news >正文

顺序表的动态分配

news 2026/7/14 20:00:35

文章目录

代码
- 代码解读
- - 类型定义
  - InitList ()含义
  - IncreaseSize()含义
  - - 流程
    - 规范说明
- 注意

代码

#include<stdlib.h>#defineInitSize10//默认的最大长度typedefstruct{int*data;// 指示动态分配数组的首地址intMaxSize;// 顺序表的最大容量intlength;// 顺序表的当前有效长度}SeqList;// 顺序表的类型定义// 初始化动态顺序表voidInitList(SeqList&L){// malloc申请连续堆内存L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;}// 扩容函数：增加动态数组的长度voidIncreaseSize(SeqList&L,intlen){int*p=L.data;// 先保存旧数组首地址// 开辟更大的新空间L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));// 把旧数据拷贝到新空间for(inti=0;i<L.length;i++){L.data[i]=p[i];}L.MaxSize=L.MaxSize+len;// 更新最大容量free(p);// 释放旧数组内存，防止内存泄漏}intmain(){SeqList L;// 栈上创建顺序表结构体InitList(L);// 初始化IncreaseSize(L,5);// 扩容5个int空间return0;}

和静态顺序表核心区别
静态：int data[MaxSize]数组空间固定在栈，无法扩容；
动态：int *data 空间在堆，可重新 malloc 扩容。

代码解读

类型定义

结构体里存的是指向堆中动态分配的数组，不是固定数组；（相当于是一张“门牌号纸条”）

typedefstruct{int*data;// ① 这是一个指针变量，将来存放堆区数组的起始地址intMaxSize;// ② 记录当前总共分配了多少个坑位（容量）intlength;// ③ 记录当前实际用了多少个坑位（有效长度）}SeqList;

栈区 (Stack)：SeqList L
[ data ] = 0x1000 (指向堆区的门牌号)
[ MaxSize ] = 10
[ length ] = 0
堆区 (Heap)：
地址 0x1000 → [ 坑0 ][ 坑1 ] … [ 坑9 ] (共 10 个 int，40 字节)

InitList ()含义

可以理解为：在堆区“盖房子”，把门牌号写在便利贴上

voidInitList(SeqList&L){// L 是 SeqList 类型变量，L.data 就是访问这个自定义成员。L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;}

malloc(InitSize * sizeof(int))：向操作系统申请10 * 4 = 40字节的连续堆内存。假设返回的起始地址是 0x1000。
(int *)强制转换：告诉编译器，“这块地以后要按 int 的步长（4字节）来切割”。
L.data = ...：把 0x1000 这个门牌号，复制到结构体 L 的 data 这个格子中。
- ** 作用：在堆内存开辟一块能存InitSize个int的连续空间，返回首地址赋值给L.data**
L.length = 0; L.MaxSize = 10;：设置当前有效个数为 0（空表），记录总容量为 10。

IncreaseSize()含义

这是整段代码的灵魂操作。当MaxSize不够用时，C 语言没有像 JS 那样的自动扩容，必须手动实现“找新家、搬家具、拆旧房”。

voidIncreaseSize(SeqList&L,intlen){int*p=L.data;// 步骤1L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));// 步骤2for(inti=0;i<L.length;i++){L.data[i]=p[i];// 步骤3}L.MaxSize=L.MaxSize+len;// 步骤4free(p);// 步骤5}

流程

步骤	代码	物理内存行为	通俗类比解释
①	int *p = L.data;	临时新建一张便利贴 p，把原来的门牌号 0x1000 抄下来。(假设的动态数组首地址)	在旧房子被推倒前，先拿手机拍下门牌号。
②	L.data = malloc((MaxSize+len)*sizeof(int));	在堆区另找一块更大的地皮（比如 0x2000），把新门牌号 0x2000 写入 L.data。	找搬家公司，在别处租了更大的新房子。
③	for… L.data[i]=p[i];	挨个访问旧地址 0x1000 + i4 读取数据，写入新地址 0x2000 + i4。	把旧房子里的家具一件件搬到新房子。
④	L.MaxSize = L.MaxSize + len;	把容量记录从 10 更新为 15。	房产证上更新新家的面积。
⑤	free(p);	把地址 0x1000 的 40 字节彻底归还给操作系统。	旧房子产权注销，彻底拆掉。