第3次-第2章-线性表及其顺序存储

1、第2章 线性表及其顺序存储卢芳芳free-计算机科学与技术学院线性表顺序表栈队列 线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。 2.1线性表 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。 线性表是一种典型的线性结构。2.2.1顺序表 线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存

2、中一组地址连续的存储单元中。 2.2顺序表顺序表的存储结构如下图所示： 结点序号 1 2 i n len len len lenk1k2k ik n内存状况 存储地址 location(k1) location(k1)+(i-1)l en 顺序表的存储结构的C语言描述如下：/*顺序表的头文件，文件名sequlist.h */ #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int size; sequence_list;表长顺序表的几个基本操作的具体实现 ：/ 函数功能:顺序表的初始化置空表

3、 / 函数参数:指向sequence_list型变量的指针变量slt / 函数返回值:空 / 文件名:sequlist.c, 函数名:init() / void init(sequence_list slt) slt-size=0; 算法2.1顺序表的初始化-置空表/ 函数功能:在顺序表后部进行插入操作 / 函数参数:指向sequence_list型变量的指针变量slt / datatype类型的变量x / 函数返回值:空 / 文件名:sequlist.c, 函数名:append() / void append(sequence_list slt,datatype x) if(slt-size

4、=MAXSIZE) printf(顺序表是满的!);exit(1); slt-aslt-size=x; slt-size=slt-size+1; 算法2.2 在顺序表后部进行插入操作打印顺序表的各结点值 / 函数功能:打印顺序表的各结点值 / 函数参数:sequence_list型变量slt / 函数返回值:空 / 文件名:sequlist.c, 函数名:display() / void display(sequence_list slt) int i; if(!slt.size) printf(n顺序表是空的!); else for(i=0;islt.size;i+) printf(%5d,

5、slt.ai); 算法2.3 打印顺序表的各结点值判断顺序表是否为空 / 函数功能:判断顺序表是否为空 / 函数参数:sequence_list型变量slt / 函数返回值:int类型。1表示空,0表示非空 / 文件名:sequlist.c,函数名:empty() / int empty(sequence_list slt) return(slt.size=0 ? 1:0); 算法2.4 判断顺序表是否为空查找顺序表中值为x的结点位置 / 函数功能:查找顺序表中值为x的结点位置 / 函数参数:sequence_list型变量slt,datatype型变量x / 函数返回值:int类型。返回x的

6、位置值,-1表示没找到 / 文件名:sequlist.c,函数名:find() / int find(sequence_list slt,datatype x) int i=0; while( islt.size&slt.ai!=x ) i+; return(islt.size? i:1); 算法2.5 查找顺序表中值为x的结点位置 取得顺序表中第i个结点的值 / 函数功能:取得顺序表中第i个结点的值 / 函数参数:sequence_list型变量slt,int型变量i / 函数返回值:datatype类型。返回第i个结点的值 / 文件名:sequlist.c,函数名:get() / data

7、type get(sequence_list slt,int i) if(i=slt.size) printf(n指定位置的结点不存在!);exit(1); else return slt.ai; 算法2.6 取得顺序表中第i个结点的值 顺序表的插入运算是将一个值为x的结点插入到顺序表的第i个位置0in，即将x插入到ki-1和ki之间，如果i=n，则表示插入到表的最后，一般地可表示为：插入前：k0, k1, , ki-1, ki, , kn-1插入后：k0, k1, , ki-1,x, ki, , kn-1 插入过程的图示见下图： k ik0k1k i-1k n-1k0k1k i-1k n-1

8、xk i后移开始位置后移结束位置插入前插入后/ 函数功能:在顺序表的position位置插入值为x的结点 / 函数参数:指向sequence_list型变量的指针变量slt / datatype型变量x,int型变量 position / 函数返回值:空 文件名:sequlist.c,函数名:insert() / void insert(sequence_list slt,datatype x,int position) int i; if(slt-size=MAXSIZE) printf(n顺序表是满的!没法插入!);exit(1); if(positionslt-size) printf(

9、n指定的插入位置不存在!);exit(1); for(i=slt-size;iposition;i-) slt-ai=slt-ai1; slt-aposition=x; slt-size+; 算法2.7 在顺序表的position位置插入值为x的结点 算法2.7中，所花费的时间主要是元素后移操作，对于在第i个位置上插入一个新的元素，需要移动（n-i）个元素，设在第i个位置上插入一个元素的概率为pi，且在任意一个位置上插入元素的概率相等，即p0=p1=p2=pn=1/(n+1)，则在一个长度为n的顺序表中插入一个元素所需的平均移动次数为： 即在长度为n的顺序表中插入一个元素平均需要移动表中的一半

