当前位置:首页 >> IT/计算机 >>

数据结构1


数据结构与算法
张斌
13487099179,tozhangbin@163.com 武汉光电国家实验室G210 课件下载地址:http://ibp.hust.edu.cn/books/ds.rar

乌鲁 木齐

哈尔 滨 长春
2 24

18 9 2

北京
137

704

216

676

西安

511

郑州

3 49

徐州

?

84 2

534

成都

武汉
409

674

?

110 0

提问:你想象中的《数据结构》是什么 样的或者是干什么用的? 答案:在计算机技术中,如何表示现实 世界中的事物、事物之间的关系,如何 方便、高效的修改这些事物和关系。
西宁 兰州
695

11 4

天津

5

大连

上海

96 7

5 82

南昌

株洲 贵阳
902

367

622

福州

昆明

639

60 7

柳州
25 5

广州
14 0

南宁

675

2 67

深圳

39 7

课程设想

呼和 浩特
668

沈阳

5 30

1 65

课程的主要内容
? ? ?

1.数据之间的逻辑关系及其分类 2.数据关系的存储方式及其分类 3.算法、算法优劣的评价

课程设想
?

学习《数据结构》的意义
?

熟练C语言,建立感性认识,走向应用的枢 纽,规范编程习惯,学习优秀的算法。 理论联系实际:编实例 多看优秀的程序,多上机,规范编程习惯

?

学习《数据结构》的方法
? ?

课本
?

?

严蔚敏,吴伟民.数据结构(C语言版).清华大学出 版社.1997年版2003年12月第24次印刷.22元 /335页:内容全面、深入、抽象,但是没有习 题、实验 朱战立.数据结构(C语言版).西安交通大学出版 社.2004年版2004年1月第15次印刷.25元/330 页:内容简单易懂,含习题、实验、实例,实 例多且具体,还介绍了相关的C语言知识

课件
?

课件下载地址:
?

http://ibp.hust.edu.cn/books/ds.rar

?

课件中的标识
? ? ? ?

红色:重点内容、超级链接 蓝色:次重点内容,标题、术语 黑色:一般了解的内容 灰色:不重要的内容(如:4串,5数组和广义表, 8动态存储管理,11外部排序,12文件)

进度安排
? ? ? ? ? ? ?

?
? ? ?

第1周:序论3 第2周:C语言回顾(引用)3、顺序表2 第3周:顺序表3、链表1 +顺序表实验 第4周:链表4 第5周:链表2 、栈与队列3 +链表实验 第6周:二叉树1 第7周:二叉树、树 第8周:查找 +二叉树实验 第9周:排序 第10周:排序、图、其它 +查找排序实验 建议学有余力的同学:还做图的实验(如显示地图)

课程设想
?

关于考试与成绩
? ?

考试:单项选择50分,程序填空50分 平时成绩10-15%,卷面成绩85-90%

TC语言与VC++语言的选择
?

?

基本使用“类C语言”、“C语言”,同 时使用C++中“引用”这一知识,编程 环境使用VC++6 但是对于想参加程序员考试和考研考该 门课的学生应当同时熟悉引用和指针两 种形参的使用

第一章 绪论

内容提要
?

本课主题:数据结构的基本概念和术语、抽象数据类
型的表示与实现、算法及算法设计要求、算法效率的 度量和存储空间需求 教学目的:了解数据结构的基本概念,理解常用术语、 了解抽象数据类型的定义、表示和实现方法、掌握算 法的定义及特性,算法设计的要求,掌握算法的时间 复杂度和空间复杂度的意义与作用 教学重点:数据结构的四种分类和两个层次、抽象数 据类型表示法、算法设计要求,时间复杂度、空间复 杂度 教学难点:抽象数据类型表示法、算法设计要求、时 间复杂度、空间复杂度

?

?

?

1.1 问题的提出
?

?

?

?

提问:你想象中的《数据结构》是什么 样的或者是干什么用的? 答案:在计算机技术中,如何表示现实 世界中的事物、事物之间的关系,如何 方便、高效的修改这些事物和关系。 ——数据元素、结构、操作、效率 提问:请列举一些事物,分析其关系
?

