《算法与数据结构(实践)》new

PAGEPAGE36辽宁省高等教育自学考试软件技术（应用本科）专业课程设计报告书课程名称算法与数据结构（实践）助学单位信息技术学院姓名刘佳旭准考证号060111300227成绩二Ｏ一一年四月实验1顺序表的应用实训目的

1、掌握顺序表的定义及操作的C语言实现方法2、掌握相关操作的基本思想及其算法。实验要求1、线性表的基本概念和基本运算。2、顺序表的存储结构和查找、插入、删除等基本运算。3、单链表的存储结构以及单链表的建立、查找、插入删除等操作。4、双向链表的存储结构以及插入、删除操作。5、静态链表的存储结构和基本运算。6、利用线性表的基本运算解决复杂问题。实验步聚1.创建和销毁顺序表存储结构。创建一个顺序表在顺序表的指定位置插入一个元素；在顺序表的指定位置删除一个元素；将两个有序顺序表合并成一个新的有序顺序表-Linearsequenceofstorage,saidtable(structure)andrealizethecreationofachronologicaltable(datafromtheproposed)intheorderoftableelementstoinsertaspecifiedlocationinorderoftableelementstodeleteaspecifiedlocationwillmergetwotablesinanorderlysequenceintoanewtableinanorderlysequence销毁线性表voidDestroy_SeqList(PSeqListSeqListPoint){/*销毁顺序表，入口参数：为要销毁的顺序表指针地址，无返回值*/if(SeqListPoint)//SeqListPoint=NULL;return;}设调用函数为主函数，主函数对初始化函数和销毁函数的调用如下：main(){PSeqListSeqListPoint;SeqListPoint=Init_SeqList();……Destroy_SeqList(SeqListPoint);}2.实现顺序表的基本操作，如插入、删除、查找和遍历等。具体插入算法描述如下：

InsertList(SeqList*L,inti,DataTypex)

{//在顺序表L中第i个位置之前插入一个新结点x

if(i<1||i>L->length+1)

{printf("positionerror");return;}

if(L->length>=ListSize)

{printf("overflow");return;}

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

L->data[j+1]=L->data[j];

//从最后一个结点开始逐一后移

L->data[i-1]=x;//插入新结点x

L->length++;//实际表长加1

}从上述的算法以及插入过程图中可以看出，一般情况下，在第i(1≤i≤n)个结点之前插入一个新结点时，需要进行n-i+1次移动。而该算法的执行时间花在for循环的结点后移上，因此，该算法的时间复杂度不仅依赖于表的长度n，而且还与结点的插入位置i有关。当i=n+1时，for循环不执行，无需移动结点，属于最好情况，其时间复杂度为O(1)；当i=1，循环需要执行n次，即需要移动表中所有结点，属于最坏情况，算法时间复杂度为O(n)。由于插入结点可在表的任何位置上进行，因此需要分析讨论算法的平均移动次数。

假设pi是在第i个结点之前插入一个结点概率，则在长度为n的线性表中插入一个结点时所需要移动结点次数的期望值(平均次数)为:不失一般性，我们假定在线性表的任何位置上插入结点的机会是相等的，即是等概率的，则有：

p1=p2=…=pn+1=1/(n+1)

因此，在等概率情况下插入需要移动结点的平均次数为：

恰好是表长的一半，当表长n较大时，该算法的效率是相当低的。因为Eis(n)是取决于问题规模n的，它是线性阶的，因此算法的平均时间复杂度是O(n)。

例如，假定一个有序表A=(23,31,46,54,58,67,72,88)，表长n=8。当向其中插入56时，此时的i等于5，因此应插入到第i-1个位置上，从而需要将第i-1个元素及之后的所有元素都向后移动一位，将第i-1个元素位置空出来，插入新元素。插入后的有序表为(23,31,46,54,56,58,67,72,88)。按上述移动次数的计算公式，可知本插入操作需要移动n-i+1=8-5+1=4次。删除结点运算的算法如下：

DataTypeDeleteList(SeqList*L,inti)

{//在顺序表L中删除第个结点，并返回删除结点的值

if(i<1||i>L->length)

{printf("positionerror");

returnError;

}

x=L->data[i];//保存结点值

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

L->data[j-1]=L->data[j];//结点前移

L->length--;//表长减1

returnx;

}该算法的时间复杂度分析与插入算法类似，删除一个结点也需要移动结点，移动的次数取决于表长n和位置i。当i=1时，则前移n-1次，当i=n时不需要移动，因此算法的时间复杂度为O(n)；由于算法中删除第i个结点是将从第i+1至第n个结点依次向前移动一个位置，共需要移动n-i个结点。同插入类似，假设在顺序表上删除任何位置上结点的机会相等，qi为删除第i个结点的概率，则删除一个结点的平均移动次数为：

由此可以看出，在顺序表上做删除运算，平均移动结点次数约为表长的一半，因此，该算法的平均时间复杂度为O(n)。7、顺序表查找

顺序表是指线性表的顺序存储结构。假定在本章的讨论中，顺序表采用一维数组来表示，其元素类型为NodeType，它含有关键字key域和其它数据域data，key域的类型假定用标识符KeyType(int)表示，具体表的类型定义如下：

typedefstruct{

KeyTypekey；

InfoTypedata；

}NodeType；

typedefNodeTypeSeqList[n+1]；

//0号单元用作哨兵

在顺序表上的查找方法有多种，这里只介绍最常用的、最主要的两种方法，即顺序查找和二分查找。。

顺序查找(SequentialSearch)又称线性查找，它是一种最简单和最基本的查找方法。其基本思想是：从表的一端开始，顺序扫描线性表，依次把扫描到的记录关键字与给定的值k相比较；若某个记录的关键字等于k，则表明查找成功，返回该记录所在的下标，若直到所有记录都比较完，仍未找到关键字与k相等的记录，则表明查找失败，返回0值。因此，顺序查找的算法描述如下：

intSeqSearch(SeqListR,KeyTypek,intn)

{//从顺序表R中顺序查找记录关键字为k的记录，

//查找成功返回其下标，否则返回0；R[0]作为哨兵，

//用R[0].key==k作为循环下界的终结条件。

R[0].key=k；//设置哨兵

i=n；//从后向前扫描

while(R[i].key!=k)

i--；

returni；//返回其下标,若找不到，返回0

}

由于这个算法省略了对下标越界的检查，查找速度有了很大的提高，其哨兵也可设在高端，其算法留给读者自己设计。尽管如此，顺序查找的速度仍然是比较慢的，查找最多需要比较n+1次。若整个表R[1..n]已扫描完，还未找到与k相等的记录，则循环必定终止于R[0].key==k，返回值为0，表示查找失败，总共比较了n+1次；若循环终止于i>0,则说明查找成功，此时，若i=n，则比较次数Cn=1；若i=1，则比较次数C1=n；一般情况下Ci=n-i+1。因此，查找成功时平均查找长度为：

即顺序查找成功时的平均查找长度约为表长的一半(假定查找某个记录是等概率)。如果查找成功和不成功机会相等，那么顺序查找的平均查找长度：

((n+1)/2+(n+1))/2=3(n+1)/4

顺序查找的优点是简单的，且对表的结构无任何要求，无论是顺序存储还是链式存储，无论是否有序，都同样适用，缺点是效率低。顺序表的简单应用有序表的合并#include<iostream>usingnamespacestd;int*init(int*x,int&n){cout<<"输入顺序表的大小：";cin>>n;x=(int*)malloc(sizeof(int)*n);cout<<"输入"<<n<<"个数据："<<endl;for(inti=0;i<n;i++)cin>>x[i];returnx;}int*hebing(int*a,int*b,intna,intnb){int*c=(int*)malloc(sizeof(int)*(na+nb));inti=0,j=0,k=0;while(i<na&&j<nb){if(a[i]<b[j]){c[k]=a[i];i++;}else{c[k]=b[j];j++;}k++;}if(i==na)while(j<nb)c[k++]=b[j++];elsewhile(i<na)c[k++]=a[i++];returnc;}intmain(){int*a,*b,*sum,na,nb;a=init(a,na);b=init(b,nb);sum=hebing(a,b,na,nb);for(inti=0;i<na+nb;i++)cout<<sum[i]<<"";cout<<endl;return0;}二分法检索又称折半检索，二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组中，首先将给定值key与字典中间位置上元素的关键码比较，如果相等，则检索成功；否则，若key小，则在字典前半部分中继续进行二分法检索，若key大，则在字典后半部分中继续进行二分法检索。这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败。二分法检索是一种效率较高的检索方法，要求字典在顺序表中按关键码排序。实验2链表的应用实验目的1、熟悉C语言的上机环境，掌握C语言的基本结构。

2、会定义线性表的链式存储结构。

3、熟悉对链表的一些基本操作和具体的函数定义。

4、本章的主要任务是使用有关单链表的操作来实现通讯录信息系统的管理。实验要求1.创建和销毁链表存储结构。2.实现链表的基本操作，如插入、删除、查找和遍历等。3.链表的简单应用，如约瑟夫环、集合求并、一元多项式相加等。实验步骤1.创建和销毁链表存储结构。创建链表

一般将链表中的每个数据对象称为节点（Node）。创建链表的基本步骤如下:

第一步，创建第一个节点，并将此节点的内存地址保存

第二步，创建第二个节点，将第二个节点的首地址保存在第一个节点的成员变量中。

第三步，以此类推，创建第n个节点，并将此节点的地址存储到第n-1节点的成员变量中。销毁一个链表在链表使用完毕后建议销毁它，因为链表本身会占用内存空间。如果一个系统中使用很多的链表，而使用完毕后又不及时地销毁它，那么这些垃圾空间积累过多，最终可能导致内存的泄漏甚至程序的崩溃。因此应当养成及时销毁不用的链表的习惯。函数destroyLinkList()的作用是销毁一个链表list，它包括以下步骤。（1）首先将*list的内容赋值给p，这样p也指向链表的第一个结点，成为了链表的表头。（2）然后判断只要p不为空（NULL），就将p指向的下一个结点的指针（地址）赋值给q，并应用函数free()释放掉p所指向的结点，p再指向下一个结点。如此循环，直到链表为空为止。（3）最后将*list的内容置为NULL，这样主函数中的链表list就为空了，防止了list变为野指针。而且链表在内存中也被完全地释放掉了。2.实现链表的基本操作，如插入、删除、查找和遍历等。链表的插入

链表能够方便地实现结点的插入和删除操作，这也是链表结构具有动态分配存储空间的体现，也是它优于数组的地方之一。还是举小朋友排队的例子来说明链表的插入和删除是怎样实现的。在这个比喻里面，每一个小朋友相当于一个结点，一个小朋友的手拉着另一个小朋友的手，相当于一个结点的指针域指向下一个结点。假设现有一对按大小个排好队的小朋友，又来一个小朋友需要加入该队列。这时候，就需要从原来队列里面的第一个小朋友开始，按照他们的身高找到新来小朋友应该站的位置（前一个小朋友的身高比他矮，后一个小朋友的身高比他高）。然后，把这两个小朋友的手分开，让前一个小朋友的手该拉着新来小朋友的一只手，新来小朋友的另一只手拉着后一个小朋友的一只手。这样，新来的小朋友就被插入到这个队伍里面了，并且这个队伍的小朋友还是按照身高顺序排列的。特别地，如果新来小朋友最矮，他只需要站在队伍的开头，并且让他的一只手拉着原来站在对头的小朋友的手就行了。实际链表的插入操作也就可以类似地实现。链表的删除在链表中删除一个节点，用图7-4描述如下：[例7-6]创建一个学生学号及姓名的单链表，即节点包括学生学号、姓名及指向下一个节点的指针，链表按学生的学号排列。再从键盘输入某一学生姓名，将其从链表中删除。首先定义链表的结构：struct从图7-4中看到，从链表中删除一个节点有三种情况，即删除链表头节点、删除链表的中间节点、删除链表的尾节点。题目给出的是学生姓名，则应在链表中从头到尾依此查找各节点，并与各节点的学生姓名比较，若相同，则查找成功，否则，找不到节点。由于删除的节点可能在链表的头，会对链表的头指针造成丢失，所以定义删除节点的函数的返回值定义为返回结构体类型的指针。链表的遍历和查找

我们可以用与Length()函数类似的方法查找链表中的某一个结点。

//给定链表的头指针和待查结点数据，返回查到的结点的指针

node*Find(node*head，intdata)

{

node*current=head;

while(current!=NULL)

if(current->data==data)break;

elsecurrent=current->next;

returncurrent;

}

Find()函数的功能是：输入链表头结点head和待查结点数据data，如果某一个结点的数据与data相等，则返回该结点的指针；如果查完每一个结点也没有找到数据与data相等的结点，则返回空指针。

需要注意的是：Find函数也可以写成下面的形式。

//给定链表的头指针和待查结点数据，返回查到的结点的指针

node*Find(node*head，intdata)

{

node*current=head;

while(current!=NULL&¤t->data==data)

current=current->next;

returncurrent;

}

但把while的条件"current!=NULL&¤t->data==data"写成"current->data==data&¤t!=NULL"的形式，则Find函数可能会出现运行错误。这是因为：如果链表的最后一个结点，仍然不是要找的结点，则到下一次循环时current为NULL，再进行条件判断时，前者current!=NULL为真，而不再作current->data==data的判断，循环便结束；而后者在作current->data==data判断时就会导致程序崩溃。3.链表的简单应用，如约瑟夫环、集合求并、一元多项式相加等。链表的约瑟夫环#include<iostream>usingnamespacestd;intmark[1005];//数组来做表,方便快速高效intcur;//表的main(){intn,m;//n个人,数到第m个出列scanf("%d%d",&n,&m);//输入信息intcnt,on=n;cur=1;inti;while(on--)//出列n次{cnt=0;for(;cnt<m;++cur){if(cur==n+1)cur=1;if(mark[cur])continue;++cnt;}mark[cur-1]=1;//标记，出队printf("%d\n",cur-1);}return0;}实验3栈和队列的应用实验目的理解栈和队列的工程原理，掌握栈和队列在计算机程序设计中的应用。实验要求1.创建和销毁栈和队列的存储结构，要求达到“熟练掌握”层次。2.实现栈和队列的基本操作，要求达到“熟练掌握”层次。3.栈和队列的简单应用，要求达到“基本掌握”层次。实验步骤1.创建和销毁栈和队列的存储结构。//*HeaderFile#ifndef__STACK_H__#define__STACK_H__structNode;typedefstructNode*PtrToNode;typedefPtrToNodeStack;intIsEmpty(StackS);StackCreateStack(void);voidDisposeStack(StackS);voidMakeEmpty(StackS);voidPush(ElementTypeX,StackS);ElementTypeTop(StackS);voidPop(StackS);#endif////*ImplementationFile//节点结构structNode{ElementTypeElement;PtrToNodeNext;};////测试堆栈是否为空intIsEmpty(StackS){returnS->Next==NULL;}////创建一个空栈StackCreateStack(void){StackS;S=(Node*)malloc(sizeof(structNode));//分配一个节点的空间给栈Sif(S==NULL)exit(1);//分配失败S->Next=NULL;MakeEmpty(S);returnS;}////将栈清空voidMakeEmpty(StackS){if(S==NULL)exit(1);else{while(!IsEmpty(S))Pop(S);}}////进栈PushvoidPush(ElementTypeX,StackS){PtrToNodeTmpCell;TmpCell=malloc(sizeof(structNode));if(TmpCell==NULL)exit(1);else{TmpCell->Element=X;TmpCell->Next=S->next;S->next=TmpCell;}}//实验4树和二叉树的应用实验目的（1）熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；

（2）重点掌握二叉树的生成、遍历及求深度等算法；

（3）掌握二叉树的线索化及线索二叉树的遍历算法；掌握赫夫曼树的含义及其应用；

（4）掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。实验要求1.创建和销毁二叉树的存储结构。2.实现二叉树的基本操作，如查找和遍历等。3.二叉树的简单应用，如线索二叉树、哈夫曼树和表达式树等。4.树转化为二叉树的存储结构的创建和销毁。5.树与森林的遍历算法。6.树的简单应用，如因特网查询等。实验步骤1.创建和销毁二叉树的存储结构。二叉树的存储结构有多种，最常用的有两种：是顺序存储结构和链表存储结构。顺序存储结构二叉树可以存放在一维数组之中，这是一种简单的顺序存储结构。请看如下语句：constintMAXSIZE20

typedefcharElemType;

ElemTypebt[MAXSIZE];其中Bt就是一维数组（向量），用它来存储一棵二叉树，每个数组元素存储树的一个结点的数据信息。假设让bt[0]闲置，让bt[1]存放根结点信息。假设按照自上而下、自左至右的顺序将图6.4(a)的满二叉树存入一维数组bt，可以发现图6.4(a)中结的编号恰好与数组元素的下标号相对应，详见6.5图。根据二叉树性质5，在bt数组中可以方便地由某结点bt[i]的下标i，找到它的双亲结点bt[i/2]或者它的左、右孩子结点bt[2i]、bt[2i+1]。例如bt[2]结点值为B，它的双亲结点是bt[1]值为A，左孩子结点是bt[4]值为D，右孩子结点是bt[5]值为E。链式存储结构用于二叉树存储的链表结构，常见的有二叉链表和三叉链表。二叉链表的每个结点有一个数据域和两个指针域，一个指针指向左孩子，另一个指针指向右孩子。2.实现二叉树的基本操作，如查找和遍历等。二叉树的一般操作，实现了下：主要练习了二叉树的非递归遍历，利用栈，和队列来完成。代码#include"stdio.h"#include"malloc.h"#define

MAXSIZE20//二叉树结点的结构体表示形式typedefstructnode{char

data;structnode*left,*right;}BTree;//栈的结构体表示形式typedefstructstackelem{BTree*a[MAXSIZE];inttop;}Stack;//队列的结构体的表示形式typedefstructqueueelem{BTree*b[MAXSIZE];intfront,rear;}Queue;//前序遍历，递归的方法voidPreorder(BTree*bt){if(NULL!=bt){printf("%c",bt->data);Preorder(bt->left);Preorder(bt->right);}}3.二叉树的简单应用，如线索二叉树、哈夫曼树和表达式树等。线索二叉树：n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded

BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

线索链表解决了二叉链表找左、右孩子困难的问题，出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题。哈夫曼树：哈夫曼树（Huffman）又称最优二叉树，是一类带权路径长度最短的树，有着广泛的应用。

在讨论哈夫曼树之前首先需要弄清楚关于路径和路径长度的概念。树中两个结点之间的路径由一个结点到另一结点的分支构成。两结点之间的路径长度是路径上分支的数目。树的路径长度是从根结点到每一个结点的路径长度之和。4.树转化为二叉树的存储结构的创建和销毁。完全二叉树结点编号

在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。完全二叉树的顺序存储

将完全二叉树中所有结点按编号顺序依次存储在一个向量bt[0..n]中。

其中：

bt[1．．n]用来存储结点

bt[0]不用或用来存储结点数目。一般二叉树的顺序存储

①将一般二叉树添上一些"虚结点"，成为"完全二叉树"

②为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给结点编号

③将结点按编号存入向量对应分量，其中"虚结点"用"∮"表示5.树与森林的遍历算法。前序遍历树

步骤：

(1)访问根结点；

(2)按从左至右的次序前序遍历根的各棵子树。

前序遍历树和前序遍历与该树相对应的二叉树具有相同的遍历结果，即它们的前序遍历是相同的。后序遍历树

