数据结构入门(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语言及数据结构实现简单贪吃蛇小游戏
|
20天前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
1月前
|
存储 算法 测试技术
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
42 7
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
39 5
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
41 5
|
1月前
|
存储 编译器 C语言
【C语言程序设计——入门】C语言入门与基础语法(头歌实践教学平台习题)【合集】
本文档介绍了C语言环境配置和编程任务,主要内容包括: - **C语言环境配置**:详细讲解了在Windows系统上配置C语言开发环境的步骤。 - **第1关:程序改错**:包含任务描述、相关知识(如头文件引用、基本语法规则)、编程要求、测试说明及通关代码。 - **第2关:scanf函数**:涉及`scanf`和`printf`函数的格式与使用方法,提供编程要求、测试说明及通关代码。 文档结构清晰,涵盖从环境搭建到具体编程任务的完整流程,适合初学者学习和实践。
50 4
|
1月前
|
C语言
【C语言程序设计——入门】基本数据类型与表达式(头歌实践教学平台习题)【合集】
这份文档详细介绍了编程任务的多个关卡,涵盖C语言的基础知识和应用。主要内容包括: 1. **目录**:列出所有关卡,如`print函数操作`、`转义字符使用`、`数的向上取整`等。 2. **各关卡的任务描述**:明确每关的具体编程任务,例如使用`printf`函数输出特定字符串、实现向上取整功能等。 3. **相关知识**:提供完成任务所需的背景知识,如格式化输出、算术运算符、关系运算符等。 4. **编程要求**:给出具体的代码编写提示。 5. **测试说明**:包含预期输入输出,帮助验证程序正确性。 6. 文档通过逐步引导学习者掌握C语言的基本语法和常用函数,适合初学者练习编程技能。
45 1
|
2月前
|
存储 NoSQL 编译器
【C语言】指针的神秘探险:从入门到精通的奇幻之旅 !
指针是一个变量,它存储另一个变量的内存地址。换句话说,指针“指向”存储在内存中的某个数据。
124 3
【C语言】指针的神秘探险:从入门到精通的奇幻之旅 !
|
2月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
53 1