数据结构与算法离线作业 答案 - 下载本文

struct LNode *next; /* 指针子域 */ }LNode; /* 结点结构类型 */ LNode *L;

/* 函数声明 */ LNode *creat_L();

void delete_L(LNode *L,int i); //返回值格式变为空

/* 建立线性链表*/ LNode *creat_L() {

LNode *h,*p,*s; ElemType x;

h=(LNode *)malloc(sizeof(LNode)); /* 分配头结点 */ h->next=NULL; p=h;

printf(\输入一串数字(以-1结束):\\ndata= \

scanf(\ /* 输入第一个数据元素 */ while( x!=-1) /* 输入-1,结束循环 */ {

s=(LNode *)malloc(sizeof(LNode)); /* 分配新结点 */ s->data=x; s->next=NULL; p->next=s; p=s; printf(\

scanf(\ /* 输入下一个数据*/ } return(h); } /* creat_L */

/* 输出单链表中的数据元素*/ void out_L(LNode *L) {

LNode *p; p=L->next; printf(\数据是:\

11

while(p!=NULL) {

printf(\ p=p->next; } } /* out_link */

/* 删除大于x小于y的值*/ void delete_L(LNode *L,int a,int b) {

LNode *p,*q; p=L; q=p; p=p->next;

if(p==NULL) printf(\链表为空\ while(p!=NULL) {

if((p->data >a) && (p->data next=p->next; free(p); p=q->next; } else { q=p; p=p->next; } }

} /* delete_L */

void main() {

int a,b;

12

L=creat_L( ); out_L(L);

printf(\请输入你要删除的元素的范围min和max:\\n\ scanf(\ delete_L(L,a,b); out_L(L); printf(\} /* main */

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

#include #include using namespace std;

#define MAXN 1003 int A[MAXN]; int dp[MAXN];

// 动态规划思想O(n^2) int main() {

int n, i, j, k; cin >> n;

for (i=1; i<=n; i++) cin >> A[i]; dp[1] = 1; // 有n个阶段

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

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

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

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

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

13

}

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

maximum = max(maximum, dp[i]); cout << maximum; }

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

Answer:

共有34种不同的输出序列

12345 12354 12435 12543 13245 13254 14325 15432 21345 21435 21543 23145 23154 23415 23451 23541 24315 24351 24531 25431 32145 32154 32415 32451 32541 34215 34251 34521 35421 43215 43251 43521 45321 54321

【10,3,2】请编写程序将中缀表达式转换为后缀表达式。

#include #include #include using namespace std; int prior(char op) {

if(op=='+'||op=='-') return 1;

if(op=='*'||op=='/') return 2; return 0; }

string middletolast(string middle) {

14

stack op; string ans;

for(int i=0;i

char c=middle[i]; if(c>='0'&&c<='9') {

ans.append(1,c); } else

{

if(c=='(') op.push('('); else {

if(c==')') {

while(op.top()!='(') {

ans.append(1,op.top()); op.pop(); }

op.pop(); } else {

if(op.empty()) {

op.push(c); } else {

if(prior(c)>prior(op.top())) op.push(c); else {

while(!op.empty()&&prior(c)<=prior(op.top())) {

ans.append(1,op.top());

15