实验一 线性表实验目的掌握用Turbo C 2.0上机调试线性表的基本方法。
掌握线性表基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和连接存储结构上的运算。
实验内容线性表基本操作的实现
[问题描述] 当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若欲删除第i个元素时，也必须把第i元素之后的所以元素前移一个位置。
[基本要求] 要求生成线性表时，可以键盘上读取元素，用顺序存储结构和连式存储结构实现存储。
[实现提示] 要实现基本操作可用已实现的基本操作，也可设计简单的算法实现
[算法实现]
typedef null 0;
typedef int datatype;
#define maxsize 1024;
typedef struct
{ datatype data[maxsize]; /*定义线性表是向量，第一接点是data[0]*/
int last;
}sequenlist;
/*插入函数*/
int insert(L,x,i) /*将新接点x插入到顺序表l第i个位置
sequenlist *L; /*l是sequenlist类型的指针变量
int i;
{ int j;
if （（*l）.last==maxsize-1）
{ printif(“overflow”);
return null;}
else
if((i<1)||(i>(*l).last+1)
{ printf(“error”);
return null;}
else
{ for(j=（*l）.last;j>=i-1;j--)
(*l).data[j+1](*l).data[j]; /*接点后移
(*l).data[I-1]=x; /*?插入x
(*l).last+1; } /*表长加一
return (1);
}
/*删除运算
int delete(L,i)/*删除第i个接点
sequenlist *L;
int i;
{ int j;
if((i<1)||(i>(*L).last+1)
{ printf(“error”);
return null; }
else
{ for (j=i;j<=(*L).last;j++)
(*l).data[j-1]=(*L).data[j];
(*L).last--; }
return (1);
}
/*生成线性表
void ceatlist()
{ sequentlist *L;
int n,I,j;
printf(“请输入n个数据\n”)；
scanf(“%d”,&n);
for(i=0,i<n,i+);
{ printf(“data[%d]=”,i);
scanf(“%d”&(*L).&data[i]);
}
(*L).last=n-1;
printf(“”\n”);
}
/*输出线性表
printout(L)
sequenlist *L;
{ int i;
for(I=0;i<(*L).last;i++)
{ printf(“data[%d]=”,i);
printf(“%d”,(*L).data[i]);
}
}
/*主程序开始
main()
{ sequenlist *L;
char cmd’
int i,t;
clscr();
printf(“i I 插入\n”);
printf(“d D 删除\n”);
printf(“q Q 退出\n”);
do
{ do
{ do{cmd=getchar();
}while((cmd!=’d’)||(cmd!=’D’)||(cmd!=’q’)||(cmd!=’Q’)||(cmd!=’i’)||(cmd!=I));
switch(cmd)
{ case ‘i’,’I’,scanf(&i);
insert(L,i);
printout(L);
break;
case ‘d’,’D’,scanf(&i);
delete(L,i);
printout(L);
break;
}
}while((cmd!=’q’||(cmd!=’D’));
}
2．约瑟夫问题
[问题描述]设有n个人围坐一圈，先从某个人开始报数，数m到的人出列,接着从出列的下一个开始重新报数，数到的M人又出列，一直下去直到所有的人出列，试设计确定他们的出列次序序列的程序。
[基本要求]选择单向循环链表作为存储结构模拟过程，并依次输出出列各人的编号。
[实现提示]程序运行之后，首先要求用户初始报数的上限值，可以n<=30,此题中循环链表可不设头接点，而且必须清楚空表和非空表的界限。如：n=8,m=4时，若从第一个人开始，设没各人的编号依次1、2、3、4…开始报数，则得到的出列次序为4 8 5 2 1 3 7 6。
[程序实现]：
struct node
{ int num;
struct node *next;
} linklist;
/*建立连表
linklist *creat(head,n)/使n个人围成一圈,并给每个人标志号数
linklist *head
int n;
{ linklist *s,*p;
int i;
s=malloc(sizeof(linklist));
head=s;
s->num=1;
p=s;
for(i=2;i<=n;i++);
{ s=malloc(sizeof(linklist));
s->num=i;
p->next=s;
p=s;
}
p->next=head;
return head;
}
linklist *select(head,m)
linklist *head;
int m;
{ linklist *p,*q;
int i,t;
p=head;t=1;
p=q; /*q为p的前驱指针
do{
p=q->next; /*指向当前报数的人
t=t+1;
if(t%m==0)
{
printf(“%4d”,p->num);
q->next=p->next;
free(p);
p=q;
}
else
p=q;
} while(p==q);
head=p;
}
/*主程序
main()
{ int n,m;
linklist *head;
scanf(&n);
scanf(&m);
creat(head,n);
select(head,m);
printf(“the last one:is%d”,head-num);
}
思考题：用环形数组来实现一元多项式简单计算
[问题描述] 设计一个一元多项式的简单计算器
[基本要求]一元多项式的基本功能：
输入并建立多项式输出多项式两个多项式相加减，相乘除，建立并输出多项式
[实现提示]可选择带头接点的单向循环链表或单项链表存储多项式，头接点可以存储多项式的参数如项数等。
[程序实现]这里利用单链表作为存储多项式的结构：单链表定义如下,#define null 0
#define true 1
#define false 0
struct mulpoly
{ int coef ;/*系数
int exp; /*指数
struct mulpoly next; }
假设输入一组多项式的系数和指数，以输入实数0为结束标记，这里建立多项式时，总是按指数从大到小排列。
/*产生多项式链表，设头指针为head
struct mulpoly creatpoly()
{ struct mulpoly *head,*r,*s;
int m,n;
head =(struct mulpoly *)malloc(sizeof(struct mulpoly));
scanf(“%d,%d”&n,&m)；
r=head;
while(n) /*n不等于0时建立多项式连表
{ s=(struct mulpoly )malloc(sizeof(struct mulpoly)); /*建立一个新结点
s->coef=n;
s->exp=m;
r->next=s; /*把*S链接到*R后面
r=s;
printf(“input coef and exp:\n”);
scanf(“%d,%d”,&n,&m);
}
r->next=null;
head=head->next;
return (head);
}
/*a+b实现多项式相加：
/*两多项式相加运算ha hb 分别是A、B连表的头指针,相加后存放到多项式C，头指针为hc
struct mulpoly polyadd(ha,hb)
struct mulpoly *ha,*hb;
{ struct mulpoly *hc,*p,*q,*s,*r;
int x;
p=ha;
q=hb;
hc=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
s=hc;
while((p!=null)&&(q!=null))
{if(p->ext==q->ext) /*两个接点指数相等
{ x=p->coef+q->coef; /*系数相加
if(x!=0)
{r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=x;
s->next=r;
s=r; }
p=p->next;
q=q->next;
}
else/*两结点指数不相等
if(p->next<q->next)
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
else /* p->next>q->next时
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=q->exp;
r->coef=q->coef;
s->next=r;
s=r;
q=q->next;
}
}
while(p) /* p!=NULL复制A的剩余部分
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
while(q) /* q!=NULL复制B的剩余部分
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=q->exp;
r->coef=q->coef;
s->next=r;
s=r;
q=q->next;
}
s->next=null; /*链成单链表
r=hc;
hc=hc->next;
free ( r );
return(hc);
}
相减运算，实际上也是多项式相加的运算，无非是各项的系数符号不等而已。而多项式的乘法运算可说明如下。
/*多项式相乘
struct mulpoly * polymulti(f,g)
struct mulpoly *f,*g;
{ mulpoly *fp,*gp,*q,*h;
int maxp,p,r,x;
extern reverse(mulpoly *p);
maxp=f->exp+q->exp;
h=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
hp=h;
reverse(g);
for(r=maxp;r>=0;r--)
{ x=0;fp=f;gp=g;
while((fq!=null)&&(gp!=null))
{ p=fp->exp=gp->exp;
if(p>r)
fp=fp->next;
else
if(p<r)
gp=gp->next;
else
{ x+=fp->coef*gp->coef;
fp=fp->next;
gp=gp->next; }
} /* end of while
if (abs(x)>le-6)
{ p=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
q->exp=r;
q->coef=x;
q(next=null;
hp->next=q;
hp=q;
}
} /* end of for
hp=h;
h=h->next;
free(hp);
return h;
}
其中的reverse函数说明如下
reverse(q)
mulpoly *q;
{ mulpoly *p1,*p2;
if(q!=null)
{ p1=q->next;
q->next=null;
while(p1!=null)
{ p2=p1->next;
p1->next=q;
q=p1;
p1=p2;
}
}
多项式的输出的输出，实际上就是单链表的输出，只是该单链表的数据域含有系数和指示两部分而已。
/*多项式的输出
ployout(head)
mulpoly *head;
{ mulploy *p,*q ;
p=head->next;
while(p!=NULL)
{ printf(“%d,%d”,p->coef,p->exp);
p=p->next;
}
}
整个实现的主程序如下：
void main()
{ mulpoly *ha,*hb,*hc,*p,*q,*h;
ha=creatpoly();
polyout(ha);
hb=creatpoly();
polyout(hb);
hc=polyadd(ha,hb)’;
polyout(hc);
h=polymulti(ha,hb);
polyout(hc);
}
掌握线性表基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和连接存储结构上的运算。
实验内容线性表基本操作的实现
[问题描述] 当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若欲删除第i个元素时，也必须把第i元素之后的所以元素前移一个位置。
[基本要求] 要求生成线性表时，可以键盘上读取元素，用顺序存储结构和连式存储结构实现存储。
[实现提示] 要实现基本操作可用已实现的基本操作，也可设计简单的算法实现
[算法实现]
typedef null 0;
typedef int datatype;
#define maxsize 1024;
typedef struct
{ datatype data[maxsize]; /*定义线性表是向量，第一接点是data[0]*/
int last;
}sequenlist;
/*插入函数*/
int insert(L,x,i) /*将新接点x插入到顺序表l第i个位置
sequenlist *L; /*l是sequenlist类型的指针变量
int i;
{ int j;
if （（*l）.last==maxsize-1）
{ printif(“overflow”);
return null;}
else
if((i<1)||(i>(*l).last+1)
{ printf(“error”);
return null;}
else
{ for(j=（*l）.last;j>=i-1;j--)
(*l).data[j+1](*l).data[j]; /*接点后移
(*l).data[I-1]=x; /*?插入x
(*l).last+1; } /*表长加一
return (1);
}
/*删除运算
int delete(L,i)/*删除第i个接点
sequenlist *L;
int i;
{ int j;
if((i<1)||(i>(*L).last+1)
{ printf(“error”);
return null; }
else
{ for (j=i;j<=(*L).last;j++)
(*l).data[j-1]=(*L).data[j];
(*L).last--; }
return (1);
}
/*生成线性表
void ceatlist()
{ sequentlist *L;
int n,I,j;
printf(“请输入n个数据\n”)；
scanf(“%d”,&n);
for(i=0,i<n,i+);
{ printf(“data[%d]=”,i);
scanf(“%d”&(*L).&data[i]);
}
(*L).last=n-1;
printf(“”\n”);
}
/*输出线性表
printout(L)
sequenlist *L;
{ int i;
for(I=0;i<(*L).last;i++)
{ printf(“data[%d]=”,i);
printf(“%d”,(*L).data[i]);
}
}
/*主程序开始
main()
{ sequenlist *L;
char cmd’
int i,t;
clscr();
printf(“i I 插入\n”);
printf(“d D 删除\n”);
printf(“q Q 退出\n”);
do
{ do
{ do{cmd=getchar();
}while((cmd!=’d’)||(cmd!=’D’)||(cmd!=’q’)||(cmd!=’Q’)||(cmd!=’i’)||(cmd!=I));
switch(cmd)
{ case ‘i’,’I’,scanf(&i);
insert(L,i);
printout(L);
break;
case ‘d’,’D’,scanf(&i);
delete(L,i);
printout(L);
break;
}
}while((cmd!=’q’||(cmd!=’D’));
}
2．约瑟夫问题
[问题描述]设有n个人围坐一圈，先从某个人开始报数，数m到的人出列,接着从出列的下一个开始重新报数，数到的M人又出列，一直下去直到所有的人出列，试设计确定他们的出列次序序列的程序。
[基本要求]选择单向循环链表作为存储结构模拟过程，并依次输出出列各人的编号。
[实现提示]程序运行之后，首先要求用户初始报数的上限值，可以n<=30,此题中循环链表可不设头接点，而且必须清楚空表和非空表的界限。如：n=8,m=4时，若从第一个人开始，设没各人的编号依次1、2、3、4…开始报数，则得到的出列次序为4 8 5 2 1 3 7 6。
[程序实现]：
struct node
{ int num;
struct node *next;
} linklist;
/*建立连表
linklist *creat(head,n)/使n个人围成一圈,并给每个人标志号数
linklist *head
int n;
{ linklist *s,*p;
int i;
s=malloc(sizeof(linklist));
head=s;
s->num=1;
p=s;
for(i=2;i<=n;i++);
{ s=malloc(sizeof(linklist));
s->num=i;
p->next=s;
p=s;
}
p->next=head;
return head;
}
linklist *select(head,m)
linklist *head;
int m;
{ linklist *p,*q;
int i,t;
p=head;t=1;
p=q; /*q为p的前驱指针
do{
p=q->next; /*指向当前报数的人
t=t+1;
if(t%m==0)
{
printf(“%4d”,p->num);
q->next=p->next;
free(p);
p=q;
}
else
p=q;
} while(p==q);
head=p;
}
/*主程序
main()
{ int n,m;
linklist *head;
scanf(&n);
scanf(&m);
creat(head,n);
select(head,m);
printf(“the last one:is%d”,head-num);
}
思考题：用环形数组来实现一元多项式简单计算
[问题描述] 设计一个一元多项式的简单计算器
[基本要求]一元多项式的基本功能：
输入并建立多项式输出多项式两个多项式相加减，相乘除，建立并输出多项式
[实现提示]可选择带头接点的单向循环链表或单项链表存储多项式，头接点可以存储多项式的参数如项数等。
[程序实现]这里利用单链表作为存储多项式的结构：单链表定义如下,#define null 0
#define true 1
#define false 0
struct mulpoly
{ int coef ;/*系数
int exp; /*指数
struct mulpoly next; }
假设输入一组多项式的系数和指数，以输入实数0为结束标记，这里建立多项式时，总是按指数从大到小排列。
/*产生多项式链表，设头指针为head
struct mulpoly creatpoly()
{ struct mulpoly *head,*r,*s;
int m,n;
head =(struct mulpoly *)malloc(sizeof(struct mulpoly));
scanf(“%d,%d”&n,&m)；
r=head;
while(n) /*n不等于0时建立多项式连表
{ s=(struct mulpoly )malloc(sizeof(struct mulpoly)); /*建立一个新结点
s->coef=n;
s->exp=m;
r->next=s; /*把*S链接到*R后面
r=s;
printf(“input coef and exp:\n”);
scanf(“%d,%d”,&n,&m);
}
r->next=null;
head=head->next;
return (head);
}
/*a+b实现多项式相加：
/*两多项式相加运算ha hb 分别是A、B连表的头指针,相加后存放到多项式C，头指针为hc
struct mulpoly polyadd(ha,hb)
struct mulpoly *ha,*hb;
{ struct mulpoly *hc,*p,*q,*s,*r;
int x;
p=ha;
q=hb;
hc=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
s=hc;
while((p!=null)&&(q!=null))
{if(p->ext==q->ext) /*两个接点指数相等
{ x=p->coef+q->coef; /*系数相加
if(x!=0)
{r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=x;
s->next=r;
s=r; }
p=p->next;
q=q->next;
}
else/*两结点指数不相等
if(p->next<q->next)
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
else /* p->next>q->next时
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=q->exp;
r->coef=q->coef;
s->next=r;
s=r;
q=q->next;
}
}
while(p) /* p!=NULL复制A的剩余部分
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=p->exp;
r->coef=p->coef;
s->next=r;
s=r;
p=p->next;
}
while(q) /* q!=NULL复制B的剩余部分
{ r=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
r->exp=q->exp;
r->coef=q->coef;
s->next=r;
s=r;
q=q->next;
}
s->next=null; /*链成单链表
r=hc;
hc=hc->next;
free ( r );
return(hc);
}
相减运算，实际上也是多项式相加的运算，无非是各项的系数符号不等而已。而多项式的乘法运算可说明如下。
/*多项式相乘
struct mulpoly * polymulti(f,g)
struct mulpoly *f,*g;
{ mulpoly *fp,*gp,*q,*h;
int maxp,p,r,x;
extern reverse(mulpoly *p);
maxp=f->exp+q->exp;
h=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
hp=h;
reverse(g);
for(r=maxp;r>=0;r--)
{ x=0;fp=f;gp=g;
while((fq!=null)&&(gp!=null))
{ p=fp->exp=gp->exp;
if(p>r)
fp=fp->next;
else
if(p<r)
gp=gp->next;
else
{ x+=fp->coef*gp->coef;
fp=fp->next;
gp=gp->next; }
} /* end of while
if (abs(x)>le-6)
{ p=(struct mulpoly *)malloc(sizeof(struct *mulpoly));
q->exp=r;
q->coef=x;
q(next=null;
hp->next=q;
hp=q;
}
} /* end of for
hp=h;
h=h->next;
free(hp);
return h;
}
其中的reverse函数说明如下
reverse(q)
mulpoly *q;
{ mulpoly *p1,*p2;
if(q!=null)
{ p1=q->next;
q->next=null;
while(p1!=null)
{ p2=p1->next;
p1->next=q;
q=p1;
p1=p2;
}
}
多项式的输出的输出，实际上就是单链表的输出，只是该单链表的数据域含有系数和指示两部分而已。
/*多项式的输出
ployout(head)
mulpoly *head;
{ mulploy *p,*q ;
p=head->next;
while(p!=NULL)
{ printf(“%d,%d”,p->coef,p->exp);
p=p->next;
}
}
整个实现的主程序如下：
void main()
{ mulpoly *ha,*hb,*hc,*p,*q,*h;
ha=creatpoly();
polyout(ha);
hb=creatpoly();
polyout(hb);
hc=polyadd(ha,hb)’;
polyout(hc);
h=polymulti(ha,hb);
polyout(hc);
}
