资源描述：
《数据结构基本概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构基本概念数据结构的有关概念本章要点数据结构的分类及表示算法及算法分析§2.1数据结构的有关概念如：一个个人书库管理程序所要处理的数据是一张表格。[数据]：客观对象的符号表示。在计算机科学中,数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格,图象等，都称为数据。在如前所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个数据元素构成。[数据元素]：数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。例如，在如前所示的个人书库表格
2、数据中，每个数据元素都有登录号、书号、书名、作者、出版社和价格等六个数据项构成。[数据项]:构成数据元素的成分,是数据不可分割的最小单位.每个数据元素可以由一个数据项,也可以由若干数据项组成.一般情况下，一个数据元素中含有若干个数据项.注:这里说的数据元素之间的关系是指元素之间本身固有的逻辑关系,与计算机无关.又称为数据的逻辑结构或抽象数据结构。[结构]：数据元素之间的关系[数据结构]：相互之间存在一种或多种特定关系的数据元素的集合,即带结构的数据元素的集合.数据元素之间的逻辑关系分为:(1)元素之间没有关系----集合(2
3、)元素之间具有线性关系---线性数据结构(线性表结构)(3)元素之间具有层次关系---层次数据结构(树结构)(4)元素之间具有网状关系---网状数据结构(图结构)[数据的逻辑结构]：数据元素之间的逻辑关系。独立于计算机，是数据本身所固有的。例1：某班学生基本情况登记表，记录了每个学生的学号、姓名、专业、政治面貌，表中的记录是按学生的学号顺序排列的.学号姓名专业政治面藐 001王洪计算机党员 002孙文计算机团员 003谢军计算机团员004李辉计算机团员005沈祥福计算机党员006余斌计算机团员 007巩力计算机团员008孔令
4、辉计算机团员学生基本情况登记表的图示001003002004006005008007学号关系是一种线性结构关系例2家族的族谱 家族的族谱反映的是家族成员之间的血缘关系，假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。这种分支的结构关系被称为树结构。它很象一棵倒置的树，A是树的根。JIACBDHGFE家族树的图示表示图形表示法：教师学生其他人员99级2000级2001级2002级……西南科技大学文艺学院土木学院制造学院……叶子根子树[数据的存储结构]：逻辑结构在计算机存贮器中的
5、映像，必须依赖于计算机。四种基本的存储方法：（1）顺序存储方法（顺序存储结构）（2）链接存储方法（链式存储结构）（3）索引存储方法（4）散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。§2.2数据结构的表示1图示表示图示表示是由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系；001003002004006005008007学生基本情况表的图示表示JIACBDHGFE家族树的图示表示用一个二元组（D，S）表示数据结构，其中D是数据元素集合，S是D上关系
6、的集合。2.二元组表示家族树的二元组表示（D，S）D={A，B，C，D，E，F，G，H，I，J} S={〈A,B>,,,,,,,,}学生基本情况表的二元组表示（D，S）D={001，002，003，004，005，006，007，008}S={<001,002>,<002,003>,<003,004>,<004,005>,<005,006>,<006,007>,<007,008>}§2.3算法与算法分析一什么是算法？算法是对特定问题求解步骤的一种
7、描述.例求10个正整数中最大数的算法。描述算法的方法有很多：流程图，自然语言，计算机语言开始为10个元素a[0]到a[9]输入数值max=a[0]i=1i<=10输出maxa[i]>maxmax=a[i]i=i+1结果NYYN求n个元素中的最大值流程图描述(1)给10个元素a[0]~a[9]输入数值;(2)把第一个元素a[0]赋给用于保存最大值元素的变量max;(3)把表示下标的变量i赋初值1;(4)如果i<=10,则向下执行,否则输出最大值max后结束算法;(5)如果a[i]>max,则将a[i]赋给max,否则不改变ma
8、x的值,这使得max始终保存着当前比较过的所有元素的最大值;(6)使下标i增1,以指示下一个元素;(7)转向第(4)步继续执行.自然语言描述main(){inti,max,a[10];printf(“请输入10个整数:”);for(i=0;i<=10;i++)scanf(“%d”,&a[i
