4
顺序表的（增删查改）实现_萌新的日常的技术博客_51CTO博客
source link: https://blog.51cto.com/u_15787387/5693627
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
顺序表的（增删查改）实现
推荐 原创一、线性表
1.线性表的概念
具有n个相同特性的数据元素的有限序列，顺序表，链表 ，栈和队列都是
常见的线性表
2.顺序表的概念
顺序表是物理地址连续的储存单元依次存储数据元素的线性结构，
一般采用数组储存，在数组上完成增删查改。
分为静态与动态两种：
静态：使用定长数组实现
动态:使用动态开辟的数组实现
这两者跟之前的通讯录的有点相似
可以看这里 ： 通讯录
3.顺序表的优缺点
1.支持随机访问
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.动态顺序表的接口
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++;
}
void SeqListpopBack(struct s* p)//尾删
{
p->size--;
}
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++;
}
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;
}
- 赞
- 收藏
- 评论
- 分享
- 举报
上一篇：时间复杂度与空间复杂度
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK