第4章 串与数组 习题参考答案Word文件下载.docx
- 文档编号:4376767
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:19
- 大小:83.38KB
第4章 串与数组 习题参考答案Word文件下载.docx
《第4章 串与数组 习题参考答案Word文件下载.docx》由会员分享,可在线阅读,更多相关《第4章 串与数组 习题参考答案Word文件下载.docx(19页珍藏版)》请在冰点文库上搜索。
B.矩阵的非零元素个数和位置在操作过程中变化不大时较有效
C.是一种链式存储方法
D.比十字链表更高效
10.用十字链表表示一个稀疏矩阵,每个非零元素一般用一个含有(A)域的结点表示。
A.5B.4C.3D.2
二、填空题
1.一个串的任意连续字符组成的子序列称为串的子串,该串称为主串。
2.串长度为0的串称为空串,只包含空格的串称为空格串。
3.若两个串的长度相等且对应位置上的字符也相等,则称两个串相等。
4.寻找子串在主串中的位置,称为模式匹配。
其中,子串又称为模式串。
5.模式串t="
ababaab"
的next[]数组值为-1001231,nextval[]数组值为-10-10-130。
6.设数组A[1..5,1..6]的基地址为1000,每个元素占5个存储单元,若以行序为主序顺序存储,则元素A[5,5]的存储地址为1140。
7.在稀疏矩阵的三元组顺序表存储结构中,除表示非零元的三元组表以外,还需要表示矩阵的行数、列数和非零元个数。
8.一个n×
n的对称矩阵,如果以相同的元素只存储一次的原则进行压缩存储,则其元素压缩后所需的存储容量为n(n+1)/2。
9.对矩阵压缩的目的是为了节省存储空间。
10.稀疏矩阵一般采用的压缩存储方法有两种,即三元组和十字链表。
三、算法设计题
1.编写基于SeqString类的成员函数count(),统计当前字符串中的单词个数。
参考答案:
publicintcount(){
intwordcount=0;
//单词个数
charcurrChar,preChar;
for(inti=1;
i<
this.length();
i++){
currChar=this.charAt(i);
//当前字符
preChar=this.charAt(i-1);
//前一个字符
if(((int)(currChar)<
65||(int)(currChar)>
122
//当前字符不是字母
||((int)(preChar)>
90&
&
(int)(preChar)<
97))
&
(((int)(preChar)>
=65&
=90)
//当前字符的前一个字符是字母
=97&
=122))){
wordcount++;
}
returnwordcount;
}
2.编写基于SeqString类的成员函数replace(begin,s1,s2)。
要求在当前对象串中,从下标begin开始,将所有的s1子串替换为s2串。
//beginint开始位置;
s1String原始字符串;
s2String目标字符串;
publicSeqStringreplace(intbegin,SeqStrings1,SeqStrings2){
if(s1==null||s2==null){
returnnull;
SeqStringss=newSeqString("
"
);
//产生空串
SeqStringsource=this;
intindex=-1;
while((index=source.indexOf(s1,begin))!
=-1){
ss.concat(source.substring(0,index));
//串连接
ss.concat(s2);
source=(SeqString)source.substring(index+s1.length());
//取子串
ss.concat(source);
returnss;
3.编写基于SeqString类的成员函数reverse()。
要求将当前对象中的字符反序存放。
publicSeqStringreverse(){
for(inti=0,j=this.length()-1;
j;
i++,j--){
chartemp=this.charAt(i);
setCharAt(i,this.charAt(j));
setCharAt(j,temp);
returnthis;
4.编写基于SeqString类的成员函数deleteallchar(ch)。
要求从当前对象串中删除其值等于ch的所有字符。
publicSeqStringdeleteAllChar(charch){
SeqStrings1=newSeqString(String.valueOf(ch));
if(s1==null){
//当前串赋值到sourse
while((index=source.indexOf(s1,0))!
source=(SeqString)source.substring(index+1);
5.编写基于SeqString类的成员函数stringcount(str)。
要求统计子串str在当前对象串中出现的次数,若不出现则返回0。
publicintstringCount(SeqStringstr){
SeqStringsource=this.curstr;
intcount=0,begin=0;
intindex;
while((index=source.indexOf(str,begin))!
count++;
begin=index+str.length();
returncount;
6.鞍点是指矩阵中的元素aij是第i行中值最小的元素,同时又是第j列中值最大的元素。
试设计一个算法求矩阵A的所有鞍点。
//存放矩阵中鞍点的类
classResult{
TripleNodedata[];
//三元组表,存放鞍点的行、列、值
intnums;
//鞍点个数
publicResult(intmaxSize){//构造方法
data=newTripleNode[maxSize];
//为顺序表分配maxSize个存储单元
for(inti=0;
data.length;
data[i]=newTripleNode();
}
nums=0;
//返回矩阵中的所有鞍点
publicResultallSaddlePoint(int[][]ar){
inti,j,flag,m,n;
Resultre=newResult(ar.length);
for(i=0;
ar.length;
m=i;
n=0;
flag=1;
//假设当前结点是鞍点
for(j=0;
j<
ar[i].length;
j++){
if(ar[i][j]<
ar[m][n]){
n=j;
if(ar[j][n]>
flag=0;
//不是鞍点
if(flag==1){//是鞍点,将其加入
re.data[re.nums]=newTripleNode(m,n,ar[m][n]);
re.nums++;
returnre;
7.设计算法,求出二维数组A[n,n]的两条对角线元素之和
publicstaticintsumOfDiagonal(int[][]a){
inti,n=a[0].length,sum1=0,sum2=0,sum;
a.length;
sum1+=a[i][i];
//主对角线之和
sum2+=a[i][n-i-1];
//副对角线之和
sum=sum1+sum2;
if(n%2==1){//若矩阵行数为奇数,则减去两条对角线相交的元素。
sum-=a[n/2][n/2];
returnsum;
四、上机实践题
1.在顺序串类SeqString中增加一个主函数,测试各成员函数的正确性。
packagech04Exercise;
importch04.SeqString;
publicclassExercise4_4_1extendsSeqString{
publicstaticvoidmain(Stringargs[]){
char[]chararray={'
W'
'
o'
r'
l'
d'
};
SeqStrings1=newSeqString();
//构造一个空串
SeqStrings2=newSeqString("
Hello"
//以字符串常量构造串对象
SeqStrings3=newSeqString(chararray);
//以字符数组构造串对象
System.out.println("
串s1="
+s1+"
s2="
+s2+"
s3="
+s3);
s1.insert(0,s2);
串s1在第0个字符前插入串s2后,s1="
+s1);
s1.insert(1,s3);
串s1在第1个字符前插入串s3后,s1="
s1.delete(1,4);
串s1删除第1到第3个字符后,s1="
串s1中从第2到第5个字符组成的子串是:
+s1.substring(2,6));
运行结果:
2.已知两个稀疏矩阵A和B,试基于三元组顺序表或十字链表的存储结构,编程实现A+B的运算。
packagech04Exercise;
importch04.SparseMatrix;
publicclassExercise4_4_2{
publicstaticSparseMatrixaddSMatrix(SparseMatrixa,SparseMatrixb){
//计算两个三元组表示的稀疏矩阵之和
if(a.getRows()!
=b.getRows()||a.getCols()!
=b.getCols()){
这两个矩阵不能相加"
SparseMatrixc=newSparseMatrix(a.getNums()+b.getNums());
inti=0,j=0,k=0;
intlen=0;
while(i<
a.getNums()&
b.getNums()){
if(a.getData()[i].getRow()<
b.getData()[j].getRow()){//A行<
B行
c.getData()[k].setColumn(a.getData()[i].getColumn());
c.getData()[k].setRow(a.getData()[i].getRow());
c.getData()[k].setValue(a.getData()[i].getValue());
c.setNums(++k);
i++;
}elseif(a.getData()[i].getRow()==b.getData()[j].getRow()){//A行号=B行号
if(a.getData()[i].getColumn()==b.getData()[j].getColumn()){//A列=B列
if(a.getData()[i].getValue()+b.getData()[j].getValue()!
=0){
c.getData()[k].setValue(a.getData()[i].getValue()+b.getData()[j].getValue());
//设置元素个数
j++;
}elseif(a.getData()[i].getColumn()<
b.getData()[j].getColumn()){//A列<
B列
}elseif(a.getData()[i].getColumn()>
b.getData()[j].getColumn()){//A列>
c.getData()[k].setColumn(b.getData()[j].getColumn());
c.getData()[k].setRow(b.getData()[j].getRow());
c.getData()[k].setValue(b.getData()[j].getValue());
}elseif(a.getData()[i].getRow()>
b.getData()[j].getRow()){//A行>
a.getNums()){//将A,B中的剩余非零元复制过去
while(j<
returnc;
publicstaticvoidmain(String[]args){
intmatrixA[][]={{3,0,0,7},{0,0,-1,0},{2,0,0,0},{0,0,0,0},{0,0,0,-8}};
intmatrixB[][]={{-3,0,0,0},{1,0,0,0},{3,0,0,0},{0,2,0,0},{0,0,0,0}};
SparseMatrixtsm1=newSparseMatrix(matrixA);
SparseMatrixtsm2=newSparseMatrix(matrixB);
矩阵A:
tsm1.printMatrix();
矩阵B:
tsm2.printMatrix();
SparseMatrixmatrixSum=addSMatrix(tsm1,tsm2);
矩阵A+矩阵B:
matrixSum.printMatrix();
3.基于十字链表类CrossList,设计插入非零元素结点的成员函数insert(row,col,val),并编程测试。
参考答案:
importch04.CrossList;
importch04.OLNode;
publicclassExercise4_4_3extendsCrossList{
publicExercise4_4_3(introw,intcol)
{
super(row,col);
@Override
publicvoidInsert(introw,intcol,inte){//插入元素
OLNodertemp=getRhead()[row-1];
OLNodectemp=getChead()[col-1];
OLNodeoldtemp=null;
OLNodecurrent=newOLNode(row,col,e);
if(rtemp.getRight()==null){
rtemp.setRight(current);
}else{
while(rtemp.getRight()!
=null){
oldtemp=rtemp;
rtemp=rtemp.getRight();
if(rtemp.getCol()>
col){
current.setRight(oldtemp.getRight());
oldtemp.setRight(current);
break;
}else//当前位置存在元素
if(rtemp.getCol()==col){
本位置存在元素"
return;
}elseif(rtemp.getRight()==null){
rtemp.setRight(current);
if(ctemp.getDown()==null){
ctemp.setDown(current);
this.setTu(this.getTu()+1);
while(ctemp.getDown()!
oldtemp=ctemp;
ctemp=ctemp.getDown();
if(ctemp.getRow()>
row){
current.setDown(oldtemp.getDown());
oldtemp.setDown(current);
if(ctemp.getRow()==row){
r
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第4章 串与数组 习题参考答案 数组 习题 参考答案