实用数据结构电子教案数组与线性表公开课一等奖优质课大赛微课获奖课件.pptx

数据结构第二章 数组与线性表第1页第1页第二章 数组与线性表 知 识 点 数组基本特点及寻址方式线性数据结构基本特性和基本运算堆栈定义和基本运算队列定义和基本运算循环队列特性，运算以及判断溢出条件与普通队列差别堆栈、队列简朴应用 难 点 循环队列特点及判断溢出条件利用本章基本知识设计有效算法处理与线性相关应用问题 第二章 数组与线性表第2页第2页要 求 纯熟掌握下列内容：线性表基本运算堆栈特性、基本运算并能设计简朴算法队列、循环队列特性、基本运算并能设计简朴算法 理解下列内容：线性表运算时间复杂性分析堆栈、队列实际应用 第二章 数组与线性表第3页第3页第二章目录2.1 数组及另一方面序存放结构2.2 线性表及其运算 2.3 堆栈及其应用2.4 队列及其应用2.5 应用实例及分析小 结习题与练习第二章 数组与线性表第4页第4页2.1.1 数组数组是由一些单元构成，每个单元相应着一组下标值和一个数组元素。n维数组每个单元相应n个下标值。数组元素能够是基本数据类型，如整数型、实数型、字符型等，也能够是有多个数据项一个结构。同一数组中各个元素必须是同一数据类型，每个数组元素都占有相同数量存储单元，才干用下标来唯一确实定数组中元素。第二章 数组与线性表第5页第5页2.1.2 数组顺序存储结构 在计算机中，表示数组是采用一组连续存储单元顺序地存储各数组元素。能够用下标值随机访问该数组任意一个元素。计算数组元素存储地址公式称为寻址公式。设数组为A，每个数组元素占s个存储单元，一旦定义了它维数和各维上、下界，就能够得到计算数组元素地址寻址公式。第二章 数组与线性表第6页第6页1.一维数组寻址公式对于一维数组，若其下标下界为LB，上界为UB，第一元素（其下标为LB）地址为Loc(LB)，下标为i数组元素Ai地址为Loc(i)，则计算Loc(i)寻址公式为：Loc(i)=Loc(LB)+(i-LB)*s 在C语言中，数组下标下界为0，则数组中任意一元素Ai寻址公式为：Loc(i)=Loc(0)+i*s 0in-1 第二章 数组与线性表第7页第7页2.二维数组寻址公式在C语言中，采用矩阵元素以行为主存储，即同一行元素连续存储，存储完一行再存储下一行。设二维数组Amn，m、n分别表示数组行和列，用Loc(i,j)表示数组元素Aij地址，每个单元占用s个存储单元，则寻址公式为：Loc(i,j)=Loc(0,0)+(i*n+j)*s 0im-1,0jn-1 第二章 数组与线性表第8页第8页定义一A23数组，相应矩阵下列：数组元素A12，其下标i=1，j=2，故它前面已有i=1行，每行有3个元素，另外本行有j=2个元素，因此在元素A12之前，本数组已有5个元素。第二章 数组与线性表第9页第9页3.三维数组寻址公式三维数组Amnp可分解为p个m*n二维数组。按行为主存储数组元素Aijk寻址公式为：Locijk=Loc000+(i*n*p+j*p+k)*s 0im-1,0jn-1，0pp-1 对于更多维数组，数组元素在内存中存储能够这类推。返回第二章 数组与线性表第10页第10页2.2.1 线性表（Linear List）线性表是由有限数目的相同类型元素构成序列。表中数据元素，除了第一个和最后一个以外，都有一个且只有一个前驱元素，同时也都有一个且只有一个后继元素；第一个元素只有一个后继元素而无前驱元素；最后一个元素只有一个前驱元素而无后继元素。线性表元素个数n称为这个表长度，当n=0时，这个表叫做空表。第二章 数组与线性表第11页第11页线性表在计算机内存中采用各元素顺序存储方式，这种存储结构叫做向量。每个线性表元素叫做这个向量一个分量。假如已知线性表第一个元素地址和每个元素占用存储单元数，由任一元素序号就能够计算出该元素在内存中地址。在编程时以一维数组表示线性表最简朴，用也最普遍。第二章 数组与线性表第12页第12页2.2.2 线性表运算对于给定线性表，可进行下列基本运算：1.求线性表长度n；2.在第i个数据元素前面插入一个新数据元素；3.删除第i个数据元素；4.存取或更新线性表第i个元素；5.将两个或两个以上线性表合并成一个线性表；6.将一个线性表拆成多个线性表；7.将线性表中各数据元素按某个域值（如关键字）递增或递减顺序重新排列；8.在线性表中查找满足某种条件数据元素；第二章 数组与线性表第13页第13页1.数据元素插入(insert)设用一个一维数组An表示此线性表，本来有m个元素（mn），元素值已给定。要求数组下标从1开始，即这里数据元素相应数组下标从1到n。要求在第i个元素前插入一个新数据元素，值为G，因原线性表数据元素是连续排列，中间没有空单元，因此第i个元素及其后面各元素均需向后移动一个单元位置，这样才干将G插入到i位置，且元素总数由m增长为（m+1）。第二章 数组与线性表第14页第14页插入函数 void insert(A,int n,m,i,G)int j;if(in+1)printf(“i值错！n”);else for(j=m;j=i;j-)Aj+1=Aj;/*将第i个元素及其后面元素后移*/Ai=G;m+;/*线性表长度加1*/第二章 数组与线性表第15页第15页插入函数分析在循环语句中，当i=1时，须循环m次，表示元素插入线性表头前面，则原线性表中m个元素均须向后移动一个单元，这是最不利情况。当i=m+1时，则循环一次也不进行，这时元素直接插入到线性表尾后面，因此线性表所有m个元素均不移动，这是最好情况。第二章 数组与线性表第16页第16页2.数据元素删除(Delete)设用一个一维数组An表示此线性表，本来有n个元素，元素值已给定。要求删除第i个数据元素，由于线性表元素在数组中必须连续排列，中间不能有空单元，故将此元素删除后，它后面所有元素都需要向前移动一个单元，且数据元素总数由本来n减少到n-1.第二章 数组与线性表第17页第17页删除函数 void delete(A,int n,i)int j;if(in)printf(“i值错！n”);else for(j=i;j=n;j+)Aj=Aj+1;n-;第二章 数组与线性表第18页第18页删除函数分析在循环语句中，当i=1时，需循环(n-1)次，这是要删除线性表表头元素，是最不利情况；当i=n时，则循环一次也不执行，只是将元素数目n比本来减少一个，而第n个数据元素不必再考虑，其余各单元元素均维持不变，这是最好情况。第二章 数组与线性表第19页第19页3.算法时间复杂性 能够用数据元素移动次数来度量这两个算法时间复杂性。插入时，至少循环0次，最多循环n次，如i各种取值概率相同，则平均循环次数为n/2；删除时至少循环次数为0次，最多为n-1次，当i取值概率相同时，平均循环次数为(n-1)/2。用数量级形式表示线性表插入、删除运算时间复杂性均为O(n)。返回第二章 数组与线性表第20页第20页2.3.1 堆栈(Stack)堆栈也简称为栈，是限定在表一端进行插入或删除操作线性表。进行插入或删除操作一段称为栈顶（top），另一端称为栈底（bottom）。插入元素又称为入栈（push），删除元素操作称为出栈（pop）。不含元素栈称为空栈。堆栈元素插入和删除只在栈顶进行，总是后进去元素先出来，因此堆栈又称为后进先出线性表或LIFO（Last-In-First-Out）表。第二章 数组与线性表第21页第21页堆栈表示堆栈最简朴表示办法是采用一维数组，为形象起见，普通在图中将堆栈画成竖直。设数组名为STACK，其下标下界为1，上界为n。普通需用一个变量top统计当前栈顶下标值，top也叫做栈指针。第二章 数组与线性表第22页第22页本例中top=4 topADCB4753216STACK第二章 数组与线性表第23页第23页1.入栈（push）入栈主要操作是先将栈顶指针加1；然后将入栈元素放到栈顶指针所批示下标值位置上。设用下标从1到n数组ST表示堆栈，入栈元素值为G，则可得到入栈函数下列：第二章 数组与线性表第24页第24页入栈函数 void push(ST,int n,top,G)if(top=n)printf(“栈溢出!n”);/*显示栈满信息*/else top=top+1;STtop=G;第二章 数组与线性表第25页第25页2.出栈（Pop）出栈运算时，先将栈顶元素值赋给某个变量，以备后面运算应用；然后栈顶指针减1，将栈顶位置下移。假设已指定变量为x，则出栈函数下列：第二章 数组与线性表第26页第26页出栈函数void pop(ST,int top,x)if(top=0)printf(“空栈!n”);/*栈为空显示相应信息*/else x=STtop;top=top-1;/*栈顶位置下移*/第二章 数组与线性表第27页第27页2.3.2 堆栈应用 1.堆栈在函数调用中应用:设有三个函数A1，A2，A3，这三个函数有下列调用关系：函数A1在其函数体某处r调用函数A2，函数A2又在其函数体某处t调用函数A3，函数A3不调用其它函数。rtA1A2A3第二章 数组与线性表第28页第28页函数嵌套调用A1调用A2，A2调用A3时返回地址在堆栈中情况如右图所表示。toprtSTACK第二章 数组与线性表第29页第29页2.堆栈在表示式计算中应用 一个算术表示式，比如A+B，其中加号“+”称作运算符，而A，B称为运算数。对于由两个运算数和一个运算符构成表示式，习惯上是将运算符写在两个运算数中间，这叫做中缀形式。计算机处理表示式时，常把运算符放在两个运算数后面或前面。1.把运算符放在两个运算数后面，比如 AB+，称为后缀形式，也叫做波兰式。2.把运算符放在两个运算数前面，比如+AB，则称做前缀形式，也叫做逆波兰表示式。第二章 数组与线性表第30页第30页算术表示式不同运算符有不同运算优先次序，如，在没有括号时，乘除运算（*或/）要比加减运算（+或-）优先进行。下面用一个简朴例子说明编译系统在处理算术表示式时，是怎样应用堆栈这种数据结构。假定表示式运算数都是使用单个字母表示，式中无括号且只有加、减、乘、除4种运算，而没有更复杂运算，比如表示式 X+Y*Z。第二章 数组与线性表第31页第31页使用S1和S2两个堆栈，S1用于存放运算数，S2用于存放运算符。编译系统处理时，将表示式从左向右逐一扫视一遍，并依据不同情况按以下标准处理:1)若是运算数，则将其压入S1栈；2)若是运算符且S2栈是空栈则将其压入 S2栈；3)若是运算符且S2栈为非空栈，且此运算符级别高于S2栈顶运算符级别，则将此运算符压入S2栈；4)凡不属于上面三条情况，则将S2栈顶运算符与S1栈最上面两个运算数出栈进行运算，并将运算结果压入S1栈。第二章 数组与线性表第32页第32页图中每一步上面括号中数字表示该步是按哪一条原则处理。返回第二章 数组与线性表第33页第33页2.4.1 队列（Queue）队列是一个运算受限制线性表，元素添加在表一端进行，而元素删除在表另一端进行。允许添加元素一端称为队尾（Rear）；允许删除元素一端称为队头（Front）。向队列添加元素称为入队，从队列中删除元素称为出队。新入队元素只能添加在队尾，出队元素只能是删除队头元素，队列特点是先进入队列元素先出队，因此队列也称作先进先出表或FIFO（First-In-First-Out）表。第二章 数组与线性表第34页第34页队列表示与堆栈类似，队列也能够简朴用一维数组表示。设数组名为Queue，其下标下界为1，上界为n。普通使用一个变量r批示队尾下标值，叫做队尾指针；用另一个变量f批示队头下标值，称为队头指针。队列中元素数目等于零称为空队列，此时队头指针和队尾指针均为零，即f=r=0。第二章 数组与线性表第35页第35页假定有AF 6个元素先后进入队列，但A、B两个元素已陆续出队了，故队尾指针r=6，而队头指针f=3。第二章 数组与线性表第36页第36页1.入队（insert）当给队列插入元素时，队尾指针r后移而队头指针不动，但有一个情况例外，即当向空队列插入第一个元素时，队头指针与队尾指针同时由0变为1。设用下标从1到n数组Q表示队列，且已知待添加元素在变量x中。第二章 数组与线性表第37页第37页入队函数 void insert(Q,int n,f,r,x)if(r=n)printf(“溢出!n”);/*判断是否已到数组末端*/else r=r+1；Qr=x;/*插入元素*/if(f=0)f=1;/*判断本来是否为空队列*/第二章 数组与线性表第38页第38页2.出队（Delete）当从队列删除元素时，队头指针f后移而队尾指针r不动，但也有一个情况例外，即当删除了最后一个元素，队列成为了空队列时，队头指针与队尾指针同时变为0。假设要求将出队元素值赋给变量x。第二章 数组与线性表第39页第39页出队函数void Delete(Q,int f,r,n,x)if(f=0)printf(“下溢出!n”);/*判断是否为空队列*/else x=Qf;/*取队头元素给x赋值*/if(f=r)f=0;/*若出队是最后一个元素，变成空队列*/r=0;else f=f+1;/*队头指针后移*/第二章 数组与线性表第40页第40页3.队列存在问题 由于队列入队操作是在两端进行，伴随元素不断插入，删除，两端都向后移动，队列会不久移动到数组末端造成溢出，而前面单元无法利用。处理办法：1)每次删除一个元素后，将整个队列向前移动一个单元，保持队列头总固定在数组第一个单元。2)将所用数组想象成是头尾相接圆环，当队列尾端到达数组末端（第n个单元）时，假如再插入元素可继续使队列向数组前端（第1个单元）延长，此队列称为循环队列。第二章 数组与线性表第41页第41页2.4.2 循环队列图中阴影部分为队列中元素。如何判断一个循环队列是满还是空？第二章 数组与线性表第42页第42页判断循环队列是否满或空 满：队尾通过一个循环而到达队首前一个单元时，这种情况下假如再插入新元素时，新元素就要把原队头元素覆盖，因此，当r=f时，插入新元素会造成队列首尾重叠；空：在队列进行删除运算时，当f=r时表明删除是队列最后一个元素，删除这个元素后，队列就变成空队列。第二章 数组与线性表第43页第43页循环队列入队函数void insert(Q,int n,f,r,i)if(r=n)r=1;/*到达数组末端则向前端延长*/else r=r+1;if(r=f)printf(“溢出！n”);else Qr=i;/*插入新元素*/if(f=0)f=1;/*鉴定是否本来是空队列*/第二章 数组与线性表第44页第44页循环队列出队函数void Delete(Q,int n,f,r,x)if(f=0)printf(“是空队列！n”);/*是否为空*/else x=Qf;/*取队头元素赋给变量x*/if(f=r)f=0;r=0;else if(f=n)f=1;/*由数组末端移到前端*/else f=f+1;/*队头指针后移*/第二章 数组与线性表第45页第45页2.4.3 队列应用 对于各种含有“先进先出”需排队处理问题，都能够应用队列来处理。比如，操作系统在管理和分派系统资源时，大量应用了队列这种数据结构。1)队列在输入/输出管理中应用 2)对CPU分派管理 返回第二章 数组与线性表第46页第46页例2.1 一个双向栈是将两个栈用一个数组构成，它们栈底分别设在数组两端。当一个栈中元素数目小于n/2时，另一个栈相应能够不小于n/2。试写出以数组高端为底栈入栈和出栈算法。第二章 数组与线性表第47页第47页例2.1解答这个栈栈顶指针top2是按相反方向移动，因此算法有所不同：入栈时为：top2=top2-1出栈时为：top2=top2+1 两个栈在进栈过程中预防溢出条件是：top2=top1+1。出栈过程中预防下溢出及判断空栈条件分别为：top1=0，top2=（n+1）。第二章 数组与线性表第48页第48页入栈算法 void push(ST,int n,top1,top2,G)if(top2=top1+1)printf(“溢出!n”);else top2=top2-1;STtop2=G;/*插入新元素*/第二章 数组与线性表第49页第49页出栈算法void pop(ST,int n,top1,top2,x)if(top2=n+1)printf(“下溢出!n”);else x=STtop2;top2=top2+1;第二章 数组与线性表第50页第50页例2.2 对于循环队列，试写出求队列长度算法。解1：设队列最大元素个数为n，设一个计数器，将其初始值设为0。从队首开始，沿着队列顺序搜索，每走过一个元素，计数器加1，直到队尾，则计数器最后值即为队列长度。解2：利用队头指针与队尾指针也可求出队列长度：当rf时，length=r-f；当r=f)length=r-f;else length=(r+n+1)-f;return(length);返回第二章 数组与线性表第53页第53页小 结 本章主要简介了采用顺序存储结构线性表及实现各种基本运算算法。数组线性表 堆栈队列 返回第二章 数组与线性表第54页第54页习题与练习 一、基本知识题 1.什么是数组？数组主要特点是什么？2.什么是线性表？线性表主要运算有哪些？3.什么是栈？什么是队列？它们各自特点是什么？4.线性表、栈、队列有什么异同？5.简述栈入栈、出栈操作过程。6.在循环队列中简述入队、出队操作过程。7.在什么情况下，才干使用栈、队列等数据结构？8.有A、B、C三个数组：A8，B47，C586，试计算它们元素个数是多少？第二章 数组与线性表第55页第55页二、算法设计题 1.设有一n个元素线性表，用一维数组An表示。试设计一个算法，使此线性表元素排队顺序颠倒过来但仍存储于原数组中。2.设用一维数组stackn表示一个堆栈，若堆栈中一个元素需占用length个数组单元（length 1），试写出其入栈、出栈操作算法。第二章 数组与线性表第56页第56页3.试编写一个遍历及显示队列中元素算法。4.设一循环队列Queue，只有头指针front，不设尾指针，另设一个内含元素个数计数器，试写出相应入队、出队算法。5.设计一算法能判断一个算术表示式中圆括号配对是否正确。（提醒：对表示式进行扫描，凡碰到“（”就进栈，碰到“）”就退出栈顶“（”，表示式扫描完毕时栈若为空则圆括号配对正确。）返回第二章 数组与线性表第57页第57页谢谢收看 返回第二章 数组与线性表第58页第58页