【数据结构】-顺序表(动态分配）

Bertha 。 2023-02-27 10:39 15阅读 0赞

### 顺序表-动态分配 ###

*  1.头文件及类型定义
 *  2.顺序表类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化顺序表
     *  4.2 求表长
     *  4.3 判空
     *  4.4 增加动态数组的长度
     *  4.5 插入操作
     *  4.6 删除操作
     *  4.7 查找操作
     *   *  4.7.1 按位查找
         *  4.7.2 按值查找
     *  4.8 遍历
     *  4.9 main函数
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>		//malloc和free函数的原型在头文件<stdlib.h>中
    #define InitSize 10	   //定义顺序表的初始长度
    #define ElemType int   //定义数据元素类型
    /*
    	02.顺序表_动态分配(malloc函数实现)
    		1.sizeof(类型符或变量名)
    			（1）当操作数为数据类型时，得到该数据类型的存储字节数
    			（2）当操作数为变量名时，得到变量使用的存储单元字节数
    		2.malloc函数的使用
    			（1）作用：分配一块连续的内存空间并返回所分配空间的起始地址
    			（2）常用格式：L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
    			（3）注意：使用该函数一般要判断其返回值，若返回值为NULL，则说明分配失败，程序要进行相应处理
    		3.free（）函数
    			 (1)释放内存空间
    			 (2)与malloc函数是一对,malloc返回值为内存空间基址，free参数为内存空间基址
    */

# 2.顺序表类型定义 #

typedef struct SeqList {
        
    	ElemType* data;		//指示动态分配数组的指针，也就是malloc函数返回的分配空间的起始地址
    	int MaxSize;		//顺序表的最大容量
    	int length;			//顺序表当前长度
    }SeqList;

# 3.函数声明 #

/*函数声明*/
    void InitList(SeqList& L);							//1.初始化顺序表
    int Length(SeqList L);								//2.求表长
    bool Empty(SeqList L);								//3.判空
    void IncreaseSize(SeqList& L, int len);				//4.增加动态数组的长度
    bool InsertList(SeqList& L, int i, ElemType e);		//5.插入操作
    bool ListDelete(SeqList& L, int i, ElemType& e);	//6.删除操作
    ElemType GetElem(SeqList L, int i);					//7-1.查找操作-按位查找
    int LocateElem(SeqList L, ElemType e);				//7-2.查找操作-按值查找
    void PrintList(SeqList L);							//8.遍历

# 4.基本操作 #

## 4.1 初始化顺序表 ##

//1.初始化顺序表
    void InitList(SeqList& L) {
        
    	L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    	L.MaxSize = InitSize;
    	L.length = 0;
    	printf("顺序表初始化成功！\n");
    }

## 4.2 求表长 ##

//2.求表长：返回顺序表的长度，即L中数据元素的个数
    int Length(SeqList L) {
        
    	return L.length;
    }

## 4.3 判空 ##

//3.判空：判断顺序表是否为空
    bool Empty(SeqList L) {
        
    	if (L.length == 0) {
        
    		printf("顺序表为空！\n");
    		return true;
    	}
    	else {
        
    		printf("顺序表非空！\n");
    		return false;
    	}
    }

## 4.4 增加动态数组的长度 ##

//4.增加动态数组的长度
    void IncreaseSize(SeqList& L, int len) {
        
    	int* p = L.data;
    	L.data = (ElemType*)malloc(sizeof(ElemType) * (L.MaxSize + len));
    	for (int i = 0; i < L.length; i++)		//将数据复制到新区域(时间开销大)
    		L.data[i] = p[i];
    	L.MaxSize += len;			//顺序表的最大长度增加len
    	free(p);		//释放原来的内存空间
    }

## 4.5 插入操作 ##

//5.插入操作：在表L的位序i上插入指定元素e
    bool InsertList(SeqList& L, int i, ElemType e) {
        
    	if (i<1 || i>L.length + 1)		//判断要插入的位序i是否合法（合法范围[1,length+1]，即首部和尾部之间）
    		return false;
    	if (L.length >= L.MaxSize)		//判断当前存储空间是否已满，若已满，不能插入
    		return false;
    	for (int j = L.length; j >= i; j--)		//将第i个元素及之后的元素后移
    		L.data[j] = L.data[j - 1];
    	L.data[i - 1] = e;					//位序为i处放入指定元素e
    	L.length++;						//顺序表长度+1
    	return true;
    }

## 4.6 删除操作 ##

//6.删除操作：删除表中位序为i的元素，并用e返回删除元素的值
    bool ListDelete(SeqList& L, int i, ElemType& e) {
        
    	if (i<1 || i>L.length) {
        	//判断要删除的位序是否合法(合法范围为[1,length])
    		return false;
    	}
    	e = L.data[i - 1];				//位序i的元素赋给e
    	for (int j = i; j < L.length; j++)		//将第i个元素之后的元素前移
    		L.data[j - 1] = L.data[j];
    	L.length--;					//顺序表长度-1
    	return true;
    }

## 4.7 查找操作 ##

### 4.7.1 按位查找 ###

//7-1.查找操作-按位查找：获取表L中位序为i的元素的值
    ElemType GetElem(SeqList L, int i) {
        
    	if (i<1 || i>L.length)
    		return -1;
    	return L.data[i - 1];
    }

### 4.7.2 按值查找 ###

//7-2.查找操作-按值查找：查找表L中第一个元素值为e的元素，并返回其位序
    int LocateElem(SeqList L, ElemType e) {
        
    	for (int i = 0; i < L.length; i++)
    		if (L.data[i] == e)
    			return i + 1;		//数组下标为i的元素值等于e，返回其位序i+1
    	return 0;	//返回值为0，说明查找失败
    }

## 4.8 遍历 ##

//8.遍历顺序表
    void PrintList(SeqList L) {
        
    	printf("遍历开始：");
    	for (int i = 0; i < L.length; i++) {
        
    		printf("%d\t", L.data[i]);
    	}
    	printf("\n");
    }

## 4.9 main函数 ##

int main() {
        
    	int n,i;
    	ElemType a,e=-1;		
    	SeqList L;		//声明一个顺序表
    	InitList(L);	//初始化顺序表
    	/*0、判空*/
    	Empty(L);
    
    	/*1、插入元素*/
    	printf("请输入元素个数：");
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) {
        		
    		scanf("%d", &a);
    		if (InsertList(L, i + 1, a))
    			printf("成功插入第%d个元素：%d\n", i + 1, a);
    		else
    			printf("第%d个元素插入失败！", i + 1);
    	}
    
    	/*2、判空*/		
    	Empty(L);
    
    	/*3、遍历当前顺序表*/
    	PrintList(L);
    
    	/*4、删除元素*/
    	printf("请输入您要删除元素的位序i：");
    	scanf("%d", &i);
    	if (ListDelete(L, i, e))
    		printf("已删除第%d个元素，其值为：%d\n", i, e);
    	else
    		printf("位序i不合法,删除失败！\n");
    
    	/*5、输出当前表长*/
    	printf("当前表长为:%d\n",Length(L));
    
    	/*6、遍历当前顺序表*/
    	PrintList(L);
    
    	/*7、按位查找*/
    	printf("请输入您要查找元素的位序i：");
    	scanf("%d",&i);
    	if (GetElem(L, i) == -1)
    		printf("您输入的位序不合法！");
    	else
    		printf("位序为%d的值为：%d\n", i, GetElem(L, i));
    
    	/*8、按值查找*/
    	printf("请输入您要查找元素的值：");
    	scanf("%d", &a);
    	printf("值为%d的元素第一次出现的位序为：%d\n", a, LocateElem(L, a));
    	return 0;
    }

# 5.小结 #

1.顺序表最大的特点是随机访问，通过首地址和元素序号可在时间O(1) 内找到指定的元素。  
2.顺序表的存储密度高，每个结点只存储数据元素。  
（相比链表，除了存储数据外，还要花费一定开销存储下一个结点的地址）  
3.缺点：逻辑上相邻的元素物理上也相邻，但插入和删除操作需要移动大量元素，时间开销很大。所以，引入链表。  
（相比链表，链表的插入删除只需要对指针进行修改即可）