《算法与数据结构（实践）》(数据结构与算法导论)

　　下面是范文网小编收集的《算法与数据结构（实践）》(数据结构与算法导论)，以供参考。

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

　　实验 1 顺序表的应用 实训目的 1、掌握顺序表的定义及操作的 C 语言实现方法 2、掌握相关操作的基本思想及其算法。

　　实验要求 1、线性表的基本概念和基本运算。

　　2、顺序表的存储结构和查找、插入、删除等基本运算。

　　3、单链表的存储结构以及单链表的建立、查找、插入删除等操作。

　　4、双向链表的存储结构以及插入、删除操作。

　　5、静态链表的存储结构和基本运算。

　　6、利用线性表的基本运算解决复杂问题。

　　实验步聚 1. 创建和销毁顺序表存储结构。

　　创建一个顺序表 在顺序表的指定位置插入一个元素； 在顺序表的指定位置删除一个元素； 将两个有序顺序表合并成一个新的有序顺序表 -Linear sequence of storage, said table (structure) and realize the creation of a chronological table (data from the proposed) in the order of table elements to insert a specified location in order of table elements to delete a specified location will merge two tables in an orderly sequence into a new table in an orderly sequence 销毁线性表 void Destroy_SeqList(PSeqList SeqListPoint) { /*销毁顺序表，入口参数：为要销毁的顺序表指针地址，无返回值*/ if (SeqListPoint) //SeqListPoint=NULL; return ; } 设调用函数为主函数，主函数对初始化函数和销毁函数的调用如下：

　　main() { PSeqList SeqListPoint; SeqListPoint =Init_SeqList( ); …… Destroy_SeqList (SeqListPoint); } } 2. 实现顺序表的基本操作，如插入、删除、查找和遍历等。

　　具体插入算法描述如下：

