广工数据结构anyview2015.doc-资料库

327a3635-d667-40d2-b8f7-0a4512210e7f.doc.pdf-第1页.png

第1页 / 共65页

327a3635-d667-40d2-b8f7-0a4512210e7f.doc.pdf-第2页.png

第2页 / 共65页

327a3635-d667-40d2-b8f7-0a4512210e7f.doc.pdf-第3页.png

第3页 / 共65页

327a3635-d667-40d2-b8f7-0a4512210e7f.doc.pdf-第4页.png

第4页 / 共65页

327a3635-d667-40d2-b8f7-0a4512210e7f.doc.pdf-第5页.png

第5页 / 共65页

327a3635-d667-40d2-b8f7-0a4512210e7f.doc.pdf-第6页.png

第6页 / 共65页

327a3635-d667-40d2-b8f7-0a4512210e7f.doc.pdf-第7页.png

第7页 / 共65页

327a3635-d667-40d2-b8f7-0a4512210e7f.doc.pdf-第8页.png

第8页 / 共65页

/********** 【题目】试写一算法，如果三个整数 a，b 和 c 的值不是依次非递增的，则通过交换，令其为非递增。 ***********/ void Descend(int &a, int &b, int &c) /* 通过交换，令 a >= b >= c */ { int t; if(a<=b){t=b;b=a;a=t;} if(b<=c){t=c;c=b;b=t;} if(a<=b){t=b;b=a;a=t;} } /********** 【题目】已知 k 阶裴波那契序列的定义为 f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1; f(n)=f(n-1)+f(n-2)+...+f(n-k), n=k,k+1,... 试编写求 k 阶裴波那契序列的第 m 项值的函数算法， k 和 m 均以值调用的形式在函数参数表中出现。 **********/ Status Fibonacci(int k, int m, int &f) /* 求 k 阶斐波那契序列的第 m 项的值 f */ { int t[100],i,j,sum; if(k<2||m<0) return ERROR; if(m

/********** 【题目】试编写算法，计算 i!×2^i 的值并存入数组 a[0..n-1]的第 i-1 个分量中 (i=1,2,…,n)。假设计算机中允许的整数最大值为 MAXINT，则当对某个 k (1≤k≤n)使 k!×2^k>MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。 **********/ Status Series(int a[], int n) /* 求 i!*2^i 序列的值并依次存入长度为 n 的数组 a； /* 若所有值均不超过 MAXINT，则返回 OK，否则 OVERFLOW */ { */ int i,s=1; if(n<0) return ERROR; for(i=1;i<=n;i++) { } a[i-1]=s*2*i; if(a[i-1]>MAXINT) return OVERFLOW; s=a[i-1]; return OK; } /********** 【题目】试写一算法，对序列 S 的第 i 个元素赋以值 e。序列的类型定义为： typedef struct { ElemType *elem; int length; } Sequence; ***********/ Status Assign(Sequence &S, int i, ElemType e) /* 对序列 S 的第 i 个元素赋以值 e，并返回 OK。 */ /* 若 S 或 i 不合法，则赋值失败，返回 ERROR */ { int j; if(S.length<=i||S.length==0)return ERROR; for(j=0;j!=i;j++); S.elem[j]=e; return OK; }

/********** 【题目】试写一算法，由长度为 n 的一维数组 a 构建一个序列 S。序列的类型定义为： typedef struct { ElemType *elem; int length; } Sequence; ***********/ Status CreateSequence(Sequence &S, int n, ElemType *a) /* 由长度为 n 的一维数组 a 构建一个序列 S，并返回 OK。 */ /* 若构建失败，则返回 ERROR { */ int i; if(n<=0) return ERROR; S.elem=(ElemType*)malloc(sizeof(ElemType)); S.length=n; for(i=0;i

/********** 【题目】链表的结点和指针类型定义如下 typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; 试写一函数，构建长度为 2 且两个结点的值依次为 x 和 y 的链表。 **********/ LinkList MakeNode(ElemType x) { LinkList Node; Node = (LinkList)malloc(sizeof(LNode)); if(Node == NULL) Node->data = x; Node->next = NULL; return Node; return NULL; } LinkList CreateLinkList(ElemType x, ElemType y) /* 构建其两个结点的值依次为 x 和 y 的链表。*/ /* 若构建失败，则返回 NULL。 { */ LinkList Node_x,Node_y; Node_x = MakeNode(x); Node_y = MakeNode(y); if(Node_x==NULL&&Node_y==NULL) Node_x->next = Node_y; return Node_x; } return NULL; /********** 【题目】链表的结点和指针类型定义如下 typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; 试写一函数，构建长度为 2 的升序链表，两个结点的值分别为 x 和 y，但应小的在前，大的在后。 **********/

LinkList MakeNode(ElemType x) { LinkList Node; Node = (LinkList)malloc(sizeof(LNode)); if(Node == NULL) Node->data = x; Node->next = NULL; return Node; return NULL; } LinkList CreateOrdLList(ElemType x, ElemType y) /* 构建长度为 2 的升序链表。 */ /* 若构建失败，则返回 NULL。 */ { LinkList p,q; p=MakeNode(x); q=MakeNode(y); if((p->data)>(q->data)) {q->next=p; else p->next=q; return p; return q;} } /********** 【题目】试写一算法，实现顺序栈的判空操作 StackEmpty_Sq(SqStack S)。顺序栈的类型定义为： typedef struct { ElemType *elem; // 存储空间的基址 int top; int size; int increment; // 栈顶元素的下一个位置，简称栈顶位标 // 当前分配的存储容量 // 扩容时，增加的存储容量 // 顺序栈 } SqStack; ***********/ Status StackEmpty_Sq(SqStack S) /* 对顺序栈 S 判空。 /* 若 S 是空栈，则返回 TRUE；否则返回 FALSE */ { */ if(!S.top)return TRUE; else return FALSE; }

/********** 【题目】试写一算法，实现顺序栈的取栈顶元素操作 GetTop_Sq(SqStack S, ElemType &e)。顺序栈的类型定义为： typedef struct { ElemType *elem; int top; int size; int increment; // 存储空间的基址 // 栈顶元素的下一个位置，简称栈顶位标 // 当前分配的存储容量 // 扩容时，增加的存储容量 // 顺序栈 } SqStack; ***********/ Status GetTop_Sq(SqStack S, ElemType &e) /* 取顺序栈 S 的栈顶元素到 e，并返回 OK； */ /* 若失败，则返回 ERROR。 { */ e=S.elem[S.top-1]; if(e!='\0')return OK; return ERROR; } /********** 【题目】试写一算法，实现顺序栈的出栈操作 Pop_Sq(SqStack &S, ElemType &e)。顺序栈的类型定义为： typedef struct { ElemType *elem; int top; int size; int increment; // 存储空间的基址 // 栈顶元素的下一个位置，简称栈顶位标 // 当前分配的存储容量 // 扩容时，增加的存储容量 // 顺序栈 } SqStack; ***********/ Status Pop_Sq(SqStack &S, ElemType &e) /* 顺序栈 S 的栈顶元素出栈到 e，并返回 OK；*/ /* 若失败，则返回 ERROR。 { */ e=S.elem[S.top-1]; S.top--; if(e!='\0')return OK; else return ERROR; }

