北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称： 实验一——线性表 学生姓名： 大学霸 班 级： xxxxxxxxxx 班内序号： xx 学 号： xxxxxxxxxx 日 期： 2012年11月1日

1． 实验要求

实验目的：

1. 学习指针，模板类，异常处理的使用； 2. 掌握线性表的操作实现方法；

3. 培养使用线性表解决实际问题的能力。 实验内容：

利用线性表实现一个通讯录管理，通信录的数据格式如下： struct DataType {

int ID; //编号 char name[10]; //姓名 char ch; //性别 char phone[13]; //电话 char addr[31]; //地址 };

具体要求：

1. 实现通信录的建立、增加、删除、修改、查询等功能

2. 能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作 3. 能够保存每次更新的数据

4. 编写main()函数测试操作的正确性

2. 程序分析

编程完成通讯录的一般性管理工作如通讯录中记录的增加、修改、查找、删除、输出等功能。每个记录包含姓名、电话号码、住址等个人基本信息。 用《数据结构》中的链表做数据结构结合c语言基本知识编写一个通讯录管理系统。本程序为使用方便，几乎不用特殊的命令，只需按提示输入即可，适合更多的用户使用。对于建立通讯录管理系统，则需了解并掌握数据结构与算法的设计方法,提高综合运用所学的理论知识和方法独立分析和解决问题的能力。

第1页

北京邮电大学信息与通信工程学院

2.1 存储结构

节点结构： data next

存储结构：带头结点和尾结点的单链表 front a[0] rear a[1] a[i-1] ^ 2.2 关键算法分析

本实验从整体上分为七大模块：（1）输入联系人信息；（2）添加联系人信息；（3）查找联系人信息；（4）查看联系人信息；（5）删除联系人信息；（6）修改联系人信息；（7）退出通讯录管理。

通讯录系统图 通讯通讯通讯通讯通讯 录的录的录的录的录的 建立 插入 查询 删除 输出

2.2.1通讯录的建立 伪代码：

1. 在堆中申请新的结点； 2. 新节点的数据域为a[i]； 3. 将新节点加入到链表中； 4. 修改尾指针；

5. 全部结点插入后需要将终结结点的指针域设为空。

C++实现：

ContactBook::ContactBook(DataType a[],int n)//尾插法 { front=new Node;

通讯录的管理 第2页

北京邮电大学信息与通信工程学院

rear=new Node; rear=front; //构造空单链表 for(int i=0;idata=a[i]; //写入数据域 rear->next=s; //将新节点加入到链表中 rear=s; //修改尾指针 } rear->next=NULL; //终端节点的指针域设为空 }

时间复杂度：o(n)

2.2.2通讯录的插入 伪代码：

插入为建立的一种特殊形式，即插入一个单独的结点，方法与上述类似

C++实现：

void ContactBook::Add(DataType a)//尾插法 { Node * s=new Node; s->data=a; rear->next=s; rear=s; rear->next=NULL; }

时间复杂度：o(1)

2.2.3按ID查找

查找操作是指用户输入要查找的用户的ID，系统该函数内找到该用户，返回用户数据域的指针，在主函数中输出该用户的全部信息。 伪代码：

1. 初始化工作指针p；

2. 循环以下操作直到p为空或找到用户

1. 如果p的数据等于i，则返回P的数据域指针； 2. P指针指向下一个节点； 3.若找不到返回空指针。

C++实现：

//通讯簿按ID查找

DataType * ContactBook::Get(int i) { Node * p=front->next; while(p)

第3页

北京邮电大学信息与通信工程学院

{ if(p->data.ID==i)return &(p->data); //根据ID找到被查元素，返回位置 p=p->next; } return NULL; //若找不到 ，返回空指针 }

时间复杂度：o(n)

2.2.4通讯录的删除

删除操作是指根据用户输入要删除用户的ID，找到该用户结点，返回该用户的数据域，删除此节点 伪代码：

1. 从第一个节点开始，查找到要删用户的的前一个用户节点，设P指向该节点； 2. 设q指向要删除的用户：q=p->next； 3. 摘链：p->next=q->next；

4. 保存q节点的数据域:x=q->data; 5. 释放q节点：deleteq；

要指出的是若在整个通讯录找不到该ID，直接跳过删除步骤，输出查无此人

C++实现：

DataType ContactBook::Delete(int i) { Node * p=front; while(p->next) { if(p->next->data.ID==i)break; //找到要删除的用户，跳出循环 p=p->next; } Node * q=p->next; //找到该用户 if(q) { p->next=q->next; DataType x=q->data; //记录用户信息 delete q; //删除用户 cout<<\ 删除成功！\ return x; } else{ cout<<\ 该用户不存在！\ } }

第4页