习题一1.什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请举例说明2.数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？3.设n为正整数, 分析下列各程序段中加下划线的语句的执行次数1) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { c[i][j] = 0.0; for (int k = 1; k <= n; k++) c[i][j] = c[i][j] + a[i][k] * b[k][j];} (2) x = 0; y = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) for (int k = 1; k <= j; k++) x = x + y;(3) int i = 1, j = 1; while (i<=n && j<=n) { i = i + 1; j = j + i; } (4)* int i =1; do{ for (int j = 1; j <= n; j++) i = i + j; }while(i<100 + n);4.试编写一个函数计算n!*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0 £ n £ arraySize。
若设计算机中允许的整数的最大值为maxInt，则当n>arraySize或者对于某一个k (0 £ k £ n)，使得k!*2k > maxInt时，应按出错处理可有如下三种不同的出错处理方式： (1) 用printf显示错误信息及exit(1)语句来终止执行并报告错误； (2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回； (3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回 试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它5.设有一个线性表 (a0, a1, …, an-2, an-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (an-1, an-2, …, a1, a0)最后分析此算法的时间复杂度及空间复杂度6.顺序表的插入和删除要求仍然保持各个元素原来的次序设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?7.利用顺序表的操作，实现以下的函数并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。
(1) 从顺序表中删除具有给定值x的所有元素 (2) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素 (3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素 (4) 将两个有序顺序表la,lb合并成一个新的有序顺序表lc (5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同8.线性表可用顺序表或链表存储试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？9.试写出计算线性链表长度的算法10.设有一个表头指针为h的单链表试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示要求逆转结果链表的表头指针h指向原链表的最后一个结点11.设有一线性链表，其结点值均为整数试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。
12．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递减有序的单链表要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间表中允许有重复的数据13．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间表中允许有重复的数据14.在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前15.对于下面的每一步，画出栈元素和栈顶指针的示意图：（1）栈初始化；（2）元素x入栈；（3）元素y入栈；（4）出栈（5）栈初始化（6）元素z入栈16.铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示试问： (1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。
17.试证明：若借助栈可由输入序列1, 2, 3, …, n得到一个输出序列p1, p2, p3, …, pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i < j < k，使得pj < pk < pi提示：用反证法)18.将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空两个栈均从两端向中间增长当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置当top[0]+1 == top[1]时或top[0] == top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法19.改写顺序栈的进栈成员函数Push(x)，要求当栈满时执行一个stackFull( )操作进行栈满处理其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。
20.根据教案中给出的优先级，回答以下问题： (1) 在表达式求值的过程中，如果表达式e含有n个运算符和分界符，问操作数栈(NS)中最多可存入多少个元素？ (2) 如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？21.表达式的中缀表示为a * x - b / x^2，试利用栈将它改为后缀表示ax * bx2^/ -写出转换过程中栈的变化^表示乘方运算)22.设循环队列的容量为70（序号从1到70），经过一系列入队和退队运算后，有：（1）front=15，rear=46；（2）front=45，rear=10问在上述两种情况下，循环队列中各有多少个元素？23.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除试编写基于此结构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件 习题21．列出右图所示二叉树的叶结点、分支结点和每个结点的层次2．使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出上图所示二叉树的存储表示3．在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？4．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
5．如果一棵树有n1个度为1的结点, 有n2个度为2的结点, … , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之6．若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1) 统计二叉树中叶结点的个数2) 以二叉树为参数，交换每个结点的左子女和右子女3) 求二叉树的深度7．一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为i的结点的父结点(若存在)的编号是多少? (3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少? (4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h是n 的什么函数关系?8．请画出下图所示的树所对应的二叉树123456789．已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树10．给定权值集合{15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权路径长度。
习题三1. 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908试画出对其进行折半查找时的二叉查找树, 并计算查找成功的平均查找长度和查找不成功的平均查找长度2. 若对有n个元素的有序顺序表和无序顺序表进行顺序查找, 试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同?(1) 查找失败;(2) 查找成功, 且表中只有一个关键码等于给定值k的对象;(3) 查找成功, 且表中有若干个关键码等于给定值k的对象, 要求一次查找找出所有对象3. 设有10000个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高查找效率, 每一个子表的大小应设计为多大? 4. 设散列表为HT[13], 散列函数为 H (key) = key %13用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表 (1) 采用线性探测法寻找下一个空位, 画出相应的散列表, 并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。
(2) 采用随机探测法寻找下一个空位, 随机数序列为：5，4，2，7，3，6，…画出相应的散列表, 并计算等概率下查找成功的平均查找长度5. 设有150个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所需记录的平均比较次数不超过2次试问散列表需要设计多大？ 设a是散列表的装载因子，则有 6. 设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录若采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？ 已知，链地址法的平均查找长度ASL=1+α/27. 设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果并说明做了多少次排序码比较 (1) 直接插入排序 (2) 希尔排序(增量为5,2,1) (3) 冒泡排序 (4) 快速排序 (5) 直接选择排序 (6) 堆排序 (7) 二路归并排序 8. 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。
在快速排序过程中有这种现象吗？9. 试设计一个算法, 使得在O(n)的时间内重排数组, 将所有取负值的排序码排在所有取正值(非负值)的排序码之前提示：对比快速排序的第一趟排序，此处，以0为控制关键字10. 手工跟踪对以下各序列进行堆排序的过程给出形成初始堆及每选出一个排序码后堆的变化 (1) 按字母顺序排序：Tim, Dot, Eva, Rom, Kim, Guy, Ann, Jim, Kay, Ron, Jan (2) 按数值递增顺序排序：26, 33, 35, 29, 19, 12, 22 (3) 同样7个数字，换一个初始排列，再按数值的递增顺序排序：12, 19, 33, 26, 29, 35, 2211. 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明12. 在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数基于这个思想，可得计数排序方法该方法在声明对象时为每个对象增加一个计数域count，用于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序试编写一个算法，实现计数排序并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要做n(n-1)/2次排序码比较。
习题解答3.设n为正整数, 分析下列各程序段中加下划线的语句的执行次数1) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { c[i][j] = 0.0; for (int k = 1; k <= n; k++) c[i][j] = c[i][j] + a[i][k] * b[k][j];} (2) x = 0; y = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) for (int k = 1; k <= j; k++) x = x + y;(3) int i = 1, j = 1; while (i<=n && j<=n) { i = i + 1; j = j + i; } (4)* int i =1; do{ for (int j = 1; j <= n; j++) i = i + j; }while(i<100 + n);【解答】 (1) (2) (3)i = 1时，i = 2，j = j + i = 1 + 2 = 2 + 1，i = 2时，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，i = 3时，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3，i = 4时，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4，……i = k时，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + … + k )，解出满足上述不等式的k值，即为语句i = i + 1的程序步数。
(4) for语句每执行一次，语句i=i+j将执行n次，而i的值会增加因此，当for语句执行k次后，i的值将变为故最终for语句的执行次数k为满足的最小整数k，语句i = i + j的程序步数为n*k4.试编写一个函数计算n!*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0 £ n £ arraySize若设计算机中允许的整数的最大值为maxInt，则当n>arraySize或者对于某一个k (0 £ k £ n)，使得k!*2k > maxInt时，应按出错处理可有如下三种不同的出错处理方式： (1) 用printf显示错误信息及exit(1)语句来终止执行并报告错误； (2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回； (3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回 试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它解答】#include const int arraySize = 100;const int MaxInt = 0x7fffffff;int calc( int T[ ], int n ) { int i, value = 1; if ( n != 0 ) { int edge = MaxInt / n / 2; for ( i = 1; i < n; i++ ) { value *= i*2; if ( value > edge ) return 0; } value *= n * 2; } T[n] = value; printf("A[ %d ]= %d\n”,n,T[n]); return 1;}void main ( ) { int A[arraySize]; int i; for ( i = 0; i < arraySize; i++ ) if ( !calc ( A, i ) ) { printf("failed at %d .\n", i ); break; }}/*---------顺序表结构的定义.为简化起见，表元素我们使用整型数据----------------------数据元素从data[0]处开始存储---------------------------------*/typedef struct /*注意typedef的使用*/{ int data[MAXSIZE]; /*数据域*/ int length; /*表长*/}listtype;5.设有一个线性表 (a0, a1, …, an-2, an-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。
请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (an-1, an-2, …, a1, a0)最后分析此算法的时间复杂度及空间复杂度解答】 void inverse (listtype * A) { int tmp; int n= A->length; for( int i = 0; i <= ( n-1 ) / 2; i++ ){ tmp = A->data[i]; A->data[i] = A->data[n-i-1]; A->data[n-i-1] = tmp; } }时间复杂度：需进行n/2次循环，因此时间复杂度为O(n)；空间复杂度：使用一个整形辅助存储单元tmp，因此空间复杂度为O(1)6.顺序表的插入和删除要求仍然保持各个元素原来的次序设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?【解答】 若设顺序表中已有n个元素又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。
插入时平均移动元素个数AMN(Averagy Moving Number )为 删除时平均移动元素个数AMN为 7.利用顺序表的操作，实现以下的函数并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因 (1) 从顺序表中删除具有给定值x的所有元素 (2) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素 (3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素 (4) 将两个有序顺序表la,lb合并成一个新的有序顺序表lc (5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同解答】 (1) 从顺序表中删除具有给定值x的所有元素void DelValue(listtype * L, int x ){int i = 0, j; while ( i < L->length ) /*循环, 寻找具有值x的元素并删除它*/if (L->data[i] == x ) { /*删除具有值x的元素, 后续元素前移*/for (j = i;j < L->length-1; j++ ) L->data[j] = L->data[j+1];L-length--; /*表长减1*/} else i++;} (2) 实现删除其值在给定值s与t之间（要求s小于t）的所有元素的函数如下：void DelValue_s_to_t (listtype *L,int s, int t){ int i,j;if ( L->length == 0 || s >= t ) { printf(“List is empty or parameters are illegal!\n”); exit(1); } i = 0; while ( i < L->length) /*循环, 寻找具有值x的元素并删除它*/if (L->data[i]>=s &&L->data[i]<= t){/*删除满足条件的元素, 后续元素前移*/for ( j = i; j < L->length-1; j++ ) L->data[j] = L->data[j+1];L->length--; /*表长减1*/ } else i++;} (3) 实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下：void DelValue_s_to_t_1 (listtype *L,int s int t){ int i,j,k;if ( L->length == 0 || s >= t ){ printf(“List is empty or parameters are illegal!\n”); exit(1); }for (i = 0; i < L->length; i++ ) /*循环, 寻找值 ≥s 的第一个元素*/if ( L->data[i] >= s ) break; /*退出循环时, i指向该元素*/if ( i < L->length ) {for (j = 1; i + j < L->length; j++ )/*循环, 寻找值 > t 的第一个元素*/if (L->data[i+j] > t ) break; /*退出循环时, i+j指向该元素*/ for (k = i+j; k < L->length; k++ ) /*删除满足条件的元素, 后续元素前移*/L->data[k-j] = L->data[k]; L->length-= j; /*表长减j*/}} (4) 实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：listtype * Merge(listtype *LA,listtype *LB ){/*合并有序顺序表LA与LB成为一个新的有序顺序表并由函数返回 listtype *LC; int value1,value2; int i,j,k; initiatelist(LC);if (LA->length + LB->length > MAXSIZE) { printf(“表上溢/n”; exit(1); } i = 0, j = 0, k = 0; value1 = LA->data[i]; value2 = LB->data[j];while (i < LA->length && j < LB->length ) {/*循环, 两两比较, 小者存入结果表*/if (value1 <= value2){ LC->data[k] = value1; i++; value1=LA->data[i];} else { LC->data[k] = value2; j++; value2=LB->data[j];}k++;} while( i < LA->length){ /*当LA表未检测完, 继续向结果表传送*/LC->data[k] = value1; i++; k++; value1 = LA->data[i]; } while( j < LB->length){ /*当LB表未检测完, 继续向结果表传送*/LC->data[k] = value2; j++; k++; value2 = LB->data[j];} LC->length = k;return LC;} (5) 实现从表中删除所有其值重复的元素的函数如下：void DelDouble(listtype *L){int i,j,k;int tmp;if(L->length == 0 ){ printf(“表空\n”; exit(1); } i=0;while ( i < L->length ) { /*循环检测*/j = i + 1; tmp = L->data[i];while( j < L->length ) { /*对于每一个i, 重复检测一遍后续元素*/if( tmp == L->data[j]) { /*如果相等,删除此结点，后续元素前移*/ for( k = j+1; k < L->length; k++ ) L->data[k-1] = L->data[k];L->length--; /*表最后元素位置减1*/}else j++;} i++; /*检测完L->data[i], 检测下一个*/}}8.线性表可用顺序表或链表存储。
试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？【解答】(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取它的存储效率高，存取速度快但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。
如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间初始时因不知道哪个表增长得快，必须平均分配空间在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素这个处理过程极其繁琐和低效如果采用链接存储表示，一个表的存储空间可以连续，可以不连续表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便对于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷所以选用链接存储表示较好 (3) 应采用顺序存储表示因为顺序存储表示的存取速度快，但修改效率低若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好/*---------链表结构的定义.为简化起见，表元素我们使用整型数据----------------------此链表带头结点--------------------------------------------*/typedef struct mynode{ int data; /*数据域：整型*/ struct mynode *next; /*指针域*/} node, linklisttype;9.试写出计算线性链表长度的算法。
int lengthsl(linklisttype *L){ linklisttype * p; int len; if(L == NULL){return –1;} p = L->next; /* p指向链表L的头结点*/ len = 0; while(p != NULL){ len++; p = p->next;}return len;}10.设有一个表头指针为h的单链表试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示要求逆转结果链表的表头指针h指向原链表的最后一个结点解答】void LinkListInverse(linklisttype *L){ linklisttype *p, *pre, *next;if(L == NULL || L->next == NULL ) return; /*表未初始化，或为空表*/ p = L->next;pre = L; while( p != NULL ) { /*循环修改链表中所有结点的后继指针的指向*/ next = p->next; /*取当前结点的后继指针*/ p->next = pre; /*当前结点的后继改为指向其原来的前驱*/ pre = p , p=next; /*指针后移*/}L->next->next = NULL; /*原第一个结点改为最后一个结点*/L->next = pre; /*链表的头结点指向原最后一个结点*/}11.设有一线性链表，其结点值均为整数。
试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点解答】void LinkListDispose(linklisttype * L,linklisttype * LA,linklisttype * LB){/*将链表L分解为LA、LB两个链表，其中LA中结点值均为正，LB中结点值均为负，并删除结点值为零的结点,最后释放L的头结点/ linklisttype *p , *pt , *pa, * pb;LA = initiatesl();pa = LA; /*指向LA中的最后一个结点*/LB = initiatesl();pb = LB; /*指向LB中的最后一个结点*/If(L == NULL || L->next == NUUL) return; /*L为空指针或L为空表*/p = L->next; /*p指向链表L的第一个结点*/while(p != NULL) /*遍历链表L*/ if(p->data > 0){ /*将p链入链表LA的pa后*/ pa->next = p; pa = p; p = p->next;}elseif(p->data < 0){ /*将p链入链表LB的pb后*/ pb->next = p; pb = p; p = p->next;}else{ /*删除值为0的结点*/ pt = p->next; /*记录当前结点的后继，以便删除当前结点*/ free(p); p = pt;} pa->next = NULL; pb->next = NULL; free(L);}12．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递减有序的单链表。
要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间表中允许有重复的数据解答】void linklistMerge(linklisttype *LA,linklisttype *LB ){/*合并有序链表LA与LB,结果存入LA中，并释放LB的头结点 */ linklisttype *pa, *pb , *pre ,*pn; if(LA == NULL || LB == NULL ||) return; if(LA->next == NULL){ /*LA为空表，则直接将LB链入LA即可*/ LA->next = LB->next; free(LB); retrun;}if(LB->next == NULL) return; /*LB为空表，则直接返回即可*/pa = LA->next, pb = LB->next ,pre=LA;while (pa != NULL && pb != NULL) /*循环, 两两比较, 小者存入结果表*/if(pa->data > pb->next){ /*将pb链入LA，然后pb指针后移*/ pre->next = pb;pn = pb->next;pb->next = pa;pb = pn;pre = pre->next} else{ /*pa指针后移*/ pa = pa->next; pre = pre->next; } if(pb != NULL) /*将pb剩余结点链入LA*/ pre->next = pb; free(LB);}13．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。
要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间表中允许有重复的数据解答】Linklisttype * linklistMerge_inverse(linklisttype *LA,linklisttype *LB ){/*合并有序链表LA与LB,结果存入LC中，并释放LA、LB的头结点 ,函数返回LC*/ linklisttype *pa, *pb , *p; if(LA == NULL || LB == NULL ||) return;LC = initiatesl();pa = LA->next, pb = LB->next;while (pa != NULL && pb != NULL) /*循环, 两两比较, 大者存入LC*/if(pa->data > pb->next){ /*将pa链为LC的第一个结点*/p = pa->next;pa->next = LC->next;LC->next = pa;pa = p;} else{ /*将pa链为LC的第一个结点*/p = pb->next;pb->next = LC->next;LC->next = pb;pb = p; } while(pa != NULL){ /*将pa剩余结点链入LC*/p = pa->next;pa->next = LC->next;LC->next = pa;pa = p; } while(pb != NULL){ /*将pb剩余结点链入LC*/p = pb->next;pb->next = LC->next;LC->next = pb;pb = p; } free(LA); free(LB);}14.在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前。
解答】设此循环链表为单链表，则其类型定义与一般单链表相同typedef struct mynode cyclelisttype;void search_movefirst(cyclelisttype *CL, int x){ cyclelisttype * p , *pre; if(CL == NULL) return; p = CL->next; pre = CL; while(p != CL)/*查找x，注意与普通单链表在判断是否到表尾上的不同*/ if(p->data == x) break; else{ pre = p; p = p->next; }if(p != CL){ /*查找成功*/ per->next = p->next; /*在原来位置删除p*/ p->next = CL->next; /*p插入到CL后*/ CL->next = p;}16.铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示试问： (1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。
解答】 (1) 可能的不同出栈序列有 种 (2) 不能得到435612和154623这样的出栈序列因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈154623也是这种情况出栈序列325641和135426可以得到3562244 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 13542617.试证明：若借助栈可由输入序列1, 2, 3, …, n得到一个输出序列p1, p2, p3, …, pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i < j < k，使得pj < pk < pi提示：用反证法)【解答】 因为借助栈由输入序列1, 2, 3, …, n，可得到输出序列p1, p2, p3, …, pn ，如果存在下标i, j, k，满足i < j < k，那么在输出序列中，可能出现如下5种情况：① i进栈，i出栈，j进栈，j出栈，k进栈，k出栈。
此时具有最小值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最大值的排在pk位置，有pi < pj < pk, 不可能出现pj < pk < pi的情形；② i进栈，i出栈，j进栈，k进栈，k出栈，j出栈此时具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中间值的排在最后pk位置，有pi < pk < pj , 不可能出现pj < pk < pi的情形；③ i进栈，j进栈，j出栈，i出栈，k进栈，k出栈此时具有中间值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj < pi < pk, 不可能出现pj < pk < pi的情形；④ i进栈，j进栈，j出栈，k进栈，k出栈，i出栈此时具有中间值的排在最前面pi 位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk < pi < pj, 也不可能出现pj < pk < pi的情形；⑤ i进栈，j进栈，k进栈，k出栈，j出栈，i出栈此时具有最大值的排在最前面pi 位置，具有中间值的排在其后pj位置，具有最小值的排在pk位置，有pk < pj < pi, 也不可能出现pj < pk < pi的情形；18.将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。
当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空两个栈均从两端向中间增长当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置当top[0]+1 == top[1]时或top[0] == top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法解答】bot[0] top[0] top[1] bot[1] 双栈的类型定义如下：typedef struct{ int top0,top1; elemtype data[MAXSIZE];}DoubleStack;判栈空int DoubleStackEmpty(DoubleStack * DS,int StackNo){/*DS：指向双栈的指针，StackNo:0或1，指定要判断的是第0栈，还是第一栈 if(StackNo==0) return(DS->top0 < 0); else retrun(DS->top1 >= MAXSIZE);}判栈满int DoubleStackFull(DoubleStack * DS){ return(DS->top1-DS->top0==1);}入栈int PopDoubleStack(DoubleStack * DS,int StackNo,elemtype x){/*将数据元素x插入到栈StackNo中*/ if(DoubleStackFull(DS)) return(FALSE);/*栈满溢出*/ if(StackNo==0){/*对第0栈插入*/ DS->top0++; DS->data[top0]=x; } else{/*对第1栈插入*/ DS->top1--; DS->data[top1]=x; } return(TRUE);}删除算法elemtype PushDoubleStack(DoubleStack * DS,int StackNo){/*从StackNo栈中删除并返回一个元素，若栈空，则返回NULL*/ if(DoubleStackEmpty(DS,StackNo)) return(NULL); if(StackNo==0){/*对0号栈进行操作*/ DS->top0--; return(DS->data[DS->top0+1]); } else{ DS->top1++; return(DS->data[DS->top1-1]);}}19.改写顺序栈的进栈成员函数Push(x)，要求当栈满时执行一个stackFull( )操作进行栈满处理。
其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置解答】void push(stack * S,elemtype x) {if(StackEmpty(S)) stackFull(S); //栈满，做溢出处理 S->top ++; S->data[S->top] = x; //进栈}void stackFull(stack *S){elemtype *temp;temp=calloc(3*MAXSIZE,sizeof(elemtype)); //创建体积大二倍的数组 for ( int i = 0; i <= S->top; i++ ) //传送原数组的数据temp[i] = S->data[i]; free(S->data); //删去原数组 MAXSIZE *= 3; //数组最大体积增长二倍 S->data = temp; //新数组成为栈的数组空间}20.根据教案中给出的优先级，回答以下问题： 。