阅读:0       作者:严长生

数据结构与算法C语言版分析概述

本节开始将带领大家系统地学习数据结构,作为一门计算机专业大二学生的必修课程,该课程面对的目标人群为初步具备基本编程能力和编程思想的程序员(大一接触了 C 语言或者 C++)。通过系统地学习数据结构,可以提高程序员分析问题和解决问题的能力。

首先,先来揭开数据结构的神秘面纱,看看什么是数据结构。

数据结构是什么?

数据结构,可以将之分为“数据”和“结构”两个方面去理解。

数据,很好理解。都说人离不开空气,感觉剥夺实验告诉我们,人也离不开信息,而信息实际上就是对数据进行加工后得到的产物。信息的形式多样化,所以数据的形态也多种多样:文字、数字、字母、符号、图形图像、音频视频等都可以是数据。

感觉剥夺实验,就是剥夺人的所有接受信息的权利,包括触觉、听觉、感觉等,这样的剥夺,任何人都是受不了的,详情可以去网上搜索。

2017 年的双 11,全球的“剁手族”为天猫贡献了 1682 亿,其中“剁手族”分布最多的城市为广东,等等这些都是通过天猫后台对一笔笔交易数据进行统计得出的结论。

结构,可以理解为各部分之间的关系。对于一篇文章的文章结构来说,有总分式,有并列式等,而判断一篇文件结构的过程实际上就是搞清楚文章中各个自然段落之间的关系。

数据结构,实际上是一门研究数据以及数据之间存在的关系的一门课程。通过理清数据及其之间存在的关系,就可以将数据有效存储到计算机中,让计算机来处理数据。

例如,在编写程序实现计算 7-2=? 的问题中,首先搞清楚的是:
  1. 问题中只涉及到两个数据:整数 7 和整数 2;
  2. 数据之间的关系是被减数与减数的关系;

全部搞清楚了之后,就可以编写程序解决此问题:定义两个整形变量,一个表示被减数,一个表示减数(确定之间的关系),将 7 和 2 赋给各自相应的变量(将数据存储到计算机中),最终输出相减的结果。

数据结构的体现不止于此,如图 1 所示,为一个家庭现有成员的树形图,现需要让计算机解决:找到孙子张磊的爷爷是谁?


图 1 家庭成员树形图

通过看这张家谱树形图,可以一眼看出,张磊的爷爷是张亮。但是如果把这个问题交给计算机来实现,就需要帮助计算机理清数据之间的关系。

数据的逻辑结构和物理结构

数据之间的关系(即数据结构)又可细分为逻辑关系逻辑结构)和物理关系物理结构)。逻辑关系就是例如张晶的父亲是张平、张群是张平的兄弟等等这样的关系,是人为赋予给数据的。

数据之间的逻辑关系分为三种:一对一”、“一对多”、“多对多”。图 1 中,每个孩子对应着唯一的父亲,这是“一对一”的关系;拿张平来说,他有两个孩子,为“一对多”的关系;在共享单车中,每个用户都可以选择多辆不同的单车;而每辆单车会被多个人使用,此为“多对多”的关系。

但是由于最终解决问题的主体是计算机,解决问题时需要将数据全部存储到计算机中,而后计算机去处理。数据在计算机中的实际存储表现出的是数据之间的物理结构,例如张晶距离张磊在实际的物理存储中有 5 比特的距离。

学习数据结构的作用就是在理清数据的逻辑关系的前提下,设计出合理的物理存储结构,使用这种结构,既能有效的存储数据,又能表示数据之间的关系。当计算机明白了这两个因素,问题自然而然就解决了。

数据结构 PK 算法

数据结构和算法两者为互利共赢的关系,两者并不冲突。使用计算机编程解决某个具体问题时,正确的做法是:
  1. 思考如何将要用到的数据存储到计算机中;
  2. 使用什么方法解决这个问题;

数据结构解决的是第一个问题,算法解决的的第二个问题。光有数据结构没有算法,相当于只把数据存储到计算机中而没有有效的方法去处理,没有任何意义;而若光有算法,没有数据结构,就相当于一个军师有锦囊妙计,但是没有士兵。

本教程的具体内容

本教程参照严蔚敏教授的《数据结构》一书,课程内容同该书同步,根据数据之间不同的逻辑关系,分为以下章节:

  • 线性表、栈和队列:解决的是具有“一对一”关系的数据的存储问题;
  • :解决的是具有“一对多”(也可以包含“一对一”)关系的数据存储问题;
  • :解决的是具有“多对多”(也包含“一对一”和“一对多”)关系的数据存储问题;

以上在介绍的同时,还会涉及到具体问题的解决,例如查找某个数据等。除以上内容外,也包含了有关字符串数组和广义表的相关内容。

除以上内容外,本教程对于各个知识点,还会配有专门的项目进行练习,同时还会不断地更新内容,给大家搜集介绍一些实用的算法。

学习数据结构的优势

  • 适用于所有编程语言

数据结构解决的是数据的有效存储问题,而不涉及到具体编程语言,是编程的基础课程。
误区:随着计算机技术日新月异的发展,越多的技术涌现,很多人花大精力和时间去追求新技术新热点,而将数据结构等基础抛之脑后,实属南辕北辙。因为软件开发不论如何改变,其最核心的底层知识不会改变。学习数据结构等一些基础课程才能真正的做到以不变应万变。
  • 扩宽解决问题的思路


对于面临的一些复杂的问题,其复杂性往往不是解决该问题的算法,更多的是思考如何存储具有复杂关系的数据。对于解决此类问题,数据结构无疑是一把利器。

数据结构中还会涉及有一些具体问题的解决算法(本教程会持续更新),例如没有接触数据结构之前,对于数据的排序,可能只想到冒泡(冒泡排序),其实你不知道,还有插入排序,快速排序等效率更高的排序算法,这些在本教程中都会以图文并茂的方式给大家讲解。

本教程 PK 其他数据结构教程

本教程依照于严蔚敏的《数据结构》一书,致力于打造一套适用与初学者,最浅显易懂的数据结构教程。

由于《数据结构》一书在对知识点的讲解上,跳跃性较强,对读者的编程思维要求较高。针对这个情况,本教程在该书的基础上对其知识点进行了更浅显易懂的讲解,在讲解过程中配有大量的样例和图示。

更重要的是,本教程对该书中所有的伪代码进行了基于 C 语言的完整实现,对实现过程进行了大量的铺垫,并附带了大量易于理解的注释和图示。

注意:本书中所有涉及到的代码都是基于 C 语言实现的,且遵循较新的 C99 标准,读者在尝试运行网站中的代码时请尽量使用较新版本的编译器。

总结

在武侠小说中,高手往往注重内功的修养,而招式则为其次,有了深厚的内力,即使不会招式,也能见招拆招;如果一味地崇拜花拳绣腿,没有内功,只是花架子,没什么卵用。

程序猿的路也是如此,要内外兼修。很多人认为大学所学的内容没用,其实不然,大学的学习就是在不断地提升自己的内功修为;毕业步入社会后,在深厚内力的基础上学习招式。

数据结构作为计算机专业的必修课程,就像“北冥神功”“易筋经”一样,是提升内功修为的绝世功法,怎么可以不学?

当你选择了本教程,你已然超越了 99% 的程序员。