哈希表的c语言操作

哈希表设计-数据结构课程设计

实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C 语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include #include//time用到的头文件 #include//随机数用到的头文件 #include//toascii()用到的头文件 #include//查找姓名时比较用的头文件 #define HASH_LEN 50//哈希表的长度 #define P 47//小于哈希表长度的P #define NAME_LEN 30//姓名表的长度 typedef struct {//姓名表 char *py; //名字的拼音 int m; //拼音所对应的 }NAME; NAME NameTable[HASH_LEN]; //全局定义姓名表 typedef struct {//哈希表 char *py; //名字的拼音

汉诺塔栈c语言

计算机科学与工程学院 《算法与数据结构》试验报告[二] 专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼 学生姓名肖宇博试验时间2012-4-14 试验项目算法与数据结构 试验类别基础性（）设计性（）综合性（√）其它（） 试验目的及要求（1）掌握栈的特点及其存储方法；（2）掌握栈的常见算法以及程序实现；（3）了解递归的工作过程。 成 绩评定表 类别评分标准分值得分合计 上机表现积极出勤、遵守纪律 主动完成设计任务 30分 程序与报告程序代码规范、功能正确 报告详实完整、体现收获 70分 备注： 评阅教师： 日期：年月日

试 验 内 容 一、实验目的和要求 1、实验目的： （1）掌握栈的特点及其存储方法； （2）掌握栈的常见算法以及程序实现； （3）了解递归的工作过程。 2、实验内容 Hanoi 塔问题。（要求4个盘子移动，输出中间结果） 3、实验要求： 要求实现4个盘子的移动，用递归和栈实现。 二、设计分析 三个盘子Hanoi 求解示意图如下： 三个盘子汉诺塔算法的运行轨迹： B A B C A B C A C A B C (a (b) (c (d) ⑸ ⑼ ⑶ Hanio(3,A,B,C) Hanio(3,A,B,C) Hanio(2,A,C,B) Hanio(2,A,C,B) Hanio(1,A,B,C) Hanio(1,A,B,C) Move (A,C) Move (A,B) Hanio(1,C,A,B) Hanio(1,C,A,B) Move (C,B) Move (A,B) Hanio(2,B,A,C) Hanio(2,B,A,C) Hanio(1,B,C,A) Hanio(1,B,C,A) Move (B,C) Hanio(1,A,B,C) Hanio(1,A,B,C) Move (A,C) Move (B,A) 递归第一层 递归第二层 递归第三层 ⑴ ⑵ ⑷ ⑹ ⑺ ⑻ ⑽ ⑾ ⑿ ⒀ ⒁

ii.c语言本质26链表、二叉树和哈希表3哈希表

第 26 章链表、二叉树和哈希表 3. 哈希表 下图示意了哈希表（Hash Table）这种数据结构。 图 26.12. 哈希表 如上图所示，首先分配一个指针数组，数组的每个元素是一个链表的头指针，每个链表称为一个槽（Slot）。哪个数据应该放入哪个槽中由哈希函数决定，在这个例子中我们简单地选取哈希函数h(x) = x % 11，这样任意数据x都可以映射成0~10之间的一个数，就是槽的编号，将数据放入某个槽的操作就是链表的插入操作。 如果每个槽里至多只有一个数据，可以想像这种情况下search、insert和delete 操作的时间复杂度都是O(1)，但有时会有多个数据被哈希函数映射到同一个槽中，这称为碰撞（Collision），设计一个好的哈希函数可以把数据比较均匀地分布到各个槽中，尽量避免碰撞。如果能把n个数据比较均匀地分布到m个槽中，每个糟里约有n/m个数据，则search、insert和delete和操作的时间复杂度都是O(n/m)，如果n和m的比是常数，则时间复杂度仍然是O(1)。一般来说，要处理的数据越多，构造哈希表时分配的槽也应该越多，所以n和m成正比这个假设是成立的。

请读者自己编写程序构造这样一个哈希表，并实现search、insert和delete 操作。 如果用我们学过的各种数据结构来表示n个数据的集合，下表是search、insert 和delete操作在平均情况下的时间复杂度比较。 表 26.1. 各种数据结构的search、insert和delete操作在平均情况下的时间复杂度比较 数据结构search insert delete O(n)，有序数组折半查找是O(lgn)O(n)O(n) 数组 双向链表O(n)O(1)O(1) 排序二叉树O(lgn)O(lgn)O(lgn) 哈希表（n与槽数m成正比）O(1)O(1)O(1) 习题 1、统计一个文本文件中每个单词的出现次数，然后按出现次数排序并打印输出。单词由连续的英文字母组成，不区分大小写。 2、实现一个函数求两个数组的交集：size_t intersect(const int a[], size_t nmema, const int b[], size_t nmemb, int c[], size_t nmemc);。数组元素是32位int型的。数组a有nmema个元素且各不相同，数组b有nmemb个元素且各不相同。要求找出数组a和数组b的交集保存到数组c中，nmemc是数组c 的最大长度，返回值表示交集中实际有多少个元素，如果交集中实际的元素数量超过了nmemc则返回nmemc个元素。数组a和数组b的元素数量可能会很大（比如上百万个），需要设计尽可能快的算法。

利用栈实现c语言计算器

栈的应用：C实现简单计算器（表达式的计算） 作为栈的著名应用，表达式的计算可以用下面方法实现： 首先建立两个栈，操作数栈NUM_S和运算符栈OPR_S。 其中，操作数栈用来存储表达式中的操作数；运算符栈用来存储表达式中的运算符。可以用字符‘=’来表示表达式结束符。 自左至右的扫描待处理的表达式，并假设当前扫描到的符号为W，根据不同的符号W 做如下不同的处理： 1.若W为操作数，则将W压入操作数栈NUM_S，且继续扫描下一个字符； 2.若W为运算符，则根据运算符的性质做相应的处理： （0）若符号栈为空，无条件入栈当前指针指向的字符 （1）若w为不大于运算符栈栈顶的运算符，则从操作数栈NUM_S中弹出两个操作数，设先后弹出的操作数为a、b，再从运算符栈 OPR_S中弹出一个运算符，比如为+，然后作运算a+b,并将运算结果压入操作数栈NUM_S。 （2）若w为左括号或者运算符的优先级大于运算符栈栈顶的运算符，则将运算符W 压入运算符栈OPR_S，并继续扫描下一个字符。 （3）若运算符W为右括号，循环操作（设先后弹出的操作数为a、b，再从运算符栈OPR_S中弹出一个运算符，比如为+，然后作运 算a+b, 并将运算结果压入操作数栈NUM_S），直到从运算符栈中弹出第一个左括号。 （4）若运算符W为表达式结束符‘=’，循环操作（设先后弹出的操作数为a、b，再从运算符栈OPR_S中弹出一个运算符，比如为 +，然后作运算a+b, 并将运算结果压入操作数栈NUM_S），直到运算符栈为空为止。此时，操作数栈栈顶元素即为表达式的 值。 ====================================================================== === 举例：计算3+(5-2*3)/4-2= （1）开始栈为空，3入栈，+入栈，（无条件入栈，5入栈，-号优先级比（高，所以-号入栈，2入栈，*优先级比目前栈顶的-号优先级高，所以*入栈，3入栈，接着扫描到）括号，）括号不入栈 | | | | --------- ---------- | 3 | | * | --------- ---------- | 2 | | - |

数据结构课程设计哈希表

数据结构课程设计报告

课题四哈希表查找的设计 1. 任务和功能要求 设哈希表长为20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法。 2. 需求分析 用户输入20个以内的数字存储在哈希表中，并可以在表中查找关键字。3.概要设计 typedef struct { int *key; //关键字 int count; //表长 }HashTable; int creat(HashTable *T) //初始化哈希表 程序调用关系如下： 主函数模块 哈希表初始化模块查询模块 插入模块 4. 详细设计 #include #include

#include #include typedef struct { int *key; //关键字 int count; //表长 }HashTable; int search(HashTable *T,int k) //初始化哈希表 { int a; a=k%13; while(a<20) { if(T->key[a]==k) break; a++; } if(a<20) return a; else return 0; } void insert(HashTable *T,int k) { int i,j; i=search(T,k); if(i!=0) printf(" 关键字已存在于位置%d",i); else { j=k%13; while(j<20) { if(T->key[j]==0) { T->key[j]=k;break; } else j++; } } }

856数据结构(C语言版)试卷

姓名： 报考专业： 准考证号码： 密封线内不要写题 年全国硕士研究生招生考试初试自命题试题科目名称：数据结构（C 语言版） 科目代码：考试时间：3小时 满分 150 分 可使用的常用工具：√无 □计算器 □直尺 □圆规（请在使用工具前打√）所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 小题，每小题2分，共20分) （最多元素为MaxSize ）为空时，其栈顶指针top 栈满的条件是（ ）。 ST.top != -1 B ）ST.top == -1 ST.top != MaxSize – 1 D ）ST.top == MaxSize –是结点 p 的直接前趋，若在 q 与 p 之间插入结点

9. 在Hash函数H(k)=k MOD m中，一般来讲m应取（）。 A）奇数 B）偶数 C）素数 D）充分大的数 10.用二分插入排序法进行排序，被排序的表应采用的数据结构是（）。 A）数组 B）单链表 C）双向链表 D）散列表 二、填空题(共10小题，每小题2分，共20分) 1. 一个栈的入栈序列为1,2,3,…,n，其出栈序列是p1,p2,p3,…,pn。若p2 = 3， 则p3可能取值的个数是（）。 2. 已知单链表A长度为m，单链表B长度为n，若将B连接在A的末尾，在没有链 尾指针的情形下，算法的时间复杂度应为（）。 3. 从一个具有n个结点的有序单链表中查找其值等于x的结点时，在查找成功的 情况下，需要平均比较（）个结点。 4. 对于一个有N个结点、K条边的森林，共有（）棵树。 5. 若以｛4，5，6，3，8｝作为叶子节点的权值构造哈夫曼树，则带权路径长度是 （）。 6. 有向图包含5个顶点（编号从1到5）6条弧（<1,2>,<1,5>,<1,3>,<2,3>, <3,4><5,4>）。该图进行拓扑排序，可以得到（）个拓扑序列。 7. 对于一个有向图，若一个顶点的入度为k1,出度为k2，则对应邻接表中该顶点 邻接点单链表中的结点数为（）。 8. 设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32， 13，49，24，38，21，4，12）按线性探测法解决冲突的方法构造哈希表，则该哈希表等概率下查找成功的平均查找长度为（）。 9. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为（）。 10. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元 素进行比较，将其放入已排序序列的正确位置上的方法称为（）。 三、判断题(对的答√错的答×，共10小题，每小题2分，共20分) 1. 不论是入队列还是入栈，在顺序存储结构上都需要考虑“溢出”情况。 2. 在顺序表中取出第i个元素所花费的时间与i成正比。 3. 线性表的插入、删除总是伴随着大量数据的移动。 4. 二叉树通常有顺序存储结构和链式存储结构。 5. 对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一 定不小于下一层任一结点的权值。 6. Prim 算法通过每步添加一条边及相连顶点到一棵树，从而生成最小生成树。 7. 用邻接矩阵存储图，占用的存储空间只与图中结点数有关，而与边数无关。 8. 散列查找主要解决的问题是找一个好的散列函数和有效解决冲突的办法。 9. 对长度为10的排好序的表用二分法检索，若检索不成功，至少需比较10次。 10. 对5个不同的数排序至少需要比较4次。 四、综合应用题(第1小题15分，第2，3，4小题各10分，共45分) 1. 分别给出在先序线索二叉树、中序线索二叉树和后序线索二叉树中结点p的直 接后继结点所在位置。 线索二叉树中结点的结构包括数据域data、左孩子域left、右孩子域right、

该程序实现的哈希表构造哈希函数的方法为除留余数法(

一、该程序实现的哈希表：构造哈希函数的方法为除留余数法(函数modhash)，处理哈希冲突的方法为链地址法。 二、对哈希表的操作：插入（函数hash_table_insert）、移除（函数hash_table_remove）、 查找（函数hash_table_lookup）、整个哈希表的释放（函数hash_table_delete）、 整个哈希表的输出（函数hash_table_print）。 三、哈希表的最大长度可以由HASHMAXLEN设置（我设为1000）。 四、输入哈希表的名称拼音字符是长度为10—20（长度可由STR_MAX_LEN和STR_MIN_LEN）的小写字母组成。这些名字字符串是我用函数rand_str随机产生的。 五、名称拼音字符（关键字）到关键字值的转换方法：先把名称的拼音字符转换对应的ASCII，累加后作为关键字值。我是用函数str_to_key实现的。 六、异常情况包括： 1、在对哈希表进行插入操作时，若哈希表的实际长度超过了哈希表的最大长度，我就输出“out of hash table memory!”，然后直接跳出插入子函数，不进行插入操作。 2、在对哈希表进行插入操作时，若插入的元素在哈希表中已经存在，我就输出“******already exists !”，然后直接跳出插入子函数，不进行插入操作。 3、在对哈希表进行查找操作时，若查到则返回其地址，若没查到则返回空地址。 4、在对哈希表进行移除操作时，对同义词元素的删除，分为表头和表中两种情况处理。 七、开发平台：DEV-C++，用c语言实现。 在哈希表程序中我比较注重整个代码风格，希望能形成很好的代码风格！如果有什么可以改进的，希望老师能跟我说说！

c语言课程设计--汉诺塔

课程设计报告 课程设计名称：C语言课程设计 课程设计题目：汉诺塔问题求解演示 院（系）：计算机学院 专业：计算机科学与技术 班级： 学号： 姓名： 指导教师： 完成时间：2010年3月18日

沈阳航空航天大学课程设计报告 目录 第1章需求分析 (3) 1.1 课程设计的题目及要求 (3) 1.2 总体分析 (3) 第2章系统设计 (4) 2.1 主要函数和函数功能描述 (4) 2.2 功能模块图 (4) 第3章详细设计 (5) 3.1主函数流程图 (5) 3.2各功能模块具体流程图 (6) 第4章调试分析 (10) 4.1.调试初期 (10) 4.2.调试中期 (10) 4.3.调试后期 (10) 参考文献 (11) 附录 (12)

第1章需求分析 1.1 课程设计的题目及要求 题目：汉诺塔问题求解演示 内容： 在屏幕上绘出三根针，其中一根针上放着N个从大到小的盘子。要求将这些盘子从这根针经过一个过渡的针移到另外一根针上，移动的过程中大盘子不能压在小盘子上面，且一次只能移动一个盘子。要求形象直观地演示盘子移动的方案和过程。 要求： 1）独立完成系统的设计，编码和调试。 2）系统利用C语言实现。 3）安照课程设计规范书写课程设计报告。 4）熟练掌握基本的调试方法，并将程序调试通过 1.2总体分析 本题目需要使用C语言绘制图形，所以需要turbo C，需要绘图函数，而汉诺塔的函数属于经典的函数，在书本上都学习过，所以这个题目的难点在于需要绘制汉诺塔图形。攻克这一点其他的问题都迎刃而解。但是我个人以前也没有学过一些关于turboC 方面的知识。所以我将重点放在了对#include下的一系列绘图函数的研究与应用,对屏幕上的图像坐标分析是一个难点。其中用到了graphics.h头文件中的bar, outtextxy, setfillstyle，closegraph函数。进行了画图（利用bar函数进行画框的操作），填充颜色（利用setfillstyle函数填充白色和黑色，以分辨图形与图形背景），在特定位置输出特定字符等操作（利用outtextxy函数）。

哈希表的设计与实现-数据结构与算法课程设计报告

合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程数据结构与算法 课程设计名称哈希表的设计与实现 学生姓名王东东 学号0804012030 专业班级08计本（2) 指导教师王昆仑、李贯虹 2010 年5 月

课程设计目的 “数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一， 是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到 理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和 数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并 用软件解决问题，培养良好的程序设计技能。 一、问题分析和任务定义 1、问题分析 要完成如下要求：设计哈希表实现电话号码查询系统。 实现本程序需要解决以下几个问题： （1）如何定义一个包括电话号码、用户名、地址的节点。 （2）如何以电话号码和用户名为关键字建立哈希表。 （3）用什么方法解决冲突。 （4）如何查找并显示给定电话号码的记录。 （5）如何查找并显示给定用户名的记录。 2 任务定义 1、由问题分析知，本设计要求分别以电话号码和用户名为关键字建立哈希表，z在此基 础上实现查找功能。本实验是要我们分析怎么样很好的解决散列问题，从而建立一比较合理 的哈希表。由于长度无法确定，并且如果采用线性探测法散列算法，删除结点会引起“信息 丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，可以使 用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。 根据问题分析，我们可以定义有3个域的节点，这三个域分别为电话号码char num[30]，姓名char name[30]，地址char address[30]。这种类型的每个节点对应链表中的每个节点，其中电话号码和姓名可分别作关键字实现哈希表的创建。 二、数据结构的选择和概要设计 1、数据结构的选择 数据结构：散列结构。 散列结构是使用散列函数建立数据结点关键词与存储地址之间的对应关系，并提供多 种当数据结点存储地址发生“冲突”时的处理方法而建立的一种数据结构。 散列结构基本思想，是以所需存储的结点中的关键词作为自变量，通过某种确定的函 数H（称作散列函数或者哈希函数）进行计算，把求出的函数值作为该结点的存储地址，并 将该结点或结点地址的关键字存储在这个地址中。 散列结构法（简称散列法）通过在结点的存储地址和关键字之间建立某种确定的函数 关系H，使得每个结点（或关键字）都有一个唯一的存储地址相对应。 当需要查找某一指定关键词的结点时，可以很方便地根据待查关键字K计算出对应的“映像”H(K)，即结点的存储地址。从而一次存取便能得到待查结点，不再需要进行若干次的 比较运算，而可以通过关键词直接计算出该结点的所在位置。

C语言 栈的使用

C语言栈的使用 #include #include #define TRUE 1 #define FALSE 0 #define MAXSIZE 100 #define ERROR 0 typedef int Elemtype; typedef struct { Elemtype data[MAXSIZE]; int top; }SqStack; void InitStack(SqStack *s) {s->top=-1; } int StackEmpty(SqStack *s) { return(s->top==-1?TRUE:FALSE); } int StackFull(SqStack *s) { return(s->top==MAXSIZE-1?TRUE:FALSE);} int Push(SqStack *s,Elemtype e) { if (StackFull(s)) return ERROR; s->top++; s->data[s->top]=e; } int Pop(SqStack *s,Elemtype &e) { if (StackEmpty (s)) return ERROR; e=s->data[s->top]; s->top--; } void Conversion(int N,int r) { SqStack s; int e; InitStack(&s);

while(N!=0) {Push (&s,N%r); N=N/r; } while(!StackEmpty(&s)) { Pop(&s,e); cout<>N; cin>>r; Conversion(N,r); }

利用哈希技术统计C源程序关键字出现频度

：利用哈希技术统计C源程序关键字出现频度 目录一．需求分析说明 (3) 二．总体设计 (3) 三．详细设计 (4) 四．实现部分 (5) 五．程序测试 (10) 六．总结 (11)

一、需求分析说明 1.课程设计目的 本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 2.题目要求 1)题目内容： 利用Hash技术统计某个C源程序中的关键字出现的频度 2)基本要求： 扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为： Hash(key)[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41 二、总体设计 一．算法思想描述 首先读取关键字文件以建立二叉排序树以供后续查询，每个树节点保存一个关键字字符串及指向左右子树的指针。同时创建一Hash表，每个节点除应保存关键字字符串外，还应保存关键字频数及该存储单元冲突次数。然后扫描一个C源程序，每次扫描一行，从中循环分离出每个单词，每次均查找其是否为关键字，若是，则按计算公式计算其KEY值并在Hash表中进行相应操作，若该节点为空则插入否者比较其是否与现有关键字相同，若相

同则增加其频数，否则增加其冲突次数并继续线性探测下一个存储单元，完了继续操作下一个分离出来的单词，如此循环运行直至扫描结束。编写本程序时，使用了二叉树创建、二叉树查找、Hash表的建立和操作及文件操作等基本算法。 二．三、详细设计 (程序结构 //Hash表存储结构 typedef struct node //定义 { char s[20]; int num,time; //num为频数，time为冲突次数 }node; //二叉排序树结构定义 typedef struct nod //定义 { char s[20]; struct nod *left,*right; }nod; int max;//max为Hash表长度

栈的基本操作c语言

#include #include #include //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //Status 是函数的类型，其值是函数结果状态代码 typedef int Status; typedef int SetElemType; typedef SetElemType ElemType; #include "tou.h" #include #include typedef char SElemType; // 栈的元素类型 #define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量 // 栈的顺序存储表示P46 typedef struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈 // 构造一个空栈S。 int InitStack(SqStack *S) { // 为栈底分配一个指定大小的存储空间 (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if( !(*S).base ) exit(OVERFLOW); // 存储分配失败 (*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈

哈希查找算法的源代码 c语言

哈希查找算法的源代码 c语言 【问题描述】 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 [基本要求] 假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。 [测试数据] 读取熟悉的30个人的姓名。 #include #include #include using namespace std; #define Maxsize 57 struct record { char name[20]; char tel[20]; char add[20]; }; typedef record * precord; struct HashTable { int elem[Maxsize]; //存放数组a[]的下标 int count; }; typedef HashTable * pHashTable; int Number; //统计当前数组a[]中的记录总数 void Getdata(precord a) //从文件telphone.txt中读取数据存放到数组a[] { Number=0; ifstream infile("telphone.txt",ios::in|ios::binary); if(!infile) {cout<<"文件打开失败!\n"; exit(1);} while(!infile.eof() && infile.get()!=EOF) //文件不为空并且文件指针没有指到结束符 {infile.seekg(Number*sizeof(a[Number]),ios::beg); //定位文件指针infile.read((char *)&a[Number],sizeof(a[Number])); Number++;

汉诺塔非递归算法C语言实现

汉诺塔非递归算法C语言实现 #include #include #define CSZL 10 #define FPZL 10 typedef struct hanoi { int n; char x,y,z; }hanoi; typedef struct Stack { hanoi *base,*top; int stacksize; }Stack; int InitStack(Stack *S) { S->base=(hanoi *)malloc(CSZL*sizeof(hanoi)); if(!S->base) return 0; S->top=S->base; S->stacksize=CSZL; return 1; } int PushStack(Stack *S,int n,char x,char y,char z) { if(S->top-S->base==S->stacksize) { S->base=(hanoi *)realloc(S->base,(S->stacksize+FPZL)*sizeof(hanoi)); if(!S->base) return 0; S->top=S->base+S->stacksize; S->stacksize+=FPZL; } S->top->n=n; S->top->x=x; S->top->y=y; S->top->z=z; S->top++; return 1; } int PopStack(Stack *S,int *n,char *x,char *y,char *z) { if(S->top==S->base)

c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课设报告

目录 题目一.二叉树操作（1）二.算术表达式求 (1) 一、课程设计的目的 (1) 二、课程设计的内容和要求 (1) 三、题目一设计过程 (2) 四、题目二设计过程 (6) 五、设计总结 (17) 六、参考文献 (18)

题目一.二叉树操作（1）二.算术表达式求 一、课程设计的目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。 （1）题目一的目的： 1、掌握二叉树的概念和性质 2、掌握二叉树的存储结构 3、掌握二叉树的基本操作 （2）题目二的目的： 1、掌握栈的顺序存储结构和链式存储结构 2、掌握栈的先进后出的特点 3、掌握栈的基本运算 二、课程设计的内容和要求 （1）题目一的内容和要求： 1、编写已知二叉树的先序、中序序列，恢复此二叉树的程序 2、编写求二叉树深度的程序 （2）题目二的内容和要求： 1、算术表达式由操作数、运算符和界限符组成。操作数是正整数，运算符为 加减乘除，界限符有左右括号和表达式起始 2、将一个表达式的中缀形式转化为相应的后缀形式 3、依据后缀表达式计算表达式的值

三、题目一设计过程 1、题目分析 现已知一棵二叉树的先序遍历序列和中序遍历序列，依次从先序遍历序列中取结点，由先序序列确定根结点(就是第一个字母)，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕（树用链式存储结构存储），用递归实现！ 由建好的二叉树，先判断这棵树是否为空，若不为空则找数的左子树，统计它的高度，然后找树的右子树，统计它的高度，比较左子树和右子树的高度，然后返回其中大的那个值加一，则求出数的高度。这里用递归实现！ 2、算法描述 main ( )（主函数） 先构造一颗二叉树，初始化为空，用来存储所构造的二叉树，并输入一棵树的先序序列和中序序列，并统计这个序列的长度。然后调用实现功能的函数。 void CreateBiTree(BiTree *T,char *pre,char *in,int len)（由先序序列和中序序列构造二叉树） 根据前序遍历的特点, 知前序序列(pre)的首个元素(pre[0])为根(root), 然后在中序序列(in)中查找此根(pre[0]), 根据中序遍历特点, 知在查找到的根(root) 前边的序列为左子树, 后边的序列为右子树。设根前边有n个元素，则又有, 在前序序列中，紧跟着根(root)的n个元素序列(即pre[1...n]) 为左子树, 在后边的为右子树，而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为pre[1...n]), 中序序列为in[0...n-1], 分别为原序列的子串, 构造右子树同样。这里用递归实现！ int Depth(BiTree T)（求树的深度） 当所给的参数T是NULL时，返回0。说明这个树只有一个叶子节点深度为0，当所给的参数不是NULL时，函数调用自己看看这个参数的左分支是不是NULL，

数据结构哈希表实验报告

HUNAN UNIVERSITY 课程实习报告 题目: 哈希表 学生姓名唐鹏 学生学号 2 专业班级物联2班 指导老师吴帆 完成日期2014年4月2日

一、需求分析: 1.本程序来自于图书馆靠书名来检索想要查找的书问题。 2.本程序要求: (1)根据输入建立图书名称表,采用创建散列表实现。 (2)建散列表后,如果想要查找的数据在散列表中输出yes否则输出no。 二、哈希表简介 结构中存在关键字与K相等的记录,则必定存储在f(K)的位置上。由此,不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hash function),按这个思想建立的表为散列表。 * 对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。 * 综上所述,根据散列函数H(key)与处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象”, 作为这条记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址。这个现象也叫散列桶,在散列桶中,只能通过顺序的方式来查找,一般只需要查找三次就可以找到。科学家计算过,当负载因子(load factor)不超过75%,查找效率最高。 * 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率就是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。 程序设计流程 程序思想 (一)哈希函数unsigned int hash_BKDE(char *str)生成映射地址,成为散列表的编 号。 (二)哈希表HashTable::HashTable()通过数组储存元素 (三)插入函数void HashTable::insert(char*c)插入字符串,先计算要插入字符串生 成的映射地址,然后在相应的地址插入,如果没有空位查找空位插入。(四)查找函数bool HashTable::find(char*c)进行查找,先计算要生成字符串的地 址,再到散列表中进行查找比较。 (五)主函数main() 1)输入:输入散列表内容与要查找的数据个数与数据

