数据结构实用教程(第三版)课后答案.pdf

《数据结构实用教程(第三版)课后答案.pdf》由会员分享，可在线阅读，更多相关《数据结构实用教程(第三版)课后答案.pdf（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实用教程（第三版）课后答案f i l e:/D|/-一上架商品一 一/数据结构实用教程（第三版）课 后 答 案（徐孝凯著）清华大学/第一章绪论.t xt第一章绪习题一一、单选题1 .一个数组元数2 订与（A ）的表示等价。A *（a+i）B a+i C*a+i D&a+i2 .对于两个函数，若函数名相同，但只是（C）不同则不是重载函数。A参数类型 B 参数个数 C 函数类型3.若需要利用形参直接访问实参，则应把形参变量说明为（B）参数。A指针 B 引用 C 值4 .下面程序段的复杂度为（C）。f or（i n t i=0；i m；i+）f or（i n t j=0；j n；j+）a i

2、 j =i*j;A 0（m 2）B 0（n 2）C 0（m*n）D 0（m+n）5 .执行下面程序段时，执行S语句的次数为（D）。f or（i n t i=l；i =n；i+）f or（i n t j=l；j =i；j+）S；A n 2 B n 2/2 C n（n+l）D n（n+l）/26 .下面算法的时间复杂度为（B）。i n t f（u n s i g n e d i n t n）i f （n=0|n l）r e t u r n 1；El s e r e t u r n n*f（n-1）；）A 0（1）B 0（n）C 0（n 2）D 0（n!）二、填空题L数据的逻辑结构被除数分为集合结构

3、、线性结构、树 型 结 构 和 图 形 结 构 四 种。2 .数据的存储结构被分为顺序结构、结 构、索引结构和散列结构四种。3.在线性结构、树型结构和图形结构中，前驱和后继结点之间分别存在着1 对 1、1 对 N和M对 N的关系。4 .一种抽象数据类型包括数据和操作两个部分。5 .当一个形参类型的长度较大时，应最好说明为引用，以节省参数值的传输时间和存储参数的空间。6 .当需要用一个形参访问对应的实参时，则该形参应说明为引用。7.在函数中对引用形参的修改就是对相应实参的修改，对 值（或赋值）形参的修改只局限在该函数的部，不会反映到对应的实参上。f i l e：/D|/-上架商品-.教 程（第二

4、版）课 后 答 案（徐孝凯著）清华大学/第一章绪论.t xt （第 1/1 0 页）2 0 1 0-3-1 6 2 2:0 6:1 7f i l e：/D|/-上架商品-/数据结构实用教程(第二版)课后答案(徐孝凯著)清华大学/第一章绪论.t xt8.当需要进行标准I/O 操作时，则应在程序文件中包含i os t r e a m.h 头文件，当需要进行文件 I/O 操作时，则应在程序文件中包含f s t r e a m.h头文件。9 .在包含有s t d l i b.h头文件的程序文件中，使 用 r a n d()%2 1 能够产生0-2 0 之间的一个随机数。1 0 .一个记录r理论上占有的

5、存储空间的大小等于所有域的长度之和，实际上占有的存储空间的大小即记录长度为s i ze of(r)。1 1 .一个数组a所占有的存储空间的大小即数组长度为s i ze of(a),下标为i的元数a i 的存储地址为a+1 ,或 者 为(c h a r*)a+i*s ize o f(a i)。1 2 .函数重载要求参数类型、参数个数或排列顺序有所不同。1 3 .对于双目操作符，其重载函数带有2个参数，其中至少有一个为用户自定义的类型。1 4 .若对象r a 和 r b 中至少有一个属于用户定义的类型，则执行r a=r b 时，需要调用等于号(=)重载函数，该函数第一个参数应与r a ,的类型相同

