算法及数据结构实验

学 生 实 验 报 告 册

课程名称：算法与数据构造

学生学号：学生：

所属院部：

. 〔理工类〕

专业班级

计算机工程学院 指导教师： 章海鸥

2016 ——2017 学年 第 1 学期

金陵科技学院教务处制

. word.zl-

. -

实验报告书写要求

实验报告原那么上要求学生手写，要求书写工整。假设因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸一律采用A4的纸。

实验报告书写说明

实验报告中一至四项容为必填项，包括实验目的和要求；实验仪器和设备；实验容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加工程。

填写考前须知

〔1〕细致观察，及时、准确、如实记录。 〔2〕准确说明，层次清晰。

〔3〕尽量采用专用术语来说明事物。

〔4〕外文、符号、公式要准确，应使用统一规定的名词和符号。 〔5〕应完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。

实验报告批改说明

实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。

实验报告装订要求

实验批改完毕后，任课教师将每门课程的每个实验工程的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。

. . word.zl-

. -

实验工程名称： 顺序表 实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

. . word.zl-

. -

实验1 顺序表

一、实验目的和要求

掌握顺序表的定位、插入、删除等操作。

二、实验仪器和设备

VC6.0

三、实验容与过程〔含程序清单及流程图〕

1、必做题

（1） 编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。

编写主函数测试结果。

（2） 编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。

如果存在，返回顺序表中和x值相等的第1个数据元素的序号〔序号从0开场编号〕；如果不存在，返回－1。编写主函数测试结果。 （3） 在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。

解题思路：首先查找插入的位置，再移位，最后进展插入操作；从第一个元素开场找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开场依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。

（4） 删除顺序表中所有等于X的数据元素。 2、选做题

（5） 两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和

B归并成一个按元素值递减有序排列的顺序表〔允许表中含有值一样

. . word.zl-

. -

的元素〕。

程序清单：

(1)

#include #define maxsize 20 typedef int datatype; typedef struct{ datatype data[maxsize]; int last; }sequenlist;

