软件技术基础 01数据结构的基本概念

软件技术基础主讲教师：：第1章数据结构第2章操作系统第3章软件工程方法第4章数据库技术第5章网络技术基础课程内容第一章数据结构目的与要求掌握数据结构的定义，三个层次及基本的数据结构类型。掌握线性结构、树结构和图结构的基本概念，能编写线性结构、树结构相关的算法。课程内容1.1数据结构的基本概念1.2线性结构1.3非线性结构1.4查找与排序算法习题与小结1.1数据结构的基本概念1.1.1什么是数据结构1.1.2数据结构中的基本概念1.1.3C语言的数据类型1.1.4抽象数据类型（略）1.1.1什么是数据结构1、数据及数据元素的概念数据是客观事物在计算机内的抽象描述可以是一些事实，或一些数，或一些符号集合组成数据的“事实”、“数值”或“符号”称为数据元素数据的基本单位是数据元素数据元素可由若干个数据项组成2、数据结构的概念结构指事物间的相互关系和约束。数据结构是指计算机系统中数据的组织形式及其相互关系例：班级学生信息表····································田径应用数学1984.1男011102张强舞蹈应用数学1983.4女011101李红特长专业出生年月性别学号姓名数据结构是计算机的专业技术基础课。它研究的主要问题有：数据之间的逻辑关系是什么?选择什么样的存储结构？采用什么样的操作实现算法效率更高？元素集合元素间的关系运算计算机系统元素在计算机系统里的表示字符？字串？整数？元素间的逻辑关系－－逻辑结构元素在计算机系统中的存储方式－－存储结构操作指令的集合－－算法1、数据的逻辑结构数据的逻辑结构描述的是各个结点（或元）之间的逻辑关系主要分为两大类：线性结构非线性结构1.1.2数据结构中的基本概念（1）线性结构线性结构的逻辑特征是：有且仅有一个开始数据元素和一个终点数据元素并且所有数据元素都最多只有一个直接前趋和一个直接后继例如：线性表是一个典型的线性结构。在这类结构中，各结点依次相随，“先后”有序一维数组是这类结构中最简单的例子，堆栈、队列和链表也是它的重要实例线性结构（2）非线性结构非线性结构的逻辑特征是：一个数据元素可能有多个直接前趋或多个直接后继例如：图结构是非线性结构中最一般的结构，其中任何元素的直接前趋和直接后继的个数不作限制2、数据的存储结构存储结构：是反映数据元素在计算机中的存储方法数据的存储结构：也称为数据的物理结构是数据的逻辑结构在存储器里的实现数据的存储方法：顺序存储方法链接存储方法索引存储方法散列存储方法顺序存储方法把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里，元素间的逻辑关系由存储单元的邻接关系体现。相邻元素（逻辑）相邻存储单元（物理）主要应用于线性的数据结构，如线性表、数组等非线性的数据结构也可通过某种线性化的方法来实现顺序存储链接存储方法不要求逻辑上相邻的元素其物理位置上亦相邻，元素间的逻辑关系由附加的指针字段表示。链式存储结构要借助于程序语言的指针类型来描述元素的存储地址每个数据元素所占存储单元分成两部分：一部分为元素本身数据项另一部分为指针项，指出其后继或前趋元素的存储地址，从而形成一个链索引存储方法在存储元素信息的同时，建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字、地址）关键字是能唯一标识一个元素的数据项数据库管理中常用索引存储方法稠密索引（DenseIndex）每个元素在索引表中都有一个索引项稠密索引中索引项的地址指示元素所在的存储位置稀疏索引（SparseIndex）一组元素在索引表中只对应一个索引项稀疏索引中索引项的地址指示一组元素的起始存储位置散列存储方法根据元素的关键字直接计算出该元素的存储地址即在数据元素的子段中，有一个或几个子段的值，通过某一散列函数唯一地确定该元素的存储地址又称散列存储方法为关键字——地址转移法散列存储方法是最快速查找的一种方式例：以用户姓名为关键值。算式：字母的序号相加DJS04＋10＋19＝33ZXM26＋24＋13＝63所以，DJS放在33号地址单元ZXM放在63号地址单元3、数据的处理和运算研究数据的逻辑结构、物理结构，最终目的——为了有效处理数据，提高数据处理的运算速度。遍历——在数据结构的各个元素中移动，或查看所有数据元素插入——往数据结构中添加新的元素更新——修改或替代数据结构中指定元素的一个或多个数据项（字段值）删除——把指定的数据元素从数据结构中去掉查找——在数据结构中查找满足一定条件的数据元素排序——在保持数据结构中数据元素个数不变的前提下，把元素按指定的顺序重新排列。排列一般是建立在线性逻辑结构的基础上（1）C语言的基本数据类型声明char字符类型;int整数类型；float浮点数类型;charch;intx;longy;floatf;占据空间数值范围1字节－128~1272字节－32768~327674字节－2G～2G1.1.3C语言的数据类型（2）C语言的指针类型存放地址信息的变量为指针变量“*”和“&”符号的使用*在变量申明时使用，表示声明指针变量。*在语句中使用，表示取指针变量指向地址单元的内容。&在语句中使用，表示取出变量的地址intx,y;int*p;p=&x;取址申明p为指针变量y=x;y=*p;等价p=&x;取p指向地址的内容（3）数组类型与字符串数组是同一类型的一组有序数据的集合。数组的声明：类型变量名[变量个数]inta[100];一维整数数组intb[10][10];二维数组数组名标识了这一数组，代表起始地址，也是一个指针变量。C语言中没有单独的字符串类型。字符串定义成字符数组。如：charname[20];每个字符串由转义符’\0’指示其结束。字符串常量用双引号指示。C语言提供了关于字符串操作的函数：strlen();strcpy(str1,str2)等。（4）C语言的结构类型结构类型由一组称为结构成员的项组成。C语言中定义结构变量由两步组成：①定义结构类型②利用该类型说明结构类型变量。struct{类型变量；类型变量；……}；typedefstructstudent{intid;charname[20];intclasses;floatscore[4];}elemtype;利用结构类型声明变量：elemtypedata[MAXNUM];1、结构体说明定义结构变量2、引入“结构标志”3、结构类型定义struct{类型变量；类型变量；……}；struct{类型变量；类型变量；……}mystruct1；structmystr{类型变量；类型变量；……}；structmystrmystruct1;typedefstruct{类型变量；类型变量；……}mystr；mystrmystruct1;小结1、数据、数据元素、数据结构2、逻辑结构分为哪几种？3、数据主要的存储方法有哪几种？