6、，第二个参数应与rb的类型相同。1 5 .从一维数组a n 中顺序查找出一个最大值元素的时间复杂度为0(n),输出一个二维数组b m n 中所有元素值的时间复杂度为0(m*n)。1 6 .在下面程序段中，s=s+p语句的执行次数为n ,p*=j语句的执行次数为n(n+l)/2,该程序段的时间复杂度为0(n 2)。in t i=0,s=0；wh il e(+i=n)in t p=l；f o r(in t j=l；j=i；j+)P*=j；s=s+p；)1 7 .一个算法的时间复杂度为(3 n 2+2 n l o g2 n+4 n-7)/(5 n),其数量级表示为0(n)1 8 .从一个数组a 7

7、中顺序查找元素时，假定查找第一个元素a 0 的概率为1/3,查找第二个元素a l l 的概率为1/4,查找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为3 5/1 2 .三、普通题1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示(当出现多个关系时，对每个关系画出相应的结构图)，并指出它们分别属于何种结构。A=(K,R)其中K=a l,a 2,a 3.,a n)R=B=(K,R)其中f il e：/D|/-上架商品-.教 程(第 二 版)课 后 答 案(徐 孝 凯著)清华大学/第一章绪论.tx t(第 2/10页)2 0 1 0-3-1 6 2 2:0 6:1 7

8、f il e：/D|/-上架商品-/数据结构实用教程(第二版)课 后 答 案(徐 孝 凯 著)清华大学/第一章绪论.tx tK=a,b,c,d,e,f,g,h)R=r r=,C=(K,R)其中K=a,b,c,d,f,g,h R=r r=,(4)D=(K,R)其中K=1,2,3,4,5,6 R=r r=(l,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)E=(K,R)其中K=4 8,2 5,6 4,5 7,8 2,3 6,7 5,4 3 R=r l,r 2,r 3 r 1=,r 2=,r 3=,6 4,7 5，解：是集合结构；是线性结构；是树型结构；散列

9、结构。只作为参考。2.设计二次多项式a x 2+b x+c的一种抽象数据类型，假定起名为Q I Ad r a tic,该类型的数据部分分为三个系数项a、b和c,操作部分为：(请写出下面每一个操作的具体实现)。初始化数据成员a b和c(假定用记录类型Q ua d r a tie定义成员)，每个数据成员的默认值为O oQ ua d r a tic I n itQ ua d r a tic(f l o a t a a=0,f l o a t b b=O,f l o a t c c=0)；解：Q ua d r a tic I n itQ ua d r a tic(f l o a t a a,f l o

10、 a t b b,f l o a t c c)(Q ua d r a tic q；q.a=a a；q.b=b b；q.c=c c；r e tur n q；)做两个多项式加法，即使对应的系数相加,并返回相加的结果。Q u a d r a t i c Ad d(Q u a d r a t i c q l,Q u a d r a t i c q 2)；解：Q u a d r a t i c Ad d(Q u a d r a t i c q l,Q u a d r a t i c q 2)；Q u a d r a t i c q;q.a=q l.a+q 2.a；q.b=q l.b+q 2.b;q.c=

