2.4　上机实践

1．编写向顺序表中插入元素的函数，函数的参数有两个：一个是需要插入的位置n，一个是需要插入的数据（这里假定数据为一个int数据）。顺序表用一个数组SL来保存。

分析：在顺序表中插入节点的操作比较麻烦，因为顺序表中的所有节点都是按序号紧邻存放的，如果要在其中插入一个节点，则需要将插入点后面的节点数据向后移动一个位置，以便用空出的位置保存插入节点的数据。

2．编写向链表插入元素的函数，函数有3个参数：第一个参数是链表的头指针，第二个参数为需要插入元素处的关键字，第三个参数是需要插入的数据。

分析：向链表中插入节点就是在链表的中间部分增加节点，这时首先需要找到要插入的位置，然后修改插入位置节点的指针，使其指向新增节点，而使新增节点指向原插入位置所指向的节点。

3．假设在周末舞会上，男士和女士进入舞厅时分别排成两队。跳舞开始时，依次从男队和女队的开始位置各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。编写程序模拟上述舞伴配对问题。

分析：先排队的男士或女士也就先出队配成舞伴。因此，这是典型的先进先出特性，可用队列作为算法的数据结构。

假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。

4．使用栈编写一个将十进制数转换为其他进制的程序，即由用户输入一个十进制数，然后再输入需要转换的目标进制，最后输出转换的结果。

分析：十进制数转换为其他任意进制时，采用反复除以某进制的基数，取其余数作为对应进制的数据，并且最先得到的是该进制的低位，最后得到的才是该进制的高位。

例如，若需将十进制数65 312转换为十六十进制，具体过程如下：

由于最先求得的余数是低位，而最后得到的余数是高位，因此，在将十进制转换为其他任意进制时需使用一个栈，将先求出来的余数放入栈中，最后从栈中弹出数据进行输出，即可将高位输出在前。