当前位置:文档之家› 第2章线性表习题解答

第2章线性表习题解答

第2章线性表习题解答第2章习题 (2)第2章习题2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last,在实现各基本运算时需要做那些修改?【解】//用线性表最后一个元素的下标last代替listLen实现顺序表#define MAXLEN 100typedef int elementType;typedef struct sllLast{elementType data[MAXLEN];int last;}seqList;//初始化void initialList(seqList &S){st=-1;}//求表长度int listLength(seqList S){return st+1;}//按序号取元素bool getElement(seqList S,int i,elementType &x){if(i<1 || i>st+1) //i为元素编号,有效范围在st+1之间return false;else{x=S.data[i-1];return true;}}//查找元素x,成功:返回元素编号;失败:返回0int listLocate(seqList S,elementType x){int i;for(i=0;i<=st;i++){if(S.data[i]==x)return i+1; //找到,转换为元素编号输出}return 0;}//插入元素int listInsert(seqList &S,elementType x, int i){int k;if(st>MAXLEN-1)return 0; //表满,返回0else if(i<1 || i>st+2)return 1; //插入位置查处范围,返回1 else{for(k=st;k>=i-1;k--)S.data[k+1]=S.data[k];S.data[i-1]=x;st++;return 2;}}//删除元素int listDelete(seqList &S,int i){int k;if(st==-1)return 0; //空表,返回0else if(i<1 || i>st+1)return 1; //删除元素编号超出范围,返回1else{for(k=i;k<=st;k++)S.data[k-1]=S.data[k];st--;return 2;}}//7. 打印表中所有元素void printList(seqList L){int i;for(i=0;i<=st;i++)cout<<L.data[i]<<"\t"; //元素之间以制表符分割cout<<endl;}//8. 交互输入数据元素--特殊输入结束void listInputC(seqList &L){if(st>=0){cout<<"顺序表已经存在,请先初始化,再输入元素。

"<<endl;return;}elementType x;cout<<"请输入数据元素(整数,-9999退出):"<<endl;cout<<"x=";cin>>x;while(x!=-9999){st++;L.data[st]=x;cout<<"x=";cin>>x;}}//随机数创建顺序表void rndCList(seqList &L){int i;int n,m;st=-1;cout<<"请输入要产生的随机数个数,n="; cin>>n;if(n>MAXLEN-1){cout<<"您要求产生的随机数个数超出了查找表长度"<<MAXLEN-1<<",创建顺序表失败。

"<<endl;return;}cout<<"请输入控制随机数大小参数,比如100以内数,请输入100,m=";cin>>m;srand((unsigned)time(NULL)); //产生随机数种子//srand((unsigned)GetTickCount()); //产生随机数种子for(i=0;i<n;i++) //随机数写入排序表A[]L.data[i]=rand()%m;st=n-1; //表长度为ncout<<endl;}2.2试用顺序表表示较多位数的大整数,以便于这类数据的存储。

请选择合适的存放次序,并分别写出这类大数的比较、加、减、乘、除等运算,并分析算法的时间性能。

【解】顺序表0单元存放操作数的符号,区分操作数是正数还是负数;为方便处理运算时进位和借位,数据的低位存放数组低位,高位存放数组高位。

【时间性能】加减法:O(max(m,n))乘除法:O(m n)2.3试用顺序表表示集合,并确定合适的约定,在此基础上编写算法以实现集合的交、并、差等运算,并分析各算法的时间性能。

【解】//求C=A∩B依次读取A的元素,检查次元素是否在B中,若在B中,则为交集元素,插入C中。

void interSet(seqList A, seqList B, seqList &C){int i;for(i=0;i<A.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中。

void mergeSet(seqList A, seqList B, seqList &C){int i;for(i=0;i<A.listLen;i++) //A中元素全部插入C中{listInsert(&C,A.data[i],C.listLen+1);}for(i=0;i<B.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中。

void differenceSet(seqList A,seqList B,seqList &C){int i;for(i=0;i<A.listLen;i++){if(listLocate(B,A.data[i])==0)listInsert(&C,A.data[i],C.listLen+1); //A.data[i]不在B中,插入C}}【算法分析】时间复杂度:O( |A| |B| )2.4假设顺序表L中的元素递增有序,设计算法在顺序表中插入元素x,要求插入后仍保持其递增有序特性,并要求时间尽可能少。

【解】如果表空间满,插入失败,返回-1;否则,从L最后一个元素开始,与x比较,若大于x,元素后移,直到L中元素小于或等于x,这个元素的后面的单元即为x的插入位置,插入成功返回插入位置。

//空间满:返回值-1;正确插入:返回表中的插入位置int incInsert(seqList &L,elementType x){int i=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++; //修改表长度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<L.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++; //修改表长度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(i<L.listLen-1){for(j=L.listLen-1; j>i; j--) //从后往前删除,效率较高{if(L.data[i]==L.data[j]) //元素重复,调用删除{listDelete(&L,j+1); //调用删除函数,下标差1,所以+1//以下部分代码是直接删除,没有调用删除函数//int k;//for(k=j; k<L.listLen-1; k++)// L.data[k]=L.data[k+1];//L.listLen--;}}i++;}}【算法分析】时间性能:O(n3)2.7假设顺序表L中的元素按从小到大的次序排列,设计算法以删除表中重复的元素, 并要求时间尽可能少。

相关主题