《数据结构》(C语言版)严蔚敏著-数据结构实验指导

1《数据结构》实验指导及报告书（2012）/学年第学期姓名：______________学号：______________班级：______________指导教师：______________信息科学与工程学院2012预备实验C语言的函数数组指针结构体知识一、实验目的1、复习C语言中函数、数组、指针、结构体与共用体等的概念。2、熟悉利用C语言进行程序设计的一般方法。二、实验预习说明以下C语言中的概念1、函数：2、数组：3、指针：4、结构体5、共用体三、实验内容和要求1、调试程序：输出100以内所有的素数（用函数实现）。#includestdio.hintisprime(intn){/*判断一个数是否为素数*/intm;for(m=2;m*m=n;m++)if(n%m==0)return0;return1;}intmain(){/*输出100以内所有素数*/inti;printf(\n);2for(i=2;i100;i++)if(isprime(i)==1)printf(%4d,i);return0;}运行结果：2、调试程序：对一维数组中的元素进行逆序排列。#includestdio.h#defineN10intmain(){inta[N]={0,1,2,3,4,5,6,7,8,9},i,temp;printf(\ntheoriginalArrayis:\n);for(i=0;iN;i++)printf(%4d,a[i]);for(i=0;iN/2;i++){/*交换数组元素使之逆序*/temp=a[i];a[i]=a[N-i-1];a[N-i-1]=temp;}printf(\nthechangedArrayis:\n);for(i=0;iN;i++)printf(%4d,a[i]);return0;}运行结果：3、调试程序：在二维数组中，若某一位置上的元素在该行中最大，而在该列中最小，则该元素即为该二维数组的一个鞍点。要求从键盘上输入一个二维数组，当鞍点存在时，把鞍点找出来。#includestdio.h#defineM3#defineN4intmain(){inta[M][N],i,j,k;printf(\n请输入二维数组的数据：\n);for(i=0;iM;i++)for(j=0;jN;j++)scanf(%d,&a[i][j]);for(i=0;iM;i++){/*输出矩阵*/for(j=0;jN;j++)printf(%4d,a[i][j]);printf(\n);}for(i=0;iM;i++){k=0;for(j=1;jN;j++)/*找出第i行的最大值*/if(a[i][j]a[i][k])k=j;for(j=0;jM;j++)/*判断第i行的最大值是否为该列的最小值*/if(a[j][k]a[i][k])break;3if(j==M)/*在第i行找到鞍点*/printf(%d,%d,%d\n,a[i][k],i,k);}return0;}运行结果：4、调试程序：利用指针输出二维数组的元素。#includestdio.hintmain(){inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23};int*p;for(p=a[0];pa[0]+12;p++){if((p-a[0])%4==0)printf(\n);printf(%4d,*p);}return0;}运行结果：5、调试程序：设有一个教师与学生通用的表格，教师的数据有姓名、年龄、职业、教研室四项，学生有姓名、年龄、专业、班级四项，编程输入人员的数据，再以表格输出。#includestdio.h#defineN10structstudent{charname[8];/*姓名*/intage;/*年龄*/charjob;/*职业或专业，用s或t表示学生或教师*/union{intclass;/*班级*/charoffice[10];/*教研室*/}depa;}stu[N];intmain(){inti;intn;printf(“\n请输入人员数(10):\n”);scanf(“%d”,&n);for(i=0;in;i++){/*输入n个人员的信息*/printf(\n请输入第%d人员的信息：(nameagejobclass/office)\n,i+1);scanf(%s,%d,%c,stu[i].name,&stu[i].age,&stu[i].job);if(stu[i].job==’s’)scanf(%d,&stu[i].depa.class);elsescanf(%s,stu[i].depa.office);}printf(“nameagejobclass/office”);for(i=0;in;i++){/*输出*/if(stu[i].job==’s’)printf(%s%3d%3c%d\n,stu[i].name,stu[i].age,stu[i].job,stu[i].depa.class);else4printf(%s%3d%3c%s\n,stu[i].name,stu[i].age,stu[i].job,stu[i].depa.office);}}输入的数据：2Wang19s99061Li36tcomputer运行结果：四、实验小结五、教师评语5实验一顺序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。二、实验预习说明以下概念1、线性表：2、顺序表：3、链表：三、实验内容和要求1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#includestdio.h#includemalloc.h#defineERROR0#defineOK1#defineINIT_SIZE5/*初始分配的顺序表长度*/#defineINCREM5/*溢出时，顺序表长度的增量*/typedefintElemType;/*定义表元素的类型*/typedefstructSqlist{ElemType*slist;/*存储空间的基地址*/intlength;/*顺序表的当前长度*/intlistsize;/*当前分配的存储空间*/}Sqlist;intInitList_sq(Sqlist*L);/**/intCreateList_sq(Sqlist*L,intn);/**/intListInsert_sq(Sqlist*L,inti,ElemTypee);/**/intPrintList_sq(Sqlist*L);/*输出顺序表的元素*/intListDelete_sq(Sqlist*L,inti);/*删除第i个元素*/intListLocate(Sqlist*L,ElemTypee);/*查找值为e的元素*/intInitList_sq(Sqlist*L){L-slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(!L-slist)returnERROR;L-length=0;L-listsize=INIT_SIZE;returnOK;}/*InitList*/intCreateList_sq(Sqlist*L,intn){ElemTypee;inti;for(i=0;in;i++){printf(inputdata%d,i+1);6scanf(%d,&e);if(!ListInsert_sq(L,i+1,e))returnERROR;}returnOK;}/*CreateList*//*输出顺序表中的元素*/intPrintList_sq(Sqlist*L){inti;for(i=1;i=L-length;i++)printf(%5d,L-slist[i-1]);returnOK;}/*PrintList*/intListInsert_sq(Sqlist*L,inti,ElemTypee){intk;if(i1||iL-length+1)returnERROR;if(L-length=L-listsize){L-slist=(ElemType*)realloc(L-slist,(INIT_SIZE+INCREM)*sizeof(ElemType));if(!L-slist)returnERROR;L-listsize+=INCREM;}for(k=L-length-1;k=i-1;k--){L-slist[k+1]=L-slist[k];}L-slist[i-1]=e;L-length++;returnOK;}/*ListInsert*//*在顺序表中删除第i个元素*/intListDelete_sq(Sqlist*L,inti){}/*在顺序表中查找指定值元素，返回其序号*/intListLocate(Sqlist*L,ElemTypee){}intmain(){Sqlistsl;intn,m,k;printf(pleaseinputn:);/*输入顺序表的元素个数*/scanf(%d,&n);if(n0){printf(\n1-CreateSqlist:\n);InitList_sq(&sl);CreateList_sq(&sl,n);printf(\n2-PrintSqlist:\n);PrintList_sq(&sl);7printf(\npleaseinputinsertlocationanddata:(location,data)\n);scanf(%d,%d,&m,&k);ListInsert_sq(&sl,m,k);printf(\n3-PrintSqlist:\n);PrintList_sq(&sl);printf(\n);}elseprintf(ERROR);return0;}运行结果算法分析2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。删除算法代码：运行结果算法分析查找算法代码：运行结果算法分析3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#includestdio.h#includemalloc.h#defineERROR0#defineOK1typedefintElemType;/*定义表元素的类型*/typedefstructLNode{/*线性表的单链表存储*/ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListCreateList(intn);/**/voidPrintList(LinkListL);/*输出带头结点单链表的所有元素*/intGetElem(LinkListL,inti,ElemType*e);/**/LinkListCreateList(intn){LNode*p,*q,*head;inti;head=(LinkList)malloc(sizeof(LNode));head-next=NULL;p=head;for(i=0;in;i++){q=(LinkList)malloc(sizeof(LNode));printf(inputdata%i:,i+1);scanf(%d,&q-data);/*输入元素值*/q-next=NULL;/*结点指针域置空*/p-next=q;/*新结点连在表末尾*/p=q;}returnhead;}/*CreateList*/voidPrintList(LinkListL){8LNode*p;p=L-next;/*p指向单链表的第1个元素*/while(p!=NULL){printf(%5d,p-data);p=p-next;}}/*PrintList*/i