顺序表的（增删查改）实现
一、线性表
1.线性表的概念
具有n个相同特性的数据元素的有限序列，顺序表，链表 ，栈和队列都是 常见的线性表
在这里插入图片描述
2.顺序表的概念 顺序表是物理地址连续的储存单元依次存储数据元素的线性结构， 一般采用数组储存，在数组上完成增删查改。 分为静态与动态两种： 静态：使用定长数组实现 动态:使用动态开辟的数组实现
这两者跟之前的通讯录的有点相似 可以看这里 ：通讯录
3.顺序表的优缺点
1.优点
1.支持随机访问
2.缺点
1.中间插入或者头插时,会很慢，要挪动数据，时间复杂度为O(N) 2.虽然说动态顺序表已经做出优化，但扩容时，依旧会造成一定的空间浪费
二、顺序表的实现
1.函数的定义和结构体的创建--contact.h
#include<stdlib.h>
#include<stdio.h>
typedef int type;
struct s
{
type* data;//动态开辟
int size;//记录数量
int cap;//容量大小
};
void SeqListinit(struct s* p);
void SeqListpushBack(struct s* p, int x);
void SeqListprint(struct s* p);
void SeqListpopBack(struct s* p);
void SeqListpushFront(struct s* p,int x);
void SeqListpopFront(struct s* p);
void checkcap(struct s* p);
int search(struct s* p, int pos);
void SeqListInsert(struct s* p, int pos, int x);
void SeqListErase(struct s* p, int pos);
void seqListdestory(struct s* p);2.函数的调用---test.c
#include"contact1.h"
int main()
{
struct s p;
SeqListinit(&p);
SeqListpushBack(&p, 1);
SeqListpushBack(&p, 2);
SeqListpushBack(&p, 3);
SeqListpushBack(&p, 4);
SeqListprint(&p);
SeqListpopBack(&p);
SeqListprint(&p);
SeqListpushFront(&p, 5);
SeqListprint(&p);
SeqListpopFront(&p);
SeqListprint(&p);
int pos=search(&p, 3);
SeqListInsert(&p, pos, 5);
SeqListprint(&p);
int pos2= search(&p, 5);
SeqListErase(&p, pos2);
SeqListprint(&p);
seqListdestory(&p);
return 0;
}3.动态顺序表的接口
1.尾插
void seqlistpushback(struct s*p,int x)
{
if(p->size==p->cap)//如果此时的数量等于容量
{
type*str=(type*)malloc(sizeof(type)*2*p->cap);//扩容2倍
if(str!=NULL)
{
p->data=str;
p->cap=2*p->cap;
}
}
p->data[p->size]=x;
p->size++;
}2.尾删
void SeqListpopBack(struct s* p)//尾删
{
p->size--;
}3.头插
void SeqListpushFront(struct s* p, int x)//同理在物理上是连续的
{//所以在头插入数据，就必须将所有数据向后移
int i = 0;
if (p->size == p->cap)//扩容
{
type* str = (type*)realloc(p->data, sizeof(type) * 2 * p->cap);
if (str != NULL)
{
p->data = str;
p->cap = 2 * p->cap;
}
}
for (i = p->size; i >=0; i--)//数据向后移
{
p->data[i + 1] = p->data[i];
}
p->data[0] = x;
p->size++;
}4.头删
void SeqListpopFront(struct s* p)//头删
{
int i = 0;//直接将第二个数据赋值给第一个数据即可
for (i = 0; i < p->size-1; i++)
{
p->data[i] = p->data[i + 1];
}
p->size--;
}5.查找指定位置
int search(struct s* p, int pos)//查找指定位置
{
int i = 0;
for (i = 0; i < p->size; i++)//如果找到这个数 返回这个数的下标
{
if (p->data[i] == pos)
{
return i ;
}
}
}6.指定插
void SeqListInsert(struct s* p, int pos, int x)//指定插
{
if (p->size == p->cap)//扩容
{
type* str = (type*)realloc(p->data, sizeof(type) * 2 * p->cap);
if (str != NULL)
{
p->data = str;
p->cap = 2 * p->cap;
}
}
int i = 0;
for (i = p->size; i >=pos; i--)//从后往前找这个数，并将数依次向后移
{
p->data[i + 1] = p->data[i];
}
p->data[pos] = x;
p->size++;
}7.指定删
void SeqListErase(struct s* p, int pos)//指定删
{
int i = 0;
for (i = pos; i < p->size-1; i++)//从前往后，从要删除的数开始，把后面的数赋值给前面的数
{
p->data[i] = p->data[i + 1];
}
p->size--;
}8.初始化
void SeqListinit(struct s* p)//初始化
{
p->cap= 5;//假设容量为5
p->size = 0;
p->data= (type*)malloc(p->cap*sizeof(type));
}9.内存销毁
void seqListdestory(struct s* p)//内存销毁
{
free(p->data);//动态开辟要记得销毁 ，否则会造成内存泄漏
p->data = NULL;
p->size = 0;
p->cap = 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-09-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
