顺序表的实现(迈入数据结构的大门)(2)

简介: 顺序表的实现(迈入数据结构的大门)(2)

书接上文

顺序表的头插(SLPushFront)

头插:

对于头插,我们需要先将数组头部的位置空余出来存放我们需要插入的数x;

所以我们需要将数组中的数向后移一位;

此时:我们有两个思路(数组移位)

1、从下标为0开始向后置换,此时会出现数值覆盖的问题,我们需要另创建一个变量(tmp)存放后一个值以防覆盖之后寻找不到;当tmp的下一个数组为NULL时;怎么办了?

这就要if语句判断或者使用while语句,那有什么方法能将此简化呢:这就来到第二个方法;

2、我们从数组末尾进行移位,这就防止了数值覆盖的问题,还不需要使用到其余语句的创建;

//头插
void SLPushFront(SL* ps, SLDataType x){
//记住SLDataType,这里为我们为了方便(typedef int SLDataType)
  assert(ps);//断言一下,防止指针为空
  SLCheckCapacity(&ps);//开辟空间
  int i = ps->size;
  for (; i > 0; i--);//从后往前移位
  {
    ps->a[i] = ps->a[i - 1];
  }
  ps->a[0] = x;//此时a[0]就空出来存放x;
  ps->size++;//不要忘记size需要++
}

顺序表的头删(学会思维的变换)(SLPopFront)

对于头删,我们需要删除下标为0的值,然后将值向前移一位,与头插类似,只不过,此时是从前往后移动;

//头删
void SLPopFront(SL* ps) {
  assert(ps);
  assert(ps->size);//存放的值不能为NULL;
  for (int i = 0; i < ps->size-1; i++) {
    ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}

顺序表的尾插(SLPushBack)

当我们学会了头插,顺序表的尾插相对我们来说,简直轻而易举

尾插:我们就要先判断是否还有空余位置,就要利用SLCheckCapacity(SL* ps);是否需要扩容

此时ps->size的位置如图所示,我们就可以直接将x的值赋给当前位置,然后ps->size++;

//尾插
void SLPushBack(SL* ps, SLDataType x) {
  assert(ps);
  void SLCheckCapacity(SL * ps);
  ps->a[ps->size++] = x;
  //相当于ps->a[ps->size] = x;
  //ps->size++;
}

有尾插就有尾删

思考一下,尾删,我们将ps->size-1的位置删除:将其置为NULL,ps->size--,就完成了尾删;

那我们换一个思路,我们只将这个位置删除,是否可以,直接ps->size--呢:因为当我们打印的时候只需打印[0,size)之间的数,size这个位置需要打印吗?当然不用啦;如果我们需要尾插的时候呢,我们可以直接将此位置覆盖掉;

//尾删
void SLPopBack(SL* ps) {
  assert(ps);
  assert(ps->size);//进行尾删,必须存在尾删的值
  ps->size--;
}

既然头与尾部的插入与删除都有,那必然少不了指定位置的插入删除

查找目标值

对于查找数组中的值时,一般使用遍历查询;

//查找
int SLFind(SL* ps, SLDataType x) {
  assert(ps);
  for (int i = 0; i < ps->size; i++) {//对数组进行遍历
    if (ps->a[i] == x) {
      return i;
    }
  }
  return -1;//循环结束,没有找到,返回-1;
}

指定位置插入(SLInsert)

指定位置插入与头插相似,需要将指定位置后的值向后移移位,在进行插入;

//注意:这里的pos对应数组下标

//指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x) {
  assert(ps);
  assert(pos >= 0 && ps->size > pos);//pos必须在含有值之间插入
  //插入数据:空间够不够
  SLCheckCapacity(ps);
  //让pos及之后的数据整体往后挪动一位
  for (int i = ps->size; i > pos; i--)
  {
    ps->a[i] = ps->a[i - 1];//a[pos+1] = a[pos]与头插具有相似之处,导致值的覆盖
  }
  ps->a[pos] = x;//这里的pos对应,数组下标,如果不对应,则按情况+-;
  ps->size++;
}

指定位置删除(SLErase)

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);
  //与头删类似
  for (int i = pos; i < ps->size - 1; i++)
  {
    ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}

打印(顺序表的结尾之声)

这里我们要注意结构体访问成员的方式 ( . )  ( -> )

C语言结构体—自定义类型—struct-CSDN博客

void SLPrint(SL s)//对于打印数组,这里不再需要传地址,而是传值
{
  for (int i = 0; i < s.size; i++)
  {//对于结构体的使用  (.)与(->)的不同
    printf("%d ", s.a[i]);
  }
  printf("\n");
}

完整顺序表代码

seqlist.h

