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||i>L->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;l<L->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(i<j)
{
while(i<j && L->elem[i]!=item) i++;
while(i<j && L->elem[i]==item) j--;

if(i<j) { 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) //寻找开始删除的位置
{pre=p; p=p->next;}

while(p)
{
if(p->data > maxk)
break;
else
{
pre->next=p->next;
free(p);
p=pre->next;
}
}
}
T(n)=O(n);

2.9试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。
（1） 以一维数组作存储结构。
（2） 以单链表作存储结构。
(略)
(1)
void ReverseArray(ElemType a[],int n)
{
int i=0,j=n-1;
ElemType t;

while(i<j)
{ t=a[i]; a[i]=a[j]; a[j]=t;}
}

(2)
void ReverseList(LinkList L)
{
p=L->next;
L->next=NULL;
while(p!=NULL)
{
q=p->next;
p->next=L->next;
L->next=p;
p=q;
}
}

2.10已知一个带有表头结点的单链表,假设链表只给出了头指针L。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，至返回0。（提示：设置两个指针，步长为k）
int SearchNode(LinkList L,int k)
{
Node *p=L,*q;
int i=0;

while(i<k && p)
{i++; p=p->next; }

if(p==NULL) return 0; //不存在倒数第k个元素

q=L->next;
while(p->next!=NULL) //p到终点时，q所指结点为倒数第k个
{q=q->next; p=p->next;}

printf("%d",q->data);
return 1;
}

2.11把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间。（头插法）
LinkList ReverseMerge(LinkList *A, LinkList *B)
{ LinkList C;
Node *pa=A->next,*pb=B->next; //pa和pb分别指向A,B的当前元素
A->next=NULL; C=A;
while(pa!=NULL && pb!=NULL)
{
if(pa->data < pb->data) /*将pa的元素前插到pc表*/
{temp=pa->next; pa->next=C->next; C->next=pa; pa=temp;}
else
{ temp=pb->next; pb->next=C->next; C->next=pb; pb=temp;} /*将pb的元素前插到pc表*/
}

while(pb!=NULL)
{ temp=pa->next; pa->next=C->next; C->next=pa; pa=temp;} /*将剩余pa的元素前插到pc表*/

while(pb!=NULL)
{ temp=pb->next; pb->next=C->next; C->next=pb; pb=temp;} /*将剩余pb的元素前插到pc表*/

return hc;
}

2.12一单链表，以第一个元素为基准，将小于该元素的结点全部放到前面，大于该结点的元素全部放到后面。时间复杂度要求为O(n)，不能申请新空间。
void AdjustList(LinkList L)
{
Node *pFlag=L->next,*q=L->next->next,*temp=NULL;
pflag->next=NULL;

while(q!=NULL)
{
if(q->data < pFlag->data) //插到链表首端
{
temp=q->next; q->next=L->next;
L->next=q; q=temp;
}
Else //插到pFlag结点后面
{
temp=q->next; q->next=pFlag->next;
pFlag->next=q; q=temp;
}
}
}

2.13假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。
void DelPreNode(Node* s)
{
Node* p=s;

while(p->next->next!=s) p=p->next;

free(p->next);
p->next=s;
}
2.14已知由单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其他字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
//L为待拆分链表
//Lch为拆分后的字母链；Lnum为拆分后的数字链，Loth为拆分后的其他字符链
//Lch,Lnum,Loth均已被初始化为带头结点的单循环链表，采用头插法
void splitLinkList(LinkList L,LinkList Lch,LinkList Lnum,LinkList Loth)
{
Node *p=L->next;

while(p!=NULL)
{
if( (p->data >='a' && p->data<='z')|| (p->data >= 'A' && p->data<='Z'))
{temp=p->next; p->next=Lch->next; Lch->next=p; p= temp; }
else if(p->data >='0' && p->data<='9')
{temp=p->next; p->next=Lnum->next; Lnum->next=p; p= temp; }
else
{temp=p->next; p->next=Loth->next; Loth->next=p; p= temp; }
}
}

2.15设线性表A=(a1, a2,…,am)，B=(b1, b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：
C= (a1, b1,…,am, bm, bm+1, …,bn) 当m≤n时；
或者
C= (a1, b1,…,an, bn, an+1, …,am) 当m>n时。
线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。
//将A和B合并为C,C已经被初始化为空单链表
void MergeLinkList(LinkList A,LinkList B,LinkList C)
{
Node *pa=A->next，*pb=B->next,*pc=C;
int tag=1;

while(pa && pb)
{
if(tag)
{pc->next=pa->next; pc=pc->next; pa=pa->next; tag=1;}
else
{pc->next=pb->next; pc=pc->next; pb=pb->next; tag=0;}
}

if(pa) pc->next=pa->next;
else pc->next=pb->next; s
}

2.16将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。
//A为循环单链表，表示某多项式；将A拆分为B和C
//其中B只含奇次项，C只含偶次项；奇偶按照幂次区分
//B,C均已被初始化为带头结点的单链表

void SplitPolyList(PolyList A,PolyList B,PolyList C)
{
PolyNode *pa=A->next,*rb=B,*rc=C;

while(pa)
{
if(pa->exp%2==0) //偶次项
{rc->next=pa->next; rc=rc->next; pa=pa->next; }
else //奇次项
{rb->next=pa->next; rb=rb->next; pa=pa->next; }
}

rb->next=NULL; rc->next=NULL;
}

2.17建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。
void BinAdd(LinkList l) /*用带头结点的单链表L存储二进制数，实现加1运算*/
{
Node *q,*r, *s;
q=l->next;
r=l;
while(q!=NULL) /*查找最后一个值域为0的结点*/
{
if(q->data == 0)
r = q;
q = q->next;
}
if (r != l)
r->data = 1; /*将最后一个值域为0的结点的值域赋为1*/
else /*未找到值域为0的结点*/
{
s=(Node*)malloc(sizeof(Node)); /*申请新结点存放最高进位*/
s->data=1; /*值域赋为1*/
s->next=L->next;
L->next = s; /*插入到头结点之后*/
r = s;
}
r = r->next;
while(r!=NULL) /*将后面的所有结点的值域赋为0*/
{
r->data = 0;
r = r->next;
}
}

2.18多项式P(x)采用书中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。
double Compute(PolyList PL,double x)
{
double sum=0;
PolyNode *p=PL->next;

while(p)
{
sum=sum+p->coef*pow(x,p->exp);
p=p->next;
}

return sum;
}