数据结构与算法离线作业2014春

n++; } else {

for(i = k; i <= m; i++) {

swap(&list[k],&list[i]); perm(list,k + 1, m); swap(&list[k],&list[i]); } } }

int main() {

int list[N];

int num,i=0;

printf(\ scanf(\ while(num != 0) {

list[i]=num; num=num/10; i++; }

perm(list,0, i-1);

printf(\ return 0; }

【7，3，2】 给定一个顺序存储的线性表L = (a1, a2, ?, an)，请设计一个算法删除所有值大于min而且小于max的元素。

#include #include #include typedef int ElemType; typedef struct LNode

{ ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */ }LNode; /* 结点结构类型 */

9

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(\,&x); /* 输入第一个数据元素 */ while( x!=-1) /* 输入-1，结束循环 */ {

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

scanf(\,&x); /* 输入下一个数据*/ }

return(h); } /* creat_L */ /* 输出单链表中的数据元素*/ void out_L(LNode *L) { LNode *p; p=L->next; printf(\数据是:\); while(p!=NULL) {

printf(\,p->data); 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;

L=creat_L(); out_L(L);

printf(\请输入你要删除的元素的范围min和max:\\n\);

10

scanf(\,&a,&b); delete_L(L,a,b); out_L(L); printf(\); }

【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];

int main() {

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

for (i=1; i<=n; i++) cin >> A[i]; dp[1] = 1;

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

dp[i] = 1;

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++)

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

11

}

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

1、2、3、4、5已经在栈中，那最后输出的是由尾到头：5、4、3、2、1。后进先出。

【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) {

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==')')

12