数据结构实验指导书(2016)

更新时间：2024-01-28 09:46:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

《数据结构》实验指导书

信息与计算科学专业教研室

2016年3月

实验一熟悉编程环境 ....................................................................................................................... 1

一、实验目的 ........................................................................................................................... 1 二、实验环境 ........................................................................................................................... 1 三、实验要求 ........................................................................................................................... 1 四、实验内容 ........................................................................................................................... 1 实验二顺序表的基本操作 ............................................................................................................... 3

一、实验目的 ........................................................................................................................... 4 二、实验环境 ........................................................................................................................... 4 三、实验要求 ........................................................................................................................... 4 四、实验内容 ........................................................................................................................... 4 实验三单链表的基本操作 ............................................................................................................... 8

一、实验目的 ........................................................................................................................... 8 二、实验环境 ........................................................................................................................... 8 三、实验要求 ........................................................................................................................... 8 四、实验内容 ........................................................................................................................... 8 实验四栈的基本操作 ..................................................................................................................... 11

一、实验目的 ......................................................................................................................... 12 二、实验环境 ......................................................................................................................... 12 三、实验要求 ......................................................................................................................... 12 四、实验内容 ......................................................................................................................... 12 实验五队列的基本操作 ................................................................................................................. 16

一、实验目的 ......................................................................................................................... 16 二、实验环境 ......................................................................................................................... 16 三、实验要求 ......................................................................................................................... 17 四、实验内容 ......................................................................................................................... 17 实验六二叉树建立及遍历操作 ..................................................................................................... 19

一、实验目的 ......................................................................................................................... 19 二、实验环境 ......................................................................................................................... 19 三、实验要求 ......................................................................................................................... 19 四、实验内容 ......................................................................................................................... 19 实验七二叉树的应用程序设计 ..................................................................................................... 21

一、实验目的 ......................................................................................................................... 21 二、实验环境 ......................................................................................................................... 21 三、实验要求 ......................................................................................................................... 21 四、实验内容 ......................................................................................................................... 22 五、报告要求 ......................................................................................................................... 22 实验八图的建立及遍历操作 ......................................................................................................... 25

一、实验目的 ......................................................................................................................... 25 二、实验环境 ......................................................................................................................... 25 三、实验要求 ......................................................................................................................... 25 四、实验内容 ......................................................................................................................... 25

实验九图的最小生成树算法的实现 ............................................................................................. 30

一、实验目的 ......................................................................................................................... 30 二、实验环境 ......................................................................................................................... 30 三、实验要求 ......................................................................................................................... 30 四、实验内容 ......................................................................................................................... 30 实验十图的最短路径算法的实现 ................................................................................................. 33

一、实验目的 ......................................................................................................................... 33 二、实验环境 ......................................................................................................................... 33 三、实验要求 ......................................................................................................................... 33 四、实验内容 ......................................................................................................................... 33 实验十一顺序表查找算法的实现 ................................................................................................. 37

一、实验目的 ......................................................................................................................... 37 二、实验环境 ......................................................................................................................... 37 三、实验要求 ......................................................................................................................... 37 四、实验内容 ......................................................................................................................... 38 实验十二有序表查找算法的实现 ................................................................................................. 41

一、实验目的 ......................................................................................................................... 41 二、实验环境 ......................................................................................................................... 41 三、实验要求 ......................................................................................................................... 41 四、实验内容 ......................................................................................................................... 42 实验十三二叉排序树的查找算法实现 ......................................................................................... 44

一、实验目的 ......................................................................................................................... 45 二、实验环境 ......................................................................................................................... 45 三、实验要求 ......................................................................................................................... 45 四、实验内容 ......................................................................................................................... 45 实验十四插入排序算法的实现 ..................................................................................................... 48

一、实验目的 ......................................................................................................................... 48 二、实验环境 ......................................................................................................................... 48 三、实验要求 ......................................................................................................................... 48 四、实验内容 ......................................................................................................................... 48 实验十五交换排序算法的实现 ..................................................................................................... 52

一、实验目的 ......................................................................................................................... 52 二、实验环境 ......................................................................................................................... 52 三、实验要求 ......................................................................................................................... 52 四、实验内容 ......................................................................................................................... 53

实验一熟悉编程环境

实验预备知识：

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];

第1页 /共58页

double subject_grades; };

struct subject sub[10];

void input() {

int i;

printf(\ for(i=0;i<10;i++) {

scanf(\rades);

}

printf(\ for(i=0;i<3;i++) {

printf(\rades);

} }

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(\high score of subject is %s %lf\\n\

}

void subject_average() {

int i;

double average,sum=sub[0].subject_grades; for(i=1;i<10;i++) {

第2页 /共58页

sum+=sub[i].subject_grades; }

average=sum/10;

printf(\}

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(\greater than is %s %lf\\n\

} } }

int main() {

input();

subject_max(); subject_average(); subjct_gtaverage(); return 0; }

average

实验二顺序表的基本操作

实验预备知识：

1．熟练运用数组进行程序设计，掌握数组名和指针作为函数参数。 2．掌握结构体和结构体数组的访问与使用。 3．熟练实现顺序表类型和变量（如下所示）定于、熟悉顺序表的访问原理（顺序存储、随机访问）。

第3页 /共58页

一、实验目的

1．掌握顺序表的建立、数据元素的插入和删除、掌握数据元素的访问。 2．能够熟练的使用函数来实现顺序表的各种操作。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。 ⒉ 软件：Windows操作系统+Turbo C；

三、实验要求

1．定义一顺序表类型，并定义顺序表。

2．将教材中顺序表的建立、初始化、插入、删除等函数实现。

3．顺序表能够存储10名学生的基本信息（包括姓名、学号和成绩）。 4．由主函数按照用户要求对各个顺序表操作访问。

5．每次操作之前要有明确的说明，操作后要输出操作结果。 6．分析顺序表的插入、删除、查找的时间和空间复杂度。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验2”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．完成顺序表操作的如下函数：建立，初始化，增加，插入，删除。

#include \#include \#include \

#define LIST_INIT_SIZE 1 #define LISTINCREMENT 1

struct stu

{char name[6]; char num[3]; int cj;};

第4页 /共58页

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));