#pragma once
typedef int SLDataType;
 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef struct SeqList
{
  SLDataType* a;
  int size; // 有效数据个数
  int capacity; // 空间容量
}SL;
 
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插?删除 / 尾部插?删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插?/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

seqlist.c

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include"seqlist.h"
 
//typedef int SLdataTapy;
//#define N  10
//
//typedef struct seqlist {
//  SLdataTapy arr[N];//定长数组
//  int size;//有效数组个数
//}SL;
 
 
//typedef int SLdataTapy;
//
//typedef struct seqlist {
//  SLdataTapy* a;//用来开辟动态内存
//  int size;//有效数组个数
//  int capacity;//剩余容量;判断是否需要新添加内存
//}SL;
 
//初始化和销毁
void SLInit(SL* ps) {
  ps->a = NULL;
  ps->size = ps->capacity = 0;
}
 
void SLDestroy(SL* ps) {
  if (ps->a) {//判断数组中是否为空
    free(ps->a);//因为需要使用malloc,所以需要注意释放内存
  }
  ps->a = NULL;
  ps->size = ps->capacity = 0;
}
 
//扩容
void SLCheckCapacity(SL* ps) {
  //先要判断内存够不够
  if (ps->size == ps->capacity) {
    //使用malloc relloc celloc
    int newcappacity = ps->capacity == 0 ? 4 :ps->capacity*2;//一般增容原来内存的二到三倍;
    SLDataType*tmp = (SLDataType*)relloc(ps->a,newcappacity * sizeof(SLDataType));
    //注:这里没有直接使用ps->a直接申请,是为了防止内存申请失败;防止数据丢失
    if (tmp == NULL) {//也可以使用assert直接终止程序;需要使用aseert.h的头文件
      perror("relloc fail");
      exit(1);//直接退出程序;也可使用return;
    }
    //空间增容成功
    ps->a = tmp;
    ps->capacity = newcappacity;
  }
}
//头插
void SLPushFront(SL* ps, SLDataType x) {
  //记住SLDataType,这里为我们为了方便(typedef int SLDataType)
  assert(ps);//断言一下,防止指针为空
  SLCheckCapacity(&ps);//开辟空间
  int i = ps->size;
  for (; i > 0; i--);//从后往前移位
  {
    ps->a[i] = ps->a[i - 1];
  }
  ps->a[0] = x;//此时a[0]就空出来存放x;
  ps->size++;//不要忘记size需要++
}
//头删
void SLPopFront(SL* ps) {
  assert(ps);
  assert(ps->size);//存放的值不能为NULL;
  for (int i = 0; i < ps->size-1; i++) {
    ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}
//尾插
void SLPushBack(SL* ps, SLDataType x) {
  assert(ps);
  void SLCheckCapacity(SL * ps);
  ps->a[ps->size++] = x;
  //相当于ps->a[ps->size] = x;
  //ps->size++;
}
//尾删
void SLPopBack(SL* ps) {
  assert(ps);
  assert(ps->size);//进行尾删,必须存在尾删的值
  ps->size--;
}
 
//查找
int SLFind(SL* ps, SLDataType x) {
  assert(ps);
  for (int i = 0; i < ps->size; i++) {
    if (ps->a[i] == x) {
      return i;
    }
  }
  return -1;
}
//指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x) {
  assert(ps);
  assert(pos >= 0 && ps->size > pos);//pos必须在含有值之间插入
  //插入数据:空间够不够
  SLCheckCapacity(ps);
  //让pos及之后的数据整体往后挪动一位
  for (int i = ps->size; i > pos; i--)
  {
    ps->a[i] = ps->a[i - 1];//a[pos+1] = a[pos]与头插具有相似之处,导致值的覆盖
  }
  ps->a[pos] = x;//这里的pos对应,数组下标,如果不对应,则按情况+-;
  ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);
  //与头删类似
  for (int i = pos; i < ps->size - 1; i++)
  {
    ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}
void SLPrint(SL s)//对于打印数组,这里不再需要传地址,而是传值
{
  for (int i = 0; i < s.size; i++)
  {//对于结构体的使用  (.)与(->)的不同
    printf("%d ", s.a[i]);
  }
  printf("\n");
}

以上我们完成了顺序表的实现,下一节我们将实现(通讯录)顺序表


看到这里就点个赞走吧!!!



相关文章
|
2月前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
57 2
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
66 3
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
2月前
|
存储
数据结构(顺序表)
数据结构(顺序表)
28 0
|
2月前
|
存储 算法
【数据结构】新篇章 -- 顺序表
【数据结构】新篇章 -- 顺序表
16 0
|
2月前
|
存储 测试技术
探索数据结构:顺序表的实现与应用
探索数据结构:顺序表的实现与应用
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
140 9
|
26天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
24 1
|
13天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
33 5