AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构之顺序表详解(二)

2023-06-10 680
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 今天给大家带来的是数据结构的顺序表结构，以及与其的有关功能的实现，在数据结构的这部分内容，可能有些知识点有点难以理解，在需要时小编会配合图画，让大家能够更好的理解，那么下面就让我们直接步入正题吧。

2.7 顺序表从前删除数据

void SeqListPopFront(SeqList* ps)
{
  assert(ps);
  assert(ps->size > 0);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
  ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}

删除第一个首元素，实际上就是把第一个元素后面的元素一次从前覆盖，然后对有效数据个数-1，即可


运行测试：


void text2()
{   
  SeqList s;
  SeqListInit(&s);
  SeqListPushFront(&s, 1);
  SeqListPushFront(&s, 2);
  SeqListPushFront(&s, 3);
  SeqListPushFront(&s, 4);
  SeqListPrint(&s);
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPrint(&s);
}
int main()
{
  text2();
  return 0;
}


结果如下:

image.png



2.8 查找功能实现

int SeqListFind(SeqList* ps, SLDateType x)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
  if (ps->a[i] == x)
  {
    return i;
  }
  }
  return -1;
}

这里我们是以内容查找，对有效的数据进行循环，找到内容一致的元素就返回该下标，否则返回-1。


运行测试：

void text3()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SLDateType x = 0;
  printf("输入你要查找的内容>");
  scanf("%d", &x);
  int i = SeqListFind(&s, x);
  printf("你所查找的元素在：%d", i);
}
int main()
{
  text3();
  return 0;
}


结果如下：

image.png



2.9  顺序表在pos位置插入

void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
  assert(ps);
  assert(pos >= 0 && pos <ps->size);
  SLCheckCapacity(ps);
  int i = 0;
  for (i = ps->size; i >=pos; i--)
  {
  ps->a[i + 1] = ps->a[i];
  }
  ps->a[pos] = x;
  ps->size++;
}

对于pos的大小范围要求是0~ps->size，既然要在pos位置插入那么我们就行需要将pos之后的有效元素后移，然后再给pos位置赋值要插入的内容。


运行测试：

void text4()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPrint(&s);
  SeqListInsert(&s, 1, 5);
  SeqListInsert(&s, 2, 6);
  SeqListPrint(&s);
}
int main()
{
  text4();
  return 0;
}

结果如下：

image.png



2.10  顺序表在pos位置删除

void SeqListErase(SeqList* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  int i = 0;
  for (i = pos+1; i < ps->size; i++)
  {
  ps->a[i-1] = ps->a[i];
  }
  ps->size--;
}

这里和上面头删除的原理相同，只是这里是将pos位置之后的值进行覆盖。


运行测试：


void text4()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPrint(&s);
  SeqListInsert(&s, 1, 5);
  SeqListInsert(&s, 2, 6);
  SeqListPrint(&s);
  SeqListErase(&s, 2);
  SeqListErase(&s, 3);
  SeqListPrint(&s);
}
int main()
{
  text4();
  return 0;
}
结果如下：
 总代码：
 text.c
