《数据结构-绪论》由会员分享，可在线阅读，更多相关《数据结构-绪论（50页珍藏版）》请在金锄头文库上搜索。
1、数据结构绪论抽象数据类型小结和作业地位和作用学习内容算法分析数据（Data）1、形式2、含义数字、字符、图形、图像、音频、视频11111111111111110000000000000001数据类型：int float double(IEEE 754)文件类型：DOC TXT JPG PDF结构（Structure）结构：关系（Relation）数据结构Data_Structure=(D, S)D: a1, a2, a3, , anS: , , D：1, 7, 8, 9D：“ABC”, “City” D：“张明”，“男”，19， “计算机”，“王明辉”，“男”，20，“法律”，数据结构物理结构
2、逻辑结构集合线性表树 图顺序结构链式结构Da1, a2, , anS 集合Da1, a2, , anS |ai-1 ,ai D, i=2,.,n 线性表Da1, a2, ,anS |i j对每个j，存在唯一的i有 树Da1, a2, ,anS |ai D, aj D 图例1有数据结构:D=1, 2, 3, 4, 5 S=, , , 什么数据结构?逻辑结构例1D=1, 2, 3, 4, 5 S=, , , 12345逻辑结构例2有数据结构:D=1, 2, 3, 4, 5, 6, 7 S=, , , , , 什么数据结构?逻辑结构例2D=1, 2, 3, 4, 5, 6, 7 S=, , , ,
3、, 1234675逻辑结构例3有数据结构:D=1, 2, 3, 4, 5, 6, 7,8 S=row, colrow=, , , , , Col=, , , 什么数据结构?逻辑结构例31234675D=1, 2, 3, 4, 5, 6, 7,8 row=, , , , , Col=, , , 8逻辑结构物理结构数据在内存中如何表示？数据之间的关系在内存中如何表示？存储器模型1、电子元器件构成存储单元2、地址寄存器4、地址总线6、数据寄存器物理模型逻辑模型5、数据总线3、地址译码器0123n存储器模型假设有5位同学的成绩表：2006001 992006003 802006004 85200600
4、5 602006006 70顺序存储结构元素n元素i元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容2006001 992006003 802006004 852006005 602006006 70链式存储结构存储内容 L0元素n元素2元素3元素12006001 992006003 802006004 852006005 602006006 70P地位与作用Niklaus Wirth（ N.沃思）教授提出： Programs = Algorithm + Data Structures 地位与作用aX2 + bX + c = 0 #include #includ
5、e int main(int argc, char* argv) int a, b, c; float r1, r2, deta; scanf(“%d%d%d“, deta = b*b -4*a*c; if(deta =a2 地位与作用#include int main(int argc, char* argv) int a10, max, i; for(i=0;i|ai-1 ,ai D, i=2,.,n 抽象数据类型的实现定义存储结构 typedef structElemType*elem;intlength;intlistsize; SqList;抽象数据类型的实现Status ListI
6、nit_Sq(SqList if(!L.elem) return (OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;return (OK);抽象数据类型的实现封装到一个头文件List_Sq.h #include #define TRUE1#define FALSE0#defineOK1#defineERROR0#defineINFEASIBLE -1#defineOVERFLOW -2抽象数据类型的使用作为一个数据类型应用： #include “List_Sq.h“int main(int argc, char* argv)SqList L
7、;ListInit_Sq(L);for(int i=1;i11;i+) ListInsert_Sq(L,i,i);ListDelete_Sq(L,5,i);算法分析算法是为了解决某类问题而规定的一个有限长的操作序列。算法分析：对算法的性能进行分析，便于算法的比较和选用。算法分析：时间复杂性分析和空间复杂性分析通常有两种衡量算法效率的方法:事后统计法事前分析估算法缺点：1、必须执行程序2、其它因素掩盖算法本质算法分析渐进时间复杂性分析方法：1、确定算法的主要操作 2、计算主要操作执行的次数 3、一般的讲，执行次数是输入的函数 4、根据函数的特点，得到函数所属的阶（order）算法分析算法分析求S
8、 = 1 + 2 + 3 +nint S=0, i, n; scanf(“%d“, for( i=1; i=n; i+) S = S + i; printf(“%d“, S); 输入的长度:n主要操作：加法执行加法的次数：n算法的时间复杂性：T(n) =O( n)算法的空间复杂性：S(n) = O(1)函数关系：f(n)=n算法分析函数的分类： 常数阶O(1)对数阶O(logn)线性阶O(n)线性对数阶O(nlogn)平方阶O(n2)指数阶O(2n)小 结物理结构逻辑结构集合线性表树 图顺序结构链式结构数据结构作业及要求阅读： 1、教材的第一章 2、Michael Main. Data Str
9、ucture and Other Objects Using Java. 机械工业出版社Chapter One: The Phases of Software Development作业及要求预习： 1、p18-26 2、C语言的一维数组内存的存放方法访问数组元素的两种方法数组名的内涵动态存储分配 malloc和realloc作业及要求思考：如何用类实现抽象数据类型？ 作业：1.3要求： 1、独立完成作业 2、字迹工整，美观 3、按时交作业 4、做错了的题下次要改正 5、准备两个本子练习2、数据的( )包括集合、线性、树和图结构四种类型 。A.存储结构 B.逻辑结构 C.物理结构 D.基本运算1、数据结构有（ ）结构和（ ）结构两种， 通常是指（ ）结构
