数据结构上机作业1-5章.doc

第一章

◆1.16② 试写一算法，如果三个整数X，Y和Z的值不是依次非递增的，则通过交换，令其为非递增。

void Descend(int &x, int &y, int &z)

/* 按从大到小顺序返回x，y和z的值 */

{ int t;

if(x<y)

{

t=x;

x=y;

y=t;

}

if(x<z)

{

t=x;

x=z;

z=t;

}

if(y<z)

{

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 temp[100];

int i,j,sum=0;

if(k<2||m<0) return ERROR;

if(m<k-1) f=0;

else if (m==k-1) f=1;

else

{

for(i=0;i<=k-2;i++) temp[i]=0;

temp[k-1]=1;

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

{

for(j=i-1;j>=i-k;j--)

sum=sum+temp[j];

temp[i]=sum;

sum=0;

}

f=temp[m];

}

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( result[i].sport )

{

switch( result[i].schoolname )

{

case 'A':

score[0].totalscore+= result[i].score;

if( result[i].gender == female )

score[0].femalescore+=result[i].score;

else

score[0].malescore+=result[i].score;

break;

case 'B':

score[1].totalscore += result[i].score;

if( result[i].gender == female )

score[1].femalescore+=result[i].score;

else

score[1].malescore+= result[i].score;

break;

case 'C':

score[2].totalscore += result[i].score;

if( result[i].gender == female )

score[2].femalescore+=result[i].score;

else

score[2].malescore += result[i].score;

break;

case 'D':

score[3].totalscore+= result[i].score;

if( result[i].gender == female )

score[3].femalescore+=result[i].score;

else

score[3].malescore+=result[i].score;

break;

case 'E':

score[4].totalscore+= result[i].score;

if( result[i].gender == female )

score[4].femalescore+=result[i].score;

else

score[4].malescore+=result[i].score;

break;

}

i++;

}

}

◆1.19④ 试编写算法，计算i!×2^i的值并存入数组

a[0..ARRSIZE-1]的第i-1个分量中 (i=1,2,…,n)。

假设计算机中允许的整数最大值为MAXINT，则当n>ARRSIZE或对某个k(1≤k≤n)使k!×2^k>MAXINT时，应

按出错处理。注意选择你认为较好的出错处理方法。

1.19

Status Series(int ARRSIZE, int a[])

/* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a； */

/* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */

{

int i=1;

int t=1;

a[0]=1;int n;

for(n=1;n<ARRSIZE;n++)

{

i=i*n;

t=2*n;

a[i]=i*t;

}

for(i=0;i<ARRSIZE;i++)

{

if(a[i]>MAXINT)

return OVERFLOW;

break;

}

return OK;

}

◆1.20④ 试编写算法求一元多项式

P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法

的时间复杂度。注意选择你认为较好的输入和输出方法。

1.20

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。 */

/* 数组a的元素a[i]为i次项的系数，i=0,...,n */

{ int i;

float s=0;

for(i=n;i>=0;i--)

s=s*x+a[i];

return s;

}

第二章

◆2.11② 设顺序表L中的数据元素递增有序。

试写一算法，将x插入到L的适当位置上，并保

持该表的有序性。

2.11

void InsertOrderList(SqList &L, ElemType x)

// 在有序的顺序表 L 中保序插入数据元素 x

{

int j;

j=L.length-1;

while(L.elem[j]>x)

{

L.elem[j+1]=L.elem[j];

j--;

}

L.elem[j+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'的首元，则A<B；否则A>B。试写一个比较A和B大小的算法。（注意：在算法中，不要破坏原表A和B，也不一定先求得A'和B'才进行比较）。

char Compare(SqList A, SqList B)

// 比较顺序表A和B,

// 返回'<', 若A<B;

// '=', 若A=B;

// '>', 若A>B

{

int i=0;

while((i<=A.length-1)&&(i<=B.length-1)&&(A.elem[i]=B.elem[i])) ++i;

if(i==A.length&&i==B.length) return '=';

else if(i==A.length&&i!=B.length&&A.elem[i]<B.elem[i]) return '<';

else if(i!=A.length&&i!=B.length&&A.elem[i]<B.elem[i]) return '<';

else 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 'NULL'

LinkList 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&&j<i-1)

{

p=p->next;

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&&j<i-1)

{

p=p->next;

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;i<=j;i++,j--)

{

temp=L.elem[i];

L.elem[i]=L.elem[j];

L.elem[j]=temp;

}

}

◆ 2.22③ 试写一算法，对单链表实现就地置。

void Inverse(LinkList &L)

/* 对带头结点的单链表L实现就地逆置 */

{

LinkList p,q,r;

p=L->next;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) 当m≤n时；或者 C=(a1,b1,...,an,bn,an+1,...,am) 当m＞n时。线性表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->data<q->data)

{

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

{

r->next=s;

r=r->next;

}

else if(s->data>='A'&&s->data<='Z'||s->data>='a'&&s->data<='z')

{

p->next=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.data[i].coef 存放ai， */

/* pn.data[i].exp存放ei (i=1,2,...,m) */

/* 本算法计算并返回多项式的值。不判别溢出。 */

/* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证*/

{ int i;

float s = 0;

for( i = 0; i < pn.length; ++i ){

s += pn.data[i].coef * f( x, pn.data[i].exp );

}

return s;

}

◆2.41② 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。

void Difference(LinkedPoly &pa)

/* 稀疏多项式 pa 以循环链表作存储结构， */

/* 将此链表修改成它的导函数，并释放无用结点 */

{

LinkedPoly p;

p=pa->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(str[i]!='&'&&str[i]!='@')

{

Push(s,str[i]);

i++;

}

if(str[i]=='@')

return FALSE;

if(str[i]=='&') i++;

while(str[i]!='@')

{

Pop(s,e);

if(e!=str[i])

return FALSE;

i++;

}

if(StackEmpty(s)&&str[i]=='@')

return TRUE;

else return FALSE;

}

3.18② 试写一个判别表达式中开、闭括号是否配对出现的算法。

Status MatchCheck(SqList exp)

/* 顺序表exp表示表达式； */

/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */

/* 注：本函数不使用栈 */

{ int i=0; int s=0;

while(exp.elem[i]!='\0')

{

if(exp.elem[i]=='(')

s++;

if(exp.elem[i]==')')

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.elem[i]!='\0')

{

if(exp.elem[i]=='