链式表
#include
#include
#define LIST_INIT_SIZE 8
#define LISTINCREMENT 2
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef struct
{ int *elem;
int length;
int listsize;
}SqList;
int InitList(SqList *L,int a)//构造一个空的线性表L。
{
(*L).elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!(*L).elem)
exit(OVERFLOW);//存储分配失败
printf("请输入六个数据：\n");
for(int i=0;i scanf("%d",&(*L).elem[i]); (*L).length=a; (*L).listsize=LIST_INIT_SIZE; return OK; }//InitList_Sq int ListInser_Sq(SqList *L,int i,int e) { if(i<1||i>(*L).length+1) return ERROR; if((*L).length>=(*L).listsize) { int *newbase=(int *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(int)); if(!newbase) exit(OVERFLOW); (*L).elem=newbase; (*L).listsize+=LISTINCREMENT; } int *q=&((*L).elem[i-1]); for(int *p=&((*L).elem[(*L).length-1]);p>=q;--p)*(p+1)=*p; *q=e; ++(*L).length; return OK; } int ListDelete_Sq(SqList *L,int i) { int *p,*q,e; if((i<1)||(i>(*L).length))return ERROR; p=&((*L).elem[i-1]); e=*p; q=(*L).elem+(*L).length-1; for(++p;p<=q;++p) *(p-1)=*p; --(*L).length; return OK; } void visit(SqList *L)//输出数据 { int i=0; printf("线性表的数据为："); while(i<(*L).length) { printf("%d ",(*L).elem[i]); i++; } printf("\n"); } void main() { int a=5,i=1,e=2; SqList z,*L=&z; InitList(L,a); ListInser_Sq(L,i,e); visit(L); ListDelete_Sq(L,i); visit(L); } 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验五线性表的链式表示和实现 学生姓名吴奇专业班级信管1204 学号31201403 实验成绩指导老师（签名）日期 一.实验目的和要求 1、掌握线性表的链式存储结构； 2、掌握单链表、循环单链表的一些基本操作实现函数。 二.实验内容 1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表各基本操作的实现函数，把它们存放在头文件LinkList.h中，同时建立一个验证操作实现的主函数文件test2_2.cpp。编译并调试程序，直到正确运行。 2、选做：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc) ，实现将两个带表头附加结点的有序单链表La和Lb合并成一个新的带表头附加结点的有序单链表Lc的功能，要求利用原存储空间。请把该函数添加到头文件LinkList.h中，并在主文件test2_2.cpp中添加相应语句进行测试。 3、填写实验报告，实验报告文件取名为report5.doc。 4、上传实验报告文件report5.doc、源程序文件test2_2.cpp及LinkList.h 到Ftp服务器上自己的文件夹下。 三. 函数的功能说明及算法思路 void initlist(lnode *&hl) 初始化链表 { hl=new lnode; 新建头节点 if(!hl){ cout<<"储存分配失败，按任意键退出系统!!"< 一: 需求分析 (2) 三: 详细设计（含代码分析） (4) 1.程序描述: (4) 2具体步骤 (4) 四调试分析和测试结果 (7) 五，总结 (9) 六.参考文献; (10) 七.致谢 (10) 八.附录 (11) 一: 需求分析 问题描述：设计哈希表实现电话号码查询系统。 基本要求 1、设每个记录有下列数据项：电话号码、用户名、地址 2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； 3、采用再哈希法解决冲突； 4、查找并显示给定电话号码的记录； 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少 两种），考察平均查找长度的变化。 二: 概要设计 进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方法建立哈希表,选2:以再哈希的方法建立哈希表,然后用户输入用户信息,分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,.当添加一定量的用户信息后,用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息.程序用链表的方式存储信息以及构造哈希表。 具体流程图如下所示: 三: 详细设计（含代码分析） 1.程序描述: 本程序以要求使用哈希表为工具快速快速查询学生信息，学生信息包括电话号码、用户名、地址；用结构体存储 struct node { string phone; //电话号码 string name; //姓名 string address;//地址 node *next; //链接下一个地址的指针 }; 2具体步骤 1. 要求主要用在哈希法解决冲突，并且至少尝试用两种方法解决冲突，定义两个指针数组存储信息node *infor_phone[MAX]; node *infor_name[MAX];前者以电话号码为关键字检索哈希表中的信息，后者以姓名为关键字检索哈希表中的信息 用链式法和再哈希法解决冲突： int hash(string key) //以姓名或者电话号码的前四位运算结果作为哈{ //希码 int result=1,cur=0,i; if(key.size()<=4) i=key.size()-1; else i=4; for(;i>=0;i--) { cur=key[i]-'0'; result=result*9+cur; } result%=(MOD); return result; 通讯录管理系统的设计与实现精选文档 TTMS system office room 【TTMS16H-TTMS2A-TTMS8Q8- 大连民族大学 计算机科学与工程学院实验报告 实验题目：1. 学生信息管理系统的设计与实现 2. 暴力算法在旅行商问题中的应用 课程名称：信息系统开发案例 实验类型：□演示性□验证性□操作性□设计性综合性 专业：软件工程班级：144 学生姓名：赵耀学号：30 实验日期：2017年3月6日—4月27日 实验地点：金石滩校区I303机房 实验学时：24学时实验成绩： 指导教师：赵戈 通讯录管理系统的设计与实现 摘要 本项目用C++语言开发了一个简单的通讯录管理系统，该系统能对联系人 信息进行“增删改查”。系统的UI设计基于Windows系统自带的控制台。测试结 果表明该通讯录管理系统可以稳定正确运行，具有较高的可靠性。 关键词：通讯录管理系统；C++语言；Windows 控制台 目录 1.选题的背景和意义 当今时代，计算机已经成为人们生活中不可或缺的一部分，它打破了地域时间限制，改变了人们的工作和生活方式。人们之间的联系越来越便捷，这就使得要经常与很多人保持着联系，而单纯依靠人脑已经很难记住所有人的联系方式还有其各做附加信息。通讯录系统能方便用户的需求，满足用户迅速、准确的查找修改或者删除联系人信息，把各个联系人信息以文件保存。本文介绍了c++编写简易通讯录管理：系统的分析，功能模块的设计，系统的流程图及运行界面。此系统的主要管理的信息由：联系人的姓名、性别、电话号码，加深对c++语言程序设计的理解，提高算法设计的能力，锻炼编程的能力。用c 语言编程一个通讯录管理系统软件，要求能实现通讯录管理系统中的增加信息，删除信息，显示通讯里的所有信息，按名字查询信息，保存通讯录，退出系统。。 2.需求分析 用例图 通讯录管理系统的用例图如下图所示： 实验报告 课程名称：数据结构与算法分析 实验名称：链表的实现与应用 实验日期：班级：数媒1401 姓名：范业嘉学号 08 一、实验目的 掌握线性表的链式存储结构设计与基本操作的实现。 二、实验内容与要求 ⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； ⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用 线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。 ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。 三、数据结构设计 1.按所用指针的类型、个数、方法等的不同，又可分为： 线性链表（单链表） 静态链表 循环链表 双向链表 双向循环链表 2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。 四、算法设计 1.定义一个链表 void creatlist(Linklist &L,int n) { int i; Linklist p,s; L=(Linklist)malloc(sizeof(Lnode)); p=L; L->next=NULL; for(i=0;i 哈希表实现电话号码查询系统 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用 C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。 二需求分析 1、程序的功能 1)读取数据 ①读取原电话本存储的电话信息。 ②读取系统随机新建电话本存储的电话信息。 2)查找信息 ①根据电话号码查询用户信息。 ②根据姓名查询用户信息。 3)存储信息 查询无记录的结果存入记录文档。 2、输出形式 1)数据文件“old.txt”存放原始电话号码数据。 2)数据文件“new.txt”存放有系统随机生成的电话号码文件。 3)数据文件“out.txt”存放未查找到的电话信息。 4)查找到相关信息时显示姓名、地址、电话号码。 3、初步测试计划 1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存 到“new.txt”中。 2)分别采用伪随机探测再散列法和再哈希法解决冲突。 3)根据姓名查找时显示给定姓名用户的记录。 4)根据电话号码查找时显示给定电话号码的用户记录。 5)将没有查找的结果保存到结果文件Out.txt中。 6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。三概要设计 1、子函数功能 int Collision_Random(int key,int i) //伪随机数探量观测再散列法处理冲突 void Init_HashTable_by_name(string name,string phone,string address) //以姓名为关键字建立哈希表 int Collision_Rehash(int key,string str) //再哈希法处理冲突 void Init_HashTable_by_phone(string name,string phone,string address) //以电话号码为关键字建立哈希表 void Outfile(string name,int key) //在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中void Outhash(int key) //输出哈希表中的记录 void Rafile() //随机生成数据，并将数据保存在new.txt void Init_HashTable(char*fname,int n) //建立哈希表 int Search_by_name(string name) //根据姓名查找哈希表中的记录 int Search_by_phone(string phone) //根据电话号码查找哈希表中的记录 课程设计(论文)任务书 软件学院学院软件工程专业班 一、课程设计(论文)题目：通讯录管理系统的设计与实现——哈希表 二、课程设计(论文)工作自2016 年 1 月 4 日起至 2016 年 1 月 10 日止 三、课程设计(论文) 地点: 软件测试中心（北区测试二室） 四、课程设计(论文)内容要求： 1．本课程设计的目的 ⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合课程的理论知识，编写程序求解指定问题； ⑵初步掌握软件开发过程的问题分析、系统设计、编码、测试等基本方法和技能； ⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。 2．课程设计的任务及要求 1）基本要求： ⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告； ⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率； ⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释； ⑷每位同学需提交可独立运行的程序和规范的课程设计报告。 2）课程设计论文编写要求 ⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订； ⑵课程设计报告包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等； ⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。 3）课程设计评分标准： ⑴学习态度：10分； ⑵系统设计：20分； ⑶编程调试：20分； ⑷回答问题：20分； ⑸论文撰写：30分。 重庆交通大学 《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)： B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作）（5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize（最大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 数据结构实验线性表的链式表示和实现（源代码） #include getchar(); p->next=NULL; q->next=p; q=p; i++; } system("cls"); return head; } struct node* clearlist(node *head) { head=NULL; return head; } status destroylist(node *head) { head=NULL; free(head); return OK; } statuslistempty(node *head) { if(head==NULL) return OK; else return ERROR; } statuslistlength(node *head) { inti=0; node *p; p=head->next; while(1) { i++; if(p->next==NULL) break; p=p->next; } 合肥学院 计算机科学与技术系 课程设计报告 2009～2010学年第二学期 课程数据结构与算法 课程设计名称哈希表实现通讯录 题目：（哈希表的设计与实现的问题） 设计哈希表实现电话号码查询系统。设计程序完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户的记录。 一、问题分析和任务定义 此程序需要完成如下要求：设计哈希表实现电话号码查询系统。 实现本程序需要解决以下几个问题： （1）设计结点使该结点包括电话号码、用户名、地址。 （2）利用再哈希法解决冲突。 （3）分别以电话号码和用户名为关键字建立哈希表。 （4）实现查找并显示给定电话号码的记录。 （5）查找并显示给定用户的记录。 本问题的关键和难点在于如何解决散列的问题。由于结点的个数无法的知，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用拉链法，当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。 首先，解决的是定义链表结点，在拉链法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成.name[8] 、num[11]和address[20]都是char浮点型，输入输出都只能是浮点型的。 采用拉链法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函数求出的散列地址。 其次，设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以电话号码和用户名为关键字建立哈希表。所以要分别以用户名、号码为关键字建立两个散列函数， 对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值相加，然后对20求余。 再次，需要实现添加结点的功能，则其中必须包括一个输入结点信息、添加结点的函数；需要实现查找函数，则必须包括一个查找结点的函数；需要对文件进行保存，则必需要包括保存文件函数。还需要包括一个主菜单和一个主函数。 最后，当程序设计出来后的测试数据为： 南昌航空大学实验报告 课程名称：数据结构实验名称：实验二线性表的链式存储结构 班级：学生姓名：冯华华学号：11046213 指导教师评定： XXX 签名: XXX 一、问题描述 1单链表的实现与操作。 2设计一个程序求出约瑟夫环的出列顺序。约瑟夫问题的一种描述是：编号为1，2，…， n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整 数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。 报m的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直到所有人全部出列为止。例如，n=7,7个人的密码依次为： 3,1,7,2,4,8,4,m的初值取6，则正确的出列顺序应为6,1,4,7,2,3,5。要求使用单向循环 链表模拟此出列过程。 二、程序分析 约瑟夫环的大小是变化的，因此相应的结点也是变化的，使用链式存储结构可以动态的 生成其中的结点，出列操作也非常简单。用单向循环链表模拟其出列顺序比较合适。 用结构指针描述每个人： struct Joseph {int num;/*环中某个人的序号*/ int secret;/环中某个人的密码*/ struct Joseph *next;/指向其下一个的指针*/}; 1）初始化约瑟夫环： 调用函数struct Joseph *creat()生成初始约瑟夫环。在该函数中使用head 指向 表头。输入序号为0时结束，指针p1指向的最后结束序号为0的结点没有加入到 链表中，p2 指向最后一个序号为非0 的结点（最后一个结点）。 2）报数出列： 调用函数voil sort(struct Joseph * head,int m)，使用条件p1->next!=p1判断 单向链表非空，使用两个指针变量p1和p2，语句p2=p1;p1=p1->next;移动指针， 计算结点数（报数）；结点p1出列时直接使用语句：p2->next=p1->next，取出该 结点中的密码作为新的循环终值。 三、调试过程及实验结果 最后程序运行结果如下所示： 输入数据：数据格式为序号，密码 输入0，0为结束 1，3↙<回车> 2，1↙<回车> 经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制 实验题目：线性表的链式存储结构和实现 实验室：机房4 设备编号： 09 完成日期： 2012.04.09 一、实验容 1.会定义线性表的链式存储结构。 2.熟悉对单链表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握链式存储结构的特点，掌握并实现单链表的常用的基本算法。 三、实验的容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表链式存储结构的表示及操作。具体实现要求： (2)完成对线性表链式存储结构的表示和实现。 (3)实现对单链表的创建。 (4)实现对单链表的插入和删除操作。 2．概要设计 抽象数据类型线性表的定义：ADT LIST{ 抽象对象：D=｛ai|ai<-Elemset,i=1,2,…,n,n>=0｝ 数据关系：R1=｛ /* （1）设计哈希表，该表应能够容纳50个英文单词。 （2）对该哈希表进行查询，实现对特定单词的快速查询，并显示经过的节点内容 已经发到你邮箱里了enochwills@https://www.wendangku.net/doc/ba4778298.html, */ #include 大连民族大学 计算机科学与工程学院实验报告 实验题目： 1. 学生信息管理系统的设计与实现 2. 暴力算法在旅行商问题中的应用 课程名称：信息系统开发案例 实验类型：□演示性□验证性□操作性□设计性 综合性 专业：软件工程班级：144 学生姓名：赵耀学号：2014082430 实验日期：2017年3月6日—4月27日 实验地点：金石滩校区I303机房 实验学时：24学时实验成绩： 指导教师：赵戈 通讯录管理系统的设计与实现 摘要 本项目用C++语言开发了一个简单的通讯录管理系统，该系统能对联系人信 息进行“增删改查”。系统的UI设计基于Windows系统自带的控制台。测试结 果表明该通讯录管理系统可以稳定正确运行，具有较高的可靠性。 关键词：通讯录管理系统；C++语言；Windows 控制台 目录 1.选题的背景和意义 (3) 2.需求分析 (3) 2.1 用例图 (3) 2.2 用例文本 (4) 3.总体设计 (5) 3.1 通讯录管理系统功能模块图 (5) 3.2 主控main函数执行流程图 (6) 3.3 执行流程图的解释说明 (6) 3.4 存储结构设计 (7) 4.详细设计 (8) 5程序运行结果 (9) 6总结和展望 (9) 7附录 (10) 程序源代码： (10) 1.选题的背景和意义 当今时代，计算机已经成为人们生活中不可或缺的一部分，它打破了地域时间限制，改变了人们的工作和生活方式。人们之间的联系越来越便捷，这就使得要经常与很多人保持着联系，而单纯依靠人脑已经很难记住所有人的联系方式还有其各做附加信息。通讯录系统能方便用户的需求，满足用户迅速、准确的查找修改或者删除联系人信息，把各个联系人信息以文件保存。本文介绍了c++编写简易通讯录管理：系统的分析，功能模块的设计，系统的流程图及运行界面。此系统的主要管理的信息由：联系人的姓名、性别、电话号码，加深对c++语言程序设计的理解，提高算法设计的能力，锻炼编程的能力。用c语言编程一个通讯录管理系统软件，要求能实现通讯录管理系统中的增加信息，删除信息，显示通讯里的所有信息，按名字查询信息，保存通讯录，退出系统。。 2.需求分析 2.1 用例图 通讯录管理系统的用例图如下图所示： 图2.1 用例图 1.实验目的 掌握线性表的链式存储结构设计与基本操作的实现。 2.实验内容与要求 ⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； ⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。 ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减； 3.数据结构设计 逻辑结构：线性结构 存储结构：链式存储结构 4.算法设计 #include 实验报告三线性表的链式存储 班级：姓名：学号：专业： 一、实验目的： （1）掌握单链表的基本操作的实现方法。 （2）掌握循环单链表的基本操作实现。 （3）掌握两有序链表的归并操作算法。 二、实验内容：（请采用模板类及模板函数实现） 1、线性表链式存储结构及基本操作算法实现 [实现提示] （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。 所加载的库函数或常量定义： （1）单链表存储结构类的定义： （2）初始化带头结点空单链表构造函数实现 输入：无 前置条件：无 动作：初始化一个带头结点的空链表 输出：无 后置条件：头指针指向头结点。 （３）利用数组初始化带头结点的单链表构造函数实现 输入：已存储数据的数组及数组中元素的个数 前置条件：无 动作：利用头插或尾插法创建带头结点的单链表 输出：无 后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。 （４）在带头结点单链表的第i个位置前插入元素e算法 输入：插入位置i，待插入元素e 前置条件：i的值要合法 动作：在带头结点的单链表中第i个位置之前插入元素e 输出：无 后置条件：单链表中增加了一个结点 （５）在带头结点单链表中删除第i个元素算法 输入：删除第i个结点，待存放删除结点值变量e 前置条件：单链表不空，i的值要合法 动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。 输出：无 后置条件：单链表中减少了一个结点 （６）遍历单链表元素算法 输入：无 前置条件：单链表不空 动作：遍历输出单链表中的各元素。 输出：无 后置条件：无 （７）求单链表表长算法。 输入：无 前置条件：无 动作：求单链表中元素个数。 输出：返回元素个数 后置条件：无 （８）判单链表表空算法 输入：无 前置条件：无 动作：判表是否为空。 输出：为空时返回１，不为空时返回0 后置条件：无 （９）获得单链表中第i个结点的值算法 输入：无 前置条件：i不空，i合法 动作：找到第i个结点。 输出：返回第i个结点的元素值。 后置条件：无 (10)删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无 前置条件：单链表存在 动作：清除单链表中所有的结点。 输出：无 后置条件：头指针指向空 实习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 福建工程学院 课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日 实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record; { Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理 long fold(NA s) //人名的折叠处理 { char *p; long sum=0; NA ss; strcpy(ss,s); //复制字符串，不改变原字符串的大小写 strupr(ss); //将字符串ss转换为大写形式 p=ss; while(*p!='\0') sum+=*p++; printf("\nsum====================%d",sum); return sum; } （2）建立哈希表 1、用除留余数法构建哈希函数 2、用线性探测再散列法处理冲突 int Hash1(NA str) //哈希函数 { long n; int m; n=fold(str); //先将用户名进行折叠处理 m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数 return m; //并返回模值 }Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突{ int i,q; i=c/2+1; while(i线性表的链式表示与实现
哈希表的设计与实现 课程设计报告
通讯录管理系统的设计与实现精选文档
线性表的链式存储结构实验报告
哈希表实现电话号码查询系统
数据结构课设-通讯录系统的设计与实现——哈希表
线性表的顺序储存结构
(数据结构)线性表的链式表示和实现(源代码)
哈希表实现通讯录-数据结构与算法课程设计报告
实验二 线性表的链式存储结构
线性表的链式存储结构和实现
哈希表查询设计及实现
通讯录管理系统的设计与实现
数据结构线性表的链式存储结构
实验3 线性表的链式存储
哈希表设计-数据结构课程设计
数据结构课程设计--哈希表实验报告