第5页 /共58页

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(\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(\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(\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(\l->length++; printlist_hc(l);}

第6页 /共58页

void listdelete_hc(struct sqlist *l) {void printlist_hc(struct sqlist *l); int i,j;

printf(\输入删除信息的位置:\scanf(\

printf(\删除的信息为:%s,%s,%d\\n\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);}

第7页 /共58页

void printlist_hc(struct sqlist *l) {int i;

printf(\当前表中信息如下:\\n\for(i=0;i<=l->length;i++)

{printf(\

实验三单链表的基本操作

实验预备知识：

1．熟练运用指针进行程序设计，掌握结构体指针。 2．掌握使用结构体指针访问结构体变量。 3．掌握指针作为函数的参数使用。

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

一、实验目的

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

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

二、实验环境

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

三、实验要求

1．定义一链表类型，并定义带有头结点的单链表。

2．将教材中链表的建立、初始化、插入、删除等函数实现。

3．链表能够存储10名学生的基本信息（包括姓名、学号和成绩）。 4．由主函数按照用户要求对各个链表操作访问。

5．每次操作之前要有明确的说明，操作后要输出操作结果。 6．分析顺序表链表的插入、删除、查找的时间和空间复杂度。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验3”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．完成链表操作的如下函数：建立，初始化，增加，插入，删除。 //链表插入、删除、合并 #include \#include\#include\

#define LEN sizeof(struct lnode_hc)

第8页 /共58页

#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);}

第9页 /共58页

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(\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(\printl(head);}

void crl(struct lnode_hc *head) {void printl(struct lnode_hc *head); int j;

struct lnode_hc *p,*p1=head;

printf(\请输入要插入信息的位置:\scanf(\

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\

第10页 /共58页

printf(\请输入要插入的信息:\\n\

scanf(\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(\while(j>1) {p1=p1->next; p2=p2->next; j--;}

printf(\删除的信息为:%s,%s,%d\\n\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(\p=p->next;}

printf(\}

实验四栈的基本操作

实验预备知识：

1．熟练运用线性结构进行数据处理，熟练使用指针进行数据访问。 2．掌握递归程序设计思想。

第11页 /共58页

3．掌握堆栈和队列的应用背景与场合。 4．理解堆栈和队列的数据类型。

一、实验目的

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

2．掌握实现栈的各种操作的算法。 3．理解栈与递归的关系。

二、实验环境

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

三、实验要求

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

2.将建栈、初始化栈、判断栈是否非空、求栈的长度、输出从栈顶到栈底的元素分别定义为5个子函数，通过主函数实现对上述子函数的调用。

3. 输入数据：数据域（data）设定为整型。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验4”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．定义两个堆栈：数据栈和操作栈。 3．实现如下堆栈处理函数。

建栈、初始化栈、判断栈是否非空、求栈的长度、输出从栈顶到栈底的元素 #include \#include \#include \#include \

#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);

第12页 /共58页

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(\作者:黄晨\

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;}

第13页 /共58页

*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\

void printstack_hc(hc_sqstack *s) {char *t=s->top-1;

printf(\当前栈中元素为:\\n\while(t!=s->base) {printf(\printf(\

栈的操作 1、入栈

#include \#include \#include \#include \

#define STACK_INIT_SIZE 1 #define STACKINCREMENT 1 #define ERROR 0

typedef struct {char *base; char *top; int stacksize; }hc_sqstack;

第14页 /共58页

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

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;

第15页 /共58页

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(\printf(\

实验五队列的基本操作

实验预备知识：

1．熟练运用线性结构进行数据处理，熟练使用指针进行数据访问。 2．掌握递归程序设计思想。

3．掌握堆栈和队列的应用背景与场合。 4．理解堆栈和队列的数据类型。

一、实验目的

1．掌握队列的抽象数据类型。 2．掌握队列的各种操作的算法。

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

二、实验环境

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

第16页 /共58页

三、实验要求

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

3．将建队列、初始化队列、判断队列是否非空、求队列的长度、输出队列的元素分别定义为5个子函数，通过主函数实现对上述子函数的调用。

4. 输入数据：数据域（data）设定为整型。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验4”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

4．实现如下链队列处理函数。

建队列、初始化队列、判断队列是否非空、求队列的长度、输出队列的元素 #include \#include \#include \#include \#define MAXQSIZE 5 #define ERROR 0 #define OK 1

typedef struct {char *base; int front; int rear; int length; }hc_sqqueue;

void main()

{hc_sqqueue *initqueue_hc(); int cshqueue_hc(hc_sqqueue *q); int enqeue_hc(hc_sqqueue *q,char e); int deqeue_hc(hc_sqqueue *q); int printqueue_hc(hc_sqqueue *q); hc_sqqueue *q; char f,e;

printf(\建立队列(C)\\n\printf(\初始化队列(N)\\n\printf(\入队列元素(I)\\n\printf(\出队列元素(D)\\n\printf(\退出(E)\\n\\n\do

{printf(\输入要做的操作:\

第17页 /共58页

flushall(); f=getchar();

if(f=='C')q=initqueue_hc(); else if(f=='N')

{cshqueue_hc(q);printqueue_hc(q);} else if(f=='I')

{printf(\输入要的入队的元素:\flushall();e=getchar();

enqeue_hc(q,e);printqueue_hc(q);} else if(f=='D')

{deqeue_hc(q);printqueue_hc(q);} }while(f!='E');

hc_sqqueue *initqueue_hc() {hc_sqqueue *q;

q=(hc_sqqueue*)malloc(sizeof(hc_sqqueue)); if(!q)exit(ERROR); return(q);}

int cshqueue_hc(hc_sqqueue *q) {char e;

int enqeue_hc(hc_sqqueue *q,char e);

q->base=(char*)malloc(MAXQSIZE*sizeof(char)); if(!q->base)exit(ERROR);

q->front=q->rear=0;q->length=0; printf(\输入元素以#结束:\\n\flushall(); e=getchar(); while(e!='#') {enqeue_hc(q,e);

if(q->length==MAXQSIZE)return(ERROR); else {flushall();e=getchar();}} return(OK);}

int enqeue_hc(hc_sqqueue *q,char e)

{if(q->length==MAXQSIZE)return(ERROR); q->base[q->rear]=e;

q->rear=(q->rear+1)%MAXQSIZE; q->length++; return(OK);}

int deqeue_hc(hc_sqqueue *q) {if(q->length==0)return (ERROR);

printf(\出队的元素为:%c\\n\

第18页 /共58页

q->front=(q->front+1)%MAXQSIZE;q->length--; return (OK);}

int printqueue_hc(hc_sqqueue *q) {int t=q->front;

if(q->length==0){printf(\队空!\\n\if(q->length==MAXQSIZE)printf(\队满!\\n\printf(\当前队列中元素为:\\n\do{printf(\

t=(t+1)%MAXQSIZE;}while(t!=q->rear); return(OK);}

实验六二叉树建立及遍历操作

实验预备知识：

1．熟练指针进行数据访问。

2．掌握二叉树的存储结构和处理方法。 3．掌握二叉树三种遍历的算法。

一、实验目的

1．熟悉二叉树的存贮结构及遍历方式，掌握有关算法的实现。 2．能够利用二叉树解决具体问题。

二、实验环境

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

三、实验要求

1．要求采用二叉链表作为存贮结构，完成二叉树的建立、先序、中序、和后序遍历的操作。其中先序遍历和后序遍历采用递归算法，中序遍历采用非递归算法。

2．输入数据：树中每个结点的数据类型设定为字符型。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验6”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．实现如下二叉树处理函数。建树子函数先序遍历子函数中序遍历子函数后序遍历子函数

第19页 /共58页

#include //头文件 #include typedef struct BiTNode {

char data;

struct BiTNode *lchild,*rchild; }

BiTNode,*BiTree;//定义结点类型 BiTree CreateBiTree()//创建树 {

char p;BiTree T; scanf(\ if(p==' ')

T=NULL; else {

T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间 T->data=p;

T->lchild=CreateBiTree(); T->rchild=CreateBiTree(); }

return (T); }

void PreOrder(BiTree T)//先序 {

if(T!=NULL) {

printf(\ PreOrder(T->lchild); PreOrder(T->rchild);

} }

void InOrder(BiTree T)//中序 {

if(T!=NULL) {

InOrder(T->lchild); printf(\ InOrder(T->rchild);

} }

void PostOrder(BiTree T)//后序

第20页 /共58页

{

if(T!=NULL) {

PostOrder(T->lchild); PostOrder(T->rchild); printf(\ } }

void main()//主函数 {

BiTree Ta;

Ta=CreateBiTree(); printf(\先序遍历:\ printf(\ PreOrder(Ta); printf(\

printf(\中序遍历:\ printf(\ InOrder(Ta); printf(\

printf(\后序遍历:\ printf(\ PostOrder(Ta); }

实验七二叉树的应用程序设计

实验预备知识：

2．掌握二叉树的创建和遍历算法。 3．掌握霍夫曼编码原理。

一、实验目的

1．进一步掌握二叉树的存储结构和相应算法。 2．掌握霍夫曼树树的创建和霍夫曼编码。

二、实验环境

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

三、实验要求

1．要求采用二叉链表作为存贮结构，完成霍夫曼树的创建。

第21页 /共58页

2．输出对应数据的霍夫曼编码，并求出平均编码长度。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验7”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某电报公司假设有10字符进行编码，这10个字符的使用频率如下表所示，请创建霍夫曼树。

A 19 B 18 C 16 D 14 E 12 F 8 G 6 H 4 I 2 J 1 3.编写函数求出A~J的霍夫曼编码。

五、报告要求

1．认真书写实验报告，字迹清晰，格式规范。报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求、实验原理（系统主要工作流程图）。

2．报告中应书写主要源程序，且源程序中要有注释。 3．报告最后包含实验总结和体会。

4．如未调试通过或结果不正确，试分析原因，利用课余时间独立完成，完成后方可书写实验报告。

#include #include #include

typedef char* HuffmanCode; typedef struct {char data;

unsigned int weight ;

unsigned int parent, LChild,RChild ; }HTNode, * HuffmanTree; //选出权值最小的两个//

void select(HuffmanTree *ht,int n, int *s1, int *s2) {int i;

int min1=0,min2=0;

(*ht)[min1].weight=(*ht)[min2].weight=101; for(i=1;i<=n;i++)

{if((*ht)[i].weight < (*ht)[min1].weight&&(*ht)[i].parent == 0) min1=i;} for(i=1;i<=n;i++)

{if((*ht)[i].weight < (*ht)[min2].weight&&(*ht)[i].parent == 0&&min1!=i) min2=i;}

*s1=min2;*s2=min1; }

第22页 /共58页

void CrtHuffmanTree(HuffmanTree *ht , int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i,w;

int s1,s2;char c; m=2*n-1;

*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ printf(\输入字符及权重:\\n\ for(i=1;i<=n;i++)

{/*1-n号放叶子结点，初始化*/ fflush(stdin);

scanf(\ (*ht)[i].data = c; (*ht)[i].weight = w; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; }

for(i=n+1;i<=m;i++) {

(*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0;

} /*非叶子结点初始化*/ /*创建非叶子结点,建哈夫曼树*/ for(i=n+1;i<=m;i++)

{ /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2;

(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; } }

//中序输出哈夫曼树叶子节点//

void outputHuffman(HuffmanTree HT, int m) { if(m!=0) {

outputHuffman(HT,HT[m].LChild);

第23页 /共58页

if(!HT[m].LChild&&!HT[m].RChild)printf(\ outputHuffman(HT,HT[m].RChild); } }

/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/ void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) {

char *cd; int i;

unsigned int c; int start; int p;

hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n个编码的头指针*/ cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/ cd[n-1]='\\0'; /*从右向左逐位存放编码，首先存放编码结束符*/ for(i=1;i<=n;i++) /*求n个叶子结点对应的哈夫曼编码*/ {

start=n-1; /*初始化编码起始指针*/

for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*从叶子到根结点求编码*/ if( (*ht)[p].LChild == c)

cd[--start]='0'; /*左分支标0*/ else

cd[--start]='1'; /*右分支标1*/

hc[i]=(char *)malloc((n-start)*sizeof(char)); /*为第i个编码分配空间*/ strcpy(hc[i],&cd[start]); }

free(cd);

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

printf(\编码为%s\\n\}

// 主函数// void main() {

HuffmanTree HT; HuffmanCode HC; int n; int m;

printf(\输入叶子节点的个数:\ scanf(\

CrtHuffmanTree(&HT,n);

m = 2*n-1;printf(\中序输出哈夫曼树叶子节点：\\n\ outputHuffman(HT,m); printf(\

第24页 /共58页

CrtHuffmanCode(&HT,&HC,n); }

实验八图的建立及遍历操作

实验预备知识：

1．掌握图的存储结构和访问。 2．掌握图的遍历及相关操作原理。

一、实验目的

1．掌握图的存储结构和相关操作。

2．能够熟练用计算机来表示图和进行图处理。

二、实验环境

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

三、实验要求

1．要求对于给定的图分别用邻接矩阵和邻接表来存储。 2．对于存储好的图进行深度和广度优先遍历。 3．完成图的各种操作。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验8”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某网络公司的光纤连接结点如下图所示，请分别用邻接矩阵和邻接表将图存储到计算机中方便进行处理。

3．现在公司想知道共有哪些结点及其名称，现在请你用深度优先和广度优先进行遍历。 4．完成如下图中没有实现的操作函数：

第25页 /共58页

#include \#include \#include \#define INFINITY 32767 #define MAX_VERTEX_NUM 20

typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc;

typedef struct arccell_hc {int adj; int *info;

}arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc;

第26页 /共58页

typedef struct arcnode_hc {int adjvex;

struct arcnode_hc *nextarc; int *info; }arcnode_hc;

typedef struct vnode_hc {char data;

arcnode_hc *firstarc;

}vnode_hc,adjlist_hc[MAX_VERTEX_NUM];

typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc;

int locatevex_hc(mgraph_hc*g,char v) {int i,k=0;

for(i=0;ivexnum;i++)

if(g->vexs[i]==v){k=i;i=g->vexnum;} return(k);}

mgraph_hc*createudg_hc() {mgraph_hc*g; char v1,v2; int i,j,incinfo;

g=(mgraph_hc*)malloc(sizeof(mgraph_hc)); g->kind=UDG;

printf(\请输入图顶点数、边数及该边相关信息:\scanf(\printf(\请输入顶点信息:\

for(i=0;ivexnum;++i)scanf(\for(i=0;ivexnum;++i) for(j=0;jvexnum;++j) g->arcs[i][j].adj=0;

printf(\输入一条边依附的顶点:\\n\flushall();scanf(\while(v1!='#'&&v2!='#')

{i=locatevex_hc(g,v1);j=locatevex_hc(g,v2); g->arcs[i][j].adj=1;

if(incinfo)g->arcs[i][j].info=&incinfo; g->arcs[j][i].adj=g->arcs[i][j].adj; g->arcs[j][i].info=g->arcs[i][j].info;

第27页 /共58页

flushall();scanf(\return(g);}

visited_hc vis[MAX_VERTEX_NUM];

int firstadjvex_hc(mgraph_hc*g,int v) {int i,k=-1;

for(i=0;ivexnum;i++)

if(g->arcs[v][i].adj==1){k=i;i=g->vexnum;} return(k);}

int nextadjvex_hc(mgraph_hc*g,int v,int w) {int i,k=-1;

for(i=0;ivexnum;i++)

if(g->arcs[v][i].adj==1&&i>w){k=i;i=g->vexnum;} return(k);}

void dfs_hc(mgraph_hc*g,int v) {int w;

vis[v]=TRUE; printf(\

for(w=firstadjvex_hc(g,v);w>=0;w=nextadjvex_hc(g,v,w)) if(!vis[w])dfs_hc(g,w);}

void dfstraverse_hc(mgraph_hc*g) {int v,i;char f;

for(v=0;vvexnum;v++)vis[v]=FALSE;

printf(\输入遍历开始顶点:\i=locatevex_hc(g,f);printf(\深度遍历结果为:\for(v=i;vvexnum;v++)if(!vis[v])dfs_hc(g,v); for(v=0;v

int locatevexal_hc(algraph_hc*a,char v) {int i,k=0;

for(i=0;ivexnum;i++)

if(a->vertices[i].data==v){k=i;i=a->vexnum;} return(k);}

char createlist_hc(algraph_hc*a,arcnode_hc*firstl,char v) {arcnode_hc*nextl; if(v!='\\n')

{nextl=(arcnode_hc*)malloc(sizeof(arcnode_hc)); nextl->adjvex=locatevexal_hc(a,v);

nextl->nextarc=NULL;nextl->info=firstl->info; firstl->nextarc=nextl;

第28页 /共58页

scanf(\return(v);}

algraph_hc*createaludg_hc() {algraph_hc*a;int i,incinfo;char v; a=(algraph_hc*)malloc(sizeof(algraph_hc)); a->kind=UDG;

printf(\请输入图顶点数、边数及该边相关信息:\scanf(\printf(\请输入顶点信息:\

for(i=0;ivexnum;++i)scanf(\for(i=0;ivexnum;++i)

{printf(\输入%c的邻接点:\flushall();scanf(\

a->vertices[i].firstarc=(arcnode_hc*)malloc(sizeof(arcnode_hc)); a->vertices[i].firstarc->adjvex=locatevexal_hc(a,v); a->vertices[i].firstarc->nextarc=NULL; if(incinfo)a->vertices[i].firstarc->info=&incinfo;

scanf(\return(a);}

visited_hc vis[MAX_VERTEX_NUM];

void dfsal_hc(algraph_hc*a,arcnode_hc*b,int k) {vis[k]=TRUE;

printf(\while(b) {k=b->adjvex;

if(!vis[k]){b=a->vertices[k].firstarc;dfsal_hc(a,b,k);} else b=b->nextarc;}}

void dfstraverseal_hc(algraph_hc*a) {char f;int i=0,k;

for(i=0;ivexnum;i++)vis[i]=FALSE;

printf(\遍历开始顶点:\k=locatevexal_hc(a,f); printf(\深度遍历结果:\for(i=k;ivexnum;i++)

if(!vis[k])dfsal_hc(a,a->vertices[i].firstarc,i); for(i=0;i

if(!vis[k])dfsal_hc(a,a->vertices[i].firstarc,i);}

void main()

{algraph_hc*a;mgraph_hc*g;

第29页 /共58页

char c;

printf(\邻接矩阵(M)\\n\printf(\邻接表(A)\\n\printf(\请选择:\c=getchar(); while(c!='E')

{if(c=='M'){g=createudg_hc();dfstraverse_hc(g);} else if(c=='A'){a=createaludg_hc();dfstraverseal_hc(a);} printf(\请选择:\

实验九图的最小生成树算法的实现

实验预备知识：

1．理解图最小生成树的意义和相应算法。 2．掌握带权图的存储结构。

一、实验目的

1．使学生熟悉最小生成树的算法实现。 2．掌握带权图的存储结构和处理方法。

二、实验环境

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

三、实验要求

1．能够独立完成带权图的存储和最小生成树的生成

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验9”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某电信公司要对如下图的几个城市之间进行光纤连接布线，请用合适的存储结构将下图存储到计算机中方便进行处理。

3．现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用普里姆算法和克鲁斯卡尔算法实现本图的最小生成树。

第30页 /共58页

#include \#include \#include \#define INFINITY 32767

typedef enum{FALSE,TRUE}panduan_hc;

typedef struct {int fromvex; int endvex ; int weight ; int tags ; }arclist_hc; typedef struct {char *vexs; int **vexlist; arclist_hc *gelist; int **arcs;

int vexnum, edgnum; }stgraph_hc;

int locatevex_hc(stgraph_hc*st,char v) {int i,k=0;

for(i=0;ivexnum;i++)

if(st->vexs[i]==v){k=i;i=st->vexnum;} return(k);}

stgraph_hc *creategraph_hc () {stgraph_hc *st;int i,j,x,y;char a,b;

if(!(st=(stgraph_hc*)malloc(sizeof(stgraph_hc)))){printf(\出错!\printf(\输入图的顶点数和边数:\

scanf(\

if(!(st->vexs=(char*)malloc(st->vexnum*sizeof(char)))){printf(\出错!\

if(!(st->gelist=(arclist_hc*)malloc(st->edgnum*sizeof(arclist_hc)))){printf(\出错!\if(!(st->arcs=(int**)malloc(st->vexnum*sizeof(int*)))){printf(\出错!\if(!(st->vexlist=(int**)malloc(st->vexnum*sizeof(int*)))){printf(\出错!\for(i=0;ivexnum;i++)

{if(!(st->arcs[i]=(int*)malloc(st->vexnum*sizeof(int)))){printf(\出错!\if(!(st->vexlist[i]=(int*)malloc(st->vexnum*sizeof(int)))){printf(\出错!\printf(\输入顶点:\

for(i=0;ivexnum;i++)scanf(\printf(\输入边及权值:\\n\for(i=0;iedgnum;i++)

{flushall();scanf(\x=locatevex_hc(st,a);y=locatevex_hc(st,b);

第31页 /共58页

if(xgelist[i].fromvex=x,st->gelist[i].endvex=y; else st->gelist[i].fromvex=y,st->gelist[i].endvex=x; st->gelist[i].tags=0;} for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)st->arcs[i][j]=0; for(i=0;ivexnum;i++) {st->vexlist[i][0]=i;

for(j=1;jvexnum;j++)st->vexlist[i][j]=-1;} return(st);}

int minweight_hc(stgraph_hc*st) {int i,min;

for(i=0;iedgnum;i++)

if(!st->gelist[i].tags){min=i;i=st->edgnum;} for(i=0;iedgnum;i++)

if(!st->gelist[i].tags&&st->gelist[min].weight>st->gelist[i].weight)min=i; st->gelist[min].tags=1;return(min);}

panduan_hc samegraph_hc(stgraph_hc *st,int a,int b) {int i,j,k;panduan_hc f=FALSE; for(i=0;st->vexlist[a][i]!=-1&&!f;i++) for(j=0;st->vexlist[b][j]!=-1&&!f;j++) if(st->vexlist[a][i]==st->vexlist[b][j])f=TRUE; if(!f)

{for(i=0;ivexnum;i++)

{for(j=0;jvexnum&&st->vexlist[i][j]!=-1;j++) {if(st->vexlist[i][j]==a)

{k=+j;while(st->vexlist[i][k]!=-1)k++;st->vexlist[i][k]=b;j=st->vexnum;} else if(st->vexlist[i][j]==b)

{k=+j;while(st->vexlist[i][k]!=-1)k++;st->vexlist[i][k]=a;j=st->vexnum;}}}} return(f);}

stgraph_hc*minspandtree_hc(stgraph_hc*st) {int i,a,b,min;

for(i=0;ivexnum-1;i++) {min=minweight_hc(st);

a=st->gelist[min].fromvex;b=st->gelist[min].endvex; if(samegraph_hc(st,a,b))i--;

else st->arcs[a][b]=st->arcs[b][a]=st->gelist[min].weight;} free(st->vexlist);free(st->gelist); return(st);}

void printst(stgraph_hc*st) {int i,j;

第32页 /共58页

printf(\最小生成树为:\\n\for(i=0;ivexnum;i++) {for(j=0;jvexnum;j++)

printf(\printf(\需要连通的点有:\for(i=0;ivexnum;i++) for(j=i;jvexnum;j++)

if(st->arcs[i][j])printf(\ \

void main() {stgraph_hc *st; st=creategraph_hc(); st=minspandtree_hc(st); printst(st);}

实验十图的最短路径算法的实现

实验预备知识：

1．理解图最短路径的意义和相应算法。 2．掌握带权图的存储结构。

一、实验目的

1．使学生熟悉最短路径算法实现。 2．掌握带权图的存储结构和处理方法。

二、实验环境

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

三、实验要求

1．能够独立完成带权图的存储和最短路径的生成。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验10”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到计算机中方便进行处理。

第33页 /共58页

3．现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra 算法实现我的要求的路径。

#include \#include \

typedef struct {int *vexs; int **arcs; int vexnum; }graph_hc;

typedef struct {int adjvex; int lowcost; }markedg_hc;

graph_hc*initgraph_hc() {int i,j;graph_hc*g;

g=(graph_hc*)malloc(sizeof(graph_hc)); g->vexnum=25;

g->vexs=(int*)malloc(g->vexnum*sizeof(int)); g->arcs=(int**)malloc(g->vexnum*sizeof(int*)); for(i=0;ivexnum;i++)

g->arcs[i]=(int*)malloc(g->vexnum*sizeof(int)); for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) {g->arcs[i][j]=0;}

第34页 /共58页

return g;}

void creategraph_hc(graph_hc *g) {int i,j;

for(i=0;ivexnum;i++)g->vexs[i]=i; g->arcs[0][9]=1892; g->arcs[1][3]=242; g->arcs[2][4]=668; g->arcs[2][9]=1145; g->arcs[3][5]=305; g->arcs[4][6]=137; g->arcs[4][11]=695; g->arcs[5][6]=704; g->arcs[5][7]=397; g->arcs[6][12]=674; g->arcs[8][9]=216; g->arcs[9][10]=676; g->arcs[10][11]=511;g->arcs[10][13]=842; g->arcs[11][12]=349;g->arcs[11][14]=534; g->arcs[12][15]=651;g->arcs[13][16]=110; g->arcs[13][17]=967;g->arcs[14][18]=409; g->arcs[15][19]=825;g->arcs[16][17]=639; g->arcs[17][18]=902;g->arcs[17][21]=607; g->arcs[18][19]=367;g->arcs[18][21]=672; g->arcs[18][23]=675;g->arcs[19][20]=622; g->arcs[21][22]=255;g->arcs[23][24]=140; for(i=0;ivexnum;i++) for(j=i;jvexnum;j++) if(g->arcs[i][j])

g->arcs[j][i]=g->arcs[i][j];}

void printgraph_hc(graph_hc*g) {int x,y;

printf(\城市间连通图为:\\n\for(x=0;xvexnum;x++) for(y=x;yvexnum;y++)

if(g->arcs[x][y])printf(\距离:%d\\t\

int selectnearvex_hc(markedg_hc*mark,int *flag,int num) {int j; int nearestv; int lowcost=32767; for(j=0;j

{if(flag[j]!=1&&mark[j].lowcost

lowcost=mark[j].lowcost;}} flag[nearestv]=1; return nearestv;}

void markothervex_hc(graph_hc*g,markedg_hc*mark,int nearestv,int num,int*flag)

第35页 /共58页

{int j;

for(j=0;jarcs[nearestv][j]>0) {if(flag[j]!=1)

{if(mark[j].lowcost>(mark[nearestv].lowcost+g->arcs[nearestv][j])) {mark[j].lowcost= mark[nearestv].lowcost+g->arcs[nearestv][j]; mark[j].adjvex=nearestv;}}}}}

void shortestpath_hc(graph_hc*g,markedg_hc*mark,int start) {int i,num; int *flag; int nearestv; num=g->vexnum;

flag=(int *)malloc((num)*sizeof(int)); flag[start]=1;

for(i=0;ivexnum;i++) {mark[i].adjvex=start; if( g->arcs[start][i]>0)

{mark[i].lowcost=g->arcs[start][i];} else

{mark[i].lowcost=32767;}} for(i=1;ivexnum;i++)

{nearestv=selectnearvex_hc(mark,flag,num); markothervex_hc(g,mark,nearestv,num,flag);}}

void printshortpath_hc(graph_hc*g,markedg_hc*mark,int start) {int i,j,k,path[25]; for(i=0;ivexnum;i++) {if(i!=start)

{printf(\从%d到%d最短路径为:%d; \printf(\途经:\k=0;path[k]=i; j=mark[i].adjvex; while(j!=start) {path[++k]=j; j=mark[j].adjvex;} printf(\

for(j=k;j>=0;j--)printf(\printf(\ main() {int city;

graph_hc*g;markedg_hc*mark; g=initgraph_hc();

第36页 /共58页

creategraph_hc(g); printf(\城市名称/代号:\

printf(\乌鲁木齐/0, 哈尔滨/1, 呼和浩特/2, 长春/3, 北京/4, \printf(\沈阳/5, 天津/6, 大连/7, 西宁/8, 兰州/9, 西安/10, 郑州/11, \printf(\徐州/12, 成都/13, 武汉/14, 上海/15, 昆明/16, 贵阳/17, 株州/18,\printf(\南昌/19, 福州/20, 柳州/21, 南宁/22, 广州/23, 深圳/24.\\n\printgraph_hc(g);

mark=(markedg_hc*)malloc(g->vexnum*sizeof(markedg_hc)); printf(\输入起始城市:\shortestpath_hc(g,mark,city); printshortpath_hc(g,mark,city);

}

实验十一顺序表查找算法的实现

实验预备知识：

1．理解记录、关键字和查找的相关概念。 2．熟练掌握顺序表的存储结构。

一、实验目的

1．掌握排序算法及基本思想及实现的技术；能够根据实际问题特点的要求选择合理的排序方法；理解排序在数据处理中的重要性；

2．学会比较各种排序方法的稳定性分析以及在最好、最坏和平均情况的时间性能分析。 3．掌握顺序查找和折半查找两种查找的算法及实现技术；了解它们各自的优缺点。 4．熟悉各种查找方法的适用范围和条件；掌握顺序查找、折半查找的基本思想及效率分析。

二、实验环境

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

三、实验要求

1．本次实验较为简单，每个同学独立按时完成，通过实验掌握记录的概念，为以后数据库技术打好基础。

2．如果输入数据较为繁琐，可减低每个班的人数。 3．输入输出数据要有提示，方便用户操作。

第37页 /共58页

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验11”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某个学院有20名同学分属于2个班级（Class1 和Class2，每个班有10名同学，每个同学记录包括：班级、学号、姓名、性别、电话号码等信息）。

3．以学号为主关键字，以班级为次关键字，建立一个顺序表，表中的每个数据元素是一个记录，其中的某个域用来存储关键字的值，按关键字的值进行顺序查找。为分析排序方法的稳定性，关键字可用次关键字。

4．完成如下函数（其中查找函数用顺序查询和折半查询两种方式实现），注意折半查询只适合有序的顺序表：

3．思考两种查找的效率分析和适用场合。 #include \#include \#include \

typedef struct {int cla; int num;

char name[20]; char sex;

long phonenum; }student;

typedef struct {student *elem; int length; int sum; }ST;

ST *initlist() {ST *l;

l=(ST*)malloc(sizeof(ST));

第38页 /共58页

if(!l)printf(\没有创建ST!\\n\

l->length=0;l->sum=3;

l->elem=(student*)malloc(3*sizeof(student)); if(!l->elem)printf(\没有创建elem!\\n\return(l); }

int place(ST *l,int c,int num) {int low,high,mid,j=-1,i; low=0;high=l->length-1; while(low<=high) {mid=(low+high)/2;

if(l->elem[mid].num>num)high=mid-1; else {j=mid;low=mid+1;}} i=j;

for(j=mid;j>=i;j--)

{if(j==-1||num>l->elem[j].num)break;

else if(num==l->elem[j].num&&c>l->elem[j].cla)break;} return(++j);}

void move(ST *l,int j) {int i;

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

{l->elem[i+1].cla=l->elem[i].cla;

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

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

void createlist(ST *l) {int i,j,c,num;

char nam[20],s;long p;

printf(\输入学生信息(class name num sex phonenum):\\n\for(i=0;isum;i++) {flushall();

scanf(\j=!(l->length)?0:place(l,c,num); move(l,j);

l->elem[j].cla=c;

strcpy(l->elem[j].name,nam); l->elem[j].num=num; l->elem[j].sex=s;

l->elem[j].phonenum=p;

第39页 /共58页

l->length++;}}

void searchban(ST *l) {int low,high,mid,num,c;

printf(\输入查找人的学号和班级号:\scanf(\if(num!=-1||c!=-1)

{low=0;high=l->length-1; while(low<=high) {mid=(low+high)/2;

if(l->elem[mid].numelem[mid].num>num)high=mid-1; else {if(l->elem[mid].claelem[mid].cla>c)mid--; break;}}

printf(\e,l->elem[mid].num,l->elem[mid].sex,l->elem[mid].phonenum); } }

void searchshun(ST *l) {int num,c,i;

printf(\输入查找人的学号和班级号:\scanf(\for(i=0;i<=l->length;i++)

if(l->elem[i].num==num)break; if(i!=l->length)

printf(\em[i].num,l->elem[i].sex,l->elem[i].phonenum); else

printf(\无此人！\ }

void printlist(ST *l) {int i,j=0;

printf(\当前表中信息如下:class/name/num/sex/phonenum\\n\for(i=0;isum;i++)

{printf(\elem[i].num,l->elem[i].sex,l->elem[i].phonenum); if(++j==3){j=0;printf(\printf(\

第40页 /共58页

void main() {ST *l; ST *l2;

printf(\

l=initlist();createlist(l);printlist(l); printf(\用折半查询实现class1\\n\searchban(l); printf(\l2=initlist(); createlist(l2); printlist(l2);

printf(\用顺序查询实现class2\\n\searchshun(l2); }

实验十二有序表查找算法的实现

实验预备知识：

1．理解记录、关键字和查找的相关概念。 2．熟练掌握有序表的存储结构。

一、实验目的

1．掌握排序算法及基本思想及实现的技术；能够根据实际问题特点的要求选择合理的排序方法；理解排序在数据处理中的重要性；

二、实验环境

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

三、实验要求

1．本次实验较为简单，每个同学独立按时完成，通过实验掌握记录的概念，为以后数据库技术打好基础。

2．如果输入数据较为繁琐，可减低每个班的人数。 3．输入输出数据要有提示，方便用户操作。

第41页 /共58页

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验11”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某个学院有20名同学分属于2个班级（Class1 和Class2，每个班有10名同学，每个同学记录包括：班级、学号、姓名、性别、电话号码等信息）。

4．完成如下函数（其中查找函数用顺序查询和折半查询两种方式实现），注意折半查询只适合有序的顺序表：

3．思考两种查找的效率分析和适用场合。 #include \#include \#include \

typedef struct {int cla; int num;

char name[20]; char sex;

long phonenum; }student;

typedef struct {student *elem; int length; int sum; }ST;

ST *initlist() {ST *l;

l=(ST*)malloc(sizeof(ST));

第42页 /共58页

if(!l)printf(\没有创建ST!\\n\

l->length=0;l->sum=3;

l->elem=(student*)malloc(3*sizeof(student)); if(!l->elem)printf(\没有创建elem!\\n\return(l); }

int place(ST *l,int c,int num) {int low,high,mid,j=-1,i; low=0;high=l->length-1; while(low<=high) {mid=(low+high)/2;

if(l->elem[mid].num>num)high=mid-1; else {j=mid;low=mid+1;}} i=j;

for(j=mid;j>=i;j--)

{if(j==-1||num>l->elem[j].num)break;

else if(num==l->elem[j].num&&c>l->elem[j].cla)break;} return(++j);}

void move(ST *l,int j) {int i;

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

{l->elem[i+1].cla=l->elem[i].cla;

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

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

void createlist(ST *l) {int i,j,c,num;

char nam[20],s;long p;

printf(\输入学生信息(class name num sex phonenum):\\n\for(i=0;isum;i++) {flushall();

scanf(\j=!(l->length)?0:place(l,c,num); move(l,j);

l->elem[j].cla=c;

strcpy(l->elem[j].name,nam); l->elem[j].num=num; l->elem[j].sex=s;

l->elem[j].phonenum=p;

第43页 /共58页

l->length++;}}

void searchshun(ST *l) {int num,c,i;

printf(\输入查找人的学号和班级号:\scanf(\for(i=0;i<=l->length;i++)

if(l->elem[i].num==num)break; if(i!=l->length)

printf(\em[i].num,l->elem[i].sex,l->elem[i].phonenum); else

printf(\无此人！\ }

void printlist(ST *l) {int i,j=0;

printf(\当前表中信息如下:class/name/num/sex/phonenum\\n\for(i=0;isum;i++)

{printf(\elem[i].num,l->elem[i].sex,l->elem[i].phonenum); if(++j==3){j=0;printf(\printf(\

void main() {

ST *l2; l2=initlist(); createlist(l2); printlist(l2);

printf(\用顺序查询实现class2\\n\searchshun(l2); }

实验十三二叉排序树的查找算法实现

实验预备知识：

1．理解哈希函数和哈希表。

2．掌握各种哈希函数和冲突解决办法。

第44页 /共58页

一、实验目的

1．理解动态查找表的动态生成过程； 2．掌握二叉排序树的建立和查找；

二、实验环境

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

三、实验要求

1．定义二叉排序树的数据结构；

2．实现二叉排序树的插入算法与查找算法，并建立二叉排序树； 3．进行数据查找和建树过程的比较。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验12”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．已知一个个数为12的数据元素序列为{Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May, July,Jan,Mar},要求：

（1）按各数据元素的顺序（字母大小顺序）构造一棵二叉排序数，并中序打印排序结果。

（2）查找数据\是否存在。

3．已知一棵二叉排序树，其根结点的地址为 root。请编写一个程序，构造出一棵具有相同结点的满二叉树，且它同样是二叉排序树。提示：可利用中序遍历，分别找出各个结点序列的中点元素，然后重新构造一棵二叉排序树。 #include #include #include struct month { char y[5]; }y[12];

typedef struct Lnode//二叉排序树的创建，采用二叉链表 {

struct Lnode *lchild,*rchild; char data[5]; }node;

int BSTsearch(node *h, char c[5]) {

if (h==NULL) {

第45页 /共58页

return 0;

}//查找失败，返回0 else {

if(strcmp(c,h->data)==0) {

c=h->data; return 1; }

else if(strcmp(c , h->data)<0) {

return BSTsearch(h->lchild,c); } else {

return BSTsearch(h->rchild,c); } } }