#include"Sqlist.h"
void text1()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s,1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPrint(&s);
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPrint(&s);
}
void text2()
{   
  SeqList s;
  SeqListInit(&s);
  SeqListPushFront(&s, 1);
  SeqListPushFront(&s, 2);
  SeqListPushFront(&s, 3);
  SeqListPushFront(&s, 4);
  SeqListPrint(&s);
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPrint(&s);
}
void text3()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SLDateType x = 0;
  printf("输入你要查找的内容>");
  scanf("%d", &x);
  int i = SeqListFind(&s, x);
  printf("你所查找的元素在：%d", i);
}
void text4()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPrint(&s);
  SeqListInsert(&s, 1, 5);
  SeqListInsert(&s, 2, 6);
  SeqListPrint(&s);
  SeqListErase(&s, 2);
  SeqListErase(&s, 3);
  SeqListPrint(&s);
}
int main()
{
  text4();
  return 0;
}
Sqlist.c
#include<stdio.h>
#include"Sqlist.h"
void SeqListInit(SeqList* ps)
{
  assert(ps);
  ps->size = 0;
  ps->a = (SLDateType*)malloc(sizeof(SLDateType) * INIT_CAPACITY);
  if (ps->a == NULL)
  {
  perror("malloc fail");
  return;
  }
  ps->capacity = INIT_CAPACITY;
}
void SeqListDestroy(SeqList* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
void SLCheckCapacity(SeqList* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
  SLDateType* temp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
  if (temp == NULL)
  {
    perror("realloc fail");
    return;
  }
  ps->a = temp;
  ps->capacity *= 2;
  }
}
void SeqListPrint(SeqList* ps)
{
  assert(ps);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
  printf("%d ", ps->a[i]);
  }
  printf("\n");
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  ps->a[ps->size++] = x;
}
void SeqListPopBack(SeqList* ps)
{  
  assert(ps);
  assert(ps->size > 0);
  ps->size--;
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{    
  assert(ps);
  SLCheckCapacity(ps);
  int i = 0;
  for (i = ps->size; i >=0; i--)
  {
  ps->a[i + 1] = ps->a[i];
  }
  ps->a[0] = x;
  ps->size++;
}
void SeqListPopFront(SeqList* ps)
{
  assert(ps);
  assert(ps->size > 0);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
  ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}
int SeqListFind(SeqList* ps, SLDateType x)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
  if (ps->a[i] == x)
  {
    return i;
  }
  }
  return -1;
}
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
  assert(ps);
  assert(pos >= 0 && pos <ps->size);
  SLCheckCapacity(ps);
  int i = 0;
  for (i = ps->size; i >=pos; i--)
  {
  ps->a[i + 1] = ps->a[i];
  }
  ps->a[pos] = x;
  ps->size++;
}
void SeqListErase(SeqList* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  int i = 0;
  for (i = pos+1; i < ps->size; i++)
  {
  ps->a[i-1] = ps->a[i];
  }
  ps->size--;
}
Sqlist.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define INIT_CAPACITY 4
typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* a;
  int size;
  int capacity;
}SeqList;
// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);
void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);


关键词：
数据结构顺序表
半只牛马
目录
相关文章
是基德吖
|
2月前
|
存储 C语言
【数据结构】顺序表
数据结构中的动态顺序表
是基德吖
35 3
【数据结构】顺序表
秋刀鱼不做梦
|
3月前
|
存储
数据结构—顺序表（如果想知道顺序表的全部基础知识点，那么只看这一篇就足够了！）
数据结构—顺序表（如果想知道顺序表的全部基础知识点，那么只看这一篇就足够了！）
秋刀鱼不做梦
45 1
2的n次方_
|
3天前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表（Arraylist）
Java集合框架主要由接口、实现类及迭代器组成，包括Collection和Map两大类。Collection涵盖List（有序、可重复）、Set（无序、不可重复），Map则由键值对构成。集合通过接口定义基本操作，具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复，Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现，各有适用场景。其中ArrayList实现了动态数组功能，可根据需求自动调整大小。
2的n次方_
24 11
sky_qiyi
|
3月前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表（双向带头循环链表）的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表（双向带头循环链表）的优缺点、CPU高速缓存命中率
sky_qiyi
38 0
小徐在进步
|
11天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
42 5
小徐在进步
|
11天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
13 1
国中之林
|
1月前
|
存储 算法
【数据结构与算法】顺序表
【数据结构与算法】顺序表
国中之林
13 0
【数据结构与算法】顺序表
aliyun6365824167
|
1月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
16 0
aliyun6365824167
|
1月前
|
存储 测试技术
【初阶数据结构篇】顺序表的实现（赋源码）
线性表（linearlist）是n个具有相同特性的数据元素的有限序列。
aliyun6365824167
17 0
睡觉待开机
|
1月前
|
存储 编译器
【数据结构】顺序表(长期维护)
【数据结构】顺序表(长期维护)
睡觉待开机
15 0