文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C语言数据结构之绪论的示例分析

2023-06-20 19:11

关注

小编给大家分享一下C语言数据结构之绪论的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

绪论

什么是数据结构?

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

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
两两为一组进行比较,大的胜出,小的淘汰。

C语言数据结构之绪论的示例分析

毋庸置疑的是,无论怎么分组,显然最大值永远不会被淘汰。故最大值为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

C语言数据结构之绪论的示例分析

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

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

故变题寻找亚军的比较次数为 l o g 2 n − 1 log_2{n}-1 log2n−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+log2n−1=n+log2n−2次比较。

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

讨论

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

C语言数据结构之绪论的示例分析

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

交叉路口交通管理系统

C语言数据结构之绪论的示例分析

变题 着色算法

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

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

Example 4

如何快速走出迷宫?

C语言数据结构之绪论的示例分析

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

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

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

C语言数据结构之绪论的示例分析

以上是“C语言数据结构之绪论的示例分析”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注编程网行业资讯频道!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