　　InsertList(SeqList *L,int i,DataType x) {//在顺序表 L 中第 i 个位置之前插入一个新结点 x if(i<1 || i>L->length+1) { printf("position error");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)。由于插入结点可在表的任何位置上进行，因此需要分析讨论算法的平均移动次数。

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

　　p 1 =p 2 = … = p n+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 次。

　　删除结点运算的算法如下：

　　DataType DeleteList(SeqList *L,int i) {//在顺序表 L 中删除第个结点，并返回删除结点的值 if(i<1||i>L->length) { printf("position error");

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

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

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

　　typedef struct { KeyType key； InfoType data； }NodeType； typedef NodeType SeqList[n+1]； //0 号单元用作哨兵 在顺序表上的查找方法有多种，这里只介绍最常用的、最主要的两种方法，即顺序查找和二分查找。

　　。

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

　　int SeqSearch(SeqList R,KeyType k,int n) {//从顺序表 R 中顺序查找记录关键字为 k 的记录，

　　//查找成功返回其下标，否则返回 0；R[0]作为哨兵， //用 R[0].key==k 作为循环下界的终结条件。

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

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

　　((n+1)/2+(n+1))/2=3(n+1)/4 顺序查找的优点是简单的，且对表的结构无任何要求，无论是顺序存储还是链式存储，无论是否有序，都同样适用，缺点是效率低。

　　顺序表的简单应用 1、 有序表的合并 #include <iostream> using namespace std; int * init(int *x , int &n) { cout<<"输入顺序表的大小："; cin>>n; x = (int*)malloc(sizeof(int) * n); cout<<"输入"<<n<<"个数据："<<endl; for(int i = 0 ; i < n ; i++) cin>>x[i]; return x; } int * hebing(int *a , int *b , int na , int nb) { int * c = (int*)malloc(sizeof(int)*(na+nb)); int i = 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++]; else while(i < na) c[k++] = a[i++]; return c; } int main() { int *a , *b , *sum , na , nb; a = init(a,na); b = init(b,nb); sum = hebing(a,b,na,nb); for(int i = 0 ; i < na+nb ; i++) cout<<sum[i]<<" "; cout<<endl; return 0; } 二分法检 索又称折半检索，二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组中，首先将给定值 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，int data) { node* current = head; while (current!=NULL) if(current->data == data) break; else current = current->next; return current; } Find()函数的功能是：输入链表头结点 head 和待查结点数据 data，如果某一个结点的数据与 data 相等，则返回该结点的指针；如果查完每一个结点也没有找到数据与 data相等的结点，则返回空指针。

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

　　//给定链表的头指针和待查结点数据，返回查到的结点的指针 node* Find(node* head，int data) { node* current = head; while (current!=NULL&& current->data == data) current = current->next; return current; } 但把while的条件"current!=NULL&& current->data == data"写成" current->data == data &&current!=NULL"的形式，则 Find 函数可能会出现运行错误。这是因为：如果链表的最后一个结点，仍然不是要找的结点，则到下一次循环时 current 为 NULL，再进行条件判

　　断时，前者 current!=NULL 为真，而不再作 current->data == data 的判断，循环便结束；而后者在作 current->data == data 判断时就会导致程序崩溃。

　　3. 链表的简单应用，如约瑟夫环、集合求并、一元多项式相加等。

　　链表的约瑟夫环 #include <iostream> using namespace std; int mark[1005];// 数组来做表,方便快速高效 int cur;//表的 index. int main() { int n,m;//n 个人,数到第 m 个出列 scanf("%d%d",&n,&m);//输入信息 int cnt ,on=n; cur = 1; int i; 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); } return 0; }

　　实验 3 栈和队列的应用 实验目的 理解栈和队列的工程原理，掌握栈和队列在计算机程序设计中的应用。

　　实验要求 1. 创建和销毁栈和队列的存储结构，要求达到“熟练掌握”层次。

　　2. 实现栈和队列的基本操作，要求达到“熟练掌握”层次。

　　3. 栈和队列的简单应用，要求达到“基本掌握”层次。

　　实验步骤 1. 创建和销毁栈和队列的存储结构。

　　//--------* Header File------------------------------------------------------------------------ #ifndef __STACK_H__ #define __STACK_H__ struct Node; typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty(Stack S); Stack CreateStack(void); void DisposeStack(Stack S); void MakeEmpty(Stack S); void Push(ElementType X, Stack S); ElementType Top(Stack S); void Pop(Stack S); #endif //---------------------------------------------------------------------------------------------- //--------* Implementation File-------------------------------------------------------------- //节点结构 struct Node { ElementType Element; PtrToNode Next; };

　　//---------------------------------------------------------------------------------------------- //测试堆栈是否为空 int IsEmpty(Stack S) { return S->Next == NULL; } //---------------------------------------------------------------------------------------------- //创建一个空栈 Stack CreateStack(void) { Stack S; S = (Node *) malloc ( sizeof(struct Node) ); //分配一个节点的空间给栈 S if(S==NULL) exit(1); //分配失败 S->Next = NULL; MakeEmpty(S); return S; } //---------------------------------------------------------------------------------------------- //将栈清空 void MakeEmpty(Stack S) { if(S == NULL) exit(1); else{ while(!IsEmpty(S)) Pop(S); } } //---------------------------------------------------------------------------------------------- //进栈 Push void Push(ElementType X, Stack S) { PtrToNode TmpCell;

　　TmpCell = malloc(sizeof(struct Node)); 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. 创建和销毁二叉树的存储结构。

　　二叉树的存储结构有多种，最常用的有两种：是顺序存储结构和链表存储结构。

　　顺序存储结构 二叉树可以存放在一维数组之中，这是一种简单的顺序存储结构。请看如下语句：

　　const int MAXSIZE 20 typedef char ElemType; ElemType bt[MAXSIZE]; 其中 Bt 就是一维数组（向量），用它来存储一棵二叉树，每个数组元素存储树的一个结点的数据信息。假设让 bt[0] 闲置，让 bt[1] 存放根结点信息。假设按照自上而下、自左至右的顺序将图 (a) 的满二叉树存入一维数组 bt ，可以发现图 (a) 中结的编号恰好与数组元素的下标号相对应，详见 图。根据二叉树性质 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 "" #include "" #define MAXSIZE 20 //二叉树结点的结构体表示形式 typedef struct node{ char data; struct node* left,*right;

　　}BTree; //栈的结构体表示形式 typedef struct stackelem{ BTree* a[MAXSIZE]; int top; }Stack; //队列的结构体的表示形式 typedef struct queueelem{ BTree* b[MAXSIZE]; int front,rear;}Queue; //前序遍历，递归的方法 void Preorder(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. 树的简单应用，如因特网查询等。

　　哈夫曼编码(Huffman Encoding) 是最古老，以及最优雅的数据压缩方法之一。它是以最小冗余编码为基础的，即如果我们知道数据中的不同符号在数据中的出现频率，我们就可以对它用一种占用空间最少的编码方式进行编码，这种方法是，对于最频繁出现的符号制定最短长度的编码，而对于较少出现的符号给较长长度的编码。

　　哈夫曼编码可以对各种类型的数据进行压缩，如应用在 JPEG 图像的算法很多领域. 在这里我们采用一个文本文件来演示哈夫曼编码的.为了说明问题,这个文本文件是高度简化,这样程序会变得相对简单,比较好理解. 1.文件内容只会出现 ASCII 字符.即字符集里的字符总数不超过 255. 2.用一串两进制数比如 10,110,1110,0 来代表文件里字符.每个字符有一个独立编码.而且是一种特殊前缀的编码,即任一个编码都不是另外一个编码的前缀. 3.统计文本文件中各个字符出现频率,出现频率最高的字符分配最短的号码.

　　实验 5 图 的应用 实验目的 （1）掌握线性结构、树形结构和图形结构等基本数据结构及算法的应用； （2）掌握分治技术、贪心技术、回溯和分支限界等经典算法设计技术应用； （3）熟练掌握搜索算法和排序算法的应用； （4）具备应用算法与数据结构开发简单应用软件的能力。

　　实验要求 （1）图的邻接表和邻接矩阵存储结构的创建和销毁，要求达到“熟练掌握”层次。

　　（2）实现图的基本操作，要求达到“熟练掌握”层次。

　　实验步骤 1. 图的邻接表和邻接矩阵存储结构的创建和销毁。

　　2．实现图的基本操作，如查找和遍历等。

　　3．图的应用，如最小生成树、单源最短路径、拓扑排序等。

　　（1）. 图的邻接表和邻接矩阵存储结构的创建和销毁。

　　////////////////////////////////////////////////////////////////// //图是通过文件建立的 //数据元素为 char 类型 //存储结构为邻接表 //文件中第一行为图的类型 //第二行为节点元素，以#结束 //下边每一行为边，和边的权值 //下边是文件的示例 /* 2 A B C D # A B 3 A C 4 B C 2 C D 4 D A 1 # # */ ////////////////////////////////////////////////////////////////// #include<iostream> #include<fstream> using namespace std; const int MaxNum= 20;

　　const int Infinity=-1; typedef char VexType; typedef int ArcType; typedef struct QNode //定义队列节点 { int data; QNode *next; }*LQueuePtr; struct LQueue //定义队列结构体 LQueuePtr front,rear;}; oid QueueInit(LQueue &Q) //队列初始化 { =new QNode; ->next =0; = ;} void Enqueue(LQueue &Q,int e) { LQueuePtr s; s=new QNode; s->data =e; s->next =0; ->next =s; =s;} bool Dequeue(LQueue &Q,int &e) { LQueuePtr p; if( == ) return false; p= ; =p->next ; e= ->data ; delete p; return true;} pedef struct ArcNode //定义边的结构体 {int adjvex; ArcType info; ArcNode *nextarc; }*ArcPtr; struct VexNode //定义节点的结构体 { VexType data; ArcPtr firstarc;}; struct ALGraph //定义图的结构体 { VexNode vexs[MaxNum+1];

　　int kind,vexnum,arcnum;}; int LocateVex(ALGraph &G,VexType v) //在图中找到某一个元素 { int i; for(i= ;i>0&& [i].data !=v;i--); return i;} void CreateGraph(ALGraph &G,char fn[]) //创建图 { int i,j; VexType u,v; ArcPtr p; ifstream f; ArcType w; (fn); //打开文件失败 if(!f) { =0; return; } //读入图的种类 f>> ; //先设置边数为 0 =0; i=0; while(true) //向节点数组中添加节点 { f>>u; if("#"==u) break; i++; [i].data =u; [i].firstarc =0; } =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==||3== )w=1; else f>>w; ++; p=new ArcNode; p->adjvex =j;

　　p->info =w; p->nextarc =[i].firstarc ; [i].firstarc =p; if( <=2) continue; p=new ArcNode; p->adjvex =i; p->info =w; p->nextarc =[j].firstarc ; [j].firstarc =p; } (); } void OutputGraph(ALGraph &G) //输出图 void DFS(ALGraph &G,int i,bool visited[],void visit(VexType)) //图的名称，当前节点位置，标记数组，访问函数 { int j; ArcPtr p; //访问当前节点 visit( [i].data ); //修改标记值 visited[i]=true; for(p=[i].firstarc ;p;p=p->nextarc ) { j=p->adjvex ; if(!visited[j]) //对下一个节点递归 DFS(G,j,visited,visit); }} void DFSTraverse(ALGraph &G,void visit(VexType)) { int i; bool visited[MaxNum+1]; for(i=1;i<= ;i++) //初始化标记数组 { visited[i]=false; }for(i=1;i<= ;i++) { if(!visited[i]) {DFS(G,i,visited,visit); } }} void BFSTraverse(ALGraph &G,void visit(VexType)) { //访问节点 visit([v].data ); visited[v]=true; //将访问的节点入队 Enqueue(q,v); while(Dequeue(q,u)) //出队并访问 { for(p=[u].firstarc ;p;p=p->nextarc )