步骤：

(1)按从左至右的次序后序遍历根的各棵子树；

(2)访问根结点。

后序遍历树和中序遍历与该树相对应的二叉树具有相同的遍历结果。森林的遍历前序遍历森林

步骤：

(1)访问森林中第一棵树的根结点；

(2)前序遍历森林中第一棵树的根结点的各子树；

(3)前序遍历森林中除第一棵树外其余各树所构成的森林。

前序遍历森林和前序遍历与该森林相对应的二叉树具有相同的遍历结果。

后序遍历森林

步骤：

(1)后序遍历森林中第一棵树的根结点的各子树；

(2)访问森林中第一棵树的根结点；

(3)后序遍历森林中除第一棵树外其余各树所构成的森林。

后序遍历森林和中序遍历与该树相对应的二叉树具有相同的遍历结果。6.树的简单应用，如因特网查询等。哈夫曼编码(HuffmanEncoding)是最古老，以及最优雅的数据压缩方法之一。它是以最小冗余编码为基础的，即如果我们知道数据中的不同符号在数据中的出现频率，我们就可以对它用一种占用空间最少的编码方式进行编码，这种方法是，对于最频繁出现的符号制定最短长度的编码，而对于较少出现的符号给较长长度的编码。哈夫曼编码可以对各种类型的数据进行压缩，如应用在JPEG图像的算法很多领域.

