一篇文章带你入门C语言数据结构:绪论

目录
  • 绪论
    • 什么是数据结构？
      • Example 1
    • 讨论
      • Example 2
      • Example 3
      • Example 4
  • 总结

绪论

什么是数据结构？

不同于计算机操作培训，注意与程序设计的区别。

Example 1

求n个数的最大值、次最大值。

//1.遍历 - 最朴素的方法
int main()
{
	int arr[10] = { 22,334,552,1,4,6,78,23,55,98 };
	int i = 0;
	int temp = 0;
	int max1 = arr[0];
	int max2 = arr[1];
	for (i = 1; i < 10; i++)
	{
		if (arr[i] > max1)
		{
			temp = max1;
			max1 = arr[i];
			arr[i] = temp;
		}
	}
	printf("%d\n", max1);
	for (i = 2; i < 10; i++)
	{
		if (arr[i] > max2)
		{
			temp = max2;
			max2 = arr[i];			arr[i] = temp;
		}
	}
	printf("%d\n", max2);
	return 0;
}

遍历方法共需进行 n − 1 + n − 2 = 2 n − 3 n-1+n-2=2n-3 n−1+n−2=2n−3次比较。

变题

有n个足球队比赛，问至少多少次比赛才能找到冠军和亚军。

解：
实际中通常采用锦标赛方法。（淘汰制）
设有8个数分别为5，7，3，6，8，9，4，2
两两为一组进行比较，大的胜出，小的淘汰。

毋庸置疑的是，无论怎么分组，显然最大值永远不会被淘汰。故最大值为9。

共进行了 8 / 2 + 4 / 2 + 2 / 2 = 7 8/2+4/2+2/2=7 8/2+4/2+2/2=7次比较。

故变题寻找冠军的比较次数为 n / 2 + n / 2 2 + … + n / 2 k = n − 1 n/2+n/2^2+…+n/2^k=n-1 n/2+n/22+…+n/2k=n−1

次最大值肯定是被最大值给比下去了，不然它就是最大值了。所以顺着这个思路，把所有和最大值进行过直接比较的数字跳出来，重新进行比较。

就是如图所示带*的数字，个数记为k，稍加思索则得出 k = l o g 2 n k=log_2{n} k=log2​n

2.故变题寻找亚军的比较次数为 l o g 2 n − 1 log_2{n}-1 log2​n−1

锦标赛方法共需 n − 1 + l o g 2 n − 1 = n + l o g 2 n − 2 n-1+log_2{n}-1=n+log_2{n}-2 n−1+log2​n−1=n+log2​n−2次比较。

课后思考：将该模型用C程序编写出来。

讨论

​ 处理一般实际工程问题的方法。

  • 找出解决方案。
  • 找出最优解。（最节省资源：CPU和内存）

Example 2

判断表达式中括号是否匹配

Z = ( ( a + b ) + c ) ∗ 2 + ( 3 − 5 ) / 7 − ( ( 6 + 2 ) / 8 + a )

void match(char* ch)
{
	int count = 0;
	int i = 0;
	while (ch[i]!= ';')
	{
		if(ch[i] == '(')
			count++;
		else if (ch[i] ==')')
			count--;
		i++;
	}
	if (count != 0)
		printf("%s\n","no match");
	else
		printf("%s\n","match");
}

