搜索
数据结构导论主讲：徐青香2013、42概述《数据结构导论》是计算机科学与技术专业的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：线性表、栈、队列、数组、树、二叉树、图等基本数据结构及其应用；排序和查找的原理与方法；数据在外存上的组织方法。3第1章概论1.1引言1.2基本概念和术语1.3算法及描述1.4算法分析4本章总述要求熟悉各名词、术语的含义，掌握基本概念。包括数据、数据元素、数据项、逻辑关系和逻辑结构、运算和基本运算、数据结构、存储方式和存储结构、算法及算法分析等。注意这些概念之间的联系。本章重点逻辑结构和数据结构的概念。本章难点算法的时间复杂性分析。561.1引言1.数据结构的概念数据结构(Datastructure）是计算机组织数据和存储数据的方式。计算机解决问题的步骤：建立数学模型设计算法编程实现算法71.1引言数据结构主要研究：1）数据（计算机加工对象）的逻辑结构。2）实现各种基本操作的算法。学习数据结构的目的：掌握常用的数据结构及其应用。学会合理地组织数据，有效地表示数据和处理数据。掌握算法设计技术和分析技术。掌握使用计算机解决问题的方法和技能，提高程序设计水平。8应用举例1——学籍档案管理学号姓名性别年龄入学成绩1001王韬男205891002潘小欣女215801003张艳女195681004赵李军男185801005刘勇男225859数据特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是：在学生档案中查找出某人的档案，读取某个学生的信息，插入某个学生的信息，删除某个学生的信息，更新某个学生的信息等等。10应用举例2——制定教学计划在制定教学计划时，需要考虑：各门课程的开设顺序，即有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。11计算机专业学生的必修课程课程编号课程名称需要的先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1应用举例2——制定教学计划12数据结构主要研究：131.2基本概念和术语14基本术语数据（Data)：所有能被计算机处理的符号的集合。数据元素（DataElement）：是数据这个集合中的一个个体即数据的基本单位。数据项（DataItem）：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。15逻辑结构（LogicalStructure）：指数据元素之间的结构关系。物理结构（PhysicalStructure）也成为存储结构：指数据结构在机内的表示，数据的逻辑结构在计算机中的实现。16数据的逻辑结构(D,{R})可分为下列几种:D={d1,d2,…,dn}。1.集合:数据元素同“属于一个集合”。R={}。2.线性结构:R={(d1,d2),(d2,d3),…,(dn-1,dn)},即除起始节点和终端结点d1,dn外,每个节点有一个前驱和一个后继。3.树状结构:(D,{R})构成树,即每个元素最多有一个前驱,可以有多个后继。4.图状结构:(D,{R})构成一个图。逻辑结构的类型17逻辑结构的种类：数据的四类逻辑结构示意图:线性结构树形结构图状结构集合结构18特别注意：逻辑结构与数据元素本身形式、内容无关逻辑结构与数据元素的相对位置无关逻辑结构与所含结点个数无关19数据在计算机内的表示形式称为数据的存储结构存储结构的主要部分存储结点（每个存储结点存放一个数据元素）数据元素之间关联方式的表示数据的存储结构20数据结构的存储包含数据元素的存储及其逻辑关系的存储存储结构可分为:顺序存储结构、链式存储结构、索引存储方式和散列存储方式等。顺序存储结构与链式存储结构最基本，应该重点掌握。如，如何操作，各有什么特点，什么时候选择顺序结构，什么时候选择链式结构等。数据的存储结构21顺序存储结构：借助数据元素的相对存储位置来表示数据的逻辑结构；线性表的顺序存储方法：将表中的结点一次存放在计算机内存中一组连续的存储单元中。链式存储结构：借助数据元素地址的指针表示数据的逻辑结构；索引存储结构：借助索引表中的索引指示各存储节点的存储位置散列存储结构：用散列函数指示各节点的存储位置4种存储结构22存储结构的分类:顺序结构顺序的方法:将元素存储到一片连续的存储区.姓名和电话号码数据23存储结构的分类:链式结构这种结构是给结点附加一个指针字段,指出其后继节点的位置,即存放结点的存储单元分为两部分:特点：1）动态分配，不需要预先确定内存分配；2）插入和删除不需要移动其他元素；3）非随机存取结构。24逻辑结构与存储结构的关系25运算运算就是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。加工型运算：其操作改变原逻辑结构的值如：结点个数，结点内容等引用型运算：其操作不改变原逻辑结构的值查找读取插入删除更新以上操作哪些是加工型操作，那些是引用型操作？261.3算法及描述(运算的实现)算法规定了求解给定类型问题所需的所有“处理步骤”及执行顺序，使给定类型问题能在有限时间内被机械的求解。算法必须使用某种语言描述：程序介于自然语言和程序设计语言的伪代码非形式算法（自然语言）框图(N-S图)本教材中使用了类C语言描述算法27一个算法是对特定问题求解步骤的一种描述,它是指令的有穷序列。算法具有以下特性：1)有穷性:一个算法总是在执行有穷步后结束。2)确定性:算法的每一步都必须是明确地定义的。3)可行性:算法中的每一步都是可以通过已经实现的操作来完成的。4)输入:一个算法有零个或者多个输入,这些输入取自于特定的对象集合。5)输出:一个算法有一个或者多个输出，它们是与输入有特定关系的量。28算法描述我们教程主要用C语言描述。以下简单复习下C语言的内容。29第29页小大字符符号关键字C语言基本组成语句函数标准库函数用户自定义函数标识符其他符号数字,字母,运算符,特殊符号直接调用先定义，再调用1.C语言的基本组成C语言概述30第30页2、基本字符集C语言编程中可以使用的字符。ASCII字符集。数字：0123456789字母：abc……zABC……Z运算符：+-*/%='==!===&|∧~&&||!()[]{}-.?:,;特殊符号：_(下划线)空格回车(\r)换行(\n)制表符(\t)其它转义字符C语言概述313、标识符字符组成的串，用来对各种用户自定义对象命名。例如：变量名、常量名、数组名、函数名、文件名、类型名等。合法的标识符：由字母或下划线开头,由字母、数字或下划线组成。字母:大小写的a～z,下划线:_,数字:0～9例如：a_rytest31string_1不能以数字开头不能包含除下划线外的运算符和其他符号大小写区分判断哪些是合法的标识符：Cx11xx+ysum_5sum-5count_z3$x_8*Z3C语言概述32第32页4、关键字C语言中由系统特殊定义的32个具有特定含义的标识符，不能作为用户自定义对象的名字。autobreakcasecharconstcontinuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhile例如:变量名不能是intC语言概述335、语句inta,b,sum;sum=a+b;printf(sum=%d,sum);5.1、输入输出语句C语言概述函数调用语句printfscanf输入输出语句字符输入输出语句格式输入输出语句getcharputchar345.2、赋值语句赋值语句:由赋值表达式加上一个分号构成，它属于表达式语句类。实例:a=1;b=2;c=3;/*三个赋值语句，分别为变量a，b，c赋值*/x=a*a+b*b+c*c;/*计算表达式a2+b2+c2的值，并赋值给变量x*/程序划分为三部分:数据输入,数据处理,数据输出。它们可以由赋值语句和输入输出语句来完成。[注意：一定要严格区分赋值表达式和赋值语句的区别。printf(“%d\n”,x=a*a+b*b+c*c);[printf(“%d\n”,x=a*a+b*b+c*c;);合法[出错，输出语句的输出列表中不允许出现语句35单分支选择if语句格式：if(条件表达式)语句双分支选择if语句格式：if(条件表达式)语句1；else语句2；5.3、选择语句多分支if语句形式的格式：if(表达式1)语句1；elseif(条件表达式2)语句2；elseif(条件表达式3)语句3；…elseif(条件表达式n)语句n；else语句n+1；36switch语句的一般格式：switch(表达式){case判断值1:语句(组)1；break;case判断值2:语句(组)2；break；…case判断值n:语句(组)n；break；default:语句(组)n+1；}C语言概述37While语句的一般形式为：While(表达式)语句；do语句；while（表达式）;for循环是C语言最常用最灵活的循环控制语句.for(赋初值表达式序列；条件；修改表达式序列)语句；5.4、循环语句While循环结构do-while循环结构for循环结构38第38页6、函数main(){inta,b,sum;sum=a+b;printf(sum=%d,sum);}ff(intx){inta,b,sum;sum=a+b;}main(){inta=0;ff(a);printf(“thisisatest);}C语言概述39第39页简单的C语言程序介绍C语言程序例1:/*example1.c*/屏幕上显示一句话main(){printf(ThisisaCprogram.\n);}运行结果是在屏幕上显示:ThisisaCprogram.思考:\n的作用是什么?函数声明部分函数体C程序由函数组成对于一个C程序,至少有一个main函数,称为主函数,main是C语言中主函数的专用名，是程序执行的起点和终点。C语言概述40第40页例2:/*example2.c*/两个固定的数求和main(){inta,b,sum;/*定义三个整型变量*/a=1;/*变量a赋值等于1*/b=2;/*变量b赋值等于2*/sum=a+b;/*计算变量a与b的和,赋值给sum*/printf(sum=%d,sum);/*输出运算结果*/}运行结果是在屏幕上显示:sum=3函数说明函数体思考：printf(a=%d,b=%d,sum=%d,a,b,sum);函数可分为函数说明部分和函数体注释:/*…*/不是程序有效部分a=1,b=2,sum=3C语言概述41第41页例3:/*example3.c*/根据用户输入，求和main()/*主函数*/{inta,b,sum;/*定义变量类型*/printf(“pleaseinput\n”);/*调用库函数printf，输出“pleaseinput”*/scanf(“%d,%d”,&a,&b);/*调用库函数scanf，给变量a，b赋值*/sum=a+b;/*计算a，b的和*/printf(“a=%d,b=%d,sum=%d”,a,b,sum);/*输出运算结果*/}运行结果是在屏幕上显示:pleaseinput10,12a=10,b=12,sum=22C语言概述42C程序文件1（*.c）文件n函数1main()函数n函数说明函数体变量说明部分执行部分…语句1语句n第42页431.4算法分析算法的设计应满足：1）正确性：对于合法的输入产