线表的基本操作及其应用.doc

线性表的基本操作及其应用一、实验目的1、帮助学生复习C+语言程序设计中的知识。2、熟悉线性表的逻辑结构。3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。二、实验内容单链表的基本操作问题描述实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。基本要求（1）依次从键盘读入数据，建立带头结点的单链表； （2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。 三、概要设计开始建立带头结点的元素 为了实现上述程序功能，应该选择线性链表的链式存储，而总体设计如下：查找第i个元素改变元素插入元素删除元素清除链表求链表的产度显示链表的元素各操作的具体函数实现：1. 用尾插法建立带头结点的链表可任意输入元素（char 型）,void CreatList(LinkList &L)/LinkList p; L=(LinkList)malloc(sizeof(LNode);int n=0,j=0;L-next=NULL;coutn;for(int i=n;i0;i-)LinkList p;p=(LinkList)malloc(sizeof(LNode);cout请输入一个节点数据:p-data;p-next=L-next;L-next=p; Length+;/每增加一个数据，Length加一2. 清空链表分析链表为空时，输出为空；当链表不为空时，清空链表，并输出原来的链表已经被清空!的字样告诉操作者，链表已为空了int ClearList(LinkList &L) if(L-next=NULL)coutnext;while(p) q=p; p=p-next; - Length; delete q; cout原来的链表已经被清空!endl; return OK;3. 求链表的长度在建立链表是已经用Length着个全局变量记载建立的结点的个数，即链表的长度用coutLength就可以得到链表的长度：int Listlength(LinkList L)cout链表长度为：Lengthnext; cout链表中的数据依次为:t; while(p) coutdatanext; 5. 从链表中查找元素用函数GetElem_L(LinkList L)来实现该功能。先输入要查找的元素的位置，再判断是否在有效区间里，如果是的话，就用字母e返回并输出，主要步骤为：if(iLength) cout想要得到的元素的位置超过链表的长度endl; return ERROR; else if(L=NULL) cout链表为空next;int j=1;while(p&jnext;+j;if(!p)coutdata;cout e data;6. 向链表中插入元素这个功能是通过函数ListInsert_L(LinkList &L)实现的。首先要判断要插入的位置i是否在有效的区间里，如果是的话，接下来要找到第i-1的位置，然后是指针的一些操作，最主要的步骤是：cout想要插入的元素:e; LinkList p,s; p=L; while(jnext; j+;if(!p|ji-1)coutdata=e; s-next=p-next;p-next=s; Length+;cout插入成功!;7. 从链表中删除元素这个功能在某种程度上与插入元素的步骤有点相似，也是先判断链表是否为空接下来是判断要删除的元素的位置i是否在有效地区间里，是的或在执行删除的功能。主要步骤如下：LinkList p,q;p=L; while(p&jnext;+j;if(!p|ji-1)coutnext;p-next=q-next;e=q-data;free(q);Length-;coute next;int j=1;while(p&jnext;+j;if(!p|ji)cout要改变的第i个元素不存在;coute;p-data=e; 在函数结尾又添加了一个菜单函数，便于各种函数的操作:；void menu()cout*我的链表*endl;cout1.初始化并创建链表!endl; cout2.清空链表!endl; cout3.求链表长度!endl; cout4.遍历链表并输出每个节点的数据!endl;cout5.从链表中查找元素!endl; cout6.向链表中插入元素!endl; cout7. 从链表中删除元素!endl; cout8. 改变元素!endl;cout9.其他键退出 !endl;四、主函数的调用过程及测试结