DS第二章-课后习题答案.doc
文本预览下载声明
第二章 线性表
2.1 填空题
(1)一半 插入或删除的位置
(2)静态 动态
(3)一定 不一定
(4)头指针 头结点的next 前一个元素的next
2.2 选择题
(1)A (2) DA GKHDA EL IAF IFA(IDA)
(3)D (4)D (5) D
2.3
头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址；
头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放；
首元素结点：第一个元素的结点。
2.4已知顺序表L递增有序，写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。
void InserList(SeqList *L,ElemType x)
{
int i=L-last;
if(L-last=MAXSIZE-1) return FALSE; //顺序表已满
while(i=0 L-elem[i]x)
{
L-elem[i+1]=L-elem[i];
i--;
}
L-elem[i+1]=x;
L-last++;
}
2.5 删除顺序表中从i开始的k个元素
int DelList(SeqList *L,int i,int k)
{
int j,l;
if(i=0||iL-last) {printf(The Initial Position is Error!); return 0;}
if(k=0) return 1; /*No Need to Delete*/
if(i+k-2=L-last) L-last=L-last-k; /*modify the length*/
for(j=i-1,l=i+k-1;lL-last;j++,l++)
L-elem[j]=L-elem[l];
L-last=L-last-k;
return 1;
}
2.6 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，删除线性表中所有值为item的数据元素。
[算法1]
void DeleteItem(SeqList *L,ElemType item)
{
int i=0,j=L-last;
while(ij)
{
while(ij L-elem[i]!=item) i++;
while(ij L-elem[i]==item) j--;
if(ij) { L-elem[i]=L-elem[j]; i++; j--;}
}
L-last=i-1;
}
[算法2]
void DeleteItem (SeqList *L,ElemType e)
{
int i,j;
i=j=0;
while(L-elem[i]!=e i=L-last)
i++;
j=i+1;
while(j=L-last)
{
while(L-elem[j]==e j=L-last)
j++;
if(j=L-last)
{
L-elem[i]=L-elem[j];
i++; j++;
}
}
L-last=i-1;
}
2.7 编写算法，在一非递减的顺序表L中，删除所有值相等的多余元素。要求时间复杂度为O(n)，空间复杂度为O(1)。
void DeleteRepeatItem(SeqList *L)
{
int i=0,j=1;
while(j=L-last)
{
if(L-elem[i]==L-elem[j])
j++;
else
{
L-elem[i+1]==L-elem[j];
i++; j++;
}
}
L-last=i;
}
2.8已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度。
void DelData(LinkList L,ElemType mink,ElemType maxk)
{
Node *p=L-next,*pre=L;
while(!p p-data = mink) //寻找开始删除
显示全部