资源预览内容
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
第9页 / 共19页
第10页 / 共19页
亲,该文档总共19页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第2章习题1第2章习题2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last,在实现各基本运算时需要做那些修改?【解】/用线性表最后一个元素的下标last代替listLen实现顺序表#define MAXLEN 100typedef int elementType;typedef struct sllLastelementType dataMAXLEN;int last;seqList;/初始化void initialList(seqList &S)S.last=-1;/求表长度int listLength(seqList S)return S.last+1;/按序号取元素bool getElement(seqList S,int i,elementType &x) if(iS.last+1) /i为元素编号,有效范围在1-S.last+1之间return false;elsex=S.datai-1;return true;/查找元素x,成功:返回元素编号;失败:返回0int listLocate(seqList S,elementType x)int i;for(i=0;iMAXLEN-1)return 0; /表满,返回0else if(iS.last+2)return 1; /插入位置查处范围,返回1elsefor(k=S.last;k=i-1;k-)S.datak+1=S.datak;S.datai-1=x;S.last+;return 2;/删除元素int listDelete(seqList &S,int i)int k;if(S.last=-1)return 0; /空表,返回0else if(iS.last+1)return 1; /删除元素编号超出范围,返回1elsefor(k=i;k=S.last;k+)S.datak-1=S.datak;S.last-;return 2;/7. 打印表中所有元素void printList(seqList L)int i;for(i=0;i=L.last;i+)coutL.datait; /元素之间以制表符分割cout=0)cout顺序表已经存在,请先初始化,再输入元素。endl;return;elementType x;cout请输入数据元素(整数,-9999退出):endl;coutx;while(x!=-9999)L.last+;L.dataL.last=x;coutx;/随机数创建顺序表void rndCList(seqList &L)int i;int n,m;L.last=-1;coutn;if(nMAXLEN-1)cout您要求产生的随机数个数超出了查找表长度MAXLEN-1,创建顺序表失败。endl;return;coutm; srand(unsigned)time(NULL);/产生随机数种子/srand(unsigned)GetTickCount();/产生随机数种子for(i=0;in;i+) /随机数写入排序表AL.datai=rand()%m; L.last=n-1; /表长度为ncoutendl;2.2试用顺序表表示较多位数的大整数,以便于这类数据的存储。请选择合适的存放次序,并分别写出这类大数的比较、加、减、乘、除等运算,并分析算法的时间性能。【解】顺序表0单元存放操作数的符号,区分操作数是正数还是负数;为方便处理运算时进位和借位,数据的低位存放数组低位,高位存放数组高位。【时间性能】加减法:O(max(m,n)乘除法:O(mn)2.3试用顺序表表示集合,并确定合适的约定,在此基础上编写算法以实现集合的交、并、差等运算,并分析各算法的时间性能。【解】/求C=AB依次读取A的元素,检查次元素是否在B中,若在B中,则为交集元素,插入C中。void interSet(seqList A, seqList B, seqList &C)int i;for(i=0;iA.listLen;i+)if(listLocate(B,A.datai)!=0) /A.datai在B中出现,是交集元素,插入C中listInsert(&C,A.datai,C.listLen+1);/求C=AB现将A中元素全部插入C中。依次读取B中元素,检查是否出现在A中,若不在A中,则为并集元素,插入C中。void mergeSet(seqList A, seqList B, seqList &C)int i;for(i=0;iA.listLen;i+) /A中元素全部插入C中listInsert(&C,A.datai,C.listLen+1); for(i=0;iB.listLen;i+)if(listLocate(A,B.datai)=0) /B.datai不在A中,插入ClistInsert(&C,B.datai,C.listLen+1);/求C=A-B依次读取A中元素,检查是否在B中出现,若不在B中,则为差集元素,插入C中。void differenceSet(seqList A,seqList B,seqList &C)int i;for(i=0;i=0 & L.dataix)L.datai+1=L.datai;i-;L.datai+1=x; /插入xL.listLen+; /修改表长度return i+2; /成功插入,返回x在顺序表中的插入位置(元素编号)【算法分析】时间复杂度:O(n)2.5假设顺序表L中的元素递增有序,设计算法在顺序表中插入元素x,并要求在插入后也没有相同的元素,即若表中存在相同的元素,则不执行插入操作。【解】与上题相似,只是在移动插入元素之前,检查L中是否已经存在值x,若存在,插入失败,返回-2。/空间满:返回值-1;x已经存在返回-2;正确插入:返回表中的插入位置int incInsert(seqList &L,elementType x)int i;if(L.listLen=MAXLEN)return -1; /表空间已满,不能插入新的元素else for(i=0;i=0 & L.dataix) /后移元素L.datai+1=L.datai;i-;L.datai+1=x; /插入xL.listLen+; /修改表长度return i+2; /成功插入,返回x在顺序表中的插入位置(元素编号)2.6设计算法以删除顺序表中重复的元素,并分析算法的时间性能。【解】【分析】三重循环实现。第一层循环,从左往右依次取出L元素,用i指示;第二层循环,对i元素在L中循环查重,用下标j指示;第三重循环,删除重复元素。查重和删除从j=L.listLen-1开始,效率稍微好一点,因为这样重复元素本身不需重复移动。如果从i+1开始查重、删除,则j+1以后的重复元素会被移动。【算法描述】void DeleteRepeatData(seqList & L)int i,j;if(L.listLen=0)cout当前顺序表空!endl;return;if(L.listLen=1)cout当前顺序表只有一个元素!endl;return;i=0;while(iL.listLen-1)f
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号