利用原表中得结点空间作为这三个表得结点空间头结点可另辟空间。13、Josephus环任给正整数
、k按下述方法可得排列12……
得一个置换将数字12、、、
环形排列如图算法设计题13、所示按顺时针方向从1开始计数计满K时输出该为之上得数字并从环中删去该数字然后从下一个数字开始继续计数直到环中所有数字均被输出为止。例如
10k3时输出得置换就是36927185104。试编写一算法对输人得任意正整数
、k输出相应得置换14在双链表上实现线性表得下列基本运算a初始化b定位c插入d删除。15设有一双链表每个结点中除有prior、data与
ext三个域外还有一个访问频度域freq在链表被起用之前其值均初始化为零。每当在双链表上进行一次LOCATELX运算时令元素值为X得结点中freq域得值增1并使此链表中结点保持按访问频度递减得顺序排列以便使频繁访问得结点总就是靠近表头。试编写实现符合上述要求得LOCATE运算得算法。16若X与Y就是用结点大小为1单链表表示得串设计一个算法找出X中第一个不在y中出现得字符。17在顺序串上实现串得判等运算EQUALST。18在链串上实现判等运算EQUALST。19若S与T就是用结点大小为1得单链表存储得两个串S、T为头指针设计一个算法将串S中首次与串T匹配得子串逆值。
f20用串得其她运算构造串得子串定位运算i
dex。
第二章参考答案
一、名词解释略
二、填空题
1、结点起始终端序号位置前趋后趋
2、ф
3、前趋前趋后趋后趋
4、线性
5、线性长度表长
6、空表
7、初始化INITLATEL求表长LENGTHL读表长GETLi定位LOCATE
LX
插入INSERTLXi删除DELETELi
8、逻辑结构中相邻得结点在存储结构中仍相邻
9、bi1xk
10、LdatajLdataj1
11、
O
2O

12、L、dataj2l、dataj1
13、
1o
12O

14、i1iL、last
15、O
O1
16、L、lastL、datai1
17、单链表循环链表双链表
18、指针19单链表
20、头结点表结点
21、首结点尾结点任何信息、特殊标志表长
22、头结点头结点
23、tmallocsizet
extNULL
24、phaedpp
ext
25、p
extNULLjI
26、p
extNULLpdatax
27、pNULLp
extNULLp
ext
28、maillocsizep
ext
29、i
sert_lklistheadxII
12O
2
30、pqp
extNULLO

31、单向循环链表简称循环链表双向循环链表简称双链表
32、NULL头结点
33、双链表
三、单项选择题1、②2、①3、①4、②5、①6、②7、③8、③9、④10、②
f11、④12、③13、⑤14、④15、③16、①17、②18、③19、④20、④21、④22、223、②24、③25、④26r