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