数据结构机考.doc

29 / 29数据结构机考一熟悉C语言的文件操作1. 用随机函数产生1000 个整数（或浮点数），保存在文件（intfile.dat）中，然后将文件中的数据读取出来显示。（1）用fprintf 函数写入数据，要注意整数之间需要有分隔符号，所有数据写入后关闭文件；（写入数据时采用相同的场宽，例如，printf(“%10d”,ai);）（2）重新打开文件，用fscanf 函数逐个读取并显示数据；（3）用fwrite 函数向文件中写入数据，重新以读方式打开文件，用fseek 函数对文件指针进行定位，仅读取需要的数据。例如，分别将文件指针定位到第5 个整数、第10 个整数，读取这两个整数并显示；分别将文件指针定位到倒数第5 个整数、倒数第10 个整数，读取这两个整数并显示。源程序：#include#includeint main() FILE *fp,*in; int i,j; int a1000,b1000,p; fp=fopen(intfile.dat,w); if(fp=NULL) printf(open file error!); exit(0); for(i=0;i1000;i+) ai=rand(); fprintf(fp,%10d,ai); fclose(fp); in=fopen(intfile.dat,r); if(in=NULL) printf(open file error!); exit(0); while(!(feof(in) j=0; fscanf(in,%10d,&bj); printf(%d ,bj); j+; printf(nnn); fseek(in,40L,SEEK_SET); fscanf(in,%8d,&p); printf(%8d,p); fseek(in,40L,SEEK_CUR); fscanf(in,%8d,&p); printf(%8d,p); fseek(in,-100L,SEEK_END); fscanf(in,%8d,&p); printf(%8d,p); fseek(in,-50L,SEEK_END); fscanf(in,%8d,&p); printf(%8d,p); fclose(in); printf(n); system(pause); return 0;2. 建立一个由5 名学生信息组成的文件（studinfo.dat），其中，每个学生都有学号、姓名、性别和三门课程的成绩。（1）用结构体类型描述学生的基本信息，其中：学号和姓名用字符串表示，其长度定义参照本校的情况，课程名自行定义，成绩采用百分制；（2）学生信息由键盘输入，先存入结构体变量；（3）用fwrite 函数将结构体变量的值写入文件studinfo.dat；（4）用fread 函数从文件studinfo.dat 中读取数据并按一定格式显示在屏幕上（例如，每行显示一个学生信息，各项信息之间要有一定的间隔，所有学生的所有信息对齐显示等）源程序：#include#includetypedef struct char num10; char name20; int sex; /1代表男生，0代表女生 int Grade3;STUDENT;STUDENT stu5;int main() FILE *fp; int i,j; for(i=0;i5;i+) printf(num%d:,i+1); scanf(%s,&stui.num); printf(name%d:,i+1); scanf(%s,&); printf(sex%d:,i+1); scanf(%d,&stui.sex); for(j=0;j3;j+) printf(Grade%d%d:,i+1,j+1); scanf(%d,&stui.Gradej); fp=fopen(studinfo.dat,w); if(fp=NULL) printf(open file error!); exit(0); fwrite(stu,sizeof(STUDENT),5,fp); fclose(fp); fp=fopen(studinfo.dat,r); for(i=0;i5;i+) fread(stu,sizeof(STUDENT),5,fp); printf(%10s,stui.num); printf(%15s,); printf(%5d,stui.sex); for(j=0;j3;+j) printf(%5d,stui.Gradej); printf(n); fclose(fp); system(pause); return 0; 二排序1用随机函数产生1000（或更多）个整数（或浮点数），保存在文件（intfile.dat / realfile.dat）中，然后将文件中的所有整数（或浮点数）读入一个数组A。（1）用冒泡法对数组A 排序；（2）用简单选择排序方法对数组A 排序；（3）用直接插入排序法对数组A 排序；将上述排序算法分别用函数实现，观察每种排序过程中元素的比较次数、交换（或移动）次数，以及排序过程所消耗的时间（以s 或ms 为单位）；#include#include#define N 100typedef int KeyType;typedef char InfoType100;typedef struct KeyType key; InfoType otherinfo;RedType;typedef struct RedType rN+1; int length;SqList;SqList L;/冒泡排序 void BubbleSort(SqList L) int i,j,exchanged,m=0,n=0; for(i=1,exchanged=1;iL.length&exchanged;+i) exchanged=0; for(j=1;jL.rj+1.key) L.r0=L.rj; L.rj=L.rj+1; L.rj+1=L.r0; exchanged=1; +n; for(i=1;i=L.length;i+) printf(%-10d,L.ri.key); printf(n冒泡排序的比较次数：%dn,m); printf(冒泡排序的交换次数：%dn,n); /简单选择排序 void SelectSort(SqList L) int i,j,k,m=0,n=0; for(i=1;iL.length;i+) for(k=i+1,j=i;k=L.length;k+,j=i) +m; if(L.rk.keyL.rj.key) j=k; if(j!=i) +n; L.r0=L.rj; L.rj=L.ri; L.ri=L.r0; for(i=1;i=L.length;i+) printf(%-10d,L.ri.key); printf(n简单选择排序的比较次数：%dn,m); printf(简单选择排序的交换次数：%dn,n); /直接插入排序法void InsertSort(SqList L) int i,j,m=0,n=0; for(i=2;i=L.length;i+) if(L.ri.keyL.ri-1.key) +m; +n; L.r0=L.ri; L.ri=L.ri-1; for(j=i-2;L.r0.keyL.rj.key;j-) +m; L.rj+1=L.rj; L.rj+1=L.r0; for(i=1;i=L.length;i+) printf(%-10d,L.ri.key); printf(n直接插入排序的比较次数：%dn,m); printf(直接插入排序的交换次数：%dn,n); int main() void BubbleSort(SqList L); void SelectSort(SqList L); void InsertSort(SqList L); FILE *fp,*in; int aN; int i; L.length=N; fp=fopen(intfile.dat,w); if(fp=NULL) printf(open file error!); exit(0); for(i=0;iN;i+) ai=rand(); fprintf(fp,%-10d,ai); fclose(fp); in=fopen(intfile.dat,r); if(in=NULL) printf(open file error!); exit(0); for(i=1;i=N;i+) fscanf(in,%10d,&L.ri.key); printf(%-10d,L.ri.key); fclose(in); printf(nn); printf(冒泡排序法:n); BubbleSort(L); printf(nn); printf(简单选择排序法:n); SelectSort(L); printf(nn); printf(直接插入排序法:n); InsertSort(L); printf(n); system(pause); return 0; 2用快速排序算法对上述数组A 中的数据进行排序，输出排序过程中元素的比较次数、交换（移动）次数，以及排序过程所消耗的时间（以s 或ms 为单位）；#include#include#define N 10typedef int KeyType;typedef char InfoType100;typedef struct KeyType key; InfoType otherinfo;RedType;typedef struct RedType rN+1; int length;SqList;SqList L;int m=0,n=0;int Partition(SqList L,int low,int high) int i,j,pivotkey; L.r0=L.rlow; pivotkey=L.r0.key; i=low; j=high; while(ij) while(i=pivotkey) +m; j-; +n; L.rj=L.ri; while(ij&L.ri.key=pivotkey) +m; i+; +n; L.ri=L.rj; L.ri=L.r0; return i;void QSort(SqList L,int low,int high) int Partition(SqList L,int low,int high); int i,pivotloc; if(lowhigh) pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); int main() void QSort(SqList L,int low,int high); FILE *fp; int i; L.length=N; fp=fopen(intfile.dat,r); if(fp=NULL) printf(open file error!); exit(0); for(i=1;i=N;i+) fscanf(fp,%10d,&L.ri.key); printf(%-10d,L.ri.key); printf(nn快速排序法:n); QSort(L,1,N); for(i=1;i=L.length;i+) printf(%-10d,L.ri.key); printf(n快速排序的比较次数：%dn,m); printf(快速排序的交换次数：%dn,n); system(pause); return 0;3利用上面实现的任意一种排序算法，对实验题目一所产生的学生信息文件studinfo.dat，读取其中的所有学生信息：（1）按学号排序输出学生信息；（2）按姓名排序输出学生信息；（3）按三门课程的平均分从高到低排序输出学生信息（除了学生基本信息外，还要输出每个学生的平均成绩），最后再加一行输出信息：每门课程的平均成绩。#include#include#includetypedef struct char name10; char num10; int sex; int grade4; STUDENT;STUDENT studinfo4;int main() FILE *in,*fp; int i,j; int aver4; int k,swap; fp=fopen(studinfo.dat,wb); if(fp=NULL) printf(open the file error！); exit(0); printf(enter the information of students:n); for(i=1;i=3;i+) scanf(%s,); scanf(%s,studinfoi.num); scanf(%d,&studinfoi.sex); for(j=1;j=3;j+) scanf(%d,&studinfoi.gradej); fwrite(studinfo,sizeof(STUDENT),3,fp); fclose(fp); in=fopen(studinfo.dat,rb); if(in=NULL) printf(open the file error); exit(0); fread(studinfo,sizeof(STUDENT),3,in); for(i=1;i=3;i+) printf(%-10s%-10s,,studinfoi.num); printf(%5d,studinfoi.sex); for(j=1;j=3;j+) printf(%5d,studinfoi.gradej); printf(n); for(i=1;ii;j-) if(strcmp(studinfoj-1.num,studinfoj.num)0) studinfo0=studinfoj-1; studinfoj-1=studinfoj; studinfoj=studinfo0; swap=1; if(!swap) break; printf(按学号排列后:n); for(i=1;i=3;i+) printf(%-10s%-10s,,studinfoi.num); printf(%5d,studinfoi.sex); for(j=1;j=3;j+) printf(%5d,studinfoi.gradej); printf(n); printf(n); for(i=1;ii;j-) if(strcmp(,)0) studinfo0=studinfoj-1; studinfoj-1=studinfoj; studinfoj=studinfo0; swap=1; if(!swap) break; printf(按姓名排序后：n); for(i=1;i=3;i+) printf(%-10s%-10s,,studinfoi.num); printf(%5d,studinfoi.sex); for(j=1;j=3;j+) printf(%5d,studinfoi.gradej); printf(n); printf(n); printf(按平均成绩排序后：n); for(i=1;i=3;i+) averi=(studinfoi.grade1+studinfoi.grade2+studinfoi.grade3)/3; for(i=1;i=2;i+) if(averiaveri+1) studinfo0=studinfoi; studinfoi=studinfoi+1; studinfoi+1=studinfo0; for(i=1;i=3;i+) printf(%-10s%-10s,,studinfoi.num); printf(%5d%5d,studinfoi.sex,averi); for(j=1;j=3;j+) printf(%5d,studinfoi.gradej); printf(n); fclose(in); system(pause); return 0;三栈1、后缀表达式求值【问题描述】表达式可以采用后缀式表示。例如，表达式“46+(5-120)*37”的后缀式为“46 5 120 37 * +”。计算后缀表达式时，从左至右扫描：若遇到运算对象，则压入栈中；遇到运算符，则从栈中弹出相关运算对象进行计算，并将运算结果压入栈中，重复以上过程，直到后缀表达式扫描结束。例如，后缀表达式“46 5 120 37 * +”的计算过程为:a. 依次将46、5、120 压入栈中；b. 遇到“-”，分别弹出120 和5，计算5120，得-115，将其压入栈中；c. 遇到37，将37 压入栈中；d. 遇到“*”，分别弹出37 和-115，计算37*-115，得-4225，将其压入栈中；e. 遇到“+”， 分别弹出-4225 和46，计算46+-4225，得-4179，将其压入栈中；f. 表达式结束，栈中的值为计算结果，计算过程完成。【基本要求】写一个程序，利用栈计算一个后缀表达式的值。#include#include#includeconst int stacksize=100;struct stack int *base; int *top; int stacksize;int main() struct stack s; /? int x=1; char cstacksize+20; int i,j,len,t,m; int sum; s.base=(int *)malloc(sizeof(int); s.top=s.base; printf(cin:n); gets(c); len=strlen(c); for(i=0,sum=0;i9|ci0) if(x) *s.top+=sum;x=0; sum=0; if(ci=-) *(s.top-2)=*(s.top-2)-*(s.top-1); else if(ci=+) *(s.top-2)=*(s.top-2)+*(s.top-1); else if(ci=*) *(s.top-2)=*(s.top-2)*(*(s.top-1); else if(ci=/) *(s.top-2)=*(s.top-2)/(*(s.top-1); else s.top+; s.top-; else sum=(ci-0)+sum*10;x=1; printf(%dn,*(s.top-1); system(pause); return 0;2.括号匹配算法#include#include#includetypedef struct _stackchar *base;char *top;int num;Sqstack;void InitStack(Sqstack &s)s.base=(char *)malloc(100*sizeof(char);if(s.base=NULL)printf(栈创建失败!n);return;s.top=s.base;*s.top=0;s.num=100;void push(Sqstack &s,char k)if(s.top-s.base)=s.num)printf(栈已满!n);return;*s.top+=k;void pop(Sqstack &s)if(s.base=s.top)printf(该栈是空栈!n);return;s.top-;bool Isempty(Sqstack &s)if(s.base=s.top)return true;return false;bool Match(Sqstack &s)char str100;int i;printf(请输入括号串:);scanf(%s,str);for(i=0;istrlen(str);i+)switch(stri)case :push(s,);break;case :if(*(s.top-1)=)pop(s);elsereturn false;break;case (:push(s,();break;case ):if(*(s.top-1)=()pop(s);elsereturn false;break; case :push(s,);break;case :if(*(s.top-1)=)pop(s);elsereturn false;break;if(Isempty(s)return true;return false;int main()Sqstack s;InitStack(s);if(Match(s)printf(输入的括号匹配!n);elseprintf(输入的括号不匹配!n);free(s.base);system(pause);return 0;四掌握图的基本存储结构及图的遍历运算1.从键盘输入图的信息，包括顶点数、边数以及各条边。（1）用邻接矩阵存储图，输出深度优先遍历的顶点序列；（问）#include#include#define MaxVnum 50typedef int AdjMatrixMaxVnum+1MaxVnum+1; typedef struct int vexnum,arcnum; /顶点数、边数 AdjMatrix arcs; /邻接矩阵Graph;Graph G;int visitedMaxVnum+1;void DFSM(Graph G,int v) int w; visitedv=1; printf(%d ,v); for(w=1;w=G.vexnum;w+) if(G.arcsvw!=0&visitedw=0) DFSM(G,w); void DFS(Graph G,int v) int i; for(i=1;i=G.vexnum;i+) visitedi=0; for(i=1;i=G.vexnum;i+) if(!visitedi) DFSM(G,i);int main() void DFS(Graph G,int v); int i,j; printf(输入顶点数：); scanf(%d,&G.vexnum); printf(输入边数：); scanf(%d,&G.arcnum); printf(输入邻接矩阵:n); for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) scanf(%d,&G.arcsij); DFS(G,1); system(pause); return 0;（2）用邻接表存储图，输出深度优先遍历的顶点序列。深度遍历邻接表（问）#include#include#define MaxVnum 50typedef struct node /邻接表结点的结构体类型 int adjvex;/邻接域； int weight; struct node *next;/链域 EdgeNode;typedef struct vnode int vertex;/顶点域 EdgeNode *link;vexnode;/顶点表结点的结构体类型 typedef vexnode GaMaxVnum;/顶点表 typedef struct Ga adjlist; int vexnum,arcnum;ALGraph;int visitedMaxVnum;void CreateAdjList(ALGraph *G) int i,j,k; EdgeNode *s; printf(输入顶点数：); scanf(%d,&G-vexnum); printf(输入边数：); scanf(%d,&G-arcnum); for(i=0;ivexnum;i+) G-adjlisti.vertex=i; G-adjlisti.link=NULL; for(k=0;karcnum;k+) scanf(%d %d,&i,&j); s=(EdgeNode *)malloc(sizeof(EdgeNode);/生成邻接结点为j的边表结点*s s-adjvex=j; s-next=G-adjlisti.link; G-adjlisti.link=s; s=(EdgeNode *)malloc(sizeof(EdgeNode);/生成邻接结点为i的边表结点*s s-adjvex=i; s-next=G-adjlistj.link; G-adjlistj.link=s;/将s插入顶点的j边表头部 void DFSTraverse(ALGraph *G,int i) EdgeNode *p; p=(EdgeNode*)malloc(sizeof(EdgeNode); visitedi=1; printf(结点%dn,G-adjlisti.vertex); p=G-adjlisti.link; while(p) if(!visitedp-adjvex) DFSTraverse(G,p-adjvex); p=p-next; void DFS(ALGraph *G) int i; for(i=0;ivexnum;i+) visitedi=0; for(i=0;ivexnum;i+) if(!visitedi) DFSTraverse(G,i); int main() int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); void CreateAdjList(ALGraph *G); void DFS(ALGraph *G); CreateAdjList(G); DFS(G); system(pause); return 0; 深度遍历邻接表存储图#include #include#define MaxVnum 50typedef struct int visited100; Node;typedef struct ArcNode int adjvex; double weight; struct ArcNode *nextarc; ArcNode;/表结点结构类型 typedef struct int data; ArcNode *firstarc; AdjListMaxVnum;/头结点 typedef struct int vexnum; int arcnum; AdjList vertices; Graph;int main() void DFS(Graph G,int v,Node *t); Graph G; ArcNode *p