20##上机实习基本要求及内容
上机实习基本目标
计算机学科分为理论、抽象、设计三个形态。
数据结构是计算机学科的重要分支研究领域之一。在算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课程中均有涉及。对特定领域或应用要使用到头特定的数据结构:编译系统要使用栈、散列表及语法树;操作系统中要用队列、存储管理表及目录树等;数据库系统要用线性表、多链表及索引树等;在人工智能领域依求解问题性质的差异将涉及到各种不同的数据结构,如广义表,集合、搜索树及各种有向图等等。
通过数据结构上机实习要让学生掌握链表、树、图是如何实现的,进一步从理论、抽象、设计的角度来考虑问题。第一,让学生真正理解“数据结构+算法=程序”。程序不仅仅是求解算法的实现,也要配有恰当的数据结构;第二,培养学生数据抽象的能力。让学生了解链表、树、图等数据结构是如何实现的,特别要加强对数据逻辑关系的分析与认识;第三,培养学生使用数据结构的能力。要把数据结构与算法的理论分析与编程实践相结合,灵活运用于实际解题中。
需要强调以下几个方面的知识和能力:
(1)掌握并能够灵活应用基本数据结构的抽象数据类型、存储方法、主要的算法,特别是线性结构、二叉树、树、图、文件等;
(2)掌握并应用常用的排序、检索和索引算法和方法;
(3)掌握基本的算法设计和分析技术,并结合具体的设计,对所设计的数据结构和算法进行分析;
(4)在进行程序设计、调试中,注意综合应用,将所学到的数据结构和算法知识应用到对具体数据对象的特性分析。结合实际例子进行设计,选择合适的数据结构和存贮结构以及相应的算法。
上机实习基本要求
1.合理地选用组织数据、有效地表示数据、正确地处理数据,清晰地表述算法。
2.完成选定题目,按照规范格式(附件一)写出实习报告(原问题、设计算法、DS、程序、给出实例并分析结果、讨论T(n))。
3.线性关系、非线性关系、算法三部分的实习报告电子版提交日期在上机后2日内提交;第四次机考电子版在上机结束时提交(电子版交liuxd@nwpu.edu.cn,将四次上机汇总打印纸版笔试前1周交西1楼711室);请按时提交注意上交电子版与纸版应一致。
4. 请按照附件给定报告内容格式安排。
附件一:报告封面格式
附件二:报告内容格式( 封面见附件一。正文要求:A4纸,小4#宋体,右下页码,最小行距)
一、上机实习题目(原问题à解目标)
二、相关知识或技术(对应DS部分)
三、算法及数据结构设计(算法设计)
四、上机环境和使用语言(计算机程序实现)
五、源程序(带注释或说明)、运行结果(数据或屏幕显示、结果分析、讨论T(n))
六、上机总结(体会提高)
七、参考资料
附件三:上机实习参考题目
(1)各个DS的插入、删除、建立、判空;
(2)线性链表操作——插入、删除、合并、排序、查找
(3)将一个递归程序转为非递归程序。
(4)编制标准算法,将两个线性表合并成一个。
(5)用一个数组S(设大小为MAX)作为对开栈的共享空间。请说明共享方法、栈满/栈空的判断条件,设计入栈操作push(i,x),其中i为0或1,用于表示栈号,x为入栈值;并设计清、判空、判满、出栈操作。
(6)对于一个堆栈,若其入栈序列为1,2,3,...,n,不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于节点个数为n的二叉树的个数,且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为1,2,3,...n)/输出序列对应一种二叉树形态的方法,并以入栈序列1,2,3(即n等于3)为例加以说明。
(7)求Л到小数点后100位。
(8)长整数四则运算ADT与存储实现。
(9)树和二叉树的递归遍历/非递归遍历;
(10)求二叉树中最长/短路径。
(11)求最大平台问题(n个整数序列,相同值连续最大的称最大平台)。
(12)最小生成树;
(13)检索与查找算法。
(14)排序与广义表算法。
(15)为图书馆借书处/食堂售卡处业务设计一个业务系统完成日常的相关工作。
(16)为民航/火车售票处的票务业务设计一个计划、团体/零售、查询系统。
(17)已知二叉树中结点的左右儿子域分别为left和right。p指向二叉树的某一节点。请编一个非递归函数postfirst(p),求p所对应子树的第一个后序(后根)遍历节点。
(18)已知树中结点的用左孩子右兄弟表示,p指向二叉树的某一结点。请编遍历树算法。
(19)编程生成国际象棋棋盘,使马踏棋盘各格一次且仅一次。
(20)编程生成迷宫(平面,立体),指定出入口位置,找出一条/所有路径。
(21)图的遍历算法。
(22)求最大平台问题(n个字符的串,相同字符最长的)。
提示:教材各章后练习题、实习题均可选用。也可选择最基本的ADT操作编程上机调试,作为课程考核内容;要求认真精选上机题完成上机调试、获取实验结果、写出实习报告。
第二篇:数据结构上机作业1-5章
第一章
◆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 */
{
SqStack Q;
SElemType e,b;
int i=0;
if(exp.elem[i]=='\0') return TRUE;
for(i=0;i<exp.length;i++)
{
e=exp.elem[i];
if(e=='('||e=='['||e=='{') Push(Q,e);
else if(exp.elem[i+1]!='\0')
{
b=exp.elem[i+1];
if(e=='['&&b!=']') return ERROR;
if(e=='('&&b!=')') return ERROR;
if(e=='{'&&b!='}') return ERROR;
}
else {
Pop(Q,e);
i=i+1;
j=j-1;
return TRUE;
}
}
StackEmpty(Q);
}
实现下列函数:
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]=='('||exp.elem[i]=='['||exp.elem[i]=='{') Push(Q,exp.elem[i]);
else if(exp.elem[i]==')'||exp.elem[i]==']'||exp.elem[i]=='}') { if(!StackEmpty(Q))
Pop(Q,e) ;
else return FALSE;
if(e=='('&&exp.elem[i]!=')')
return ERROR;
if(e=='['&&exp.elem[i]!=']')
return ERROR;
if(e=='{'&&exp.elem[i]!='}')
return ERROR;
}
i++;
}
if(StackEmpty(Q))
return TRUE;
else return FALSE;
}
3.20③ 假设以二维数组g(1..m,1..n)表示一个图像区域,g[i,j]表示该区域中点(i,j)所具颜色,其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。
实现下列函数:
void ChangeColor(GTYPE g, int m, int n,
char c, int i0, int j0);
/* 在g[1..m][1..n]中,将元素g[i0][j0] */
/* 所在的同色区域的颜色置换为颜色c */
表示图像区域的类型定义如下:
typedef char GTYPE[m+1][n+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)
/* 在g[1..m][1..n]中,将元素g[i0][j0] */
/* 所在的同色区域的颜色置换为颜色c */
{ Stack s;
int row,col;//行,列
InitStack(s);
char f;
f = g[i0][j0];
g[i0][j0] = c;
Push( s, i0);
Push( s, j0);
while( !StackEmpty(s) ){
Pop( s, col );
Pop( s, row );
if( row > 1 && g[row-1][col] == f ){ Push( s, row-1);
Push( s, col);
g[row-1][col] = c;
}
if( row < m && g[row+1][col] ==f ){ Push( s, row+1);
Push( s, col);
g[row+1][col] = c;
}
if( col > 1&& g[row][col-1] == f ){ Push( s, row);
Push( s, col-1);
g[row][col-1] = c;
}
if( col < n && g[row][col+1] == f ){ Push( s, row );
Push( s, col+1 );
g[row][col+1] = c;
}
}
}
◆3.21③ 假设表达式由单字母变量和双目四则运
算算符构成。试写一个算法,将一个通常书写形式
且书写正确的表达式转换为逆波兰式。
实现下列函数:
char *RPExpression(char *e);
/* 返回表达式e的逆波兰式 */
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);
int precede(char op)
{ int x;
switch(op)
{
case '*': x=2; break;
case '/': x=2; break;
case '+': x=1; break;
case '-': x=1; break;
default : x=0;
}
return x;
}
char *RPExpression(char *e)
{/* 返回表达式e的逆波兰式 */
char *c;
c=(char*)malloc(sizeof(char)*20);
Stack s1;
InitStack(s1);
int i=0,j=0;
char ch;
Push(s1,'@');
ch=e[i++];
while(ch!= 0)
{
if(ch=='(')
{
Push(s1,ch);
ch=e[i++];
}
else if(ch==')')
{
while(Top(s1)!='(')
{
//不能用char c[]
Pop(s1,c[j++]);
}
/* to[j++]=pop(&s1);*/
Pop(s1,ch);
ch=e[i++];
}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{
char w;
w=Top(s1);
while(precede(w)>=precede(ch))
{
Pop(s1,c[j++]);
w=Top(s1);
}
Push(s1,ch);
ch=e[i++];
}
else
{
//while((ch<='z'&&ch>='a')||(ch<='Z'
&& ch>='A')){
c[j++]=ch;
ch=e[i++];
//}
//c[j++]=' ';
}
}
Pop(s1,ch);
while(ch!='@')
{
c[j++]=ch;
Pop(s1,ch);
}
//c[j++]=;
c[j++]=0;
return c;
}
3.24③ 试编写如下定义的递归函数的递归算法:
g(m,n) = 0 当m=0,n>=0
g(m,n) = g(m-1,2n)+n 当m>0,n>=0
并根据算法画出求g(5,2)时栈的变化过程。
int G(int m, int n)
/* if m<0 or n<0 then return -1. */
{
int F;
if(m<0||n<0) return -1;
else if(m==0&&n>0) F=0;
else if(m==0&&n==0)
else if(m>0&&n>=0)
F=G(m-1,2*n)+n;
return F;
}
3.25
int F(int n)
/* if n<0 then return -1. */
{ int f;
if(n<0) return -1;
else
{
if(n==0) f=n+1;
else f=n*F(n/2);
return f;
}
}
F=0;
3.25④ 试写出求递归函数F(n)的递归算法,
并消除递归:
F(n) = n+1 当n=0
F(n) = nF(n/2) 当n>0
实现下列函数:
int F(int n);
/* if n<0 then return -1. */
int F(int n)
/* if n<0 then return -1. */
{ int f;
if(n<0) return -1;
else
{
if(n==0) f=n+1;
else f=n*F(n/2);
return f;
}
}
◆3.28② 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队列和出队列的算法。
实现下列函数:
Status InitCLQueue(CLQueue &rear);
Status EnCLQueue(CLQueue &rear, ElemType x);
Status DeCLQueue(CLQueue &rear, ElemType &x);
带头结点循环链队列CLQueue的类型为以下LinkList类型:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
typedef LinkList CLQueue;
Status InitCLQueue(CLQueue &rear)
{
rear=(LNode*)malloc(sizeof(LNode));
rear->next=rear;
return OK;
}
Status EnCLQueue(CLQueue &rear, ElemType x)
{
LinkList p;
p=(LNode*)malloc(sizeof(LNode));
p->data=x;
p->next=rear->next;
rear->next=p;
rear=p;
return OK;
}
Status DeCLQueue(CLQueue &rear, ElemType &x)
{ LinkList p;
if(rear->next!=rear )
{
p=rear->next;
rear->next=p->next;
free(p);
return OK; }
else return ERROR;
}
3.29③ 如果希望循环队列中的元素都能得到利用,则需设置一个标志域tag,并以tag的值为0或1来区分,尾指针和头指针值相同时的队列状态是"空"还是"满"。试编写与此结构相应的入队列和出队列的算法,并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围(比如,当循环队列容量较小而队列中每个元素占的空间较多时,那一种方法较好?)。
实现下列函数:
Status EnCQueue(CTagQueue &Q, QElemType x);
Status DeCQueue(CTagQueue &Q, QElemType &x);
本题的循环队列CTagQueue的类型定义如下:
typedef char QElemType;
typedef struct {
QElemType elem[MAXQSIZE];
int tag;
int front;
int rear;
} CTagQueue;
Status EnCQueue(CTagQueue &Q, QElemType x)
{ int tag;
if(Q.front==Q.rear&&tag==1)
return ERROR;
Q.elem[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXQSIZE;
tag=1;
return OK;
}
Status DeCQueue(CTagQueue &Q, QElemType &x)
{
int tag;
if(Q.front==Q.rear&&tag==0)
return ERROR;
x=Q.elem[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
if(Q.front==Q.rear)
tag=0;
return OK;
}
◆3.30② 假设将循环队列定义为:以域变量rear
和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件,并写出相应的入队列和出队列的算法(在出队列的算法中要返回队头元素)。
实现下列函数:
Status EnCQueue(CLenQueue &Q, QElemType x);
Status DeCQueue(CLenQueue &Q, QElemType &x);
本题的循环队列CLenQueue的类型定义如下:
typedef char QElemType;
typedef struct {
QElemType elem[MAXQSIZE];
int length;
int rear;
} CLenQueue;
StatusEnCQueue(CLenQueue&Q,
QElemType x)
{
if(Q.length==MAXQSIZE)
return ERROR;
Q.rear=(Q.rear+1)%MAXQSIZE;
Q.elem[Q.rear]=x;
Q.length++;
return OK;
}
Status DeCQueue(CLenQueue &Q, QElemType &x)
{
if(Q.length==0)
return ERROR;
x=Q.elem[(Q.rear-Q.length+1+MAXQSIZE)%MAXQSIZE];
Q.length--;
return x;
}
◆3.31③ 假设称正读和反读都相同的字符序列为"回文",例如,'abba'和'abcba'是回文,'abcde'
和'ababab'则不是回文。试写一个算法判别读入的
一个以'@'为结束符的字符序列是否是"回文"。
实现下列函数:
Status Palindrome(char *word);
/* 利用栈和队列判定字符序列word是否是回文 */
可使用栈Stack和队列Queue及其下列操作:
Status InitStack(Stack &S);
Status Push(Stack &S, ElemType x);
Status Pop(Stack &S, ElemType &x);
Status StackEmpty(Stack S);
Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, ElemType x);
Status DeQueue(Queue &Q, ElemType &x);
Status QueueEmpty(Queue Q);
Status Palindrome(char *word)
/* 利用栈和队列判定字符序列word是否是回文 */
{
Stack Q;
SElemType e,f;
Queue S;
char *p;
p=word;
InitStack(Q);
InitQueue(S);
while(*p!='@')
{
Push(Q,*p);EnQueue(S,*p);
p++;
}
while(!StackEmpty(Q))
{ Pop(Q,e); DeQueue(S,f);
if(e!=f)
return ERROR;
}
return OK;
}
第四章
4.10③ 编写对串求逆的递推算法。
要求实现以下函数:
void Reverse(StringType &s);
/* Reverse s by iteration. */
StringType是串的一个抽象数据类型,它包含以下6种基本操作:
void InitStr(StringType &s);
// 初始化s为空串。
void StrAssign(StringType &t, StringType s);
// 将s的值赋给t。s的实际参数是串变量。
int StrCompare(StringType s, StringType t);
// 比较s和t。若s>t,返回值>0;若s=t,返回值=0;若s<t,返回值<0。
int StrLength(StringType s);
// 返回s中的元素个数,即该串的长度。
StringType Concat(StringType &s, StringType t);
// 返回由s和t联接而成的新串。
StringType SubString(StringType s, int start, int len);
// 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时,
// 返回s中第start个字符起长度为len的子串,否则返回空串。
// 注意,不要使用 " s = " 的形式为 StringType 类型的变量赋值 ,
// 而要使用 StrAssign 函数!!!
void Reverse(StringType &s)
/* Reverse s by iteration. */
{
int i=0,j=StrLength(s)-1;
char temp;
while(i<=j)
{
temp=s[i];
s[i]=s[j];
s[j]=temp;
i++;j--;
}
}
4.12③ 编写一个实现串的置换操作Replace(&S,T,V)的算法。
要求实现以下函数:
void Replace(StringType &S, StringType T, StringType V);
/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */
StringType是串的一个抽象数据类型,它包含以下6种基本操作:
void InitStr(StringType &s);
// 初始化s为空串。
void StrAssign(StringType &t, StringType s);
// 将s的值赋给t。s的实际参数是串变量。
int StrCompare(StringType s, StringType t);
// 比较s和t。若s>t,返回值>0;若s=t,返回值=0;若s<t,返回值<0。
int StrLength(StringType s);
// 返回s中的元素个数,即该串的长度。
StringType Concat(StringType &s, StringType t);
// 返回由s和t联接而成的新串。
StringType SubString(StringType s, int start, int len);
// 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时,
// 返回s中第start个字符起长度为len的子串,否则返回空串。
// 注意,不要使用 " s = " 的形式为 StringType 类型的变量赋值 ,
// 而要使用 StrAssign 函数!!!
void Replace(StringType &S, StringType T, StringType V)
/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */
{
int i; StringType head,tail;
//InitStr(head);InitStr(tail);
for(i=1;i<=StrLength(S)-StrLength(T)+1;i++)
if(!StrCompare(SubString(S,i,StrLength(T)),T))
{
StrAssign(head,SubString(S,1,i-1));
StrAssign(tail,SubString(S,i+StrLength(T),StrLength(S)-i-StrLength(T)+1));
StrAssign(S,Concat(head,V));
Concat(S,tail);
i=i+StrLength(V)-1;
}
}
4.13③ 编写算法,从串s中删除所有和串t相同的子串。
要求实现以下函数:
void DelSubString(StringType &scrStr, StringType subStr);
/* Remove all substring matching 'subStr' from 'scrStr'. */
StringType是串的一个抽象数据类型,它包含以下6种基本操作:
void InitStr(StringType &s);
// 初始化s为空串。
void StrAssign(StringType &t, StringType s);
// 将s的值赋给t。s的实际参数是串变量。
int StrCompare(StringType s, StringType t);
// 比较s和t。若s>t,返回值>0;若s=t,返回值=0;若s<t,返回值<0。
int StrLength(StringType s);
// 返回s中的元素个数,即该串的长度。
StringType Concat(StringType &s, StringType t);
// 返回由s和t联接而成的新串。
StringType SubString(StringType s, int start, int len);
// 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时,
// 返回s中第start个字符起长度为len的子串,否则返回空串。
// 注意,不要使用 " s = " 的形式为 StringType 类型的变量赋值 ,
// 而要使用 StrAssign 函数!!!
void DelSubString(StringType &scrStr, StringType subStr)
/* Remove all substring matching 'subStr' from 'scrStr'. */
{
StringType head,tail,S;
int i;
InitStr(head);
InitStr(tail);
for(i=1;i<=StrLength(scrStr)-StrLength(subStr)+1;i++)
if(!StrCompare(SubString(scrStr,i,StrLength(subStr)),subStr))
{
StrAssign(head,SubString(scrStr,1,i-1));
StrAssign(tail,SubString(scrStr,i+StrLength(subStr),StrLength(scrStr)-i-StrLength(subStr)+1)); StrAssign(scrStr,Concat(head,tail));
i--; /*向后退一位*/
}
}
4.17③ 编写算法,实现串的基本操作Replace(&S,T,V)。要求采用教科书4.2.1节中所定义的定长顺序存储表示,但不允许调用串的基本操作。
要求实现以下函数:
Status Replace(SString& s, SString t, SString v);
/* 用串v替换串s中所有和串t匹配的子串。 */
/* 若有与t匹配的子串被替换,则返回TRUE;*/
/* 否则返回FALSE */
定长顺序串SString的类型定义:
typedef unsigned char SString[MAXSTRLEN+1];
/* s[0] is the string's length */
int Index(SString s, SString t,int pos )
{
int i = pos;
int j = 1;
while( i<= s[0]&&j<=t[0])
{
if( s[i] == t[j] ){ ++i; ++j; }
else{i= i-j+2;j=1;}
}
if( j > t[0] ) return i - t[0];
else return 0;
}
Status Replace(SString& s, SString t, SString v)
/* 用串v替换串s中所有和串t匹配的子串。 */
/* 若有与t匹配的子串被替换,则返回TRUE;*/
/* 否则返回FALSE */
{ int flag = 0;//是否替换的标志
int i,j,w,r; //i是s1的标志,j是s的标志,
SString s1;
for( i = 0; i <= s[0]; i++ )
s1[i] = s[i];
for( i = 1, j = 1; i <= s1[0]; )
{
w = Index( s1, t, i); //返回t的起始位置
if( !w )
{
while( i <= s1[0] )
s[j++] = s1[i++];
}
else
{
while( i < w )
s[j++] = s1[i++];
for( r = 1; r <= v[0]; r++ )
s[j++] = v[r];
flag++;
i += t[0];
}
}
s[0] = --j;
if( flag )
return TRUE;
return FALSE;
}
/*int i,j,k,l;
for(i=1;i<=s[0]-t[0]+1;i++)
{
for(j=i,k=1;t[k]&&s[j]==t[k];j++,k++)
if(k>t[0])
{
if(t[0]==v[0])
for(l=1;i<=t[0];l++)
s[i+l-1]=v[l];
else if(t[0]<v[0])
{
for(l=s[0];l>i+t[0];l--)
s[l+v[0]-t[0]]=s[l];
for(l=1;l<=v[0];l++)
s[i+l-1]=v[l];
}
else
{
for(l=i+v[0];l<=s[0]+v[0]-t[0];l++)
s[l]=s[l-v[0]+t[0]];
for(l=1;l<=v[0];l++)
s[i+l-1]=v[l];
}
s[0]=s[0]-t[0]+v[0];
i=i+v[0];
}
}
return TRUE; */
4.20③ 编写算法,从串s中删除所有和串t相同的子串。
要求实现以下函数:
Status DelSub(SString &s, SString t);
/* 从串s中删除所有和串t匹配的子串。 */
/* 若有与t匹配的子串被删除,则返回TRUE;*/
/* 否则返回FALSE */
定长顺序串SString的类型定义:
typedef unsigned char SString[MAXSTRLEN+1];
/* s[0] is the string's length */
int Index(SString s, SString t,int pos )
{
int i = pos;
int j = 1;
while( i<= s[0]&&j<=t[0])
{
if( s[i] == t[j] ){ ++i; ++j; }
else{i= i-j+2;j=1;}
}
if( j > t[0] ) return i - t[0];
else return 0;
}
Status DelSub(SString &s, SString t)
/* 从串s中删除所有和串t匹配的子串。 */
/* 若有与t匹配的子串被删除,则返回TRUE;*/
/* 否则返回FALSE */
{
int flag = 0;//是否替换的标志
int i,j,w; //i是s1的标志,j是s的标志,
for( i = 1, j = 1; i <= s[0]; )
{
w = Index( s, t, i); //返回t的起始位置
if( !w )
{
while( i <= s[0] )
s[j++] = s[i++];
}
else
{
while( i < w )
s[j++] = s[i++];
flag++;
i += t[0];
}
}
s[0] = --j;
if( flag )
return TRUE;
return FALSE;
}
4.24③ 采用教科书4.2.2节中所定义的堆分配存储表示。试写一算法,在串的堆存储结构上实现串基本操作Concat(&T, s1, s2)。
要求实现以下函数:
Status Concat(HString &S, HString S1, HString S2)
/* 用S返回由S1和S2联接而成的新串 */
堆串HString的类型定义:
typedef struct {
char *ch; // 若是非空串,则按串长分配存储区,否则ch为NULL
int length; // 串长度
} HString;
Status Concat(HString &S, HString S1, HString S2)
/* 用S返回由S1和S2联接而成的新串 */
{
int i, j;
if( !(S.ch=(char*)realloc(S.ch,(S1.length+S2.length)*sizeof(char)))) exit(OVERFLOW);
for(i=0;i<S1.length;i++)
S.ch[i]=S1.ch[i];
for(j=0;j<S2.length;j++)
S.ch[j+i]=S2.ch[j];
S.length=S1.length+S2.length;
}
4.30⑤ 假设以定长顺序存储结构表示串,试设计
一个算法,求串s中出现的第一个最长重复子串及
其位置,并分析你的算法的时间复杂度。
要求实现以下函数:
void CommonStr(SString s, SString &sub, int &loc);
/* 求串s中出现的第一个最长重复子串sub及其位置loc */
定长顺序串SString的类型定义:
typedef unsigned char SString[MAXSTRLEN+1];
/* s[0] is the string's length */
void CommonStr(SString s, SString &sub, int &loc)
/* 求串s中出现的第一个最长重复子串sub及其位置loc */
{ int index=0,length=0,length1,i=0,j,k; while(i<s[0])
{
j=i+1;
while(j<=s[0])
{
if(s[i]==s[j])
{
length1=1;
for(k=1;s[i+k]==s[j+k];k++)
length1++;
if(length1>=length)
{
index=i;
length=length1;
}
j=j+length1;
}
else j++;
}
i++;
}
loc=index;
sub[0]=length;
}
第五章
5.21④ 假设稀疏矩阵A和B均以三元组表作为存储结构。
试写出矩阵相加的算法,另设三元组表C存放结果矩阵。
要求实现以下函数:
Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C);
/* 三元组表示的稀疏矩阵加法: C=A+B */
稀疏矩阵的三元组顺序表类型TSMatrix的定义:
#define MAXSIZE 20 // 非零元个数的最大值
typedef struct {
int i,j; // 行下标,列下标
ElemType e; // 非零元素值
}Triple;
typedef struct {
Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用
int mu,nu,tu; // 矩阵的行数、列数和非零元个数
}TSMatrix;
Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)
/* 三元组表示的稀疏矩阵加法: C=A+B */
{if( A.mu != B.mu || A.nu != B.nu )
return ERROR;
C.mu=A.mu;C.nu=A.nu;C.tu=0;
int pa=1;
int pb=1;
int pc=1;
ElemType ce;
int x;
for(x=1;x<=A.mu;x++)
{
while(A.data[pa].i<x) pa++;
while(B.data[pb].i<x) pb++;
while(A.data[pa].i==x&&B.data[pb].i==x)
{
if(A.data[pa].j==B.data[pb].j)
{
ce=A.data[pa].e+B.data[pb].e;
if(ce) //和不为0
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=ce;
pa++;pb++;pc++;
}
}//if
else if(A.data[pa].j>B.data[pb].j)
{
C.data[pc].i=x;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++;pc++;
}
else
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e;
pa++;pc++;
}
}//while
while(A.data[pa].i==x) //插入A中剩余的元素(第x行) {
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e;
pa++;pc++;
}
while(B.data[pb].i==x) //插入B中剩余的元素(第x行)
{
C.data[pc].i=x;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++;pc++;
}
}//for
C.tu=pc;
return OK;
}//TSMatrix_Add
{ int s=1,t=1,k=1;
while(s<A.tu&&t<B.tu)
if(A.data[s].i==B.data[t].i)
{
if(A.data[s].i<B.data[t].i)
{C.data[k].i=A.data[s].i;
C.data[k].j=A.data[s].j;
C.data[k].e=A.data[s].e;
k++;
s++;
}
else if(A.data[s].i>B.data[t].i) {C.data[k].i=B.data[t].i;
C.data[k].j=B.data[t].j;
C.data[k].e=B.data[t].e;
k++;
t++;
}
else
{
C.data[k].i=B.data[t].i;
C.data[k].j=B.data[t].j;
C.data[k].e=A.data[s].e+B.data[t].e; if(C.data[k].e!=0)
k++;
s++;
t++;
}
}
else if(A.data[s].i<B.data[t].i) {C.data[k].i=A.data[s].i;
C.data[k].j=A.data[s].j;
C.data[k].e=A.data[s].e; k++;
s++;
}
else
{C.data[k].i=B.data[t].i;
C.data[k].j=B.data[t].j;
C.data[k].e=B.data[t].e;
k++;
t++;
}
C.mu=A.mu;
C.nu=A.nu;
C.tu=k;
return 1;
}
*/
5.23② 三元组表的一种变型是,从三元组表中去掉行下标域得到二元组表,另设一个行起始向量,其每个分量是二元组表的一个下标值,指示该行中第一个非零元素在二元组表中的起始位置。试编写一个算法,由矩阵元素的下标值i,j求矩阵元素。试讨论这种方法和三元组表相比有什么优缺点。
要求实现以下函数:
Status GetElem(T2SMatrix M, int i, int j, ElemType &e);
/* 求二元组矩阵的元素A[i][j]的值e */
稀疏矩阵的二元组顺序表+行起始向量的类型T2SMatrix的定义:
typedef struct{
int j;
ElemType e;
}TwoTuples;
typedef struct{
TwoTuples data[MAXSIZE];
int cpot[MAXROW]; // 这个向量存储每一行在二元组中的起始位置
int mu,nu,tu;
} T2SMatrix; // 二元组矩阵类型
Status GetElem(T2SMatrix M, int i, int j, ElemType &e)
/* 求二元组矩阵的元素A[i][j]的值e */
{ int t;
if( i > M.mu || i < 0 || j > M.nu || j < 0 ) //i,j超出范围,0<i<M.mu,0<j<M.nu return ERROR;
for( t = M.cpot[i]; M.data[t].j != j&&t < M.cpot[i+1]; t++ );
if( t == M.cpot[i+1] )
e = 0;
else
e = M.data[t].e;
return OK;
}
/*
Status GetElem(T2SMatrix M, int i, int j, ElemType &e)
{
for(s=A.cpot[i];s<A.cpot[i+1]&&A.data[s].j!=j;s++);//注意查找范围
if(s<A.cpot[i+1]&&A.data[s].j==j) //找到了元素A[i][j]
{
e=A.data[s];
return OK;
}
return ERROR;
}
*/
5.26③ 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。
要求实现以下函数:
void OutCSM(CrossList M);
/* 以三元组格式输出十字链表表示的矩阵 */
稀疏矩阵的十字链表存储表示:
typedef struct OLNode {
int i,j; // 该非零元的行和列下标
ElemType e; // 非零元素值
OLNode *right,*down; // 该非零元所在行表和列表的后继链域
}OLNode, *OLink;
typedef struct {
OLink *rhead,*chead; // 行和列链表头指针向量基址
int mu,nu,tu; // 稀疏矩阵的行数、列数和非零元个数
}CrossList;
void OutCSM(CrossList M, void(*Out3)(int, int, int))
/* 用函数Out3,依次以三元组格式输出十字链表表示的矩阵 */
{ int i; OLink p;
for(i=0;i<=M.mu;i++)
{
if(M.rhead[i])
for(p=M.rhead[i];p;p=p->right)
Out3(i,p->j,p->e);
}
}
5.30③ 试按表头、表尾的分析方法重写求广义表
的深度的递归算法。
要求实现以下函数:
int GListDepth(GList ls);
/* Return the depth of list */
广义表类型GList的定义:
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
char atom;
struct {
GLNode *hp, *tp;
} ptr;
}un;
} *GList;
int GListDepth(GList ls)