资源描述：
《ch01-绪论&线性表(old).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、绪论绪论学科形成背景复杂非数值处理应用出现，数据量大学科地位程序=数据结构+算法核心问题对具体问题提取数据对象并定义对象间的关系和操作学习目的培养数据抽象能力绪论数据结构的概念数据结构的三个研究方面数据的逻辑结构（算法设计的基础）数据的存储结构（算法实现的基础）数据的操作算法术语数据计算机化的信息。如数字、文字、图像等数据元素（元素、结点）信息处理的基本单位。如书本、学生等数据项（域、属性）不可再分的数据单元。如书号、书名等数据对象数据元素的集合。如书库等术语数据的逻辑结构数据元素集合及元素间的相互
2、关系按元素间的关系分类集合：元素间相互独立线性结构：元素间一对一关系非线性结构：树形结构：元素间一对多关系图形结构：元素间多对多关系逻辑结构的形式定义D_S=(D,S)，即由元素集D和关系集S组成的二元组术语例如复数Complex=(D,S)D={d1,d2}//实部，虚部S={}研究小组Group(D,S)D={T,G1,…,Gn,S11,…,Snm}S={S1,S2}S1={
3、1<=i<=n}S2={
4、1<=i<=n,1<=j<=m}术语数据的存储结构数
5、据的逻辑结构在计算机中的表示分类顺序存储结构逻辑上相邻的元素存放在相邻的存储单元链式存储结构每个元素附加指针字段，用以表示元素间的逻辑关系术语数据类型数据特性的描述，包括值的集合及相关操作基本数据类型不同语言中有不同的定义，如整型、实型、布尔型、字符型、枚举型、数组等结构类型包含多个域，如typedefstruct{char*name;intage;}Student;抽象数据类型(ADT)包括两方面内容的描述数学模型及相关操作的定义数学模型及相关操作的表示与实现ADT的形式定义ADTadt_name
6、{D={…}//数据对象S={…}//数据关系P://基本操作……}ADTadt_name;抽象数据类型(ADT)例如ADT成绩表{D={d1,…,dn}//n个学生的成绩S={
7、di>di+1}P:Input(…);Insert(…);Delete(…);Search(…);}ADT成绩表;抽象数据类型(ADT)用类C语言表示ADTC语言的核心子集，稍加扩充预定义的常量和类型数据的存储结构用typedef描述基本操作用函数形式描述算法和算法分析算法问题的求解过程算法的特性有穷性：
8、在有限时间内完成确定性：指令无二义性可行性：语言支持并可实现输入：零或多个输出：一或多个算法和算法分析算法设计的要求正确性：无编辑、编译错误，逻辑正确可读性：注释齐备、风格良好健状性：具有错误识别和报告功能高效低耗：速度快，所需系统资源少算法效率的度量时间复杂度T(n)：算法中基本操作的重复执行次数考察算法最坏情况下的时间复杂度只计阶数，如多项式阶O(nk)，指数阶O(kn)算法存储空间需求的度量空间复杂度S(n)：输入数据量大小，辅助空间多少考察最坏情况下的空间占用量算法分析例如：for(i=1;
9、i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[j][k]*b[k][j];}时间复杂度T(n)=O(n3)例如：for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i][j]=x;}时间复杂度T(n)=O(n2)重要的数据结构重要的数据结构线性结构线性表顺序表链表特殊的线性结构栈、队列、字符串、数组、广义表等非线性结构树树、二叉树等图图、网等线性表线性表的特征同一线性表中的元素具有相
10、同特性(类型)相邻元素间存在序偶关系具有n个元素的有限序列(a1,…ai-1,ai,ai+1,…,an)前驱元素/后继元素线性表的长度：n位序：i为元素ai在线性表中的位序线性表的ADT定义ADTList{D={ai
11、i=1,…n}S={
12、i=2,…n}P:InitList(&L);DestoryList(&L);ClearList(&L);ListEmpty(L);ListLength(L);GetElem(L,i,&e);PriorElem(L,Cur_e,&pre_e);Ne
13、xtElem(L,Cur_e,&next_e);ListInsert(&L,i,e);ListDelete(&L,i,&e);……}ADTList;线性表的表示和实现线性表的顺序表示和实现线性表的链式表示和实现线性表的顺序表示和实现概念也称顺序表用一组地址连续的存储单元依次存储各元素高级语言中常用静态数组来描述顺序表，但如果线性表大小未定，则可使用语言中提供的动态分配空间机制(如C的malloc,free)来定义特点各元素的存储位置容易计算，易于各元素的随机存取即Lo
