延庆免费网站建设,wordpress post meta,营销策划的流程,唐山建设信息网站目录 1. 线性表2.顺序表3.顺序表的优缺点4.实现#xff08;C语言#xff09;4.1 头文件 seqList.h4.2 实现 seqList.c 1. 线性表 线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构#xff0c;常见… 目录 1. 线性表2.顺序表3.顺序表的优缺点4.实现C语言4.1 头文件 seqList.h4.2 实现 seqList.c 1. 线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储
2.顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储在数组上完成数据的增删查改。
顺序表一般可以分为
静态顺序表使用定长数组存储元素。动态顺序表使用动态开辟的数组存储。 静态顺序表只适用于确定知道需要存多少数据的场景静态顺序表的定长数组长度N定大了空间开多了浪费开少了不够用。所以基本都是使用动态顺序表根据需要动态的分配空间大小。
3.顺序表的优缺点
缺点增删改速度慢。
中间 / 头部的插入删除时间复杂度为O(N)。增容需要申请新空间拷贝数据释放旧空间会有不小的消耗。增容一般是呈1.5或2倍的增长势必会有一定的空间浪费。
优点有数组索引查询速度快。
4.实现C语言
4.1 头文件 seqList.h
#pragma once#include stdlib.h
#include assert.h
#include string.h// 初始大小
#define STD_SIZE 4// 顺序表数据类型
typedef int seqListDataType;// 顺序表
typedef struct SeqList
{seqListDataType* list;int size; // 有效数据个数int cap; // 顺序表容量
} SeqList;// 初始化销毁
void init(SeqList* psl);
void destroy(SeqList* psl);// 扩容
void checkResize(SeqList* psl);// 头插头删尾插尾删
void addFront(SeqList* psl, seqListDataType ele);
void removeFront(SeqList* psl);
void addBack(SeqList* psl, seqListDataType ele);
void removeBack(SeqList* psl);// 指定位置[0-size1插入[0~size删除
void insert(SeqList* psl, int pos, seqListDataType ele);
void erase(SeqList* psl, int pos);4.2 实现 seqList.c
#define _CRT_SECURE_NO_WARNINGS 1#include seqlist.h// 初始化
void init(SeqList* psl)
{assert(psl);psl-list NULL;psl-size 0;psl-cap 0;
}// 销毁
void destroy(SeqList* psl)
{assert(psl psl-list);free(psl-list);psl-list NULL;psl-size 0;psl-cap 0;
}// 检查容量并扩容
static void checkResize(SeqList* psl)
{if (psl-size psl-cap) {int newCap psl-size 0 ? STD_SIZE : psl-cap * 2;seqListDataType* tmpList realloc(psl-list, newCap * sizeof(seqListDataType));if (tmpList ! NULL){psl-list tmpList;psl-cap newCap;// 只将扩容的内存置0memset((psl-list) psl-size, 0, psl-size * sizeof(seqListDataType));}else{perror(checkCap(SqList* psl) realloc error);}}
} // 头插
void addFront(SeqList* psl, seqListDataType data)
{assert(psl);checkResize(psl);// 所有元素往后挪1位for (int i psl-size - 1; i 0; i--){psl-list[i 1] psl-list[i];}psl-list[0] data;psl-size;
}// 头删
void removeFront(SeqList* psl)
{assert(psl psl-size 0);// 第2个元素开始所有元素往前挪1位for (int i 1; i psl-size; i){psl-list[i - 1] psl-list[i];}psl-list[psl-size - 1] 0;psl-size--;
}// 尾插
void addBack(SeqList* psl, seqListDataType data)
{assert(psl);checkResize(psl);psl-list[psl-size] data;psl-size;
}// 尾删
void removeBack(SeqList* psl)
{assert(psl psl-size 0);psl-list[psl-size - 1] 0;psl-size--;
}// 指定位置[0-size1插入
void insert(SeqList* psl, int pos, seqListDataType ele)
{ assert(psl);checkResize(psl);assert(pos 0 pos psl-size 1);// 从插入位置开始所有元素向后挪动1位for (int i psl-size - 1; i pos; i--){psl-list[i 1] psl-list[i];}psl-list[pos] ele;psl-size;
}// 指定位置[0~size删除
void erase(SeqList* psl, int pos)
{assert(psl pos 0 pos psl-size);// 从删除位置开始所有元素往前移动1位for (int i pos; i psl-size; i){psl-list[i] psl-list[i 1];}psl-list[psl-size - 1] 0;psl-size--;
}
