浙大远程数据结构与算法离线答案-最完整版(4)

删除所有值大于min而且小于max的元素。

SeqList Delete(SeqList &L, int min, int max) {

int i;=0,j=0

for (i=0; i

if(L.elem[i]>min && L.elem[i]

{ }

for(j=i;j

L.elem[j]=L.elem[j+1]; --L.length;

}

return L ; }

【8，3，2】给定一个顺序存储的线性表L = (a1, a2, ?, an)，请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。

void main() {

int n, i, j, k;

int A[1024]={}; int dp[1024]={};

scanf(\, &n); for (i=1; i<=n; i++) scanf(\, A[i]); dp[1] = 1; // 有n个阶段

for (i=2; i<=n; i++) {

dp[i] = 1; // 每个阶段只有1个状态

16

// 每个状态有i种决策,以得出以元素i结尾的最长递归子序列的长度 for (j=i-1; j>=0; j--) {

if (A[i]>A[j])

{ }

dp[i] = max(dp[i], dp[j]+1); } }

int maximum = dp[1]; for (i=2; i<=n; i++) }

{ }

printf(\, maximum); maximum = max(maximum, dp[i]);

【9，3，3】 如果有1、2、3、4、5按顺序入栈，不同的堆栈操作（pop, push）顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？

答案：按照正常情况，1,2,3,4,5的全排列组合共有5! = 120,即120种，但由于 像：12435、12534之类的无法按顺序出入栈，故按照顺序入栈的情况共有56种： 以1开始排列组合为14种

17

以2开始排列组合为14种 以3开始的排列组合为9种 以4开始的排列组合为4种 以5开始的排列组合为1种

【10，3，2】请编写程序将中缀表达式转换为后缀表达式。 答案：使用栈的循序存储结构实现、栈的顺序存储结构，用一维数组实现

#include #include

#define OK 1 #define ERROR -1 #define TRUE 1 #define FALSE 0

18

#define MAXSIZE 10 typedef int Status; typedef char ElemType; typedef struct {

ElemType data[MAXSIZE]; int top;//栈顶指针 }Stack; //1. 初始化

Status InitStack(Stack *S){ int i;

for(i=0;idata[i]=NULL; S->top=-1; return OK; }

//2. 创建一个长度为n的堆栈

Status CreateStack(Stack *S,int n){ int i =0;

if(n>MAXSIZE || n<1){

printf(\输入长度有误！\\n\); return ERROR; }

for(i=0;i

S->data[i]=rand()0+1; }

S->top=n-1;

return OK; }

Status push(Stack *S,ElemType e){ if(MAXSIZE-1==S->top){ printf(\栈已满\\n\); return ERROR; }

//栈顶指向的元素有值 ++(S->top);

19

S->data[S->top]=e; return OK; } //4. 出栈

Status pop(Stack *S,ElemType *e){ //将栈顶元素出栈，传给e if(-1==S->top){

printf(\栈为空！\\n\); return ERROR; }

*e=S->data[S->top]; --(S->top); return OK; }

//5. 中缀表达式转后缀表达式

void MidToFinal(char *mid,char *final){

//中缀表达式为middle，要转换成后缀表达式传给last //新建一个栈，来存储符号 char e; Stack S;

if(OK!=InitStack(&S)){

printf(\初始化栈失败！\\n\); }

//当带转换的字符串*mid未终止时，循环处理 while(*mid){

//如果是数字，则直接输出 if(*mid>='0' && *mid<='9'){ *(final++)=*(mid++); continue;

}else if(*mid=='+' || *mid=='-' || *mid=='*' || *mid=='/' || *mid=='(' || *mid==')'){

//输入的是合法运算符号,比较之前是否有更高优先级的符号 if(S.top==-1 || '('==*mid){

//当符号栈为空或遇到左括号时，符号入栈 push(&S,*(mid++)); continue; }

20