10 《数据结构与算法》课间实习指导书.pptx

第1页：数据结构与算法实验指导书

数据结构与算法实验指导书

第2页：前言

前言地理信息系统(GeographicInformationSystem,GIS)专业的主要工作是利用计算机技术手段有效管理各类空间信息，并为各种与地学分布有关的研究领域提供决策服务。《数据结构》课程是地理信息系统专业一门重要的专业基础课程，主要涉及数据的表示与数据处理。通过本课程的教学，学生应该掌握算法分析、算法设计和为计算机加工处理的数据设计逻辑结构的基本方法和理论；学会分析研究数据结构的特性，以便为地理信息系统研究与应用领域所涉及的数据选择适当的逻辑结构，为GIS程序设计、二次开发打下扎实的基础。实验实习是理论教学向实践性转化的重要手段，通过实验可以使学生对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。根据本课程内容，结合GIS专业特点，同时从学时数的角度来考虑，我们选择了四个课内实验实习：线性表的插入和删除算法实现；栈和队列的插入和删除算法实现；二叉树的操作算法的实现；最短路径算法的实现。同时选择了两个可选实验：排序、查找。为了提高学生自学编程的积极性，本指导书还选择了八个课外上机实验源程序，有时间或感兴趣的同学可以利用课外时间上机编程实现。本实验指导书的以程序或子程序的形式给出，编程语言为C或VC++，上机时同学们可以根据实际情况选择相应的语言加以调试实现，为了帮助同学们理解，本指导书同时给出了（子）程序实现思路或算法。本书给出的程序均为可运行程序的子程序，或可运行程序，同学们根据自己的理解增加主程序、头文件定义就可调用相应的子程序。最好在阅读本实验指导书源程序的基础上进行扩充，以便在更复杂数据元素的情况下，实现相应的数据结构与算法。由于时间仓促，错误难免。希望同学们在学习过程中加以指正。

第3页：目录

目录第一部分：课内实验内容实验一线性表的插入和删除算法实………………………………………………………………1实验二栈和队列的插入和删除算法实现…………………………………………………………9实验三二叉树的操作算法的实现………………………………………………………………17实验四最短路径算法的实现……………………………………………………………………29实验五排序………………………………………………………………………………………40实验六查找………………………………………………………………………………………42第二部分：课外上机实验源程序1、基本排序………………………………………………………………………………………452、基数排序………………………………………………………………………………………513、顺序查找………………………………………………………………………………………554、折半查找………………………………………………………………………………………575、二叉树的操作…………………………………………………………………………………586、二叉排序树上的查找…………………………………………………………………………627、以字符串为数据的单链表操作………………………………………………………………658、邻接表表示的图的深度优先搜索和广度优先搜索程序……………………………………67第三部分：实验步骤、实验报告规范………………………………………………………………………………………………………71课内实验主程序………………………………………………………………………………………………………73

第4页：

第5页：实验一线性表的插入和删除

第一部分：课内实验内容实验一线性表的插入和删除算法实现一、实验目的掌握用VC或TurboC上机调试线性表的基本方法；掌握线性表的基本操作，以顺序表示、链式表示两种存储方式实现线性表的建立、插入、删除等算法；了解线性表的查找、合并算法的实现。二、实验内容熟悉在VC或TurboC环境下的编程与调式程序的方法；在线性表的顺序表示和链式表示两种方式中选择一种存储方式，实现线性表的创建、插入、删除算法；编写主程序、定义相应的变量，上机调式实现本次实验内容。三、提交成果实习报告与可运行的源程序。四、算法子程序(一)线性表的顺序表示时基本操作实现——静态数组一)基本思想线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构如图1-1所示，其特点是：1

• 第i个元素ai的存储位置可以用公式计LOC(ai)=LOC(a1)+(i-1)*L其中LOC(a1)第一个元素a1的存储位置，L素需占的存储单元2.表中相邻的元素ai和ai+1赋以相邻的存LOC(ai)和LOC(ai+1)3.是一种随机存储结构：只要知道线性表的置就可随机存取线性表中的任一元素。每个元储位置起始位图1-1线性表的顺序存储结构示意图二）线性表的插入与删除操作思路当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。它们的操作过程如图1-2所示。1

第6页：实验一内容与参数定义

在线性表上的第i个位置插入一个元素e删除线性表上第i个元素并赋给e图1-2线性表的插入与删除操作示意图三）算法实现1.参数定义2Null0; intdatatype; typedeftypedef#definemaxsize1024; 2.结构定义typedefstruct{ datatypedata[maxsize]; intlast; } sequenlist; 3.子程序intinsert(L,x,i)sequenlistinti; { intj; *L; if((*L).last==maxsize-1){ printf(“overflow”); returnNull; } else

第7页：顺序表插入算法实现

3if((i<1)‖(i>(*L).last+1){ printf(“error”); returnNull; } else{ for(j=(*L).last; j>=i-1; j--)(*L).data[j+1]=(*L).data[j]; (*L).data[i-1]=x; (*L).last=(*L).last+1; } return(1); } intdelete(L,i)sequenlist*L; inti; { intj; if((i<1)‖(i>(*L).last+1)){ printf(“error”); returnNull; } else{ for(j=i,j<=(*L).last; j++)(*L).data[j-1]=(*L).data[j]; (*L).data--; } return(1); } voidcreatlist(){ sequenlist*L; intn,i,j; printf(“请输入n个数据\n”); scanf(“%d”,&n); for(i=0; i<n; i++){

第8页：顺序表建立与输出

printf(“data[%d]=”,i);scanf(“%d”,(*L).data[i]);}(*L).last=n-1;printf(“\n”);}printout(L)sequenlist*L;{inti;for(i=0;i<(*L).last;i++){printf(“data[%d]=”,i);printf(“%d”,(*L).data[i]);}}（二）线性表的链式表示时基本操作实现——链表一）基本思想线性表的链式表示是利用一组任意的存储单元存储线性表的元素。其特点是：1、存储单元除包含数据元素本身外，还包含指向前驱结点或后继结点的指针；2、链式存储单元也叫结点，包含数据域、指针域；3、逻辑上相邻、物理位置不一定相邻，因此不能随机存取；4、三种形式：线性链表、循环链表、双向链表。二）线性表的链表示的三种形式1

• 线性链表结点：包含数据域和后继指针域，如图1-3所示。图1-3结点结构图线性链表的n个结点(ai(1≤i≤n)的存储映象)链接成一个链表；每个结点只包含一个后继指针，又称线性链表或单链表。设有线性表:（a1,a2,…,ai,…,an），则可用图1-4表示。图1-4带头结点的单链表4

第9页：线性链表的特征

线性链表的特征：单链表任意两个元素的存储位置没有固定的关系；但每个元素的位置都包含在其直接前驱结点的信息之中；若p->data=ai，则p->next->data=ai+1。查找第i个元素必须从头指针开始。2.循环链表循环链表如图1-5所示，它是另一种形式的链式存储结构。结点也包含数据域和后继指针域。它的特点是：1最后一个结点的指针指向头结点，整个链形成一个环2可以从任何一个结点出发找到其他点3头指针作为循环判断条件4两个线性表合并时，一个表的表尾和另一个表的表头连接图1-5循环链表3

• 双向链表双向链表如图1-6所示，它的结点有两个指针域：一个指向直接后继，另一个指向直接前驱。目的是克服单链表的单向寻查的缺点。图1-6双向链表表示三）线性表的插入与删除操作思路插入元素：当插入数据元素时，首先生成一个结点，结点的数据域为插入的元素；然后找到元素的插入位置；最后修改指针域。例如，图1-7中，在p结点后插入新生成结点s，则修改指针的语句为：s->data=e;s->next=p->next;p->next=s;图1-7单链表插入结点指针表化情况5

第10页：单链表删除结点

删除元素：当删除数据元素时，仅修改待删除结点的前一个结点的指针。例如，图1-8中，待删除的结点为q，q的前一个结点为p，删除后结点q的数据赋给e，则修改指针的语句为：q=p->next; p->next=q->next; e=q->data; free(q); 图1-8单链表删除结点指针表化情况四）算法实现本子程序为线性链表的插入和删除算法。1 参数与结点定义#defineNULL0struct node//定义节点{ intdata;//链接指针域} ; node *head,*p,*q,*nw;子程序voiddisp(){ if(head==NULL){return; } inti=1; p=head;printf("\n(%d)=%3d",i,p->data);//指向下一个节点i++;while(p!=NULL);} 6

第11页：单链表插入结点算法

