数据结构实验指导书

PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn 目 录 实验一 线性 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 的应用 ...................... 5 实验二 栈和队列的应用 ................... 11 实验三 串的应用 ......................... 17 实验四 二叉排序树应用 ................... 19 实验五 Halfman树 ....................... 23 实验六 图的遍历 ........................ 25 实验七 哈希查找 ......................... 30 实验八 排序 ............................ 33 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn 一、 实验目的 《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每 个学生必须完成一定数量的上机作业。通过本课程的上机作业，要求在数 据结构的选择和应用、算法的设计及实现等方面加深对课程基础 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 的理 解，同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到 比较系统和严格的训练。 二、 实验要求 ⒈ 问题分析 充分地分析和理解问题本身，弄清要求做什么，包括功能要求、 性能要求、设计要求和约束以及基本数据特性，数据间的联系等。 ⒉ 数据结构设计 针对要求解决的问题，考虑各种可能的数据结构，并且力求从 中出最佳 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 (必须连同算法一起考虑)，确定主要的数据结构及全程变量。对 引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。 ⒊ 算法设计 算法设计分概要设计和详细设计，概要设计着重解决程序的模 块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模 块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题. 详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，相当于 PASCAL语言的过程或函数设计。 ⒋ 测试用例设计 准备典型测试数据和测试方案，测试数据要有代表性、敏感性， 测试方案包括模块测试和模块集成测试。 ⒌ 上机调试 对程序进行编译，纠正程序中可能出现的语法错误，测试前，先 运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试 方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手 段。 三、 实习报告内容 ⒈ 问题描述： 包括目标、任务、条件和约束的描述。 ⒉ 设计： ⑴ 数据结构设计和核心算法设计描述； ⑵ 主控及功能模块层次结构； ⑶ 主要功能模块的输入、处理(算法框架描述)和输出； ⑷ 功能模块之间的调用与被调用关系等。 ⒊ 测试： 测试范例，测试结果，测试结果的分析与讨论，测试 过程中遇到的主要问题及所采用的解决措施。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn ⒋ 使用说明和作业小结： ⑴ 使用说明主要描述如何使用你的程序以及使用时的主要事项； ⑵ 在小结中说明程序的改进思想、经验和体会，并回答教师布置的讨论 题。 ⒌整理一份程序 清单 安全隐患排查清单下载最新工程量清单计量规则下载程序清单下载家私清单下载送货清单下载 及运行示例的结果。 将以上各项文字 材料 关于××同志的政审材料调查表环保先进个人材料国家普通话测试材料农民专业合作社注销四查四问剖析材料 及程序清单等装订成册，形成一个完整的 报告。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn 实验一 线性表的应用 一、 实验目的 1、掌握线性表的概念。 2、掌握线性表的各种基本操作。 3、理解线性表的顺序、链式存储。 二、实验内容 1、建立顺序存储的线性表，并对之进行插入、删除操作。 2、建立链式存储的线性表，并对之进行插入、删除操作。 三、C语言算法实现 1、建立顺序存储的线性表，并对之进行插入、删除操作。 #include “stdio.h” #include “stdlib.h” #define MAX 20 #define ELEMTP int #define v(*p) /* 在下列程序中 p是指向结构体的指针型变量，*p代表一个此类结构体 */ /* v也代表一个结构体，为使算法可读性好，用 v代替(*p) */ struct sequnce { ELEMTP elem[MAX]; int len; }; main() {struct sequnce *pz; int i,y,cord; void outlin(struct sequnce s); void creat(struct sequnce *p); void insert(struct sequnce *p,int i,int x); void delete(struct sequnce *p,int i); PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn do { printf(“\n 主菜单 \n”); printf(“\n 1、建立线性表 \n”); printf(“\n 2、插入一个元素 \n”); printf(“\n 3、删除一个元素 \n”); printf(“\n 4、结束程序运行 \n”); printf(“--------------------------------------\n”); printf(“请输入您的选择（1,2,3,4）”); scanf(“%d”,&cord); switch (cord) {case 1:{ pz=(struct sequnce *) malloc (sizeof(struct sequnce)); creat(pz); outlin(*pz); }break; case 2:{printf(“请输入插入的位置 i，数据 x:”); scanf(“%d,%d”,&i,&y); insert(pz,i,y); outlin(*pz); }break; case 3:{scanf(“%d”,&i); delete(pz,i); outlin(*pz); }break; case 4:exit(0); } }while (cord<=4); }/*main end*/ void outlin(struct sequnce s) {int i,j; for (i=1;i<=s.len;i++) printf(“%2d%6d\n”,i,s.elem[i]); }/*outlin end*/ PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn void insert (struct sequnce *p,int i,int x ) {int j; if (i<1||i>v.len+1) print(“位置不存在。”); else {for (j=v.len;j>=i;j--) v.elem[j+1]=v.elem[j]; v.elem[i]=x; v.len++; } }/*insert end*/ void delete(struct sequnce *p,int i) {int j; if (i<1||i>v.len) print(“位置不存在。”); else {for (j= i;j< v.len;j++) v.elem[j]=v.elem[j+1]; v.len--; } }/* delete end */ void creat(struct sequnce *p) {int i,j; printf(”n=”); scanf(“%d”,&(v.len)); for(i=1;i<=v.len;i++) {printf(“data=”); scanf(“%d”,&(v.elem[i]); } }/* creat end */ 2、建立链式存储的线性表，并对之进行插入、删除操作。 #include “stdio.h” #include “stdlib.h” #define MAX 20 #define ELEMTP int; struct node {ELEMTP data; struct node *next; PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn }; struct node p,q,*s,*head; main() {int i,y,cord; void outlin(struct node *h); void creat(); void insert(struct node *h,ELEMTP x,ELEMPT y); void delete(struct node *h,ELEMTP x) do {printf(“\n 主菜单 \n”); printf(“ 1 建立线性表 \n”); printf(“ 2 插入一个元素 \n”); printf(“ 3 删除一个元素 \n”); printf(“ 4 结束程序运行 \n”); printf(“--------------------------------------\n”); printf(“请输入您的选择（1,2,3,4）”); scanf(“%d”,&cord); switch (cord) {case 1: {creat(); outlin(head); }break; case 2: {printrf(“x,y=? 注意用逗号分隔”); scanf(“%d,%d”,&x,&y); insert(head,x,y); outlin(head); }break; case 3:{printf(“x=?”); scanf(“%d”,&x); delete(head,x); outlin(head); }break; case 4:exit(0); PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn }/*switch */ }while (cord<=4); }/*main end */ void creat() {/* 与前页单链表建立相同，上机时按前面代码输入即可。在此省略不重复 */ }/*creat end */ void outlin(struct node *h) {p=h->next; while(p!=NULL) {printf(“data=%4d”,p->data); p=p->next; } printf(“\n输出结束\n\n”); }/*outlin end */ void insert(struct node *h,int x,int y) {/*在值为 x的结点之前插入值为 y的结点，表中若无 x则 y接在表尾*/ s=(struct node *) malloc(sizeof(struct node)); s->data=y; q=h; p=h->next; while(p!=NULL && p->data!=x) {q=p;p=p->next;} q=h; p=h->next; while(p!=NULL && p->data!=x) {q=p;p=p->next;} q->next=s; s->next=p; }/*insert end */ void delete(struct node *h,int x) {p=h; while(p->next!=NULL&& p->next->data!=x)p++; if(p->next==NULL)printf(“x不存在！”); PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn else {q=p->next; p->=next=q->next; free(q); } }/*delete end */ PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn 实验二 栈和队列的应用 一、实验目的 1、掌握栈和队列的概念。 2、掌握栈和队列的基本操作（插入、删除、取栈顶元素、出队、入队等）。 3、理解栈和队列的顺序、链式存储。 4、理解线性表、栈和队列的异同。 二、实验内容 1、建立顺序存储的栈，并对之进行入栈、出栈、取栈顶元素操作。 2、建立链式存储的队列，并对之进行入队、出队操作。 三、C语言.算法实现 1、建立顺序存储的栈，并对之进行入栈、出栈、取栈顶元素操作。 #include “stdio.h” #include “stdlib.h” #define MAX 20 #define ELEMTP int; #define S(*p) /*在下列程序中 p是指向结构体的指针变量，p代表一个此类结构体*/ /*S也代表一个结构体，为使算法可读性好，用 S代替 （*p）*/ struct sqstack{ ELEMTP elem[MAX]; /*顺序栈存储结构*/ int top; }; main() {struct sqstack *q; int i,y,cord,ELEMTP a; void outstack(struct sqstack S); void initstack(struct sqstack *p); void push(struct sqstack *p,ELEMTP x); PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn ELEMTP pop(struct sqstack *p); ELEMTP getpop(struct sqstack *p); do {printf(“\n”); printf(“\n 主菜单 \n”); printf(“ 1 初始化顺序栈 \n”); printf(“ 2 入栈 \n”); printf(“ 3 出栈 \n”); printf(“ 4 结束程序运行 \n”); printf(“--------------------------------------\n”); printf(“请输入您的选择（1,2,3,4）”); scanf(“%d”,&cord); switch(cord) { case 1:{q=(struct sqstack *)malloc(sizeof(struct sqstack)); initstack(q); outstack(q); }break; case 2:{printf(“请输入要入栈的数据 a=”); scanf(“%d”,&a); push(q,a); outstack(q); }break; case 3:{pop(q); outstack(q); }break; case 4:{y=gettop(q); printf(“\ny=%d\n,y”); outstack(q); }break; case 5:exit(0); } PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn }while (cord<=5); }/*main end*/ void initstack(struct sqstack *p,ELEMTP x) {if (!p) printf(“ERROR!”); s.top=0; } void push(struct sqstack *p,ELEMTP x) {if(S.top0;i--) printf(“%2d%6d\n”,i,S.elem[i]); } 2、建立链式存储的队列，并对之进行入队、出队操作。 #include “stdio.h” #include “stdlib.h” #define ELEMTP int; #define Q (*qe) /*为使参数传址需用*qe，为使算法易读写 Q而不写(*qe)*/ struct quenode {ELEMTP data; /*数据元素类型*/ struct quenode next; /*指针域*/ }*p,*s,*h; struct quefr /*队列头、尾指针被封装在一起*/ {struct quenode *front, *rear; } main() {struct quefr *que; int i,x,y,cord; void outlin(struct quefr qq); void creat(struct quefr *qe); void insert(struct quefr *qe,ELEMTP x); ELEMTP delete(struct quefr *qe); do {printf(“\n”); printf(“\n 主菜单 \n”); printf(“ 1 初始化顺序栈 \n”); printf(“ 2 入栈 \n”); printf(“ 3 出栈 \n”); printf(“ 4 结束程序运行 \n”); PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn printf(“--------------------------------------\n”); printf(“请输入您的选择（1,2,3,4）”); scanf(“%d”,&cord); switch(cord) { case 1: {que=(struct quefr *)malloc (sizeof(struct quefr)); /*重要，这是头尾指针结点*/ creat(que); outlin(*que); }break; case 2: {printf(“x=?”); scanf(“%d,&x”); insert(que,x); outlin(*que); }break; case 3: {printf(“x=%d\n”,delete(que)); outlin(*que); }break; case 4: exit(0); } }while (cord<=4); }/*main end */ void outlin(struct quefr qq) {p=qq.front->next; /*指向第一个数据元素结点*/ while(p!=NULL) {printf(“data=%4d\n”,p->data); p=p->next; } printf(“\n outend \n\n”); } void insert(struct quefr *qe,int x) {/*值为 x的结点入队*/ PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn s=(struct quenode *) malloc(sizeof(struct quenode)); s->data=x; s->next=NULL; Q.rear->next=s; Q.rear=s; } ELEMTP delete(struct quefr *qe) {ELEMTP x; if (Q.front==Q.rear) {printf(“队列为空。\n”); x=0;} else {p=Q.front->next; Q.front->next=p->next; if(p->next==NULL) Q.rear=Q.front; /*防止尾指针丢失*/ x=p->data; free(p); } return(x); } void creat(struct quefr *qe) {int i,n,x; printf(“n=”); scanf(“%d”,&n); h=(struct quenode *) malloc(sizeof(struct quenode)); h->next=NULL; Q.front=h; Q.rear=h; For(i=1;i<=n;i++) {scanf(“%d”,&x); insert(qe,x); } } PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn 实验三 串的应用 一、目的和要求 1、掌握串的存储方式。 2、掌握串的模式匹配算法。 3、理解算法的实际应用价值。 二、实验内容 判断两个串是否匹配（在串 t中寻找串 p）。 三、C语言算法实现 1、简单匹配算法 一般的匹配算法 int simp(char *t,char *p) {n=strlen(t); m=strlen(p); i=0; bool=1; while((i<=n-m)&&(bool!=0)) {j=0; while((j<=m-1)&&(p[j]==t[i+j])) j++; if(j<=m-1) {bool=1;i++;} else bool=0; } if(bool==0) return(i); else return(0); /* bool=1, 返回 0，表示串 P不存在*/ } 2、串的带有失败链接值的模式匹配算法 失败链接值子函数 void faillink(char *p) {int j=2,k; PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn flink[1]=0; while(j<=m) {k=flink[j-1]; while (k!=0) && (p[k]!=p[j-1])) k=flink[k]; flink[j]=k+1; j=j+1; } } 模式匹配算法 int kmpmatch(int * t,int * p,int * flink) {n=strlen(t); m=strlen(p); int i=0,j=0,succ=false ; while ((i<=n) && (!succ)) {while((j!=0) && (p[j]!=t[i])) j=flink[j]; /*flink定义如前*/ if(j==m) {succ=true; return (i-m+1); } else {i=i+1; j=j+1; } } if(!succ) return(0); } PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn 实验四 二叉排序树应用 一、目的和要求 1、掌握二叉排序树的生成和遍历算法。 2、理解二叉排序树的概念。 二、 实验内容 1、建立二叉树。 2、使用三种遍历方法进行遍历二叉树。 三、C语言算法实现 #include “stdio.h” #include “stdlib.h” #define ELEMTP int; struct node {ELEMTP data; struct node lc,rc; } struct node root; /*根结点、做全局变量*/ int m=0; /*统计叶结点数，初值置零*/ main() {int cord; struct node *creat(); void preorderz(struct node t); /*参数必须与下边函数说明一 致 */ void inorder(struct node *t); void postorder(struct node *t); do {printf(“\n”); printf(“\n 主菜单 \n”); printf(“ 1 建立二叉树 \n”); PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn printf(“ 2 先序非递归遍历 \n”); printf(“ 3 中序递归遍历 \n”); printf(“ 4 后序递归遍历，求叶结点数 \n”); printf(“ 5 结束程序运行 \n ”); printf(“---------------------------------------------------------\n ”); printf(“请输入您的选择（1,2,3,4）”); scanf(“%d”,&cord); switch(cord) {case 1: {root=creat(); /*建立二叉树*/ printf(“建立二叉树程序已执行完，\n”); printf(“请返回主菜单，用遍历算法验证程序的正确性\n”); }break; case 2: {preorderz(root); printf(“先序非递归遍历程序已经执行完\n”); }break; case 3: {inoder(root); printf(“\n中序遍历二叉树程序已经执行完\n); }break; case 4: {postorder(root); printf(\n后序遍历二叉树程序已经执行完\n); printf(“叶结点数 m=%3d\n”,m); } case 5: {printf(“二叉树程序已经执行完，再见！\n”)； exit(0); } } /*swtich*/ }while(cord<=5); } /*main*/ struct node creat() /*建立二叉树*/ PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn {struct node t,q,*s[30]; int i,j,x; printf(“i,x=”); scanf(“%d%d”,&I,&x); /*i是满二叉树编号，x结点应有的序号，x是结点数据*/ while (i!=0)&&(x!=0) {q=(struct node ) malloc(sizeof(struct node)) /*产生一个结 点*/ q->data=x; q->lch=NULL; q->rch=NULL; s[i]=q; if(i==1) t=q; /*t代表树的根结点 */ else {j=i/2; /*双亲结点编号*/ if((i%2)==0) s[j]->lch=q; else s[j]->rch=q; } printf(“i=,x=”); scanf(“%d%d”,&i,&x); } return(t); } /*creat*/ void preorderz(struct node *p) /* 先序非递归算 法*/ {struct node q,s[30]; /*s是辅助栈*/ int top,bool; q=p; top=0; /*栈顶指针*/ bool=1; /*bool为真值继续循环；bool为假值为栈空，结束循环 */ PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn do{while(q!=NULL) {printf(“%6d”,q->data); /*访问根结点*/ top++; s[top]=q; q=q->lch; } if(top==0) bool=0; else {q=s[top]; top--;q=q->rch;} }while(bool); printf(“\n”); } /*preorderz*/ void inorder(struct node *p) {if(p!=NULL) {inoder(p->lch;) printf(“%6d”,p->data); inoder(p->rch); } } /*inoder*/ void postorder(struct node *p) {if (p!NULL) {postorder(p->lch); postorder(p->rch); printf(“%6d”,p->data); if(p->lch==NULL && p->rch==NULL) m++; /*统计叶结点*/ } } /*postorder*/ PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn 实验五 Halfman树 一、目的和要求 1、掌握 Halfman树的建立和编码算法。 2、理解 Halfman树的概念和编码。 二、实验内容 1、建立 Halfman树。 2、编 Halfman码。 三、C语言算法实现 struct nodeh {int data; /*权值域*/ int lch,rch; /*左、右孩子结点在数组中的下标*/ int tag; /*tag=0 结点独立；tag=1结点已并入树中*/ } int Huffman(struct node r[20]) {scanf(“n=%d”,&n); /*n为叶子结点的个数*/ for(j=1;j<=n;j++) {scanf(“%d”,&r[j].data); r[j].tag=0;r[j].lch=0;r[j].rch=0; } i=0; while(iadjvex=j; p->nextarc=A[i-1].firstarc; /*每一个边结点均插入在链表的首部*/ PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn A[i-1].firstarc=p; p=(struct ArcNode *) malloc (sizeof(struct ArcNode)); p->adjvex=i; p->nextarc=A[j-1].firstarc; A[j-1].firstarc=p; } printf(“\n”); for(k=0;kadjvex); p=p->nextarc; } printf(“\n”); } }/*creatgraph end*/ void dfs(struct Vnode A[Maxsize]) {struct ArcNode p,ar[Maxsize]; /*ar[MAX]作为顺序栈，存放遍历过程 中边结点的地址*/ int x,i,y,top=-1; int visited[Maxsize]; /*用作存放已遍历过顶点的标记*/ for (i=0;i=0)) PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn {if (!p) {p=ar[top];top--;} y=p->adjvex; if(visited[y-1]==0) {visited[y-1]=1; /*若未遍历过，则遍历，并且把下一个 顶点进栈，从本顶点出发继续按深度遍历*/ printf(“->%d”,y); p=p->nextarc; if(p) {top++;ar[top]=p;} p=A[y-1].firstarc; } else p=p->nextarc; } }/*dfs end*/ void bfs(struct Vnode A[Maxsize]) {struct ArcNode *p; int x,i,y,front=-1,rear=-1,ar[Maxsize],visited[Maxsize]; /*数组 ar[MAX]为顺序队列存放刚遍历过的顶点号*/ for(i=0;iadjvex; if(visited[y-1]==0) /*遍历顶点并插入队列*/ {visited[y-1]=1; PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn printf(“->%d”,y); rear++; ar[rear]=y; } p=p->nextarc; } }/*bfs*/ PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn 实验七 哈希查找 一、目的和要求 1、掌握哈希表的建立、哈希查找算法。 2、理解哈希存储思想。 二、实验内容 针对某一集体中的人名（30人）设计一个哈希表，使得平均查找长度不超过 2。 1、建立哈希表。 2、进行哈希查找。 三、C语言算法实现 #include #include /*主函数*/ main() {void creathash(char hash[][20],int n); int mid(unsigned long int s); void search(char hash[][20],char name[]); char name[20],hashlist[50][20]; creathash(hashlist,30); printf(“enter the name