DS第二章课后习题答案

第二章线性表。

2.1填空题。

1)一半插入或删除的位置(2)静态动态(3)一定不一定。

4)头指针头结点的next前一个元素的next

2.2选择题。

1)a(2) dagkhdaeliafifa(ida)(3)d(4)d(5)d2.3

头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址；

头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放；首元素结点：第一个元素的结点。

2.4已知顺序表l递增有序，写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性。

void inserlist(seqlist *l,elemtype x)

l->elem[i+1]=x;l->last++;

2.5删除顺序表中从i开始的k个元素int dellist(seqlist *l,int i,int k)

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;llast;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)}

l->last=i-1;}

算法2]voiddeleteitem (seqlist *l,elemtype e)}l->last=i-1;}

2.7编写算法，在一非递减的顺序表l中，删除所有值相等的多余元素。要求时间复杂度为o(n)，空间复杂度为o(1)。

void deleterepeatitem(seqlist *l)}

l->last=i;}

2.8已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度。

void deldata(linklist l,elemtype mink,elemtype maxk)while(p)}}

t(n)=o(n);

2.9试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...an）逆置为（an, an-1,..

a1）。（1）以一维数组作存储结构。（2）以单链表作存储结构。

(略)(1)

void reversearray(elemtype a,int n)}

2.10已知一个带有表头结点的单链表，假设链表只给出了头指针l。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。

若查找成功，算法输出该结点的data域的值，并返回1；否则，至返回0。（提示：设置两个指针，步长为k）

int searchnode(linklist l,int k)

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

q=l->next;

while(p->next!=null) /p到终点时，q所指结点为倒数第k个。

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

2.11把元素递增排列的链表a和b合并为c,且c中元素递减排列，使用原空间。（头插法）linklist reversemerge(linklist *a, linklist *b)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)

else//插到pflag结点后面}}

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

void delprenode(node* s)

2.14已知由单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其他字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。//l为待拆分链表。

/lch为拆分后的字母链；lnum为拆分后的数字链，loth为拆分后的其他字符链//lch,lnum,loth均已被初始化为带头结点的单循环链表，采用头插法void splitlinklist(linklist l,linklist lch,linklist lnum,linklist loth)

else if(p->data >=0' &p->data<='9')else}}

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)else}if(pa)pc->next=pa->next;elsepc->next=pb->next;s}

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

void splitpolylist(polylist a,polylist b,polylist c)else//奇次项}rb->next=null; rc->next=null;}

2.17建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。

void binadd(linklistl)/*用带头结点的单链表l存储二进制数，实现加1运算*/if(r !=l)r->data = 1;/*将最后一个值域为0的结点的值域赋为1*/else/*未找到值域为0的结点*/

r = r->next;while(r!=null)/*将后面的所有结点的值域赋为0*/}

2.18多项式p(x)采用书中所述链接方法存储。写一算法，对给定的x值，求p(x)的值。double compute(polylist pl,double x)

return sum;}

DS第二章课后习题答案

第二章课后习题答案

第二章课后习题答案

第二章课后习题答案

其他用户还读了