汉诺塔程序实验报告

实验题目： Hanoi 塔问题 一、问题描述： 假设有三个分别命名为 A , B 和C 的塔座，在塔座 B 上插有n 个直径大小各不相同、从小到 大编号为1, 2,…，n 的圆盘。现要求将塔座 B 上的n 个圆盘移至塔座 A 上并仍按同样顺序 叠排，圆盘移动时必须遵守以下规则： (1 )每次只能移动一个圆盘； (2)圆盘可以插在 A , B 和C 中任一塔上； ( 3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 要求： 用程序模拟上述问题解决办法,并输出移动的总次数, 圆盘的个数从键盘输入； 并想 办法计算出程序运行的时间。 二、 算法思路： 1 、建立数学模型： 这个问题可用递归法解决,并用数学归纳法又个别得出普遍解法： 假设塔座B 上有3个圆盘移动到塔座 A 上： (1) "将塔座B 上2个圆盘借助塔座 A 移动到塔座C 上; (2) "将塔座B 上1个圆盘移动到塔座 A 上; (3) "将塔座C 上2个圆盘借助塔座 B 移动到塔座A 上。 其中第 2步可以直接实现。第 1步又可用递归方法分解为： 1.1"将塔座B 上1个圆盘从塔座 1.2"将塔座B 上1个圆盘从塔座 1.3"将塔座A 上1个圆盘从塔座 第 3 步可以分解为： 3.1将塔座C 上1个圆盘从塔座 3.2将塔座C 上1个圆盘从塔座 3.3将塔座B 上1个圆盘从塔座 综上所述：可得到移动 3 个圆盘的步骤为 B->A,B->C, A->C, B->A, C->B, C->A, B->A, 2、算法设计： 将n 个圆盘由B 依次移到A , C 作为辅助塔座。当 n=1时，可以直接完成。否则，将塔 座B 顶上的n-1个圆盘借助塔座 A 移动到塔座C 上；然后将圆盘B 上第n 个圆盘移到塔 座A 上；最后将塔座 C 上的n-1个圆盘移到塔座 A 上，并用塔座B 作为辅助塔座。 三、原程序 #include #include #include int times = 0; void move(char a, char b) { printf("%c > %c \n", a,b); } void hno(int n,char a , char b, char c) { if (n==1) { move(a,c); times ++; } X 移动到塔座 A ； X 移动到塔座 C ； Z 移动到塔座 C 。 Y 移动到塔座 Y 移动到塔座 X 移动到塔座 B ； A ；

数据结构实验C语言实现散列表

实验课题：做这个实验时采用Open Addressing框架，也可加做Separate Chaining以形成比较。 1 构造散列表，把字符串数组中的各项加入到散列表中 string MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay", "owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" }; 用C表示，可以是 char * MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay", "owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" }; 为便于观察冲突现象，初始构造散列表时，表的容量不要过大，对Open Addressing，装载因子为0.5左右，对于Separate Chaining，装载因子为1左右即可。也不要做rehash（应该改源代码的哪里，如何改）。 建议对源代码做些改动、增加一些输出（建议用条件编译控制这些输出），以便于观察冲突的发生和解决； 对于Open Addressing，参考代码的冲突解决方案是用的平方探测（quadratic probing），如果用线性探测（linear probing）的策略，应该对函数findPos做什么修改（冲突解决的策略都集中在那里） #include #include #include "hashquad.h" #include #define MinTableSize 26 typedef unsigned int Index; typedef Index Position; struct HashTbl; typedef struct HashTbl *HashTable; enum KindOfEntry { Legitimate, Empty, Deleted }; struct HashEntry { char *Element; enum KindOfEntry Info; }; typedef struct HashEntry Cell; struct HashTbl { int TableSize; Cell *TheCells; }; static int NextPrime( int N ) { int i;

