发布时间 : 星期六 文章北邮数据结构实验报告-线性表 - 图文更新完毕开始阅读
北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称： 实验1——线性表 学生姓名： 曲岩 班 级： 2014211120 班内序号： 08
学 号： 2014210569 日 期： 2015年11月20日
1．实验要求
? 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 ? 学习指针、模板类、异常处理的使用 ? 掌握线性表的操作的实现方法 ? 学习使用线性表解决实际问题的能力
2. 程序分析
包含一个头文件和测试cpp文件，头文件中存储ADT及相关操作，测试cpp文件中的main函数可以采用交互式或文件读入式输入，用以展示链表类功能。
2.1 存储结构
储存结构：单链表（带头节点）
（图1 单链表结构示意图）
ADT结构为一个包含基本存储结构的节点类，以及一个包含若干操作的链表类。其中，定义链表类是节点类的友元。
2.2 关键算法分析
【1.节点的删除T list
关键代码：
a. s=r->next; b. x=s->data;
c. r->next=r->next->next;
第1页
北京邮电大学信息与通信工程学院
d. delete s; e. length--; f. return x; 自然语言描述： a. 将目标节点的地址保存在s中 b. 将目标节点的数据保存在x中 c. 目标节点的前一个结点的next指向下一个节点（摘链） d. 通过s中保存的地址删除目标节点 e. 表长减一 f. 返回x中保存的数据值
（图1删除节点示意图）
时间复杂度： 寻找待删除节点O(n);删除操作O(1);
【2.节点的插入void list
关键代码：
a. for(int i=1;i<=n-1;i++)r=r->next; b. s->next=r->next; c. r->next=s; d. length++; 自然语言描述： a. 找到插入位置的前一个结点 b. 将待插入节点的next指向插入位置的下一个节点 c. 将插入位置的前一个结点的next指向待插入节点 d. 表长加一，插入完毕
（图2 插入节点示意图）
时间复杂度： 寻找待插入节点O(n);插入操作O(1);
【3.头插法建立链表node
关键代码：
第2页
北京邮电大学信息与通信工程学院
a. node
b. cin>>x; c. s->data=x;
d. s->next=head->next; e. head->next=s; 自然语言描述： a. 创建新节点 b. 读取新节点数据值 c. 赋值给新节点 d. 令新节点的next指向头结点的下一个节点 e. 令头结点的next指向新节点
（图3 头插法示意图）
时间复杂度：
O(n);
【4.尾插法建立链表node
关键代码：
a. node
b. cin>>x; c. s->data=x; d. r->next=s; e. r=s; 自然语言描述：
a. 创建新节点
b. 读取新节点数据值 c. 赋值给新节点
d. 尾指针的next指向新节点 e. 尾指针指向新节点
（图4 尾插法示意图）
时间复杂度： O(n);
【5.顺序插法建立链表node
关键代码：
第3页
北京邮电大学信息与通信工程学院
a. node
b. cin>>x; c. s->data=x;
d. node
e. for(int j=1;j<=length && s->data>r->next->data;j++)r=r->next; f. s->next=r->next; g. r->next=s; h. length++;
自然语言描述： a. 建立新节点 b. 读入新节点数据 c. 赋值给新节点 d. 新建r指针指向头结点
e. 从头结点开时，向后查找，直到找到第一个next->data的值大于新
节点data值的节点
fg.将s插入到该节点后面 h.表长加一 时间复杂度： 对于每个新节点，都要从头查找一遍之前构造的表，复杂度为O(n^2)
【6.按位查找T list
关键代码：
a. node
b. for(int i=1;i<=n;i++)r=r->next; c. return r->data;
自然语言描述： a. 新建r指针指向头结点 b. r向后移动n位 c. 返回当前r的data值
(此处也可设计成返回r，方便其它函数复用该函数) 时间复杂度： O(n);
2.3 其他
3. 程序运行结果
流程图：
第4页