实验一 线性表的基本操作及其应用.doc

------------------------------------------------------------------------------------------------ ——————————————————————————————————————实验一线性表的基本操作及其应用中原工学院计算机学院网络 13 级卓越班郑仙玉学号: 201300824401 1 中原工学院计算机学院网络 13 级卓越班郑仙玉学号: 201300824401 一、实验目的 1 、帮助读者复****C++ 语言程序设计中的知识。 2 、熟悉线性表的逻辑结构。 3 、熟悉线性表的基本运算在两种存储结构上的实现,其中以熟悉链表的操作为侧重点。二、实验内容本次实验提供 4 个题目,每个题目都标有难度系数, * 越多难度越大, 学生可以根据自己的情况选做, 其中题目一是必做题, 其它选作! ? 题目一:单链表的基本操作(必做题*) 题目二:约瑟夫环( **) [ 问题描述] 实现带头结点的单链表的建立、求长度,取元素、修改元素、插入、删除等单链表的基本操作。[ 基本要求](1 )依次从键盘读入数据,建立带头结点的单链表; ------------------------------------------------------------------------------------------------ ——————————————————————————————————————(2 )输出单链表中的数据元素(3 )求单链表的长度; (4 )根据指定条件能够取元素和修改元素; (5 )实现在指定位置插入和删除元素的功能。[ 测试数据] 由学生任意指定。 2 中原工学院计算机学院网络 13 级卓越班郑仙玉学号: 201300824401 三、算法设计 1. 算法思想: 主要设计了一个包含数据和指针域的结点。删除: 四、本函数包含八个模块 1. 主函数 int main() : 初始化一个链表 L ,显示菜单,主要语句: switch 语句, while 语句, goto 语句。 2. 创建并输入链表数据 linklist createlist (), 在该函数中创建头结点,并输入结点上的数据。伪代码: while (当 x!=00 ) {p= new list; p->data = x; p->next = NULL; ------------------------------------------------------------------------------------------------ —————————————————————————————————————— 3 中原工学院计算机学院网络 13 级卓越班郑仙玉学号: 201300824401 } q->next = p;q= p; 3. 显示链表数据 void show ( linklist L) 1 )先判断是否是空表,再逐个寻找想要的元素。 2 )主要代码: while(p) {} cout<<p->data<<"\t"; p= p->next; 4. 获取链表长度 int getlength(linklist L) 1) 先判断是否为空,再遍历链表,算出链表长度。 2) 主要代码: while(p) {}p= p->next; length++; 5. 获取第 i 个元素 int getdata(linklist L, int i) 1 )当 0<i<length 时,遍历链表,找到第 i 个元素。 2 )主要代码: while(p&&j<i) {} 6. 改变链表数据 int changedata(linklist L,int e,int d) 1 )找到要修改的值 e ,再把 d 赋值给 e. j++; p= p->next; ------------------------------------------------------------------------------------------------ —————————————————————————————————————— 4 中原工学院计算机学院网络 13 级卓越班郑仙玉学号: 201300824401 2) 主要代码: while(p&&p->data!=e) {} if(!p) return ERROR; p= p->next; p->data = d; 7. 插入一个结点 linklist insertlist(linklist L,in