广工Anyview数据结构上机作业110章.doc

第一章1.16 试写一算法，如果三个整数X，Y和Z的值不是依次非递增的，则通过交换，令其为非递增。void Descend(int &x, int &y, int &z)/* 按从大到小顺序返回x，y和z的值 */ int t; if(xy) t=x; x=y; y=t; if(xz) t=x; x=z; z=t; if(yz) t=y; y=z; z=t; 1.17 已知k阶裴波那契序列的定义为 f0=0, f1=0, ., fk-2=0, fk-1=1; fn=fn-1+fn-2+.+fn-k, n=k,k+1,.试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。要求实现下列函数：Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ int tempd; int temp100; int i,j,sum=0; if(k2|m0) return ERROR; if(mk-1) f=0; else if (m=k-1) f=1; else for(i=0;i=k-2;i+) tempi=0; tempk-1=1; for(i=k;i=i-k;j-) sum=sum+tempj; tempi=sum; sum=0; f=tempm; return OK; 1.18 假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为项目名称 性别 校名 成绩 得分.编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已经储存在result 数组中, */* 并以特殊记录 , male, , , 0 （域scorce=0）*/* 表示结束 */ int i = 0; while( resulti.sport ) switch( resulti.schoolname ) case A: score0.totalscore+= resulti.score; if( resulti.gender = female ) score0.femalescore+=resulti.score; else score0.malescore+=resulti.score; break; case B: score1.totalscore += resulti.score; if( resulti.gender = female ) score1.femalescore+=resulti.score; else score1.malescore+= resulti.score; break; case C: score2.totalscore += resulti.score; if( resulti.gender = female ) score2.femalescore+=resulti.score; else score2.malescore += resulti.score; break; case D: score3.totalscore+= resulti.score; if( resulti.gender = female ) score3.femalescore+=resulti.score; else score3.malescore+=resulti.score; break; case E: score4.totalscore+= resulti.score; if( resulti.gender = female ) score4.femalescore+=resulti.score; else score4.malescore+=resulti.score; break; i+; 1.19 试编写算法，计算i!2i的值并存入数组a0.ARRSIZE-1的第i-1个分量中 (i=1,2,n)。假设计算机中允许的整数最大值为MAXINT，则当nARRSIZE或对某个k(1kn)使k!2kMAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。1.19Status Series(int ARRSIZE, int a) /* 求i!*2i序列的值并依次存入长度为ARRSIZE的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ int i=1; int t=1; a0=1;int n; for(n=1;nARRSIZE;n+) i=i*n; t=2*n; ai=i*t; for(i=0;iMAXINT) return OVERFLOW; break; return OK; 1.20 试编写算法求一元多项式 P(x) = a0 + a1x + a2x2 + . + anxn的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。1.20float Polynomial(int n, int a, float x)/* 求一元多项式的值P(x)。 */* 数组a的元素ai为i次项的系数，i=0,.,n */ int i; float s=0; for(i=n;i=0;i-) s=s*x+ai; return s;第二章2.11 设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。 2.11void InsertOrderList(SqList &L, ElemType x)/ 在有序的顺序表 L 中保序插入数据元素 x int j; j=L.length-1; while(L.elemjx) L.elemj+1=L.elemj; j-; L.elemj+1=x; L.length+; 2.12 设A=(a1,am)和B=(b1,bn)均为有序顺序表，A和B分别为A和B中除去最大共同前缀后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后的子表分别为A=(x,z)和B=(y,x,x,z)）。若A=B=空表，则A=B；若A=空表，而B 空表，或者两者均不为空表，且A的首元小于B的首元，则AB。试写一个比较A和B大小的算法。（注意：在算法中，不要破坏原表A和B，也不一定先求得A和B才进行比较）。char Compare(SqList A, SqList B)/ 比较顺序表A和B, / 返回, 若A, 若AB int i=0; while(i=A.length-1)&(i=B.length-1)&(A.elemi=B.elemi) +i; if(i=A.length&i=B.length) return =; else if(i=A.length&i!=B.length&A.elemiB.elemi) return ; else if(i!=A.length&i!=B.length&A.elemiB.elemi) return ;2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现下列函数：LinkList Locate(LinkList L, ElemType x);/ If x in the linked list whose head node is pointed / by L, then return pointer pointing node x, / otherwise return NULLLinkList Locate(LinkList &L, ElemType x)/ If x in the linked list whose head node is pointed/ by L, then return pointer ha pointing node x,/ otherwise return NULL LinkList ha; ha=L-next; while(ha!=NULL&ha-data!=x) ha=ha-next; if(ha=NULL) return NULL; else return ha; 2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。 int Length(LinkList L)/ Return the length of the linked list / whose head node is pointed by L LinkList p; int i=0; p=L; while(p-next!=NULL) p=p-next; i+; return i;2.17 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。void Insert(LinkList &L, int i, ElemType b) LinkList p,s; if(!L&i=1) L=(LinkList)malloc(sizeof(LNode); L-data=b; L-next=NULL; else if(i=0) else if(i=1) s=(LinkList)malloc(sizeof(LNode); s-data=b; s-next=L; L=s; else p=L; int j=1; while(p&jnext; j+ ; s=(LinkList)malloc(sizeof(LNode); s-data=b; s-next=p-next; p-next=s; 2.18 同2.17题要求。试写一算法，实现线性表操作DELETE(L,i)。void Delete(LinkList &L, int i) LinkList p,q; if(i=0) else if(i=1) p=L; L=L-next; free(p); else int j=1; p=L; while(p-next!=NULL&jnext; j+; q=p-next; p-next=q-next; free(q); 2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素 (使得操作后的线性表中所有元素的值均不相同) 同时释放被删结点空间，并分析你的算法的时间复杂度。void Purge(LinkList &L) LinkList p,q; p=L-next; q=p-next; while(q) if(p-data=q-data) q=q-next; p-next=q; q=q-next; p=p-next; 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,an)逆置为(an,an-1,a1)。void Inverse(SqList &L) int temp; int i,j; for(i=0,j=L.length-1;inext;q=NULL; while(p) r=q; q=p; p=p-next; q-next=r; L-next=q; 2.23 设线性表A=(a1,.,am), B=(b1,.,bn)，试写一个按下列规则合并A、B为线性表C的算法，即使得 C=(a1,b1,.,am,bm,bm+1,.,bn) 当mn时；或者 C=(a1,b1,.,an,bn,an+1,.,am) 当mn时。线性表A、B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。void Merge(LinkList ha, LinkList hb, LinkList &hc)/* 依题意，合并带头结点的单链表ha和hb为hc */ LinkList pa,pb,pc; pa=ha-next;pb=hb-next;pc=hc=ha; while(pa&pb) pc-next=pa;pc=pa;pa=pa-next; pc-next=pb;pc=pb;pb=pb-next; while(pa) pc-next=pa; pc=pa; pa=pa-next; while(pb) pc-next=pb; pc=pb; pb=pb-next; 2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C， 并要求利用原表（即A表和B表）的结点空间构造C表。void Union(LinkList &lc, LinkList &la, LinkList &lb) LinkList p,q,s,t; lc=la; p=la-next; q=lb-next; lc-next=NULL; while (p & q) if (p-datadata) s=p-next; p-next=lc-next; lc-next=p; p=s; else t=q-next; q-next=lc-next; lc-next=q; q=t; while (p) s=p-next; p-next=lc-next; lc-next=p; p=s; while (q) t=q-next; q-next=lc-next; lc-next=q; q=t; free(lb);2.31 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。ElemType DeleteNode(LinkList s) /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */ LinkList p,q; nt i; p=s; while(p-next-next!=s) p=p-next; q=p-next; i=q-data; p-next=q-next; free(q); return i;2.32 已知有一个单向循环链表，其每个结点中含三个域：prev、data和next，其中data为数据域，next为指向后继结点的指针域，prev也为指针域，但它的值为空(NULL)，试编写算法将此单向循环链表改为双向循环链表，即使prev成为指向前驱结点的指针域。void PerfectBiLink(BiLinkList &CL) BiLinkList p; for(p=CL;!p-next-prev;p=p-next) p-next-prev=p; 2.33 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll) LinkList p,q,r,s; p=lc;q=lo; r=ld,s=ll-next; while(s) if(s-data=0&s-datanext=s; r=r-next; else if(s-data=A&s-datadata=a&s-datanext=s; p=p-next; else q-next=s; q=q-next; s=s-next; p-next=NULL; q-next=NULL; r-next=NULL;2.37 设以带头结点的双向循环链表表示的线性表L=(a1,a2,.,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,.,an,.,a4,a2)。 void ReverseEven(BiLinkList &L) BiLinkList p; p=L-next; if(p-next=L) else while(p-next!=L&p-next-next!=L) p-next=p-next-next; p=p-next; if(p-next=L) p-next=L-prev-prev; else p-next=L-prev; p=p-next; while(p-prev-prev!=L) p-next=p-prev-prev; p=p-next; p-next=L; for(p=L;p-next!=L;p=p-next) p-next-prev=p; L-prev=p; 2.39 试对稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为给定值），并分析你的算法的时间复杂度。float f(float x,int j) int i; float s = 1; for( i = 0 ; i j; +i ) s *= x; return s;float Evaluate(SqPoly pn, float x)/* pn.datai.coef 存放ai， */* pn.datai.exp存放ei (i=1,2,.,m) */* 本算法计算并返回多项式的值。不判别溢出。 */* 入口时要求0e1e2.em，算法内不对此再作验证*/ int i; float s = 0; for( i = 0; i next; if(!p-exp) pa-next=p-next; p=p-next; while(p!=pa) p-coef=p-coef*p-exp ; p-exp-; p=p-next; 第三章3.17 试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而1+3&3-1则不是。Status match(char *str)/* 若str是属该模式的字符序列，*/* 则返回TRUE，否则返回FALSE */ SqStack s; SElemType e; InitStack(s); int i=0; while(stri!=&stri!=) Push(s,stri); i+; if(stri=) return FALSE; if(stri=&) i+; while(stri!=) Pop(s,e); if(e!=stri) return FALSE; i+; if(StackEmpty(s)&stri=) return TRUE; else return FALSE;3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。Status MatchCheck(SqList exp)/* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */* 注：本函数不使用栈 */ int i=0; int s=0; while(exp.elemi!=0) if(exp.elemi=() s+; if(exp.elemi=) s-; if(s=0) return TRUE; else return FALSE; 实现下列函数：Status MatchCheck(SqList exp);/* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */* 注：本函数不使用栈 */ 顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList; / 顺序表 3.19 假设一个算术表达式中可以包含三种括号：圆括号( 和)，方括号和和花括号和，且这三种括号可按任意的次序嵌套使用（如：()）。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。 实现下列函数：Status MatchCheck(SqList exp); /* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ 顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList; / 顺序表 Stack是一个已实现的栈。可使用的相关类型和函数：typedef char SElemType; / 栈Stack的元素类型Status InitStack(Stack &s);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType &e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType &e);Status MatchCheck(SqList exp)/* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ SqStack Q; int i=0; SElemType e; while(exp.elemi!=0) if(exp.elemi=(|exp.elemi=|exp.elemi=) Push(Q,exp.elemi); else if(exp.elemi=)|exp.elemi=|exp.elemi=) if(!StackEmpty(Q) Pop(Q,e) ; else return FALSE; if(e=(&exp.elemi!=) return ERROR; if(e=&exp.elemi!=) return ERROR; if(e=&exp.elemi!=) return ERROR; i+; if(StackEmpty(Q) return TRUE; else return FALSE;3.20 假设以二维数组g(1.m,1.n)表示一个图像区域，gi,j表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。 实现下列函数：void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0);/* 在g1.m1.n中，将元素gi0j0 */* 所在的同色区域的颜色置换为颜色c */ 表示图像区域的类型定义如下：typedef char GTYPEm+1n+1; Stack是一个已实现的栈。可使用的相关类型和函数：typedef char SElemType; / 栈Stack的元素类型Status StackInit(Stack &s, int initsize);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType &e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType &e);void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0)/* 在g1.m1.n中，将元素gi0j0 */* 所在的同色区域的颜色置换为颜色c */ Stack s; int row,col;/行，列 InitStack(s); char f; f = gi0j0; gi0j0 = c; Push( s, i0); Push( s, j0); while( !StackEmpty(s) ) Pop( s, col ); Pop( s, row ); if( row 1 & grow-1col = f ) Push( s, row-1); Push( s, col); grow-1col = c; if( row 1& growcol-1 = f ) Push( s, row); Push( s, col-1); growcol-1 = c; if( col =precede(ch) Pop(s1,cj+); w=Top(s1); Push(s1,ch); ch=ei+; else /while(ch=a)|(ch=A) cj+=ch; ch=ei+; / /cj+= ; Pop(s1,ch); while(ch!=) cj+=ch; Pop(s1,ch); /cj+=; cj+=0; return c; 3.24 试编写如下定义的递归函数的递归算法: g(m,n) = 0 当m=0,n=0 g(m,n) = g(m-1,2n)+n 当m0,n=0并根据算法画出求g(5,2)时栈的变化过程。int G(int m, int n)/* if m0 or n0 then return -1. */ int F; if(m0|n0) F=0; else if(m=0&n=0) F=0; else if(m0&n=0) F=G(m-1,2*n)+n;