void CreateList(sequenlist *L,int n) {int i;

printf(\"please input n numbers\\n\"); for(i=0;iscanf(\"%d\ (*L).last=n; } }

void PrintList(sequenlist *L,int n)

. . word.zl-

. -

{int i;

printf(\"the sequenlist is\\n\"); for(i=0;iprintf(\"%d \} main() { int i,x; int n=10; sequenlist L; CreateList(&L,n); PrintList(&L,n); getchar(); } (2)

#include typedef int datatype; #define maxsize 1024 typedef struct {

. . word.zl-

. -

datatype data[maxsize]; int last; }sequenlist;

int fun(sequenlist L,int x,int n) { int i;

for(i=0;ireturn i;

return -1;

} void main() { sequenlist L; int i,n,y;

int x; printf(\"请输入元素的个数：\"); scanf(\"%d\ for(i=0;iscanf(\"%d\

. . word.zl-

. -

}

printf(\"\\n请输入要查找的数据元素：\"); scanf(\"%d\ y = fun(L,x,n); if (y==1)

printf(\"\\n所要查找的数据元素不存在\\n\");

else

printf(\"\\n数据元素%d所在的位置为%d\\n\

} (3)

#include #define maxsize 100 typedef struct { int data[maxsize];

int last;

}sequenlist; main() { int i,x,j;

sequenlist l={{1,2,4,5,6,7,8},6};

. . word.zl-

. -

printf(\"\\n插入元素前的数据为:\"); for(i=0;i<=l.last;i++) printf(\"%2d\

printf(\"\\n请输入要插入的元素:\"); scanf(\"%d\ for(i=1;i<=l.last;i++)

if(l.data[i-1]>x) break;

if(i>l.last ) { l.data [l.last +1]=x;

} else { for(j=l.last;j>=i-1;j--) l.data[j+1]=l.data[j]; l.data[i-1]=x;

} l.last++;

printf(\"插入元素后的数据为:\\n\"); for(j=0;j<=l.last;j++) printf(\"%3d\ printf(\"\\n\");

. . word.zl-

. -

return 0;

} (4)

#include #define maxsize 100 typedef struct { int data[maxsize];

int last;

}sequenlist; main() { int i,j,x=0,k=0;

sequenlist L={{1,3,5,7,2,4,6,8,2,9},9};

printf(\"\\n原数据为:\"); for(i=0;i<=L.last;i++) printf(\"%3d\ printf(\"\\n请输入要删除的数据:\"); scanf(\"%d\ for(i=1;i<=L.last+1;i++)

if(L.data[i-1]==x)

. . word.zl-

. -

{ for(j=i;j<=L.last+1;j++) L.data[j-1]=L.data[j]; L.last--; i--; k=1;

}

if(k==1) { printf(\"删除后的数据为:\\n\"); for(j=0;j<=L.last;j++)

printf(\"%3d\

}

else printf(\"Not found!\\n\");

printf(\"\\n\");

}

四、实验结果与分析〔程序运行结果及其分析〕

1.1

1.2

. . word.zl-

. -

1.3

1.4

五、实验体会〔遇到问题及解决方法，编程后的心得体会〕

遇到问题：读取数据元素时，误将==写成=，导致错误。实验过程中，顺序表的赋值没有弄懂，以致输出多个0或者少输出。格式运算符也要正确控制，否那么系统会停顿工作。

实验体会：通过实验掌握了顺序表的根本操作，如初始化、插入、读取元素、删除等等。并了解到线性表顺序存储构造的特点，即逻辑关系上相邻的两个元素在物理位置上也相邻，然而从另一方面来看，在做插入和删除时需要移动大量元素。本次实验根本完成了实验要求的目的，顺序表的初始化，定义，插入，查找等，更好的了解了顺序表根本操作的算法，以及更直观的了解了数据构造在C语言环境下的表达。

. . word.zl-

. -

实验工程名称： 单链表 实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

. . word.zl-

. -

实验2 单链表

一、实验目的和要求

1、实验目的

掌握单链表的定位、插入、删除等操作。 2、实验要求

〔1〕注意链表的空间是动态分配的，某结点不用之后要及时进展物理删除，以便释放其存空间。

〔2〕链表不能实现直接定位，一定注意指针的保存，防止丧失。

二、实验仪器和设备

Visual C++6.0

三、实验容与过程〔含程序清单及流程图〕

1、必做题

（1） 编写程序建立一个单链表，并逐个输出单链表中所有数据元素。 （2） 在递增有序的单链表中插入一个新结点x，保持单链表的有序性。

解题思路：首先查找插入的位置然后进展插入操作；从第一个结点开场找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保存插入位置之前结点的指针才能完成插入操作。

（3） 编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。 2、选做题

指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实

. . word.zl-

. -

现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。 程序清单：

〔1〕

#include #include typedef struct node{

int data; struct node *next; }*Linklist,Node;

Linklist creat(int n) {

Linklist head,r,p; int x,i;

head=(Node*)malloc(sizeof(Node)); r=head;

printf(\"输入数字:\\n\"); for(i=n;i>0;i--) {

scanf(\"%d\

. . word.zl-

. -

p=(Node*)malloc(sizeof(Node)); p->data=x; r->next=p;

r=p;

}

r->next=NULL; return head; }

void output(Linklist head) { Linklist p;

p=head->next; do{ printf(\"%3d\

p=p->next; }while(p);

printf(\"\\n\"); } void main()

. . word.zl-

. -

{ Linklist head; int x,n;

printf(\"输入数字的个数(n):\\n\"); scanf(\"%d\ head=creat(n); printf(\"输出数字:\\n\"); output(head);

} 〔2〕

#include #include typedef struct node { int data; struct node *next; } linklist; main() { int x,y;

. . word.zl-

. -

linklist *h,*s,*r,*p,*q,*m,*n; h=malloc(sizeof(linklist)); r=h;

printf(\"请输入一个数组 :\"); scanf(\"%d\ while(x!=0) {

s=malloc(sizeof(linklist)); s->data=x; r->next=s; r=s;

scanf(\"%d\ }

r->next=NULL; printf(\"请输入插入值:\"); scanf(\"%d\ p=h->next; while(p!=NULL) {

if ((p->data)p=p->next;

else

. . word.zl-

. -

break;

}

q=malloc(sizeof(linklist)); q->data=y; m=h;

while(m->next!=p)

m=m->next;

q->next=p; m->next=q; n=h->next;

printf(\"这个链表是:\"); while(n!=NULL) {

printf(\"%2d\ n=n->next; } } 〔3〕

#include #include typedef struct node {

. . word.zl-

. -

int data; struct node *next; } linklist; main() { int x;

linklist *h,*s,*r,*p,*q,*t; h=malloc(sizeof(linklist)); r=h;

printf(\"请输入一个数组:\"); scanf(\"%d\ while(x!=-1) {

s=malloc(sizeof(linklist)); s->data=x; r->next=s; r=s;

scanf(\"%d\ }

r->next=NULL;

printf(\"\\n这个链表是:\\n\");

. . word.zl-

. -

p=h->next; while(p!=NULL) {

printf(\"%2d\ p=p->next; }

p=h->next; q=p->next; while(q!=NULL) {

t=q->next; q->next=p; p=q; q=t; }

h->next->next=NULL; h->next=p;

printf(\"\\n翻转转后的链表是:\\n\"); p=h->next; while(p!=NULL) {

printf(\"%2d\

. . word.zl-

. -

p=p->next; } }

四、实验结果与分析〔程序运行结果及其分析〕

(1)

(2)

(3)

五、实验体会〔遇到问题及解决方法，编程后的心得体会〕

遇到问题：编写成功后运行时，没有参加$导致程序运行不成功，不能够退出。后注意到这个问题才继续运行下去。

实验体会：在编写程序时，设置了完毕字符一定要牢牢记住，并且在输入时观察仔细类型是什么，以及是否是输入一串有顺序的数字，编写成功不难，但是要规格式，不能仅仅以完成程序为目的。而完成这一章的实验也让我了解了，顺

. . word.zl-

. -

序表便于查找不便于插入删除，而链表恰恰相反，链表的插入删除只需要移动指针，而顺序表要从后往前依次移动，二者各有优劣.

. . word.zl-

. -

. . word.zl-

. -

实验工程名称： 堆栈和队列 实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

. . word.zl-

. -

实验3 堆栈和队列

一、实验目的和要求

〔1〕掌握应用栈解决问题的方法。 〔2〕掌握利用栈进展表达式求和的算法。

〔3〕掌握队列的存储构造及根本操作实现，并能在相应的应用问题中正确选用它们。

二、实验仪器和设备

Visual C++6.0

三、实验容与过程〔含程序清单及流程图〕

1、必做题

（1） 判断一个算术表达式中开括号和闭括号是否配对。 （2） 测试“汉诺塔〞问题。

（3） 假设称正读和反读都一样的字符序列为〞回文〞，试写一个算法判别读入的一个以’’为完毕符的字符序列是否是“回文〞。 2、选做题

在顺序存储构造上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原那么，假设一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，那么插入在队头，否那么插入在队尾。 程序清单：

〔1〕

#include

. . word.zl-

. -

#include typedef char datatype; #define maxsize typedef struct {

datatype data[maxsize]; int top; }seqstack;

int match(char exp[],int n)

{char st[maxsize]; //设置一个栈，用来存放扫描表达式中的括号 int top=-1,i=0,tag=1; while(i{if(exp[i]=='('||exp[i]=='['||exp[i]=='{') //遇到'(''[''{',那么将其入栈 { top++;

st[top]=exp[i]; }

if(exp[i]==')') //遇到')',假设栈顶是'(',那么继续处理，否那么以不配对返回

. . word.zl-

. -

if(st[top]=='(') top--; else tag=0; if(exp[i]==']')

if(st[top]=='[') top--; else tag=0; if(exp[i]=='}')

if(st[top]=='{') top--; else tag=0;

i++; }

if(top>=0) tag=0; //假设栈不空，那么不配对 return tag; } main() {int tag,i;

char exp[7]={'+','(','2','-','4',')'};

printf(\"请输入一个算式表达式：\\n\"); for(i=0;i<7;i++) exp[i]=getchar(); tag=match(exp,7);

. . word.zl-

. -

if(tag)

printf(\"算式表达式中的开括号和闭括号配对。\"); else

printf(\"算式表达式中的开括号和闭括号不配对！\"); } (2)

#include

void move(char x,char z) {printf(\"%c-->\ printf(\"%c\\n\}

void Hanoi(int n,char x, char y,char z) { if(n==1) move(x,z); else

{Hanoi(n-1,x,z,y);

. . word.zl-

. -

move(x,z); Hanoi(n-1,y,x,z); } } main() { int m;

printf(\"请你输入A上面的碟子总数\"); scanf(\"%d\ Hanoi(m,'A','B','C'); getchar(); getchar(); } (3)

#include #define N 100 typedef struct {

char data[N]; int top; } seqstack;

. . word.zl-

. -

main() {

char str[N]; int i=0,n; seqstack a; a.top=0; gets(str); while(str[i]!='')

i++;

n=i;

for(i=0;ia.top++; a.data[a.top]=str[i]; } i=i-1; if(n%2==0) i++; else i=i+2;

while(i. . word.zl-

. -

i++; a.top--; } if(i==n)

printf(\"是回文数组\\n\");

else }

printf(\"不是回文数组\\n\");

四、实验结果与分析〔程序运行结果及其分析〕 1

2

3

. . word.zl-

. -

五、实验体会〔遇到问题及解决方法，编程后的心得体会〕

遇到问题：在本章栈和队列中编程，有许多的if语句，编写时一不小心就会少加一个花括号，以致编写不成功。在本章汉诺塔问题中，使用了栈以及函数的递归，这其中的过程一直不是很了解，在经过教师的讲解后，理解了大致过程。

实验体会：递归函数是编程中经常会用到的一种函数，它可以实现许多我们在平时言语和解释上解决不了的问题，我们需要理解并且可以熟练的使用它，这对我们之后的编程会有很大的帮助。而汉诺塔利用栈是一种很经典的递归的算法，这让我们理解栈和递归。

. . word.zl-

. -

实验工程名称： 串 实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

. . word.zl-

. -

实验4 串

一、实验目的和要求

掌握串的存储及应用。

二、实验仪器和设备

Visual C++6.0

三、实验容与过程〔含程序清单及流程图〕

1、必做题

（1） 编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数

测试结果。

（2） 编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测

试结果。

解题思路：可以将第一题程序改良成一个子函数，在此题中循环调用。 （3） 设字符串采用单字符的链式存储构造，编程删除串s从位置i开场长度

为k的子串。

2、选做题

假设以链构造表示串，编写算法实现将串S插入到串T中某个字符之后，假设串T中不存在这个字符，那么将串S联接在串T的末尾。 提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。 程序清单： (1)

#include

. . word.zl-

. -

void search(char *s,char ch) { int i=0,n=0; while (*(s+i)) { if(*(s+i)==ch) { printf(\"第一个字符：s[%d]=%c\\n\ n++; break;

} i++;

}

if(!n)

printf(\"No Found!\\n\");

} void main() { char s[20],ch;

printf(\"请输入一个串:\"); gets(s);

printf(\"请输入要找的元素:\"); . . word.zl-

. -

scanf(\"%c\ search(s,ch);

} (2)

#include void search(char *s,char ch) { int i=0,n=0; while (*(s+i)) { if(*(s+i)==ch) { n++;

printf(\"第%d个%c在串中的下标为：%d\\n\

} i++;

} if(!n)

printf(\"No Found!\\n\"); } void main() {

. . word.zl-

. -

char s[20],ch;

printf(\"请输入串元素：\"); gets(s);

printf(\"请输入要找的元素：\"); scanf(\"%c\ search(s,ch);

} (3)

#include #include typedef struct linknode { char data;

struct linknode *next;

}linkstring; linkstring *CREAT() { linkstring *head = NULL,*p = NULL,*s = NULL; int a;

printf(\"请输入顺序表的值，'-1'表示输入完毕：\\n\"); scanf (\"%d\

while (a!=-1)

. . word.zl-

. -

{ s= (linkstring *)malloc(sizeof(linkstring)); if (s == NULL)

exit(0);

s->data = a; if(head == NULL)

head = s;

else

p->next = s;

p=s;

scanf (\"%d\

}

p->next = NULL; printf(\"建立完毕！\\n\"); return head;

}

int SEARCH(linkstring *s,int i, int k) { linkstring *p =s; int j= 0;

for(;jnext!=NULL;j++)

{

. . word.zl-

. -

p = p->next;

}

if(j==i+k-2)

return 1;

return 0;

}

void DELETE(linkstring *s,int i,int k) { linkstring *p = s,*q = NULL; int j=1; for(;jnext;

}

for(j=0;jnext; p->next = q->next; free(q);

}

printf(\"成功删除！\"); }

. . word.zl-

. -

void PRINT(linkstring *head) { linkstring *s = NULL; s = head; while (s) { printf(\"%d \ s= s->next;

}

printf(\"打印完毕！\\n\\n\");

} int main() { linkstring *ls; int i,k,m; ls = CREAT(); PRINT(ls);

printf(\"输入你想删除第几个字符起的连续的多少个字符：\"); scanf (\"%d%d\ m = SEARCH(ls,i,k); if(m==0)

printf(\"不存在这样的子串，删除失败！\");

. . word.zl-

. -

}

else { } return 0;

DELETE(ls,i,k); PRINT(ls);

四、实验结果与分析〔程序运行结果及其分析〕 (1)

(2)

(3)

五、实验体会〔遇到问题及解决方法，编程后的心得体会〕

. . word.zl-

. -

实验体会：本章第一题可以作为第二题的子函数，使用调用；也可以从开头查找对应的字符到结尾，最后全部输出。前两题使用顺序串，后面一题是链串。串的存储构造包含有顺序存储构造和链式存储构造。在串的顺序存储构造中，表示串的长度通常有两种方法：一种方法是设置一个串的长度参数，其优点在于便于在算法中用长度参数控制循环过程；另一种方法是在串值得末尾添加完毕标记，此种方法的优点在于便于系统自动实现。在串的存储过程中，串值用双引号引起来，系统将自动在串值得末尾添加完毕标记\\0字符。

. . word.zl-

. -

实验工程名称： 二叉树 实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

. . word.zl-

. -

实验5 二叉树

一、实验目的和要求

〔1〕掌握二叉树的生成，以及前、中、后序遍历算法。 〔2〕掌握应用二叉树递归遍历思想解决问题的方法。

二、实验仪器和设备

Visual C++6.0

三、实验容与过程〔含程序清单及流程图〕

1、必做题

（1） 建立一棵二叉树。对此树进展前序遍历、中序遍历及后序遍历，输出

遍历序列。

（2） 在第一题根底上，求二叉树中叶结点的个数。 （3） 在第一题根底上，求二叉树中结点总数。 （4） 在第一题根底上，求二叉树的深度。 2、选做题

一棵完全二叉树存于顺序表sa中，sa.elem[1…sa.last]存储结点的值。试编写算法由此顺序存储构造建立该二叉树的二叉链表。

解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“复原〞了二叉树，之后再按照二叉树二叉链表的构造方法进展建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。 程序清单：

. . word.zl-

. -

〔1〕

#include #include #define maxsize 20 typedef struct node{ char data;

struct node *lchild,*rchild; }bitree;

bitree *Q[maxsize]; bitree *Creatree(){ char ch; int front,rear; bitree *root,*s;

root=NULL;front=1;rear=0;

printf(\"Now Creat the bitree,input baseing the order top to bottom,left to right:\\n\"); ch=getchar(); while(ch!='#'){ s=NULL; if(ch!=''){

s=malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL;

. . word.zl-

. -

s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1) root=s; else{

if(s && Q[front]) if(rear%2==0) Q[front]->lchild=s; else

Q[front]->rchild=s;

if(rear%2==1) front++; }

ch=getchar(); }

return root; }

void preorder(t) bitree *t; { if(t) {

printf(\"%c\

. . word.zl-

. -

preorder(t->lchild); preorder(t->rchild); } }

void inorder(t) bitree *t; { if(t){

inorder(t->lchild); printf(\"%c\ inorder(t->rchild); } }

void postorder(t) bitree *t; { if(t){

postorder(t->lchild); postorder(t->rchild); printf(\"%c\

. . word.zl-

. -

} } main(){ bitree *root; root=Creatree();

printf(\"preorder is:\");preorder(root); printf(\"\\n\");

printf(\"inorder is:\");inorder(root); printf(\"\\n\");

printf(\"postorder is:\");postorder(root); printf(\"\\n\"); } (2)

#include #include #define maxsize 100 typedef struct node{ char data;

struct node *lchild,*rchild; }bitree;

. . word.zl-

. -

bitree *Q[maxsize]; bitree *Creatree(){ char ch; int front,rear; bitree *root,*s;

root=NULL;front=1;rear=0;

printf(\"Now Creat the bitree,input baseing the order top to bottom,left to right:\\n\"); ch=getchar(); while(ch!='#'){ s=NULL; if(ch!=''){

s=malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1) root=s; else{

if(s && Q[front])

if(rear%2==0) Q[front]->lchild=s;

. . word.zl-

. -

else

Q[front]->rchild=s;

if(rear%2==1) front++; }

ch=getchar(); }

return root; }

int left(bitree *t){ int num1,num2; if(t==NULL) return 0;

else if(t->lchild==NULL && t->rchild==NULL) else{

num1=left(t->lchild); num2=left(t->rchild); return(num1+num2); } } main(){ bitree *root;

. return 1; . word.zl-

. -

root=Creatree();

printf(\"lefts is %d\\n\} (3)

#include #include #define maxsize 100 typedef struct node{ char data;

struct node *lchild,*rchild; }bitree;

bitree *Q[maxsize]; bitree *Creatree(){ char ch; int front,rear; bitree *root,*s;

root=NULL;front=1;rear=0;

printf(\"Now Creat the bitree,input baseing the order top to bottom,left to right:\\n\"); ch=getchar(); while(ch!='#'){ s=NULL; if(ch!=''){

. . word.zl-

. -

s=malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1) root=s; else{

if(s && Q[front]) if(rear%2==0) Q[front]->lchild=s; else

Q[front]->rchild=s;

if(rear%2==1) front++; }

ch=getchar(); }

return root; }

int nodes(bitree *t){ int num1,num2;

. . word.zl-

. -

if(t==NULL) return 0;

else if(t->lchild==NULL &&t->rchild==NULL) return 1; else{

num1=nodes(t->lchild); num2=nodes(t->rchild); return (num1+num2+1); } } main(){ bitree *root; root=Creatree();

printf(\"nodes is %d\\n\} (4)

#include #include #define maxsize 100 typedef struct node{ char data;

struct node *lchild,*rchild; }bitree;

. . word.zl-

. -

bitree *Q[maxsize]; bitree *Creatree(){ char ch; int front,rear; bitree *root,*s;

root=NULL;front=1;rear=0;

printf(\"Now Creat the bitree,input baseing the order top to bottom,left to right:\\n\"); ch=getchar(); while(ch!='#'){ s=NULL; if(ch!=''){

s=malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1) root=s; else{

if(s && Q[front])

if(rear%2==0) Q[front]->lchild=s;

. . word.zl-

. -

else

Q[front]->rchild=s;

if(rear%2==1) front++; }

ch=getchar(); }

return root; }

int depth(bitree *t){ int dep1,dep2; if(t==NULL) return 0; else{

dep1=depth(t->lchild); dep2=depth(t->rchild); if(dep1>dep2) return (dep1+1); else return(dep2+1); } } main(){ bitree *root;

. . word.zl-

. -

root=Creatree();

printf(\"depth is %d\\n\}

四、实验结果与分析〔程序运行结果及其分析〕 1.

2.

3.

4.

五、实验体会〔遇到问题及解决方法，编程后的心得体会〕

遇到问题：这章从一开场编写成功后运行就一直不顺利，理论上程序时正确的，但是输入运行处的结果却总是错误一大堆。在询问教师后，经过运行及测试，

. . word.zl-

. -

才明白我是对ch=getchar();这个函数的理解错误，在这个函数中，空格也算作一个字符，所以当我输入的时候，每一个字符中间空一个，输入五个对于程序我相当于输入了十个字符。

实验体会：这次的实验让我明白了根底理论知识的重要性，没有坚实的根底知识，在这种问题上，即使编写出来了，检查错误调试就要花许多时间。并且我也学会了二叉树的输入赋值以及它的各种计算。

. . word.zl-

. -

实验工程名称： 图 实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

. . word.zl-

. -

实验6 图

一、实验目的和要求

〔1〕熟练掌握图的根本概念、构造及其存储构造。

〔2〕熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。

二、实验仪器和设备

Visual C++6.0

三、实验容与过程〔含程序清单及流程图〕

1、必做题

〔1〕构造一个无向图〔用邻接矩阵表示存储构造〕。

〔2〕对上面所构造的无向图，进展深度优先遍历和广度优先遍历，输出遍历序列。 2、选做题

采用邻接表存储构造，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。简单路径是指其顶点序列中不含有重复顶点的路径。提示：两个顶点及k值均作为参数给出。 程序清单： 〔1〕

#include #include typedef int datatype; #define maxsize 1024

. . word.zl-

. -

#define n 100 typedef char VEXTYPE; typedef int ADJTYPE; typedef struct { VEXTYPE vexs[n] ; ADJTYPE arcs[n][n] ; int num ; }GRAPH;

void GraphInit(GRAPH *L) {

L->num=0; }

int GraphVexs(GRAPH *L) {

return(L->num); }

. . word.zl-

. -

void GraphCreate(GRAPH *L) { int i,j; GraphInit(L);

printf(\"请输入顶点数目：\\n\"); scanf(\"%d\

printf(\"请输入各顶点的信息：\\n\"); for(i=0;inum;i++) {

fflush(stdin);

scanf(\"%c\ }

printf(\"请输入边权矩阵的信息：\\n\"); for(i=0;inum;i++) {

for(j=0;jnum;j++) {

scanf(\"%d\ } }

printf(\"图已经创立完毕！\"); }

. . word.zl-

. -

void GraphOut(GRAPH L) { int i,j;

printf(\"\\n图的顶点数目为：%d\ printf(\"\\n图的各顶点的信息为：\\n\"); for(i=0;iprintf(\"\\n图的边权矩阵的信息为：\\n\"); printf(\"\\n\"); for(i=0;ifor(j=0;jprintf(\"%6d\ }

printf(\"\\n\"); }

printf(\"图已经输出完毕！\"); }

. . word.zl-

. -

void main() {

GRAPH tu; GraphCreate(&tu); GraphOut(tu); system(\"pause\"); } (2)

#include #include typedef int datatype; #define maxsize 1024 #define n 100 typedef char VEXTYPE; typedef int ADJTYPE; typedef struct { VEXTYPE vexs[n] ; ADJTYPE arcs[n][n] ; int num ; }GRAPH;

. . word.zl-

. -

void GraphInit(GRAPH *L) {

L->num=0; }

int GraphVexs(GRAPH *L) {

return(L->num); }

void GraphCreate(GRAPH *L) { int i,j; GraphInit(L);

printf(\"请输入顶点数目：\\n\"); scanf(\"%d\

printf(\"请输入各顶点的信息：\\n\"); for(i=0;inum;i++) {

fflush(stdin);

. . word.zl-

. -

scanf(\"%c\ }

printf(\"请输入边权矩阵的信息：\\n\"); for(i=0;inum;i++) {

for(j=0;jnum;j++) {

scanf(\"%d\ } }

printf(\"图已经创立完毕！\"); }

void GraphOut(GRAPH L) { int i,j;

printf(\"\\n图的顶点数目为：%d\ printf(\"\\n图的各顶点的信息为：\\n\"); for(i=0;iprintf(\"\\n图的边权矩阵的信息为：\\n\"); printf(\"\\n\");

. . word.zl-

. -

for(i=0;ifor(j=0;jprintf(\"%6d\ }

printf(\"\\n\"); }

printf(\"图已经输出完毕！\"); }

void DFS(GRAPH g,int qidian,int mark[]) { int v1; mark[qidian]=1;

printf(\"%6c\ for(v1=0;v1if(g.arcs[qidian][v1]!=0&&mark[v1]==0) DFS(g,v1,mark); } }

. . word.zl-

. -

void GraphDFS(GRAPH g) {

int qidian,v,v1,mark[maxsize]; printf(\"\\n深度优先遍历：\"); printf(\"\\n请输入起点的下标：\"); scanf(\"%d\ for(v=0;vmark[v]=0; }

for(v=qidian;vv1=v%g.num; if(mark[v1]==0) DFS(g,v1,mark); } }

typedef int DATATYPE; typedef struct {

DATATYPE data[maxsize]; int front,rear;

. . word.zl-

. -

} SEQQUEUE;

void QueueInit(SEQQUEUE *sq) {

sq->front=0; sq->rear=0; }

int QueueIsEmpty(SEQQUEUE sq) {

if (sq.rear==sq.front) return(1); else return(0); }

int QueueFront(SEQQUEUE sq,DATATYPE *e) {

if (QueueIsEmpty(sq))

{ printf(\"queue is empty!\\n\");return 0;} else

{ *e=sq.data[(sq.front)]; return 1;} }

int QueueIn (SEQQUEUE *sq,DATATYPE x) {

. . word.zl-

. -

if (sq->front==(sq->rear+1)%maxsize) {

printf(\"queue is full!\\n\"); return 0; } else {

sq->data[sq->rear]=x;

sq->rear=(sq->rear+1)%maxsize; return(1); } }

int QueueOut(SEQQUEUE *sq) {

if (QueueIsEmpty(*sq)) {

printf(\"queue is empty!\\n\"); return 0; } else {

sq->front=(sq->front+1)%maxsize;

. . word.zl-

. -

return 1; } }

void BFS(GRAPH g,int v,int mark[]) { int v1,v2; SEQQUEUE q; QueueInit(&q); QueueIn(&q,v); mark[v]=1;

printf(\"%6c\ while(QueueIsEmpty(q)==0) {

QueueFront(q,&v1); QueueOut(&q); for(v2=0;v2if(g.arcs[v1][v2]!=0&&mark[v2]==0) {

QueueIn(&q,v2); mark[v2]=1;

printf(\"%6c\

. . word.zl-

. -

} } } }

void GraphBFS(GRAPH g) {

int qidian,v,v1,mark[maxsize]; printf(\"\\n广度优先遍历：\"); printf(\"\\n请输入起点的下标：\"); scanf(\"%d\ for(v=0;vmark[v]=0; }

for(v=qidian;vv1=v%g.num; if(mark[v1]==0) BFS(g,v1,mark); } }

. . word.zl-

. -

void main() {

GRAPH tu; GraphCreate(&tu); GraphOut(tu); GraphDFS(tu); GraphBFS(tu); system(\"pause\"); }

四、实验结果与分析〔程序运行结果及其分析〕 1.

. . word.zl-

. -

2.

. . word.zl-

. -

五、实验体会〔遇到问题及解决方法，编程后的心得体会〕

遇到问题：这一章编写的极其的不顺利，首先在理论上我认为是正确的程序在运行时却一次次的出现error和warning，让我这章容进展了两次课时。耽误了下一章的编写。首先是在文档中编写时，首字母自动大写而没有发现，其次是有clrscr()这个函数但是头文件却忘记写了，然后教师批评最严重的一个问题是没有标志语言，这章图的编写即使输入进去也不会显示出来，因此应该添加标志语言。

实验体会：在编写时需要认真对待，认真检查C语言语法以及在编写时有可能忘记的容。最重要的是在一些程序中，需要添加标志语言，不能因为完成了就是完成了，需要简明易懂给人提示。

. . word.zl-

. -

实验工程名称： 排序 实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

. . word.zl-

. -

实验7 排序

一、实验目的和要求

〔1〕熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的根本概念。

〔2〕掌握以上各种排序的算法。区分以上不同排序的优、缺点。

二、实验仪器和设备

Visual C++6.0

三、实验容与过程〔含程序清单及流程图〕

1、必做题

用随机数产生100000个待排序数据元素的关键字值。测试以下各排序函数的机器实际执行时间〔至少测试两个〕：直接插入排序、希尔排序〔增量为4，2，1〕、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序和基于链式队列的基数排序。 2、选做题

假设含n个记录的序列中，其所有关键字为值介于v和w之间的整数，且其中很多关键字的值是一样的。那么可按如下方法排序：另设数组number[v…w]，令number[i]统计关键字为整数i的纪录个数，然后按number重排序列以到达有序。试编写算法实现上述排序方法，并讨论此种方法的优缺点。 程序清单：

〔1〕

. . word.zl-

. -

#include #include #include #define N 1000 void Creatstring(int a[]) { int i; int rand(void); srand(time(NULL)); for(i=0;ivoid Outputstring(int a[]) { int i;

for(i=0;iprintf(\"%4d\

if((i+1)%20==0) printf(\"\\n\"); } }

. . word.zl-

. -

void Sortstring(int a[])//直接选择排序 {

int i,j,temp; int k;

for(i=0;ifor(j=i+1;jif(a[j]} if(i!=k) {

temp=a[i];

a[i]=a[k]; a[k]=temp;

}

. . word.zl-

. -

} } int main() { int a[N]; Creatstring(a); printf(\"排序前:\\n\"); Outputstring(a); printf(\"\\n\"); printf(\"排序后:\\n\"); Sortstring(a); Outputstring(a); return 0; }

(2)

#include #include #include #define N 1000 void Creatstring(int a[]) {

. . word.zl-

. -

int i; int rand(void); srand(time(NULL)); for(i=0;ivoid Outputstring(int a[]) { int i;

for(i=0;iprintf(\"%4d\

if((i+1)%20==0) printf(\"\\n\"); } }

void Sortstring(int a[])//冒泡 { int i,j,t,flag; for(i=0;iflag=1;

. . word.zl-

. -

for(j=N-1;j>i;j--) if(a[j-1]>a[j]) { t=a[j-1]; a[j-1]=a[j]; a[j]=t;

flag=0;

} if(flag) break;

}

}

int main() { int a[N]; Creatstring(a); printf(\"排序前:\\n\"); Outputstring(a); printf(\"\\n\"); printf(\"排序后:\\n\"); Sortstring(a); Outputstring(a);

. . word.zl-

. -

return 0; }

四、实验结果与分析〔程序运行结果及其分析〕 1

2

. . word.zl-

. -

五、实验体会〔遇到问题及解决方法，编程后的心得体会〕

实验体会：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序和基于链式队列的基数排序。这几种排序各有优缺点，但是总是将这几个弄混，在看书后得以解决。在这几种排序中：假设只从存储空间考虑，那么应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法； 假设只从排序结果的稳定性考虑，那么应选取归并排序方法；假设只从平均情况下最快考虑，那么应选取快速排序方法；假设只从最坏情况下最快并且要节省存考虑，那么应选取堆排序方法。

. . word.zl-

. -

. . word.zl-

. -

实验工程名称： 查找 实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

. . word.zl-

. -

实验8 查找

一、实验目的和要求

〔1〕掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。 〔2〕掌握哈希表设计。

二、实验仪器和设备

Visual C++6.0

三、实验容与过程〔含程序清单及流程图〕

1、必做题

（1） 在一个递增有序的线性表中利用二分查找法查找数据元素X。 注：查找X的过程 〔2〕分块查找 2、选做题

（3） 构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用

链地址法。设计一个测试程序进展测试。

提示：构造哈希表只是完成查找的第一步，大家应该掌握在哈希表上进展查找的过程，可以试着编程序实现。 程序清单：

. . word.zl-

. -

四、实验结果与分析〔程序运行结果及其分析〕

五、实验体会〔遇到问题及解决方法，编程后的心得体会〕

. . word.zl-