整数,字符,人,图形,图像,数学定理

1.1.1逻辑关系分类-线性结构
?

1.线性结构
? ?

例如:人员管理 涉及的主要操作:创建,插入,删除,修改
姓名 张涵韵 李宇春 尚雯婕 性别 女 女 女 年龄 20 18 16 ...

编号 2004 2005 2006 ...

1.1.1逻辑关系分类-线性结构
?

1.线性结构

教育科学体育卫生: 厂矿企业: 1.学籍管理(姓名/班级/学号) 11.部门管理(名称/负责人/职责) 2.课程管理(课程/课本/学时) 12.工资管理(姓名/时间/工资) 3.图书管理(书名/作者/价格) 13.财务管理(流水号/事由/费用) 4.字典(单词/词性/含义) 14.仓库管理(编号/名称/库存量) 5.教室管理(教室号/时间/用途) 15.售后服务管理(时间/客户/问题) 6.金牌榜(名次/国家/金牌数) 16.考勤管理(人员/时间/事件) 7.生物信息系统(物种/门类/数量) 17.资产管理(编号/名称/型号) 8.地理信息系统(省/省会/人口) 18.住房管理(房号/主人/房型) 9.历史信息系统(朝代/领袖/时间) 19.会议管理(主题/时间/地点) 10.医院信息系统(编号/病人/病况) 20.车辆管理(牌照/司机/车型)

1.1.1逻辑关系分类-线性结构
?

1.线性结构
IT行业: 31.计算机管理(型号/配置/价格) 32.软件管理(名称/种类/文件) 33.地址簿(人员/电话/邮箱) 34.邮件箱(主题/时间/发件人) 35.病毒信息系统(名称/发作时间/特征) 36.日志管理(时间/事件/操作者) 37.内存管理(起始地址/大小/进程) 38.版本管理(版本号/新功能/发布时间) 39.域名管理(域名/单位/申请时间) 40.菜单管理(菜单项/功能/快捷键)

服务娱乐业: 21.航班管理(航班/起止站/价格) 22.定票系统(客户/航班/数量) 23.股票信息(名称/收盘价/成交量) 24.天气预报(城市/天气/气温) 25.名胜管理(景点/地点/票价) 26.客房管理(房号/入住时间/客人) 27.明星档案管理(姓名/类型/作品) 28.点歌系统(序号/歌名/演唱者) 29.银行系统(时间/金额/操作员) 30.保单管理(保险人/种类/保额)

规律:并列关系,先后关系——一对一关系

1.1.2逻辑关系分类-树形结构
?

2.层次结构(树形结构)
? ?

例如:组织机构、家族关系 主要操作:创建,插入,删除,修改
总经理

人事处

财务处

生产处

销售处

材料车间

加工车间

造型车间

装配车间

1.1.2逻辑关系分类-树形结构
?

2.层次结构(树形结构)
?

?

例如:组织机构、家族谱、生物进化史、计 算机硬件结构、文件系统、分类、迷宫、对 弈问题、电报系统数据编码、表达式求值、 最佳判定树 规律:存在上下级关系、包含关系——一对 多关系

1.1.3逻辑关系分类-图形结构
?

3.图形结构(网状结构)
? ?

例如:社会关系、地图 主要操作:创建,插入,删除,修改
曹操

刘备

孙权

1.1.3逻辑关系分类-图形结构
?

3.图形结构(网状结构)
?

?

例如:社会关系、地图、交通图、计算机网 络、项目进度安排、食物链、新陈代谢过程、 网站网页链接关系、流程图 规律:存在复杂的多对多关系

1.1.4逻辑关系分类-复杂结构
?

4.更复杂的情况:产品数据管理、项目 管理、CIMS、排课管理、字典等——存 在线性关系、层次关系、图形关系的组 合、索引关系

数据结构的定义
?

?

?

结论:《数据结构》研究非数值计算环 境下的操作对象及其相互关系和操作。 不仅要研究数据的逻辑特性,还要考虑 其存储、算法,还要研究各算法的质量、 效率。 创始人:唐.欧.克努特(美),1968年发表