　　{ w=p->adjvex ; if(!visited[w]) {visit([w].data ); visited[w]=true; Enqueue(q,w); } }} }} int main() {ALGraph G; CreateGraph(G,""); cout<<"创建的图为:"; OutputGraph(G); cout<<"深度优先遍历："<<endl; DFSTraverse(G,visit); cout<<endl<<"广度优先遍历"<<endl; BFSTraverse(G,visit); cout<<endl; return 0; } 2．实现图的基本操作，如查找和遍历等 #include<> #include<> struct graph {char tnode; char hnode; double quanzhi; }gr[100]; char node[50]=" "; double graphshu[50][50]; int mini(int t,int n) printf("用普里姆算法得出的结果是:\n"); printf("路径为："); int t2=0; for(k=0;k<n-1;k++) { int t1=mini(t2,n); sum=sum+graphshu[t2][t1]; for(int i=0;i<n;i++) graphshu[i][t2]=; graphshu[t2][t1]=; 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); }void Kruscal(int k,int n)

　　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=; 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;} } int p,o=1; for(int j=0;j<k;j++)//n 为顶点数 { for(int t=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(int t=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(int i=0;i<n;i++) for(int j=0;j<n;j++) graphshu[i][j]=; for(i=0;i<k;i++)//构造数组 { for(int j=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(int j=i;j<n;j++) graphshu[j][i]=graphshu[i][j]; // prim(k,n); char option; int x; 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 之间有一条边，我们表示为“i j”。例如图一就可以表示为：