11、q l.c+q 2.c；f i l e:/D|/-上架商品-.教 程(第 二 版)课 后 答 案(徐 孝 凯著)清华大学/第一章 绪论.t x t (第3/10页)2 0 1 0-3-1 6 2 2:0 6：1 7 f i l e：/D|/-上架商品-/数据结构实用教程(第二版)课后答案(徐孝凯著)清华大学/第一章绪论.t x tr e t u r n q；)根据给定x的值计算多项式的值。f l o a t Ev a l(Q u a d r a t i c q,f l o a t x)；解：f l o a t Ev a l(Q u a d r a t i c q,f l o a t x)(r

12、e t u r n(q.a*x*x+q.b*x+q.c)；)计 算 方 程a x 2+b x+c=0的两个实数根，对于有实根、无实根和不是实根方程(即a=0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。i n t R o o t (Q u a d r a t i c q,f l o a t&r l,f l o a t&r 2)；解：i n t R o o t(Q u a d r a t i c q,f l o a t&r l,f l o a t&r 2)(i f(q.a=0)r e t u r n -1；f l o a t x=q.b*q.b-4*q.a*q.c；i f(x=

13、0)r l=(f l o a t)(-q.b+s q r t(x)/(2*q.a)；r2=(f l o a t)(-q.b-s q r t (x)/(2*q.a)；r e t u r n 1；)e l s er e t u r n 0；按照a x*2+b x+c的格式(x 2用x*2表示)输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。v o i d P r i n t(Q u a d r a t i c q)解：v o i d P r i n t(Q u a d r a t i c q)(i f(q.a)c o u t q.a 0)c o u t +

14、H q.bMx；e l s ec o u t 0)c o u t n+n q.c；e l s ec o u t x 2,x l=x 2 和 x l x 2 这三种不同情 况 分 别 返 回=和 字符。假定简单类型用S i m p l e T y p e 表示，它可通过t y p e d e f语句定义为任一简单类型。解：c h a r c o m p a r e(S i m p l e T y p e x l,S i m p l e T y p e x 2)(i f(x l x 2)r e t u r n ；e l s e i f(x l=x 2)r e t u r n t=,；e l s e

15、 r e t u r n*,；其时间复杂度为0(1)将一个字符串中的所有字符按相反方的次序重新放置。解：v o i d R e v e r s e(c h a r*p)(i n t n=s t r l e n (p)；f o r (i n t i=0；i n/2；i+)c h a r c h；c h=p i p i =p n-i-1 ；p n-i-l =c h；)其时间复杂度为0(n)求一维d o u b l e 型数组.a n 中的所有元素之乘积。解：d o u b l e p r o d u c t (d o u b l e a ,i n t n)(d o u b l e p=l；f o

16、r(i n t i=0；i n；i+)p*=a i ；r e t u r n p；)其时间复杂度为0(n)(4)计算 En i=O x i/i+l 的值。解：d o u b l e Ac c u m u l a t e(d o u b l e x,i n t n)(d o u b l e p=l,s=l；f o r(i n t i=l；i =n；i+)p*=x；s+=p/(i+l)；f i l e：/D|/-上架商品-.教 程(第 二 版)课 后 答 案(徐 孝 凯著)清华大学/第一章绪论.t x t (第 5/10页)2 0 1 0-3-1 6 2 2:0 6:1 7 f i l e：/D|

17、/-一上架商品一 一/数据结构实用教程(第二版)课后答案(徐孝凯著)清华大学/第一章绪论.t x t)r e t u r n s；)其时间复杂度为0(n)(5)假定一维数组a n 中的每个元素值均在 0,2 0 0 区间，分别统计出落在 0,2 0),2 0,5 0),5 0,8 0),8 0,1 3 0),1 3 0,2 0 0 等各区间的元素个数。解：i n t Co u n t(i n t a ,i n t n,i n t c 5 )用数组 c 5 保存统计结果(i n t d 5 =2 0,5 0,8 0,1 3 0,2 0 1；用来保存各统计区间的上限i n t i,j；f o r

18、(i=0；i 5；i+)c i =0；给数组c 5 中的每个元素赋初值0f o r(i=0；i n；i+)(i f(a i 2 0 0)r e t u r n 0；/返回数值0表示数组中数据有错，统计失败f o r(j=0；j 5；j+)查找 a i 所在区间i f(a i =n 和 N =n 的条件，L i n 和 C o l 为引用形参，它是对应实参的别名，其值由实参带回L i n=0；C o l=0；f o r(i n t i=0；i m；i+)f o r(i n t j=0；j a L i n C o l)L i n=i；C o l=j;)其时间复杂度为0(m*n)4.指出下列各算法的

19、功能并求出其时间复杂度。(1)i n t p r i m e (i n t n)(i n t i=2；i n t x=(i n t)s q r t (n)；w h i l e(i x)r e t u r n 1；e l s er e t u r n 0；解：判断n是否是一个素数，若是则返回数值1,否则返回0。该算法的时间复杂度为0(n l/2)o(2)i n t s u m l (i n t n)(i n t p=l,s=0；f o r(i n t i=l；i =n；i+)p*二 i;s+=p；)r e t u r n s；解：计算E i!(上标为n,下标为i=l)的值，其时间的复杂度为0(n

20、)。i n t s u m 2(i n t n)i n t s=0；f o r(i n t i=l；i =n；i+)i n t p=l；f o r(i n t j=l；j =i；j+)P*二 j；s+二 p；)r e t u r n s；)解：计算 i!的值,时间复杂度为0(n 2)(4)i n t f u n(i n t n)(i n t i=l,s=l；w h i l e(s n)s+=+i；r e t u r n i；)解：求出满足不等式1+2+3.+i n 的最小i 值，其时间复杂度为0(n l/2)o(5)v o i d Us e F i l e(i f s t r e a m&i

21、n p,i n t c 10)假定i n p 所对应的文件中保存有n个整数f i l e:/D|/-上架商品-.教 程（第二版）课 后 答 案（徐孝凯著）清华大学/第一章绪论.t x t （第 7/1 0 页）2010-3-16 22:06：17f i l e：/D|/-上架商品-/数据结构实用教程（第二版）课 后 答 案（徐孝凯著）清华大学/第一章绪论.t x t（f o r（i n t i=0；i 10；i+）c i=0；i n t x；w h i l e（i n p x）i=x%10；c i+;）解：利用数组c 10中的每个元素c i 对应统计出i n p 所联系的整数文件中个位值同为i

22、 的整数个数，时间复杂度为0（n）（6）v o i d r a t a b l e（i n t n）（f o r（i n t i=l；i =n；i+）f o r（i n t j=i；j =n；j+）c o u t i *j =s e t w（2）i*j ；c o u t e n d l；）解：打印出一个具有n行的乘法表，第 i 行（I W i W n）中有n-i+1个乘法项，每个乘法项为i与 J（i W j W n）的乘积，时间复杂度为0（n 2）。v o i d c m a t r i x（i n t a M N,i n t d）M 和 N为全局整型常量（f o r（i n t i=0；i

23、M；i+）f o r（i n t j=0；j N；j+）a i j*=d；）解：使数组a M N 中的每一个元素均详细以d的值，时间复杂度为0（M*N）（8）v o i d m a t r i m u l t（i n t a M N,i n t b N L,i n t c M L）/（i n t i,j,k；f o r（i=0；i M；i+）f o r（j=0；j L；j+）c i j=0；f o r（i=0；i M；i+）f o r（j=0；j L；j+）f o r（k=0；k N；k+）c i j+=a i k*b k j；f i l e：/D|/-上架商品-.教 程（第二版）课 后 答

24、案（徐孝凯著）清华大学/第一章绪论.t x t （第 8/1 0 页）2010-3-16 22:06:17f i l e：/D|/-一上架商品一 一/数据结构实用教程（第二版）课 后 答 案（徐孝凯著）清华大学/第一章绪论.t x t）解：矩阵相乘，即 a M N Xb N L f c M L,时间复杂度为 O（M X N X L）。5.题目略解：v o i d I n i t Se t （Se t&.s）（f o r（i n t i=l；i =SE TSI ZE；i+）s.m i=0；解：v o i d I n i t Se t (Se t&s,i n t a,i n t n)f o t(i

25、 n t i=0；i n；i+)s.m a i=l；)解：Se t o p e r a t o r +(Se t s i,Se t s 2)(Se t s；I n i t Se t(s)；f o r(i n t i=l；i =SE TSI ZE；i+)i f (s i.|s 2.m i=l)s.=r e t u r n s；)解：Se t o p e r a t o r*(Se t s i,Se t s 2)(Se t s；I n i t Se t (s)；f o r(i n t i=l；i =SE TSI ZE；i+)i f (s i.m i=l)&(s 2.m i=l)s.=r e t u

26、 r n s；解:Bo o l e a n o p e r a t o r (i n t e l t,Se t s)(i f (s.m e l t=l)r e t u r n Tr u e；e l s ef i l e：/D|/-上架商品-.教 程（第二版）课 后 答 案（徐孝凯著）清华大学/第一章 绪论.t x t （第9/1 0页）2010-3-16 22:06:17f i l e:/D|/-上架商品-/数据结构实用教程（第二版）课后答案(徐孝凯著)清华大学/第一章绪论.t x tr e t u r n F a l s e；)解：v o i d I n i s e r t(Se t&s,i

27、 n t n)(s.m n=l；)解：v o i d D e l e t e(Se t&s,i n t n)s.m l n=0；）解：o s t r e a m&o p e r a t o r（o s t r e a m f e o s t r,Se t&s）（o s t r f o r（i n t i=l；i =SE TSI ZE；i+）i f（s.m i=l）o s t r i ne xt=HL；B p=ne xt=HL；HL=p；C p-ne xt=HL；p=HL；D p-ne xt=HL-ne xt；HL-ne xt=p；5 .在一个单链表H L 中，若要在指针q 所指结点的后面插入一

28、个自由指针p 所指向的结点，则执行D oA q-ne xt=p-ne xt;p-ne xt=q；B p-ne xt=q-ne xt；q=p；C q-ne xt=p-ne xt；p-ne xt=q D p-ne xt=q-ne xt；q-ne xt=p；6 在一个单链表H L 中，若要删除由指针q 所指向结点的后继结点，则 执 行 C oA p=q-ne xt；p-ne xt=q-ne xt；B p=q-ne xt；q-ne xt=p；C p=q-ne xt；q-ne xt；q-ne xt=q；D q-ne xt=q=-N e xt-ne xt；q-ne xt=q；二、填空题1.在线性表的单存储

29、结构中，每个结点包含有两个域，一 个 叫 值，另一个叫指针 域。2.在下面数组a中存储着一个线性表，表头指针为a 0 .ne xt,则该线性表为(3 8,5 6,25,6 0,4 2,7 4)oa 01 2 345678d a ta 6 0 5 6 4 2 3 8 7 4 25 ne xt 43762 0 13 .对于一个长度为1 的顺序存储的线性表，在表头插入元素的时间复杂度幡o(n),在表尾插入元素的时间复杂 度 为 0(1)。4 .对于一个单存储的线性表，在表头插入结点沿时话里有话复杂度为o(l),在表尾插入元素的时间复杂度为o(n)。5 .在线性表的顺序存储中，若一个元素的下标为i,则

30、它的前驱元素的下标为i-1,后继元素的下标为i+1。f i le：/D|/-上架商品-.一程(第二版)课后答案(徐孝凯著)清华大学/第二章线性表.txt(第 1/2 1 页)20 10-3-16 22:0 6:5 9 f i le:/D|/-一上架商品一 一/数据结构实用教程(第二版)课后答案(徐孝凯著)清华大学/第二章线性表.txt6 .在线性表的单存储中，若一个元素所在结点的地址为p,则后继结点的地址为p-ne xt,若假定P 为一个数组a中的下标，则其后继结点的下标为a p.ne xt。7 .在循环单表中，最后一个结点的指针域指向表头结点。8 .在双向表中每个结点包含有两个针域，一个指向

31、其前驱结点，另一个指向其后继结点。9 .在循环双向表中表头结点的左指针域指向表尾结点，最后一个结点的右指针域指向 表 头 结 点。10 .在 以 H L为 表 头 指 针 的 带 表 头 附 加 结 点 的 单 表 中，链 表 为 空 的 条 件 分 别 为HL-ne xt=N U L LHL-ne xt=HL 。II.在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 a i .ne xt=a l.ne xt；a l.ne xt=i;。12.在由数组a中元素结点构成的单链表中，在插入下标为i的结点后，需要从空闲表头中删除一个结点，并将该结点下

32、标赋给i,具体操作为i=a l.ne xt；a l.ne xt=a i .ne xt；o13 .在由数组a中元素结点构成的单链表中，删除下标为i的后继结点并将被删除结点的下标赋给i时,所进行的操作描述为 p=a i .ne xt；a i l.ne xt=a p.ne xt；i=p；14 .在由数组a中元素结点构成的单链表中，在下标为i 的结点的后面插入一个下标为j的结点时，需要进行的操作为 a j .ne xt=a i .ne xt；a i .ne xt=j；,三、普通题1.解：(7 9,6 2,3 4,5 7,26,4 8)解：(26,3 4,4 8,5 7,6 2,7 9)解:(4 8,5

33、 6,5 7,6 2,7 9,3 4)解：(5 6,5 7,7 9,3 4)解：(26,3 4,3 9,4 8,5 7,6 2)2.解：f i le：/D|/-上架商品-.程(第二版)课后答案(徐孝凯著)清华大学/第二章 线性表.txt(第 2/2 1 页)20 10-3-16 22:0 6:5 9 f i le：/D|/-一上架商品一 一/数据结构实用教程(第二版)课后答案(徐孝凯著)清华大学/第二章线性表.txt为了排版方便，假定采用以下输出格式表示单表的示意图；每个括号的数据表示一个元素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为表头指针。1.(7(

34、7 9,6),(6 2,5),(3 4,4),(5 7,3),(26,2),(4 8,0)2.(3 (26,5),(3 4,2),(4 8,4),(5 7,6),(6 2,7),(7 9,0)3 .(2(4 8,8),(5 6,4),(5 7,6),(6 2,7),(7 9,5),(3 4,0)4 .(8(5 6,4),(5 7,7),(7 9,5),(3 4,0)3.对于L i st类型的线性表，编写出下列每个算法。从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。解：Ele m T y p e DMVal u e(Li s t&

35、L)从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补,若线性表为空则显示出错信息并退出运行(i f(Li s t Em p t y(L)cer r Li s t i s Em p t y!en dl;ex i t(1)；El em Ty p e x；x=L.l i s t 0;i n t k=0；fo r(i n t i=l；i L.s i z e；i+)El em Ty p e y=L l i s t i；i f(y x)x=y；k=i；)L.l i s t k=L.l i s t L.s i z e-1；L.s i z e一；r et u r n x；)(2)从线性

36、表中删除第i 个元素并由函数返回。解：i n t Del et el(Li s t ft L,i n t i)从线性表中删除第i 个元素并由函数返回i f(i L.s i z e)cer r HIn dex i s o u t r an g e!w en dl；ex i t (1);)El em Ty p e x;x=L.l i s t i-l；fo r(i n t j=i-l；j L.s i z e-1;j+)L.l i s t j=L.l i s t j+l；L.s i z e;fi l e：/D|/-上架商品-程(第二版)课后答案(徐孝凯著)清华大学/第二章 线性表.t x t (第 3

37、/21 页)2 0 10-3-16 2 2:0 6:5 9 fi l e：/D|/-一上架商品一 一/数据结构实用教程(第二版)课后答案(徐孝凯著)清华大学/第二章线性表.t x tr et u r n x；)(3)向线性表中第i 个元素位置插入一个元素。解：v o i d In s er l(Li s t&L,i n t i,El em Ty p e x)向线性表中第i 个元素位置插入一个元素(i f(i L.s i z e+1)cer r wIn dex i s o u t r an g e!en dl；ex i t (1)；)i f(L.s i z e二 二 Max Si z e)(ce

38、r r MLi s t o v er fl o w!”en dl；ex i t (1)；)fo r(i n t j=L.s i z e-1；j-)L.l i s t j+l=L.l i s t t j；L.l i s t i-l=x；L.s i z e+；)(4)从线性表中删除具有给定值x的所有元素。解：v o i d Del et e2(Li s t&L,El em Ty p e x)从线性表中删除具有给定值x的所有元素(i n t i=0;w h i l e(i L.s i z e)i f(L.l i s t i=x)fo r (i n t j=i+l；j L.s i z r；j+)L.l

39、 i s t j-l=L.l i s t t j;L.s i z e-；)el s ei+;)从线性表中删除其值在给定值S 和 t 之间(要求S 小于t)的所有元素。解：v o i d Del et e3(Li s t&L.El em Ty p e s,El em Ty p e t)从线性表中删除其值在给定值s 和 t之间的所有元素(i n t i=0；w h i l e(i=s)&(L l i s t i =t)fo r(i n t j=i+l；j L.s i z e；j+)L.l i s t j-i=L.l i s t j；L.s i z e;)el s ei+;(6)从有序表中删除其值在

40、给定值s 和 t之间(要求s 小于t)的所有元素。解：v o i d Del et e4(Li s t ft L.El em Ty p e s,El em Ty p e t)从有序表中删除其值在给定值s 和 t之间的所有元素(i n t i=0；w h i l e(i L.s i z e)从有序表L 中查找出大于等于s的第一个元素i f(L l i s t i s)i+；el s e br eak；i f(i L.s i z e)Wh i l e(i+j L.s i z e)&(L.l i s t i+j =t)j+;求出s 和 t之间元素的个数fo r(i n t k=i+j；kMax Si

41、 z e)cer r Li s t o v er fl o w!en dl；ex i t(1)；)i n t i=0,j=0,k=0；w h i l e(i Ll.s i z e)&(j L2.s i z e)i f(Ll.l i s t i =L2.l i s t j)将L I 中的元素赋给LL l i s t k=Ll.l i s t i；i+:)el s e 将 L 2 中的元素赋给LL l i s t k=L2.l i s t j；j+；fi l e：/D|/-上架商品-.一程(第二版)课后答案(徐孝凯著)清华大学/第二章线性表.t x t (第 5/21 页)2 0 10-3-16