当然，上述代码是由左向右数括号数是否相等来判断括号是否匹配，很容易就可以举出反例 f = ) a + b ( f=)a+b( f=)a+b( ，所有该方法是不成熟的。

Example 3

交叉路口交通管理系统

  • 把可以走通的道路设为顶点
  • 如果两个顶点有冲突，用顶点之间的连线表示

变题 着色算法

在状态图中，相邻（有连线）的顶点不能是同一种状态。故对于顶点的不同状态，我们用不同的颜色去表示。由于四色定理，多余5叉的路口不能用少于4种颜色来表示。

在状态图中至少需要多少种颜色来表示？

Example 4

如何快速走出迷宫？

以上问题现阶段并不作要求，目的是向大家介绍下数据结构的研究问题。

现在我们是否能回答出刚开始时问大家的问题呢？数据结构是什么？

数据结构是研究的是非数值计算的程序设计方法。

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • 一篇文章带你了解C语言:入门基础

    一篇文章带你了解C语言:入门基础

    目录 C语言本身特点 数据类型 常量变量 变量分类 使用小建议 生命周期作用域 常量分类及其特点 字符串+转义字符+注释 字符串 转义字符 两种注释 选择循环语句 函数 数组 总结 闲话少说,先上思维导图. 如图所示,现在还是初识C语言的第一部分,本次只介绍了C语言本身特点,数据类型,常量变量,字符串转义字符注释,选择循环语句,函数,数组. 接下来请和我一起粗略地探讨其中内涵所在. C语言本身特点 这是C语言的定义: C语言是一门通用计算机编程语言,广泛应用于底层开发.C语言的设计目标是提供一种

  • 一篇文章带你入门C语言:操作符

    一篇文章带你入门C语言:操作符

    目录 操作符 分类 算术操作符 移位操作符 整数存储规则 左右移位规则 赋值操作符 单目操作符 取地址操作符& 解引用操作符* 类型长度操作符sizeof 按位取反操作符~ ++ -- 操作符 强制类型转换操作符(type) 关系操作符= 逻辑操作符 短路运算 条件操作符 逗号表达式 下标引用.函数调用和结构成员 下标引用操作符[] 函数调用操作符() 结构成员操作符. -> 结构体定义 结构体使用 结构体地址 表达式求值 隐式类型转换 整型提升 如何整型提升 有符号数 无符号数 算术转换

  • 一篇文章带你入门C语言:数组

    一篇文章带你入门C语言:数组

    目录 数组 一维数组 初始化 使用 总结: 内存存储 二维数组 创建 初始化 数组越界问题 数组作函数参数 应用实例 总结 数组 一维数组 创建 定义 数组是一组相同类型的元素的集合.那数组的语法形式: type_t arr_name [const_n] //如: int arr[10]; type_t 指的是数组元素的类型. const_n 指的是一个常量表达式,用来指定数组的大小. 此时运行程序的话,系统会报一个警告:未初始化变量.打开调试就会发现系统默认填入一些无意义的数据. 当然全局数组

  • 一篇文章带你了解C语言:入门基础(2)

    一篇文章带你了解C语言:入门基础(2)

    目录 操作符 算术操作符 移位操作符 位操作符 单目操作符 逻辑反操作! 操作符++,-- 逻辑操作符 条件操作符 逗号表达式 常见关键字 typedef extern static 修饰局部变量 修饰全局变量和函数 其它 #define定义常量和宏 定义常量 定义宏 指针 内存单元 指针变量 &取地址操作符,*解引用操作符 类型所占空间 结构体 定义结构体 使用结构体变量 总结 本节将结束对初识C语言的概述,只追求大概,不求精细. 本节包括的内容有操作符,常见关键字,#define定义常量和宏

  • 一篇文章带你入门C语言:函数

    一篇文章带你入门C语言:函数

    目录 函数 定义 库函数 定义 介绍 Example 1 strcpy Example 2 memset 自定义函数 Example 1 Example 2 两数交换 链式访问 Example 1 函数声明 函数递归 Example 1 Example 2 函数迭代 Example 3 Example 4 总结 函数 定义 程序里的函数又被叫做子程序,他作为一个大型程序的部分代码,有一或多个语句项组成.函数负责完成某项特定任务,提供了对过程的封装和对细节的隐藏,这样的代码通常会被集成为软件库.

  • 一篇文章带你入门C语言数据结构:绪论

    一篇文章带你入门C语言数据结构:绪论

    目录 绪论 什么是数据结构? Example 1 讨论 Example 2 Example 3 Example 4 总结 绪论 什么是数据结构? 不同于计算机操作培训,注意与程序设计的区别. Example 1 求n个数的最大值.次最大值. //1.遍历 - 最朴素的方法 int main() { int arr[10] = { 22,334,552,1,4,6,78,23,55,98 }; int i = 0; int temp = 0; int max1 = arr[0]; int max2

  • 一篇文章带你入门Springboot沙箱环境支付宝支付(附源码)

    一篇文章带你入门Springboot沙箱环境支付宝支付(附源码)

    目录 0.前言 1.效果展示 2.技术栈介绍 3.前期准备 第一步:申请一个沙箱测试账号 第二步:电脑下载一个支付宝提供的客户端用于生成RSA2 第三步:手机下载 [沙箱版支付宝] 4.后端搭建 项目目录结构 pom.xml application.yml application-alipay.proerties Order订单实体类 Service层 Controller层 配置类 跨域拦截器配置以及注册 启动spirngboot项目 支付操作的页面: 支付完成后支付宝回调的页面: 启动前端项

  • 一篇文章带你入门Java数据结构

    一篇文章带你入门Java数据结构

    目录 1.逻辑结构和物理结构 2.顺序结构,链式结构,栈,队列,二叉树 二叉树 普通二叉树: 满二叉树: 完全二叉树: 平衡二叉树: 排序二叉树: 二叉树的遍历: 总结 1.逻辑结构和物理结构 逻辑结构:    集合: 数据与数据之间没有任何关系 线性: 一对一关系 树型: 一对多关系 图型: 多对多关系 物理结构: 顺序结构(数组): 链式结构(链表): 2.顺序结构,链式结构,栈,队列,二叉树 顺序结构: 可扩容数组,底层用数组实现,顺序排列,标号连续,内存空间连续 优缺点: 查询速度快,在

  • 一篇文章带你入门Springboot整合微信登录与微信支付(附源码)

    一篇文章带你入门Springboot整合微信登录与微信支付(附源码)

    0. 前期准备 在使用微信支付前,默认小伙伴已经具备以下技能: 熟练使用springboot(SSM) + Mybatis(plus)/JPA + HttpClient + mysql5.x 了解JWT 权限校验 阅读过微信开放平台微信支付与微信登录相关文档,可以简单看懂时序图 有微信开放平台开发者资质认证账户,具备开通微信支付(如果不具备的小伙伴可以找身边有的人借一下) 1. 微信扫码登录 1.1 微信授权一键登录功能介绍 简介:登录方式优缺点和微信授权一键登录功能介绍 # 1.手机号或者邮箱

  • 一篇文章带你入门Java修饰符

    一篇文章带你入门Java修饰符

    目录 定义 分类 访问控制修饰符 非访问控制修饰符 修饰符的使用说明 修饰类 修饰方法 访问控制修饰符 非访问控制修饰符 修饰变量 总结 定义 Java修饰符:修饰符用来定义类.方法或者变量,通常放在语句的最前端. 分类 主要分为2类: 访问控制修饰符 非访问控制修饰符 访问控制修饰符 可以使用访问控制符来保护对类.变量.方法和构造方法的访问.分为以下4中权限:private,default,protected,public. 权限说明: 修饰符 当前类 同包 子类(不同包) 不同包(其他类)

随机推荐