《数据结构实验与实训教程(第3版)》课件

i目录第一部分预备知识...........................................................................................................................1预备知识.....................................................................................................................................1预备知识实验.............................................................................................................................2第二部分基础实验...........................................................................................................................4实验1线性表的基本操作......................................................................................................4实验2链表的基本操作..........................................................................................................9实验3栈的基本操作............................................................................................................15实验4队列的基本操作........................................................................................................22实验5数组的基本操作........................................................................................................32实验6字符串的基本操作....................................................................................................36实验7二叉树的基本操作....................................................................................................41实验8树的遍历和哈夫曼树................................................................................................46实验9图的基本操作............................................................................................................53实验10排序......................................................................................................................59实验11查找......................................................................................................................64第三部分课程设计实验.................................................................................................................69实验1航空客运订票系统......................................................................................................69实验2汉诺塔游戏程序..........................................................................................................75实验3全屏幕编辑程序设计..................................................................................................79实验4旅游路线安排模拟系统..............................................................................................90实验6最小生成树kruskal算法.............................................................................................931第一部分预备知识预备知识例1．1#includestdio.hintsumabc(inta,intb,intc)/*求三个整数之和*/{ints;a=b+c;s=a+b+c;returns;}voiddisplayLine(void){printf(”----------------------\n“);}voidmain(){intx,y,z,sabc;x=y=z=8;display();/*画一条线*/printf(“\nsum=%d”,sumabc(x,y,z));/*在输出语句中直接调用函数sumabc()*/printf(“\n%6d%6d%6d”,x,y,z);display();/*画一条线*/x=2;y=4;z=6;sabc=sumabc(x,y,z);/*在赋值语句中调用函数sumabc()*/printf(“\n“sum=%d”,sabc);printf(“\n%6d%6d%6d”,x,y,z);display();/*画一条线*/}例1.2intsumabc(int*a,intb,intc){ints;*a=b+c;s=*a+b+c;2returns;}预备知识实验intmain(){//在main函数中调用上述声明的函数intn;//记录个数STUDENTstu[MAXSIZE;//顺序存储结构，方法一静态一维数组。/*顺序存储结构，方法二动态一维数组，用malloc函数分配如下：STUDENT*stu;stu=(STUDENT*)malloc(sizeof(STUDENT)*MAXSIZE);//内存空间的分配注意：分配空间可用malloc()函数,释放空间用free()函数，如free(stu);*/intindex;printf(\n请输入学生记录个数n=);scanf(%d”,&n);InputStu(stu,n);//预先处理输入,建表while(1)//永真循环,重复显示菜单,直至退出{printf(\n**********************学生信息管理主菜单**********************\n);printf(\t1.显示学生信息\n);printf(\t2.查找学生信息\n);printf(\t3.修改学生信息\n);printf(\t4.添加学生信息\n);printf(\t5.退出\n\n);printf(\t\t请选择(1~5):);scanf(%d,&index);printf(\n**************************************************************\n);switch(index){case1:OutputStu(stu,n);break;case2:SearchStu(stu,n);break;case3:UpdateStu(stu,n);break;case4:AppendStu(stu,&n);break;case5:return0;default:printf(\n输入有误,请重新输入!\n);}//switch3}//while（1）}//main4第二部分基础实验实验1线性表的基本操作四、参考程序程序1：题1线性表基本操作函数#includestdio.h#includestdlib.h#includealloc.hstructLinearList／*定义线性表结构*/{int*list;/*存线性表元素*/intsize;/*存线性表长度*/intMaxSize;/*存list数组元素个数*/};typedefstructLinearListLIST;voidInitList(LIST*L,intms)/*初始化线性表*/{if((L-list=1)==NULL){printf(内存申请错误!\n);exit(1);}2L-MaxSize=ms;}intInsertList(LIST*L,intitem,intrc)/*item:记录值rc:插入位置*/{inti;if(3)/*线性表已满*/return-1;if(rc0)/*插入位置为0--L-size*/5rc=0;if(4)rc=L-size;for(i=L-size-1;i=rc;i--)/*将线性表元素后移*/5L-list[rc]=item;L-size++;return0;}voidOutputList(LIST*L)/*输出线性表元素*/{inti;for(i=0;6i++)printf(%d,L-list[i]);printf(\n);}intFindList(LIST*L,intitem)/*返回=0为元素位置-1没找到*/{inti;for(i=0;iL-size;i++)if(7)/*找到相同的元素，返回位置*/returni;return-1;/*没找到*/}intDeleteList1(LIST*L,intitem)/*删除指定元素值的线性表记录，返回=0：删除成功*/{inti,n;for(i=0;iL-size;i++)if(item==L-list[i])/*找到相同的元素*/break;if(iL-size){for(n=i;nL-size-1;n++)L-list[n]=L-list[n+1];L-size--;returni;}6return-1;}intDeleteList2(LISTL,intrc)/*删除指定位置的线性表记录*/{8/*编写删除指定位置的线性表记录子程序*/}程序2：题2voidmain(){LISTLL;inti,r;printf(listaddr=%p\tsize=%d\tMaxSize=%d\n,LL.list,LL.size,LL.MaxSize);InitList(&LL,100);printf(listaddr=%p\tsize=%d\tMaxSi