在这里我们采用一个文本文件来演示哈夫曼编码的.为了说明问题,这个文本文件是高度简化,这样程序会变得相对简单,比较好理解.

1.文件内容只会出现ASCII字符.即字符集里的字符总数不超过255.

2.用一串两进制数比如10,110,1110,0来代表文件里字符.每个字符有一个独立编码.而且是一种特殊前缀的编码,即任一个编码都不是另外一个编码的前缀.

3.统计文本文件中各个字符出现频率,出现频率最高的字符分配最短的号码.

实验5图的应用实验目的（1）掌握线性结构、树形结构和图形结构等基本数据结构及算法的应用；（2）掌握分治技术、贪心技术、回溯和分支限界等经典算法设计技术应用；（3）熟练掌握搜索算法和排序算法的应用；（4）具备应用算法与数据结构开发简单应用软件的能力。实验要求（1）图的邻接表和邻接矩阵存储结构的创建和销毁，要求达到“熟练掌握”层次。（2）实现图的基本操作，要求达到“熟练掌握”层次。实验步骤1.图的邻接表和邻接矩阵存储结构的创建和销毁。2．实现图的基本操作，如查找和遍历等。3．图的应用，如最小生成树、单源最短路径、拓扑排序等。（1）.图的邻接表和邻接矩阵存储结构的创建和销毁。////////////////////////////////////////////////////////////////////图是通过文件建立的//数据元素为char类型//存储结构为邻接表//文件中第一行为图的类型//第二行为节点元素，以#结束//下边每一行为边，和边的权值//下边是文件的示例/*2ABCD#AB3AC4BC2CD4DA1##*///////////////////////////////////////////////////////////////////#include<iostream>#include<fstream>usingnamespacestd;constintMaxNum=20;constintInfinity=-1;typedefcharVexType;typedefintArcType;typedefstructQNode//定义队列节点{intdata;QNode*next;}*LQueuePtr;structLQueue//定义队列结构体LQueuePtrfront,rear;};oidQueueInit(LQueue&Q)//队列初始化{Q.front=newQNode;Q.front->next=0;Q.rear=Q.front;}voidEnqueue(LQueue&Q,inte){LQueuePtrs;s=newQNode;s->data=e;s->next=0;Q.rear->next=s;Q.rear=s;}boolDequeue(LQueue&Q,int&e){LQueuePtrp;if(Q.front==Q.rear)returnfalse;p=Q.front;Q.front=p->next;e=Q.front->data;deletep;returntrue;}pedefstructArcNode//定义边的结构体{intadjvex;ArcTypeinfo;ArcNode*nextarc;}*ArcPtr;structVexNode//定义节点的结构体{VexTypedata;ArcPtrfirstarc;};structALGraph//定义图的结构体{VexNodevexs[MaxNum+1];intkind,vexnum,arcnum;};intLocateVex(ALGraph&G,VexTypev)//在图中找到某一个元素{inti;for(i=G.vexnum;i>0&&G.vexs[i].data!=v;i--);returni;}voidCreateGraph(ALGraph&G,charfn[])//创建图{inti,j;VexTypeu,v;ArcPtrp;ifstreamf;ArcTypew;f.open(fn);//打开文件失败if(!f){G.vexnum=0;return;}//读入图的种类f>>G.kind;//先设置边数为0G.arcnum=0;i=0;while(true)//向节点数组中添加节点{f>>u;if('#'==u)break;i++;G.vexs[i].data=u;G.vexs[i].firstarc=0;}G.vexnum=i;while(true)//读入各条边{f>>u>>v;if('#'==u||'#'==v)break;i=LocateVex(G,u);if(0==i)continue;j=LocateVex(G,v);if(0==j||j==i)continue;if(1==G.kind||3==G.kind)w=1;elsef>>w;G.arcnum++;p=newArcNode;p->adjvex=j;p->info=w;p->nextarc=G.vexs[i].firstarc;G.vexs[i].firstarc=p;if(G.kind<=2)continue;p=newArcNode;p->adjvex=i;p->info=w;p->nextarc=G.vexs[j].firstarc;G.vexs[j].firstarc=p;}f.close();}voidOutputGraph(ALGraph&G)//输出图voidDFS(ALGraph&G,inti,boolvisited[],voidvisit(VexType))//图的名称，当前节点位置，标记数组，访问函数{intj;ArcPtrp;//访问当前节点visit(G.vexs[i].data);//修改标记值visited[i]=true;for(p=G.vexs[i].firstarc;p;p=p->nextarc){j=p->adjvex;if(!visited[j])//对下一个节点递归DFS(G,j,visited,visit);}}voidDFSTraverse(ALGraph&G,voidvisit(VexType)){inti;boolvisited[MaxNum+1];for(i=1;i<=G.vexnum;i++)//初始化标记数组{visited[i]=false;}for(i=1;i<=G.vexnum;i++){if(!visited[i]){DFS(G,i,visited,visit);}}}voidBFSTraverse(ALGraph&G,voidvisit(VexType)){//访问节点visit(G.vexs[v].data);visited[v]=true;//将访问的节点入队Enqueue(q,v);while(Dequeue(q,u))//出队并访问{for(p=G.vexs[u].firstarc;p;p=p->nextarc){w=p->adjvex;if(!visited[w]){visit(G.vexs[w].data);visited[w]=true;Enqueue(q,w);}}}}}intmain(){ALGraphG;CreateGraph(G,"aaa.txt");cout<<"创建的图为:";OutputGraph(G);cout<<"深度优先遍历："<<endl;DFSTraverse(G,visit);cout<<endl<<"广度优先遍历"<<endl;BFSTraverse(G,visit);cout<<endl;return0;}2．实现图的基本操作，如查找和遍历等#include<stdio.h>#include<iostream.h>structgraph{chartnode;charhnode;doublequanzhi;}gr[100];charnode[50]="";doublegraphshu[50][50];intmini(intt,intn)printf("用普里姆算法得出的结果是:\n");printf("路径为：");intt2=0;for(k=0;k<n-1;k++){intt1=mini(t2,n);sum=sum+graphshu[t2][t1];for(inti=0;i<n;i++)graphshu[i][t2]=30000;graphshu[t2][t1]=30000;for(i=0;i<n;i++)graphshu[t1][i]=minval(graphshu[t2][i],graphshu[t1][i]);printf("(%c,%c)",node[t2],node[t1]);t2=t1;}printf("\n最小生成树的总耗费为:%f\n",sum);}voidKruscal(intk,intn)value=gr[0].quanzhi;for(i=1;i<k;i++)//tt为最小权的下标if(value>=gr[i].quanzhi){tt=i;value=gr[i].quanzhi;}///////for(i=0;i<n;i++){if(gr[tt].tnode==node[i])ii=i;if(gr[tt].hnode==node[i])jj=i;}if(nod[ii]==nod[jj]){gr[tt].quanzhi=30000;continue;}else{if(nod[ii]>=nod[jj]){for(i=0;i<n;i++)if(nod[i]==nod[ii])nod[i]=nod[jj];}else{for(i=0;i<n;i++)if(nod[i]==nod[jj])nod[i]=nod[ii];{cin>>gr[k].hnode;cin>>gr[k].quanzhi;}}intp,o=1;for(intj=0;j<k;j++)//n为顶点数{for(intt=0;t<o;t++)if(gr[j].tnode!=node[t])p=0;else{p=1;break;}if(p==0){node[n]=gr[j].tnode;n++;o++;}}for(j=0;j<k;j++){for(intt=0;t<o;t++)if(gr[j].hnode!=node[t])p=0;else{p=1;break;}if(p==0){node[n]=gr[j].hnode;n++;o++;}}for(inti=0;i<n;i++)for(intj=0;j<n;j++)graphshu[i][j]=30000;for(i=0;i<k;i++)//构造数组{for(intj=0;j<n;j++)if(gr[i].tnode==node[j]){ii=j;break;}for(j=0;j<n;j++)if(gr[i].hnode==node[j]){jj=j;break;}graphshu[ii][jj]=gr[i].quanzhi;}for(i=0;i<n;i++)for(intj=i;j<n;j++)graphshu[j][i]=graphshu[i][j];//prim(k,n);charoption;intx;for(x=1;x<=4;x++){cout<<"求给定网的最小生成树"<<endl;cout<<"1.普里姆（Prim）算法"<<endl;cout<<"2.克鲁斯卡尔（Kruskal）算法"<<endl;cout<<"3.退出"<<endl;cout<<"请选择:";cin>>option;switch(option){case'1':Prim(n,k);break;case'2':Kruscal(n,k);break;case'3':return;}}}输入文件：如果该数字序列不是度序列，只需在第一行输出“No！”;如果该数字序列是一个度序列，首先在第一行输出“Yes！”；然后在接下来的若干行里输出一个符合该度序列的图所有边，每行一条边。我们默认一个图的顶点编号为1至T，如果顶点i与j之间有一条边，我们表示为“ij”。例如图一就可以表示为：13243435输入样例1：532111输出样例1：Yes!13243435输入样例2：No!说明：若连接结点之间的边可以不止一条，这样的图称为多重图。一个结点如果有指向自己的边，这条边被称为自环。无向简单图是指无自环的非多重图。3．图的应用，如最小生成树、单源最短路径、拓扑排序等/*已调试成功前半部分(yes/no)*/#include<stdio.h>#defineNMAX100intmain(){statica[NMAX][NMAX];inttop[NMAX];inttops,i,temp,s=0,s1=0;scanf("%d",&tops);if(tops>NMAX){fprintf(stderr,"toomanyvertax...\n");return-1;}for(i=0;i<tops;++i){scanf("%d",&temp);s+=top[i]=temp;if(temp%2)++s1;}if(s%2||s1%2){printf("No!\n");return1;}printf("Yes!\n");/*waiting...*/return0;}实验6散列表的应用实验目的(1)掌握散列查找的基本思想；(2)掌握闭散列表的构造方法；(3)掌握线性探测处理冲突的方法；(4)掌握散列技术的查找性能。实验要求(1)了解散列表存储结构的创建和销毁。(2)了解实现散列表的基本操作，如插入、删除和查找等。(3)解决散列冲突方法的应用，如开放地址法和链地址法等。实验步骤散列表由固定数目的散列表元组成。散列表元或是空，或是包含有与某个关键字相关联的数据。为了找到某个关键字值的数据，就要通过散列函数作用于关键字值来计算出散列表元数。对于某一个给定关键字的值，散列函数总是产生出相同的散列表元数。

