资源描述：
《数据结构入门介绍ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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王萍女9901表1.
3、1学生表该表中的记录顺序反映了数据元素之间的逻辑关系,用学号标识每个学生记录,这种逻辑关系可以表示为：<1,8>,<8,34>,<34,20>,<20,12>,<12,26>,<26,5>其中尖括号“”表示元素ai和ai+1之间是相邻的,即ai在ai+1之前,ai+1在ai之后。数据在计算机存储器中的存储方式就是存储结构。C/C++语言中，通常采用结构体数组和链表两种方式实现其存储结构。存放学生表的结构体数组Stud定义为：struct{intno;/*存储学号*/charname[8];/*存储姓名*/charsex[2];/*存储性别*/charclass[4
4、];/*存储班号*/}Stud[7]={{1,“张斌”,“男”,“9901”},…,{5,"王萍","女","9901"}};结构体数组Stud各元素在内存中顺序存放,即第i(1≤i≤6)个学生对应的元素Stud[i]存放在第i+1个学生对应的元素Stud[i+1]之前,Stud[i+1]正好在Stud[i]之后。9901女王萍5…9901男张斌1Stud[0]Stud[6]Stud数组起始地址存放学生表的链表的结点类型StudType定义为：typedefstructstudnode{intno;/*存储学号*/charname[8];/*存储姓名*/charsex[2];/*存
5、储性别*/charclass[4];/*存储班号*/structstudnode*next;/*存储指向下一个学生的指针*/}StudType；链表首结点地址head1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901∧学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。学生表构成的链表对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构中
6、,其实现过程是不同的。例如,查找学号为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={k
7、i
8、1≤i≤n,n≥0}R={rj
9、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∈K)x为第一结点,y为第二结点。x为y的直接前驱结点(通常