　　1 3 2 4 3 4 3 5 输入样例 1：

　　5 3 2 1 1 1 输出样例 1：

　　Yes! 1 3 2 4 3 4 3 5 输入样例 2：

　　No! 说明：若连接结点之间的边可以不止一条，这样的图称为多重图。一个结点如果有指向自己的边，这条边被称为自环。无向简单图是指无自环的非多重图。

　　3．图的应用，如最小生成树、单源最短路径、拓扑排序等 /*已调试成功前半部分(yes/no)*/ #include<> #define NMAX 100 int main( ) { static a[NMAX][NMAX]; int top[NMAX]; int tops,i,temp,s=0,s1=0; scanf("%d",&tops); if(tops>NMAX) { fprintf(stderr,"too many vertax...\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"); return 1; } printf("Yes!\n"); /* waiting...*/ return 0; }

　　实验 6 散列表 的应用 实验目的 (1)掌握散列查找的基本思想； (2)掌握闭散列表的构造方法； (3)掌握线性探测处理冲突的方法； (4)掌握散列技术的查找性能。

　　实验要求 (1)了解 散列表存储结构的创建和销毁。

　　(2)了解实现散列表的基本操作，如插入、删除和查找等。

　　(3)解决散列冲突方法的应用，如开放地址法和链地址法等。

