2.3.4　实验提示

1. 线性表基本操作的实现

【问题描述】 当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。反之，欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。

【基本要求】 要求生成线性表时，可以从键盘上读取元素，用顺序存储结构和链式存储结构实现。

【程序实现】

//顺序存储类型定义

//插入函数

{

//删除运算

//创建线性表

//输出线性表

请读者完成链式存储结构的操作实现。

2. 约瑟夫问题

【问题描述】 设有n个人围坐一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到M的人又出列，如此下去，直到所有人都出列为止。试设计确定他们的出列次序序列的程序。

【基本要求】 选择单向循环链表作为存储结构模拟整个进程，并依次输出出列的各人的编号。

【实现提示】 由于该问题由古罗马著名史学家Josephus提出的问题演变而成，所以通常称之为Josephus问题。

【程序实现】

//结点类型定义

//使n个人围成一圈,并给每个人标识号数

//出列算法

请读者思考如何用数组来实现。

3. 一元多项式的简单计算器

【问题描述】 设计一个一元多项式简单的计算器。

【基本要求】 一元多项式简单计算器的基本功能为：

(1) 输入并建立多项式：

(2) 输出多项式；

(3) 两个多项式相加减、相乘，建立并输出多项式。

【实现提示】 可选择带头结点的单向循环链表或单链表存储多项式、头结点可存放多项式的参数如项数等。

【程序实现】

//多项式类型描述

//产生多项式链表

//两个多项式相加

请读者自行完成两个多项式相减的算法实现。

//两个多项式相乘

其中的reverse函数实现如下:

//多项式的输出