数据结构实验指导书及答案.docx

数据结构实验实验指导书及答案信电工程学院计算机科学和技术教研室编2011.12数据结构实验所有代码整理作者郑涛声明：在这里我整理了数据结构实验的所有代码，希望能对大家的数据结构实验的考试有所帮助，大家可以有选择地浏览，特别针对一些重点知识需要加强记忆（ps:重点知识最好让孙天凯给出），希望大家能够在数据结构实验的考试中取得令人满意的成绩，如果有做的不好的地方请大家谅解并欢迎予以指正。实验一熟悉编程环境实验预备知识：1 .熟悉本课程的语言编译环境（TC或VC）,能够用C语言编写完整的程序，并能够发 现和改正错误。2. 能够灵活的编写C程序，并能够熟练输入C程序。一、实验目的1. 熟悉C语言编译环境，掌握C程序的编写、编译、运行和调试过程。2. 能够熟练的将C程序存储到指定位置。二、实验环境1. 硬件：每个学生需配备计算机一台。2. 软件：Windows操作系统+Turbo C；三、实验要求1 .将实验中每个功能用一个函数实现。2. 每个输入前要有输入提示（如：请输入2个整数当中用空格分割：），每个输出数据 都要求有内容说明（如：280和100的和是：380。）。3. 函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。四、实验内容1. 在自己的U盘中建立“姓名+学号”文件夹，并在该文件夹中创建“实验1”文件夹 （以后每次实验分别创建对应的文件夹），本次实验的所有程序和数据都要求存储到本文件 夹中（以后实验都按照本次要求）。2. 编写一个输入某个学生10门课程成绩的函数(10门课程成绩放到结构体数组中， 结构体包括：课程编号，课程名称，课程成绩)。3. 编写一个求10门成绩中最高成绩的函数，输出最高成绩和对应的课程名称，如果有 多个最高成绩，则每个最高成绩均输出。4. 编写一个求10门成绩平均成绩的函数。5. 编写函数求出比平均成绩高的所有课程及成绩。#include<stdio.h>#include<conio.h>struct subjectint subject_id;char subject_name20;double subject_grades;struct subject sub10;void input()int i;printf("please input:n");for(i=0;i<10;i+)scanf("%d %s %lf”,&subi.subject_id,&subi.subject_name,&subi.subject_g rades);printf("you just input:n");for(i=0;i<3;i+)printf("%d %s %lfn”,subi.subject_id,subi.subject_name,subi.subject_g rades);void subject_max()int i,flag;double max=sub0.subject_grades;for(i=0;i<10;i+)if(subi.subject_grades>max) max=subi.subject_grades;flag=i; printf("Thehighscoreofsubjectis %s %lfn”,subflag.subject_name,max);void subject_average()int i;double average,sum=sub0.subject_grades;for(i=1;i<10;i+)sum+=subi.subject_grades;average=sum/10;printf("subject's average is %lfn”,average);void subjct_gtaverage()int i,flag;double average,sum=sub0.subject_grades;for(i=1;i<10;i+)sum+=subi.subject_grades;average=sum/10;for(i=0;i<10;i+)if(subi.subject_grades>average)flag=i;printf("subjectgreaterthanaverageis %s %lfn”,subflag.subject_name,subflag.subject_grades); int main()input();subject_max();subject_average();subjct_gtaverage();return 0;实验二顺序表的基本操作实验预备知识:1 .熟练运用数组进行程序设计，掌握数组名和指针作为函数参数。2. 掌握结构体和结构体数组的访问与使用。3. 熟练实现顺序表类型和变量（如下所示）定于、熟悉顺序表的访问原理（顺序存储、 随机访问）。100 /线性表存储空间的初始分配量10 /践性我存储空间的分配增量矛黯性表的动态分配顺序存慵始构/存储宅M基址/当前长度/当前分配的存傩容髭（以BiaeDfCElemlype）为单位）* length? li&tsize；#define LIST. INIT. SIZE # Refine LI STINCREMEJri typedef struct ElemTpe int intSgListf一、实验目的1 .掌握顺序表的建立、数据元素的插入和删除、掌握数据元素的访问。2.能够熟练的使用函数来实现顺序表的各种操作。二、实验环境1. 硬件：每个学生需配备计算机一台。2. 软件：Windows操作系统+Turbo C；三、实验要求1 .定义一顺序表类型，并定义顺序表。2. 将教材中顺序表的建立、初始化、插入、删除等函数实现。3. 顺序表能够存储10名学生的基本信息（包括姓名、学号和成绩）。4. 由主函数按照用户要求对各个顺序表操作访问。5. 每次操作之前要有明确的说明，操作后要输出操作结果。6. 分析顺序表的插入、删除、查找的时间和空间复杂度。四、实验内容1. 在自己的U盘的“姓名+学号”文件夹中创建“实验2”文件夹，本次实验的所有程 序和数据都要求存储到本文件夹中。2. 完成顺序表操作的如下函数：建立，初始化，增加，插入，删除。#include "stdio.h"#include "malloc.h"#include "string.h"#define LIST_INIT_SIZE 1#define LISTINCREMENT 1struct stu(char name6;char num3;int cj;struct sqlist(struct stu *elem;int length;int listsize;void main()(struct sqlist* initlist_hc();void cshlist_hc(struct sqlist *l);void listinsert_hc(struct sqlist *l);void listdelete_hc(struct sqlist *l);void listhb_hc(struct sqlist *l1,struct sqlist *l2,struct sqlist *l3);struct sqlist *l1,*l2,*l3;char f;int i, k=0;printf("请选择对顺序表的操作，操作菜单如下：n");for(i=0;i<80;i+)printf("*");printf("建立顺序表(C)n");printf("初始化顺序表(N)n");printf("顺序表中插入元素(I)n");printf("顺序表中删除元素(D)n");printf("合并顺序表(H)n");printf("退出系统(E)n");for(i=0;i<80;i+)printf("*");do(printf("输入大写字母按Enter确定:")；flushall();f=getchar();if(f='C')(if(k=0)l1=initlist_hc();else (l2=initlist_hc();k+;else if(f='N')if(k=1)cshlist_hc(l1);else cshlist_hc(l2);else if(f='I')if(k=1)listinsert_hc(l1);else listinsert_hc(l2);else if(f='D')if(k=1)listdelete_hc(l1);else listdelete_hc(l2);else if(f='H')l3=initlist_hc();listhb_hc(l1,l2,l3);while(f!='E'); struct sqlist *initlist_hc()struct sqlist *l;l=(struct sqlist*)malloc(sizeof(struct sqlist);if(!l)printf("出错!n");return(l);void cshlist_hc(struct sqlist *l)struct stu *newbase;void printlist_hc(struct sqlist *l);char x6,y3;int z;l->elem=(struct stu*)malloc(LIST_INIT_SIZE*sizeof(struct stu);if(!l->elem)printf("出错!n");l->length=0;l->listsize=LIST_INIT_SIZE;printf("请输入信息以-1结束:n");scanf("%s %s %d”,x,y,&z);while(z!=-1)if(l->length=l->listsize)newbase=(struct stu*)realloc(l->elem,(l->listsize+LISTINCREMENT)*sizeof(struct stu);if(!newbase)printf("出错!n");l->elem=newbase;l->listsize+=LISTINCREMENT;strcpy(l->eleml->length.name,x);strcpy(l->eleml->length.num,y);l->eleml->length.cj=z;scanf("%s %s %d”,x,y,&z);if(z!=-1)l->length+;printlist_hc(l);void listinsert_hc(struct sqlist *l)int i,j;struct stu *newbase;void printlist_hc(struct sqlist *l);if(l->length=l->listsize)newbase=(struct stu*)realloc(l->elem,(l->listsize+LISTINCREMENT)*sizeof(struct stu);if(!newbase)printf("出错!n");l->elem=newbase;l->listsize+=LISTINCREMENT;printf(-输入要插入信息的位置:，scanf("%d”,&j);j-;for(i=l->length;i>=j;i-)strcpy(l->elemi+1.name,l->elemi.name);strcpy(l->elemi+1.num,l->elemi.num);l->elemi+1.cj=l->elemi.cj;printf("输入插入信息:n");scanf("%s %s %d",l->elemj.name,l->elemj.num,&l->elemj.cj);l->length+;printlist_hc(l);void listdelete_hc(struct sqlist *l)void printlist_hc(struct sqlist *l);int i,j;printf(-输入删除信息的位置:， scanf("%d”,&j);j-;printf("删除的信息为:s,%s,%dn”,l->elemj.name,l->elemj.num,l->elemj.cj);for(i=j+1;i<=l->length;i+)strcpy(l->elemi-1.name,l->elemi.name);strcpy(l->elemi-1.num,l->elemi.num);l->elemi-1.cj=l->elemi.cj;l->length-;printlist_hc(l);void listhb_hc(struct sqlist *l1,struct sqlist *l2,struct sqlist *l3) void printlist_hc(struct sqlist *l);struct stu *p1,*p2,*p3;struct stu *p1_last,*p2_last;p1=l1->elem;p2=l2->elem;l3->length=l1->length+l2->length+1;l3->listsize=l1->length+l2->length+2;p3=l3->elem=(struct stu*)malloc(l3->listsize*sizeof(struct stu);if(!l3->elem)printf("出错!n");p1_last=l1->elem+l1->length;p2_last=l2->elem+l2->length;while(p1<=p1_last&&p2<=p2_last)if(p1->cj>p2->cj)strcpy(p3->name,p1->name);strcpy(p3->num,p1->num);p3->cj=p1->cj;p1+;p3+;elsestrcpy(p3->name,p2->name);strcpy(p3->num,p2->num);p3->cj=p2->cj;p2+;p3+;while(p1<=p1_last)strcpy(p3->name,p1->name);strcpy(p3->num,p1->num);p3->cj=p1->cj;p1+;p3+;while(p2<=p2_last)strcpy(p3->name,p2->name);strcpy(p3->num,p2->num);p3->cj=p2->cj;p2+;p3+;printlist_hc(l3);void printlist_hc(struct sqlist *l) int i;printf(-当前表中信息如下:n");for(i=0;i<=l->length;i+)printf("%s,%s,%dn”,l->elemi.name,l->elemi.num,l->elemi.cj);实验三单链表的基本操作实验预备知识：1 .熟练运用指针进行程序设计，掌握结构体指针。2 .掌握使用结构体指针访问结构体变量。3. 掌握指针作为函数的参数使用。4. 理解单链表的含义、目的和处理方法。一、实验目的1 .掌握线性表的链式存贮结构及基本操作，深入了解链表的基本特性，以便在实际问 题背景下灵活运用它们。2. 巩固该存贮结构的构造方法，深入理解和灵活掌握链表的插入、删除等操作。二、实验环境1. 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows；2. 软件：DOS或Windows操作系统+Turbo C；三、实验要求1. 定义一链表类型，并定义带有头结点的单链表。2. 将教材中链表的建立、初始化、插入、删除等函数实现。3. 链表能够存储10名学生的基本信息(包括姓名、学号和成绩)。4. 由主函数按照用户要求对各个链表操作访问。5. 每次操作之前要有明确的说明，操作后要输出操作结果。6. 分析顺序表链表的插入、删除、查找的时间和空间复杂度。四、实验内容1. 在自己的U盘的“姓名+学号”文件夹中创建“实验3”文件夹，本次实验的所有程 序和数据都要求存储到本文件夹中。2. 完成链表操作的如下函数：建立，初始化，增加，插入，删除。链表插入、删除、合并#include "stdio.h"#include"string.h”#include"malloc.h"#define LEN sizeof(struct lnode_hc)#define LEN1 sizeof(struct hc_stu)struct hc_stu(char name3;char num3;int cj;；struct lnode_hc(struct hc_stu *data;struct lnode_hc *next;void main()(struct lnode_hc *jll();void cshl(struct lnode_hc *head);void crl(struct lnode_hc *head);void scl(struct lnode_hc *head);void hbl(struct lnode_hc *h1,struct lnode_hc *h2,struct lnode_hc *h3);struct lnode_hc *h1,*h2,*h3;char f;int i, k=0;printf("请选择对链表的操作，操作菜单如下：n");for(i=0;i<80;i+)printf("*");printf("建立链表(C)n");printf("初始化链表(N)n");printf("链表中插入元素(I )n");printf("链表中删除元素(D)n");printf("合并链表(H)n");printf("退出系统(E)n");for(i=0;i<80;i+)printf("*");do(printf("输入大写字母按Enter确定:")； flushall();f=getchar();if(f='C')if(k=0)h1习ll();else h2=jll();k+;else if(f='N')if(k=1)cshl(h1);else cshl(h2);else if(f='I')if(k=1)crl(h1);else crl(h2);else if(f='D')if(k=1)scl(h1);else scl(h2);else if(f='H')h3=jll();hbl(h1,h2,h3);while(f!='E');struct lnode_hc *jll() struct lnode_hc *head;head=(struct lnode_hc*)malloc(LEN);if(!head)printf("出错!n"); head->next=NULL;return (head);void cshl(struct lnode_hc *head) void printl(struct lnode_hc *head);char x3,y3;int z;struct lnode_hc *p1=head,*p2;printf("请输入信息以-1结束:n");scanf("%s %s %d”,x,y,&z);while(z!=-1)p2=(struct lnode_hc*)malloc(LEN);if(!p2)printf("出错!n");p2->data=(struct hc_stu*)malloc(LEN1); if(!p2->data)printf("出错!n");strcpy(p2->data->name,x);strcpy(p2->data->num,y);p2->data->cj=z;p2->next=NULL;p1->next=p2;p1=p2;scanf("%s %s %d”,x,y,&z); printl(head); void crl(struct lnode_hc *head)(void printl(struct lnode_hc *head);int j；struct lnode_hc *p,*p1=head;printf(-请输入要插入信息的位置:，scanf("%d”,&j);while(j->1)p1=p1->next;p=(struct lnode_hc*)malloc(LEN);if(!p)printf("出错!n");p->data=(struct hc_stu*)malloc(LEN1);if(!p->data)printf("出错!n");printf("请输入要插入的信息:n");scanf("%s %s %d”,p->data->name,p->data->num,&p->data->cj);p->next=p1->next;p1->next=p;printl(head);void scl(struct lnode_hc *head)(void printl(struct lnode_hc *head);int j;struct lnode_hc *p1=head,*p2=head->next;printf(-请输入要删除信息的位置:，scanf("%d”,&j);while(j>1)(p1=p1->next;p2=p2->next;j-;printf("删除的信息为:s,%s,%dn”,p2->data->name,p2->data->num,p2->data->cj);p1->next=p2->next;free(p2);printl(head);void hbl(struct lnode_hc *h1,struct lnode_hc *h2,struct lnode_hc *h3)(struct lnode_hc *p1,*p2,*p3;p1=h1->next;p2=h2->next;h3=p3=h1;while(p1&&p2)(if(p1->data->cj>p2->data->cj)(p3->next=p1;p3=p1;p1=p1->next;else(p3->next=p2;p3=p2;p2=p2->next;p3->next=p1?p1:p2;free(h2);printl(h3);void printl(struct lnode_hc *head)(struct lnode_hc *p=head->next;printf("当前表中元素如下:n");while (p->next!=NULL)(printf("%s,%s,%dn",p->data->name,p->data->num,p->data->cj);p=p->next;printf("%s,%s,%dn",p->data->name,p->data->num,p->data->cj);实验四栈的基本操作实验预备知识：1. 熟练运用线性结构进行数据处理，熟练使用指针进行数据访问。2. 掌握递归程序设计思想。3 .掌握堆栈和队列的应用背景与场合。4. 理解堆栈和队列的数据类型。一、实验目的1. 掌握栈的抽象数据类型。2 .掌握实现栈的各种操作的算法。3 .理解栈与递归的关系。二、实验环境1. 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows；2. 软件：DOS或Windows操作系统+Turbo C；三、实验要求1. 用C描述栈的每种操作在顺序栈或链栈上的实现。2. 将建栈、初始化栈、判断栈是否非空、求栈的长度、输出从栈顶到栈底的元素分别定 义为5个子函数，通过主函数实现对上述子函数的调用。3. 输入数据：数据域(data)设定为整型。四、实验内容1.在自己的U盘的“姓名+学号”文件夹中创建“实验4”文件夹，本次实验的所有程 序和数据都要求存储到本文件夹中。2 .定义两个堆栈：数据栈和操作栈。3. 实现如下堆栈处理函数。建栈、初始化栈、判断栈是否非空、求栈的长度、输出从栈顶到栈底的元素#include "stdio.h"#include "stdlib.h"#include "malloc.h"#include "string.h"#define STACK_INIT_SIZE 1#define STACKINCREMENT 1#define ERROR 0typedef struct(char *base;char *top;int stacksize;hc_sqstack;void main()(hc_sqstack *initstack_hc();void cshstack_hc(hc_sqstack *s);void push_hc(hc_sqstack *s);void pop_hc(hc_sqstack *s);void printstack_hc(hc_sqstack *s);hc_sqstack *s;char f;printf("建立栈(C)n");printf("初始化栈(N)n");printf("入栈元素(I)n");printf("出栈元素(D)n");printf("退出(E)nn");do(printf("输入要做的操作:， flushall();f=getchar();if(f='C')s=initstack_hc();else if(f='I')(push_hc(s);printstack_hc(s);else if(f='N')(cshstack_hc(s);printstack_hc(s);else if(f=D')(pop_hc(s);printstack_hc(s);while(f!='E');printf("n作 者:黄晨”);hc_sqstack *initstack_hc() (hc_sqstack *s;s=(hc_sqstack*)malloc(sizeof(hc_sqstack); if(!s)exit(ERROR);return(s); void cshstack_hc(hc_sqstack *s)(char e;s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);if(!s->base)exit(ERROR);s->top=s->base;s->stacksize=STACK_INIT_SIZE;printf("输入要栈的元素以#结束:n");flushall();e=getchar();while(e!='#')(if(s->top-s->base>=s->stacksize)(s->base=(char*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char);if(!s->base)exit(ERROR);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;flushall();e=getchar();void push_hc(hc_sqstack *s)(char e;printf("输入要入栈顶元素:")；flushall();e=getchar();if(s->top-s->base>=s->stacksize)(s->base=(char*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char);if(!s->base)exit(ERROR);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;void pop_hc(hc_sqstack *s)(if(s->top=s->base) exit(ERROR);printf("出栈的元素为:cn”,*-s->top);void printstack_hc(hc_sqstack *s)(char *t=s->top-1;printf("当前栈中元素为:n");while(t!=s->base)(printf("%cn”,*t-);printf("%cn”,*t);栈的操作1、入栈#include "stdio.h"#include "stdlib.h"#include "malloc.h"#include "string.h"#define STACK_INIT_SIZE 1#define STACKINCREMENT 1#define ERROR 0typedef struct(char *base;char *top;int stacksize;hc_sqstack;void main()(hc_sqstack *initstack_hc();void cshstack_hc(hc_sqstack *s);void push_hc(hc_sqstack *s);void printstack_hc(hc_sqstack *s);hc_sqstack *s;char f;printf("建立栈(C)n");printf("初始化栈(N)n");printf("入栈元素(I)n");printf("退出(E)nn");do(printf("输入要做的操作:， flushall();f=getchar();if(f='C')s=initstack_hc();else if(f='I')(push_hc(s);printstack_hc(s);else if(f='N')(cshstack_hc(s);printstack_hc(s); while(f!='E');hc_sqstack *initstack_hc()(hc_sqstack *s;s=(hc_sqstack*)malloc(sizeof(hc_sqstack); if(!s)exit(ERROR);return(s); void cshstack_hc(hc_sqstack *s) (char e;s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);if(!s->base)exit(ERROR);s->top=s->base;s->stacksize=STACK_INIT_SIZE;printf("输入要栈的元素以#结束:n");flushall();e=getchar();while(e!='#')if(s->top-s->base>=s->stacksize)s->base=(char*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char);if(!s->base)exit(ERROR);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;flushall();e=getchar();void push_hc(hc_sqstack *s)char e;printf("输入要入栈顶元素:")；flushall();e=getchar();if(s->top-s->base>=s->stacksize)s->base=(char*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char);if(!s->base)exit(ERROR);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;*s->top+=e;void printstack_hc(hc_sqstack *s)char *t=s->top-1;printf("当前栈中元素为:n");while(t!=s->base)printf("%cn”,*t-);printf("%cn”,*t);实验五队列的基本操作实验预备知识：1. 熟练运用线性结构进行数据处理，熟练使用指针进行数据访问。2. 掌握递归程序设计思想。3 .掌握堆栈和队列的应用背景与场合。4. 理解堆栈和队列的数据类型。一、实验目的1. 掌握队列的抽象数据类型。2 .掌握队列的各种操作的算法。3. 掌握队列的链式存贮结构及基本操作，深入了解链队列的基本特性，以便在实际问 题背景下灵活运用它们。二、实验环境1.