第1次课绪论（一）.ppt.ppt

数据结构 ;C语言 数据结构 软件工程;前期课程;数据结构的定义;教学目标 理解掌握数据结构的定义 理解掌握逻辑结构和存储结构 理解掌握数据结构和数据类型联系与区别;教学重点 数据结构的定义 逻辑结构类型 存储结构类型 教学难点 抽象数据类型; 数据：是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。 ; 例如,200402班为一个学生数据对象,而其中的“张三”是一个数据元素)。; 数据结构包括如下几个方面： (1) 数据元素之间的逻辑关系,即数据的逻辑结构。 (2) 数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构。 (3) 施加在该数据上的操作,即数据的运算。; 例1.1 有一个学生表如表1.1所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。;; 该表中的记录顺序反映了数据元素之间的逻辑关系, 用学号标识每个学生记录,这种逻辑关系可以表示为： 1,8,8,34,34,20,20,12,12,26,26,5 其中尖括号“ai,ai+1”表示元素ai和ai+1之间是相邻的,即ai在ai+1之前,ai+1在ai之后。; 数据在计算机存储器中的存储方式就是存储结构。 C/C++语言中，通常采用结构体数组和链表两种方式实现其存储结构。;存放学生表的结构体数组Stud定义为： struct { int no; /*存储学号*/ char name[8]; /*存储姓名*/ char sex[2]; /*存储性别*/ char class[4]; /*存储班号*/ } Stud[7]={{1,“张斌”,“男”,“9901”},…, {5,王萍,女,9901}};; 结构体数组Stud各元素在内存中顺序存放,即第i(1≤i≤6)个学生对应的元素Stud[i]存放在第i+1个学生对应的元素Stud[i+1]之前,Stud[i+1]正好在Stud[i]之后。; 存放学生表的链表的结点类型StudType定义为： typedef struct studnode { int no; /*存储学号*/ char name[8]; /*存储姓名*/ char sex[2]; /*存储性别*/ char class[4]; /*存储???号*/ struct studnode *next; /*存储指向下一个学生的指针*/ } StudType；;链表首结点地址head ; 对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。 从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中,其实现过程是不同的。; 例如,查找学号为20的学生的姓名： 对于Stud数组,可以从Stud[0]开始比较,Stud[0].no不等于20,再与Stud[1].no比较,…,直到Stud[3].no等于20,返回Stud[3].name。 对于head为首结点指针的链表,从head所指结点开始比较,head-no不等于20,从它的next得到下一个结点的地址,再与下一个结点的no域比较,…,直到某结点的no域等于20,返回其name域。; 为了更确切地描述一种数据结构,通常采用二元组表示： B=(K,R) 其中,B是一种数据结构,它由数据元素的集合K和K上二元关系的集合R所组成。其中： K={ki| 1≤i≤n,n≥0} R={rj| 1≤j≤m,m≥0} ; 其中： ki表示集合K中的第i个结点或数据元素。 n为K中结点的个数,特别地,若n=0,则K是一个空集,因而B也就无结构可言,有时也可以认为它具有任一结构。 rj表示集合R中的第j个二元关系(后面均简称关系)。 m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合K中的元结点间不存在任何关系,彼此是独立的。; 序偶x,y(x,y∈K) ? x为第一结点,y为第二结点。