北邮数据结构实验一通讯录实验报告

数据结构实验报告实验名称：实验一——线性表学生姓名：班级：班内序号：学号：日期：2014年11月20日1．实验要求[正文格式要求]字体：汉字宋体、英文Times New Roman字号：五号颜色：黑色行距：单倍行距[内容要求]描述要求的实验目的和具体的实验内容2. 程序分析2.1 存储结构带头结点单链表2.2 关键算法分析一：关键算法1：头插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。

将新结点加入链表中伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:s->next=front->next;d:front->next=s2：尾插法自然语言描述：a:在堆中建立新结点：b:将a[i]写入到新结点的数据域：c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:r->next=s;d:r=s3：析构/删除函数自然语言描述：a:新建立一个指针，指向头结点b:判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:Node <T> * p=frontb:while(p)c:front=pd:p=p->nexte:delete front4：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1 b:循环以下操作，直到p为空或者j等于1b1：p指向下一个结点b2：j加1c:若p为空，说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node <T> * p=front->next;j=1;b:while(p&&j!=1)b1:p=p->nextb2:j++c:if(!p) throw ”error”d:return p5：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点b1：判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j的值加一c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:Node <T> * p=front->next;j=1;b:while(p)b1:if(p->next==x) return jp=p->nextj++c:return “error”6：插入函数自然语言描述：a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:Node <T> * s=new Node <T>;b:s-data=p->datac:s->next=p->nextd:p->next=se:p->data=x7：删除函数自然语言描述：a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述a:q=p->nextb:p->next=q->nextc:x=q->datad:delete q8：遍历打印函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空伪代码描述If front->next==NULLThrow ”an empty list ”Node<T>* temp=front->next;while(temp->next){cout<<temp->data<<" ";temp=temp->next;}8：获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e: 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n伪代码描述int n=0if front->next==NULLn=0else{Node<T>* temp=front->next; while(temp->next)n++;temp=temp->next; }return n;4. 总结1、调试时出现的问题及解决的方法编程序时总是不考虑异常抛出，后经老师指点改正。

北邮数据结构实验报告摘要：本报告基于北邮数据结构实验，通过实际操作和实验结果的分析，总结和讨论了各实验的目的、实验过程、实验结果以及相关的问题和解决方法。

本报告旨在帮助读者了解数据结构实验的基本原理和应用，并为今后的学习和研究提供参考。

1. 实验一：线性表的操作1.1 实验目的本实验旨在掌握线性表的基本操作以及对应的算法实现，包括插入、删除、查找、修改等。

1.2 实验过程我们使用C++语言编写了线性表的相关算法，并在实际编程环境下进行了测试。

通过插入元素、删除元素、查找元素和修改元素的操作，验证了算法的正确性和效率。

1.3 实验结果经过测试，我们发现线性表的插入和删除操作的时间复杂度为O(n)，查找操作的时间复杂度为O(n)，修改操作的时间复杂度为O(1)。

这些结果与预期相符，并反映了线性表的基本特性。

1.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如插入操作的边界条件判断、删除操作时的内存释放等。

通过仔细分析问题，我们优化了算法的实现，并解决了这些问题。

2. 实验二：栈和队列的应用2.1 实验目的本实验旨在掌握栈和队列的基本原理、操作和应用，并进行实际编程实现。

2.2 实验过程我们使用C++语言编写了栈和队列的相关算法，并在实际编程环境下进行了测试。

通过栈的应用实现表达式求值和逆波兰表达式的计算，以及队列的应用实现图的广度优先遍历，验证了算法的正确性和效率。

2.3 实验结果经过测试，我们发现栈的应用可以实现表达式的求值和逆波兰表达式的计算，队列的应用可以实现图的广度优先遍历。

这些结果证明了栈和队列在实际应用中的重要性和有效性。

2.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如中缀表达式转后缀表达式的算法设计、表达式求值的优化等。

通过查阅资料和与同学的讨论，我们解决了这些问题，并完善了算法的实现。

3. 实验三：串的模式匹配3.1 实验目的本实验旨在掌握串的基本操作和模式匹配算法，并进行实际编程实现。

数据结构通讯录管理系统课程设计实验报告背景随着信息化的快速发展，通讯录管理系统成为了每个人生活中必备的工具之一。

传统的纸质通讯录已经无法满足人们对于信息管理的需求，因此开发一个高效、便捷、用户友好的通讯录管理系统显得尤为重要。

本次课程设计实验的目标是设计一个基于数据结构的通讯录管理系统，实现通讯录的创建、查找、修改、删除等功能。

通过本次实验，我们可以学习和掌握数据结构中的链表、哈希表等基础概念和算法，并将其应用到实际项目中。

分析通讯录管理系统主要有以下几个功能：1.创建通讯录：通讯录是一个存储联系人信息的数据结构，可以存储联系人的姓名、电话号码、邮箱地址等信息。

2.添加联系人：可以向通讯录中添加新的联系人，包括姓名、电话号码、邮箱地址等信息。

3.查找联系人：可以根据姓名或电话号码查找通讯录中的联系人，并显示其详细信息。

4.修改联系人：可以根据姓名或电话号码修改通讯录中的联系人信息。

