c语言数据结构第01讲绪论

《c语言数据结构第01讲绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、绪论绪论知识点数据结构中常用的基本概念和术语算法描述和分析方法难点算法时间复杂度要求了解数据的逻辑结构和物理结构；了解算法对于程序设计的重要性；掌握算法时间复杂度的分析方法。目录1-1数据结构研究的内容1-2数据的逻辑结构1-3数据的存储结构1-4算法和算法分析小结实验1习题11-1数据结构研究的内容数据结构研究的内容用计算机解决具体问题需要经过的步骤：（1）从具体问题抽象出适当的数学模型；（2）设计解数学模型的算法；（3）编制程序、运行并调试程序，直到解决实际问题。【例1-1】学生入学情况登记问题表1-1学生入

2、学情况简表学号姓名性别入学总分01丁一男44002马二男43503张三女43804李四男43005王五女44506赵六男42807钱七女43208孙八男43709冯九女42610郑十女435【例1-2】井字棋对奕问题【例1-3】七桥问题图1-2七桥问题图1-3欧拉回路1-2数据的逻辑结构1-2-1基本概念1．数据（Data）数据是信息的载体，是对客观事物的符号表示。通俗的说，凡是能被计算机识别、存取和加工处理的符号、字符、图形、图像、声音、视频信号等一切信息都可以称为数据。2.数据元素（DataElement）数

3、据元素是对现实世界中某独立个体的数据描述，是数据的基本单位。数据元素也称为结点（Node），在计算机中，常作为一个整体来处理。3．数据项(DataItem)数据项是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。数据项也称为域，或字段（Field）。4．数据对象（DataObject）数据对象是性质相同的数据元素的集合，是数据的一个子集。例如在“学生入学情况表”中，数据对象就是全体学生记录的集合。5．数据逻辑结构（DataStructure）数据的逻辑结构是相互之间存在的一种或多种特定关系的数

4、据元素的集合。（1）集合——结构中数据元素之间，除了“同属于一个集合”关系之外，别无其它关系。（2）线性结构——结构中的数据元素之间存在着“一对一”的关系。（3）树形结构——结构中的数据元素之间存在着“一对多”的关系。（4）图形结构——结构中的数据元素之间存在着“多对多”的关系。图1-4所示为四类基本数据结构的示意图（b）线性结构（c）树形结构（d）图形结构图1-4四类基本数据结构的示意图（a）集合结构1-2-2逻辑结构的描述数据元素之间的逻辑关系，称为数据的逻辑结构。一个数据的逻辑结构可以用二元组来表示：G=(

5、D,R)其中：D是数据元素的集合；R是D上所有数据元素之间关系的有限集合。【例1-4】一种数据结构Line=（D，R），其中:D={01,02,03,04,05,06,07,08,09,10}R={r}r={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>,<07,04>,<04,06>,<06,09>,<09,10>}【例1-5】一种数据结构Tree=（D，R），其中:D={01,02,03,04,05,06,07,08,09,10}R={r}r={<01,02>,<01,03>,

6、<01,04>,<02,05>,<02,06>,<02,07>,<03,08>,<03,09>,<04,10>}01020803070605040910图1-6树形结构【例1-6】一种数据结构graph=（D，R），其中:D={a,b,c,d,e}R={r}r={（a,b）,(a,d),（b,d）,（b,c）,（b,e）,（c,d）,（d,e）}圆括号表示的关系集合是无方向的，如（a,b）表示从a到b之间的边是双向的。其特点是各个结点之间都存在着多对多（M:N）的关系，即每个结点都可以有多个直接前驱或多个直接后继

7、，如图1-7所示，我们把具有这种特点的数据结构叫做图形结构，简称图。图1-7图形结构badce1-3数据的存储结构数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。四种不同的存储结构:1.顺序存储顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如，一个字母占一个字节，输入A、B、C、D、E，并存储在2000起始的连续的存储单元，如图1-8为顺序存储结构。ABCDE2.021004.820002001210020022000200220032004图1-8顺序存储结构图1-

8、9链式存储结构………………2.链式存储借助指示元素存储地址的指针（Pointer）来表示数据元素之间的逻辑关系。例如，图1-9为表示复数z=2.0+4.8i的链式存储结构。其中地址2000存放实部，地址2100存放虚部，实部与虚部的关系用值为”2100”的指针来表示（本例仅仅是为了简化讨论而作的一个引例，实际应用中，像复数这样简单的结构并不需要采用链式存储结构）。3.索引