《实用数据结构（修订版） 教学课件 ppt 作者 佟维 谢爽爽 第二章 数组与线性表》由会员分享，可在线阅读，更多相关《实用数据结构（修订版） 教学课件 ppt 作者 佟维 谢爽爽 第二章 数组与线性表（57页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第二章 数组与线性表,第二章 数组与线性表,第二章 数组与线性表,知 识 点 数组的基本特点及寻址方式 线性数据结构的基本特征和基本运算 堆栈的定义和基本运算 队列的定义和基本运算循环队列的特征，运算以及判断溢出的条件与普通队列的差别 堆栈、队列的简单应用 难 点 循环队列的特点及判断溢出的条件 利用本章的基本知识设计有效的算法解决与线性相关的应用问题,第二章 数组与线性表,要 求 熟练掌握以下内容： 线性表的基本运算 堆栈的特征、基本运算并能设计简单算法 队列、循环队列的特征、基本运算并能设计简单算法 了解以下内容： 线性表运算时间复杂性分析 堆栈、队列实际应用,第二章 数组与线性
2、表,第二章目录,2.1 数组及其顺序存储结构 2.2 线性表及其运算 2.3 堆栈及其应用 2.4 队列及其应用 2.5 应用实例及分析 小 结 习题与练习,第二章 数组与线性表,2.1.1 数组,数组是由一些单元组成的，每个单元对应着一组下标值和一个数组元素。 n维数组的每个单元对应n个下标值。 数组元素可以是基本数据类型，如整数型、实数型、字符型等，也可以是有多个数据项的一种结构。 同一数组中各个元素必须是同一数据类型，每个数组元素都占有相同数量的存储单元，才能用下标来唯一的确定数组中的元素。,第二章 数组与线性表,2.1.2 数组的顺序存储结构,在计算机中，表示数组是采用一组连续的存储单
3、元顺序地存储各数组元素。 可以用下标值随机的访问该数组的任意一个元素。 计算数组元素存储地址的公式称为寻址公式。 设数组为A，每个数组元素占s个存储单元，一旦定义了它的维数和各维的上、下界，就可以得到计算数组元素地址的寻址公式。,第二章 数组与线性表,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*
4、s 0in-1,第二章 数组与线性表,2. 二维数组寻址公式,在C语言中，采用矩阵元素以行为主存储，即同一行的元素连续存放，存储完一行再存储下一行。 设二维数组Amn，m、n分别表示数组的行和列，用Loc(i,j)表示数组元素Aij的地址，每个单元占用s个存储单元，则寻址公式为： Loc(i,j)=Loc(0,0)+(i*n+j)*s 0im-1, 0jn-1,第二章 数组与线性表,定义一A23数组，对应的矩阵如下： 数组元素A12，其下标i=1，j=2，故它前面已经有i=1行，每行有3个元素，另外本行有j=2个元素，所以在元素A12之前，本数组已有5个元素。,第二章 数组与线性表,3. 三维
5、数组寻址公式,三维数组Amnp可分解为p个m*n的二维数组。 按行为主存储的数组元素Aijk的寻址公式为： Locijk=Loc000+(i*n*p+j*p+k)*s 0im-1, 0jn-1，0pp-1 对于更多维的数组，数组元素在内存中的存储可以此类推。,返回,第二章 数组与线性表,2.2.1 线性表（Linear List）,线性表是由有限数目的相同类型元素组成的序列。 表中的数据元素，除了第一个和最后一个以外，都有一个且只有一个前驱元素，同时也都有一个且只有一个后继元素； 第一个元素只有一个后继元素而无前驱元素；最后一个元素只有一个前驱元素而无后继元素。 线性表的元素个数n称为这个表的
6、长度，当n=0时，这个表叫做空表。,第二章 数组与线性表,线性表在计算机内存中采用各元素顺序存储的方式，这种存储结构叫做向量。 每个线性表元素叫做这个向量的一个分量。 如果已知线性表第一个元素的地址和每个元素占用的存储单元数，由任一元素的序号就可以计算出该元素在内存中的地址。 在编程时以一维数组表示线性表最简单，用的也最普遍。,第二章 数组与线性表,2.2.2 线性表的运算,对于给定的线性表，可进行如下的基本运算： 1. 求线性表的长度n； 2. 在第i个数据元素前面插入一个新的数据元素； 3. 删除第i个数据元素； 4. 存取或更新线性表第i个元素； 5. 将两个或两个以上的线性表合并成一个
7、线性表； 6. 将一个线性表拆成多个线性表； 7. 将线性表中各数据元素按某个域值（如关键字）递增或递减的顺序重新排列； 8. 在线性表中查找满足某种条件的数据元素；,第二章 数组与线性表,1. 数据元素的插入(insert),设用一个一维数组An表示此线性表，原来有m个元素（mn），元素值已给定。 规定数组的下标从1开始，即这里数据元素对应的数组下标从1到n。 要求在第i个元素前插入一个新数据元素，值为G，因原线性表的数据元素是连续排列的，中间没有空单元，所以第i个元素及其后面的各元素均需向后移动一个单元位置，这样才能将G插入到i位置，且元素总数由m增加为（m+1）。,第二章 数组与线性表,
8、插入函数,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*/ ,第二章 数组与线性表,插入函数分析,在循环语句中，当i=1时，须循环m次，表示元素插入线性表头的前面，则原线性表中m个元素均须向后移动一个单元，这是最不利的情况。 当i=m+1时，则循环一次也不进行，这时元素直接插入到线性表尾的后面，所以线性表的所有m个元素均不移动，这是最好的情况。,第二章 数组与线性表,2.
9、 数据元素的删除(Delete),设用一个一维数组An表示此线性表，原来有n个元素，元素值已给定。 要求删除第i个数据元素，由于线性表元素在数组中必须连续排列，中间不能有空单元，故将此元素删除后，它后面的所有元素都需要向前移动一个单元，且数据元素总数由原来的n减少到n-1.,第二章 数组与线性表,删除函数,void delete(A,int n,i) int j; if (in) printf(“i值错！n”); else for (j=i;j=n;j+) Aj=Aj+1; n-; ,第二章 数组与线性表,删除函数分析,在循环语句中，当i=1时，需循环(n-1)次，这是要删除线性表表头元素，是
10、最不利的情况； 当i=n时，则循环一次也不执行，只是将元素数目n比原来减少一个，而第n个数据元素不必再考虑，其余的各单元的元素均维持不变，这是最好的情况。,第二章 数组与线性表,3. 算法的时间复杂性,可以用数据元素的移动次数来度量这两个算法的时间复杂性。 插入时，最少循环0次，最多循环n次，如i的各种取值概率相同，则平均循环次数为n/2； 删除时最少的循环次数为0次，最多为n-1次，当i取值概率相同时，平均循环次数为(n-1)/2。 用数量级的形式表示线性表插入、删除运算的时间复杂性均为O(n)。,返回,第二章 数组与线性表,2.3.1 堆栈(Stack),堆栈也简称为栈，是限定在表的一端进
11、行插入或删除操作的线性表。 进行插入或删除操作的一段称为栈顶（top），另一端称为栈底（bottom）。 插入元素又称为入栈（push），删除元素操作称为出栈（pop）。 不含元素的栈称为空栈。 堆栈元素的插入和删除只在栈顶进行，总是后进去的元素先出来，所以堆栈又称为后进先出线性表或LIFO（Last-In-First-Out）表。,第二章 数组与线性表,堆栈的表示,堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的 。 设数组名为STACK，其下标的下界为1，上界为n。 一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。,第二章 数组与线性表,本例中t
12、op=4,第二章 数组与线性表,1. 入栈（push）,入栈的主要操作是先将栈顶指针加1； 然后将入栈元素放到栈顶指针所指示下标值的位置上。 设用下标从1到n的数组ST表示堆栈，入栈的元素值为G，则可得到入栈函数如下：,第二章 数组与线性表,入栈函数,void push (ST, int n, top, G) if (top=n) printf(“栈溢出!n”); /*显示栈满信息*/ else top=top+1; STtop=G; ,第二章 数组与线性表,2. 出栈（Pop）,出栈运算时，先将栈顶的元素值赋给某个变量，以备后面的运算应用； 然后栈顶指针减1，将栈顶位置下移。 假设已指定的变
13、量为x，则出栈的函数如下：,第二章 数组与线性表,出栈函数,void pop (ST, int top, x) if (top=0) printf(“空栈!n”); /*栈为空显示相应的信息*/ else x=STtop; top=top-1; /*栈顶位置下移*/ ,第二章 数组与线性表,2.3.2 堆栈的应用,1. 堆栈在函数调用中的应用: 设有三个函数A1，A2，A3，这三个函数有如下的调用关系：函数A1在其函数体的某处r调用函数A2，函数A2又在其函数体某处t调用函数A3，函数A3不调用其他函数。,第二章 数组与线性表,函数嵌套调用A1调用A2，A2调用A3时的返回地址在堆栈中的情况如
14、右图所示。,第二章 数组与线性表,2. 堆栈在表达式计算中的应用,一个算术表达式，例如A+B，其中加号“+”称作运算符，而A，B称为运算数。 对于由两个运算数和一个运算符组成的表达式，习惯上是将运算符写在两个运算数中间，这叫做中缀形式。 计算机处理表达式时，常把运算符放在两个运算数的后面或前面。 1. 把运算符放在两个运算数的后面，例如 AB+ ，称为后缀形式，也叫做波兰式 。 2. 把运算符放在两个运算数的前面，例如 +AB，则称做前缀形式，也叫做逆波兰表达式。,第二章 数组与线性表,算术表达式的不同运算符有不同的运算优先顺序，如，在没有括号时，乘除运算（*或/）要比加减运算（+或-）优先进
15、行。 下面用一个简单的例子说明编译系统在处理算术表达式时，是如何应用堆栈这种数据结构的。 假定表达式的运算数都是使用单个字母表示的，式中无括号且只有加、减、乘、除4种运算，而没有更复杂的运算，例如表达式 X+Y*Z。,第二章 数组与线性表,使用S1和S2两个堆栈，S1用于存储运算数，S2用于存储运算符。 编译系统处理时，将表达式从左向右逐个扫视一遍，并根据不同情况按以下原则处理: 1) 若是运算数，则将其压入S1栈； 2) 若是运算符且S2栈是空栈则将其压入 S2栈； 3) 若是运算符且S2栈为非空栈，且此运算符的级别高于S2栈顶运算符的级别，则将此运算符压入S2栈； 4) 凡不属于上面三条的
16、情况，则将S2的栈顶运算符与S1栈最上面的两个运算数出栈进行运算，并将运算结果压入S1栈。,第二章 数组与线性表,图中每一步上面括号中的数字表示该步是按哪一条原则处理的。,返回,第二章 数组与线性表,2.4.1 队列（Queue）,队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。 允许添加元素的一端称为队尾（Rear）；允许删除元素的一端称为队头（Front）。 向队列添加元素称为入队，从队列中删除元素称为出队。 新入队的元素只能添加在队尾，出队的元素只能是删除队头的元素，队列的特点是先进入队列的元素先出队，所以队列也称作先进先出表或FIFO（First-In-First-Out）表。,第二章 数组与线性表,队列的表示,与堆栈类似，队列也可以简单的用一维数组表示。 设数组名为Queue，其下标下界为1，上界