10、元素。该算法的时间复杂度为O（n）。 顺序表的删除操作是指删除顺序表中的第i个结点，0in-1，一般地可表示为： 删除前：k0, k1, , ki-1, ki, ki+1, , kn-1 删除后：k0, k1, , ki-1, ki+1, , kn-1 删除过程的图示见下图 ：k ik0k1k i-1k n-1k0k1k i-1k n-1k i+1前移结束位置前移开始位置删除前删除后k i+1删除操作的具体实现见算法2.8 / 函数功能:删除顺序表中第position位置的结点 / 函数参数:指向sequence_list型变量的指针变量slt / int型变量 position / 函数返回

11、值:空 文件名:sequlist.c,函数名:dele() / void dele(sequence_list slt,int position) int i; if(slt-size=0) printf(n顺序表是空的!);exit(1); if(position=slt-size) printf(n指定的删除位置不存在!);exit(1); for(i=position;isize-1;i+) slt-ai=slt-ai+1; slt-size-; 算法2.8 删除顺序表中第position位置的结点 要删除顺序表中的第i个结点，则需要移动（n-i-1）个元素，设删除表中第i个结点的概率为

12、qi，且在表中每一个位置删除的概率相等，即：q0=q1=qn-1=1/n 则在一个长度为n的顺序表中删除一个结点的平均移动次数为： 这表明，在一个长为n的顺序表中删除一个元素平均需要移动表中大约一半的元素。该算法的时间复杂度为O（n）。 栈2.3 栈 2.3.1栈 栈是一种特殊的线性表，对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行，进行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。 如果栈中有n个结点k0, k1, k2, , kn-1，k0为栈底，kn-1是栈顶，则栈中结点的进栈顺序为k0, k1, k2, , kn-1，而出栈的顺

13、序为kn-1, kn-2, , k1, k0。如图所示。 栈具有后进先出或先进后出（FILO,First In Last Out）的性质 k0k1k n-1栈顶栈底 出栈 进栈2.3.2顺序栈及其实现 栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。 一般地，可以设定一个足够大的一维数组存储栈，数组中下标为0的元素就是栈底，对于栈顶，可以设一个指针top指示它。 为了方便，设定top所指的位置是下一个将要插入的结点的存储位置，这样，当top=0时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关

14、系如下图所示。 k0k1k0k2k1k 数组下标 数组下标 数组下标MAXSIZE-1 MAXSIZE-1 MAXSIZE-12 top 2 21 1 1 top 0 0 0top (a)空栈 (b)有两个结点的栈 (c)栈已满栈的顺序存储结构的C语言描述如下：/ 栈（顺序存储）的头文件 / 文件名seqstack.h / #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int top; sequence_stack;下面是顺序存储栈的几个基本操作的具体实现 / 函数功能:栈（顺序存储）初始

15、化 / 函数参数:指向sequence_stack型变量的指针变量st / 函数返回值:空 / 文件名:seqstack.c,函数名:init() / void init(sequence_stack st) st-top=0; 算法2.9栈（顺序存储）初始化 说明:top=0表示栈空，这种情况下栈顶指示位内容始终为空。/ 函数功能:判断栈（顺序存储）是否为空 / 函数参数:sequence_stack型变量st / 函数返回值:int类型。1表示空,0表示非空 / 文件名:seqstack.c,函数名:empty() / int empty(sequence_stack st) return

