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

北京邮电大学信息与通信工程学院第16页北京邮电大学电信工程学院第1页数据结构实验报告实验名称：实验———线性表学生姓名：班级：班内序号：学号：日期：实验要求1.1实验目的通过选择下面四个题目之一进行实现，掌握如下内容：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力1.2实验内容利用线性表实现一个通讯录管理，通信录的数据格式如下： structDataType{ intID; //编号charname[10]; //姓名 charch; //性别 charphone[13]; //电话 charaddr[31]; //地址};具体要求实现通讯录的建立、增加、删除、修改、查询等功能能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。能够保存每次更新的数据（选作）能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作）编写测试main()函数测试线性表的正确性程序分析通过编程完成通讯录管理系统，实现建立、增加、修改、查找、删除、输出等一般功能，每个数据元素包含成员的ID、姓名、电话、住址等基本信息。本程序使用链表的功能，以C++语言为基础编写。对于本通讯录管理系统的建立，需要了解并掌握链表的算法与设计方法，综合运用所学知识完成。datanext2.1存储结构节点结构:存储结构：带头结点和尾节点的单链表reara[0]a[n-1]^front2.2关键算法分析通讯录系统图2.2.1通讯录的建立伪代码：在堆栈中申请新的节点新节点的数据为a[i]将新节点添加到链表修改尾指针全部插入后最后一个节点的指针域设为空代码实现：ContactBook::ContactBook(DataTypea[],intn){front=newNode; rear=newNode; rear=front; for(inti=0;i<n;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查找成员伪代码：初始化指针p指向头指针循环直到匹配到ID或为p为空找到则返回p的位置找不到则返回空指针代码实现：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删除成员伪代码：初始化指针p指向头指针循环匹配ID找到要删除的成员的前一个节点初始化指针q指向要删除的成员保存q的数据p指向q的下一节点释放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的next deleteq; cout<<"删除成功！"<<endl; returnx; } else { 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) { 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.总结通过本实验，巩固了我对链表的理解，学会了使用线性表解决一些实际的问题。但实验中还是有一些问题暴露了出来。比如一开始在调试的时候，打印成员时出现了如下截图中的问题。经过分析，才知道原来初始化指针p的时候指向了头指针并打印了出来，修改后p应该指向头指针的next域。调试中诸如这样的问题并不少见，也就是内存错误。本实验还要求我们学会对异常操作进行处理，本程序中也对该要求做了相关改进，比如要求“请输入数字选择”时，对于输入不合理的数字或字符都有相应的提示、处理。本程序的不足之处有二。一是查找用户时只能进行ID匹配查找，而不能对其他信息进行匹配查找。二是没加入读取和保存联系人的功能，该功能可以通过使用文件流，将联系人信息输出到指定文件中保存，并且可以读取后进行操作。附源程序：#include<iostream>usingnamespacestd;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;};ContactBook::ContactBook(){ front=newNode; rear=newNode; front->next=NULL; rear=front;}ContactBook::ContactBook(DataTypea[],intn){ front=newNode; rear=newNode; rear=front; for(inti=0;i<n;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;}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) { cout<<p->data.ID<<""<<p-><<"" <<p->data.ch<<""<<p->data.phone<<"" <<p->data.addr<<endl; cout<<"********************"<<endl; p=p->next; }}ContactBook::~ContactBook(){ Node*p=front; while(p) { front=p; p=p->next; deletefront; }}voidmain(){cout<<"欢迎使用通讯录管理系统"<<endl; DataTypea[3]={{1001,"张三",'m',,"北京"}, {1002,"李四",'f',,"海南"}, {1003,"王五",'m',,"天津"}}; ContactBookTest(a,3);//初始化通讯录 intno; do{ cout<<"1.建立我的通讯录"<<endl; cout<<"2.增加通讯录成员"<<endl; cout<<"3.查找通讯录成员"<<endl; cout<<"4.修改通讯录成员"<<endl; cout<<"5.删除通讯录成员"<<endl; cout<<"6.查看通讯录成员"<<endl; cout<<"0.退出系统"<<endl; cout<<"请输入数字选择："; cin>>no; switch(no) { case1: cout<<"建立成功！"<<endl;cout<<"********************"<<endl; break; case2: cout<<"请输入成员ID，姓名，性别，电话号码，地址"<<endl; DataTypex; cin>>x.ID>>>>x.ch>>x.phone>>x.addr; Test.Add(x); cout<<"添加成功！"<<endl;cout<<"********************"<<endl; break; case3: cout<<"请输入要查找成员的ID："<<endl; intg; cin>>g; Test.Get(g); if(Test.Get(g)) { cout<<"该用户信息如下："<<endl; cout<<Test.Get(g)->ID<<""<<Test.Get(g)->name<<"" <<Test.Get(g)->ch<<""<<Test.Get(g)->phone<<"" <<Test.Get(g)->addr<<endl; } else cout<<"该用户不存在!"; cout<<"********************"<<endl; break; case4: cout<<"请输入要修改成员的ID:"; intm; cin>>m; if(Test.Get(m)) { cout<<"请输入修改后成员的ID，姓名，性别，手机号码，地址："<<endl; DataTypex; cin>>x.ID>>>>x.ch>>x.phone>>x.addr; Test.Modify(x,m); cout<<"修改成功！"<<endl; } else cout<<"该成员不存在！"<<endl;cout<<"********************"<<endl; break; case5: cout<<"请输入要删除成员的ID："<<en