数据结构线性表实验报告.docVIP

一、实验目的和要求 （1）理解线性表的逻辑结构特性。 （2）深入掌握线性表的两种存储方法，即顺序表和链表。体会这两种存储结构之间的差异。 （3）重点掌握顺序表和链表上各种基本运算的实现。 （4）综合运用线性表解决一些复杂的实际问题。 二、实验内容 实验2.1 编写一个程序algo2-1.cpp，实现顺序表的各种基本运算（假设顺序表的元素类型为char）,并在此基础上设计一个程序exp2-1.cpp，完成如下功能： 初始化顺序表L； 采用尾插法依次插入元素a，b，c，d，e； 输出顺序表L; 输出顺序表L长度； 判断顺序表L是否为空； 输出顺序表L的第三个元素； 输出元素a的位置； 在第4个元素位置上插入元素f； 输出顺序表L； 删除L的第3个元素； 输出顺序表L； 释放顺序表L。 实验2.2 编写一个程序algo2-2.cpp，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计一个程序exp2-2.cpp，完成如下功能： 初始化单链表h； 采用尾插法依次插入元素a，b，c，d，e； 输出单链表h; 输出单链表h长度； 判断单链表h是否为空； 输出单链表h的第三个元素； 输出元素a的位置； 在第4个元素位置上插入元素f； 输出单链表h； 删除L的第3个元素； 输出单链表h；、 释放单链表h。 释放顺序表L。 实验2.3 编写一个程序algo2-3.cpp，实现双链表的各种基本运算（假设双链表的元素类型为char），并在此基础上设计一个程序exp2-3.cpp，完成如下功能： 初始化双链表h； 采用尾插法依次插入元素a，b，c，d，e； 输出双链表h; 输出双链表h长度； 判断双链表h是否为空； 输出双链表h的第三个元素； 输出元素a的位置； 在第4个元素位置上插入元素f； 输出双链表h； 删除L的第3个元素； 输出双链表h；、 释放双链表h。 三、实验过程描述 实验2.1 程序algo2-1.cpp如下： 设计如下exp2-1.cpp主程序： 程序执行结果如下： 实验2.2 程序algo2-2.cpp如下： 设计如下exp2-2.cpp主程序： 程序执行结果如下： 实验2.3 程序algo2-2.cpp如下： 设计exp2-3.cpp主程序： 程序执行结果如下： 四、实验结果分析 实验1.1 对于prime(n)，其时间复杂度为O()，由于偶数不可能是素数，所以程序中只对奇数进行素数的判断。因此，上述程序的时间复杂度较低。 实验1.2 func(n)的时间复杂度为O(len(n))，len(n)为正整数n的位数。程序的时间复杂度也为O(len(n))。 实验1.3 在func(s)算法中，for循环语句的执行次数为n/2（n为字符串s的长度），则它的时间复杂度为O(n)。程序的时间复杂度也为O(n)。