北邮数据结构实验一通讯录实验报告内容.pdf

北京邮电大学信息与通信工程学院 数据结构实验报告 实验名称： 实验———线性表 学生姓名： 班 级： 班内序号： 学 号： 日 期：实验要求 1.1 实验目的 通过选择下面四个题目之一进行实现，掌握如下内容：  熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法  学习指针、模板类、异常处理的使用  掌握线性表的操作的实现方法  学习使用线性表解决实际问题的能力 1.2 实验内容 利用线性表实现一个通讯录管理，通信录的数据格式如下： structDataType { int ID; //编号 charname[10]; //姓名 char ch; //性别 charphone[13]; //电话 char addr[31]; //地址 }; 1.3 具体要求  实现通讯录的建立、增加、删除、修改、查询等功能  能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操 作。  能够保存每次更新的数据 （选作）  能够进行通讯录分类，比如班级类、好友类、黑名单等等 （选作）  编写测试main()函数测试线性表的正确性 1 第 页 北京邮电大学信息与通信工程学院 2. 程序分析 通过编程完成通讯录管理系统，实现建立、增加、修改、查找、删除、输出等一般功能， 每个数据元素包含成员的ID、姓名、电话、住址等基本信息。本程序使用链表的功能，以 C++语言为基础编写。对于本通讯录管理系统的建立，需要了解并掌握链表的算法与设计方 法，综合运用所学知识完成。 2.1 存储结构 节 点 结 构: data next 存储结构：带头结点和尾节点的单链表 rear front a[0] a[n-1] ^ 2.2 关键算法分析 通讯录系统图 2.2.1 通讯录的建立 伪代码： 1. 在堆栈中申请新的节点 2. 新节点的数据为a[i] 3. 将新节点添加到链表 4. 修改尾指针 5. 全部插入后最后一个节点的指针域设为空 2 第 页 北京邮电大学信息与通信工程学院 代码实现： ContactBook::ContactBook(DataTypea[],intn) { front newNode; rear newNode; rear front; for(int i 0;i<n;i++) //尾插法 { Node*p newNode; p->data a[i]; rear->next p; rear p; } rear->next NULL; } 时间复杂度 o(n) 2.2.2 添加新成员 伪代码：与通讯录的建立类似，通过尾插法实现 代码实现： void ContactBook::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. 找不到则返回空指针 代码实现： DataType