16、(st.top? 0:1); 算法2.10判断栈（顺序存储）是否为空 / 函数功能:读栈顶（顺序存储）结点值 / 函数参数:sequence_stack型变量st / 函数返回值:datatype类型。返回栈顶结点值 / 文件名:seqstack.c,函数名:read() / datatype read(sequence_stack st) if (empty(st) printf(n栈是空的!);exit(1); else return st.ast.top-1; 算法2.11 取得栈顶（顺序存储）结点值顺序栈的进栈与出栈操作下图表明进出栈情况。543210top（a）空栈543210top

17、A（b）A进栈543210-1topA（c）B、C、D进栈BCDtoptoptop543210A（d）D,C出栈BCDtop543210（e）E进栈ABCDtopEtop543210ABEDtop（f）E、B、A出栈toptop/ 函数功能:栈（顺序存储）的插入（进栈）操作 / 函数参数:指向sequence_stack型变量的指针变量st / datatype型变量x / 函数返回值:空 / 文件名:seqstack.c,函数名:push() / void push(sequence_stack st,datatype x) if(st-top=MAXSIZE) printf(nThe se

18、quence stack is full!);exit(1); st-ast-top=x; st-top+; 算法2.12 栈（顺序存储）的插入操作 / 函数功能:栈（顺序存储）的删除（出栈）操作 / 函数参数:指向sequence_stack型变量的指针变量st / 函数返回值:空 / 文件名:seqstack.c,函数名pop() / void pop(sequence_stack st) if(st-top=0) printf(nThe sequence stack is empty!);exit(1); st-top-; 算法2.13栈（顺序存储）的删除操作 思考:如果将栈空表示为to

19、p=-1,则所有栈的所有操作为何变化呢?2.3.3栈的应用之一-括号匹配 设一个表达式中可以包含三种括号：小括号、中括号和大括号，各种括号之间允许任意嵌套，如小括号内可以嵌套中括号、大括号，但是不能交叉。举例如下：()正确的() 正确的()正确的()不正确的() 不正确的 如何去检验一个表达式的括号是否匹配呢？大家知道当自左向右扫描一个表达式时，凡是遇到的开括号（或称左括号）都期待有一个和它对应的闭括号（或称右括号）与之匹配。 按照括号正确匹配的规则，在自左向右扫描一个表达式时，后遇到的开括号比先遇到的开括号更加期待有一个闭括号与之匹配。（后进先出） / 函数功能:判断表达式括号是否匹配 /

20、函数参数:char类型数组c / 函数返回值:int类型。返回1为匹配,返回0为不匹配 / 文件名:seqmatch.c,函数名:match_kouhao() /int match_kuohao(char c) int i=0; sequence_stack s; init(&s); while(ci!=#) switch(ci) case : case : case (:push(&s,ci);break; case :if(!empty(s)&read(s)= ) pop(&s);break; else return 0; case :if(!empty(s)&read(s)= ) pop

21、(&s);break; else return 0; case ):if(!empty(s)&read(s)=( ) pop(&s);break; else return 0; i+; return (empty(s); /栈为空则匹配,否则不匹配/ 算法2.14 判断表达式括号是否匹配 算术表达式通常是由操作数、算术运算符和一对圆括号“（”和“）”组合而成。其中操作数允许是程序语言中任意合法的变量名或常数。 以下我们讨论+、-、*、/四种算术运算。表达式求值中的首要问题：如何确定表达式中所含运算的计算次序。算术运算的规则：1）先括号内、后括号外2）先乘除、后加减3）从左算到右2.3.4栈的应

22、用之二-算术表达式求值 方法1：加括号，即对每个一运算都用一对括号将与其配对的左、右操作对象括在一起，由此上面算术表达式将写成（A+（B*（C+D）利用栈求表达式的值：1）自左至右的扫描加括号的算术表达式2）将非右括号“）”的符号进栈3）每当遇见右括号“）”，从栈顶向下扫描至第一个左括号“（”，这就是和遇见的右括号“）”配对的左括号“（”，该左括号“（”上面的表达式就是现在应该计算的表达式，从栈中弹出对应的左括号“（”以上的所有符号（含左括号”（“），计算相应表达式，并将结果压入栈中。重复1）2）3）即可计算出表达式的值。特点：方法简单明了，但要求人们事先为要计算的表达式加好括号，这既繁琐，又

23、易出错。方法2：重新改写表达式为后缀表达式。在计算机中，表达式可以有三种不同的标识方法设 Exp = S1 + OP + S2则称 OP + S1 + S2 为表达式的前缀表示法 称 S1 + OP + S2 为表达式的中缀表示法 称 S1 + S2 + OP 为表达式的后缀表示法 可见，它以运算符所在不同位置命名的。例： 中缀表达式 后缀表达式 （1） A A （2） A+B AB+ （3） A+B*C ABC*+ （4） A*（B-C）+D ABC-*D+ （5） D+A/（B-C） DABC-/+算法：将中缀表达式转换为后缀表达式根据中缀表达式与后缀表达式的特点，可得将中缀表达式变换为后

24、缀表达式的方法：1）操作数的排列次序不变2）把每一运算符从第二操作数之前排到第二操作数之后3）删去所有括号关键问题：如何找到一个运算符的第二个操作数的结束位置？算法：利用后缀表达式求值基本思想：1）从左到右扫描后缀表达式，遇到操作对象进栈。2）遇到运算符，弹出栈顶的元素，其中栈顶为第二操作对象，次栈顶为第一操作对象，对其按遇到的运算符进行运算，并将结果进栈。重复上述动作最后即可求出表达式的值。例如有中缀表达式：A/B-（C+D）*E其对应的后缀表达式为：AB/CD+E*-利用后缀表达式求值过程如下所示：步骤 操作数栈 后缀表达式 说明1 AB/CD+E*-# 初始栈空，A进栈2 A AB/CD

25、+E*-#B进栈3 AB AB/CD+E*-#遇/，弹出栈顶两元素做A/B= ，并将其进栈4 AB/CD+E*-# C进栈5 C AB/CD+E*-# D进栈9 AB/CD+E*-# 8 E AB/CD+E*-# 7 AB/CD+E*-# 6 CD AB/CD+E*-# 步骤 操作数栈 后缀表达式 说明遇+，弹出CD做 C+D= ，并将其进栈E进栈遇*，弹出栈顶两元做 *E= ，并将结果进栈遇-，弹出栈顶二元做 - = ，并将结果进栈10 AB/CD+E*-# 遇#，结束，栈顶就是表达式的计算结果习题:数制转换问题 十进制n和其它进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个

26、简单算法基于下列原理: n=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2倒取余数(1348)10=(2504)8例用栈的知识实现任意正的10进制整数到其它进位制的转换程序。算法设计题:2、回文是指正读和反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文，试写一个算法判定给定的字符向量是否为回文。 void conversion( ) init(s); scanf

27、 (“%d”,&n); while(n) /余数进栈 push(&s,n%8); n=n/8; while(! Stackempty(s) e=pop(&s); /余数出栈 printf(“%d”,e); 习题一解答:队列2.4 队列 2.4.1 队列 队列是一种特殊的线性表，它的特殊性在于队列的插入和删除操作分别在表的两端进行。插入的那一端称为队尾，删除的那一端称为队首。队列的插入操作和删除操作也分别简称进队和出队。 对于一个队列：k0, k1, k2, , kn-1则k0是这些结点中最先插入的结点，若要做删除操作，k0将首先被删除，所以说，队列是具有“先进先出”（FIFO,First In

28、 First Out）特点的线性结构。 队列类型的描述如下：ADT sequence_queue 数据集合K:K=k1,k2,kn,n0,K中的元素是datatype类型; 数据关系R:R=r r= | i=1,2,n1。 操作集合: （1）void init (sequence_queue sq) 队列（顺序存储）初始化; （2）int empty (sequence_queue sq) 判断队列（顺序存储）是否为空; （3）void display (sequence_queue sq) 打印队列（顺序存储）的结点值; （4）datatype get(sequence_queue sq)

29、取得队列（顺序存储）的队首结点值; （5）void insert(sequence_queue sq,datatype x) 队列（顺序存储）的插入操作; （6）void dele(sequence_queue sq) 队列（顺序存储）的删除操作。 ADT sequence_queue;2.4.2顺序队列及其实现 队列的顺序存储在C语言中可以用一维数组表示，为了标识队首和队尾，需要附设两个指针front和rear，front指示的是队列中最前面，即队首结点在数组中元素的下标，rear指示的是队尾结点在数组中元素的下标的下一个位置，也就是说rear指示的是即将插入的结点在数组中的下标。 队列的几

30、种状态 ：队首、队尾指针 front rear 数组下标 0 1 MAXSIZE-1 (a)初始状态-空队列AB队首、队尾指针 front rear 数组下标 0 1 MAXSIZE-1 (b)连续插入几个结点后的状态DC队首、队尾指针 front rear 数组下标 0 1 2 3 MAXSIZE-1 (c)连续删除几个结点后的状态-此时队列中只有一个结点D队首、队尾指针 front rear 数组下标 0 1 MAXSIZE-1 (d) 在(c)状态下再删除一个结点后的状态-空队列X队首、队尾指针 front rear 数组下标 0 1 2 3 MAXSIZE-1 (e)连续插入若干结点后

31、的状态-此时队列呈现满的状态，但数组前部有空位子DE队列的顺序存储结构的C语言描述如下：/ 队列（顺序存储）的头文件 / 文件名seqqueue.h / #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int front; /队首 int rear; /队尾 sequence_queue;顺序存储队列的几个基本操作的具体实现 :/ 函数功能:队列（顺序存储）初始化 / 函数参数:指向sequence_queue类型变量的指针变量sq / 函数返回值:空 / 文件名:seqqueue.c,函数

32、名:init() / void init(sequence_queue sq) sq-front=sq-rear=0; 算法2.20 队列（顺序存储）初始化 / 函数功能:判断队列（顺序存储）是否为空 / 函数参数:sequence_queue类型变量sq / 函数返回值:int类型。返回1表示空,0表示非空 / 文件名:seqqueue.c,函数名:empty() / int empty(sequence_queue sq) return (sq.front=sq.rear? 1:0); 算法2.21判断队列（顺序存储）是否为空 / 函数功能:打印队列（顺序存储）的结点值 / 函数参数:se

33、quence_queue类型变量sq / 函数返回值:空 / 文件名:seqqueue.c,函数名:display() /void display(sequence_queue sq) int i; if(empty(sq) printf(n顺序队列是空的!); else for(i=sq.front;irear=MAXSIZE) printf(n顺序队列是满的!);exit(1); sq-asq-rear=x; sq-rear=sq-rear+1; 算法2.24 队列（顺序存储）的插入操作/ 函数功能:队列（顺序存储）的删除（出队）操作 / 函数参数:指向sequence_queue类型变量

34、的指针变量sq / 函数返回值:空 / 文件名:seqqueue.c,函数名:dele() / void dele(sequence_queue sq) if(sq-front=sq-rear) printf(n顺序队列是空的！不能做删除操作！); exit(1); sq-front+; 算法2.25 队列（顺序存储）的删除操作 在队列的几种状态图的（e）状态中，队列是一种队满状态，将不能再插入新的结点，而实际上数组的前部还有许多空的位置。为了充分地利用空间，可以将队列看作一个循环队列，在数组的前部继续作插入运算，这就是循环队列。 X队首、队尾指针 front rear 数组下标 0 1 2

35、3 MAXSIZE-1 (e)连续插入若干结点后的状态-此时队列呈现满的状态，但数组前部有空位子DE2.4.3顺序循环队列及其实现 给定一个大小为MAXSIZE的数组存储一个队列时，经过若干次插入和删除操作后，当队尾指示rear=MAXSIZE时，呈现队列满的状态，而事实上数组的前部可能还有空闲的位置。为了有效利用空间，将顺序存储的队列想象为一个环状，把数组中的最前和最后两个元素看作是相邻的，这就是循环队列。 front450123 (e) E、F进队EFrearfront450123rear (f) G H I J进队EFgHIJ队满2015.3.20 在循环队列中进行出队、入队操作时，头尾

36、指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（MaxSize-1）时，其加1操作的结果是指向向量的下界0。 这种循环意义下的加1操作可以描述为： if(rear+1=MaxSize) rear=0; else rear+; 利用模运算可简化为： rear=(rear+1)%MaxSizerear front450123(a)队列初始情况450123rear front (b)A进队A front450123rear (c) B、C、D进队ABCD450123rear (d) ABCD出队front队空 front450123rear (f) G H I J进队EFgHIJfront45

37、0123 (e) E、F进队EFrear队满如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。本书采用牺牲一个数组元素的空间，即若数组的大小是MAXSIZE，则该数组所表示的循环队列最多允许存储MAXSIZE-1个结点。这样，循环队列满的条件是(rear+1)%MAXSIZE=front循环队列空的条件是 rear=front 解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若

38、相等则认为队满（注意：rear所指的单元始终为空）；其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。循环队列的插入与删除操作的实现 ：/ 函数功能:循环队列（顺序存储）的插入操作/ 函数参数:指向sequence_queue类型变量的指针变量sq/ datatype类型的变量x / 文件名:secqinse.c,函数名:insert_sequence_cqueue()/void insert_sequence_cqueue(sequence_queue sq,datatype x) if(sq-rear+1)%MAXSIZE=sq-front) printf(n顺序循环队列是满的

39、！无法进行插入操作！);exit(1); sq-asq-rear=x; sq-rear=(sq-rear+1)%MAXSIZE; 算法2.26 循环队列（顺序存储）的插入操作 循环队列（顺序存储）的删除操作 / 函数功能:循环队列（顺序存储）的删除操作 / 函数参数:指向sequence_queue类型变量的指针变量sq / 函数返回值:空 / 文件名secqdele.c, 函数名dele_sequence_cqueue() / void dele_sequence_cqueue(sequence_queue sq) if(sq-front=sq-rear) printf(n循环队列是空的！无

40、法进行删除操作！); exit(1); sq-front=(sq-front+1)%MAXSIZE; 算法2.27 循环队列（顺序存储）的删除操作习题:1、以计数器的方法实现循环队列的基本运算。2、对于循环队列，写出求队列长度的公式。*2.1 选择题（1）表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（），删除一个元素所需移动元素的平均个数为（）。A（n1）/2BnCn+1Dn1En/2F(n+1)/2G(n2)/2（2）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，

41、若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S的容量至少应该为（）。A6B4C3D2（3）设栈的输入序列为1、2、3n，若输出序列的第一个元素为n，则第i个输出的元素为（）。A不确定Bni+1CiDni（4）在一个长度为n的顺序表中删除第i个元素（1=i=n）时，需向前移动（）个元素。AniBni+1Cni1Di（5）若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（）。AO(n)BO(1)CO(n2)DO(n3)（6）表达式a*(b+c)d的后缀表达式是（）。Aabcd*+Babc+*dCabc*+dD+*abcd（7）队列是一种特殊的线性

42、表，其特殊性在于（）。A插入和删除在表的不同位置执行B插入和删除在表的两端位置执行 C插入和删除分别在表的两端执行D插入和删除都在表的某一端执行（8）栈是一种特殊的线性表，具有（）性质。A先进先出B先进后出C后进后出D顺序进出（9）顺序循环队列中（数组的大小为n），队头指示front指向队列的第1个元素，队尾指示rear指向队列最后元素的后1个位置，则循环队列中存放了n1个元素，即循环队列满的条件为（）。A(rear+1)%n=front1B(rear+1)%n=frontC(rear)%n=frontDrear+1=front（10）顺序循环队列中（数组的大小为6），队头指示front和队尾

43、指示rear的值分别为3和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（）。A5和1B2和4C1和5D4和2*2.2 什么是顺序表？什么是栈？什么是队列？2.3 设计一个算法，求顺序表中值为x的结点的个数。2.4 设计一个算法，将一个顺序表倒置，即如果顺序表各个结点值存储在一维数组a中，倒置的结果是使得数组a中的a0等于原来的最后一个元素，a1等于原来的倒数第2个元素，a的最后一个元素等于原来的第一个元素。2.5 已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序。*2.6 将下列中缀表达式转换为等

44、价的后缀表达式。（1）5+675 6 7*+（2）（56）/75 6- 7/（3）56785 6 7 *8*-（4）5785 7*8-（5）5（76）+8/95 7 6-* 8 9/+（6）7（568）97 5 6 8*-* 9-*2.7 已知循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，写出求循环队列中当前结点个数的表达式。*2.8 编号为1，2，3，4的4列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果有n列火车通过调度站，设计一个算法，输出所有可能的调度结果。#include #define MAXSIZE 100 /*表的最大空间大小*/typedef int datatype;typedef struct datatype aMAXSIZE ; /*向量data用于*/ int size; /*当前的表长度*/ sequence_list;实验：自定义一个线性表 sequlist.h（1）void reverse(seqlist *L) 将顺序表L就地转置，即借助于O（1）的