实验2：链表的基本操作

实验名称： 链表的基本操作 成绩：

实验日期： 年 月 日 实验报告日期： 年 月 日

一、实验目的

1、复习C语言程序设计中结构体指针的知识。

2、掌握线性表的逻辑结构

3、掌握线性表的链式存储结构。

4、熟练掌握线性表的插入、删除等操作在链表上的实现。

二、实验内容

在Turbo C下完成“递增有序线性表的合并”。

三、实验要求

1、递增有序线性表的合并。

算法要求：

（1）合并后仍然是一个有序表，并且为递减有序。

（2）算法的时间复杂度为O(n+m)。(n,m分别为线性表的长度)

四、实验步骤、过程

1、算法分析

①为使算法的时间复杂度为O(n+m)只能采用“平移指针，一次扫描”的方法，于是设两个指针分别指向两个线性表表头。

②为使合并后仍为一个有序表，需对指针所指结点的数据域进行比较。

③要使合并后的有序表为递减有序表，比较后选出较小的一个将其从原链表中取出插入到新表的表首。

④指针后移，重复②，③步，直到其中一个表结束，将尚未结束表的元素依次取出插入新表。

⑤为减少头指针的变化，采用带有头结点的链表。

3、头文件与类型定义:

4、建立链表算法

5、有序链表合并算法

6、main()函数

六、实验小结和思考

八、实验评分

实验日期： 　 年 　 月 　日

链表的基本操作