计算机二级数据结构与算法.ppt

*二级公共基础05年4月试题（1）数据的存储结构是指????A）存储在外存中的数据B）数据所占的存储空间量C）数据在计算机中的顺序存储方式D）数据的逻辑结构在计算机中的表示第30页，讲稿共67页，2023年5月2日，星期三*线性结构与非线性结构有且只有一个根结点（没有前件的结点）。每一个结点最多只有一个前件，也最多只有一个后件。第31页，讲稿共67页，2023年5月2日，星期三*线性结构A,B,C,·······，X,Y,Z学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表——结点间是以线性关系联结ABC第32页，讲稿共67页，2023年5月2日，星期三*非线性结构如果数据结构不满足线性结构的条件，则称之为非线性结构。此外，在线线结构中插入或删除一个结点，还应是线线结构，否则此结构非线线ABCD第33页，讲稿共67页，2023年5月2日，星期三*树形结构全校学生档案管理的组织方式计算机程序管理系统也是典型的树形结构第34页，讲稿共67页，2023年5月2日，星期三*ABCDEFGH树形结构——结点间具有分层次的连接关系HBCDEFGA第35页，讲稿共67页，2023年5月2日，星期三*1.3线性表1.3.1线性表的定义线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，……，ai，……，an其中n称作表的长度，当n=0时，称作空表。第36页，讲稿共67页，2023年5月2日，星期三*线性表的特点：1.线性表中所有元素的性质相同。2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前件和一个后件。第一个数据元素无前件，最后一个数据元素无后件。3.数据元素在表中的位置只取决于它自身的序号。在线性表上常用的运算有：初始化、求长度、取元素、修改、前插、删除、检索、排序。第37页，讲稿共67页，2023年5月2日，星期三*1.3.2线性表的顺序存储结构线性表顺序存储结构的特点：1、线性表所有元素所占的存储空间是连续的。2、线性表各数据元素在存储空间中是按逻辑顺序依次存放的。在计算机中存放线性表，采用顺序存储是一种简单方便的方法。第38页，讲稿共67页，2023年5月2日，星期三*元素an……..元素ai……..元素a2元素a1bADR(a1)+k存储地址内存状态顺序存储结构示意图(顺序表)：首地址ADR(a1)每个元素所占用的存储单元个数ADR(a1)+(i-1)*kADR(a1)+(n-1)*kADR(ai)=ADR(a1)+(i-1)*k第39页，讲稿共67页，2023年5月2日，星期三*n-1线性表的插入和删除运算示意图ai-1…..a2a1an…ai+1aixai-1…..a2a1aiai+1…alengthan……ai+1aix删除运算插入运算第40页，讲稿共67页，2023年5月2日，星期三*若长度为n的线性表表示为：(a1,a2,…,ai,…an)运算后表示为：(a’1,a’2,…,a’i,…a’n)，则满足以下关系：插入新元素b后a’jaj1=j=i-1bj=iaj-1i+1=j=n+1长度增加为：n+1删除第i个元素后a’jaj1=j=i-1aj+1i=j=n-1长度减少为：n-1第41页，讲稿共67页，2023年5月2日，星期三*1.4栈和队列1.4.1栈和队列的定义栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。第42页，讲稿共67页，2023年5月2日，星期三*1.4.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为先进后出(FILO)或后进先出(LIFO)设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；栈底（bottom):不允许插入和删除的一端。约定用指针top始终指向栈顶的位置，用指针bottom指向栈底。a1a2….ai