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

实验一 线性表的基本操作及其应用 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、实验内容 本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！ ? 题目一：单链表的基本操作（必做题 *） 题目二：约瑟夫环（**） [问题描述] 实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。 [基本要求] （1）依次从键盘读入数据，建立带头结点的单链表； （2）输出单链表中的数据元素 （3）求单链表的长度； （4）根据指定条件能够取元素和修改元素； （5）实现在指定位置插入和删除元素的功能。 [测试数据] 由学生任意指定。 三、算法设计 1.算法思想： 主要设计了一个包含数据和指针域的结点。 Data *next 主要思想： 插入： 删除： 四、本函数包含八个模块 1.主函数int main() :初始化一个链表L，显示菜单，主要语句：switch语句，while语句，goto语句。 2.创建并输入链表数据linklist createlist（），在该函数中创建头结点，并输入结点上的数据。 伪代码：while（当x!=00） { p = new list; p-data = x; p-next = NULL; q-next = p; q = p; } 3.显示链表数据void show（linklist L） 1）先判断是否是空表，再逐个寻找想要的元素。 2）主要代码： while(p) { coutp-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）当0ilength时，遍历链表，找到第i个元素。 2）主要代码： while(pji) { j++; p = p-next; } 6.改变链表数据int changedata(linklist L,int e,int d) 1）找到要修改的值e，再把d赋值给e. 2)主要代码： while(pp-data!=e) { p = p-next; } if(!p) return ERROR; p-data = d; 7.插入一个结点linklist insertlist(linklist L,int i,int e) 1)因为要插入第i个元素，所以要先找到第i-1个元素，在i-1后面插入。 2）主要代码： s-data = e; s-next = p-next ; p-next = s; 8.删除一个结点linklist deletelist(linklist L,int i) 1）同插入差不多，先找到第i-1个元素，然后再把i-1结点指针域指向原本指向结点的下一个，把中间那个删除，再free，释放空间， 主要代码： q = p-next; p-next =q-next; free(q); 五、实验过程 图1、登陆界面 图2、功能键1，2，3，4的实现 图3、功能键5、6的实现 图4、功能键7、0的实现 六、调试及感受 又是一次课设时，每次写程序总会遇到大大小小的毛病，就不断的调试调试，觉得写代码是需要很大的耐心，一直琢磨，一直分析，一直改，直至完美。可是当代码运行到自己想要的程度时，内心是那么的自豪，那么的傲娇，那么的兴奋，仿佛心长了翅膀似的，飞到高空翱翔去了，呵呵，感觉不错。不过，我希望自己下次不用再借鉴网上的代码，就能够自己迎仞有余，加油，我可以的！ 并且谢谢老师的教导，老师您辛苦了！！！ 七、源代码 #includeiostream #includestdio.h #includemalloc.h #define ERROR -1; using namespace std; typedef struct node{ int data; node *next; }list,*linklist; linklist createlist()//输入链表数据 { linklist head; head = new list; h