/********** 【题目】若顺序栈的类型重新定义如下。试编写算法，构建初始容量和扩容增量分别为 size 和 inc 的空顺序栈 S。 typedef struct { ElemType *elem; // 存储空间的基址 ElemType *top; int size; int increment; // 当前分配的存储容量 // 扩容时，增加的存储容量 // 栈顶元素的下一个位置 } SqStack2; ***********/ Status InitStack_Sq2(SqStack2 &S, int size, int inc) /* 构建初始容量和扩容增量分别为 size 和 inc 的空顺序栈 S。*/ /* 若成功，则返回 OK；否则返回 ERROR。 { */ return ERROR; if(size<=0||inc<=0) return ERROR; ElemType* base; base = (ElemType*)malloc(size*sizeof(ElemType)); if(base == NULL) S.elem = base; S.top = base; S.size = size; S.increment = inc; return OK; } /********** 【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的判空操作。 typedef struct { ElemType *elem; // 存储空间的基址 ElemType *top; int size; int increment; // 当前分配的存储容量 // 扩容时，增加的存储容量 // 栈顶元素的下一个位置 } SqStack2; ***********/ Status StackEmpty_Sq2(SqStack2 S) /* 对顺序栈 S 判空。 */

/* 若 S 是空栈，则返回 TRUE；否则返回 FALSE */ { if(S.elem==S.top) return TRUE; else return FALSE; } /********** 【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的入栈操作。 typedef struct { ElemType *elem; // 存储空间的基址 ElemType *top; int size; int increment; // 当前分配的存储容量 // 扩容时，增加的存储容量 // 栈顶元素的下一个位置 } SqStack2; ***********/ Status Push_Sq2(SqStack2 &S, ElemType e) /* 若顺序栈 S 是满的，则扩容，若失败则返回 ERROR。*/ /* 将 e 压入 S，返回 OK。 { */ ElemType *newbase; if(S.top>=S.size){ int t=S.top-S.elem; newbase=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType)); if(NULL==newbase)return ERROR; S.elem=newbase; S.top=S.elem+t; } *S.top++=e; return OK; } /********** 【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的出栈操作。 typedef struct { ElemType *elem; // 存储空间的基址 ElemType *top; int size; // 当前分配的存储容量 // 栈顶元素的下一个位置

资料库

广工数据结构anyview2015.doc

相关推荐

课程资源

热门标签

最新资料