第二章 线性表.docx
- 文档编号:13737643
- 上传时间:2023-06-16
- 格式:DOCX
- 页数:70
- 大小:72.38KB
第二章 线性表.docx
《第二章 线性表.docx》由会员分享,可在线阅读,更多相关《第二章 线性表.docx(70页珍藏版)》请在冰点文库上搜索。
第二章线性表
第二章 线性表
2.5实训
【实训1】顺序表的应用
1.实训说明
本实训是有关线性表的顺序存储结构的应用,在本实训的实例程序中,通过C语言中提供的数组来存储两个已知的线性表,然后利用数组元素的下标来对线性表进行比较。
通过对本实训的学习,可以理解线性表在顺序存储结构下的操作方法。
在实训中,我们设A=(a1,a2,…,an)和B=(b1,b2,…,bm)是两个线性表,其数据元素的类型是整型。
若n=m,且ai=bi,则称A=B;若ai=bi,而aj
设计一比较大小的程序。
2.程序分析
已知A和B是两个线性表,且其数据元素为整型数据,因此,可以使用线性表的顺序存储结构来实现,在C语言中,可以使用一维数组来存储顺序表。
1)初始化两个线性表:
输入两个数组A和B。
2)调用子函数intcompare(intA[],intB[],intm)比较两个数组的大小:
比较A[i]和B[i]:
若A[i]>B[i]返回BIG
若A[i]
若A[i]==B[i]且i 3.程序源代码 该实例程序的源代码如下: #include"stdio.h" #defineMAXSIZE100/*最大数组元素个数*/ #defineBIG1 #defineSMALL-1 #defineEQUAL0 intcompare(intA[],intB[],intm)/*比较数组数据*/ {inti; for(i=0;i {if(A[i]>B[i]) returnBIG;/*返回在A>B*/ else if(A[i] returnSMALL;/*返回在A } returnEQUAL;/*返回在A=B*/ } /*主程序*/ main() {intA[MAXSIZE],B[MAXSIZE]; intm,s,i; printf("请输入数据的大小m(0-100): "); scanf("%d",&m); while(m<=0&&m>=MAXSIZE) {printf("请输入数据的大小m(0-100): "); scanf("%d",&m);} for(i=0;i {printf("请输入数组A的第%d个数组元素",i+1); scanf("%d",&A[i]);} for(i=0;i {printf("请输入数组B的第%d个数组元素",i+1); scanf("%d",&B[i]);} s=compare(A,B,m); if(s==BIG) printf("数组A大于数组B"); else if(s==SMALL) printf("数组A小于数组B"); else printf("数组A等于数组B");} 最后程序运行结果如下所示: 请输入数据的大小m(0-100): 3↙<回车> 请输入数据A的第1个数组元素1↙<回车> 请输入数据A的第2个数组元素2↙<回车> 请输入数据A的第3个数组元素3↙<回车> 请输入数据B的第1个数组元素1↙<回车> 请输入数据B的第2个数组元素2↙<回车> 请输入数据B的第3个数组元素4↙<回车> 数组A小于数组B 【实训2】链表的应用 1.实训说明 本实训是有关线性表的链式存储结构的应用,在本实训的实例程序中,通过C语言中提供的结构指针来存储线性表,利用malloc函数动态地分配存储空间。 通过对本实训的学习,可以理解线性表在链序存储结构下的操作方法。 在实训中,我们设计一个程序求出约瑟夫环的出列顺序。 约瑟夫问题的一种描述是: 编号为1,2,…,n的n个人按顺时针方向围坐一圈,每个人持有一个密码(正整数)。 一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。 报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。 例如,n=7,7个人的密码依次为: 3,1,7,2,4,8,4,m的初值取6,则正确的出列顺序应为6,1,4,7,2,3,5。 要求使用单向循环链表模拟此出列过程。 2.程序分析 约瑟夫环的大小是变化的,因此相应的结点也是变化的,使用链式存储结构可以动态的生成其中的结点,出列操作也非常简单。 用单向循环链表模拟其出列顺序比较合适。 用结构指针描述每个人: structJoseph {intnum;/*环中某个人的序号*/ intsecret;/环中某个人的密码*/ structJoseph*next;/指向其下一个的指针*/}; 1)初始化约瑟夫环: 调用函数structJoseph*creat()生成初始约瑟夫环。 在该函数中使用head指向表头。 输入序号为0时结束,指针p1指向的最后结束序号为0的结点没有加入到链表中,p2指向最后一个序号为非0的结点(最后一个结点)。 2)报数出列: 调用函数voilsort(structJoseph*head,intm),使用条件p1->next! =p1判断单向链表非空,使用两个指针变量p1和p2,语句p2=p1;p1=p1->next;移动指针,计算结点数(报数);结点p1出列时直接使用语句: p2->next=p1->next,取出该结点中的密码作为新的循环终值。 3.程序源代码 该实例程序的源代码如下: #defineNULL0 #defineLENGTHsizeof(structJoseph) #include"stdlib.h" #include"stdio.h" structJoseph {intnum; intsecret; structJoseph*next; };/*定义结点num为序号,secret为密码*/ /*创建初始链表函数*/ structJoseph*creat() {structJoseph*head; structJoseph*p1,*p2; intn=0; p1=p2=(structJoseph*)malloc(LENGTH); scanf("%d,%d",&p1->num,&p1->secret); head=NULL; while(p1->num! =0) {n=n+1; if(n==1)head=p1; elsep2->next=p1; p2=p1; p1=(structJoseph*)malloc(LENGTH); scanf("%d,%d",&p1->num,&p1->secret); } p2->next=head; return(head); } /*报数出列*/ voidsort(structJoseph*head,intm) {structJoseph*p1,*p2; inti; if(head==NULL) printf("\n链表为空! \n"); p1=head; while(p1->next! =p1) {for(i=1;i {p2=p1;p1=p1->next;} p2->next=p1->next; m=p1->secret; printf("%d",p1->num); p1=p2->next; } if(p1->next==p1) printf("%d",p1->num); } main() {structJoseph*head; intm; printf("\n输入数据: 数据格式为序号,密码\n输入0,0为结束\n"); head=creat(); printf("输入m值\n"); scanf("%d",&m); if(m<1)printf("error! 请输入一个合法的m值! "); printf("出列的序号是: \n"); sort(head,m); } 最后程序运行结果如下所示: 输入数据: 数据格式为序号,密码 输入0,0为结束 1,3↙<回车> 2,1↙<回车> 3,7↙<回车> 4,2↙<回车> 5,4↙<回车> 6,8↙<回车> 7,4↙<回车> 0,0↙<回车> 输入m值 6↙<回车> 出列的序号是 6147235 第三章栈和队列 3.4实训 【实训1】栈的应用 1.实训说明 本实训是关于栈的应用,栈在各种高级语言编译系统中应用十分广泛,在本实训程序中,利用栈的“先进后出”的特点,分析C语言源程序代码中的的括号是否配对正确。 通过本对本实训的学习,可以理解的基本操作的实现。 本实训要求设计一个算法,检验C源程序代码中的括号是否正确配对。 对本算法中的栈的存储实现,我们采用的是顺序存储结构。 要求能够在某个C源程序上文件上对所设计的算法进行验证。 2.程序分析 (1)intinitStack(sqstack**s)初始化一个栈 (2)intpush(sqstack*s,charx)入栈,栈满时返回FALSE (3)charpop(sqstack*s)出栈,栈空时返回NULL (4)intEmpty(sqstack*s)判断栈是否为空,为空时返回TRUE (5)intmatch(FILE*f)对文件指针f对指的文件进行比较括号配对检验,从文件中每读入一个字符ch=fgetc(f),采用多路分支switch(ch)进行比较: ①若读入的是“[”、“{”或“(”,则压入栈中, ②若读入的是“]”,则: 若栈非空,则出栈,判断出栈符号是否等于“[”,不相等,则返回FALSE。 ③若读入的是“}”,则: 若栈非空,则出栈,判断出栈符号是否等于“{”,不相等,则返回FALSE。 ④若读入的是“)”,则: 若栈非空,则出栈,判断出栈符号是否等于“(”,不相等,则返回FALSE。 ⑤若是其它字符,则跳过。 文件处理到结束时,如果栈为空,则配对检验正确,返回TRUE。 (6)主程序main()中定义了一个文件指针,输入一个已经存在的C源程序文件。 3.程序源代码 #defineMAXNUM200 #defineFALSE0 #defineTRUE1 #include"stdio.h" #include"stdlib.h" #include"string.h" typedefstruct{ charstack[MAXNUM]; inttop;}sqstack;/*定义栈结构*/ intinitStack(sqstack**s) {/*初始化栈*/ if((*s=(sqstack*)malloc(sizeof(sqstack)))==NULL)returnFALSE; (*s)->top=-1; returnTRUE; } intpush(sqstack*s,charx) {/*将元素x插入到栈s中,作为s的新栈顶*/ if(s->top>=MAXNUM-1)returnFALSE;/*栈满*/ s->top++; s->stack[s->top]=x; returnTRUE; } charpop(sqstack*s) {/*若栈s不为空,则删除栈顶元素*/ charx; if(s->top<0)returnNULL;/*栈空*/ x=s->stack[s->top]; s->top--; returnx; } intEmpty(sqstack*s) {/*栈空返回TRUE,否则返回FALSE*/ if(s->top<0)returnTRUE; returnFALSE;} intmatch(FILE*f) {charch,ch1;sqstack*S; initStack(&S); while(! feof(f)) {ch=fgetc(f); switch(ch) {case'(': case'[': case'{': push(S,ch);printf("%c",ch);break; case')': if(Empty(S)! =TRUE) {ch1=pop(S);printf("%c",ch); if(ch1=='(') break; else returnFALSE;} else returnFALSE; case']': if(Empty(S)! =TRUE) {ch1=pop(S);printf("%c",ch); if(ch1=='[') break; else returnFALSE;} else returnFALSE; case'}': if(Empty(S)! =TRUE) {ch1=pop(S);printf("%c",ch); if(ch1=='{') break; else returnFALSE;} else returnFALSE; default: break; } } if(Empty(S)! =TRUE) returnFALSE; returnTRUE;} voidmain() {FILE*fp;charfn[20]; printf("请输入文件名: "); scanf("%s",fn); if((fp=fopen(fn,"r"))==NULL) {printf("不能打开文件\n"); exit(0);} elseif(match(fp)==TRUE) printf("括号正确\n"); else printf("括号不正确\n"); fclose(fn); } 最后程序运行结果如下所示: 请输入文件名: F: \exam.c<回车> (){[]()}括号正确 【实训2】队列的应用 1.实训说明 本实训是队列的一种典型的应用,队列是一种“先到先服务”的特殊的线性表,本实训要求模拟手机短信功能,使用链式存储结构的队列,进行动态地增加和删除结点信息。 通过本实训的学习,可以理解队列的基本操作的实现。 设计程序要求,模拟手机的某些短信息功能。 功能要求: (1)接受短信息,若超过存储容量(如最多可存储20条),则自动将最早接受的信息删除。 (2)显示其中任意一条短信息。 (3)逐条显示短信息。 (4)删除其中的任意一条短信息。 (5)清除。 2.程序分析 采用结构体指针定义存储短信结点: typedefstructQnode {chardata[MAXNUM];/*字符数组存储短信*/ structQnode*next; }Qnodetype;/*定义队列的结点*/ 定义队列: typedefstruct {Qnodetype*front;/*头指针*/ Qnodetype*rear;/*尾指针*/ intnumber;/*短信数量*/ }Lqueue; (1)intinitLqueue(Lqueue**q)初始化短信队列。 (2)intLInQueue(Lqueue*q,charx[])入队列,将字符串x加入到队列尾部。 (3)char*LOutQueue(Lqueue*q)出队列,删除队头元素,返回其中的字符串。 (4)voidget(Lqueue*q,charx[])接收短数,若短信数量超过20条,则删除队头短信。 (5)voiddeleteall(Lqueue*q)清除所有短信。 (6)voiddeleteone(Lqueue*q,intn)删除第n条短信。 (7)voiddisplayall(Lqueue*q)显示所有短信。 (8)voiddisplayone(Lqueue*q,intn)显示第n条短信。 在main()函数中,采用菜单方式,菜单中同时显示出已有的短信数量,由用户选择输入命令,实现程序要求功能,命令说明: R(r): 接收短信 L(l): 显示任意一条短信 A(a): 显示所有短信 D(d): 删除任意一条短信 U(u): 删除所有短信 Q(q): 退出 3.程序源代码 #defineMAXNUM70 #defineFALSE0 #defineTRUE1 #include"stdio.h" #include"stdlib.h" #include"string.h" typedefstructQnode {chardata[MAXNUM]; structQnode*next; }Qnodetype;/*定义队列的结点*/ typedefstruct {Qnodetype*front;/*头指针*/ Qnodetype*rear;/*尾指针*/ intnumber;/*短信数量*/ }Lqueue; intinitLqueue(Lqueue**q) {/*创建一个空链队列q*/ if(((*q)->front=(Qnodetype*)malloc(sizeof(Qnodetype)))==NULL)returnFALSE; (*q)->rear=(*q)->front;strcpy((*q)->front->data,"head"); (*q)->front->next=NULL;(*q)->number=0; returnTRUE;} intLInQueue(Lqueue*q,charx[]) {/*将元素x插入到链队列q中,作为q的新队尾*/ Qnodetype*p; if((p=(Qnodetype*)malloc(sizeof(Qnodetype)))==NULL)returnFALSE; strcpy(p->data,x); p->next=NULL; /*置新结点的指针为空*/ q->rear->next=p;/*将链队列中最后一个结点的指针指向新结点*/ q->rear=p;/*将队尾指向新结点*/ returnTRUE; } char*LOutQueue(Lqueue*q) {/*若链队列q不为空,则删除队头元素,返回其元素值*/ charx[MAXNUM]; Qnodetype*p; if(q->front->next==NULL)returnNULL;/*空队列*/ p=q->front->next;/*取队头*/ q->front->next=p->next;/*删除队头结点*/ if(p->next==NULL)q->rear=q->front; strcpy(x,p->data); free(p); returnx; } voidget(Lqueue*q,charx[]) {/*接受短信*/ intn; if(q->number==20) {LOutQueue(q);q->number--;} LInQueue(q,x); q->number++;} voiddeleteall(Lqueue*q) {/*删除所有短信*/ while(q->front! =q->rear) LOutQueue(q);q->number=0;} voiddeleteone(Lqueue*q,intn) {/*删除第n条短信*/ Lqueue*p;Qnodetype*s; inti; p=q;i=1; while(i {p->front=p->front->next; i=i+1;} s=p->front->next; p->front->next=p->front->next->next; free(s); q->number--;} voiddisplayall(Lqueue*q) {/*显示所有短信*/ Lqueue*p;charx[MAXNUM]; p=q; while(p->front! =q->rear) { p->front=p->front->next; printf("%s\n",p->front->data); }printf("\n"); } voiddisplayone(Lqueue*q,intn) {/*显示第n条短信*/ Lqueue*p;Qnodetype*s; inti; p=q;i=1; while(i {p->front=p->front->next; i=i+1;} s=p->front->next; printf("%s\n",s->data); } voidmain() {Lqueue*Lp;inti;Qnodetype*headnode; charcommand,ch[MAXNUM]; initLqueue(&Lp);headnode=Lp->front; while (1) {printf("Getinformation(%d),pleaseenterR\n",Lp->number); printf("Displayoneinformation(%d),pleaseenterL\n",Lp->number); printf("Displayallinformation(%d),pleaseenterA\n",Lp->number); printf("Deleteoneinformation(%d),pleaseenterD\n",Lp->number); printf("Deleteallinformation(%d),pleaseenterU\n",Lp->number); printf("Quit,pleaseenterQ\n"); printf("pleaseinputcommand: "); scanf("%c",&command); switch(command) {case'r': case'R': gets(ch);Lp->front=headnode;get(Lp,ch);break; case'l': case'L': printf("enterNo.: "),scanf("%d",&i); Lp->front=headnode;displayone(Lp,i);break; case'a': case'A': Lp->front=headnode;displayall(Lp);break; case'd': case'D': printf("
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二章 线性表 第二 线性