5.删除联系人：可以根据姓名或电话号码删除通讯录中的联系人。

为了实现上述功能，我们可以使用链表来实现通讯录的存储，每个节点表示一个联系人。

每个节点包含姓名、电话号码、邮箱地址等信息，并且有指向下一个节点的指针。

为了提高查找联系人的效率，我们还可以使用哈希表来实现联系人的快速查找。

哈希表采用键值对的方式存储数据，通讯录中的联系人可以以姓名为键，联系人节点为值存储在哈希表中。

结果实验的最终结果是一个完善的通讯录管理系统，能够实现创建通讯录、添加联系人、查找联系人、修改联系人和删除联系人等功能。

在实现过程中，我们遵循了以下步骤：1.首先，我们设计了联系人节点的数据结构，包括姓名、电话号码、邮箱地址等字段，并定义了节点的操作方法。

2.接着，我们设计了通讯录的数据结构，使用链表来存储联系人节点，并实现了通用的链表操作方法，如插入节点、删除节点等。

3.然后，我们设计了哈希表的数据结构，使用哈希函数将联系人节点存储在哈希表中，并实现了查找联系人的快速算法。

实验课程名称通讯录管理系统专业班级 10级计科1班学生姓名学号指导教师2012至2013学年第一学期第1 至18 周目录第１章概述 (3)1.1现状分析 (3)1.2实现意义 (3)第2章系统分析 (4)2.1用户需求分析 (4)2.2管理者需求分析 (4)第３章概要设计 (5)3.1主控菜单设计 (5)3.2 总结构设计流程图 (6)第4章详细设计 (6)4.1通讯录建立模块设计 (6)4.2通讯录查询模块设计 (7)4.3通讯录删除模块设计 (7)4.4通讯录链表的输出模块设计 (8)第5章运行与测试 (9)第6章总结和心得 (9)参考文献 (10)附件（源代码） (10)第１章概述1.1现状分析日益繁多的人际交往使得我们很难记住与每个人之间的联系方式，通讯录能够便捷的给我们带来所需要的相关信息。

为了实现通讯录管理的几种操作功能，首先设计一个含有多少个菜单项的主控菜单程序，然后再为这些菜单配上相应的功能。

1.2实现意义随着计算机的普及，人们的生活摆脱了传统式的记事本、电话簿，越来越多的靠计算机或者手机中的电话簿程序来帮助人们记住这些事情，极其简便。

这就需要有一个使用的通讯录管理系统，用户可以方便的通过自己电脑的通讯录管理系统，来随时查阅自己所需要的信息，而不必再大费周折去翻开那繁琐的记事本。

通讯录管理系统是一个专门针对储存用户联系方式以及一些简单个人信息的实用管理系统，它方便了用户对众多客户、朋友、同事等个人信息的储存和快速查阅的功能，大大减少了查找过程的时间。

然而要靠计算机来记住这些信息，首先就得要求用单链表做数据结构，设计一个实现通讯者信息的输入、查询、删除、输出、等功能的通讯录管理系统。

每条通讯者信息包含：编号、姓名、性别、电话号码、地址等信息。

第2章系统分析2.1用户需求分析为实现系统功能，本程序主要分为五个模块。

它们分别为：输入一个信息、删除一个信息、查询一个信息、插入一个信息、输出所有的信息、退出该程序。

随着信息技术的飞速发展，通讯录在人们的工作、生活中扮演着越来越重要的角色。

为了提高同学们对通讯录管理的认识，培养实际操作能力，我校组织了通讯录实训活动。

本次实训旨在使同学们掌握通讯录的基本操作，提高信息处理能力，为今后的工作打下坚实基础。

二、实训目标1. 熟悉通讯录的基本概念和作用；2. 掌握通讯录的创建、编辑、查询、导出等功能；3. 学会使用通讯录进行日常信息管理；4. 培养同学们团队协作和沟通能力。

三、实训内容1. 通讯录基础知识实训老师首先向同学们介绍了通讯录的基本概念、作用以及常见的通讯录类型。

通讯录是一种用于存储和查询联系人信息的工具，可以方便地记录和查找电话、邮箱、地址等个人信息。

常见的通讯录类型有纸质通讯录、电子通讯录等。

2. 通讯录创建与编辑同学们在实训老师的指导下，学习了如何创建一个新的通讯录。

首先，选择合适的通讯录类型，如电子通讯录；然后，输入联系人的姓名、电话、邮箱、地址等基本信息。

在编辑通讯录时，同学们掌握了如何修改、删除、添加联系人信息。

3. 通讯录查询与导出实训老师讲解了如何通过姓名、电话、邮箱等条件在通讯录中查询联系人信息。

此外，同学们还学会了如何将通讯录导出为Excel、Word等格式，方便后续的整理和使用。

4. 实际操作演练为了巩固所学知识，同学们进行了实际操作演练。

在实训老师的带领下，同学们分组进行通讯录管理，包括创建通讯录、添加联系人、查询信息等。

通过实际操作，同学们熟练掌握了通讯录的基本操作。

1. 同学们对通讯录的基本概念、作用有了更深入的了解；2. 掌握了通讯录的创建、编辑、查询、导出等功能；3. 提高了信息处理能力，为今后的工作打下了坚实基础；4. 培养了团队协作和沟通能力。

五、实训总结本次通讯录实训活动，同学们积极参与，认真完成各项任务。

通过实训，同学们对通讯录有了更加全面的认识，掌握了通讯录的基本操作，提高了信息处理能力。

在今后的工作和生活中，通讯录将发挥重要作用，希望同学们能够充分利用所学知识，提高工作效率。

数据结构实验报告之通讯录的实现一、实验题目利用线性表实现一个通讯录管理，通信录的数据格式如下：struct DataType{int ID; //编号char name[10]; //姓名char ch; //性别char phone[13]; //电话char addr[31]; //地址};要求：∙实现通讯录的建立、增加、删除、修改、查询等功能∙能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。

∙能够保存每次更新的数据（选作）∙能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作）∙编写测试main()函数测试线性表的正确性二、实验目的1、熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法。

2、掌握线性表的操作的实现方法。

3、运用线性表解决实际问题。

三、实验内容通过编写一个C++程序完成一个简易的通讯录管理系统，能够实现建立，增加，删除，修改，查找，浏览，输出，菜单等基本功能。

管理系统中每个元素含有成员的ID、姓名、性别、电话、地址等信息。

程序是使用链表的功能，通过一些算法简单的实现。

四、算法思路与主要代码1. 通信录管理结构：建立，增加，删除，修改，查找，浏览，菜单。

2.建立通讯录构造函数，建立头节点PHONEBOOK::PHONEBOOK(){first = new DataType;first->next = first->prior = first;first->ID = 0;}头插法，添加联系人1:在堆中建立新结点2:将 a[i]写入到新结点的数据域3:修改新结点的指针域4:修改头结点的指针域，将新结点加入链表中即 1:Node <T> * s=new Node <T> 2:s->data=a[i] 3:s->next=front->next; 4:front->next=s代码实现void PHONEBOOK::Insert(){DataType *data = new DataType;data->next = first->next;data->prior = first;first->next = data;data->next->prior = data;m++;data->ID = m;3.查找联系人按姓名查找查找是指用户输入要查找的联系人的姓名，系统该函数内找到该联系人，返回该联系人数据域的指针，在主函数中输出该联系人的全部信息。

[数据结构课程设计通讯录查询系统实验报告范文及源代码]数据结构通讯录工程名称：停车管理系统姓名：学号：专业：软件工程1.需求分析为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的与地址。

设计散列表存储，设计并实现通讯录查找系统。

1.根本要求〔1〕每个记录有以下数据项：号码、用户名、地址；〔2〕从键盘输入各记录，分别以号码为关键字建立散列表；〔3〕采用二次探测再散列法解决冲突；〔4〕查找并显示给定号码的记录；〔5〕通讯录信息文件保存。

2.重点、难点重点：〔1〕通过实验深入理解哈希表既是一种存储形式，又是一种查找方法；〔2〕哈希表的构造；〔3〕哈希冲突方案的设计。

难点：哈希表的构造与哈希冲突方案的设计输入的形式和输入值的范围；输入三个字符串：分别是号码，姓名，地址，每行一个数据字符串长度适当如：号码〔纯数字〕姓名地址输出的形式；如：姓名号码地址程序所能到达的功能。

1：并且通过号码为关键字，用二次再散列法寻找地址储存在哈希表中。

2：3：4：5：显示通讯录6：把通讯录写入文件储存。

2.概要设计(1)数据结构tructlit{chara[12];charname[15];charadd[15];intf=0;};用连续的内存空间构建哈希表tructqtack{tructlit某bae;inti;};(2)程序模块1：构建二次再散列：inti;for(i=1;i<25;i++)d[2某i]=-1某i某i;for(i=1;i<25;i++)/某构造二次再散列某/d[i+i-1]=i某i;2：主菜单：voidinterface(){inti;printf("某某某某某某某某某某某某某某某某某某某某\n");printf("某某某某某某某某某某某某某某某某某某某某\n");canf("%d",&i);witch(i){cae0:return;break;cae1:huru();break;cae2:print();break;cae3:each();break;cae4:del();break;cae5:change();break;cae6:write();break;};}3：输入voidhuru()4：存入哈希表，采用二次探测再散列法解决冲突；voidtore(char某a,char某name,char某add)voideach()；voidchange()Voiddel〔〕；voidwrite()(3)各模块之间的调用关系以及算法设计3.详细设计4.测试与分析主界面：构建哈希表，允许号码重复可以支持姓名，，地址三个关键字的查找可以按照姓名地址删除写文件：创立文件通讯录.t某t 如图：5.附录3.cpp#include<tdio.h>#include<tdlib.h>#include<tring.h>#include<iotream>#include<tring.h>uingnamepacetd;intd[50];/某再散列某/tructlit{chara[12];charname[15];charadd[15];intf=0;};tructqtack{tructlit某bae;inti;};tructqtackS;voidtore(char某a,char某name,char某add){intkey;key=int(a[0])+int(a[3])+int(a[7]);/某以号码的第1,4,8位作为关键字构造哈希函数某/S.i=key%20;intj=1;while(true){if((S.bae+S.i)->f==0){trcpy((S.bae+S.i)->a,a);trcpy((S.bae+S.i)->name,name);trcpy((S.bae+S.i)->add,add);(S.bae+S.i)->f=1;break;}S.i=(key%20+d[j])%20;j++;}}voidhuru(){voidinterface();cout<<"请输入：\n例如：\n小王\n安徽省合肥市\n输入0结束\n"; chara[12];charname[15];charadd[15];while(true){canf("%",a);if(a[0]=='0')break;canf("%",name);canf("%",add);printf("%已保存\n",name);tore(a,name,add);/某将输入保存到哈希表某/}interface();}voidprint(){voidinterface();inti;printf("姓名号码地址\n");for(i=0;i<20;i++){if((S.bae+i)->f==1){printf("%%%\n",(S.bae+i)->name,(S.bae+i)->a,(S.bae+i)->add);}}interface();}voideach(){voidinterface();inti;intff=0;intb;chara[15];printf("输入1按号码查找，输入2按姓名查找，输入3按地址查找\n");canf("%d",&b);witch(b){cae1:printf("请输入号码\n");canf("%",a);for(i=0;i<20;i++)if(trcmp(a,(S.bae+i)->a)==0){printf("%%%\n",(S.bae+i)->name,(S.bae+i)->a,(S.bae+i)->add); ff=1;}if(ff==0)printf("找不到该用户\n");break;cae2:printf("请输入姓名\n");canf("%",a);for(i=0;i<20;i++)if(trcmp(a,(S.bae+i)->name)==0){printf("%%%\n",(S.bae+i)->name,(S.bae+i)->a,(S.bae+i)->add); ff=1;}if(ff==0)printf("找不到该用户\n");break;cae3:printf("请输入地址\n");canf("%",a);for(i=0;i<20;i++)if(trcmp(a,(S.bae+i)->add)==0){printf("%%%\n",(S.bae+i)->name,(S.bae+i)->a,(S.bae+i)->add); ff=1;}if(ff==0)printf("找不到该用户\n");break;}interface();}voiddel(){voidinterface();inti;intff=0;chara[15];printf("输入1按号码删除，输入2按姓名删除，输入3按地址删除\n");canf("%d",&b);witch(b){cae1:printf("请输入号码\n");canf("%",a);for(i=0;i<20;i++)if(trcmp(a,(S.bae+i)->a)==0){(S.bae+i)->f=0;Print(“已删除：%%%\n",(S.bae+i)->name,(S.bae+i)->a,(S.bae+i)->add);ff=1;}if(ff==0)printf("找不到该用户\n");cae2:printf("请输入姓名\n");canf("%",a);for(i=0;i<20;i++)if(trcmp(a,(S.bae+i)->name)==0){(S.bae+i)->f=0;printf("已删除：%%%\n",(S.bae+i)->name,(S.bae+i)->a,(S.bae+i)->add);ff=1;}if(ff==0)printf("找不到该用户\n");break;cae3:printf("请输入地址\n");canf("%",a);for(i=0;i<20;i++)if(trcmp(a,(S.bae+i)->add)==0){(S.bae+i)->f=0;printf("已删除：%%%\n",(S.bae+i)->name,(S.bae+i)->a,(S.bae+i)->add);ff=1;}if(ff==0)printf("找不到该用户\n");break;}interface();}voidchange(){voidinterface();inti;intff=0;intb;chara[15];printf("请输入姓名\n");canf("%",a);for(i=0;i<20;i++)if(trcmp(a,(S.bae+i)->name)==0){printf("您要修改的是：%%%\n",(S.bae+i)->name,(S.bae+i)->a,(S.bae+i)->add);printf("请输入新信息\n");canf("%",(S.bae+i)->a);canf("%",(S.bae+i)->name);canf("%",(S.bae+i)->add);printf("已修改成：%%%\n",(S.bae+i)->name,(S.bae+i)->a,(S.bae+i)->add);ff=1;}if(ff==0)printf("找不到该用户\n");interface();}voidwrite()voidinterface();inti=0;FILE某fp;if((fp=fopen("通讯录.t某t","wb"))==NULL){printf("openfileerror\n");e某it(1);}for(i=0;i<=20;i++){intch=32;if((S.bae+i)->f==1){fprintf(fp,"%",(S.bae+i)->name);fputc(ch,fp); fprintf(fp,"%",(S.bae+i)->a);fputc(ch,fp);ch=10;fprintf(fp,"%",(S.bae+i)->add);fputc(ch,fp); }fcloe(fp);interface();}voidinterface(){inti;printf("某某某某某某某某某某某某某某某某某某某某\n"); printf("某某某某某某某某某某某某某某某某某某某某\n"); canf("%d",&i);witch(i){cae0:return;break;cae1:huru();break;cae2:print();break;cae3:each();break;cae4:del();break;cae5:change();break;cae6:write();break;}intmain(){ytem("color70");//可以写成red调出颜色组S.bae=(tructlit某)malloc(20某izeof(tructlit)); ytem("date/T");ytem("TIME/T");inti;for(i=1;i<25;i++)d[2某i]=-1某i某i;for(i=1;i<25;i++)/某构造二次再散列某/d[i+i-1]=i某i;interface();}6.用户使用手册根据主菜单提示选择所想要的操作0：结束程序小华安徽合肥可以根据姓名，，地址分别作为关键字进行查询谢谢使用!。

北邮数据结构实验报告-排序北邮数据结构实验报告-排序一、实验目的本实验旨在掌握常见的排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序等，并通过实际编程实现对数字序列的排序。

二、实验内容1.冒泡排序冒泡排序是一种简单的排序算法，其基本思想是依次比较相邻的两个元素，并按照从小到大或从大到小的顺序交换。

具体步骤如下：- 从待排序序列的第一个元素开始，依次比较相邻的两个元素；- 如果前面的元素大于后面的元素，则交换这两个元素的位置；- 重复上述步骤，直到整个序列有序。

2.插入排序插入排序是一种简单且直观的排序算法，其基本思想是将待排序序列分为已排序和未排序两部分，每次从未排序部分中选择一个元素插入到已排序部分的合适位置。

具体步骤如下：- 从待排序序列中选择一个元素作为已排序部分的第一个元素；- 依次将未排序部分的元素插入到已排序部分的合适位置，使得已排序部分保持有序；- 重复上述步骤，直到整个序列有序。

3.选择排序选择排序是一种简单且直观的排序算法，其基本思想是每次选择未排序部分中的最小（或最大）元素，并将其放在已排序部分的末尾。

具体步骤如下：- 在未排序部分中选择最小（或最大）的元素；- 将选择的最小（或最大）元素与未排序部分的第一个元素交换位置；- 重复上述步骤，直到整个序列有序。

4.快速排序快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序序列分割成两部分，其中一部分的元素都比另一部分的元素小。

具体步骤如下：- 选择一个枢轴元素（一般选择第一个元素）；- 将待排序序列中小于枢轴元素的元素放在枢轴元素的左侧，大于枢轴元素的元素放在枢轴元素的右侧；- 对枢轴元素左右两侧的子序列分别进行递归快速排序；- 重复上述步骤，直到整个序列有序。

5.归并排序归并排序是一种高效的排序算法，其基本思想是将待排序序列划分成足够小的子序列，然后对这些子序列进行两两合并，最终形成有序的序列。

具体步骤如下：- 将待排序序列递归地划分成足够小的子序列；- 对每个子序列进行归并排序；- 合并相邻的子序列，直到整个序列有序。

北邮数据结构实验报告北邮数据结构实验报告一、引言数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化起着至关重要的作用。

本报告旨在总结北邮数据结构实验的相关内容，包括实验目的、实验设计、实验过程和实验结果等。

二、实验目的本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。

具体目的如下：1. 掌握线性表、栈和队列等基本数据结构的实现方法；2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法；3. 学会使用递归和非递归算法解决实际问题；4. 培养编程实践能力和团队合作意识。

三、实验设计本次实验包括以下几个部分：1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和查找等。

通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。

2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。

通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。

3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。

通过实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表达式求值等。

4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。

通过实验，掌握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索算法。

四、实验过程1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。

在实验过程中，遇到了一些问题，如边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。

2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和出队等基本操作。

在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。

3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查找等操作。

在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。

一、实验背景随着科技的发展，人们的生活节奏越来越快，通讯方式也日益多样化。

为了方便人们管理和查阅通讯信息，通讯录管理系统应运而生。

本实验旨在通过设计和实现一个通讯录管理系统，提高通讯信息管理的效率和便捷性。

二、实验目的1. 熟悉通讯录管理系统的基本功能和操作流程；2. 掌握通讯录管理系统的设计方法和实现技巧；3. 提高编程能力和系统分析能力。

三、实验内容1. 系统需求分析根据实验要求，本通讯录管理系统应具备以下功能：（1）添加联系人：输入联系人信息，包括姓名、电话、邮箱、QQ号等，并将其保存到系统中；（2）删除联系人：根据联系人姓名或电话，删除指定联系人信息；（3）修改联系人信息：根据联系人姓名或电话，修改指定联系人的信息；（4）查询联系人：根据联系人姓名、电话、邮箱或QQ号，查询指定联系人的信息；（5）导出通讯录：将通讯录信息导出到文本文件或Excel文件；（6）导入通讯录：从文本文件或Excel文件中导入通讯录信息。

2. 系统设计本系统采用C++编程语言，利用面向对象编程思想进行设计。

系统采用单例模式，确保全局只有一个通讯录对象。

联系人信息以链表形式存储，便于插入、删除和修改操作。

（1）数据结构设计联系人信息使用结构体存储，包括姓名、电话、邮箱、QQ号等字段。

```cppstruct Contact {string name;string phone;string email;string qq;Contact next;};```（2）类设计- Contact类：负责存储联系人信息，包括姓名、电话、邮箱、QQ号等字段；- ContactManager类：负责管理联系人链表，包括添加、删除、修改、查询、导出和导入等功能。

```cppclass Contact {public:string name;string phone;string email;string qq;Contact next;Contact(string n, string p, string e, string q) : name(n), phone(p), email(e), qq(q), next(NULL) {}};class ContactManager {private:Contact head;public:ContactManager() : head(NULL) {}~ContactManager() {// 释放链表内存Contact temp;while (head != NULL) {temp = head;head = head->next;delete temp;}}void AddContact(Contact contact) {// 添加联系人}void DeleteContact(string phone) {// 删除联系人}void ModifyContact(string phone, Contact newContact) { // 修改联系人信息}Contact QueryContact(string phone) {// 查询联系人return NULL;}void ExportContact() {// 导出通讯录}void ImportContact() {// 导入通讯录}};```3. 系统实现根据系统设计，使用C++编程语言实现各个功能模块。

一、实验目的1、能够利用单链表的基本运算进行单链表的相关操作。

2、加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。

3、熟练掌握线性表的类型定义方法、存储方法及其基本运算（元素的建立、查找、删除等）的实现方法，培养综合运用所学知识，根据具体问题进行数据结构设计和算法设计的能力。

二、实验环境具有Windows XP或2003的计算机、V istual C++ 6.0、网络环境。

三、实验内容设计一个班级同学的通讯录，要求如下：✓通讯录中每个同学的信息包含以下内容：学号（id）、姓名（name）、电话号码（tel）。

如果需要更多其他信息，请自行添加。

✓程序主菜单包含以下几个功能：（1）添加记录：通过键盘输入信息，添加一条通讯录记录。

（2）删除记录：通过键盘输入学号，删除该学号的记录。

（3）输出记录：输出通讯录全部记录。

（4）按姓名查找：通过键盘输入姓名，输出该同学的所有信息。

（5）按电话号排序：按电话号码从小到大排序并输出排序后的信息。

（6）清空记录：删除通讯录中的全部记录，并删除文件。

（7）退出。

程序清单#include<stdio.h>#include<stdlib.h>#include<string.h>#define N 20typedef struct student{char tel[N];char name[N];char id[N];struct student *next;}linklist;//创建信息void createlist(linklist *&l){int ch;linklist *s,*p;printf("***********创建通讯录***********\n");printf("----请输入通讯者信息-----：\n请输入非零整数，输入0则退出:\n");scanf("%d",&ch);l=(linklist *)malloc(sizeof(linklist));s=l;while(ch!=0){p=(linklist *)malloc(sizeof(linklist));printf("请输入通讯者姓名:");scanf("%s",p->name);printf("请输入通讯者电话号:");scanf("%s",p->tel);printf("请输入通讯者身份证号:");scanf("%s",p->id);s->next=p;s=p;printf("请输入通讯者信息：\n请输入非零整数，输入0则退出:\n");scanf("%d",&ch);}s->next=NULL;}//删除信息void listdelete(linklist *&l,int t ){int j=0;linklist *p,*q;p=l;while(p!=NULL&&j<t-1){j++;p=p->next;}if(p==NULL)exit(0);else{q=p->next;if(q==NULL)exit(0);p->next=q->next;printf("***************删除系统**************\n");printf("-------你将删除的联系人的信息为-------:\n");printf("通讯者姓名:%s\n",q->name);printf("通讯者电话号:%s\n",q->tel);printf("通讯者身份证号:%s\n",q->id);printf("******-------******删除成功******------*******\n");free(q);}}//输出信息void output(linklist *l){linklist *p;p=l->next;printf("----***----输出所有联系者信息----***----:\n");while(p!=NULL){printf("通讯者姓名:%s\n",p->name);printf("通讯者电话号:%s\n",p->tel);printf("通讯者身份证号:%s\n",p->id);printf("*****************************\n");p=p->next;}}//按姓名查找void findname(linklist *l){char n[N];linklist *p=l->next;printf("***************查找系统*************\n");printf("----------请输入要查找的姓名---------:\n");scanf("%s",n);while(p!=NULL){if(strcmp(p->name,n)){printf("-----***--你要查找的资料为--***----:\n");printf("通讯者姓名:%s\n",p->name);printf("通讯者电话号:%s\n",p->tel);printf("通讯者身份证号:%s\n",p->id);printf("*****************************");break;}elsep=p->next;}}//按电话号排序void sorttel(linklist *&l){linklist *p,*q,*s;q=l;p=q->next->next;q->next->next=NULL;while(p){while(q->next&&(strcmp(p->tel,q->next->tel)>0))q=q->next;s=p->next;p->next=q->next;q->next=p;p=s;q=l;}}//清空void release(linklist *&l){linklist *p,*q;p=l;q=p->next;while(q!=NULL){free(p);p=q;q=p->next;}free(p);printf("--------数据已全部被清空----------\n，*****内存回收*****\n"); }//主函数void main(){int i,t;linklist *l;while(1){printf("通讯录功能如下:\n1.建立通讯录信息\n2.删除信息\n3.输出信息\n4.按姓名查找信息\n5.按电话号排序信息\n6.清空信息\n7.退出");scanf("%d",&i);if(i<=0||i>7)break;switch(i){case 1:createlist(l);break;case 2:printf("---------请输入第t个要删除的信息---------:\n");scanf("%d",&t);listdelete(l,t);break;case 3:output(l);break;case 4:findname(l);break;case 5:sorttel(l);printf("-----***---&&&--这是按电话号排序后的信息列表--&&&---***-----\n");output(l);break;case 6:release(l);break;case 7:break;}}}运行结果：建立通讯录信息运行结果截图：输入零后通讯录信息输出结果截面图：查询通讯录信息运行结果截图：通讯录信息排序运行结果截图：删除通讯录信息运行结果截图：删除通讯录信息后的输出结果截面图：清空通讯录信息的运行结果截面图：四、实验心得与小结通过这次的上机实验，使我学到了一些回顾了以前学过的知识，使我对数据结构程序设计有了更深层次的认识和理解，懂得了灵活运用。

数据结构实验报告实验名称：实验———线性表学生姓名：班级：班内序号：学号：日期：实验要求1.1 实验目的通过选择下面四个题目之一进行实现，掌握如下内容：➢熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法➢学习指针、模板类、异常处理的使用➢掌握线性表的操作的实现方法➢学习使用线性表解决实际问题的能力1.2 实验内容利用线性表实现一个通讯录管理，通信录的数据格式如下：struct DataType{int ID; //编号char name[10];//姓名char ch;//性别char phone[13];//电话char addr[31];//地址};1.3具体要求➢实现通讯录的建立、增加、删除、修改、查询等功能➢能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。

➢能够保存每次更新的数据（选作）➢能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作）➢编写测试main()函数测试线性表的正确性2. 程序分析通过编程完成通讯录管理系统，实现建立、增加、修改、查找、删除、输出等一般功能，每个数据元素包含成员的ID 、姓名、电话、住址等基本信息。

本程序使用链表的功能，以C++语言为基础编写。

对于本通讯录管理系统的建立，需要了解并掌握链表的算法与设计方法，综合运用所学知识完成。

2.1 存储结构节点结构:2.2 关键算法分析通讯录系统图2.2.1 通讯录的建立 伪代码：1. 在堆栈中申请新的节点2. 新节点的数据为a[i]3. 将新节点添加到链表4. 修改尾指针5.全部插入后最后一个节点的指针域设为空代码实现：ContactBook::ContactBook(DataType a[],int n){front=new Node;rear=new Node;rear=front;for(int i=0;i<n;i++) //尾插法{Node* p=new Node;p->data=a[i];rear->next=p;rear=p;}rear->next=NULL;}时间复杂度=o(n)2.2.2 添加新成员伪代码：与通讯录的建立类似，通过尾插法实现代码实现：void ContactBook::Add(DataType a){Node* p=new Node;p->data=a;rear->next=p;rear=p;rear->next=NULL;}时间复杂度=o(1)2.2.3 查找成员伪代码：1.初始化指针p指向头指针2.循环直到匹配到ID或为p为空3.找到则返回p的位置4.找不到则返回空指针代码实现：DataType* ContactBook::Get(int i)Node* p=front;while(p){if(p->data.ID==i) //ID匹配模式查找return &p->data; //找到则返回p的地址p=p->next;}return NULL; //找不到则返回空}时间复杂度=o(n)2.2.4 删除成员伪代码：1.初始化指针p指向头指针2.循环匹配ID找到要删除的成员的前一个节点3.初始化指针q指向要删除的成员4.保存q的数据5.p指向q的下一节点6.释放q节点代码实现：DataType ContactBook::Delete(int i){Node* p=front;while(p){if(p->next->data.ID==i)break;p=p->next;}Node* q=p->next;//q指针指向要删除的成员if(q){DataType x=q->data;//保存成员数据p->next=q->next;//p的next指向q的nextdelete q;cout<<"删除成功！"<<endl;return x;}else{cout<<"该成员不存在！"<<endl;}}时间复杂度=o(n)2.2.5 修改成员先调用查询模块，找到并打印用户信息，然后依次修改成员信息代码实现：void ContactBook::Modify(DataType a,int i){DataType* p=Get(i);*p=a;}时间复杂度=o(n)2.2.6 打印成员依次打印成员信息代码实现：void ContactBook::printList(){cout<<"您的通讯录成员如下："<<endl;cout<<"********************"<<endl;Node* p=front->next;while(p){cout<<p->data.ID<<" "<<p-><<" "<<p->data.ch<<" "<<p->data.phone<<" "<<p->data.addr<<endl;cout<<"********************"<<endl;p=p->next;}}时间复杂度=o(n)3. 程序运行结果3.1 主程序流程图图2 流程图示意图3.2 测试截图3.2.1 建立通讯录3.2.2 增加成员3.3.3 查找成员3.3.4 修改成员3.3.5 删除成员3.3.6 打印成员3.3.7 退出4. 总结通过本实验，巩固了我对链表的理解，学会了使用线性表解决一些实际的问题。

北邮数据结构实验报告图一、实验报告规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：1.需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定：(1)输入的形式和输入值的范围;(2)输出的形式;(3)程序所能达到的功能;(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2.概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

3.详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);画出函数的调用关系图。

4.调试分析内容包括：(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想;(3)经验和体会等。

5.用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。

6.测试结果列出你的测试结果，包括输入和输出。

这里的测试数据应该完整和严格，最好多于需求分析中所列。

7.附录带注释的源程序。

如果提交源程序软盘，可以只列出程序文件名的清单。

值得注意的是，实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然也可以应该最后用实验报告纸誊清或打印)。

数据结构实验报告;实验名称：实验一线性表实现一个多项式;学生姓名：黄锦雨;班级：XX211109;班内序号：20;学号：XX210263;日期：XX年10月31日;实验目的：;1.熟悉C++语言的基本编程方法，掌握集成编译环;2.学习指针、模板类、异常处理的使用;3.掌握线性表的操作的实现方法;4.学习使用线性表解决实际问题的能力;实验内容：;数据结构实验报告实验名称：实验一线性表实现一个多项式学生姓名：黄锦雨班级：XX211109班内序号： 20学号： XX210263日期： XX年10月31日实验目的：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + … + anxn要求：1. 能够实现一元多项式的输入和输出2. 能够进行一元多项式相加3. 能够进行一元多项式相减4. 能够计算一元多项式在x处的值5. 能够计算一元多项式的导数(选作)6. 能够进行一元多项式相乘(选作)7. 编写测试main()函数测试线性表的正确性2. 程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。

一、实训目的本次数据结构实训通讯录报告旨在通过实际操作，加深对数据结构理论知识的理解，提高编程能力，培养实际解决问题的能力。

通过设计、实现和维护一个通讯录管理系统，使学生掌握线性表、链表、树、图等基本数据结构的应用，同时熟悉数据库操作和前端界面设计。

二、实训环境1. 操作系统：Windows 102. 开发工具：Visual Studio 20193. 编程语言：C++4. 数据库：MySQL5. 前端界面设计：Qt三、实训内容1. 系统需求分析（1）功能需求① 添加：允许用户添加新的联系人信息，包括姓名、电话、邮箱、地址等。

② 查询：根据姓名、电话、邮箱等关键字进行模糊查询。

③ 修改：允许用户修改指定联系人的信息。

④ 删除：允许用户删除指定联系人信息。

⑤ 导出：将通讯录数据导出为Excel格式。

⑥ 导入：允许用户从Excel文件导入联系人信息。

（2）性能需求① 系统应具备良好的响应速度，用户操作时，系统应迅速给出反馈。

② 系统应具备较高的稳定性，避免因操作失误导致数据丢失。

2. 系统设计① 联系人信息采用结构体存储，包括姓名、电话、邮箱、地址等字段。

② 联系人信息存储在MySQL数据库中，使用线性表进行管理。

③ 查询操作采用二分查找算法，提高查询效率。

（2）功能模块设计① 添加模块：用户输入联系人信息，系统将其存储在数据库中。

② 查询模块：用户输入关键字，系统从数据库中查找匹配的联系人信息。

③ 修改模块：用户输入联系人信息，系统将其更新到数据库中。

④ 删除模块：用户输入联系人信息，系统将其从数据库中删除。

⑤ 导出模块：将数据库中的联系人信息导出为Excel格式。

⑥ 导入模块：用户上传Excel文件，系统将其中的联系人信息导入数据库中。

3. 系统实现（1）数据库设计① 创建联系人信息表（contact_info），包括姓名、电话、邮箱、地址等字段。

② 设计SQL语句，实现数据的增删改查操作。

（2）编程实现① 使用C++实现各个功能模块，包括添加、查询、修改、删除等。

北邮世纪学院数据结构实验文档实验一：线性表的实现<上机实验要求>修订历史记录本文档简要说明了第一次上机实验的作业要求。

目录修订历史记录 (1)1实验目的 (3)2问题描述 (3)2.1基本要求 (3)2.2高级要求 (3)3实验要求 (3)4上机实验文档要求 (3)5编程提示 (3)1实验目的(1)熟悉Visual C++6.0的编程环境，学会编译、设置断点、调试程序；(2)学习使用MSDN帮助(3)了解线性表的不同存储结构，并掌握顺序表和链表的编程方法(4)了解软件测试的工作内容和方法。

(5)熟悉软件文档的写作(6)了解团队开发，增强合作精神。

2问题描述有n个同学一起玩游戏(10≤n≤99)，大家围成一圈，依靠学号来区分同学，从某一个同学(编号为a)开始数数，遇到7的倍数或者包含7的数（比如17，27），则该同学退出圈外，请求解同学们退出的顺序（用学号表示）。

2.1基本要求(1)同学的总人数n可变(10≤n≤99)，开始位置a可变(1≤a≤n)；(2)用两种线性表的存储结构来分别表示围成圈的同学和退出顺序。

比如，可以用循环链表或者双链表表示围成的圈，用顺序表(一位数组)来存储退出的同学学号的顺序；(3)同学的学号可以用简单1,2,3,…,M编号；(4)文档中，对算法的时间复杂度和空间复杂度进行分析，判断复杂度与n之间的关系。

(5)算法的流程图使用Visio绘制。

2.2高级要求(1)通过读取txt文件来读取学生的学号和姓名，最后的输出结果采用名单的方式显示到屏幕上；(2)用结构体存储学生的信息；(3)可以将“过七”改成“过x”，x为2~9的任意整数。

(4)程序有差错控制，能够对错误的输入参数进行提示和识别，比如总人数为负数。

3实验要求三人一组，文档完备，不得抄袭；成绩计算方法：编码50% 测试20% 文档30%4上机实验文档要求参考“实验报告模板.doc”，包含问题描述、算法思路、算法描述、源程序清单、测试结果(典型测试实例)、心得体会、分工及签名要求上交打印版，包含签名。