冲突和重复

当散列表元的数目少于关键字值的数目时，两个或者两个以上的关键字值就有可能被散列到同一个散列表元上，这被称作冲突。当发生冲突的时候，有两种选择，一种是扩展散列表元，使它可以含有多个表项；另一种是不能有多重散列表项。

后种方法不是一个好的解决方案，这使我们构造巨大的散列表以避免冲突。在大多数情况下，可以让散列表元包含多个散列表项，而这些散列表项都是被散列到该散列表元的。

散列表元可以是一个包含简单表项的链表，空的散列表元含有一个空的链表，散列表元的新表项被附加到该散列表元的表项链表的尾部。

FrankAn(WindSor,Ontario,Canada)写了一个简单的算法，代码如下：#include<iostream>

#include<stdlib.h>usingnamespacestd;enumHashKeyType

{

KEY_STRING,

KEY_INT,

KEY_LONG,

KEY_USER1,

KEY_USER2,

KEY_USER3,

KEY_USER4

};//定义1

structHashEntryBase

{

HashEntryBase*Prev;

HashEntryBase*Next;

HashEntryBase();

virtualHashKeyTypeGetKeyType()const=0;

virtualsize_tHash(size_tbuckets)const=0;

virtualintKeyEquals(constHashEntryBase*entry)const=0;

};//定义2

