第2章线性表习题解答.doc

《第2章线性表习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、..第2章习题1第2章习题2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？【解】//用线性表最后一个元素的下标last代替listLen实现顺序表#defineMAXLEN100typedefintelementType;typedefstructsllLast{elementTypedata[MAXLEN];intlast;}seqList;//初始化voidinitialList(seqList&S){S.last=-1;}

2、//求表长度intlistLength(seqListS){returnS.last+1;}//按序号取元素boolgetElement(seqListS,inti,elementType&x){if(i<1

3、

4、i>S.last+1)//i为元素编号，有效范围在1--S.last+1之间returnfalse;else{x=S.data[i-1];returntrue;}..下载可编辑....}//查找元素x，成功：返回元素编号；失败：返回0intlistLocate(seqListS,eleme

5、ntTypex){inti;for(i=0;i<=S.last;i++){if(S.data[i]==x)returni+1;//找到，转换为元素编号输出}return0;}//插入元素intlistInsert(seqList&S,elementTypex,inti){intk;if(S.last>MAXLEN-1)return0;//表满，返回0elseif(i<1

6、

7、i>S.last+2)return1;//插入位置查处范围，返回1else{for(k=S.last;k>=i-1;k--)S

8、.data[k+1]=S.data[k];S.data[i-1]=x;S.last++;return2;}}//删除元素intlistDelete(seqList&S,inti){intk;if(S.last==-1)return0;//空表，返回0elseif(i<1

9、

10、i>S.last+1)return1;//删除元素编号超出范围，返回1else..下载可编辑....{for(k=i;k<=S.last;k++)S.data[k-1]=S.data[k];S.last--;return2;}}

11、//7.打印表中所有元素voidprintList(seqListL){inti;for(i=0;i<=L.last;i++)cout<=0){cout<<"顺序表已经存在，请先初始化，再输入元素。"<

12、:"<>x;while(x!=-9999){L.last++;L.data[L.last]=x;cout<<"x=";cin>>x;}}..下载可编辑....//随机数创建顺序表voidrndCList(seqList&L){inti;intn,m;L.last=-1;cout<<"请输入要产生的随机数个数，n=";cin>>n;if(n>MAXLEN-1){cout<<"您要求产生的随机数个数超出了查找表长度"<

13、"<>m;srand((unsigned)time(NULL));//产生随机数种子//srand((unsigned)GetTickCount());//产生随机数种子for(i=0;i

14、请选择合适的存放次序，并分别写出这类大数的比较、加、减、乘、除等运算，并分析算法的时间性能。【解】顺序表0单元存放操作数的符号，区分操作数是正数还是负数；为方便处理运算时进位和借位，数据的低位存放数组低位，高位存放数组高位。【时间性能】加减法：O(max(m,n))乘除法：O(m´n)2.3试用顺序表表示集合，并确定合适的约定，在此基础上编写算法以实现集合的交、并、差等运算，并分析各算法的时间性能。【解】//求C=A∩B..下载可编辑....依次读取A的元素，检查次元素是否在B中，