　　实验步骤 散列表由固定数目的散列表元组成。散列表元或是空，或是包含有与某个关键字相关联的数据。为了找到某个关键字值的数据，就要通过散列函数作用于关键字值来计算出散列表元数。对于某一个给定关键字的值，散列函数总是产生出相同的散列表元数。

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

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

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

　　Frank An(WindSor,Ontario,Canada)写了一个简单的算法，代码如下：

　　#include <iostream> #include <> using namespace std; enum HashKeyType { KEY_STRING, KEY_INT, KEY_LONG, KEY_USER1, KEY_USER2,

　　KEY_USER3, KEY_USER4 }; //定义 1 struct HashEntryBase { HashEntryBase *Prev; HashEntryBase *Next; HashEntryBase(); virtual HashKeyType GetKeyType() const =0; virtual size_t Hash(size_t buckets) const =0; virtual int KeyEquals(const HashEntryBase *entry) const=0; }; //定义 2 struct HashEntryInt:public HashEntryBase { int Key; HashEntryInt(const int &k); HashEntryInt(const HashEntryInt &e); virtual HashKeyType GetKeyType() const; virtual size_t Hash(size_t buckets) const; virtual int KeyEquals(const HashEntryBase *entry) const; protected: HashEntryInt(); }; struct HashEntryIntDB:public HashEntryInt { int data; HashEntryIntDB(const int &k, const int &db):HashEntryInt(k) { data = db; } }; struct HashEntryStr:public HashEntryBase { string Key; HashEntryStr(const string &k); HashEntryStr(const HashEntryStr &e); virtual HashKeyType GetKeyType() const; virtual size_t Hash(size_t buckets) const;

　　virtual int KeyEquals(const HashEntryBase *entry) const; protected: HashEntryStr(); }; struct HashEntryStrDB:public HashEntryStr { string data; HashEntryStrDB(const string &k, const string &db):HashEntryStr(k) { data = db; } }; //定义 3 class HashBucker; //定义 4 class HashTableBase { public: HashTableBase(size_t buckets); ~HashTableBase(); protected: bool AddEntry(HashEntryBase *newe); bool DelEntry(const HashEntryBase *dele); bool IsDupe(const HashEntryBase *dupe); const HashEntryBase * FindEntry(const HashEntryBase *find); virtual bool TravCallback(const HashEntryBase *e)const=0; bool Traverse(); size_t NoOfBuckets; HashBucker **Table; }; typedef bool(HashTableBase:: *HashTravFunc)(const HashEntryBase *e) const; //定义 3 class HashBucker { public: HashBucker(); ~HashBucker(); bool AddEntry(HashEntryBase *newe); bool DelEntry(const HashEntryBase *dele); bool IsDupe(const HashEntryBase *dupe);