structHashEntryInt:publicHashEntryBase

{

intKey;

HashEntryInt(constint&k);

HashEntryInt(constHashEntryInt&e);

virtualHashKeyTypeGetKeyType()const;

virtualsize_tHash(size_tbuckets)const;

virtualintKeyEquals(constHashEntryBase*entry)const;

protected:

HashEntryInt();

};

structHashEntryIntDB:publicHashEntryInt

{

intdata;

HashEntryIntDB(constint&k,constint&db):HashEntryInt(k)

{

data=db;

}

};

structHashEntryStr:publicHashEntryBase

{

stringKey;

HashEntryStr(conststring&k);

HashEntryStr(constHashEntryStr&e);

virtualHashKeyTypeGetKeyType()const;

virtualsize_tHash(size_tbuckets)const;

virtualintKeyEquals(constHashEntryBase*entry)const;

protected:

HashEntryStr();

};

structHashEntryStrDB:publicHashEntryStr

{

stringdata;

HashEntryStrDB(conststring&k,conststring&db):HashEntryStr(k)

{

data=db;

}

};//定义3

classHashBucker;//定义4

classHashTableBase

{

public:

HashTableBase(size_tbuckets);

~HashTableBase();

protected:

boolAddEntry(HashEntryBase*newe);

boolDelEntry(constHashEntryBase*dele);

boolIsDupe(constHashEntryBase*dupe);

constHashEntryBase*FindEntry(constHashEntryBase*find);

virtualboolTravCallback(constHashEntryBase*e)const=0;

boolTraverse();

size_tNoOfBuckets;

HashBucker**Table;

};typedefbool(HashTableBase::*HashTravFunc)(constHashEntryBase*e)const;//定义3