42、2 2:0 6:5 9 fi l e:/D|/-一上架商品一 一/数据结构实用教程(第二版)课后答案(徐孝凯著)清华大学/第二章线性表.t x t)k+；w h i l e(i Ll.s i z e)将L I 中剩余的元素赋给LL l i s t k=Ll.l i s t Ei；i+；k+；)w h i l e(j L2.s i z e)将 L 2 中剩余的元素赋给LL.l i s t k=L2.l i s t j；j+;k+；L.s i z e=k；(8)从线性表中删除所有其值重复的元素，使其所有元素的值均不同，如对于线性表8,9,2,5,5,6,8,7,2),则执行此算法后变为(2,8,9

43、,5,6,7)解：v o i d Del et e5 (Li s t&L)从线性表中删除所有其值重复的元素，使其所有元素的值均不同(i n t i=0；w h i l e(i L.s i z e)i n t j=i+l;w h i l e(j L.s i z e)删除重复值为L.l i s t l i 的所有元素i f(L.l i s t j=L.l i s t i)fo r(i n t k=j+1；kn ex t；/p 指向下一个待逆序的结点 将 q结点插入到已序单链表的表头q-n ex t=HL；HL=q；删除单链表中的第i 个结点。解：v o i d Del et el(LNo de*&

44、HL,i n t i)删除单链表中的第i 个结点(i f(i n ex t；j+；i f(cp=NULL)cer r n ex t；el s eap-n ex t=cp-n ex t；del et e cp；)从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。解：El em Ty p e Max Val u e(LNo de*HL)从单链表中查找出所有元素的最大值，该值由函数返回fi l e:/D|/-上架商品-.程(第二版)课后答案(徐孝凯 著)清华大学/第二章 线性表.t x t (第 7/21 页)2 0 10-3-16 2 2:0 6:5 9 f

45、i l e：/D|/-上架商品-/数据结构实用教程(第二版)课后答案(徐孝凯著)清华大学/第二章线性表.t x t(i f(HL=NULL)cer r Li n ked l i s t i s em p t y!en dl；ex i t(l);)El em Ty p e m ax=HL-dat a;LNo de*p=HL-n ex t；w h i l e(p!=NULL)i f(m ax dat a)m ax=p-dat a；p=p-n ex t；r et u r n m ax；)(4)统计出单链表中结点的值等于给定值x的结点数。解：i n t Co u n t (LNo de*HL,El e

46、m Ty p e x)统计出单链表中结点的值等于给定值X 的结点数(i n t n=0；w h i l e(HL!=NULL)i f(HL-dat a=x)n+；HL=HL-n ex t；)r et u r n n；)根据一维数组a n 建立一个单链表，使单链表中元素的次序与a n 中元素的次序相同,并使该算法的时间复杂度为0(n)。解：v o i d Cr eat e(LNo de*&HL,El em Ty p e a,i n t n)根据一维数组a n 建立一个单链表(In i t Li s t(HL);fo r(i n t i=n-l；i=0；i 一)In s er t Fr ont(H

47、 L,a i；)(6)将一个单链表重新成有序单链表。解：v oid Or d e r L is t(L Nod e*&H L)将一个单链表重新成有序单链表(L Nod e*p=H L；p指向待处理的第一个结点，初始指向原表头结点H L=NUL L；肛仍为待建立的有序表的表头指针，禄始值为空w hil e(p!=NUL L)/把原单链表中的结点依次进行有序f il e：/D|/-上架商品-.程(第二版)课后答案(徐孝凯 著)清华大学/第二章 线性表.t xt (第 8/21页)2 0 1 0-3-1 6 2 2:0 6:5 9 f il e:/D|/-一上架商品一 一/数据结构实用教程(第二版)

48、课后答案(徐孝凯著)清华大学/第二章线性表.t xtL Nod e*q=p；q指向待处理的结点p=p-ne xt；p指向下一个待处理的结点L Nod e*a p=NUL L,*c p=H L;c p指向有序表中待比较的结点，a p指向其前驱结点w hil e(c p!=NUL L)为插入q 结点寻找插入位置if(q-d a t a d a t a)b r e a k；e l s e (a p=c p；c p=c p-ne xt;)将q 结点插入到a p和 c pxf hko pp u jq-ne xt=c p；if(a p=NUL L)H L=q；e l s ea p-ne xt=q；)将两个

49、有序单链表合并成一个有序单链表，合并后使原有单链表为空。解：L Nod e*Me r g e l(L Nod e*&pl,L Nod e*&p2)/将两个有序单链表合并成一个有序单链表(L Nod e a；/a 结点作为结果的有序单链表的表头附加结点，这样便于处理,处理结束后返回a结点的镣针域的值L Nod e*p=&a；p指向结果的有序单链表的表尾结点p-ne xt=NUL L；初始指向表头附加结点w hil e(pl!=NUL L)&(p2!=NUL L)处理两个表非空的情况if(pl-d a t a d a t a)p-ne xt=pl；pl=pl-ne xt；)e l s e p-ne

50、 xt=p2；p2=p2-；p=p-ne xt;)if(pl!=NUL L)p-ne xt=pl；if(p2!=NUL L)p-ne xt=p2；pl=p2=NUL L;r e t u r n a.ne xt；f il e：/D|/-上架商品-.一程(第二版)课后答案(徐孝凯著)清华大学/第二章 线性表.t xt (第 9/21页)2 0 1 0-3-1 6 2 2:0 6:5 9 f il e：/D|/-一上架商品一 一/数据结构实用教程(第二版)课后答案(徐孝凯著)清华大学/第二章线性表.t xt(8)根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假定两个有序单链表 中