[数据结构] 线性表的顺序存储方式

谁践踏了优雅 2023-01-18 15:19 41阅读 0赞

此篇博客主要对线性表的顺序存储方式进行解释，如果想了解链式存储点击此链接跳转: [线性表的链式存储结构][Link 1]。

# 线性结构 #

线性结构指的是每个元素都有一个唯一的前驱与后继，但第一个元素只能有后继，最后一个元素只能有一个前驱。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

# 顺序存储方式 #

1.静态顺序表：使用定长数组存储，声明结构体时直接指定长度

#define ARRLEN 10
    struct SeqList{ 
    	int arr[ARRLEN];
    	....
    };

2.动态顺序表：使用动态开辟的数组存储

struct SeqList{ 
    	int *arr;	// 在初始化时确定长度
    	....
    };

顺序表的优劣：

1.  存储形式  
    数据在内存中使用的内存空间连续，可以通过数组形式进行访问。
2.  缺点  
    在数组访问时，时间复杂度为O(1)，但在插入删除数据时，时间复杂度为O(n)。

# 顺序存储方式的基本操作 #

## 结构 ##

struct SeqList
    { 
    	DataType* array;
    	int capacity;    // 表示array指向的空间总的大小
    	int size;        // 表述顺序表中有效元素的个数
    };

## 动态扩容 ##

void SeqListReserve(SeqList* ps, int capacity)
    { 
    	assert(ps);
    	// 如果新申请空间变小了，则不进行操作
    	if (capacity <= ps->capacity)
    		return;
    
    	// 如果ps为空 则新申请一块内存空间进行存储
    	ps->array = (DataType*)realloc(ps->array, capacity * sizeof(DataType));
    	ps->capacity = capacity;
    }

## 根据位置插入删除元素 ##

void SeqListInsert(SeqList* ps, int pos, DataType data)
    { 
    	assert(ps);
    
    	// 判断插入位置是否符合要求
    	if (pos < 0 || pos > ps->size)
    	{ 
    		printf("位置非法!!!\n");
    		return;
    	}
    
    	// 判断空间是否足够插入元素 不够则扩容
    	if (ps->size >= ps->capacity)
    	{ 
    		SeqListReserve(ps, SeqListCapacity(ps) * 2);
    	}
    
    	// 插入
    	// 1. 将pos及其后续所有的元素整体往后搬移
    	// i: 表示元素要搬移到的位置
    	for (int i = ps->size; i > pos; --i)
    	{ 
    		ps->array[i] = ps->array[i - 1];
    	}
    	ps->array[pos] = data;
    	ps->size++;
    }
    
    void SeqListErase(SeqList* ps, int pos)
    { 
    	assert(ps);
    	// 判断删除位置是否符合要求
    	if (pos < 0 || pos > ps->size)
    	{ 
    		printf("位置非法!!!\n");
    		return;
    	}
    
    	for (int i = pos + 1; i < ps->size; i++)
    	{ 
    		ps->array[i - 1] = ps->array[i];
    	}
    	ps->size--;
    }

## 其他基本操作 ##

// 顺序表初始化
    void SeqListInit(struct SeqList* ps, int initCap)
    { 
    	// 申请内存空间
    	ps->array = (DataType*)malloc(sizeof(DataType) * initCap);
    	// 初始化起始容量与带下
    	ps->capacity = initCap;
    	ps->size = 0;
    }
    
    void SeqListDestroy(SeqList* ps)
    { 
    	assert(ps);
    
    	if (ps->array != NULL)
    	{ 
    		// 释放申请的内存空间
    		free(ps->array);
    		ps->array = NULL;
    
    
    		ps->capacity = 0;
    		ps->size = 0;
    	}
    }
    
    // 向顺序表中尾插data
    void SeqListPushBack(SeqList* ps, DataType data)
    { 
    	assert(ps);
    
    	// 判断空间是否足够放入元素
    	if (ps->size >= ps->capacity)
    		SeqListReserve(ps, SeqListCapacity(ps) * 2);
    
    	ps->array[ps->size++] = data;
    }
    
    // 将顺序表中最后一个元素删除掉
    void SeqListPopBack(SeqList* ps)
    { 
    	assert(ps);
    
    	// 判断顺序表是否为空 为空则不进行元素删除
    	if (SeqListEmpty(ps))
    	{ 
    		return;
    	}
    
    	ps->size--;
    }
    
    // 获取有效元素的个数
    int SeqListSize(SeqList* ps)
    { 
    	return ps->size;
    }
    
    // 获取顺序表的总容量--底层空间总的大小
    int SeqListCapacity(SeqList* ps)
    { 
    	return ps->capacity;
    }
    
    // 检测顺序表是否为空
    int SeqListEmpty(SeqList* ps)
    { 
    	assert(ps);
    
    	
    	return 0 == ps->size;
    }
    
    // 查找指定元素
    int SeqListFind(SeqList* ps, DataType data)
    { 
    	assert(ps);
    
    	for (int i = 0; i < ps->size; i++)
    	{ 
    		if (ps->array[i] == data)
    			return i + 1;
    	}
    
    	return -1;
    }

[Link 1]: https://blog.csdn.net/weixin_43717520/article/details/115423398
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/bb8aa4f305ad4f63878a4bd8ad11e55b.png