浙大远程教育数据结构与算法离线作业参考答案(3)

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; /* 结点结构类型 */

11

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) /* {

s=(LNode *)malloc(sizeof(LNode)); /* s->data=x; s->next=NULL p->next=s; p=s; printf(\

scanf(\ }

12

分配头结点 */ 输入第一个数据元素 */ 输入-1，结束循环 */ 分配新结点 */ 输入下一个数据*/ return(h); } /* creat_L */

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

LNode *p; p=L->next;

printf(\数据是:\ 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;

13

p=p->next;

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

if((p->data >a) && (p->data

q->next=p->next; free(p); p=q->next; } else { q=p; p=p->next; } }

} /* delete_L */ void main() {

int a,b

14

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;

15