作。 能够保存每次更新的数据（选作） 能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作） 编写测试 main()函数测试线性表的正确性
第 1页
北京邮电大学信息与通信工程学院
2. 程序分析
通过编程完成通讯录管理系统，实现建立、增加、修改、查找、删除、输出等一般功能， 每个数据元素包含成员的 ID、姓名、电话、住址等基本信息。本程序使用链表的功能，以 C++语言为基础编写。对于本通讯录管理系统的建立，需要了解并掌握链表的算法与设计方 法，综合运用所学知识完成。
p=p->next; } return NULL; }
第 12页
北京邮电大学信息与通信工程学院
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; cout<<"删除成功！"<<endl; return x; } else { cout<<"该成员不存在！"<<endl; } }
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->data;
时间复杂度=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; }
第 11页
北京邮电大学信息与通信工程学院
ContactBook::ContactBook() {
front=new Node; rear=new Node; front->next=NULL; rear=front; }
ContactBook::ContactBook(DataType a[],int n) {
北京邮电大学信： 实验———线性表 学生姓名： 班 级： 班内序号： 学 号：
日 期：实验要求
1.1 实验目的
通过选择下面四个题目之一进行实现，掌握如下内容： 熟悉 C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力
{
DataType data;
//数据
struct Node * next; //指针指向下一节点
};
class ContactBook { public:
ContactBook();//默认构造函数 ContactBook(DataType a[],int n);//构造函数 void Add(DataType a); //增加成员 DataType Delete(int i);//删除成员 DataType *Get(int i);//查找成员 void Modify(DataType a,int i);//修改成员 void printList();//打印所有成员 ~ContactBook();//析构函数 private: Node* front; Node* rear; };
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; }
void ContactBook::Add(DataType a)//尾插法 {
4. 总结
通过本实验，巩固了我对链表的理解，学会了使用线性表解决一些实际的问题。但实验 中还是有一些问题暴露了出来。
比如一开始在调试的时候，打印成员时出现了如下截图中的问题。
经过分析，才知道原来初始化指针 p 的时候指向了头指针并打印了出来，修改后 p 应该指向 头指针的 next 域。调试中诸如这样的问题并不少见，也就是内存错误。
2.1 存储结构
节点结
构:
data next
存储结构：带头结点和尾节点的单链表
rear
front
a[0]
a[n-1] ^
2.2 关键算法分析
通讯录系统图
2.2.1 通讯录的建立 伪代码： 1. 在堆栈中申请新的节点 2. 新节点的数据为 a[i] 3. 将新节点添加到链表 4. 修改尾指针 5. 全部插入后最后一个节点的指针域设为空
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 的 next delete q; cout<<"删除成功！"<<endl; return x; } else { cout<<"该成员不存在！"<<endl; } }
Node* p=front; while(p) {
if(p->data.ID==i) return &p->data;
p=p->next; } return NULL; }
//ID 匹配模式查找 //找到则返回 p 的地址
//找不到则返回空
时间复杂度=o(n)
2.2.4 删除成员 伪代码：
1. 初始化指针 p 指向头指针 2. 循环匹配 ID 找到要删除的成员的前一个节点 3. 初始化指针 q 指向要删除的成员 4. 保存 q 的数据 5. p 指向 q 的下一节点 6. 释放 q 节点 代码实现：
{1002,"李四",'f',"13518802020","海南"}, {1003,"王五",'m',"15501010101","天津"}}; ContactBook Test(a,3);//初始化通讯录 int no; 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) { case 1: cout<<"建立成功！"<<endl; cout<<"********************"<<endl; break; case 2: cout<<"请输入成员 ID，姓名，性别，电话号码，地址"<<endl; DataType x; cin>>x.ID>>>>x.ch>>x.phone>>x.addr; Test.Add(x); cout<<"添加成功！"<<endl; cout<<"********************"<<endl;
第 4页
北京邮电大学信息与通信工程学院
时间复杂度=o(n)
2.2.5 修改成员 先调用查询模块，找到并打印用户信息，然后依次修改成员信息
代码实现： void ContactBook::Modify(DataType a,int i) {
DataType* p=Get(i); *p=a; }
时间复杂度=o(n)
附源程序： #include<iostream> using namespace std;
struct DataType {
int ID; char name[10]; char ch; char phone[13]; char addr[31]; };
//ID //姓名
//性别 //电话
//地址
struct Node
退出 是
结束
图 2 流程图示意图