数据结构第二章参考答案

3.size:195 4.size:100 （3）程序段三

int a[]={1,2,3,4,5}; list ilist(3,2); ilist.assign(a,a+5);

//1 2 3 4 7

ilist.pop_back (); //1 2 3 4 ilist.insert (ilist.end(),7); ilist.pop_front (); //2 3 4 7 ilist.front ()=20; //20 3 4 7 ilist.sort(); //3 4 7 20

for ( list::iterator it = ilist.begin (); it != ilist.end(); it++ )

cout << *it <<\; cout << endl;

答案：3 4 7 20

5．算法设计

（1）分别编程实现顺序表类和链表类，并设计完整的测试程序对每个接口进行测试。 （2）设A=（a1,a2,a3,......an）和B=(b1,b2,.. .,bm)是两个线性表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,.. .,j)且aj+1B。试编写一个比较A和B的算法，当AB是分别输出-1，0或者1。

（3）假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。

（4）试分别以顺序表和单链表作为存储结构，各写一个实现线性表的就地（即使用尽可能少的附加空间）逆置的算法，在原表的存储空间内将线性表（a1，a2,，??，an-1，an)逆置为（an，an-1，??，a2，a1)。

（5）假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 答案：

template

void DeletePreNode (Node * s) {

Node * p = s;

//得到s的结点的前一个结点的前一个结点 while (p->next->next != s) p=p->next; //删除p->next指向的结点 Node * q = p->next; p->next = s; delete q; }

（6）已知一单链表中的数据元素含有三类字符(即:字

5

母字符、数字字符和其它字符)。试编写算法，构造三个

n1循环链表，使每个循环链表中只含同一类的字符，且利2n-1用原表中的结点空间作为这三个表的结点空间(头结点可3n-2另辟空间)。

（7）Josephus环问题：任给正整数n、k，按下述方法可得排列1，2，??，n的一个置换：将数字1，2，??，n环形排列（如图2-36所示），按顺时针方向从1开始计数，计满k时输出该位置上的数字（并从环中删去该数图2-36 Josephus环 字），然后从下一个数字开始继续计数，直到环中所有数

字均被输出为止。例如，n=10，k=3时，输出的置换是3，6，9，2，7，1，8，5，10，4。试编写一算法，对输入的任意正整数n、k，输出相应的置换数字序列。

6

7