第2章线性表习题解答

1第2章习题...............................................................................................................................1第2章习题2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？【解】//用线性表最后一个元素的下标last代替listLen实现顺序表#defineMAXLEN100typedefintelementType;typedefstructsllLast{elementTypedata[MAXLEN];intlast;}seqList;//初始化voidinitialList(seqList&S){S.last=-1;}//求表长度intlistLength(seqListS){returnS.last+1;}//按序号取元素boolgetElement(seqListS,inti,elementType&x){if(i1||iS.last+1)//i为元素编号，有效范围在1--S.last+1之间returnfalse;else{x=S.data[i-1];returntrue;}2}//查找元素x，成功：返回元素编号；失败：返回0intlistLocate(seqListS,elementTypex){inti;for(i=0;i=S.last;i++){if(S.data[i]==x)returni+1;//找到，转换为元素编号输出}return0;}//插入元素intlistInsert(seqList&S,elementTypex,inti){intk;if(S.lastMAXLEN-1)return0;//表满，返回0elseif(i1||iS.last+2)return1;//插入位置查处范围，返回1else{for(k=S.last;k=i-1;k--)S.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(i1||iS.last+1)return1;//删除元素编号超出范围，返回1else3{for(k=i;k=S.last;k++)S.data[k-1]=S.data[k];S.last--;return2;}}//7.打印表中所有元素voidprintList(seqListL){inti;for(i=0;i=L.last;i++)coutL.data[i]\t;//元素之间以制表符分割coutendl;}//8.交互输入数据元素--特殊输入结束voidlistInputC(seqList&L){if(L.last=0){cout顺序表已经存在，请先初始化，再输入元素。endl;return;}elementTypex;cout请输入数据元素(整数，-9999退出):endl;coutx=;cinx;while(x!=-9999){L.last++;L.data[L.last]=x;coutx=;cinx;}}4//随机数创建顺序表voidrndCList(seqList&L){inti;intn,m;L.last=-1;cout请输入要产生的随机数个数，n=;cinn;if(nMAXLEN-1){cout您要求产生的随机数个数超出了查找表长度MAXLEN-1，创建顺序表失败。endl;return;}cout请输入控制随机数大小参数，比如100以内数，请输入100，m=;cinm;srand((unsigned)time(NULL));//产生随机数种子//srand((unsigned)GetTickCount());//产生随机数种子for(i=0;in;i++)//随机数写入排序表A[]L.data[i]=rand()%m;L.last=n-1;//表长度为ncoutendl;}2.2试用顺序表表示较多位数的大整数，以便于这类数据的存储。请选择合适的存放次序，并分别写出这类大数的比较、加、减、乘、除等运算，并分析算法的时间性能。【解】顺序表0单元存放操作数的符号，区分操作数是正数还是负数；为方便处理运算时进位和借位，数据的低位存放数组低位，高位存放数组高位。【时间性能】加减法：O(max(m,n))乘除法：O(mn)2.3试用顺序表表示集合，并确定合适的约定，在此基础上编写算法以实现集合的交、并、差等运算，并分析各算法的时间性能。【解】//求C=A∩B5依次读取A的元素，检查次元素是否在B中，若在B中，则为交集元素，插入C中。voidinterSet(seqListA,seqListB,seqList&C){inti;for(i=0;iA.listLen;i++){if(listLocate(B,A.data[i])!=0)//A.data[i]在B中出现，是交集元素，插入C中listInsert(&C,A.data[i],C.listLen+1);}}//求C=A∪B现将A中元素全部插入C中。依次读取B中元素，检查是否出现在A中，若不在A中，则为并集元素，插入C中。voidmergeSet(seqListA,seqListB,seqList&C){inti;for(i=0;iA.listLen;i++)//A中元素全部插入C中{listInsert(&C,A.data[i],C.listLen+1);}for(i=0;iB.listLen;i++){if(listLocate(A,B.data[i])==0)//B.data[i]不在A中，插入ClistInsert(&C,B.data[i],C.listLen+1);}}//求C=A-B依次读取A中元素，检查是否在B中出现，若不在B中，则为差集元素，插入C中。voiddifferenceSet(seqListA,seqListB,seqList&C){inti;for(i=0;iA.listLen;i++){if(listLocate(B,A.data[i])==0)listInsert(&C,A.data[i],C.listLen+1);//A.data[i]不在B中，插入C}}6【算法分析】时间复杂度：O(|A||B|)2.4假设顺序表L中的元素递增有序，设计算法在顺序表中插入元素x，要求插入后仍保持其递增有序特性，并要求时间尽可能少。【解】如果表空间满，插入失败，返回-1；否则，从L最后一个元素开始，与x比较，若大于x，元素后移，直到L中元素小于或等于x，这个元素的后面的单元即为x的插入位置，插入成功返回插入位置。//空间满：返回值-1；正确插入：返回表中的插入位置intincInsert(seqList&L,elementTypex){inti=L.listLen-1;if(L.listLen==MAXLEN)return-1;//表空间已满，不能插入新的元素else{while(i=0&&L.data[i]x){L.data[i+1]=L.data[i];i--;}}L.data[i+1]=x;//插入xL.listLen++;//修改表长度returni+2;//成功插入，返回x在顺序表中的插入位置（元素编号）}【算法分析】时间复杂度：O(n)2.5假设顺序表L中的元素递增有序，设计算法在顺序表中插入元素x，并要求在插入后也没有相同的元素，即若表中存在相同的元素，则不执行插入操作。【解】与上题相似，只是在移动插入元素之前，检查L中是否已经存在值x，若存在，插入失败，返回-2。//空间满：返回值-1；x已经存在返回-2；正确插入：返回表中的插入位置intincInsert(seqList&L,elementTypex){inti;7if(L.listLen==MAXLEN)return-1;//表空间已满，不能插入新的元素else{for(i=0;iL.listLen;i++)if(L.data[i]==x)return-2;//元素x已经存在，插入失败，返回-2i=L.listLen-1;while(i=0&&L.data[i]x)//后移元素{L.data[i+1]=L.data[i];i--;}}L.data[i+1]=x;//插入xL.listLen++;//修改表长度returni+2;//成功插入，返回x在顺序表中的插入位置（元素编号）}2.6设计算法以删除顺序表中重复的元素，并分析算法的时间性能。【解】【分析】三重循环实现。第一层循环，从左往右依次取出L元素，用i指示；第二层循环，对i元素在L中循环查重，用下标j指示；第三重循环，删除重复元素。查重和删除从j=L.listLen-1开始，效率稍微好一点，因为这样重复元素本身不需重复移动。如果从i+1开始查重、删除，则j+1以后的重复元素会被移动。【算法描述】voidDeleteRepeatData(seqList&L){inti,j;if(L.listLen==0){cout当前顺序表空！endl;return;}if(L.listLen==1){cout当前顺序表只有一个元素！endl;8return;}i=0;while(iL.listLen-1){for(j=L.listLen-1;ji;j--)//从后往前删除，效率较高{if(L.data[i]==L.data[j])//元素重复，调用删除{listDelete(&L,j+1);//调用删除函数，下标差1，所以+1//以下部分代码是直接删除，没有调用删除函数//intk;//for(k=j;kL.listLen-1;k++)//L.data[k]=L.data[k+1];//L.listLen--;}}i++;}}【算法分析】时间性能：O(n3)2.7假设顺序表L中的元素按从小到大的次序排列，设计算法以删除表中重复的元素,并要求时间尽可能少。要求：（1）对顺序表（1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9）模拟执行本算法，并统计移动元素的次数。（2）分析算法的时间性能。【解】【分析】将元素分成两个部分：已经处理元素和待处理元素。已经处理部分返回L中，用下标i指示最后一个元素，初始化i=0。待处理部分用下标j指示第一个元素，初始化j=1.左边下标小于i的元素已经处理好重复，等于i是当前正在处理的元素，将data[i]与data[j]进行比较，会出现下列情况：①data[i]==data[j]，说明j指示的是i的重复元素，继续处理j的下一个元素，即执行j++。②data[i]data[j]，说明j指示元素与i的元素不同，如果i+1!=j，将j元素复制到i+1，即：L.data[i+1]=L.data[j]，再执行j++，i++；若i+1==j，说明j是i的直接后继，无需复制，直接执行i++，j++。循环执行上述操作，直到表尾。修改L的长度为i+1。【算法描述】9voidDeleteRepeatData(seqList&L){inti,j;//分别指向已处理部分最后元素和未处理部分第一个元素，皆为数组下标if(L.listLen2)return;//少于2个元素，直接退出i=0;//初始化i指向第一个元素j=1;//j指向第二个元素while(jL.listLen){if(L.data[i]==L.data[j])//j为重复元素，j后移j++;else//因为L递增，所以剩下情况即L.data[i]L.data[j]，j为目标元素{//如果j==i+1，说明j紧随i，无需移动元素，直接