从0开始学习数据结构 C语言实现 1.前篇及二分查找算法

简介: 从0开始学习数据结构 C语言实现 1.前篇及二分查找算法

一、前篇

1、什么是数据结构?

数据结构是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系

2、时间复杂度与空间复杂度

大O符号是用于描述函数渐进行为的数学符号

常用函数的增长表

阶乘O(n!) > 指数阶(2^n) > 立方阶O(n^3) > 平方阶O(n^2) > 线性对数阶O(nlog2n) > 线性阶O(n) > 对数阶O(log2n) > 常数阶O(1)

从立方阶开始,时间复杂度较大

二、二分查找

在有序数组中查找一个值,如果找到了则返回下标,如果没找到则返回-1

方法一:遍历数组进行查找

时间复杂度:O(n)

//1.遍历算法在数组中查找一个元素
//方法体
int search(int* arr, int length, int target) {
  for (int i = 0; i < length; i++) {
    if (arr[i] == target) {
      return i;
    }
  }
}

方法二:减小循环次数进行遍历查找

时间复杂度小于O(n)

因为题目里声明是有序数组,所以当数组中的值比查找的值大时,可以直接break跳出循环,减少循环次数

//2.减小循环次数进行遍历查找
//方法体
int search2(int* arr, int length, int target) {
  for (int i = 0; i < length; i++) {
    if (arr[i] == target) {
      return i;
    }
    if (arr[i] > target) {
      break;
    }
  }
  return -1;
}

方法三;二分查找

二分思想就是将一个 有序数组 不断进行平分,直到找到为止,不断平分除以二,降低时间复杂度

时间复杂度:O(og2n)

//3.二分查找
//方法体
int binarySearch(int* arr, int target, int left, int right) {
  if (left > right) {
    return -1;
  }
  int mid = (left + right) / 2;
  if (arr[mid] == target) {
    return mid;
  }
  if (arr[mid] > target) {
    mid = binarySearch(arr, target, left, mid - 1);
    return mid;
  }
  else {
    mid = binarySearch(arr, target, mid + 1, right);
    return mid;
  }
}
int search3(int* arr, int length, int target) {
  return binarySearch(arr, target, 0, length - 1);
}


目录
相关文章
|
25天前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
46 1
|
3天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
3天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
5天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
5天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
|
5天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表:顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表,使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作,并提供了具体代码示例。静态分配方式下顺序表的长度固定,而动态分配则可根据需求调整大小。此外,还总结了顺序表的优点,如随机访问效率高、存储密度大,以及缺点,如扩展不便和插入删除操作成本高等特点。
|
5天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构,其中节点的度为其分支数量,树的度为树中最大节点度数。二叉树是一种特殊的树,其节点最多有两个子节点,具有多种性质,如叶子节点数与度为2的节点数之间的关系。此外,还介绍了二叉树的不同形态,包括满二叉树、完全二叉树、二叉排序树和平衡二叉树,并探讨了二叉树的顺序存储和链式存储结构。
|
5天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表,常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈,顺序栈使用数组存储,链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛,如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成,链栈则基于单链表的头插法实现。
|
5天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
5天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。