- 1、本文档共35页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
数据结构;课时安排:
课堂讲授——60学时
上机——12学时
教材与主要参考书:
教材
严蔚敏.《数据结构(C语言版)》.清华大学出版社
参考书目
王红梅.《数据结构(C++版)》(第2版).清华大学出版社2011
王红梅.《数据结构(C++版)学习辅导预实验指导》.清华大学出版社
李云清.《数据结构(C语言版)》.人民邮电出版社
唐策善.《数据结构-用C语言描述》.高等教育出版社
(美)MarkAllenWeiss.《数据结构与算法分析-C语言描述》.机械工业出版社
陈慧南.《数据结构—使用C++语言描述(第2版)》.人民邮电出版社
严蔚敏.《数据结构题集》.清华大学出版社;第一章绪论;
计算机软件与理论学科的专业基础课程
后续专业课程学习的必要知识与技能准备
操作系统中用队列、存储管理表及目录树
数据库系统运用线性表、多链表及索引树编译技术
要使用栈、散列表及语法树
增强求解复杂问题的能力
;;;例2人机对弈问题;课程编号;例3多叉路口交通灯管理问题;数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。;1.2基本概念和术语;学号;数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合。它一般包括以下三方面的内容:数据的逻辑结构、数据的存储结构和该类数据上的操作(即运算)。
(1)数据的逻辑结构:数据元素之间的逻辑关系;(2)数据的存储结构:数据元素及其关系在计算机中的存储表示。
顺序存储结构:用一组连续的存储单元依次存储数据元素,借助数据元素在存储器中的相对位置来表示数据元素间的逻辑关系。例如
链式存储结构:用一组任意的存储单元存储数据元素,借助指针表示数据元素间的逻辑关系。例如;元素n;1536;(3)数据的操作(即运算):是在该类数据上施加的一系列操作,给出了数据被使用的方式。
最常用的操作有:插入、删除、查找、更新等。
例:栈队列;数据结构的三个方面:;数据结构的三个方面:;实现一个数据结构,必须首先确定数据的存储表示,然后在给定的存储方式下实现相应的操作。;??据类型—是一组值的集合以及定义于这个值集上的一组运算的总称。;抽象数据类型可以通过固有的数据类型来表示和实现。
本教材采用类C语言描述抽象数据类型。类C语言精选了C语言的一个核心子集,同时作了若干扩充修改,增强了语言的描述功能。;作业;1.4算法和算法分析;二、算法设计的要求
正确性
可读性
健壮性
效率与低存储量需求
;三、算法效率的度量
执行算法所耗费的时间
执行算法所耗费的存储空间(辅助存储空间)
;算法效率的度量(续)
;
例1:求下列程序段的时间复杂度(N*N矩阵相乘)
for(i=1;i=n;i++)
for(j=1;j=n;j++)
{c[i][j]=0;
for(k=1;k=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
} ;例2(a){++x;s=0;}
---该程序段的执行时间是与问题规模n无关的常数,所以算法的时间复杂度为常数阶T(n)=O(1)
(b)for(i=1;i=n;++i)
{++x;s+=x;}
(c)for(i=1;i=n;++i)
for(j=1;j=n;++j)
{++x;s+=x;};例3分析程序段的时间复杂度:
for(i=2;i=n;++i)
for(j=2;j=i-1;++j)
{++x;a[i,j]=x;}
语句频度为:(n-2+1)(n-2)/2
=(n-1)(n-2)/2
=(n2-3n+2)/2
∴时间复杂度为O(n2)
即此算法的时间复杂度为平方阶.;;有的情况下,即使问题规模相同,算法中基本操作重复执行的次数还随问题的输入数据不同而不同。例如:
;一个程序执行需要空间:
①程序(指令、常数、变量)
②输入数据所占空间----和算法
您可能关注的文档
- 新产品开发计划方案分析表.docx
- 浅析化工技术中的问题及发展趋势.docx
- 构造地质学习题集及参考答案.文档.doc
- 振兴中华从我做起主题班会教案.docx
- 步态分析课件演示课件.ppt
- 必威体育精装版冀教版小学四年级科学上册教案(全册).pdf
- 人教版五年级上册科学试卷.doc
- 全国计算机等级考试二级教程——公共基础知识.docx
- 人教部编版初中历史七年级上册第一章第1节中国早期人类的代表——北京人-课件(共36张课件).ppt
- 溶血性贫血试题.doc
- (统编2024版)道德与法治七上2.2做更好的自己 课件.pdf
- (统编2024版)语文七年级上册 生动具体显文采 课件.pdf
- (人教2024版)英语七年级上册 Unit 1单元解读课件(新教材).pdf
- 第7章 JSP数据库编程.pptx
- (人教2024版)英语七年级上册Unit 1.5 Section B Project 课件(新教材).pdf
- (沪教2024版)数学一年级上册开学第一课.pdf
- 2024秋季开学第一课巴黎奥运会主题班会PPT.pptx
- 2024秋季巴黎奥运会开学第一课主题班会PPT.pptx
- 第3章 JSP内置对象-3.6~3.7.pptx
- 第6章 Servlet应用课件.pptx
最近下载
- 泛微协同办公标准版e-office产品使用手册.pdf VIP
- 新《安全生产法》全面解读“三管三必须”.pptx VIP
- 2022-2023多层次医疗保障创新案例集-75页-WN6.pdf
- 沥青罐体着火处置方案.docx
- 2023-2024年应急救援员(五级)理论考试题库(含答案).pdf VIP
- NB∕T 11422-2023 分布式光伏发电系统工程技术规范.pdf
- 简历制作教学课件.ppt
- 2024年茶评员高级技师(一级)职业鉴定理论考试题库(含答案).docx
- 泛微协同办公平台-office10服务器管理应用说明.pdf VIP
- 大型商业综合体、大型超市、农贸市场企业安全风险辨识清单21.docx VIP
文档评论(0)