1.2 基本概念和术语
? ?

一、数据元素、数据结构的定义 1、数据:客观事物的符号表示。在计算机科 学中指能输入到计算机中并被计算机程序处理 的符号的总称。如:数字,字符,图形,声音
姓名 张涵韵 李宇春 尚雯婕 性别 女 女 女 年龄 20 18 16 ...

编号 2004 2005 2006 ...

1.2.1数据元素
?

2、数据元素、数据项
?

数据元素:数据的基本单位,它由不可分割 的数据项组成。通常数据元素用来表示一个 事物,而数据项用来表示事物的属性。

1.2.1数据元素
?

2、数据元素、数据项
物质 数据元素 结构体、变量 记录 物质的属性 数据项 成员变量 域(字段)

《哲学》中的概念 《数据结构》中的概念 《C语言》中的概念 《数据库》中的概念

1.2.1数据元素
?

3、数据对象 数据对象:性质相同的数据元素的集合。 如上例:整个表可以看作一个数据对象。 《数据结构》通常需要研究一组数据元 素,即数据对象。

1.2.2数据结构
?

★4、数据结构 (1)数据结构:相互之间存在特定关系的 数据元素的集合。 ★数据的逻辑结构:数据元素之间的相 互关系。 注意不要混淆这两个概念。

1.2.2数据结构的形式定义
?

(2)数据结构的形式定义:
数据结构名称=(D,S) 其中: D为数据元素的有限集{d1,d2,d3,...}, S是D上关系的有限集 {<d1,d2>,<d1,d3>,<d2,d3>,...} 在关系<d1,d2>中,称d1是d2的直接前驱 (简称前驱),d2是d1的直接后继(简称后继)。
真如上述定义的结构是什么类型的结构?

1.2.2数据结构的分类
?

★(3)数据结构的种类

1.2.2数据结构的分类
?

★(3)数据结构的种类
示例

数据结构类 数据元素间 型 的关系

树形结构 (层次结构)

前驱:后继 一对多

图形结构 (网状结构)

前驱:后继 多对多

1.2.2数据结构的存储结构
?

★(4)数据结构的两个层次:
? ?

逻辑结构 存储结构(物理结构)
“数据结构”定义中的“关系”指数据元素之间的逻辑关系,故称数 据结构为逻辑结构。 数据结构在计算机中的表示称为物理结构,又称存储结构。它 又分为两类: ??顺序存储结构:借助内存单元的相对位置表示数据元素之 间的逻辑关系。 ??链式存储结构:借助指针表示数据元素之间的逻辑关系。

逻辑结构

存储结构 (物理结构)

线性结构必须使用顺序存储结构吗?树、图呢?

1.2.2数据结构的存储结构
?

(5)存储结构详解: 计算机中存储信息的最小单位:位。8 位为一字节;两个字节为一字。通常把 多个字节、字或二进制位组成的位串用 来表示一个数据元素。当数据元素由若 干数据项组成时,位串中对应于各个数 据项的子位串称为数据域(Data Field)。

1.2.3数据类型与操作
?

1、数据类型:一个值的集合和定义在这 个值集上的一组操作的总称(C语言中下 的定义)。
?

?

操作:对一种数据类型的数据进行的某种处 理。 例:整型,其值集为(一定范围内的)自然 数,其操作:加、减、乘、除、比较大小、 取模、阶乘。

1.2.3数据类型与操作
?

2、数据类型的种类:
特征 例 int float char * 操作(运算) 加、减、乘、除 、比较、赋值等

原子类型 值在逻辑上不可分解 结构类型
?

值由若干成分按某种 结构组成

struct CStudent 取成员,复制

数据类型封装了数据存储与操作的具体 细节。该概念是从C语言中的数据类型的 角度下的定义。

1.3 抽象数据类型的表示与实现
? ?

一、抽象数据类型(ADT) (1)抽象数据类型(ADT):一个数学模型以及 定义在该模型上的一组操作(数据结构中下的 定义)。
?

