第2章线性表习题解答.docx

第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;
}
}

//查找元素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
{
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<<L.data[i]<<"\t"; //元素之间以制表符分割
cout<<endl;
}

//8. 交互输入数据元素--特殊输入结束
void listInputC(seqList &L)
{
if(L.last>=0)
{
cout<<"顺序表已经存在，请先初始化，再输入元素。"<<endl;
return;
}

elementType x;

cout<<"请输入数据元素(整数，-9999退出):"<<endl;
cout<<"x=";
cin>>x;

while(x!=-9999)
{
L.last++;
L.data[L.last]=x;

cout<<"x=";
cin>>x;
}
}

//随机数创建顺序表
void rndCList(seqList &L)
{
int i;
int n,m;

L.last=-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;
L.last=n-1; //表长度为n
cout<<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中，插入C
listInsert(&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; //插入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;
if(L.listLen==MAXLEN)
return -1; //表空间已满，不能插入新的元素
else
{
for(i=0;i<L.listLen;i++)
if(L.data[i]==x)
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<<"当前顺序表空！"<<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中的元素按从小到大的次序排列，设计算法以删除表中重复的元素, 并要求时间尽可能少。要求：
（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。
【算法描述】
void DeleteRepeatData(seqList & L)
{
int i,j; //分别指向已处理部分最后元素和未处理部分第一个元素，皆为数组下标

if(L.listLen<2)
return; //少于2个元素，直接退出
i=0; //初始化i指向第一个元素
j=1; //j指向第二个元素
while(j<L.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，无需移动元素，直接i++、j++即可
if((i+1)!=j)
L.data[i+1]=L.data[j]; //j元素复制到i+1

i++; //无论那种情况，都需要同时后移i、j
j++;
}
}
L.listLen=i+1; //修改表的实际长度
}
【算法分析】时间复杂度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]，当前元素为非交集元素，只需移动ia，即ia++
(3) A.data[ia]>B.data[ib]，当前元素为非交集元素，只需移动ib，即ib++
重复以上过程，直至A、B中至少一个表结束。
修改A表长度为i+1。
【算法描述】
void InterSet(seqList &A, seqList &B)
{
int i=-1; //为了最后更新交集元素表长度操作一致，初始化为-1
int ia=0, ib=0; //A、B表当前元素的数组下标
while(ia<A.listLen && ib<B.listLen)
{
if(A.data[ia]==B.data[ib]) //ia和ib指示的是交集元素
{
if(ia!=i+1) //ia元素复制到i+1，否则ia位置即目标位置，不需复制元素
A.data[i+1]=A.data[ia];
i++;
ia++;
ib++;
}
else if(A.data[ia]<B.data[ib]) //以下为非交集元素处理
ia++;
else
ib++;
}
A.listLen=i+1; //更新A表长度，使等于交集元素个数。
}

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]<B.data[ib]，ia指示的元素不可能在B中出现，故比为A-B中元素。需要的话迁移到目标位置，即 (i+1)!=ia时，执行A.data[i+1]=A.data[ia]。若(i+1)==ia，ia即为目标位置，无需复制迁移。迁移完成，移动指示器：i++，ia++。
重复以上过程，直至A、B中至少一个表结束。
还有一种情况：B表已结束，但A表尚未结束，说明A剩下元素不在B中，全为A-B中元素，全部迁移到目标位置。
最后，修改A表长度为i+1。
【算法描述】
void SetSubtraction(seqList & A, seqList & B)
{
int i=-1; //指示A中已经处理的最后元素
int ia=0, ib=0; //指示A、B中，当前待处理的元素，初始指向第一个元素
while( ia<A.listLen && ib<B.listLen )
{
if(A.data[ia]==B.data[ib]) //非A-B中元素，ia、ib同时后移
{
ia++;
ib++;
}
else if(A.data[ia]>B.data[ib])
ib++; //此时，ia指示元素可能在B中ib指示的元素后面，移动ib。
else //此为，A.data[ia]<B.data[ib]，因为递增性，ia指示的元素不可能在B中。
{ //所以ia指示元素必在A-B中。
//如果(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<A.listLen)
{
if(i+1!=ia)
A.data[i+1]=A.data[ia];

i++; //A-B集合最后元素指示器后移
ia++; //A的指示器后移
}
A.listLen=i+1; //更新表A的长度，使等于|A-B|
}
【算法分析】时间性能 O(|A| + |B|)
【思考问题】A、B两表谁先结束？

下面是本题的另一种解法，因为用到A表中交集元素的删除，所以效率较差。
【算法描述-1】
void SetSubtraction1(seqList & A, seqList & B)
{
int ia=0, ib=0; //ia、ib指示A、B表中当前元素。初始指向第一个元素。
while(ia<A.listLen)
{
if(A.data[ia]<B.data[ib]) //元素不在B中，移动A到下一个元素
ia++;
else if(A.data[ia]>B.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