classHashBucker

{

public:

HashBucker();

~HashBucker();

boolAddEntry(HashEntryBase*newe);

boolDelEntry(constHashEntryBase*dele);

boolIsDupe(constHashEntryBase*dupe);

constHashEntryBase*FindEntry(constHashEntryBase*find);

boolTraverse(constHashTableBase&table,HashTravFuncfunc);

protected:

HashEntryBase*First;

};//定义5

typedefbool(*HashEnumFuncIntDB)(constint&k,constint&db);

classHashTableIntDB:privateHashTableBase

{

public:

HashTableIntDB(size_tbuckets):HashTableBase(buckets){};

boolInsert(constint&key,constint&db);

boolDelete(constint&dele);

intLookUp(constint&key);

boolEnumerate(HashEnumFuncIntDBfunc);

protected:

virtualboolTravCallback(constHashEntryBase*e)const;

HashEnumFuncIntDBEnumCallBack;

};typedefbool(*HashEnumFuncStrDB)(conststring&k,conststring&db);

classHashTableStrDB:privateHashTableBase

{

public:

HashTableStrDB(size_tbuckets):HashTableBase(buckets){};

boolInsert(conststring&key,conststring&db);

boolDelete(conststring&dele);

stringLookUp(conststring&key);

boolEnumerate(HashEnumFuncStrDBfunc);

protected:

virtualboolTravCallback(constHashEntryBase*e)const;

HashEnumFuncStrDBEnumCallBack;

};

//实现1

inlineHashEntryBase::HashEntryBase()

{

Prev=NULL;

Next=NULL;

}//实现2

inlineHashEntryInt::HashEntryInt()

{

}

inlineHashEntryInt::HashEntryInt(constint&k):Key(k)

{

}

inlineHashEntryInt::HashEntryInt(constHashEntryInt&e):Key(e.Key)

{

}

HashKeyTypeHashEntryInt::GetKeyType()const

{

returnKEY_INT;

}

intHashEntryInt::KeyEquals(constHashEntryBase*entry)const

{

if(KEY_INT!=entry->GetKeyType())

printf("mismatchedtypes.\n");

return(Key==((constHashEntryInt*)entry)->Key);

}

size_tHashEntryInt::Hash(size_tbuckets)const

