《数据结构实验》实验指导书及答案

信电工程学院 计算机科学和技术教研室 编

2011.12

数据结构实验所有代码整理

作者 郑涛

声明：在这里我整理了数据结构实验的所有代码，希望能对大家的数据结构实验的考试有所帮助，大家可以有选择地浏览，特别针对一些重点知识需要加强记忆（ps:重点知识最好让孙天凯给出），希望大家能够在数据结构实验的考试中取得令人满意的成绩，如果有做的不好的地方请大家谅解并欢迎予以指正。

实验一 熟悉编程环境

实验预备知识：

1．熟悉本课程的语言编译环境（TC或VC），能够用C语言编写完整的程序，并能够发现和改正错误。

2．能够灵活的编写C程序，并能够熟练输入C程序。

一、实验目的

1．熟悉C语言编译环境，掌握C程序的编写、编译、运行和调试过程。

2．能够熟练的将C程序存储到指定位置。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。

⒉ 软件：Windows操作系统+Turbo C；

三、实验要求

1．将实验中每个功能用一个函数实现。

2．每个输入前要有输入提示（如：请输入2个整数当中用空格分割：），每个输出数据都要求有内容说明（如：280和100的和是：380。）。

3．函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。

四、实验内容

1．在自己的U盘中建立“姓名+学号”文件夹，并在该文件夹中创建“实验1”文件夹（以后每次实验分别创建对应的文件夹），本次实验的所有程序和数据都要求存储到本文件夹中（以后实验都按照本次要求）。

2．编写一个输入某个学生10门课程成绩的函数（10门课程成绩放到结构体数组中，结构体包括：课程编号，课程名称，课程成绩）。

3．编写一个求10门成绩中最高成绩的函数，输出最高成绩和对应的课程名称，如果有多个最高成绩，则每个最高成绩均输出。

4．编写一个求10门成绩平均成绩的函数。

5．编写函数求出比平均成绩高的所有课程及成绩。

#include

#include

struct subject

{

int subject_id;

char subject_name[20];

double subject_grades;

};

struct subject sub[10];

void input()

{

int i;

printf("please input:\n");

for(i=0;i<10;i++)

{

scanf("%d %s %lf",&sub[i].subject_id,&sub[i].subject_name,&sub[i].subject_grades);

}

printf("you just input:\n");

for(i=0;i<3;i++)

{

printf("%d %s %lf\n",sub[i].subject_id,sub[i].subject_name,sub[i].subject_grades);

}

}

void subject_max()

{

int i,flag;

double max=sub[0].subject_grades;

for(i=0;i<10;i++)

{

if(sub[i].subject_grades>max)

max=sub[i].subject_grades;

flag=i;

}

printf("The high score of subject is %s %lf\n",sub[flag].subject_name,max);

}

void subject_average()

{

int i;

double average,sum=sub[0].subject_grades;

for(i=1;i<10;i++)

{

sum+=sub[i].subject_grades;

}

average=sum/10;

printf("subject's average is %lf\n",average);

}

void subjct_gtaverage()

{

int i,flag;

double average,sum=sub[0].subject_grades;

for(i=1;i<10;i++)

{

sum+=sub[i].subject_grades;

}

average=sum/10;

for(i=0;i<10;i++)

{

if(sub[i].subject_grades>average)

{

flag=i;

printf("subject greater than average is %s %lf\n",sub[flag].subject_name,sub[flag].subject_grades);

}

}

}

int main()

{

input();

subject_max();

subject_average();

subjct_gtaverage();

return 0;

}

实验二 顺序表的基本操作

实验预备知识：

1．熟练运用数组进行程序设计，掌握数组名和指针作为函数参数。

2．掌握结构体和结构体数组的访问与使用。

3．熟练实现顺序表类型和变量（如下所示）定于、熟悉顺序表的访问原理（顺序存储、随机访问）。

一、实验目的

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 1

struct stu

{char name[6];

char num[3];

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 x[6],y[3];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->elem[l->length].name,x);

strcpy(l->elem[l->length].num,y);

l->elem[l->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->elem[i+1].name,l->elem[i].name);

strcpy(l->elem[i+1].num,l->elem[i].num);

l->elem[i+1].cj=l->elem[i].cj;}

printf("输入插入信息:\n");

scanf("%s %s %d",l->elem[j].name,l->elem[j].num,&l->elem[j].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,%d\n",l->elem[j].name,l->elem[j].num,l->elem[j].cj);

for(i=j+1;i<=l->length;i++)

{strcpy(l->elem[i-1].name,l->elem[i].name);

strcpy(l->elem[i-1].num,l->elem[i].num);

l->elem[i-1].cj=l->elem[i].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++;}

else

{strcpy(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,%d\n",l->elem[i].name,l->elem[i].num,l->elem[i].cj);}}

实验三 单链表的基本操作

实验预备知识：

1．熟练运用指针进行程序设计，掌握结构体指针。

2．掌握使用结构体指针访问结构体变量。

3．掌握指针作为函数的参数使用。

4．理解单链表的含义、目的和处理方法。

一、实验目的

1．掌握线性表的链式存贮结构及基本操作，深入了解链表的基本特性，以便在实际问题背景下灵活运用它们。

2．巩固该存贮结构的构造方法，深入理解和灵活掌握链表的插入、删除等操作。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows；

⒉ 软件：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 name[3];

char num[3];

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=jll();

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 x[3],y[3];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,%d\n",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,%d\n",p->data->name,p->data->num,p->data->cj);

p=p->next;}

printf("%s,%s,%d\n",p->data->name,p->data->num,p->data->cj);

}

实验四 栈的基本操作

实验预备知识：

1．熟练运用线性结构进行数据处理，熟练使用指针进行数据访问。

2．掌握递归程序设计思想。

3．掌握堆栈和队列的应用背景与场合。

4．理解堆栈和队列的数据类型。

一、实验目的

1．掌握栈的抽象数据类型。

2．掌握实现栈的各种操作的算法。

3．理解栈与递归的关系。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows；

⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．用Ｃ描述栈的每种操作在顺序栈或链栈上的实现。

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 0

typedef 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)\n\n");

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("出栈的元素为:%c\n",*--s->top);}

void printstack_hc(hc_sqstack *s)

{char *t=s->top-1;

printf("当前栈中元素为:\n");

while(t!=s->base)

{printf("%c\n",*t--);}

printf("%c\n",*t);}

栈的操作

1、入栈

#include "stdio.h"

#include "stdlib.h"

#include "malloc.h"

#include "string.h"

#define STACK_INIT_SIZE 1

#define STACKINCREMENT 1

#define ERROR 0

typedef 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)\n\n");

do

{printf("输入要做的操作:");

flushall();

f=getchar();

本文来源：https://www.2haoxitong.net/k/doc/0ea41fbdf424ccbff121dd36a32d7375a417c686.html