　　const HashEntryBase * FindEntry(const HashEntryBase *find); bool Traverse(const HashTableBase &table, HashTravFunc func); protected: HashEntryBase *First; }; //定义 5 typedef bool (*HashEnumFuncIntDB)(const int &k, const int &db); class HashTableIntDB: private HashTableBase { public: HashTableIntDB(size_t buckets):HashTableBase(buckets){}; bool Insert(const int &key, const int &db); bool Delete(const int &dele); int LookUp(const int &key); bool Enumerate(HashEnumFuncIntDB func); protected: virtual bool TravCallback(const HashEntryBase *e) const; HashEnumFuncIntDB EnumCallBack; }; typedef bool (*HashEnumFuncStrDB)(const string &k, const string &db); class HashTableStrDB: private HashTableBase { public: HashTableStrDB(size_t buckets):HashTableBase(buckets){}; bool Insert(const string &key, const string &db); bool Delete(const string &dele); string LookUp(const string &key); bool Enumerate(HashEnumFuncStrDB func); protected: virtual bool TravCallback(const HashEntryBase *e) const; HashEnumFuncStrDB EnumCallBack; }; //实现 1 inline HashEntryBase::HashEntryBase() { Prev=NULL; Next=NULL; } //实现 2 inline HashEntryInt::HashEntryInt()

　　{ } inline HashEntryInt::HashEntryInt(const int &k):Key(k) { } inline HashEntryInt::HashEntryInt(const HashEntryInt &e):Key() { } HashKeyType HashEntryInt::GetKeyType() const { return KEY_INT; } int HashEntryInt::KeyEquals(const HashEntryBase *entry) const { if(KEY_INT!=entry->GetKeyType()) printf("mismatched types.\n"); return (Key==((const HashEntryInt *)entry)->Key); } size_t HashEntryInt::Hash(size_t buckets) const { return size_t(Key%(unsigned long)buckets); } inline HashEntryStr::HashEntryStr() { } inline HashEntryStr::HashEntryStr(const string &k):Key(k) { } inline HashEntryStr::HashEntryStr(const HashEntryStr &e):Key() { } HashKeyType HashEntryStr::GetKeyType() const { return KEY_STRING; } int HashEntryStr::KeyEquals(const HashEntryBase *entry) const { if(KEY_STRING!=entry->GetKeyType()) printf("mismatched types.\n"); return (Key==((const HashEntryStr *)entry)->Key); } size_t HashEntryStr::Hash(size_t buckets) const

　　验 实验 7 排序 的应用 实验目的 （1）掌握查找的不同方法，并能用高级语言实现查找算法。

　　（2）熟练掌握顺序表和有序表的顺序查找和二分查找方法。

　　（3）掌握排序的不同方法，并能用高级语言实现排序算法。

　　（4）熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现 实验要求 (1）深化理解书本上的理论知识，将书本的知识变“活”（为已掌握，为已活用）； (2）理论和实践相结合，学会将相关的数据结构和算法应用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。

　　实验步骤 输入：一个包含 n 个正整数的文件，每个正整数小于 n,n 等于 10 的 7 次方（一千万）。并且文件内的正整数没有重复和关联数据。

　　输出: 输入整数的升序排列 约束：

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

　　阶段 1：初始化一个空集合 for i=[0,n) bit[i]=0; 阶段 2：读入数据 i，并设置 bit[i]=1 for each i in the input file bit[i]=1; 阶段 3：输出 排序的结果 for i=[0,n) if bit[i]==1 write i on the output file 算法的时间复杂度为 O(N) #include <> #define WORD 32 #define SHIFT 5 #define MASK 0x1F #define N

　　int bitmap[1 + N / WORD]; /* * 置位函数——用"|"操作符,i&MASK 相当于 mod 操作 * m mod n 运算，当 n = 2 的 X 次幂的时候,m mod n = m&(n-1) */ void set (int i) { bitmap[i>>SHIFT] |= (1 << (i&MASK)); } /* 清除位操作，用&~操作符 */ void clear (int i) { bitmap[i>>SHIFT] &= ~(1...

　　数据结构实验

　　数据结构实习

　　《数据结构》实验题

　　数据结构实习报告

　　大数据应用初探与实践

《算法与数据结构（实践）》(数据结构与算法导论)相关文章：