1、 1第 2 章习题 .1第 2 章习题2.1 若将顺序表中记录其长度的分量 listlen 改为指向最后一个元素的位置 last，在实现各基本运算时需要做那些修改？【解】/用线性表最后一个元素的下标 last 代替 listLen 实现顺序表#define MAXLEN 100typedef int elementType;typedef struct sllLastelementType dataMAXLEN;int last;seqList;/初始化void initialList(seqList /求表长度int listLength(seqList S)return S.last+1;
2、/按序号取元素bool getElement(seqList S,int i,elementType elsex=S.datai-1;return true;2/查找元素 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
3、;/删除元素int listDelete(seqList if(S.last=-1)return 0; /空表，返回 0else if(iS.last+1)return 1; /删除元素编号超出范围，返回 1else3for(k=i;k=0)coutx;while(x!=-9999)L.last+;L.dataL.last=x;coutx;4/随机数创建顺序表void rndCList(seqList int n,m;L.last=-1;coutn;if(nMAXLEN-1)coutm; srand(unsigned)time(NULL); /产生随机数种子/srand(unsigned)Ge
4、tTickCount(); /产生随机数种子for(i=0;i=0 i-;L.datai+1=x; /插入 xL.listLen+; /修改表长度return i+2; /成功插入，返回 x 在顺序表中的插入位置（元素编号）【算法分析】时间复杂度：O(n)2.5 假设顺序表 L 中的元素递增有序，设计算法在顺序表中插入元素 x，并要求在插入后也没有相同的元素，即若表中存在相同的元素，则不执行插入操作。【解】与上题相似，只是在移动插入元素之前，检查 L 中是否已经存在值 x，若存在，插入失败，返回-2。/空间满：返回值-1；x 已经存在返回-2 ；正确插入：返回表中的插入位置7int incIn
5、sert(seqList if(L.listLen=MAXLEN)return -1; /表空间已满，不能插入新的元素else for(i=0;i=0 i-;L.datai+1=x; /插入 xL.listLen+; /修改表长度return i+2; /成功插入 ，返回 x 在顺序表中的插入位置（元素编号）2.6 设计算法以删除顺序表中重复的元素，并分析算法的时间性能。【解】【分析】三重循环实现。第一层循环，从左往右依次取出 L 元素，用 i 指示；第二层循环，对i 元素在 L 中循环查重，用下标 j 指示；第三重循环，删除重复元素。查重和删除从 j=L.listLen-1 开始，效率稍微好
6、一点，因为这样重复元素本身不需重复移动。如果从 i+1 开始查重、删除，则 j+1 以后的重复元素会被移动。【算法描述】void DeleteRepeatData(seqList if(L.listLen=0)couti; j-) /从后往前删除，效率较高if(L.datai=L.dataj) /元素重复，调用删除listDelete( /调用删除函数，下标差 1，所以+1/以下部分代码是直接删除，没有调用删除函数/int k;/for(k=j; kB.dataib，当前元素为非交集元素，只需移动 ib，即 ib+重复以上过程，直至 A、B 中至少一个表结束。修改 A 表长度为 i+1。【算法描述】void InterSet(seqList /为了最后更新交集元素表长度操作一致，初始化为-1int ia=0, ib=0; /A、B 表当前元素的数组下标while(iaB.dataib，ia 指示的元素可能在 B 表 ib 指示的元素后面，ia 不动，移动ib，即 ib+。(3) A.dataiaB.dataib，ia 指示的元素不可能在 B 中出现，故比为 A-B 中元素。需要
