最最简单的数据结构线性表——顺序表(数据结构C语言实现2)

简介: 最最简单的数据结构线性表——顺序表(数据结构C语言实现2)

本节目标

了解线性表结构

能够自己实现顺序表

顺序表oj题

1.线性表概念

1线性表线性表(linear list)


是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。


数组结构形式

image.png

链表结构形式

image.png

我们今天来实现顺序表结构,即数组结构形式的顺序表。

2.顺序表实现

3.顺序表相关OJ题练习


顺序表实现

概念


顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。


结构


1 静态顺序表:使用定长数组存储。

2 动态顺序表:使用动态开辟的数组存储。

静态顺序表

顺序表都以数组形式,静态顺序表示定长数组。


//顺序表的静态存储
    #define N 7   //定长为7个元素的顺序表
    typedef int SLDataType;
    typedef struct SeqList 
    {
        SLDataType array[N];  //定长数组
        size_t size;   //有效元素个数
    }SeqList;

image.png

这就是静态顺序表,

很明显当顺序表能存下数据的个数是有限的。所以极其不便。我们静态顺序表就介绍到这。


动态顺序表

//顺序表的动态存储
    typedef int SLDataType;
    typedef struct SeqList 
    {
        SLDataType *array;  //指向动态开辟的数组
        size_t size;   //有效元素个数
        size_t capicity; //容量空间大小 
    }SeqList;

image.png

如何实现动态开辟数呢?


void *malloc( size_t size );

<stdlib.h>


Allocates memory blocks.

这是个动态开辟内存空间的函数。

函数的返回值:void*无类型的指针,需要根据自己开辟数据类型的指针强制转换。

函数的常数:size_t字节大小,根据自己需要开辟空间大小。


接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表。


线性表就是存数据的一种数据结构,而增删查改等接口的实现是这种数据结构的学习的基础!


// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* array;  // 指向动态开辟的数组
size_t size ;       // 有效数据个数
size_t capicity ;   // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);
// 检查空间,如果满了,进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表初始化
void SeqListInit(SeqList* psl)
{
  psl->array = NULL;
  psl->size = 0;
  psl->capacity = 0;
}
// 顺序表销毁
void SeqListDestory(SeqList* psl)
{
  free(psl->array);   //释放空间,防止内存泄漏
  psl->array = NULL;
}
// 顺序表打印
void SeqListPrint(SeqList* psl)
{    
  int i = 0;
  for(i=0;i<psl->size;i++)
  { 
   printf("%d ",psl->array[i]);
  }
  printf("\n");
}
// 检查空间,如果满了,进行增容
void SeqListCheckCapacity(SeqList* psl)
{
  // 满了就要扩容
  if (psl->size == psl->capacity)
  {
  int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
  SLDataType* tmp = (SLDataType*)realloc(psl->array, newcapacity * sizeof(SLDataType));
  if (tmp == NULL)
  {
    printf("realloc fail\n");
    exit(-1);
  }
  else
  {
    psl->array = tmp;
    psl->capacity = newcapacity;
  }
  }
}
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
  SeqListCheckCapacity(psl);
  psl->array[psl->size] = x;
  psl->size++;
}

image.png

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
  SeqListCheckCapacity(psl);
  int i = 0;
  for (i = psl->size; i >0; i--)
  {
   psl->array[i]=psl->array[i-1];
  }
  psl->array[i] = x;
  psl->size++;
}

image.png

//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
  psl->size--;
}

image.png

// 顺序表头删
void SeqListPopFront(SeqList* psl)
{
  int end = 0;
  while (end<psl->size)
  {
  psl->array[end] = psl->array[end+1];
  end++;
  }
  psl->size--;
}

image.png

// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x)
{
  if (psl == NULL)
  return 0;
  int i = 0;
  for (i = 0; i < psl->size; i++)
  {
  if (psl->array[i] == x)
  {
    printf("找到了、下标为:%d\n", i);
    return i;
     }
  }
  printf("找不到\n");
  return -1;
}

image.png


// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
  SeqListCheckCapacity(psl);
  if (psl->size > pos)
  {
  int i = 0;
  for (i = psl->size; i>pos; i--)
  {
    psl->array[i] = psl->array[i - 1];
  }
  psl->array[i] = x;
  psl->size++;
  }
  else
  {
  printf("该位置不存在\n");
  }
}

image.png

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
  if (psl == NULL)
  return 0;
  if (psl->size > pos)
  {
  int i = 0;
  for (i = pos; i < psl->size-1; i++)
  {
    psl->array[i] = psl->array[i + 1];
  }
  psl->size--;
  }
}

image.png

bug郭
+关注
目录
打赏
0
0
0
0
9
分享
相关文章
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
69 1
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
69 4
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
56 4
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
57 4
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
27 5
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
89 5
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
83 1
|
2月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
287 9
|
2月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
44 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等