数据结构(C语言)栈的基本操作

实验名称栈的基本操作 实验目的 掌握栈这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序栈或链式栈，并完成下列操作： （1）初始化栈； （2）判栈为空； （3）出栈； （4）入栈。 算法设计分析 （一）数据结构的定义 struct stackNode{ int data; struct stackNode *nextPtr; }; typedef struct stackNode listStact; typedef listStact *stackNodePtr; （二）总体设计 程序由主函数、入栈函数，出栈函数，删除函数判官是否为空函数和菜单函数组成。 （1）主函数：调用各个函数以实现相应功能

（三）各函数的详细设计： Function1: void instruct() //菜单 （1）：使用菜单显示要进行的函数功能； Function2：void printStack(stackNodePtr sPtr) //输出栈 （1）：利用if判断栈是否为空； （2）：在else内套用while（头指针不为空条件循环）循环输出栈元素； Function3：void push(stackNodePtr *topPtr,int value //进栈 （1）：建新的头指针； （2）：申请空间； （3）：利用if判断newPtr不为空时循环进栈 （4）：把输入的value赋值给newPtr，在赋值给topPtr，再指向下一个位置； Function4：int pop(stackNodePtr*topPtr) //删除 （1）：建新的头指针newPtr； （2）：利用if判断newPtr是否为空，再删除元素。 （3）：把topPtr等于newPtr，把头指针指向的数据赋值给topValue，输出要删除的数据值，头指针指向下一个位置，并清空newPtr； （4）：完成上述步骤后，return toPvalue，返回；