搜索
哈尔滨工业大学第二章基本数据结构及其运算线性表；线性链表；数组；树；图第二章基本数据结构哈尔滨工业大学第二章基本数据结构及运算•1数据结构的基本概念•2线性表及其顺序存储结构•3线性链表及其运算•4数组•5树与二叉树•6图第二章基本数据结构哈尔滨工业大学2.1数据结构基本概念数据结构：逻辑结构、存储结构、运算第二章基本数据结构哈尔滨工业大学1.数据结构举例•无序表和有序表1621293335434654788535167885432933215446有序表无序表第二章基本数据结构线性表哈尔滨工业大学•学生成绩表：学号姓名性别年龄成绩01张三男208602李四男198303王五女197004赵六男219105钱七女187806刘八女198007朱九男189508孙十女2189第二章基本数据结构线性表哈尔滨工业大学树……..……..…...…...…...…...第二章基本数据结构•井字棋对弈的问题：哈尔滨工业大学•五叉路口的交通灯管理问题：右行规则道路Ｃ、E的箭头表示单行道用多少种颜色的交通灯分配路线，不考虑过度灯CEDABABACADBABCBDDADBDCEAEBECED图第二章基本数据结构哈尔滨工业大学2.什么是数据结构•－－是指相互有关联的数据元素的集合。•定义理解数据结构＝数据元素＋前后件关系–数据元素（dataelement）：•是组成数据的基本单位。–前后件关系：•数据元素的任何关系都可以用前后件关系来描述–举例：•E.g.1一年四季数据结构；•E.g.2家庭成员数据结构；第二章基本数据结构哈尔滨工业大学3.数据结构的内涵•数据结构包含三个方面的内容：–数据的逻辑结构；–数据的存储结构;–对数据所施加的运算。数据的逻辑结构独立于计算机，是数据本身固有的。是逻辑结构在计算机内存中的映像必须依赖于计算机。指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。第二章基本数据结构哈尔滨工业大学4.数据逻辑结构•1.反映数据元素之间逻辑关系的数据结构–逻辑结构表示：B＝（D，R)其中D:数据元素集合；R:D中各数据元素之间的前后件关系。–举例：•E.g.1一年四季数据逻辑结构；•E.g.2家庭成员数据逻辑结构；•E.g.3mxn矩阵数据逻辑结构；第二章基本数据结构哈尔滨工业大学4.数据逻辑结构•2.数据逻辑结构类型–线性结构•线性结构判定条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多一个后件。•线性结构插入或删除任一结点后还是线性结构。–非线性结构e.g.树结构和图结构第二章基本数据结构没有前件的结点哈尔滨工业大学4.数据逻辑结构E.g.用图形表示数据结构B＝（D，R）D＝{di|1≤i≤7}＝{d1，d2，d3，d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}第二章基本数据结构d1d7d6d5d4d3d2根节点终端节点非线性结构哈尔滨工业大学4.数据逻辑结构第二章基本数据结构ACDB非线性结构若在数据结构中，插入或删除任何节点后就不满足线性结构的两个条件，则该结构为非线性结构。哈尔滨工业大学5.数据存储结构•数据逻辑结构在计算机存储空间中的存放形式•常用的存储结构包括：–顺序存储：–链接存储：–索引存储：–散列存储：•一种逻辑结构可根据需要表示成多种存储结构第二章基本数据结构哈尔滨工业大学6.数据结构的运算•基本运算：–插入–删除•其它运算：–查找–分类–合并–复制–修改•空数据结构第二章基本数据结构哈尔滨工业大学2.2线性表及其顺序存储结构线性表及其运算栈及其运算队列及其运算第二章基本数据结构哈尔滨工业大学2.2.1线性表及其运算第二章基本数据结构哈尔滨工业大学1.什么是线性表•线性表：–是由n(n≥0)个数据元素组成的有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。逻辑上为一个一维向量：(a1,a2,a3,……an)–特征：•有且只有一个根结点a1，其无前件；•有且只有一个终结点an，其无后件；•其它结点有且只有一个前件及后件。–线性表的长度：n（n=0，定义为空表）第二章基本数据结构哈尔滨工业大学–英文小写字母表(a，b，c，…，z)是一个长度为26的线性表–矩阵是一个比较复杂的线性表–学生情况登记表是一个复杂的线性表由若干数据项组成的数据元素称为记录(record)由多个记录构成的线性表又称为文件(file)1.什么是线性表第二章基本数据结构哈尔滨工业大学2.线性表顺序存储结构•对应到程序设计语言中的一维数组a1a2a3……aiai+1ai+2……an序号内容插入前第二章基本数据结构占k个字节占k个字节占k个字节占k个字节占k个字节占k个字节占k个字节存储地址ADR(a1)ADR(a1)+kADR(a1)+2kADR(a1)+(i-1)kADR(a1)+ikADR(a1)+(i+1)kADR(a1)+(n-1)k哈尔滨工业大学用来泛指某种数据类型3.线性表C语言描述#definemaxsizemaxlenstructsequenlist{Elemtypea[maxsize];intlen;}；表示线性表（a1，a2，….,an）len表示线性表的实际长度maxlen表示线性表允许的最大长度第二章基本数据结构哈尔滨工业大学线性表顺序存储结构下的运算：–(1)在线性表的指定位置处加入一个新的元素（即线性表的插入）–(2)在线性表中删除指定的元素（即线性表的删除）–(3)在线性表中查找某个（或某些）特定的元素（即线性表的查找）–(4)对线性表中的元素进行整序（即线性表的排序）–(5)按要求将一个线性表分解成多个线性表（即线性表的分解）–(6)按要求将多个线性表合并成一个线性表（即线性表的合并）–(7)复制一个线性表（即线性表的复制）–(8)逆转一个线性表（即线性表的逆转）。第二章基本数据结构哈尔滨工业大学4.线性表基本运算－插入第二章基本数据结构E.g.用如图为一个长度为8的线性表顺序存储在长度为10的存储空间中。现要求在第2个元素(18)之前插入一个新的元素87，之后在新的线性表的第9个元素之前插入一个新元素23。291856633524314687长度为8的线性表298718566335243146插入87之后2329871856633524312346插入23之后再次插入新元素则会“上溢”哈尔滨工业大学线性表在顺序存储下的插入算法输入：线性表的存储空间V(1：m)；线性表的长度n（n≤m）；插入的位置i（i表示在第i个元素之前插入）；插入的新元素b。PROCEDUREINSL(V，m，n，i，b)1.IF(n＝m)THEN{OVERFLOW；RETURN}2.IF(i＞n)THENi＝n＋13.IF(i＜1)THENi＝14.FORj＝nTOiBY－1DOV(j＋1)＝V(j)5.V(i)＝b6.n＝n＋17.RETURN第二章基本数据结构哈尔滨工业大学•C语言算法描述：–在长度为n的线性表中第i个元素前插入新元素x(i为插入位置)M为线性表最大长度；n_pointer存放线性表已有的记录数intInsert_list(inti,Elementx,Elements[],int*n_pointer,intM){intj,n;n=*n_pointer;if(n==M)return(0);elseif(i1)i=1;elseif(in)s[n]=x;for(j=n;j=i;j--)s[j]=s[j-1];s[i-1]=x;n++;*n_pointer=n;return(1);}}n为线性表实际长度从i开始的元素后移注意“上溢”第二章基本数据结构哈尔滨工业大学上文回顾•算法的复杂度分析•数据结构的基本概念•线性表时间频度、时间复杂度、空间复杂度逻辑结构:B=(D,R);线性结构;非线性结构存储结构运算特征顺序存储表示插入运算哈尔滨工业大学5.线性表基本运算－删除第二章基本数据结构E.g.用如图为一个长度为8的线性表顺序存储在长度为10的存储空间中。现要求删除线性表中的第一个元素。之后，删除线性表中的第6个元素。2918566335243146长度为8的线性表18566335243146删除29之后185663352446删除31之后如线性表为空，则“下溢”错误。哈尔滨工业大学线性表在顺序存储下的删除算法输入：线性表的存储空间V(1：m)；线性表的长度n（n≤m）；删除的位置i（表示删除第i个元素）。PROCEDUREDESL(V，m，n，i)1.IF(n＝0)THEN{UNDERFLOW；RETURN}2.IF(i＜1)or(i＞n)THEN{“Notthiselementinthelist”；RETURN}3.FORj＝iTOnDOV(j-1)＝V(j)4.n＝n－15.RETURN第二章基本数据结构哈尔滨工业大学intDelete_list(inti,ints[],int*n_pointer){intj,n;n=*n_pointer;if((i1)||(in)||(n=0))return(0);for(j=i;jn;j++)s[j-1]=s[j];n--;*n_pointer=n;return(1);}•C算法描述–在长度为n的线性表中删除第i个元素n_pointer存放线性表已有的记录数n为线性表实际长度从i开始的元素前移注意“下溢”错误第二章基本数据结构哈尔滨工业大学2.2.2栈及其运算第二章基本数据结构哈尔滨工业大学什么是栈E.g主程序与子程序之间的调用关系MAINSUB1SUB2SUB3SUB4…………………………CALLSUB1CALLSUB2CALLSUB3CALLSUB4……A：……B：……C：……D：……………………………………ENDRETURNRETURNRETURNRETURN第二章基本数据结构哈尔滨工业大学SUB1SUB2SUB3B:C:D:SUB4RETURNRETURNRETURNRETURNMAINA:ENDAABABCABCDABCABA线性表第二章基本数据结构哈尔滨工业大学1.栈•栈(stack)是限定在一端进行插入与删除的线性表。•允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。•栈是按照“先进后出”(FILO—FirstInLastOut)或“后进先出”(LIFO—LastInFirstOut)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。第二章基本数据结构a3a2a1……an栈顶top栈底bottom入栈出栈12345表尾表头哈尔滨工业大学第二章基本数据结构1.栈•用指针top来指示栈顶的位置，用指针bottom指向栈底。•往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算•栈的物理存储可以用顺序存储结构，也可以用链式存储结构。在顺序存储结构中，栈底指针bottom总是指向栈空间的低地址一端（数组的起始地址）。哈尔滨工业大学2.栈运算举例A进BA进A出CA进A出DA进A出出初始出栈元素顺序：B→C→D→A第二章基本数据结构哈尔滨工业大学3.栈的运算—栈的定义与初始化•顺序栈的定义#defineM10structSQSTACK{intelem[M];inttop;};栈顶top第二章基本数据结构•栈的初始化voidInitStack(structSQSTACK*stack){stack-top=0;}哈尔滨工业大学4.栈的运算—栈的判空与判满•栈判空intStackEmpty(structSQSTACKstack){if(stack.top==0)return(1);return(0);}第二章基本数据结构•栈判满intStackFull(structSQSTACK*stack){if(stack-top==M)return(1);return(0);}哈尔滨工业大学5.栈运算—入栈pushintPush