西南民院计算机系

《西南民院计算机系》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》西南民院计算机系北京理工大学现代远程教育TEL85572772Email:liuli@swun.cn题型1选择题2填空题3解答题4算法题第一章绪论第一章绪论计算机的发展硬件CPU、内、外存储器等软件：系统软件、应用软件应用科学计算数据处理过程控制等处理数据的能力和种类：数值字符、字符串具有多个属性对象图形图像声音数据结构的研究对象：非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。本课程讨论的问题：应用中常用的几种数据结构，以及如何存储,如何处理它们。第一章绪论1数据：客观对象的符号表示。例如：课程名，地

2、名，书名都是数据2数据结构：带有结构和操作的数据元素集合结构：数据元素之间的关系；操作：对数据的加工处理；第一章绪论第一章绪论3数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。4常用的有下列几类基本结构：（1）集合（2）线性结构（3）树结构（4）图结构（5）其它复杂结构5数据结构的基本操作：也叫基本运算：是指对数据结构的加工处理；第一章绪论6数据的存储结构：数据结构在计算机内存中的表示。7顺序存储结构用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系；8链式存储结构用任意一组存储单元存储数据

3、元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。数据结构基本操作的实现：基本操作在计算机上的实现（方法）9数据结构的表示1图示表示2二元组表示图示表示：由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系；第一章绪论JIHGFEDBAC二元组表示用一个二元组（D，S）表示数据结构，其中D是数据元素集合，S是D上关系的集合。D={A，B，C，D，E，F，G，H，I，J}S={R}R={〈A,B>,,,,,,,}第一章绪论

4、第一章绪论10算法的概念算法是求解问题的操作序列（或操作步骤）11时间复杂度T（n）以求解问题的基本操作（原操作）的执行次数作为算法的时间度量空间复杂度用执行算法所需的辅助空间的大小作为算法所需空间的度量第一章　练习题1数据结构：带有结构和操作的数据元素集合。2常用的数据结构数据结构的表示4数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。数据结构的基本操作：也叫基本运算：是指对数据结构的加工处理；数据的存储结构：数据结构在计算机内存中的表示数据结构基本操作的实现：基本操作在计算机上的实现（方法）顺序存储结构链式存储结构10算

5、法的概念算法是求解问题的操作序列（或操作步骤）。11时间复杂度T（n）以求解问题的基本操作（原操作）的执行次数作为算法时间的度量第二章线性表常用的数据结构1）集合2）线性结构3）树结构4）图结构5）其它复杂结构第二章　线性表对每种数据结构，主要讨论如下两方面的问题1数据的逻辑结构，数据结构的基本操作；2数据的存储结构，数据结构基本操作的实现第二章　线性表线性数据结构：除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。2.1线性表的概念一线性表的逻辑结构在线性表中，除第一个元素和最后一个

6、元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。2.1线性表的概念a1a2ai-1aiai+1an线性表的基本操作1初始化操作InitList(&L)2销毁操作DetroyList(&L)3置空操作ClearList(&L)4判空操作ListEmpty(L)5求表长操作ListLength(L)6取元素操作：GetElem(L,i,&e)7查找操作LocateElem(L,e,compare())8插入操作ListInsert(&L,i,e)9删除操作ListDelete(&L,i,&e)10遍历操作ListTra

7、verse(&L,visit())2.1线性表的概念2.2线性表的顺序存储和实现一线性表的顺序存储结构——顺序表1顺序表用一组连续的内存单元依次存放线性表的数据元素。2顺序表的类型定义typedefstruct{ElemType*elem;//线性表存储空间基址intlength;//当前线性表长度intlistsize;//当前分配的存储空间大小}SqList;顺序表图示设A=（a1,a2,a3,...an）是一线性表，L是SqList类型的结构变量，用于存放A2.2线性表的顺序存储和实现L.elemL.lenghtL.lis

8、tsizen99a1a2ai-1aiai+1an01i-2i-1in-199顺序表保存了哪些信息?2.2线性表的顺序存储和实现顺序表保存了哪些信息？*线性表中的数据元素；*线性表中数据元素的顺序关系；*表中元素个数（简化算法）*当前分配的存储空间