前言
本文总结学习动态顺序表的各个接口实现。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。 一般分为:
- 静态顺序表:使用定长数组存储元素
- 动态顺序表:使用动态开辟的数组存储,本文基于动态顺序表来实现接口。
一、顺序表头文件SeqList.h
本节主要包含:结构体类型创建,函数声明,头文件包含
#pragma once
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <errno.h>
typedef int SLdataType;
typedef struct SeqList
{
SLdataType* arr;
size_t size;
size_t capicity;
}SeqList;
void SeqListInit(SeqList* psl);
void SeqListDestory(SeqList* psl);
void SeqListPrint(SeqList* psl);
void SeqListCheckCapacity(SeqList* psl);
void SeqListInsert(SeqList* psl, size_t pos, SLdataType x);
void SeqListErase(SeqList* psl, size_t pos);
int SeqListFind(SeqList* psl, SLdataType x);
void SeqListPushBack(SeqList* psl, SLdataType x);
void SeqListPopBack(SeqList* psl);
void SeqListPushFront(SeqList* psl, SLdataType x);
void SeqListPopFront(SeqList* psl);
void SeqListModify(SeqList* psl, size_t pos, SLdataType x);
二、顺序表各接口具体实现SeqList.c
本节主要包含:顺序表各个接口的实现方法
2.1 顺序表初始化
void SeqListInit(SeqList* psl)
{
assert(psl);
psl->arr = NULL;
psl->capicity = 0;
psl->size = 0;
}
2.2 顺序表销毁
void SeqListDestory(SeqList* psl)
{
assert(psl);
free(psl->arr);
(psl->arr) = NULL;
psl->capicity = psl->size = 0;
}
2.3 顺序表打印
void SeqListPrint(SeqList* psl)
{
assert(psl);
int i = 0;
for (i = 0; i < (psl->size); i++) {
printf("%d ", (psl->arr)[i]);
}
printf("\n");
}
2.4 检查空间,如果满了(psl->size == psl->capacity),进行增容(2倍)
void SeqListCheckCapacity(SeqList* psl)
{
assert(psl);
int newcapacity = (0 == (psl->capicity)) ? 4 : 2 * (psl->capicity);
if ((psl->capicity) == (psl->size)) {
SLdataType* tmp = (SLdataType*)realloc(psl->arr, newcapacity * sizeof(SLdataType));
if (NULL == tmp) {
printf("%s\n", strerror(errno));
exit(-1);
}
else {
psl->arr = tmp;
psl->capicity = newcapacity;
}
}
}
2.5 顺序表在pos位置(下标)插入元素x
void SeqListInsert(SeqList* psl, size_t pos, SLdataType x)
{
assert(psl);
SeqListCheckCapacity(psl);
if (pos > (psl->size)) {
printf("pos 越界:%d\n", pos);
return;
}
int end = (psl->size);
while (end > pos) {
(psl->arr)[end] = (psl->arr)[end - 1];
end--;
}
(psl->arr)[pos] = x;
(psl->size)++;
}
2.6 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
if (pos >= (psl->size)) {
printf("pos 越界:%d\n", pos);
return;
}
int end = (psl->size) - 1;
while (pos < end) {
(psl->arr)[pos] = (psl->arr)[pos + 1];
pos++;
}
(psl->size)--;
}
2.7 顺序表查找(按数组元素值)(找到返回对应下标,未找到返回-1)
int SeqListFind(SeqList* psl, SLdataType x)
{
assert(psl);
int i = 0;
for (i = 0; i < (psl->size); i++) {
if (x == (psl->arr)[i]) {
return i;
}
}
return -1;
}
2.8 顺序表尾插
void SeqListPushBack(SeqList* psl, SLdataType x)
{
assert(psl);
SeqListInsert(psl, (psl->size), x);
}
2.9 顺序表尾删
void SeqListPopBack(SeqList* psl)
{
assert(psl);
SeqListErase(psl, (psl->size) - 1);
}
2.10 顺序表头插
void SeqListPushFront(SeqList* psl, SLdataType x)
{
assert(psl);
SeqListInsert(psl, 0, x);
}
2.10 顺序表头删
void SeqListPopFront(SeqList* psl)
{
assert(psl);
SeqListErase(psl, 0);
}
2.11 顺序表修改指定位置元素
void SeqListModify(SeqList* psl, size_t pos, SLdataType x)
{
assert(psl);
if (pos >= (psl->size)) {
printf("pos 越界:%d\n", pos);
return;
}
(psl->arr)[pos] = x;
}
三、顺序表测试test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
int main()
{
SeqList s = { 0 };
SeqListInit(&s);
int i = 0;
for (i = 0; i < 10; i++) {
SeqListInsert(&s, 0, i);
}
SeqListPrint(&s);
SeqListErase(&s, 3);
SeqListPrint(&s);
int ret = SeqListFind(&s, 4);
printf("%d\n", ret);
SeqListPushBack(&s, 99);
SeqListPrint(&s);
SeqListPopBack(&s);
SeqListPrint(&s);
SeqListPushFront(&s, 100);
SeqListPrint(&s);
SeqListPopFront(&s);
SeqListPrint(&s);
SeqListModify(&s, 3, 555);
SeqListPrint(&s);
SeqListDestory(&s);
return 0;
}
注意:调用函数时需结构体传址,因为:
1-传值的话,调用函数时,main函数和接口函数分别开辟栈帧,形参是实参的拷贝,改变形参不影响实参,调用函数,形参实例化(本质是给临时变量开辟空间,将拷贝后的形参放入空间),形参是实参的拷贝,二者开辟不同栈帧,占据不同空间,改变形参不影响实参。
2-函数传参时,参数是需要压栈,会有时间和空间上的系统开销。如果传递一个结构体对象时(传值),结构体过大,参数压栈的系统开销比较大,所以会导致性能的下降。
总结
这里对文章进行总结: 以上就是今天总结的内容,本文包括了C语言实现动态顺序表各个接口,分享给大家。 真💙欢迎各位给予我更好的建议,欢迎访问!!!小编创作不易,觉得有用可以一键三连哦,感谢大家。peace 希望大家一起坚持学习,共同进步。梦想一旦被付诸行动,就会变得神圣。
欢迎各位大佬批评建议,分享更好的方法!!!🙊🙊🙊
|