《数据结构教程》第1章绪论.ppt

《《数据结构教程》第1章绪论.ppt》由会员分享，可在线阅读，更多相关《《数据结构教程》第1章绪论.ppt（78页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第1章绪论 1.2算法及其描述 1.1什么是数据结构1.3算法分析 本章小结1.4数据结构算法程序 1.1.1 数据结构的定义1.1.2 逻辑结构类型 1.1.3 存储结构类型1.1.4 数据结构和数据类型 1.1 什么是数据结构数据：是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据(集合)中的一个“个体”,是数据的基本单位。1.1.1 数据结构的定义数据对象：是具有相同性质的若干个数据元素的集合。例如,200402班为一个学生数据对象,而其中的“张三”是一个数据元素)。数据结构：是指数据以及数据

2、元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。因此,可时把数据结构看成是带结构的数据元素的集合。数据结构包括如下几个方面：(1)数据元素之间的逻辑关系,即数据的逻辑结构。(2)数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构。(3)施加在该数据上的操作,即数据的运算。例1.1有一个学生表如表1.1所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。学号 姓名 性别 班号1张斌 男99018刘丽 女990234李英 女990120陈华 男990212王奇 男990126董强 男99025王萍

3、女9901表1.1学生表 该表中的记录顺序反映了数据元素之间的逻辑关系,用学号标识每个学生记录,这种逻辑关系可以表示为：,其中尖括号“”表示元素ai和ai+1之间是相邻的,即ai在ai+1之前,ai+1在ai之后。数据在计算机存储器中的存储方式就是存储结构。C/C+语言中，通常采用结构体数组和链表两种方式实现其存储结构。存放学生表的结构体数组Stud定义为：struct intno;/*存储学号*/charname8;/*存储姓名*/charsex2;/*存储性别*/charclass4;/*存储班号*/Stud7=1,“张斌”,“男”,“9901”,5,王萍,女,9901;结构体数组Stud

4、各元素在内存中顺序存放,即第i(1i6)个学生对应的元素Studi存放在第i+1个学生对应的元素Studi+1之前,Studi+1正好在Studi之后。9901 女 王萍 5 9901 男 张斌 1Stud0 Stud6Stud数组起始地址 存放学生表的链表的结点类型StudType定义为：typedefstructstudnode intno;/*存储学号*/charname8;/*存储姓名*/charsex2;/*存储性别*/charclass4;/*存储班号*/structstudnode*next;/*存储指向下一个学生的指针*/StudType；链表首结点地址head1 张斌 男 9

5、9018 刘丽 女 990234 李英 女 990120 陈华 男 990212 王奇 男 990126 董强 男 99025 王萍 女 9901 学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。学生表构成的链表 对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的。例如,查找学号为20的学生的姓名：对 于 Stud数 组,可 以 从 Stud0开 始 比 较,Stud0.no不等于 20,再

6、与 Stud1.no比较,直到Stud3.no等于20,返回Stud3.name。对于head为首结点指针的链表,从head所指结点开始比较,head-no不等于20,从它的next得到下一个结点的地址,再与下一个结点的no域比较,直到某结点的no域等于20,返回其name域。为了更确切地描述一种数据结构,通常采用二元组表示：B=(K,R)其中,B是一种数据结构,它由数据元素的集合K和K上二元关系的集合R所组成。其中：K=ki|1in,n0R=rj|1jm,m0 逻辑结构的描述或表示：其中：ki表示集合K中的第i个结点或数据元素。n为K中结点的个数,特别地,若n=0,则K是一个空集,因而B也就无结构可言,有时也可以认为它具有任一结构。rj表示集合R中的第j个二元关系(后面均简称关系)。m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合K中的元结点间不存在任何关系,彼此是独立的。序偶(x,y K)x为第一结点,y为第二结点。x为y的直接前驱结点(通常简称前驱结点)y为x的直接后继结点(通常简称后继结点)。若某个结点没有前驱结点,则称该结点为开始结点；若某个结点没有后继结点,则称该结点为终端结点。说明：表示有向关系，(x,y)表示无向关系。采用离散数学的表示方法。