实验一 线性表应用 一. 实验目的
1、 掌握用Turbo C或VC++上机调试线性表的基本方法；
2、 掌握线性表的基本操作，如插入、删除、查找，以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；并能够运用线性表基本操作解决问题，实现相应算法。
二. 实验学时： 课内实验学时：2学时 课外实验学时：4学时 三．备选实验题目
1． 单链表基本操作练习（实验类型：验证型）
1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能： 1…建立链表
2…连接链表 3…输出链表 0…结束
2）实验要求：在程序中定义下述函数，并实现所要求的函数功能： CreateLinklist( ): 从键盘输入数据，创建一个单链表 ContLinklist( )：将前面建立的两个单链表首尾相连 OutputLinklist( )：输出显示单链表 3）实验提示: ?
单链表数据类型定义（C语言）
# include
typedef int ElemType； //元素类型 typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; ?
为了算法实现简单，最好采用带头结点的单向链表。
4）注意问题: ? ?
重点理解链式存储的特点及指针的含义。 注意比较顺序存储与链式存储的各自特点。
? ?
注意比较带头结点、无头结点链表实现插入、删除算法时的区别。
单链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。
2． 顺序表基本操作练习（实验类型：验证型） 1）问题描述： ? ? ? ?
从键盘输入一组整型元素序列，建立顺序表。 实现该顺序表的遍历。
在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。 判断该顺序表中元素是否对称,对称返回1,否则返回0。
2）实验要求： ? ?
对应问题描述，在程序中定义4个相应的函数，实现上面要求的函数功能： 在主程序中设计一个简单的菜单，调用上述4个函数
3）实验提示: ?
顺序表存储数据类型定义（C语言）
# define MAXSIZE 100 //表中元素的最大个数 typedef int ElemType； //元素类型 typedef struct list{
ElemType elem[MAXSIZE]; //静态线性表 int length; //表的实际长度 }SqList; //顺序表的类型名 4）注意问题: ? ?
插入、删除时元素的移动原因、方向及先后顺序。 理解不同的函数形参与实参的传递关系。
3． 约瑟夫环问题（实验类型：综合型）
1）问题描述：有编号为1, 2…n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。
2）实验要求: 采用顺序和链式两种存储结构实现 3) 实现提示： ? ?
用顺序表来存储围座者的序号和密码(顺序存储结构).
用number 和code分别表示围座者的序号和密码.假设围座者人数为 j,当前使
用密码为m,开始报数者位置为s, 那么下一出列者位置为s=(s+m-1) mod j.
? 当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先
将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。
?
用链式存储解决此问题时可以采用循环链表.
4）注意问题: ? 区别。
4． 一元稀疏多项式简单的计算器（实验类型：综合型）
1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器 2）实验要求: ? ? ? ?
采用单链表存储结构一元稀疏多项式 输入并建立多项式 输出多项式
实现多项式加、减运算
顺序存储和链式存储实现此算法时计算出列位置的不同方法，人员出列后所做操作的
3) 实现提示：以两个多项式相加为例 ? ? ? ? ?
结果多项式另存
扫描两个相加多项式，若都未检测完：
若当前被检测项指数相等，系数相加，若结果未变成0，则将结果插入到结果多项式。 若当前被检测项指数不等，则将指数较小者插入到结果多项式。
若有一个多项式已检测完，则将另一个多项式剩余部分直接连接到结果多项式。
5． 长整数（任意长度）四则运算演示程序（实验类型：综合型） 1）问题描述：设计一个实现任意长的整数进行加法运算的演示程序 2）实验要求: ?
利用双向循环链表实现长整数的存储，给各结点含一个整型变量。任何整型变量的的范
围是 -（215-1）~（215-1）。
?
输入和输出形式：按照中国对长整数的表示习惯，每四位一组，组间用逗号隔开。
3) 实现提示： ?
每个结点中可以存放的最大整数为2-1=32767，才能保证两数相加不会溢出。但若这
15
样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。
? 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点的树木。
相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。
4）注意问题: ?
不能给常整数位数规定上限。
程序设计源代码如下：
第一题：
#include
#include
typedef int ElemType; ////元素类型 typedef struct LNode {
ElemType data;
struct LNode *next; }LNode;
typedef LNode *LinkList;
LinkList head;
LinkList L; ////定义单链表头指针L
LinkList L1; LinkList L2; LinkList L12;
LinkList Creatlist_L() ///////尾插入法建立单链表 {
LinkList L,p,r; int x;
r=L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
cin>>x;
while(x!=0) { p=(LinkList)malloc(sizeof(LNode)); }
return L; }
LinkList Show_L(LinkList L) {
LinkList p2; p2=L;
while(p2->next!=NULL) { }
cout<
return L; }
LinkList Contlist_L(LinkList A,LinkList B) {
LinkList C,a,b,e,f; a=A->next;
b=B->next;
C=A; ////C表的头节点 f=C=(LinkList)malloc(sizeof(LNode));
C->next=NULL; //////建立空链表 while(a) {
e=(LinkList)malloc(sizeof(LNode)); e->data=a->data; e->next=NULL; f->next=e; f=e;
a=a->next;