7voidaddnode(){ inta,b; printf ("请输入插入位置的原数据a="); scanf("%d",&a); printf("\n"); printf ("请输入插入的新数据b="); scanf("%d",&b); printf("\n"); nw=(node*)malloc(sizeof(node));//将插入数据填入新节点if(head==NULL){nw->next=NULL; } else{ if (head->data==a){head=nw; } else{ if(head->next==NULL){nw->next=NULL; } else{ p=head; do{p=p->next; } while(p->data!=a&&p->next!=NULL); if (p->data==a){nw->next=p; } else{nw->next=NULL; }

第12页：单链表删除结点算法

8} } } disp();voiddelnode(){ if(head==NULL){ printf("\n空表!\n"); return; } inta; printf ("请输入待删除的数据a="); scanf("%d",&a); printf("\n"); if (head->data==a){head=p->next; free (p);else{ p=head; do{p=p->next; } while(p->data!=a&&p->next!=NULL); if (p->data==a){free (p);else{ printf ("\n找不到待删除的数据!\n"); return; } } disp(); 
第13页：实验二栈和队列的插入和删除
实验二栈和队列的插入和删除算法实现一、实验目的掌握用VC或TurboC上机调试栈和队列的基本方法；掌握栈和队列基本操作；掌握队列的链式、循环表示算法程序实现二、实验内容栈和队列基本操作的实现；上机调式本次实习内容。三、提交成果实习报告与可运行的源程序。四、算法子程序（一）栈的线性链表的压入和弹出算法实现一）栈的基本概念栈(Stack)是限定仅在表尾进行插入和删除操作的线性表，如铁路调度。如图2-1所示。表尾端称为栈顶(Top)，表头端称为栈底(bottom)。设栈S=(a1,a2, …, an),则a1为栈底元素，an为栈顶元素。进栈次序是a1,a2, …,an；出栈次序是an,an-1, …,a1。栈又称后进先出(LastIn First Out)线性表。基本操作：插入、删除、初始化、判空、取栈顶元素。二）栈的的表现形式图2-1栈的示意图栈有两种表示形式：栈的表示和实现、栈的链式表示。1
栈的表示和实现利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。如图2-2所示。图2-2栈顶指针和栈中元素之间的关系同时设置栈顶指针(top)和栈底指针(base)。当top=base表示栈空；增加一个元素，top增加1；删除栈顶元素，top减1。非空栈顶指针始终在始终在栈顶元素的下一个位置。2
栈的链式表示9
第14页：栈的链式表示与压入弹出
当栈的长度无法估计时最好用栈的链式表示，如图2-3所示。结点包含数据元素和指针两个数据域。三）栈的链式表示时元素压入、弹出算法实现思路1.栈的线性链表的压入算法如图2-4所示，压入算法过程为：定义新的结点p、修改新结点的指针（指向原栈顶结点top）、给新结点p赋值为x、修改新栈顶的指针（指向新结点p）。2.栈的线性链表的弹出算法图2-3链栈示意图如图2-4所示，弹出算法过程为：将栈顶结点top赋给p、取结点p的值并赋给x、调整栈顶位置（指向结点p的下一个结点）、释放结点p的空间。图2-4链栈压入与弹出元素示意图四）算法的实现1.定义参数与结点#defineNULL0structnode//定义节点{ intdata;//链接指针域} ; node*p;//指向堆栈栈顶的指针2.子程序voiddisp(){ if(top==NULL){return; 栈底栈顶栈顶toptop压入栈底栈顶toptopx弹出10
第15页：链栈显示与压入算法
11} inti=1; p=top; do{//显示一个节点的数据p=p->next;//序号加一} while(p!=NULL);} voidpushnode(intx){ p=(node*)malloc(sizeof(node));//链接//赋值//新的栈顶p->data=x; top=p; disp(); } intpopnode(){ intx; p=top;//取值top=p->next;disp(); returnx;（二）循环队列的算法程序实现一）队列的基本概念和栈相反，队列(Queue)是一种先进先出（FirstInFirstOut）的线性表，如图2-5所示。只允许在表的一端进行插入，而在另一端删除元素，如日常生活中的排队现象。队列中允许插入的一端叫队尾(rear)，允许删除的一端称队头(front)。假设队列为q=(a1,a2,…,an)，则a1为队头元素，an为队尾元素。队列中出队的顺序和进队顺序一致。队列的基本操作与栈类似，包括：初始化、清空、销毁、求长度、得到对头元素、插入、删除。
第16页：队列的链式表示
A1A2A3…..An出队列入队列队头队尾图2-5队列示意图二）队列的表示形式队列的表示形式有两种：队列的链式表示、队列的顺序表示。1
队列的链式表示用链表来表示的队列，简称链队列，如图2-6所示。在这种表示形式中，需要两个分别指向队头（front或head）和队尾(rearh或end)的指针。与线性表的单链表类似，需要设置头结点。队列为空的条件是队头指针和队尾指针均指向头结点。实际上链队列的操作为单链表的插入和删除操作的特殊情况。链队列插入与删除元素时的指针变化情况如图2-7。图2-6链队列示意图图2-7链队列插入与删除元素时指针变化示意图2
队列的顺序表示如图2-8所示，队列的顺序表示用一组地址连续的存储单元依次存放从队头（front）到队尾（rear）的元素。此外，还需要设置两个指针分别指向队头元素和队尾元素。初始化时Q.front= Q.rear = 0，插入元素时尾指针加1，删除元素时，头指针增加1。图2-8队列的顺序表示12
第17页：循环队列的判空判满
为保证插入新元素时不会使数组越界，并充分利用队头删除元素后的空间，可设计一个环行空间，构成循环队列，如图2-9所示。但是，凭Q.front=Q.rear无法判断队列是满还是空。处理方法有两种：一是设标志，二是少用一个元素空间。特点是无法用动态分配的一维数组实现循环队列图2-9循环队及其头尾指针示意图三）循环队列入队、出队实现思路1.循环队列入队算法入队算法过程为：判断队列是否已满？如果已满则退出；否则，队尾指针加1，并在队尾插入新的元素。2.循环队列出队算法出队算法过程为：判断队列是否为空？如果为空则退出；否则，队头指针加1，并删除队头元素。四）算法实现1.参数定义13#definem12intv[m+1]; intf,r;inti=0,j=f; if(r==f){ printf ("队列已空!\n"); return;
第18页：循环队列显示与入队
14} printf ("序号位置do{ 数值\n"); i++; j++; if(j==m+1)j=0;%2dprintf("%2d//到队尾结束} while(j!=r); printf("\n"); return; } voidaddqulink(){ if((r+1)==f||(r-m)==f){ printf("队列已满!\n"); return; } r++; if(r==m+1)r=0; printf ("请输入新入队数据ax="); scanf("%d",&v[r]);disp();intoutqulink(){ if(r==f){ printf("队列已空!\n"); return0; } f++; if(f==m+1)f=0; disp();returnv[f]; } （三）链式队列的算法程序实现一）链式队列入队、出队实现思路1 链式队列入队算法入队算法过程为：申请一个新结点nw，给新结点赋值；判断队列是否为空？如果为空，则队头（或队首）(head)、队尾(end)均指向新结点new；否则，新结点加到队尾。2 链式队列出队算法
第19页：链队列出队思路与参数定义
15出队算法过程为：判断队头是否为空？如果不为空，则队头结点赋给p，取队头元素给x，修改队头指针，释放结点p；如果为空，则退出。二）算法实现1 参数定义#defineNULL0struct node//定义节点{ intdata;//链接指针域} ; node *head,*end,*p,*nw;inti=1; if(head==NULL){return; } p=head;printf("\n(%d)=%3d",i,p->data);//指向下一个节点i++;while(p!=NULL);} intaddqulink(intn){ nw=(node*)malloc(sizeof(node));scanf("%d",&nw->data);nw->next=NULL;//对于空队,以新节点作队头队尾else end=end->next=nw;returnn; } 
第20页：链队列出队算法
16intoutqulink(intn){ intx; if(head!=NULL){ p=head; x=head->data;//调整队首free(p);printf("\n出队数据ax=%d\n",x); } if(head==NULL){ printf("\n队列已空!\n"); end=NULL; n=0; } if(head!=NULL)disp();}
第21页：实验三二叉树的操作算法
实验三二叉树的操作算法的实现一、实验目的进一步掌握指针变量、动态变量的含义；掌握二叉树的的概念和结构特征，以及各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算。掌握二叉链表的建立、递规和非递规时二叉树的遍历方法二、实验内容编写二叉链表的建立、递规和非递规时二叉树的先根遍历、中根遍历、后根遍历。已知以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法。三、提交成果实习报告与可运行的源程序。四、算法子程序（一）二叉树的概念一）二叉树的定义和树结构定义类似，二叉树的定义也可以递归形式给出：二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒。因此，二叉树有五种不同的形态，参见图3-1。图3-1二叉树的五种基本形态二）二叉树的存贮结构二叉树的存贮结构分：顺序存贮结构、链式存贮结构。1
顺序存贮结构将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。如图3-2给出了顺序存贮形式。17
第22页：二叉树的顺序与链式存储
图3-2二叉数的顺序存储形式对于一棵二叉树，若采用顺序存贮时，当它为完全二叉树时，比较方便，若为非完全二叉树，将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部只有右分支，设高度为K,则需占用2K-1个存贮单元，而实际只有k个元素,实际只需k个存储单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。2
二叉链表存贮结构（1）二叉链表表示将一个结点分成三部分，一部分存放结点本身信息，另外两部分为指针，分别存放左、右孩子的地址。二叉链表中一个结点可描述为：对于图3-2所示二叉树，用二叉链表形式描述见图3-3。图3-3二叉树的二叉链表示对于一棵二叉树，若采用二叉链表存贮时，当二叉树为非完全二叉树时,比较方便，若为完全二叉树时,将会占用较多存贮单元(存放地址的指针)。若一棵二叉树有n个结点,采用二叉链表作存贮结构时，共有2n个指针域，其中只有n-1个指针指向左右孩子，其余n+1个指针为空，没有发挥作用，被白白浪费掉了(当然后面介绍的线索可利用它)。（2）二叉链表的数据类型18
第23页：二叉链表的数据类型与建立
19二叉链表的数据类型描述如下:structbitree{ elemtype data;} ；//定义左、右孩子为指针型(3)二叉链表的建立为了后面遍历二叉树方便，先介绍建立二叉链表的算法（假设elemtype为char型）。假设二叉链表的数据类型描述如刚才所述，为建立二叉链表，用一个一维表数组来模拟队列，存放输入的结点，但是，输入结点时，必须按完全二叉树形式，才能使结点间满足性质5，若为非完全二叉树，则必须给定一些假想结点(虚结点)，使之符合完全二叉树形式。为此，我们在输入结点值时，存在的结点则输入它对应的字符，不存在的结点(虚结点)，输入逗号，最后以一个特殊符号"#"作为输入的结束,表示建二叉链表已完成。建成的二叉链表可以由根指针root唯一确定。算法描述如下（C++程序）#include<iostream.h>typedefcharelemtype; structbitree{ elemtypedata; bitree*lchild,*rchild; } ; bitree*create(){ bitree*q[100];//二叉链表中的结点bitree *root;//定义队列的头、尾指针char ch;cin>>ch; while(ch!='#')//输入值为#号,算法结束{ s=NULL; if(ch!=',')//输入数据不为逗号,表示不为虚结点,否则为虚结点{ s=newbitree; s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; q[rear]=s; 
第24页：二叉链表建立算法
else{if((s!=NULL)&&(q[front]!=NULL)){if(rear%2==0)q[front]->lchild=s;//rear为偶数,s为双亲左孩子elseq[front]->rchild=s;} 
第25页：二叉树的遍历规则
21所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。通常有DLR、LDR、LRD三种遍历规则。DLR称为前根遍历(或前序遍历、先序遍历、先根遍历)，LDR称为中根遍历(或中序遍历)，LRD称为后根遍历(或后序遍历)。一）前根遍历所谓前根遍历，就是根结点最先遍历，其次左子树，最后右子树。1
递归遍历前根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则1输出根结点；2前根遍历左子树;3前根遍历右子树;算法如下:voidpreorder(bitree*root){bitree*p;p=root;if(p!=NULL){cout<<p->data<<"";preorder(p->lchild);preorder(p->rchild);}}2
非递归遍历利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右孩子。如此重复，直到栈为空或指针为空止。算法如下：voidpreorder1(bitree*root){bitree*p,*s[100];int top=0; 
第26页：中根遍历递归算法
22}p=s[top--];p=p->rchild;}}二）中根遍历所谓中根遍历，就是根在中间，先左子树，然后根结点，最后右子树。1
递归遍历中根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束；否则⑴中根遍历左子树;⑵输出根结点;⑶中根遍历右子树。算法如下:voidinorder(biteee*root){bitree*p;p=root;if(p!=NULL){norder(p->lchild);cout<<p->data<<"";inorder(p->rchild);}}2
非递归遍历同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。算法如下:voidinorder1(bitree*root){bitree*p,*s[100];//s为一个栈inttop=0;p=root;while((p!=NULL)||(top>0)){
第27页：中根遍历非递归算法
23while(p!=NULL){s[++top]=p;p=p->lchild;}p=s[top--];cout<<p->data<<"";p=p->rchild;}}三）后根遍历所谓后根遍历，就是根在最后，即先左子树，然后右子树，最后根结点。1
递归遍历后根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则1后根遍历左子树:2后根遍历历子树;3访问根结点。算法如下:voidpostorder(bitree*root){bitree*p;p=root;if(p!=NULL){postorder(p->lchild);postorder(p->rchild);cout<<p->data<<"";}}2
非递归遍历利用栈来实现二叉树的后序遍历要比前序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树,所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，一个元素第一次进栈标志为0，第二次进标志为1，并将标志存入另一个栈中，当从标志栈中退出的元素为1时，访问结点。
第28页：后根遍历非递归算法
24算法如下：voidpostorder1(bitree*root){bitree*p,*s1[100];ints2[100],top=0,b;p=root;//s1栈存放结点,s2栈存放进栈标志do{while(p!=NULL){s1[top]=p;s2[top++]=0;//第一次进栈标志为0p=p->lchild;}if(top>0){b=s2[--top];p=s1[top];if(b==0){s1[top]=p;s2[top++]=1;//第二次进栈标志为1p=p->rchild;}else{cout<<p->data;p=NULL;}}}while(top>0);}（三）遍历算法应用举例一）例1由二叉树的前序序列和中序序列建立该二叉树分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：1.用前序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列;4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，则得到的二叉树如下页所示：
第29页：遍历示例说明
（1）A为根结点ABDGHCEFIGDHBAECIF（2）B为左子树的根结点BDGHGDHB（3）D为左子树的左子树的根结点（4）C为右子树的根结点CEFIECIF25
第30页：按层次遍历二叉树
（5）F为右子树的右子树的根结点二）例2按层次遍历一棵二叉树对于一棵二叉树，若规定遍历顺序为从上到下(上层遍历完才进入下层)，从左到右(同一层从左到右进行，这样的遍历称为按层次遍历：例1的树的层次遍历序列为：ABCDEFGHI。下面用一个一维数组来模拟队列，实现二叉树的层次遍历。Voidlorder(bitree*t){bitree*q[maxsize],*p; 
第31页：二叉树实验参数与结构定义
27算法程序实现：1 参数与结构定义M100Null0structnode#define#definetypedef{ intdata; structnode*lchild,*rchild; } bitree; bitree*que[M]; intfront=0,rear=0; 2 子程序bitree*creat(){ bitree*t; intx; scanf(“%d”,&x); if(x==0)else{ t=Null; t=malloc(sizeof(bitree)); t→data=x; t→lchild=creat(); t→rchild=creat(); } returnt; } voidinorder(t)bitree*t; { if(t!=Null){ inorder(t→lchild); printf(“%4d”,t→data); inorder(t→rchild); } } voidenqueue(t)
第32页：队列操作与层次遍历实现
28bitree*t;{if(front!=(rear+1)%M){rear=(rear+1)%M;que[rear]=t;}}bitree*delqueue(){if(front==rear)returnNull;front=(front+1)%M;return(que[front]);}voidlevorder(t)bitree*t;{bitree*p;if(t!=Null){enqueue(t);while(front!=rear){p=delqueue();printf(“%4d”,p→data);if(p→lchild!=Null)enqueue(p→lchild);if(p→rchild!=Null)enqueue(p→rchild);}}}
第33页：实验四最短路径算法
实验四最短路径算法的实现一、实验目的掌握用VC或TurboC上机调试图、最短路径的基本方法；掌握图图的存储、图的遍历、最短路径算法；二、实验内容编写函数分别建立图的邻接矩阵和邻接表，要求直接能从键盘输入图；编写Dijstra、Floyd算法求最短路径算法的函数；编写主函数(使用字符选单形式)，选择其中一项可以运行相应的函数；编写图的DFS和BFS函数；上机调式本次实习内容。三、提交成果实习报告与可运行的源程序。四、算法子程序（一）图的建立、存储和最短路径算法一）图的基本概念图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点的非空有限集、E(G)是边的有限集合，边是顶点的无序对或有序对。有向图——有向图G是由两个集合V(G)和E(G)组成的，其中：V(G)是顶点的非空有限集，E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头。无向图——无向图G是由两个集合V(G)和E(G)组成的，其中：V(G)是顶点的非空有限集，E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v），并且（v,w）=(w,v)。例如，图G1中，V(G1)={1,2,3,4,5,6}；E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}图4-1有向图实例有时，图的边或弧具有与它相关的数，这种与图或弧相关的数叫做权，带权的图又称为网。二）图的存储结构图的存储结构常用的有：数组表示法（邻接矩阵）、邻接表、十字链表、邻接多重表。29
第34页：图的数组表示法
V1V2V3V4V5图4-2无向图实例1
数组表示法（邻接矩阵）用两个数组分别存储图的顶点信息和顶点之间关系的信息。#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20#typedefenum{DE,DN,AG,AN}GraphKind；TypedefstructArcCell{VRTypeadj;//顶点关系类型infoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]TypedefstructVNode{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarc;//邻接矩阵30vexnum,arcnum;kind；//图的种类标志intGraphKind}Mgraph对与无向图，顶点Vi的度是邻接矩阵中第i行或i列非零元素之和。对有向图，第i行元素之和为顶点Vi的出度，第j列元素之和为顶点Vj的入度。图4-2的邻接矩阵如图4-3。0100111001011001101001010图4-3图的邻接矩阵2
邻接表图中每个顶点建立一个单链表，第i个单链表中的结点表示依附顶点Vi的边，每个链表设置一个头结点，头结点以顺序结构存储（有点类似树的孩子表示法）。#defineMAX_VERTEX_NUM20TypedefstructArcNode{itadjvex;//该弧所指向的顶点sructut*nextarc;//下一条弧InfoType*info;//与该弧相关信息
第35页：图的邻接表表示
}ArcNode;Typedefstruct{VertexTypeArcNodedata;//顶点信息*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];图4-2的邻接表如图4-4。V1V2V3V4V5V2V4V1V3V5V1V2V4V3V5V2V4图4-4图的邻接表三）图的建立和存储、和最短路径算法实现思路1.图的建立以屏幕交互方式输入有关数据。先输入顶点数n、边数e；然后依次输入顶点信息、边信息（边信息的结构为：起点，终点，权值）。2
从某个源点到其余各点的最短路径采用迪杰斯特拉(Dijkstra)算法实现，步骤为：(1)求从v点到其余各点vi最短路径长度的初值D[i]，S赋空；D[i] = arcs[LocateVex(G,v)[i] ] |viV(2)选择vj，使得D[j] =Min{D[i]|viV-S}，Vj为当前求得的一条从v出发的最短路径终点，S = S U {j}。(3)修改从v出发到集合V-S上任意一点vk可达到的最短路径长度如果D[j]+arcs[j][k]<D[k]，则D[k] = D[j]+arcs[j][k](4)重复(2)，(3)共n-1次，即可求得v到各点的最短路径。3
每一对顶点之间的最短路径可以每次以一个顶点为源，重复执行迪杰斯特拉算法实现。也可采用弗洛伊德(Floyd)法求Vi到Vj的最短路径，过程为：如果从Vi到Vj存在弧，则arcs[I][j]是从Vi到Vj的路径，但不是最短路径，需要进行n次测试；首先考虑（Vi,V0,Vj）是否存在，如果存在则在(Vi,Vj)和(Vi,V0,Vj)之间中取长度最短的路径为从Vi到Vj的中间顶点不大于0的路径；依次类推。31
第36页：弗洛伊德算法思路
32若(Vi,…,Vk)和(Vk,…Vj)分别为是从Vi到Vk和从Vk到Vj的中间顶点号不大于k-1的最短路径，则将(Vi,…,Vk,…Vj)和已得到的从Vi到Vj且中间顶点序号不大于k-1的最短路径比较，长度最短者便是从Vi到Vj的中间顶点序号不大于k的最短路径经过n次比较后，并可求得从Vi到Vj的最短路径。三）算法实现#defineMAX32767#defineMAXVEX100structvertex{ intnum; char data; } ; typedefstructgraph{ structvertexvexs[MAXVEX]; intedges[MAXVEX][MAXVEX]; } adjmax; intdist[MAXVEX],shortest[MAXVEX][MAXVEX]; adjmaxadj; intn,e; voidcreatgraph(){ inti,j,k,w; charb,t; printf("\n输入顶点数(n):"); scanf("%d",&n); printf("\n输入边数(e):"); scanf("%d",&e); printf("\n++++++输入顶点信息++++++\n"); for(i=1; i<=n; i++){ getchar(); printf("\n输入第%d个顶点的信息:",i); scanf("%c",&adj.vexs[i].data); adj.vexs[i].num=i; }
第37页：图的建立与边信息输入
33for(i=1;i<=n;i++)for(j=1;j<=n;j++)adj.edges[i][j]=MAX;for(i=1;i<=n;i++)adj.edges[i][i]=0;printf("\n++++++输入边信息++++++\n");for(k=1;k<=e;k++){getchar();printf("\n输入第%d条边的信息(起点,终点，权值):",k);scanf("%c,%c,%d",&b,&t,&w);i=1;while(i<=n&&adj.vexs[i].data!=b)i++;if(i>n){printf("输入的起点不存在!\n");}j=1;while(j<=n&&adj.vexs[j].data!=t)j++;if(j>n){printf("输入的终点不存在!\n");}if(i<=n&&j<=n)adj.edges[i][j]=w;elsek--;}}voidprint(){inti,k,j;i=1;while(i<=n){printf("\n第%d个顶点:",adj.vexs[i].num);printf("%c\n",adj.vexs[i].data);i=i+1;}for(k=1;k<=n;k++)for(j=1;j<=n;j++){if(adj.edges[k][j]!=32767)
第38页：弗洛伊德算法实现
34printf("\n起点:%d,终点:%d,权值:%d\n",k,j,adj.edges[k][j]);}}voidshortpath_Floyd(){intpath[MAXVEX][MAXVEX];inti,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++){shortest[i][j]=adj.edges[i][j];path[i][j]=0;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(shortest[i][j]>(shortest[i][k]+shortest[k][j])){shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;}printf("\nFloyd算法运行成功\n");}voidprintpath_Floyd(){inti,j;printf("\n源点到各点之间的最短路径(源点-->其它点):\n");for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i!=j){if(shortest[i][j]!=MAX)printf("%c-->%c:%-5d",adj.vexs[i].data,adj.vexs[j].data,shortest[i][j]);elseprintf("%c-->%c:%s",adj.vexs[i].data,adj.vexs[j].data,"NOWAY");printf("\n");}}
第39页：迪杰斯特拉算法实现
35}}voidshortpath_Dijkstra(intv0){ints[MAXVEX];intmindis,dis,i,j,u;for(i=1;i<=n;i++){dist[i]=MAX;dist[i]=adj.edges[v0][i];s[i]=0;}s[v0]=1;for(i=1;i<=n;i++){mindis=MAX;for(j=1;j<=n;j++)if(s[j]==0&&dist[j]<mindis){u=j;mindis=dist[j];}s[u]=1;for(j=1;j<=n;j++)if(s[j]==0){dis=dist[u]+adj.edges[u][j];dist[j]=(dist[j]<dis)?dist[j]:dis;}}printf("\nDijkstra算法运行成功\n");}voidprintpath_Dijkstra(v0){inti;printf("\n从源点%c到其它各点的最短路径:\n",adj.vexs[v0].data);for(i=1;i<=n;i++){
第40页：图的深度与广度优先搜索
printf("%c-->%c):",adj.vexs[v0].data,adj.vexs[i].data); if(dist[i]==MAX)printf("NOWAY\n"); elseprintf("%-5d\n",dist[i]); } } （二）用邻接矩阵表示的图的深度优先搜索和广度优先搜索一）图的遍历概念图的遍历是从图中某个顶点出发，访遍图中其余结点，且使每个顶点仅被访问一次。图的遍历过程如图4-5所示。（a）无向图；（b）深度优先搜索过程；（c）广度优先搜索过程图4-5遍历图的过程1.深度优先搜索类似树的先根遍历，是树的先根遍历的推广。从图中某个顶点v出发，访问此结点，然后依次从v的未访问的邻结点出发深度优先遍历图，直到和v有路径的相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问过的顶点作起点，重复上述过程，直到图中所有顶点都被访问过为止。例如图4-5（a）图的深度优先搜索的过程为：v1-->v2-->v4-->v8-->v5-->v3-->v6-->v72.广度优先搜索类似树的按层次遍历过程。以v点为起始点，由近至远，依次访问和v有路径相通且路径长度为1，2，…的顶点。例如图4-5（a）图的广度优先搜索的过程为：v1-->v2-->v3-->v4-->v5-->v6-->v7-->v8二）算法实现#definemaxvertexnum100//设置邻接矩阵的最大阶数#definequeuesize100//设置循环队列的最大空间typedefstruct{ intfront,rear,count,data[queuesize]; } cirqueue; 
第41页：图遍历的参数与结构定义
37typedefintvertextype;//设置边上权值为整型typedefstruct{ vertextype vexs[maxvertexnum];//图的邻接矩阵int n,e;mgraph;FALSE,TRUE} boolean; booleanvisited[maxvertexnum];inti,j,k,w; intflag; printf("\ncreat:\n"); printf("digragh--0\n"); printf("undigragh--1\n"); scanf("%d",&flag); printf("inputn,e\n"); scanf("%d%d",&g->n,&g->e);for(i=0; i<g->n; i++)//输入n个顶点的信息scanf("%d",&(g->vexs[i])); for(i=0; i<g->n; i++)//将邻接矩阵数组初始化for(j=0; j<g->n; j++)g->edges[i][j]=0; for(k=0; k<g->e; k++){scanf("%d%d%d",&i,&j,&w); g->edges[i][j]=w; if (flag)//构造无向图g->edges[j][i]=w; } } dfsm(mgraph*g,inti){ intj; printf("visitvertex:%d",g->vexs[i]); 
第42页：深度优先搜索算法
38visited[i]=TRUE;j<g->n; j++)//扫描邻接矩阵的第i行，做以下操作if((g->edges[i][j]!=0)&&(!visited[j]))//寻找序号为i的顶点的未访问过的邻接点(设序号为k),dfsm(g,j);//endofdfsmdfstraverse(mgraph*g){ inti; for(i=0; i<g->n; i++)//将图的所有顶点设置为未访问过visited[i]=FALSE; for(i=0; i<g->n; i++)//对图*g进行深度优先搜索if(!visited[i])dfsm(g,i); printf("\n"); }inti,j; cirqueue*q; q=(cirqueue*)malloc(sizeof(cirqueue));//将循环队列*q设置为空队列printf("visitvertex:%d",g->vexs[k]);//将序号为k是结点设置为已访问过q->data[q->rear]=k; q->rear=(q->rear+1)%queuesize; q->count++;//若队列不为空，则做以下操作i=q->data[q->front]; q->front=(q->front+1)%queuesize; q->count--;j<g->n; j++)//寻找序号为i顶点的邻接点，并做如下处理if((g->edges[i][j]!=0)&&(!visited[j])){//访问序号为j的顶点visited[j]=TRUE;q->rear=(q->rear+1)%queuesize; q->count++;//endofif}//endofbfsm
第43页：广度优先搜索算法
39bfstraverse(mgraph*g){inti;for(i=0;i<g->n;i++)//将所有顶点设置为未访问过visited[i]=FALSE;for(i=0;i<g->n;i++)//对邻接矩阵表示的图进行广度优先搜索if(!visited[i])bfsm(g,i);printf("\n");}//endofbfstraverse
第44页：实验五排序
40实验五排序一、实验目的掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验内容统计成绩三、提交成果本次实习可选实习，时间允许时可以进行实验。四、算法子程序（一）问题描述给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：1按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；2按名次列出每个学生的姓名与分数。（二）基本要求学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。（三）算法实现下面给出的是用直接选择排序算法，实现思路是：通过n-i次关键字间的比较，从n-i-1个记录中选择关键字最小的记录，并和第i（1<=i<=n）个记录进行交换。#definen30typedefstructstudent{ charname[8]; intscore; } studentR[n]; main(){ intnum,i,j,max,temp; printf(“\n请输入学生成绩:\n”); for(i=0; i<n; i++){ printf(“姓名:”);
第45页：成绩统计的输入与排序
41scanf(“%s”,&stu[i].name);scanf(“%4d”,&stu[i].score);}num=1;for(i=0;i<n;i++){max=i;for(j=i+1;j<n;j++)if(R[j].score>R[max].score)max=j;if(max!=i){temp=R[max];R[max]=R[i];R[i]=temp;}if((i>0)&&(R[i].score<R[i-1].score))num=num+1;printf(“%4d%s%4d”,num,R[i].name,R[i].score);}}
第46页：实验六查找
实验六查找一、实验目的掌握查找的不同方法，并能用高级语言实现查找算法；熟练掌握二叉树的构造和查找方法。二、实验内容设计一个读入一串整数构成一棵二叉排序树的算法。三、提交成果本次实习可选实习，时间允许时可以进行实验。四、算法子程序（一）二叉排序树概念或者是一棵空树，或者具有如下性质的二叉树:(1)如果左子树不为空，则左子树上的所有结点的值均小于它的根结点的值；(2)如果右子树不为空，则右子树上的所有结点的值均大于它的根结点的值；(3)它的左右子树均为二叉排序树。如图6-1。图6-1二叉排序树示例（二）二叉排序树的查找过程将给定值与根结点的关键字比较，若相等则查找成功，否则根据给定值和根结点的关键字之间的关系分别在左子树(>根)和右子树(<根)上继续查找。二叉排序树是一种动态树表，是在查找过程中当树种不存在关键字等于给定的结点时在进行插入。实现提示：二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。其构造过程如图6-2所示。42
第47页：二叉排序树构造过程
图6-2二叉排序树的构造过程（三）算法实现：typedefstructnode{ intkey; intother; structnode*lchild,*rchild; } bstnode; voidinorder(t)bstnode*t; { if(t!=Null){ inorder(t→lchild); printf(“%4d”,t→key); inorder(t→rchild); } } bstnode*insertbst(t,s)bstnode*s,*t; { bstnode*f,*p; p=t; while(p!=Null){ f=p; if(s→key==p→key)returnt; 43
第48页：二叉排序树插入与创建
44if(s→key<p→key)p=p→lchild; elsep=p→rchild; } if(t==Null)returns; if(s→key<f→key)f→lchild=s; elsef→rchild=s; returnt; } bstnode*creatord(){ bstnode*t,*s; intkey; t=Null; scanf(“%d”,&key); while(key!=0){ s=malloc(sizeof(bitree)); s→key=key; s→lchild=Null; s→rchild=Null; scanf(“%d”,&data); s→other=data; t=insertbst(t,s); scanf(“%d”,&key); } returnt; } main(){ bstnode*root; root=creatord(); inorder(root); }
第49页：第二部分上机实验源程序清单
45第二部分：附上机实验源程序清单一、基本排序#include<stdio.h>#include<time.h>#include<stdlib.h>#include<dos.h>#definen10000typedefintkeytype; typedefstruct{ keytypekey; } rectype;seqlistr; intm; main()//主程序{ inti,j;printf("2---inscredata\n"); printf("3---descredata\n"); printf("4---inputdata\n"); scanf("%d",&j); if (j==1) randoming();m<=n; m++)r[m].key=m; if (j==3)//产生一组递减序列for(m=1; m<=n; m++)r[m].key=n-m+1; if(j==4){r[0].key=1; m=0; while((m<=n)&&(r[m].key)){
第50页：基本排序程序菜单
46m++;scanf("%d",&(r[m].key));}//endofwhilem--;}//endofifprintf("1-----insertsort\n");printf("2-----bubblesort\n");printf("3-----selectsort\n");printf("4-----quicksort\n");printf("5-----heapsort\n");scanf("%d",&j);//输出排序前的序列printf("thesourcedata:\n");for(i=1;i<=m;i++)printf("%d",r[i].key);printf("\n");//选择一种方法进行排序if (j==1) insertsort(m);//直接插入排序if(j==2)bubblesort(m);//冒泡排序if (j==3) selectsort(m);//直接选择排序if(j==4)quicksort(1,m);//快速排序if(j==5)heapsort(m);//堆排序//以下输出排序结果printf("theanswerdata:\n");for(i=1;i<=m;i++)printf("%d",r[i].key);}//endofmaininsertsort(intm){//直接插入排序inti,j;for(i=2;i<=m;i++)if(r[i].key<r[i-1].key){r[0].key=r[i].key;j=i-1;do{r[j+1].key=r[j].key;j--;
第51页：插入排序与冒泡排序源程序
47}while(r[0].key<r[j].key);r[j+1].key=r[0].key;}//endofif}//endofinsertsortbubblesort(intm){//冒泡排序inti,j;intexchange;for(i=1;i<m;i++){exchange=0;//设置未交换过标记for(j=m-1;j>=1;j--)if(r[j+1].key<r[j].key){//若逆序r[0].key=r[j+1].key;//以r[0]为辅助空间交换r[j+1].key=r[j].key;r[j].key=r[0].key;exchange=1;//设置做过交换标志}//endofifif(!exchange)return;}//endoffor}//endofbubblesortselectsort(intm){//直接选择排序inti,j,k;for(i=1;i<m;i++){k=i;for(j=i+1;j<=m;j++)//在无序区r[j..m]中查找最小关键字位置kif(r[j].key<r[k].key)k=j;if (k!=i){//若k<>i，则交换，扩大有序区r[0].key=r[i].key;r[i].key=r[k].key;r[k].key=r[0].key;}//endofif}//endoffor}//endofselectsortquicksort(intlow,inthigh){//对r[low..high]进行快速排序intpivotpos;if(low<high){
第52页：快速排序源程序
48pivotpos=partition(low,high);//对r[low..high]进行一次快速排序，//以pivotpos为划分点，分成两个无序区r[low..pivotpos-1]和r[pivotpos+1..high]quicksort(low,pivotpos-1);//对r[low..pivotpos-1]进行快速排序quicksort(pivotpos+1,high);//对r[pivotpos+1..high]进行快速排序}//endofif}//endofquicksortintpartition(inti,intj){//一次划分算法rectypepivot;pivot.key=r[i].key;//取支点while(i<j){while((i<j)&&(r[j].key>=pivot.key))j--;//j指针的扫描if(i<j)r[i++].key=r[j].key;while((i<j)&&(r[i].key<=pivot.key))i++;//i指针扫描if(i<j)r[j--]=r[i];}//endofwhiler[i].key=pivot.key;//将支点放入目标位置return i;//返回支点位置}//endofpartitionheapsort(intm){//堆排序inti;buildheap(m);//建大根堆for(i=m;i>1;i--){r[0].key=r[1].key;r[1].key=r[i].key;r[i].key=r[0].key;//将根结点与堆的最后一个结点交换位置heapify(1,i-1);//自根而下调整堆}//endoffor}//endofheapsortheapify(intlow,inthigh){//筛选法调整堆intlarge;rectypetemp;temp.key=r[low].key;for(large=2*low;large<=high;large*=2){if((large<high)&&(r[large].key<r[large+1].key))large++;if(temp.key>=r[large].key)break;
第53页：堆排序与归并源程序
49r[low].key=r[large].key;low=large;}r[low].key=temp.key;}buildheap(m){//建堆inti;for(i=m/2;i>0;i--)heapify(i,m);}merge(intlow,intn1,inthigh){//将两个相邻有序序列合并inti=low,j=n1+1,p=0;rectype *r1;//r1为辅助空间r1=(rectype*)malloc((high-low+1)*sizeof(rectype));if(!r1)error("insufficientmemoryavailable!");while((i<=n1)&&(j<=high))r1[p++].key=(r[i].key<=r[j].key)?r[i++].key:r[j++].key;while(i<=m)r1[p++].key=r[i++].key;while(j<=high)r1[p++].key=r[j++].key;for(p=0,i=low;i<=high;p++,i++)r[i].key=r1[p].key;}mergepass(intlength,intm){//一趟二路归并inti;for(i=1;i+2*length-1<=m;i=i+2*length)merge(i,i+length-1,i+2*length-1);if(i+length-1<m)merge(i,i+length-1,m);}mergesort(m){//二路归并intlength;
第54页：归并排序主过程与错误处理
50for(length=1;length<m;length*=2)mergepass(length,m);}error(char*message){fprintf(stderr,"error:%s\n",message);exit(1);}randoming(){//生成随机序列intn2;randomize();n2=random(10000)+1;m=0;while(n2-->0){m++;r[m].key=random(1000);}}
第55页：基数排序源程序
51二、基数排序#include<stdio.h>#include<stdlib.h>#define radix 10//定义基数#define keysize 4//定义关键字的位数#definenull0#definen100typedef int keytype;keytypekey; } rectype;//定义含n个记录的待排序文件类型typedefstructqueuenode{ intdata; structqueuenode*next; } queuenode;queuenode*front,*rear; } linkqueue;linkqueue b[radix];intj,i;printf("2--inscreedata\n"); printf("3--descreedata\n"); printf("4--inputdata\n"); scanf("%d",&j); if (j==1) randoming();i<n; i++)r[i].key=i+1; 
第56页：基数排序的输入处理
52if(j==3)for(i=0; i<n; i++)r[i].key=n-i;//用户输入生成初始序列printf("inputdata:\n"); for(i=0; i<n; i++)scanf("%d",&r[i].key); }for(i=0; i<n; i++)printf("%d",r[i].key); printf("\n");//打印排序结构printf("resultdata:"); for(i=0; i<n; i++)printf("%d",r[i].key); printf("\n"); } error(char*message){exit(1); } initqueue(linkqueue*q){} intqueueempty(linkqueue*q){} enqueue(linkqueue*q,intx){p->data=x; p->next=null; if(queueempty(q))
第57页：链队列的入队出队操作
53q->front=q->rear=p; else{ q->rear->next=p; q->rear=p; } } intdequeue(linkqueue*q){queuenode*p; if(queueempty(q))error("queueunderflow"); p=q->front; x=p->data; q->front=p->next; if(q->rear==p)q->rear=null; free(p); returnx; } intqueuefront(linkqueue*q){returnq->front->data; } collect(seqlistr,linkqueueb[]){for(j=0; j<radix; j++)while(!queueempty(&b[j]))r[i++].key=dequeue(&b[j]); } distribute(seqlistr,linkqueueb[],intj){j=keysize-j; for(i=0; i<n; i++){
第58页：基数排序的分配与收集
54k=r[i].key;for(t=1;t<j;t++)k=k/10;k=k%10;enqueue(&b[k],r[i].key);}}radixsort(seqlistr){//基数排序inti;for(i=0;i<radix;i++)initqueue(&b[i]);for(i=keysize-1;i>=0;i--){distribute(r,b,i);collect(r,b);}}randoming(){//生成随机数序列inti;for(i=0;i<n;i++)r[i].key=random(10000);}
第59页：顺序查找源程序
55三、顺序查找#include<stdio.h>#include<stdlib.h>#definen100typedefintkeytype; typedefstruct{ keytypekey; } nodetype; typedefnodetypeseqlist[n+1]; seqlistr; main(){ intm,i,j; keytypek; printf("1---randamdata\n"); printf("2---inscreedata\n"); printf("3---descreedata\n"); printf("4---inputdata\n"); scanf("%d",&j); if(j==1)randoming(); if(j==2)for(i=1; i<=n; i++)r[i].key=i; if(j==3)for(i=1; i<=n; i++)r[i].key=n-i+1; if(j==4){ printf("input%nkeys:\n",n); for(i=1; i<=n; i++)scanf("%d",&(r[i].key)); } for(i=1; i<=n; i++)printf("%d--%d",i,r[i].key); printf("\n"); printf("inputk:\n"); scanf("%d",&k); printf("searchpositionis:%d\n",seqsearch(r,k)); } intseqsearch(seqlistr,keytypek){ inti;
第60页：顺序查找算法实现
56r[0].key=k;for(i=n;r[i].key!=k;--i);returni;}randoming(){inti;randomize();i=1;while(i++<=n)r[i].key=random(1000);}
第61页：折半查找源程序
57四、折半查找#include<stdio.h>#definen100typedefintkeytype; typedefstruct{ keytypekey; } nodetype; typedefnodetypeseqlist[n+1]; seqlistr; main(){ intm,i,j; keytypek; for(i=1; i<=n; i++)r[i].key=i;i<=n; i++)//输出查找的序列printf("%d--%d",i,r[i].key); printf("\n"); printf("input k:\n");printf("searchpositionis:%d\n",binsearch(r,k));//endofmainintbinsearch(seqlistr,keytypek){while(low<=high){ mid=(low+high)/2; if(r[mid].key==k)returnmid; if(r[mid].key>k)high=mid-1; elselow=mid+1; } return0; }
第62页：二叉树操作源程序
58五、二叉树的操作#include<stdlib.h>#include<stdio.h>#definequeuesize100#definenull0typedefchardatatype; typedefstructnode{ datatypedata; structnode*lchild,*rchild; } bintnode;//定义二叉链表指针类型typedefstruct{ intfront,rear; bintreedata[queuesize];} cirqueue;//建立二叉树的二叉链表表示，并进行先序遍历、中序遍历、后序遍历和按层次遍历，//求出所有叶子和结点总数。bintreet=null; intn; printf("pleaseinputnodesofbintree:\n"); createbintree(&t);preorder(t);printf("theinorderis:"); inorder(t);postorder(t);leverorder(t);//求出二叉树的叶子数n
第63页：二叉树叶子输出
59printf("\ntheleaveofbintreeis:%d",n);//当叶子数不为0printf("\nthelistofleaveis:"); leavelist(t);elseprintf("\nnoleave!");//输出二叉树的总结点数} createbintree(bintree*t){if((ch=getchar())=='')//如果读入空格字符，创建空树*t=null; else{ *t=(bintnode*)malloc(sizeof(bintnode));//将结点数据ch放入根结点的数据域createbintree(&(*t)->lchild);//建右子树}//endofcreatbintreepreorder(bintreet){printf("%c",t->data); preorder(t->lchild); preorder(t->rchild); }//endofpreorderinorder(bintreet){inorder(t->lchild); printf("%c",t->data); inorder(t->rchild); }//endofinorder
第64页：后根遍历与错误处理
60postorder(bintreet){postorder(t->lchild); postorder(t->rchild); printf("%c",t->data); }//endofpostordererror(char*message){exit(1); } leverorder(bintreet){ cirqueue*q; bintreep; q=(cirqueue*)malloc(sizeof(cirqueue));//将循环队列初始化为空q->data[q->rear]=t; q->count++; q->rear=(q->rear+1)%queuesize;//当队首元素不为空指针，做以下操作p=q->data[q->front];//打印*p结点的数据域信息q->front=(q->front+1)%queuesize; q->count--;else{q->data[q->rear]=p->lchild; q->rear=(q->rear+1)%queuesize; }else{q->data[q->rear]=p->rchild; q->rear=(q->rear+1)%queuesize; }//endofifelse{q->count--; }
第65页：求二叉树叶子总数
61}//求以t为树根的二叉树的叶子总数if (!t)//若根结点为return 0;//返回叶子数1else//根结点的左、右孩子有1个不为空return(leave(t->lchild)+leave(t->rchild));leavelist(bintreet){ if(t){ leavelist(t->lchild);leavelist(t->rchild);//endofif}if (!t)//若二叉树为空树return 0;//二叉树的结点总数为左、右子树的结点总数加上1（根结点）} 
第66页：二叉排序树查找源程序
62六、二叉排序树上的查找#include<stdio.h>#include<stdlib.h>#definenull0#definen100typedefintkeytype; typedefstructnode{ keytype key;} bstnode;//二叉排序树类型定义bstnode*searching(bstreetree,keytypekey){//返回根结点指针if(key<tree->key)//若key大于根结点的关键字的值returnsearching(tree->lchild,key);//在根的右子树中查找}bstreet=null,q=null; keytypek; createbst(&t);inorder(t);printf("inputsearchkey:\n"); scanf("%d",&k);//在二叉排序树t中查找值为k的结点，//返回找到结点的指针，若查找失败返回nullif (q==null)//若返回null，输出查找失败信息printf("search%ddefault!\n",k); else//若q不为空，则输出查找成功的信息printf("search%dsuccess!\n",q->key); } 
第67页：二叉排序树插入算法
63insertbst(bstree*tptr,keytypekey){while(p){//返回f=p;//若key>p->key，//p指向*p的左孩子，否则指向右孩子}//找到插入位置后，申请结点空间*pp->key=key; p->lchild=p->rchild=null;//直接将结点*p作为根结点else//若待插入的二叉排序树非空if(key<f->key)//若key小于f->keyf->lchild=p;//将*p结点作为*f结点的右孩子插入}//创建一棵二叉排序树tkeytypekey; intj,i,m; printf("1--randomdata\n"); printf("2--inscreedata\n"); printf("3--descreedata\n"); printf("4--inputdata\n"); scanf("%d",&j);//随机输入100个以内的数据生成二叉排序树m=random(100); printf("randomsourcedata:"); for(i=1; i<=m; i++){ key=random(100); printf("%d",key); insertbst(t,key);printf("\n"); }
第68页：生成二叉排序树序列
64if(j==2){printf("inscreesourcedata:"); for(i=1; i<=m; i++){ insertbst(t,i); printf("%d",i); } printf("\n"); } if(j==3){printf("inscreesourcedata:"); for(i=1; i<=m; i++){ insertbst(t,m-i+1); printf("%d",m-i+1); } printf("\n"); } if(j==4){scanf("%d",&key); while(key){ insertbst(t,key); scanf("%d",&key); }//endofif}//对二叉排序树t进行中序遍历if(t){ inorder(t->lchild);//访问根结点inorder(t->rchild);//endofif} 
第69页：字符串单链表操作源程序
65七、以字符串为数据的单链表操作#include<stdio.h>#include<string.h>#definenull0typedefstructnode{ char *data;//结点的指针域} linkstrnode;main(){char*t; printf("\npleaseinputthenodeofthelinklist:"); printf("\nnodesdataisstrings,andendof#\n"); creatlinkstr(&head);printing(head);gets(t);//在单链表head中找到并删除值与t相同的结点printf("\nthefinallinklistis:\n"); printing(head);creatlinkstr(linkstringhead){linkstrnode*p; head=(linkstrnode*)malloc(sizeof(linkstrnode));printf("\npleaseinputthenodedata(string),endof#"); gets(t);//当t的值不为“#”时，做以下操作p=head; 
第70页：单链表查找与插入
66p=p->next; if (p->next)//如果存在数据域与t相同的结点，则输出存在信息printf("\nstring%sexisted",t); else{//在单链表表尾申请一个新结点p=p->next;//将t的值复制到*p结点的数据域中p->next=null;printf("\npleaseinputthenodedata(string),endof#"); gets(t);//endofwhile}//输出head单链表linkstrnode*p; p=head->next; while(p){ puts(p->data);} }//若head单链表中有数据为t的结点，删除之linkstrnode*p,*s; p=head; while((p->next)&&(strcmp(p->next->data,t)))//以p为扫描指针对head链表进行查找数据域值为*t结点，//为了能方便删除操作，p指向待查结点的前趋p=p->next; if(p->next){p->next=s->next; free(s); printf("\ndeletesuccessful!"); } else//若head链表中没有数据域的值为*t的结点，则输出删除失败的信息printf("\ndeletefailure!"); }
第71页：第三部分实验步骤与报告规范
67八、邻接表表示的图的深度优先搜索和广度优先搜索程序#include<stdio.h>#definemaxvertexnum100#definequeuesize100#definenull0typedefstruct{ intfront,rear,count,data[queuesize]; } cirqueue;//为了简单，设图中结点的数据为整型typedefstructnode{ int adjvex;//指向下一个边结点} edgenode;vertextype vertex;//指向第一个边结点} vertexnode;//用向量定义图的邻接表表示的顶点表typedefstruct{ adjlistadjlist; int n;//图的边数} algraph;FALSE,TRUE} boolean; booleanvisited[maxvertexnum];//建立图g，并进行深度优先搜索和广度优先搜索algraph*g; g=(algraph*)malloc(sizeof(algraph));//建立图g的邻接表表示printf("thedfsis:"); /dfstraverse(g); 
第72页：实验报告的内容要求
68bfstraverse(g);createalgraph(algraph*g){intflag; edgenode*s; printf("\ncreat:\n")//选择建立有向图或无向图printf("digraph--0\n"); printf("undigraph--1\n"); scanf("%d",&flag); printf("inputn,e\n"); scanf("%d%d",&g->n,&g->e);for(i=0; i<g->n; i++){//输入顶点的数据域（为了简单起见，输入为整数）g->adjlist[i].firstedge=null;//endforfor(k=0; k<g->e; k++){ printf("inputi,j(0~n-1):\n"); scanf("%d%d",&i,&j);//申请一个边结点*ss->adjvex=j;//将边结点*s作为第一个邻接点插入到序号为i的顶点的边表中g->adjlist[i].firstedge=s; if (flag){申请一个边结点*ss->adjvex=i;//将边结点*s作为第一个邻接点插入到序号为j的顶点的边表中g->adjlist[j].firstedge=s; }//endoffor}//对图g进行以序号为i的顶点作为出发点深度优先搜索edgenode*p; printf("visitvertex:%d",g->adjlist[i].vertex); 
第73页：课内实验主程序
69visited[i]=TRUE;//设置寻找序号为i的第一个未访问过邻接点的扫描指针while(p){ if(!visited[p->adjvex])//若*p边结点对应顶点（假设序号为j）未访问过dfs(g,p->adjvex);//p顺着边表next指针，往后继续寻找}//endofdfsdfstraverse(algraph*g){for(i=0; i<g->n; i++)//将图g的所有顶点设置未访问过标记visited[i]=FALSE; for(i=0; i<g->n; i++)//对图g调用dfs函数进行深度优先搜索if(!visited[i])dfs(g,i); printf("\n"); }//对图g进行以序号为k的顶点作为出发点广度优先搜索inti,j; cirqueue *q;q=(cirqueue*)malloc(sizeof(cirqueue));//将循环队列置为空队printf("visitvertex:%d",g->adjlist[k].vertex); visited[k]=TRUE;q->rear=(q->rear+1)%queuesize; q->count++;//当队列非空时做以下操作i=q->data[q->front]; q->front=(q->front+1)%queuesize; q->count--;//设置寻找序号为i顶点的未访问过邻接点的扫描指针pwhile (p){//若*p边结点对应顶点（假设序号为j）未访问过printf("visitvertex:%d",g->adjlist[p->adjvex].vertex);//设置已访问过标记q->data[q->rear]=p->adjvex; q->rear=(q->rear+1)%queuesize; q->count++;//endofif
第74页：线性表链式主程序
70p=p->next;//endofwhile}//endofbfsbfstraverse(algraph*g){for(i=0; i<g->n; i++)//将图g的所有顶点设置未访问过标记visited[i]=FALSE; for(i=0; i<g->n; i++)//对图g调用bfs函数进行广度优先搜索if(!visited[i])bfs(g,i); printf("\n"); }
第75页：栈的主程序
71第三部分：实验步骤、实验报告规范一、实验步骤（一）问题分析和任务的定义明确问题要求做什么，限制做什么（本步强调做什么，而不是怎么做）。对问题的描述应避开算法和所涉及的数据类型，而是所完成的任务做出明确的回答。如输入数据的类型、值的范围以及输入的形式；输出数据的类型、值d的范围及输出的形式；这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。（二）据类型和系统设计在设计这一步骤中分为逻辑设计和详细设计两步实现。逻辑设计指的是，为问题的描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统的功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据的封装，基本操作的规格说明尽可能的明确和具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作的规格说明做出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出函数形式的算法框架。（三）编码实现和静态检查（四）上机准备和上机调试（五）总结和整理实习报告二、报告规范实验题目班级姓名学号（一）需求分析1.程序的功能；2.输入输出的要求；3.测试数据。（二）概要设计1.本程序所用的抽象数据类型的定义；2.主程序的流程及各程序模块之间的层次关系。（三）详细设计1.采用c语言定义相关的数据类型；日期
第76页：循环队列主程序
722.写出各模块的伪码算法；3.画出函数的调用关系图。（四）调试分析1.调试中遇到的问题及对问题的解决方法；2.算法的时间复杂度和空间复杂度。（五）使用说明及测试结果（六）源程序（带注释）
第77页：链队列主程序
73课内实验主程序一、线性表顺序表示主程序（实验一）main(){ sequenlist*L; charcmd; inti,t; clscr(); printf(“i,I…..插入\n”); printf(“d,D…..删除\n”); printf(“q,Q……退出\n”); do{ do{ cmd=getchar(); } while((cmd!=‘d’)‖(cmd!=‘D’) ‖(cmd!=‘q’)‖(cmd!=‘Q’)‖(cmd!=‘i’)‖(cmd!=‘I’)); switch(cmd){ case‘i’,‘I’; scanf(&x); scanf(&i); insert(L,x,i); printout(L); break; case‘d’,‘D’; scanf(&i); delete(L,i); printout(L); break; } } while((cmd!=‘q’)&&(cmd!=‘Q’)); } 二、线性表的链式表示主程序（实验一）#include<stdio.h>#include<stdlib.h>#include<conio.h>voidmain(){
第78页：图的主程序功能选择
74intn,i; charch; head=NULL;printf ("请输入已有节点个数n="); scanf("%d",&n); printf("\n"); if(n>=0)break; printf ("节点个数无效!\n"); } if(n>0){ printf ("请给线性链表各节点赋值\n\n"); for(i=1; i<(n+1); i++){ nw=(node*)malloc(sizeof(node));//对于空表,以新节点作头节点elsep->next=nw;printf("(%d)=",i); scanf("%d",&p->data);p->next=NULL;disp();while(1){ printf("\nch=getch(); switch(ch){ 请选择:(1)插入数据(2)删除数据(3)结束\n"); case'1':addnode(); break; case'2':delnode(); break; case'3':return; } } } 三、栈的线性链表的压入和弹出算法实现主程序（实验二）#include<stdio.h>#include<stdlib.h>#include<conio.h>//主程序
第79页：图的遍历主程序
75voidmain(){ intx; charch; top=NULL;printf("\n请选择:(1)数据入栈ch=getch(); switch(ch){ case'1':{ (2)数据出栈(3)结束\n"); printf ("请输入入栈数据ax="); scanf("%d",&x); pushnode(x); break; } case'2':{ if(top==NULL)printf("\n堆栈下溢!\n"); elseprintf("\n弹出数据为%4d\n\n",popnode()); break; } case'3':return; } } } 四、循环队列的算法程序实现主程序（实验二）#include<stdio.h>#include<conio.h>//主程序voidmain(){ intn,i; charch; while(1){ printf ("\n请输入队首位置F="); scanf("%d",&f); f--; r=f; printf("\n"); if(f>=0&&f<m)break; printf("队首位置应在1--%2d之中!\n",m); }
第80页：循环队列主程序（续）
76while(1){ printf ("请输入已有元素个数n="); scanf("%d",&n); printf("\n"); if(n>=0&&n<=m)break; printf ("元素个数应在1--%2d之间!\n",m); } if(n>0){ printf ("请给已有元素赋值:\n\n"); for(i=1; i<=n; i++){ r++; if(r==m+1)r=0;scanf("%d",&v[r]); printf("\n"); } disp();while(1){ printf("\n请选择:(1)数据入队(2)数据出队ch=getch(); switch(ch){ case'1':addqulink(); break; case'2':outqulink(); break; case'3':return; } } (3)结束\n"); } 五、链式队列的算法程序实现（实验二）#include<stdio.h>#include<stdlib.h>#include<conio.h>//主程序voidmain(){ intn,i,a; charch; head=end=NULL; printf ("请输入已有元素个数n="); scanf("%d",&n); printf("\n"); if(n>0){
第81页：链队列主程序（续）
77(2)数据出队printf ("请给链式队列各节点赋值\n\n"); for(i=0; i<n; i++)addqulink(i); } while(1){ printf("\n请选择:(1)数据入队ch=getch(); switch(ch){ (3)结束\n"); case'1':n=addqulink(n); break; case'2':n=outqulink(n); break; case'3':return; } } } 六、已知以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法主程序（实验三）main(){ bitree*root; printf(“\n”); root=creat(); inorder(root); printf(“\n”); levorder(root); } 七、图的建立、存储和最短路径算法主程序（实验四）#include<stdio.h>#include<stdlib.h>#include<malloc.h>main(){ intf=1; intcycle=1; charc; while(cycle){
第82页：图的主程序功能选择（续）
78printf("\n功能选择:\n"); printf("\n1.创建图"); printf("\n2.打印图"); printf("\n3.求最短路径FLOYD"); printf("\n4.打印最短路径FLOYD"); printf("\n5.求最短路径Dijkstra"); printf("\n6.打印最短路径Dijkstra"); printf("\n7.退出"); printf("\n\n请选择: "); scanf("%c",&c); if(c!='7'){ switch(c){ case'1':creatgraph(); break; case'2':print(); break; case'3':shortpath_Floyd(); break; case'4':printpath_Floyd(); break; case'5':printf("\n请输入起始点序号(从1开始)\n"); scanf("%d",&f); shortpath_Dijkstra(f); break; case'6':printpath_Dijkstra(f); break; default:break; } } elsecycle=0; } } 八、用邻接矩阵表示的图的深度优先搜索和广度优先搜索（实验四）#include<stdio.h>//主函数main(){g=(mgraph*)malloc(sizeof(mgraph));//建立图g
第83页：图的遍历主程序（续）
79printf("thedfsis:");//对图g进行深度优先搜索dfstraverse(g);printf("thebfsis:");//对图g进行广度优先搜索bfstraverse(g);}