《北邮数据结构实验一通讯录实验报告》由会员分享,可在线阅读,更多相关《北邮数据结构实验一通讯录实验报告(16页珍藏版)》请在金锄头文库上搜索。
1、北京邮电大学信息与通信工程学院第 1页数据结构实验报告实验名称: 实验线性表学生姓名:班级:班内序号:学号:日期:实验要求1.1 实验目的通过选择下面四个题目之一进行实现,掌握如下内容:熟悉 C+语言的基本编程方法,掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力1.2 实验内容 利用线性表实现一个通讯录管理,通信录的数据格式如下: struct DataType int ID;/编号 char name10;/姓名 char ch;/性别 char phone13;/电话 char addr31;/地址 ;1.3 具体要求实
2、现通讯录的建立、增加、删除、修改、查询等功能能够实现简单的菜单交互,即可以根据用户输入的命令,选择不同的操作。能够保存每次更新的数据(选作)能够进行通讯录分类,比如班级类、好友类、黑名单等等(选作)编写测试 main()函数测试线性表的正确性北京邮电大学信息与通信工程学院第 2页2. 程序分析通过编程完成通讯录管理系统,实现建立、增加、修改、查找、删除、输出等一般功能, 每个数据元素包含成员的 ID、姓名、电话、住址等基本信息。本程序使用链表的功能,以 C+语言为基础编写。对于本通讯录管理系统的建立,需要了解并掌握链表的算法与设计方 法,综合运用所学知识完成。2.1 存储结构节 点 结构:存储
3、结构:带头结点和尾节点的单链表rearfront2.2 关键算法分析通讯录系统图2.2.1 通讯录的建立 伪代码: 1.在堆栈中申请新的节点 2.新节点的数据为 ai 3.将新节点添加到链表 4.修改尾指针 5.全部插入后最后一个节点的指针域设为空datanexta0an-1北京邮电大学信息与通信工程学院第 3页代码实现: ContactBook:ContactBook(DataType a,int n) front=new Node; rear=new Node; rear=front; for(int i=0;idata=ai; rear-next=p; rear=p; rear-next
4、=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) 北京邮电大学信息与通信工程学院第 4页
5、Node* p=front; while(p) if(p-data.ID=i)/ID 匹配模式查找 return /找到则返回 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-da
6、ta.ID=i)break; p=p-next; Node* q=p-next;/q 指针指向要删除的成员 if(q) DataType x=q-data;/保存成员数据 p-next=q-next;/p 的 next 指向 q 的 next delete q; coutnext; while(p) coutdata.IDdata.namedata.chdata.phonedata.addrnext; 时间复杂度=o(n)3.程序运行结果3.1 主程序流程图开始创建通讯录类对象北京邮电大学信息与通信工程学院第 6页否是图 2 流程图示意图3.2 测试截图 3.2.1 建立通讯录初始化创建删除成
7、员添加成员查找成员打印成员修改成员退出退出结束北京邮电大学信息与通信工程学院第 7页3.2.2 增加成员3.3.3 查找成员北京邮电大学信息与通信工程学院第 8页3.3.4 修改成员3.3.5 删除成员北京邮电大学信息与通信工程学院第 9页3.3.6 打印成员3.3.7 退出北京邮电大学信息与通信工程学院第 10页4.总结通过本实验,巩固了我对链表的理解,学会了使用线性表解决一些实际的问题。但实验 中还是有一些问题暴露了出来。 比 如 一 开 始 在 调 试 的 时 候 , 打 印 成 员 时 出 现 了 如 下 截 图 中 的 问 题 。经过分析, 才知道原来初始化指针 p 的时候指向了头指
8、针并打印了出来, 修改后 p 应该指向 头指针的 next 域。调试中诸如这样的问题并不少见,也就是内存错误。北京邮电大学信息与通信工程学院第 11页本实验还要求我们学会对异常操作进行处理, 本程序中也对该要求做了相关改进, 比如 要求“请输入数字选择”时,对于输入不合理的数字或字符都有相应的提示、处理。 本程序的不足之处有二。一是查找用户时只能进行 ID 匹配查找,而不能对其他信息进 行匹配查找。二是没加入读取和保存联系人的功能,该功能可以通过使用文件流,将联系人 信息输出到指定文件中保存,并且可以读取后进行操作。附源程序: #include using namespace std;stru
9、ct DataType int ID;/ID char name10;/姓名 char ch;/性别 char phone13;/电话 char addr31;/地址 ;struct Node DataType data;/数据 struct Node * next; /指针指向下一节点 ;class ContactBook public: ContactBook();/默认构造函数 ContactBook(DataType a,int n);/构造函数 void Add(DataType a);/增加成员 DataType Delete(int i);/删除成员 DataType *Get(
10、int i);/查找成员 void Modify(DataType a,int i);/修改成员 void printList();/打印所有成员 ContactBook();/析构函数 private: Node* front; Node* rear; ;北京邮电大学信息与通信工程学院第 12页ContactBook:ContactBook() front=new Node; rear=new Node; front-next=NULL; rear=front; ContactBook:ContactBook(DataType a,int n) front=new Node; rear=ne
11、w Node; rear=front; for(int i=0;idata=ai; rear-next=p; rear=p; rear-next=NULL; void ContactBook:Add(DataType a)/尾插法 Node* p=new Node; p-data=a; rear-next=p; rear=p; rear-next=NULL; DataType* ContactBook:Get(int i) Node* p=front; while(p) if(p-data.ID=i) return p=p-next; return NULL; 北京邮电大学信息与通信工程学院第
12、 13页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; delete q; coutnext; while(p) coutdata.IDdata.namedata.chdata.phonedata.addrnext; 北京邮电大学信息与通信工程学院第 14页ContactBook:ContactBook
13、() Node* p=front; while(p) front=p; p=p-next; delete front; void main() coutno; switch (no) case 1: coutx.IDx.namex.chx.phonex.addr; Test.Add(x); coutg; Test.Get(g); if(Test.Get(g) coutIDnamechphoneaddrm; if(Test.Get(m) coutx.IDx.namex.chx.phonex.addr; Test.Modify(x,m); coutd; if(Test.Get(d) coutIDname chphone addryn; if(yn=y|yn=y) Test.Delete(d); else cout“取消删除!“endl; else cout“该成员不存在!“endl; cout“*“endl; break; case 6: Test.printList(); cout“*“endl; break; case 0: cout“退出成功!“endl; cout“*“endl; break; default: cout“操作有误!“endl; cout“*“endl; break; while(no!=0);