?

ADT仅仅取决于其逻辑特性,与其在计算机中如何 表示和实现无关,与语言无关。但实际问题或数学 模型最终又必须借助计算机来表示和实现。 编写软件和算法至少需要分两步走: ? 算法设计(思路),只注重数学模型的逻辑特性; ? 算法实现(程序),关注数学模型的计算机表示和 实现。

1.3.1抽象数据类型分类
?

抽象数据类型分类

抽象数据类型分类 原子类型 值不可分解,如int 值由确定数目的成分按某种 固定聚合类型 结构组成,如复数 结构类型 值的成分数目不确定,如学 可变聚合类型 生基本情况

1.3.1抽象数据类型形式定义
?

(2)抽象数据类型的形式定义 抽象数据类型=(D, S, P) 其中: D是数据对象, S是D上的关系集, P是对D的基本操作集。

1.3.1抽象数据类型定义格式
(3)书中定义某个抽象数据类型的格式: ADT 抽象数据类型名{ 数据对象:<数据对象的定义> 数据关系:<数据关系的定义> 基本操作:<基本操作的定义> }ADT 抽象数据类型名
?

1.3.1抽象数据类型定义举例
?

例:线性表的ADT(参见P19)

ADT List{ 数据对象: D={ai| ai∈ElemSet,i=1,2,...,n,n>=0} 数据关系: R={<ai-1,ai>| ai-1,ai∈D,i=2,...,n} 基本操作: InitList(&L) DestroyList(&L)//注意该操作 ListInsert(&L,i,e) ListDelete(&L,i,&e) }ADT List

1.3.2类C语言
?

?

?

任何一种抽象数据类型必须借助一种计 算机语言来描叙和实现。 教材采用“类C语言”讲授,但是注意它 不能在VC++中运行。 课件采用简单的C++(在C语言基础上主 要补充了“引用”这一技术)

1.3.2类C语言语法
类C语言语法示例 #define TRUE 1 #define FALSE 0 #define OK 1 1、预定义常量和类型 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; //Status是函数的类型,其值是函数结果状态代码。 2、数据结构的存储结构 typedef 用户自定义数据类型 ElemType; 函数类型 函数名(函数参数表){ //算法说明 3、基本操作的算法 语句序列 }//函数名 注意:特别添加C++中引用调用的参数传递方式 简单赋值: 变量名=表达式; 串联赋值: 变量名1=变量名2=...=变量名k=表达式; (变量名1,...,变量名k)=(表达式1,...,表达式k); 结构名=结构名; 成组赋值: 结构名=(值1,...,值k); 变量名[]=表达式; 变量名[起始下标..终止下标]=变量名[起始下标..终止下标]; 交换赋值: 变量名<-->变量名; 条件赋值: 变量名=条件表达式 ? 表达式T : 表达式F

4、赋值语句

1.if(表达式) 语句; 2.if(表达式) 语句;else 语句; 3.switch(表达式){ case 值1:语句序列1;break; ... case 值n:语句序列n;break; default:语句序列n+1;break; 5、选择语句 } 4.switch{ case 条件1:语句序列1;break; ... case 条件n:语句序列n;break; default:语句序列n+1;break; } for(赋初值表达式;条件;修改表达式序列)语句; 6、循环语句 while(条件)语句; do{ 语句序列} while(条件); return [表达式]; return; //函数结束语句 7、结束语句 break; //case结束语句 exit(异常代码); //异常结束语句 8、输入和输出 scanf([格式串],变量1,...,变量n);//类C语言中该语句不含符号&,但考试用C语言! 语句 printf([格式串],表达式1,...,表达式n); 9、注释 //文字序列 max(表达式1,...,表达式n),min(表达式1,...,表达式n) 10、基本函数 abs,floor,ceil,eof,eoln 11、逻辑运算 &&与运算;||或运算

1.3.3 C++语言实现举例
?

?

线形表的实现示例:“人员信息管理 (静态线性表)”的C++语言实现。 请从该例直观理解数据元素、逻辑结构、 存储结构、数据类型等各种基本概念的 含义

1.4 算法和算法分析
? ?

? ?

一、算法的定义及特性 1、算法:对特定问题求解步骤的一种描 述。它是指令的有限序列,其中每一条 指令表示一个或多个操作。 注意:算法实质上是一种思路而非代码 设计程序:先输入全班人员的学号、姓 名、成绩,然后输出全体人员的全部信 息和名次。

1.4.1算法的五个特性
算法(对任何合法的输入值)必须总是在执 有穷性 行有穷步之后结束,且每一步都可在有穷时 long factorial(int n)//阶乘 间内完成; { return n*factorial(n-1); } float average(int *a, int num) 算法中每一条指令必须有确切的含义,读者 { long sum=0; 理解时不会产生二义性。并且在任何条件 for(int i=0;i<num;i++) sum+=*(a++); 确定性 下,算法只有唯一的一条执行路径,即对于 return sum/num; 相同的输入只能得出相同的输出。 } printf("%d %d %d", c++, ++c, c++); 算法中描述的操作都可以通过执行有限次已 颠倒13张扑克牌的顺序最少需移动操作多少次? 可行性 经实现了的基本运算来实现。//该定义不严 注:1年=3e7秒=1e17个3.33GHzCPU时钟周期 一个算法有零个或多个的输入,这些输入取 输入 自于某个特定的对象的集合。 int getsum(int n) 一个算法有一个或多个的输出,这些输出是 { int i, sum=0; 输出 同输入有着某些特定关系的量。 for(i=1;i<=n;i++) sum+=i; }//无输出的算法一般没有实际意义

1.4.2算法设计的要求:正确
?

1、正确性:满足具体问题的需求(能够 实现需要的功能)。
?

算法正确性分4个层次,一般达到第3层即可

★1.4.2正确性
算法正确性的四个层次 int max(int a, int b, int { if (a>b) 程序不含语法错误。 if(a>c) return c; } int max(int a, int b, int 程序对于几组输入数据能够得出满 { if (a>b) 足规格说明要求的结果。 if(a>c) return a; } /* 8,6,7 */ /* 9,3,2 */ int max(int a, int b, int 程序对于精心选择的典型、苛刻而 { if (a>b) 带有刁难性的几组输入数据(如最 if(a>c) return a; 小值、最大值、0、负数等)能够 else 得出满足规格说明要求的结果。 if(b>c) return b; } 程序对于一切合法的输入数据都能 产生满足规格说明要求的结果。 c) else return a; c) else return c; c) else return c; else return c;

★1.4.2健壮性
?

2、健壮性:输入数据非法时,算法也能 适当的作出反应(如返回错误消息), 而不会产生奇怪的输出结果。

★1.4.2可读性
?

3、★可读性
?

? ? ?

? ?

标识符的命名要见名知义、标识符的命名习惯: CPerson person; person.name=“张三”; CPerson, c_person, FirstPerson, first_person, per1 缩进格式习惯 必要的注释:不要太多,也不要太少 程序段不要令人产生歧义: *(a++),printf("%d %d %d", c++, ++c, c++); 采用模块化算法,不要使用生僻算法 尽量使用局部变量,不要使用外部变量

1.4.2算法设计的要求
?

?

?

4、高效率:对于解决同一问题的多个算 法,执行时间短的算法效率高。 5、低存储量需求:存储量需求指算法执 行过程中所需要的最大存储空间(如辅 助局部变量、全局变量)。 高效率和低存储量都与问题的规模有关, 并且它们常常相互矛盾,相互矛盾时一 般优先考虑效率。

1.4.2算法设计的要求:举例
? ?

提问:以下三个算法哪个更好? 算法1最快;算法2比较通用,可读性好, 需要1个额外空间;算法3程序虽短,效 率不一定高,可读性差。
算法2 int max(int a, int b, int c) { int m; if (a>b) m=a; else m=b; if (c>m) m=c; return m; }//需要1个额外存储空间,需两 次比较,至少一次赋值 算法3 int max(int a, int b, int c) { if (a<b) a=b; return a>c ? a : c; }//无需额外存储空间,需两次比较, 至多一次赋值

算法1 int max(int a, int b, int c) { if (a>b) if(a>c) return a; else return c; else if(b>c) return b; else return c; }//无需额外存储空间,需两次比较

1.4.3算法效率的度量
?

1.算法效率即算法执行时间。度量方法:
? ?

(1) 事后统计法:依赖程序本身、软硬件环境 (2) 事前估算法:不好估计,影响因素太多。

程序在计算机上运行所需时间的影响因素 算法本身选用的策略、算法优劣 问题的规模 规模越大,消耗时间越多 书写程序的语言 语言越高级,消耗时间越多 编译产生的机器代码质量 机器执行指令的速度
?

综合考虑,比较算法本身的优劣,应主要考 虑指令数与问题的规模之间的关系。

★1.4.3时间复杂度:定义
?

2.算法中基本操作重复执行的次数应当是问题 规模n的函数f(n)。我们称算法中对于所研究的 问题来说是基本操作的操作为原操作,算法的 时间量度应当以原操作的执行次数f(n)为依据, 我们称之为算法的时间复杂度,记做: T (n)=O (f(n)) 即:随着问题规模n的增大,算法执行时间的 增长率和f(n)的增长率相同,就具有相同的时 间复杂度。

★1.4.3时间复杂度
?

提问:增长率相同是什么意思?
?

?

?

?

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(nk) <O(2n)<O(n!)<O(nn) 原操作执行次数和包含它的语句的频度相同。 语句的频度指的是该语句重复执行的次数。 很多情况下难以精确计算原操作的执行次数, 计算时间复杂度通常只需要求出它关于问题规 模n的阶即可

例如:O(an3+bn2+cn+d)=O(n3), O(log2n)=O(log3n)。

★1.4.3时间复杂度:举例
? ?

时间复杂度举例说明。 提问:为何最后2段程序的时间复杂度是分别是 O(log2n)和O(n)而不是O(n)和O(1)?
语句执行频度 循环体执行 频度 1 n 时间复杂度 O(1) O(n) 举例 求和1+2+...+n2 参见程序sum.cpp

语句

{++x;s=0;} 2 for(i=1;i<=n;++i) sum+=i; 3n+2 for(i=1;i<=n;++i) for(j=i+1;j<=n;++j) 约(3n+2)2/2 约n*(n-1)/2 sum+=a[i][j]; for(i=1; i<=n; i+=i) sum+=i; 3[log2n+1]+2 log2 n+1 long factorial(int n)//阶乘 { if(n==0) return 1; return n*factorial(n-1); }

O(n )
O(log2 n)

2

O(n)

★1.4.3时间复杂度
?

?

提问:为何最后2段程序的时间复杂度是 分别是O(log2n)和O(n)而不是O(n)和O(1)? 提示: (1)设频度为k,可求得n=g(k)=2k-1,反 解可求得k=f(n)=log2n+1。 (2)设频度为f(n),则f(n)=1+f(n-1)=n+1。 注意不是f(n)=n*f(n-1)。

★1.4.3时间复杂度
?

提示:提高效率的方法(参见sum.cpp、 card.cpp)
?

? ?

? ?

(1)利用规模小的时候的结论,或根据该结 论大胆获取推论 (2)寻找恰当的数学模型、简化数学模型 (3)借助数学工具,或分析出现结果的最大 可能方向 (4)增大存储空间或借用辅助变量 (5)减小精度或缩小规模或牺牲通用性

★1.4.3平均时间复杂度
?

3.基本操作的执行次数不确定时的时间 复杂度:平均时间复杂度,最坏情况下 时间复杂度
最好情况:比较一次,T(n)=O(1) 最坏情况:比较n次甚至n+1次, T(n)=O(n) 平均:比较n/2次,T(n)=O(n/2)=O(n)

int search(int num[], int n, int key) { for(int i=0;i<n;i++) if(num[i]==key) return i+1; return 0; }

★1.4.4空间复杂度:定义
?

?

类似于算法的时间复杂度,算法的空间 复杂度可以作为算法所需存储空间的量 度。记作: S (n)=O (f (n)) 若额外空间相对于输入数据量来说是常 数,则称此算法为原地工作。

★1.4.4空间复杂度:举例
语句 辅助变量 辅助空间数 空间复杂度 备注 int max(int a, int b, int c) { int m; 原地 if (a>b) m=a; else m=b; m 1 O(1) 工作 if (c>m) m=c; return m; } int getsum(int n) { int sum=0; 原地 sum, i 2 O(1) for(int i=1;i<=n;++i) sum+=i; 工作 return sum; } int search(int num[], int n, int key) { 原地 for(int i=0;i<n;i++) i 1 O(1) 工作 if(num[i]==key) return i+1; return 0; } long factorial(int n)//阶乘 { 形参n n+1 O(n) if(n==0) return 1; return n*factorial(n-1); }

★1.4.4空间复杂度
?

?

?

提问:为什么第4个算法中的形参n占用辅助空 间而其它算法中的形参不占用辅助空间?为何 该算法的空间复杂度是O(n)? 提示:如果输入数据(如形参)所占空间与算 法(如递归)有关,则应同时考虑输入本身所 需空间。P17 如果所占空间量依赖于特定的输入,则除特别 指明外,均按最坏情况来分析。

总结
? ? ? ? ?

本章的主要内容: 1.数据之间的逻辑关系及其分类 2.数据关系的存储方式及其分类 3.算法优劣的评价 4.相关的概念(数据元素、数据结构、数 据的逻辑结构和存储结构、抽象数据类 型、可读性、时间复杂度、空间复杂度)

谢谢!


相关文章:
图形数据结构1
图形数据结构1 - 实验报告书 课程名:题班学姓目: 级: 号: 名: 数据结构 图形数据结构实验(1) 评语: 成绩: 指导教师: 批阅时间: 年月日 《 数据...
数据结构1-3章相关测试题(含答案)
数据结构》第 1 教学单元测试练习题一、选择(60 分) 1、以下说法正确的是 ( ) A、数据元素是数据的最小单位 B、数据项是数据的基本单位 C、数据结构是...
数据结构1-3章相关测试题(含答案)
数据结构1-3章相关测试题(含答案) - 《数据结构》第 1 教学单元测试练习题 选择(60 分) 1、以下说法正确的是 ( ) A、数据元素是数据的最小单位 B、数据...
十套数据结构试题及答案1
十套数据结构试题及答案1 - 数据结构试卷(一)... 1 数据结构试卷(一)参考答案 ... 27 数据结构试卷(二)......
数据结构1
数据结构1_数学_自然科学_专业资料。实验 2 线性表的顺序储存结构实现 13081319 金晨 (3)设计线性表的接口函数”int MergeList(LIST &L1,LIST L2);”,把线性表...
数据结构1-3章习题答案2013
数据结构1-3章习题答案2013 - 一、填空 1、一种数据结构的二元组表示如下: K={a,b,c,d} R=(a,b),(b,c),(c,d),(a,d)} 此数据结构是 图。 ...
数据结构1-5章习题参考答案
数据结构1-5章习题参考答案 - 【参考答案】 第 1 章 绪论 一、填空题 01、 【操作对象】 【关系和运算】 02、 【数据元素】 【关系】 03、 【逻辑结构】...
数据结构试题及答案(1)
数据结构试题及答案(1) - 数据结构试题 一、 单选题 1、 在数据结构的讨论中把数据结构从逻辑上分为 (C ) A C 内部结构与外部结构 线性结构与非线性结构 ...
数据结构1,2章
线性结构的特点:在数据元素的非空有限集中,(1)存在惟一的一个被称做“第一个”的 数据元素; (2)存在惟一的一个被称做“最后一个”的数据元素; (3)除第一...
数据结构第1章习题解答
数据结构第1章习题解答 - 第 1 章习题解答 1.1 什么是数据结构?一个数据结构结构的二元组定义形式是什么样的?举例解释其 含义。 [解答] 概括地说,数据结构...
更多相关标签: