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

北京邮电大学信息与通信工程学院第1页数据结构实验报告实验名称：实验———线性表学生姓名：班级：班内序号：学号：日期：实验要求1.1实验目的通过选择下面四个题目之一进行实现，掌握如下内容：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力1.2实验内容利用线性表实现一个通讯录管理，通信录的数据格式如下：structDataType{intID;//编号charname[10];//姓名charch;//性别charphone[13];//电话charaddr[31];//地址};1.3具体要求实现通讯录的建立、增加、删除、修改、查询等功能能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。能够保存每次更新的数据（选作）能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作）编写测试main()函数测试线性表的正确性北京邮电大学信息与通信工程学院第2页2.程序分析通过编程完成通讯录管理系统，实现建立、增加、修改、查找、删除、输出等一般功能，每个数据元素包含成员的ID、姓名、电话、住址等基本信息。本程序使用链表的功能，以C++语言为基础编写。对于本通讯录管理系统的建立，需要了解并掌握链表的算法与设计方法，综合运用所学知识完成。2.1存储结构节点结构:存储结构：带头结点和尾节点的单链表rearfront2.2关键算法分析通讯录系统图2.2.1通讯录的建立伪代码：1.在堆栈中申请新的节点通讯录管理系统建立增加查找修改删除退出datanexta[0]a[n-1]^北京邮电大学信息与通信工程学院第3页2.新节点的数据为a[i]3.将新节点添加到链表4.修改尾指针5.全部插入后最后一个节点的指针域设为空代码实现：ContactBook::ContactBook(DataTypea[],intn){front=newNode;rear=newNode;rear=front;for(inti=0;in;i++)//尾插法{Node*p=newNode;p-data=a[i];rear-next=p;rear=p;}rear-next=NULL;}时间复杂度=o(n)2.2.2添加新成员伪代码：与通讯录的建立类似，通过尾插法实现代码实现：voidContactBook::Add(DataTypea){Node*p=newNode;p-data=a;rear-next=p;rear=p;rear-next=NULL;}时间复杂度=o(1)2.2.3查找成员伪代码：1.初始化指针p指向头指针2.循环直到匹配到ID或为p为空3.找到则返回p的位置4.找不到则返回空指针北京邮电大学信息与通信工程学院第4页代码实现：DataType*ContactBook::Get(inti){Node*p=front;while(p){if(p-data.ID==i)//ID匹配模式查找return&p-data;//找到则返回p的地址p=p-next;}returnNULL;//找不到则返回空}时间复杂度=o(n)2.2.4删除成员伪代码：1.初始化指针p指向头指针2.循环匹配ID找到要删除的成员的前一个节点3.初始化指针q指向要删除的成员4.保存q的数据5.p指向q的下一节点6.释放q节点代码实现：DataTypeContactBook::Delete(inti){Node*p=front;while(p){if(p-next-data.ID==i)break;p=p-next;}Node*q=p-next;//q指针指向要删除的成员if(q){DataTypex=q-data;//保存成员数据p-next=q-next;//p的next指向q的nextdeleteq;cout删除成功！endl;returnx;}else{北京邮电大学信息与通信工程学院第5页cout该成员不存在！endl;}}时间复杂度=o(n)2.2.5修改成员先调用查询模块，找到并打印用户信息，然后依次修改成员信息代码实现：voidContactBook::Modify(DataTypea,inti){DataType*p=Get(i);*p=a;}时间复杂度=o(n)2.2.6打印成员依次打印成员信息代码实现：voidContactBook::printList(){cout您的通讯录成员如下：endl;cout********************endl;Node*p=front-next;while(p){coutp-data.IDp-data.namep-data.chp-data.phonep-data.addrendl;cout********************endl;p=p-next;}}时间复杂度=o(n)3.程序运行结果3.1主程序流程图北京邮电大学信息与通信工程学院第6页否是图2流程图示意图3.2测试截图3.2.1建立通讯录开始创建通讯录类对象初始化创建删除成员添加成员查找成员打印成员修改成员退出退出结束北京邮电大学信息与通信工程学院第7页3.2.2增加成员3.3.3查找成员北京邮电大学信息与通信工程学院第8页3.3.4修改成员3.3.5删除成员北京邮电大学信息与通信工程学院第9页3.3.6打印成员3.3.7退出北京邮电大学信息与通信工程学院第10页4.总结通过本实验，巩固了我对链表的理解，学会了使用线性表解决一些实际的问题。但实验中还是有一些问题暴露了出来。比如一开始在调试的时候，打印成员时出现了如下截图中的问题。经过分析，才知道原来初始化指针p的时候指向了头指针并打印了出来，修改后p应该指向头指针的next域。调试中诸如这样的问题并不少见，也就是内存错误。北京邮电大学信息与通信工程学院第11页本实验还要求我们学会对异常操作进行处理，本程序中也对该要求做了相关改进，比如要求“请输入数字选择”时，对于输入不合理的数字或字符都有相应的提示、处理。本程序的不足之处有二。一是查找用户时只能进行ID匹配查找，而不能对其他信息进行匹配查找。二是没加入读取和保存联系人的功能，该功能可以通过使用文件流，将联系人信息输出到指定文件中保存，并且可以读取后进行操作。附源程序：#includeiostreamusingnamespacestd;structDataType{intID;//IDcharname[10];//姓名charch;//性别charphone[13];//电话charaddr[31];//地址};structNode{DataTypedata;//数据structNode*next;//指针指向下一节点};classContactBook{public:ContactBook();//默认构造函数ContactBook(DataTypea[],intn);//构造函数voidAdd(DataTypea);//增加成员DataTypeDelete(inti);//删除成员DataType*Get(inti);//查找成员voidModify(DataTypea,inti);//修改成员voidprintList();//打印所有成员~ContactBook();//析构函数private:Node*front;Node*rear;};北京邮电大学信息与通信工程学院第12页ContactBook::ContactBook(){front=newNode;rear=newNode;front-next=NULL;rear=front;}ContactBook::ContactBook(DataTypea[],intn){front=newNode;rear=newNode;rear=front;for(inti=0;in;i++)//尾插法{Node*p=newNode;p-data=a[i];rear-next=p;rear=p;}rear-next=NULL;}voidContactBook::Add(DataTypea)//尾插法{Node*p=newNode;p-data=a;rear-next=p;rear=p;rear-next=NULL;}DataType*ContactBook::Get(inti){Node*p=front;while(p){if(p-data.ID==i)return&p-data;p=p-next;}returnNULL;}北京邮电大学信息与通信工程学院第13页DataTypeContactBook::Delete(inti){Node*p=front;while(p){if(p-next-data.ID==i)break;p=p-next;}Node*q=p-next;//q指针指向要删除的成员if(q){DataTypex=q-data;//保存成员数据p-next=q-next;deleteq;cout删除成功！endl;returnx;}else{cout该成员不存在！endl;}}voidContactBook::Modify(DataTypea,inti){DataType*p=Get(i);*p=a;}voidContactBook::printList(){cout您的通讯录成员如下：endl;cout********************endl;Node*p=front-next;while(p){coutp-data.IDp-data.namep-data.chp-data.phonep-data.addrendl;cout********************endl;p=p-next;}北京邮电大学信息与通信工程学院第14页}ContactBook::~ContactBook(){Node*p=front;while(p){front=p;p=p-next;deletefront;}}voidmain(){cout欢迎使用通讯录管理系统endl;DataTypea[3]={{1001,张三,'m',13518800000,北京},{1002,李四,'f',13518802020,海南},{1003,王五,'m',15501010101,天津}};ContactBookTest(a,3);//初始化通讯录intno;do{cout1.建立我的通讯录endl;cout2.增加通讯录成员endl;cout3.查找通讯录成员endl;cout4.修改通讯录成员endl;cout5.删除通讯录成员endl;cout6.查看通讯录成员endl;cout0.退出系统endl;cout请输入数字选择：;cinno;switch(no){case1:cout建立成功！endl;cout********************endl;break;case2:cout请输入成员ID，姓名，性别，电话号码，地址endl;DataTypex;cinx.IDx.namex.chx.phonex.addr;Test.Add(x);cout添加成功！endl;cout********************endl;北京邮电大学信息与通信工程学院第15页break;case3:cout请输入要查找成员的ID：endl;intg;cing;Test.Get(g);if(Test.Get(g)){cout该用户信息如下：endl;coutTest.Get(g)-IDT