顺序表的实现方式之静态分配和动态分配_顺序表动态分配

---

前言

顺序表的实现方式分为两种，即静态分配和动态分配，其具有逻辑上相邻的数据元素物理上也相邻的特点

---

一、静态分配

1. 定义并且初始化顺序表

• 注：
  （1）在内存中分配存储顺序表L的空间。包括MaxSize*sizeof(ElemType)和存储length的空间
  （2）把各个数据元素的值设为默认值（可省略）
  （3）将length长度设为0

#include <stdio.h>
#define MaxSize 10	//定义最大长度
typedef struct{
	int data[MaxSize];	//用静态的“数组”存放数据元素
	int length;	//顺序表的当前长度
}Sqlist;	//顺序表的定义类型
//基本操作：初始化一个顺序表
void Initlist(Sqlist &L){
	for(int i=0;i<MaxSize;i++){
		L.data[i]=0;	//将所有数据元素设置为默认初始值
		L.length=0;	//顺序表初始长度为0
	}
}
int main()
{
	Sqlist L;	//申明一个顺序表
    Initlist(L);	//初始化顺序表
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.当没有设置数据元素的默认值时，以下情况会存在脏数据

/*不初始化数据元素，内存不刷0*/
#include <stdio.h>
#define MaxSize 10	//定义最大长度
typedef struct{
	int data[MaxSize];	//用静态的“数组”存放数据元素
	int length;	//顺序表的当前长度
}Sqlist;	//顺序表的定义类型
//基本操作：初始化一个顺序表
void Initlist(Sqlist &L){
	//没有设置数据元素的初始值
		L.length=0;	//顺序表初始长度为0
	
}
int main()
{
	Sqlist L;	//申明一个顺序表
    Initlist(L);	//初始化顺序表
	//尝试“违规”的打印整个data数组
	for(int i=0;i<MaxSize;i++){
		printf("data[%d]=%d\n",i,L.data[i]);
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果

在main函数中for做如下修改：

for(int i=0;i<L.length;i++）
1

此时由于L.length初始化为0，故不执行for循环中的printf语句

3.最好访问方式是使用顺序表中的按位查找方式访问各个数据元素

#include <stdio.h>
#define MaxSize 10
typedef struct {
	int data[MaxSize];
	int length;
}Sqlist;
void Initlist(Sqlist& L) {
	L.length = 0;
}
void Getelem(Sqlist &L, int i) {
	L.data[i - 1] = 5;
}
int main()
{
	Sqlist L;
	int i=1;
	Initlist(L);
	Getelem(L, i);
	printf("L.data[%d]=%d\n", i, L.data[i-1]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二、动态分配

1.动态分配所需函数

C语言中malloc和free函数
malloc函数返回一个指针，需要强制转型为定义的数据元素类型指针
malloc函数的参数指明要分配多大的连续内存空间

L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
1

malloc和free函数包含在#include<stdlib.h>头文件中

2.动态分配部分代码

#include <stdio.h>
#include<stdlib.h>
#define InitSize 10	//默认的最大长度
typedef struct{
	int MaxSize;
	int length;
	int *data;	//指示动态分配数组的指针
}Seqlist;
void Initlist(Seqlist &L){
	//用malloc函数分配一段连续的内存空间
	L.data=(int *)malloc((sizeof(int)*InitSize);
	L.length=0;
	L.MaxSize=InitSize;
}
//动态增加数组的长度
void IncreaseSize(Seqlist &L,int len){
	int *p=L.data;
	L.data=(int *)(malloc(sizeof(int)*(L.MaxSize+len));
	for(int i=0;i<L.length;i++){
		L.data[i]=p[i];	//将数据复制到新的区域
	}
	L.MaxSize=L.MaxSize+len;
	free(p);	//释放原来的内存空间
}
				  						 
int main(){
	Seqlist L;
	Initlist(L);
//往顺序表插入几个元素（此处暂时省略）
    
	IncreaseSize(L,5);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

动态增加数组过程

---

总结

顺序表的静态分配无法改变内存空间大小，而动态分配增加数组长度时，将原数据复制到新的空间时时间开销大