绪论(数据结构)

数据结构主讲教师：李丽平1/19/20241课程要求课前请做好预习保持课堂安静，头脑清醒，思维活泼认真、独立、按时完成并提交作业重视上机实践，有效利用珍贵的上机时间不迟到早退，不旷课，保证学习的连续性先序课：《C++程序设计》1/19/20242什么是数据结构根本概念和术语算法描述算法分析第一章绪论1/19/202431.1数据结构的根本概念和术语什么是数据结构例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表1/19/20244例2人机对奕问题树……..……..…...…...…...…...1/19/20245例3：在n个城市之间建立通信线路图1/19/20246数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。1/19/20247根本概念和术语数据〔data)—所有能输入到计算机中去的描述客观事物的符号数据元素〔dataelement〕—数据的根本单位，在计算机程序中通常作为一个整体进行考虑和处理数据项〔dataitem〕—有独立含义的数据最小单位数据对象〔DataObject)性质相同的数据元素的集合数据的逻辑结构〔datalogicalstructure)—存在着一种或多种关系的数据元素的集合，也称数据结构〔datastructure)1/19/20248序偶：由有固定次序的两个客体组成，常用来表示客体之间的关系序偶的表示：<a,b>前驱后继1/19/20249根据数据元素间关系的根本特性，有四种根本数据结构〔集合〕——数据元素间除“同属于一个集合〞外，无其它关系线性结构——一对一，如线性表、栈、队列树形结构——一对多，如树图状结构——多对多，如图1/19/202410数据的存储〔物理〕结构—数据的逻辑结构在计算机存储器中的存放方式存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系1/19/202411元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1/19/2024121536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素1

14001346元素4∧…….……..…….

1400

元素21536…….……..…….1536元素31346

链式存储

h1/19/202413数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：1/19/2024141.2算法和算法描述什么是算法算法〔algorithm〕：解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性1/19/202415算法的描述工具框图算法描述虚拟语言算法描述类语言算法描述程序设计语言1/19/2024161.3算法分析技术初步算法的评价—衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率：空间效率和时间效率1/19/202417算法效率的度量运行时间=算法中每条语句执行时间之和。每条语句执行时间=该语句的执行次数〔频度〕*语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，那么一个算法的运行时间就是该算法中所有语句的频度之和。一般情况下并不是计算所有的语句的频度，而是只计算执行次数最多的那些语句的频度，这样的语句对应的操作叫根本操作。〔根本操作一般是最内层循环的循环体〕。一般来说，设算法中根本操作的执行次数是问题规模n的某个函数f(n)1/19/202418算法的时间复杂度记作：

T(n)=O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同。分析一个算法的时间复杂度的步骤：找出根本操作计算根本操作执行的次数忽略所有的常数和低次项，用大O表示法表示出来1/19/202419作业：100元买100支笔,其中钢笔3元/支,圆珠笔2元/支,铅笔0.5元/支.写算法输出各种组合方案解法1#defineN100voidscheme(){inti,j,k,count,money;for(i=0;i<=N;i++)

for(j=0;j<=N;j++)for(k=0;k<=N;k++){count=i+j+k;money=3*i+2*j+0.5*k;

if(count==N&&money==N)printf(“%d,%d,%d\n%〞,i,j,k);

}

}算法的时间复杂度为O(N3)1/19/202420例题：100元买100支笔,其中钢笔3元/支,圆珠笔2元/支,铅笔0.5元/支.写算法输出各种组合方案解法2#defineN100voidscheme(){inti,j;for(i=0;i<=N/3;i++)for(j=0;