程序设计与软件开发基础(二).doc

《程序设计与软件开发基础(二).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第28讲程序设计与软件开发基础(-)教学目标及基本要求掌握数据结构的基木概念，掌握线性表、栈和队列这三种数据结构的定义、顺序存储结构及其基木运算，了解线性单链表、循环链表的结构及其基木运算。教学重点数据结构的基木概念，线性表、栈和队列的定义、顺序存储结构及其基木运算。教学难点线性单链表、循坏链表的结构及其基木运算。教学内容1.数据结构的基木概念2.线性表3.栈4.队列教学时间1学时主要内容：7.3数据结构基础73.1数据结构的基本概念数据结构(DataStructure)是指数据以及数据Z间的关系。数据结构包括3个方面：数据的逻辑结构、数据的存储结构以及对数据的操作(运算)。1・数据数据(D

2、ata)是信息的载体，它可以用计算机表示并加工。2.数据元素数据元索(DataElement)是数据集合中的一个个体，是数据的基木单位。数据元索有时也称为节点(Node)或记录(Record)。注意：数据元素不一定是单个的数字或字符，它木身也可能是若干数据项的纟R合。如表7・1所示的学生成绩登记表，其屮每一个学生的全部信息组成一个数据元素，它由学号、姓名、班级、成绩4个数据项组成。表7・1学生成绩登记表学号姓名班级成绩034100001张山电本1班77034100002李明电木1班88034200003干-小倩电气1班67034200004王芳电气1班903.数据对象具有相同性质的数据元素的

3、集合称为数据对象(DataObject)o4.数据结构数据结构是指同一数据对象屮备数据元素间存在的关系。用集合论方法定义数据结构为S=(D,R)数据结构S是一个二元组，其屮D是一个数据元素的非空有限集合，尺是定义在D上的关系的非空有限集合。这种抽象的定义可以用來描述广泛的数据结构问题。比如一个n维向量,X=(xl,x2,...»xn),它的数据元素集合为D={xl,x2,…，xn},D上的关系R={(xl,x2),(x2,x3),(xn-1,xn)),这种关系在数据结构中称为线性表。5・逻辑结构与物理结构(1)逻辑结构数据的逻辑结构研究数据元素及其关系的数学特性，它只抽象地反映数据元素的结构

4、,而不管H存储方式的数据结构。根据数据元素之间的关系的不同特性，通常有以卞4类基木结构。%1集合：结构屮的数据元素之间除了同属于一个集合的关系外，别无其他关系。%1线性结构：结构屮的数据元素Z间存在一个对一个的关系。%1树形结构：结构屮的数据元素Z间存在一个对多个的关系。%1图状或网状结构：结构屮的数据元素Z间存在多个对多个的关系。(2)物理结构数据的物理结构是逻辑结构在计算机屮的映像，也就是具体实现，通常川高级语言中备种数据类型来描述这种实现，也称为存储结构。它通常有两种不同存储结构图：顺序存储结构和链式存储结构。%1顺序存储结构：它主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物

5、理上也相邻的存储单元中，顺序存储结构只存储节点的值，不存储节点ZI'川的关系，节点2间的关系由存储单元的邻接关系来体现。%1链式存储结构：它不仅存储节点的值，而口存储节点Z间的关系。它利用节点附加的指针域，存储其后继节点的地址。它的节点由两部分组成，一部分存储节点本身的值，称为数据域，另一部分存储该节点的后继节点的存储单元地址，称为指针域。＞链式存储结构的特点节点屮除了自身信息外，还有表示连接信息的指针域，因此比顺序存储结构的存储密度小，存储空间利用率低；逻辑上相邻的节点物理上不必相邻；插入、删除操作灵活，不必移动节点，只要改变节点屮的指针即可。6・数据类型数据类型是指程序设计语言屮允许的变

6、量类型，程序中岀现的每一个变量必须与一个且仅与一个数据类型相联系，它不仅规定该变量可以设定的值的集合，而且规定了这个集合上的一组运算，各种语言都规定了它所允许的数据类型。7.数据的运算数据的运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。常用的运算有如下几种。(1)检索：在数据结构里杏找满足一定条件的节点。(2)插入：往数据结构里增加新的节点。(3)删除：把指定的节点从数据结构里去掉。(4)更新：改变指定节点的一个或多个域的值。(5)排序：使节点屮的某个域的值按由小到大对节点进行排列。7.线性结构与非线性结构如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据

7、结构。根据数据结构屮备数据元素Z间前示件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。>线性结构如果一个非空的数据结构满足下列两个条件：(1)有且只有一个根节点；(2)每一个节点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个节点后还应是线性结构。>非线性结构如果一个数据结构不是线性结构，则称为非线性结构。73.2线性表1.