顺序表的（增删查改）实现

作者：lovevivi

2022-10-22
吉林
本文字数：1865 字
阅读完需：约 6 分钟

@TOC

一、线性表

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;}

复制代码

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/8f37ae5bd233cb4753f8ab14a】。文章转载请联系作者。

lovevivi

关注

还未添加个人签名 2022-10-12 加入

还未添加个人简介

发布

暂无评论

创作场景

顺序表的（增删查改）实现

一、线性表

1.线性表的概念

2.顺序表的概念

3.顺序表的优缺点

1.优点

2.缺点

二、顺序表的实现

1.函数的定义和结构体的创建--contact.h

2.函数的调用---test.c

3.动态顺序表的接口

1.尾插

2.尾删

3.头插

4.头删

5.查找指定位置

6.指定插

7.指定删

8.初始化

9.内存销毁

lovevivi

评论