数据结构入门(C语言版)线性表中顺序表介绍及接口实现(上)

简介: 不论在程序员的工作上,还是在学习或是考研上,数据结构都是一门非常重要且值得我们一直研究探索的学科,可以说数据结构和算法就是编程的核心。OK,接下来我们来到数据结构的入门第一步就是学习线性表,接下来由作者来详细介绍数据结构第一章线性表。

d8f6065f8366462eb74ef189278b2373.png


数据结构入门之线性表


C语言的学习结束,就该入门数据结构了呦


不论在程序员的工作上,还是在学习或是考研上,数据结构都是一门非常重要且值得我们一直研究探索的学科,可以说数据结构和算法就是编程的核心。OK,接下来我们来到数据结构的入门第一步就是学习线性表,接下来由作者来详细介绍数据结构第一章线性表。


一、线性表


1、什么是线性表?


维基百科:线性表(英语:Linear List)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列。


你可以理解为零个或多个数据元素的有限序列。


线性表的数据集合为{a1,a2,…,an},其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。


在较复杂的线性表中,一个数据元素可以由若干个数据项组成。


2、线性表的存储结构


线性表的可按照顺序存储结构形成顺序表,或者按照链式结构形成链式表。

这里我们先介绍顺序表


二、顺序表


1、 顺序表基本概念


定义:用一组地址连续的存储单元依次存储线性表的数据元素,这种存储结构的线性表称为顺序表。


特征:逻辑上相邻的数据元素,物理次序也是相邻的。


优缺点:


①随机访问:只要确定好了存储线性表的起始位置,线性表中任一数据元素都可以随机存取(数据读写所需的时间与存储位置无关)。在O(1)的时间内找到第 i 个元素。代码上以数组 (序号读取地址) 的方式实现。


②存储密度高:每个节点只存储数据元素。


③静态拓展容量不方便,动态拓展容量易造成空间浪费。


④插入、删除数据不方便,需要移动大量数据。


2、静态顺序表结构体定义


#define N 100
typedef int SeqDataType;
typedef struct Seqlist
{
  SeqDataType a[N];//定值数组
  int size;//表示数组中存储了多少个数据
}SeqList;


静态特点:如果满了就不让插入

缺点:给多少空间不确定 给小了不够用,给大了浪费

一般不推荐,在现实中运用少,但适合初学者练习顺序表的建立


3、动态顺序表结构体定义


typedef int SeqDataType;
typedef struct SeqList
{
  SeqDataType* a;//指向动态开辟的数组指针
  int size;      // 有效数据的个数
  int capacity;  // 容量
}SeqList; 


动态特点:将静态的定值数组改为了可以接收动态开辟内存地址的指针,且增加了一个变量capacity表示容量。

我们这里使用动态顺序表结构体来定义接口函数


三、顺序表接口实现


1、头文件的结构体建立和接口函数声明


typedef int SeqDataType;
typedef struct SeqList
{
  SeqDataType* a;
  int size;      
  int capacity;
}SeqList;
void SeqListInit(SeqList* pq);//初始化
void SeqListCheckCapacity(SeqList* ps);//检查扩容
void SeqListPushBack(SeqList* pq, SeqDataType x);//尾插
void SeqListPushFront(SeqList* pq, SeqDataType x);//头插
void SeqListPopBack(SeqList* pq);//尾删
void SeqListPopFront(SeqList* pq);//头删
int SeqListFind(SeqList* pq, SeqDataType x);//查找
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//任意位置插入
void SeqListErase(SeqList* pq, int pos);//任意位置删除
void SeqListModify(SeqList* pq, int pos, SeqDataType x);//修改
void SeqListPrint(SeqList* pq);//打印
void SeqListDestory(SeqList* pq);//销毁


2、接口函数代码实现


A、初始化接口函数


void SeqListInit(SeqList* pq)
{
  assert(pq);
  pq->a = NULL;
  pq->size = pq->capacity = 0;
}


初始化即将指针置空,长度容量初始化为0。


B、检查扩容接口函数


void SeqCheckCapacity(SeqList* pq)
{
  // 满了,需要增容
  if (pq->size == pq->capacity)
  {
    int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
    SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType)*newcapacity);
    if (newA == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    pq->a = newA;
    pq->capacity = newcapacity;
  }
}


在这里作者用了一个三目操作符判定空间如果为空则增加4个整形空间,若满则以2倍增容,这样不容易造成空间浪费,当然,随着数组长度越来越大,你会发现浪费依然存在且越来越大,实际上这也就是我们在前面提到的线性表的缺点,这是不可避免的,在后面我们学到的链表就很好的弥补了这个缺陷。


C、尾部插入接口函数


void SeqListPushBack(SeqList* pq, SeqDataType x)
{
  assert(pq);
  SeqCheckCapacity(pq);
  pq->a[pq->size] = x;
  pq->size++;
}


尾插在顺序表中是最好实现的,直接增加一位插入即可。

相关文章
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
71 1
|
2月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
73 4
|
2月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
56 4
|
16天前
|
存储 算法 测试技术
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
39 7
|
16天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
31 5
|
16天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
31 5
|
2月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
91 5
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
84 1
|
2月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
292 9
|
2月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
45 1