数据结构入门(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++;
}


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

相关文章
|
10月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
867 9
|
5月前
|
存储 前端开发 Java
线性数据结构详解
本文介绍了线性数据结构中的核心概念——节点,以及基于节点构建的链表、队列和栈等重要数据结构。节点是计算机科学中基本的构建单元,包含数据和指向其他节点的链接。通过添加约束或行为,可以构建出单向链表、双向链表、队列和栈等复杂结构。
146 1
|
8月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
9月前
|
存储 NoSQL 编译器
【C语言】指针的神秘探险:从入门到精通的奇幻之旅 !
指针是一个变量,它存储另一个变量的内存地址。换句话说,指针“指向”存储在内存中的某个数据。
300 7
【C语言】指针的神秘探险:从入门到精通的奇幻之旅 !
|
8月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
188 5
|
8月前
|
存储 编译器 C语言
【C语言程序设计——入门】C语言入门与基础语法(头歌实践教学平台习题)【合集】
本文档介绍了C语言环境配置和编程任务,主要内容包括: - **C语言环境配置**:详细讲解了在Windows系统上配置C语言开发环境的步骤。 - **第1关:程序改错**:包含任务描述、相关知识(如头文件引用、基本语法规则)、编程要求、测试说明及通关代码。 - **第2关:scanf函数**:涉及`scanf`和`printf`函数的格式与使用方法,提供编程要求、测试说明及通关代码。 文档结构清晰,涵盖从环境搭建到具体编程任务的完整流程,适合初学者学习和实践。
168 4
|
8月前
|
C语言
【C语言程序设计——入门】基本数据类型与表达式(头歌实践教学平台习题)【合集】
这份文档详细介绍了编程任务的多个关卡,涵盖C语言的基础知识和应用。主要内容包括: 1. **目录**:列出所有关卡,如`print函数操作`、`转义字符使用`、`数的向上取整`等。 2. **各关卡的任务描述**:明确每关的具体编程任务,例如使用`printf`函数输出特定字符串、实现向上取整功能等。 3. **相关知识**:提供完成任务所需的背景知识,如格式化输出、算术运算符、关系运算符等。 4. **编程要求**:给出具体的代码编写提示。 5. **测试说明**:包含预期输入输出,帮助验证程序正确性。 6. 文档通过逐步引导学习者掌握C语言的基本语法和常用函数,适合初学者练习编程技能。
220 1
|
9月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
10月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
384 16
|
10月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
197 4