第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<tC(seqList &L)
{
if(L.last>=0)
{
cout<<"顺序表已经存在，请先初始化，再输入元素。"<i; j--) //从后往前删除，效率较高
{
if(L.data[i]==L.data[j]) //元素重复，调用删除
{
listDelete(&L,j+1); //调用删除函数，下标差1，所以+1
//以下部分代码是直接删除，没有调用删除函数
//int k;
//for(k=j; k2,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]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(jstLen=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]，当前元素为非交集元素，只需移动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]ata[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表尚未结束，说明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( iaa++;
ib++;
}
else if(A.data[ia]>B.data[ib])
ib++; //此时，ia指示元素可能在B中ib指示的元素后面，移动ib。
else //此为，A.data[ia]];

i++; //A-B集合最后元素指示器后移
ia++; //A的指示器后移
}
}
//处理B已经，A尚未结束情况，A中剩下部分元素全部为A-B元素
while(ia问题】A、B两表谁先结束？

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