第2章线性表习题解答

第2章习题 ............................................................................................................................... 1

第2章习题

2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？

【解】

//用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType;

typedef struct sllLast { elementType data[MAXLEN]; 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(i<1 || i>S.last+1) //i为元素编号，有效范围在1--S.last+1之间 return false; else { x=S.data[i-1]; return true; }

1

}

//查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=S.last;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; }

//插入元素

int listInsert(seqList &S,elementType x, int i) { int k; if(S.last>MAXLEN-1) return 0; //表满，返回0 else if(i<1 || i>S.last+2) return 1; //插入位置查处范围，返回1 else { for(k=S.last;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; S.last++; return 2; } }

//删除元素

int listDelete(seqList &S,int i) { int k; if(S.last==-1) return 0; //空表，返回0 else if(i<1 || i>S.last+1) return 1; //删除元素编号超出范围，返回1 else

2

{ for(k=i;k<=S.last;k++) S.data[k-1]=S.data[k]; S.last--; return 2; } }

//7. 打印表中所有元素 void printList(seqList L) { int i; for(i=0;i<=L.last;i++) cout<

//8. 交互输入数据元素--特殊输入结束 void listInputC(seqList &L) { if(L.last>=0) { cout<<\顺序表已经存在，请先初始化，再输入元素。\ return; } elementType x; cout<<\请输入数据元素(整数，-9999退出):\ cout<<\ cin>>x; while(x!=-9999) { L.last++; L.data[L.last]=x; cout<<\ cin>>x; } }

3

//随机数创建顺序表

void rndCList(seqList &L) { int i; int n,m; L.last=-1; cout<<\请输入要产生的随机数个数，n=\ cin>>n; if(n>MAXLEN-1) { cout<<\您要求产生的随机数个数超出了查找表长度\，创建顺序表失败。\

return; } cout<<\请输入控制随机数大小参数，比如100以内数，请输入100，m=\ cin>>m; srand((unsigned)time(NULL)); //产生随机数种子 //srand((unsigned)GetTickCount()); //产生随机数种子 for(i=0;i

L.last=n-1; //表长度为n cout<

2.2试用顺序表表示较多位数的大整数，以便于这类数据的存储。请选择合适的存放次序，并分别写出这类大数的比较、加、减、乘、除等运算，并分析算法的时间性能。

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

【时间性能】

加减法：O(max(m,n)) 乘除法：O(m?n)

2.3试用顺序表表示集合，并确定合适的约定，在此基础上编写算法以实现集合的交、并、差等运算，并分析各算法的时间性能。

【解】

//求C=A∩B

4

依次读取A的元素，检查次元素是否在B中，若在B中，则为交集元素，插入C中。 void interSet(seqList A, seqList B, seqList &C) { int i; for(i=0;i

//求C=A∪B

现将A中元素全部插入C中。依次读取B中元素，检查是否出现在A中，若不在A中，则为并集元素，插入C中。

void mergeSet(seqList A, seqList B, seqList &C) { int i; for(i=0;i

//求C=A-B

依次读取A中元素，检查是否在B中出现，若不在B中，则为差集元素，插入C中。 void differenceSet(seqList A,seqList B,seqList &C) { int i; for(i=0;i

5

【算法分析】

时间复杂度：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; //插入x L.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;

6

if(L.listLen==MAXLEN) return -1; //表空间已满，不能插入新的元素 else {

for(i=0;i

return -2; //元素x已经存在，插入失败，返回-2

i=L.listLen-1;

while(i>=0 && L.data[i]>x) //后移元素 { L.data[i+1]=L.data[i]; i--; } } L.data[i+1]=x; //插入x L.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<<\当前顺序表空！\ return; } if(L.listLen==1) { cout<<\当前顺序表只有一个元素！\

7

return; } i=0; while(ii; j--) //从后往前删除，效率较高 { if(L.data[i]==L.data[j]) //元素重复，调用删除 { listDelete(&L,j+1); //调用删除函数，下标差1，所以+1 //以下部分代码是直接删除，没有调用删除函数 //int k; //for(k=j; k

【算法分析】时间性能：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]

循环执行上述操作，直到表尾。 修改L的长度为i+1。 【算法描述】

8

void DeleteRepeatData(seqList & L) { int i,j; //分别指向已处理部分最后元素和未处理部分第一个元素，皆为数组下标 if(L.listLen<2) return; //少于2个元素，直接退出 i=0; //初始化i指向第一个元素 j=1; //j指向第二个元素 while(j

【算法分析】时间复杂度O(n)。上例中只需移动8个元素。

2.8若递增有序顺序表A、B分别表示一个集合，设计算法求解A=A?B，并分析其时间性能。

【解】 【分析】

审题：A、B为集合，说明两个表中都没有重复元素

A=A∩B，即要求交集元素就放在A表中，而不是创建一个新表来存放。 设置两个指针ia、ib分别指向A、B表当前处理的元素；

设置一个指针i指示已经求取的交集元素在A的表中的最后元素位置； 比较A、B表当前元素，会出现以下三种情况

(1) A.data[ia]==B.data[ib]，则ia或ib是交集元素，如果ia!=i+1，将ia元素复制到i+1,即：A.data[i+1]=A.data[ia]；否则，若ia==i+1，说明ia就在i的后面，无需复制元素。最后，无论那种情况，修改指针：ia++，ib++，i++

(2) A.data[ia]B.data[ib]，当前元素为非交集元素，只需移动ib，即ib++ 重复以上过程，直至A、B中至少一个表结束。

9

修改A表长度为i+1。 【算法描述】

void InterSet(seqList &A, seqList &B) { int i=-1; //为了最后更新交集元素表长度操作一致，初始化为-1 int ia=0, ib=0; //A、B表当前元素的数组下标 while(ia

2.9递增有序顺序表A、B分别表示一个集合，设计算法求解A=A－B，并分析其时间性能。

【解】【分析】

审题：A=A-B，即要求要利用A表的空间保存差集元素，而不是创建一个新表。 设置两个指针ia、ib分别指向A、B表当前处理的元素；

设置一个指针i指示已经求取的差集元素在A的表中的最后元素位置； 比较A、B表当前元素，会出现以下三种情况

(1) A.data[ia]==B.data[ib]，则ia或ib是交集元素，不是A-B中元素，直接跳过，修改指针：ia++，ib++。

(2) A.data[ia]>B.data[ib]，ia指示的元素可能在B表ib指示的元素后面，ia不动，移动ib，即ib++。

(3) A.data[ia]

重复以上过程，直至A、B中至少一个表结束。

还有一种情况：B表已结束，但A表尚未结束，说明A剩下元素不在B中，全为A-B中元素，全部迁移到目标位置。

10

最后，修改A表长度为i+1。 【算法描述】

void SetSubtraction(seqList & A, seqList & B) { int i=-1; //指示A中已经处理的最后元素 int ia=0, ib=0; //指示A、B中，当前待处理的元素，初始指向第一个元素 while( iaB.data[ib]) ib++; //此时，ia指示元素可能在B中ib指示的元素后面，移动ib。 else //此为，A.data[ia]

//如果(i+1)==ia，说明ia元素不需迁移位置，直接为A-B中元素

if(i+1!=ia) //(i+1!=ia)，需要将ia指示元素迁移到目标位置i+1 A.data[i+1]=A.data[ia]; i++; //A-B集合最后元素指示器后移 ia++; //A的指示器后移 } }

//处理B已经，A尚未结束情况，A中剩下部分元素全部为A-B元素 while(ia

【算法分析】时间性能 O(|A| + |B|) 【思考问题】A、B两表谁先结束？

下面是本题的另一种解法，因为用到A表中交集元素的删除，所以效率较差。 【算法描述-1】

11

void SetSubtraction1(seqList & A, seqList & B) { int ia=0, ib=0; //ia、ib指示A、B表中当前元素。初始指向第一个元素。 while(iaB.data[ib]) //A元素可能在B中，移动B到下一个元素 { ib++; if(ib>=B.listLen) break; } else //A.data[ia]==B.data[ib]，删除A中元素，同时移动指针 { listDelete(&A, ia+1); //ia++; 不能增加ia，因为A已经往前移动一个元素 ib++; if(ib>=B.listLen) break; } } }

【算法分析】时间性能 O(|A| + |B|)

12

本文来源：https://www.bwwdw.com/article/pepx.html