{

returnsize_t(Key%(unsignedlong)buckets);

}

inlineHashEntryStr::HashEntryStr()

{

}

inlineHashEntryStr::HashEntryStr(conststring&k):Key(k)

{

}

inlineHashEntryStr::HashEntryStr(constHashEntryStr&e):Key(e.Key)

{

}

HashKeyTypeHashEntryStr::GetKeyType()const

{

returnKEY_STRING;

}

intHashEntryStr::KeyEquals(constHashEntryBase*entry)const

{

if(KEY_STRING!=entry->GetKeyType())

printf("mismatchedtypes.\n");

return(Key==((constHashEntryStr*)entry)->Key);

}

size_tHashEntryStr::Hash(size_tbuckets)const

实验7排序的应用实验目的（1）掌握查找的不同方法，并能用高级语言实现查找算法。（2）熟练掌握顺序表和有序表的顺序查找和二分查找方法。（3）掌握排序的不同方法，并能用高级语言实现排序算法。（4）熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现实验要求(1）深化理解书本上的理论知识，将书本的知识变“活”（为已掌握，为已活用）；(2）理论和实践相结合，学会将相关的数据结构和算法应用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。实验步骤输入：一个包含n个正整数的文件，每个正整数小于n,n等于10的7次方（一千万）。并且文件内的正整数没有重复和关联数据。

输出:

输入整数的升序排列

约束：限制在1M左右内存，充足的磁盘空间假设整数占32位，1M内存可以存储大概250000个整数，第一个方法就是采用基于磁盘的合并排序算法，第二个办法就是将0-9999999切割成40个区间，分40次扫描（10000000/250000)，每次读入250000个在一个区间的整数，并在内存中使用快速排序。书中提出的第三个解决办法是采用bitmap（或者称为bitvector）来表示所有数据集合（注意到条件，数据没有重复），这样就可以一次性将数据读入内存，减少了扫描次数。算法的伪代码如下：

阶段1：初始化一个空集合

fori=[0,n)

bit[i]=0;

阶段2：读入数据i，并设置bit[i]=1

foreachiintheinputfile

bit[i]=1;

阶段3：输出排序的结果

fori=[0,n)

ifbit[i]==1

writeiontheoutputfile算法的时间复杂度为O(N)

#include<stdio.h>

#defineWORD32

#defineSHIFT5

#defineMASK0x1F

#defineN10000000

intbitmap[1+N/WORD];

/*

*置位函数——用"|"操作符,i&MASK相当于mod操作

*mmodn运算，当n=2的X次幂的时候,mmodn=m&(n-1)

*/

void

set(inti)

{

bitmap[i>>SHIFT]|=(1<<(i&MASK));

}

/*清除位操作，用&~操作符*/

void

clear(inti)

{

bitmap[i>>SHIFT]&=~(1<<(i&MASK));

}

/*测试位操作用&操作符*/

int

test(inti)

{

returnbitmap[i>>SHIFT]&(1<<(i&MASK));

}

intmain()

{

inti=0;

printf("beforesort:\n");

while(scanf("%d",&i)!=EOF){

set(i);

}

printf("aftersort:\n");

for(i=0;i<N;i++){

if(test(i)){

printf("%d\n",i);

}

}

return0;

}======================基于位图的整数序列合并算法=====================================搜索引擎检索时，常常要将两个结果进行组合处理，例如查询“中国北京”，则需要将包含“中国”和“北京”的文档编号序列进行合并的操作。常用的算法有归并，先排序后去重等，但这些算法在大数据量的情况下，如对包含“中国”的10万个文档编号序列和包含“北京”的8万个文档编号序列进行组合时，效率比较低，无法满足搜索引擎高速的检索要求。我们引入了基于二进制数组的算法来解决这个问题。

基于二进制数组的整数序列合并算法是一种高速的多个整数序列组合的算法。它的基本原理是将各整数序列保存在一个二进制的数组当中，然后对这些二进制数组进行并，或的运算。

下面详细介绍一下此算法的处理过程。

1．将整数序列转为二进制数组。

先申请一个二进制数组，其大小为有可能出现的最大的整数值，如500万，如图所示。（图1）

假设有5个整数组成的序列{2,3,200,7000,12000}，则我们可以将这个序列保存在二进制数组当中，如图2所示，第n位如果为1，则表示n存在于这个序列中：（图2）

2．对两个序列进行位运算。

如果需要对两个整数序列进行并的操作，那么只需要对它们对应的二进制数组进行“并”的位运算；如果需要对两个整数序列进行或的操作，那么只需要对它们对应的二进制数组进行“或”的位运算；如果需要对两个整数序列进行NOT的操作，那么只需要对它们对应的二进制数组先进行“并”的位运算，再进行“异或”的位运算。

计算机进行位运算的速度是最快的。在实际的程序中，我们可以以long类型为基本的位运算单位，相同位置的long型数据进行两两位运算，以提高速度。

3．将二进制数组转为结果整数序列。

位运算结束后，需要将这个结果再转为整数序列。这个转换后的整数序列就是我们需要的最终结果。

下面是一次完整的运算过程，我们需要将{2,3,300}和{2,3,200,7000,12000}这两个序列进行并的操作。如图3所示。实验八典型算法的应用实验目的掌握顺序查找（设置监视哨）、折半查找等典型HYPERLI