线性表的顺序存储结构.doc

实验一：线性表的顺序存储结构实验学时：2实验类型：验证一、实验目的： 1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；二、实验内容： 1输入一组整型数据，建立顺序表。2实现该线性表的删除。3、实现该线性表的插入。4实现线形表中数据的显示。5实现线性表数据的查找和定位5、编写一个主函数,调试上述算法。三、实验原理、方法和手段1. 根据实验内容编程，上机调试、得出正确的运行程序。2. 编译运行程序，观察运行情况和输出结果。3. 写出实验报告（包括源程序和运行结果）。四、实验条件运行Visual stadio 2010的微机一台五、实验步骤（程序清单）：/ 实验一.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include#include#includeusing namespace std;typedef int ElemType;struct ListElemType *list;int size;int MaxSize;void InitList(List &L,int n) /初始化线性表L.MaxSize =n+5;L.list=new ElemType L.MaxSize;if(L.list=NULL)cout动态可分配的存储空间已用完,退出运行!endl;exit(1);L.size=0;void InputList(List &L) /输入元素L.size =L.MaxSize-5; for(int i=0;iL.size;i+)cout请输入第i+1个元素:L.listi;void FindList(List &L) /查找位置if(L.size=0)cout线性表为空，查找失败！endl;return;elseint item;Find:coutitem;int i;for(i=0;iL.size;i+)if(L.listi=item)item=L.listi;cout查找成功！您所查找的数据 item 在第 i+1个位置=L.size)cout您所查找的数据不存在！endl;Find2:coutc;if(strlen(c)=1)if(c0=y)goto Find;else if(c0!=y&c0!=n)cout您输入的操作无效！;goto Find2;else return;else cout您输入的操作无效！请重新选择：;goto Find2;void DisplayList(List &L) /按位置查找元素if(L.size =0)cout线性表为空，查找失败！endl;return;elseint pos;Display:coutpos;if(posL.size)cout您输入的位置无效！endl;Display2:coutc;if(strlen(c)=1)if(c0=y)goto Display;else if(c0!=y&c0!=n)cout您输入的操作不合法！;goto Display2;else return;else cout您输入的操作不合法！;goto Display2;else cout您要查找的第 pos 个数据为 L.listpos-1endl;void ClearList(List &L) /清空线性表if(L.list!=NULL)delete L.list;L.list=NULL;L.MaxSize=0;L.size=0;cout清空成功！endl;void InsertList(List &L) /插入一个元素if(L.size=0)cout线性表为空，插入失败！endl;return;else Insert:coutpos;coutitem;if(posL.size+1)cout位置值无效！endl;Insert2:coutc;if(strlen(c)=1)if(c0=y)goto Insert;else if(c0!=y&c0!=n)cout您输入的操作无效！;goto Insert2;else return;elsecout您输入的操作无效！;goto Insert2;int i;if(pos=0)for(i=0;iL.size;i+)if(itemL.listi) break;pos=i+1;else if(pos=-1) pos=L.size+1;if(L.size=L.MaxSize)int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);if(L.list=NULL)cout动态可分配的存储空间已用完,退出运行!=pos-1;i-)L.listi+1=L.listi;L.listpos-1=item;L.size+;cout插入成功！endl;void DisplayAllList(List &L) /显示线性表数据if(L.size =0)cout线性表不存在，请先创建！endl;elsecoutSize=L.sizeMaxSize=L.MaxSizeendl;for(int i=0;iL.size;i+)coutL.listi ;coutendl;void DeleteList(List &L) /删除一个元素if(L.size=0)cout线性表为空,删除无效!endl;return;Delete:coutpos;ElemType item;if(posL.size)cout位置值无效!endl;Delete2:coutc;if(strlen(c)=1)if(c0=y)goto Delete;else if(c0!=y&c0!=n)cout您输入的操作不合法！;goto Delete2;return;elsecout您输入的操作不合法！;goto Delete2;int i;if (pos=0)coutitem;for(i=0;iL.size;i+ )if(item=L.listi) break;if(i=L.size) cout按查找删除，没有找到您要删除的元素！ endl;Delete3:coutc;if(strlen(c)=1)if(c0=y)goto Delete;else if(c0!=y&c0!=n)cout您输入的操作不合法！;goto Delete3;else return;elsecout您输入的操作不合法！;goto Delete3;pos=i+1;else if(pos=-1)pos=L.size;item=L.listpos-1;cout您要删除的元素 L.listpos-1已删除成功！endl;for(i=pos;iL.size ;i+)L.listi-1=L.list i;L.size-;if(float(L.size)/L.MaxSize10)int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2);L.MaxSize=L.MaxSize/2;void menu()List t;InitList(t,0);menu:cout欢迎进入线性表管理系统：endl;cout 1. 创建一个线性表endl;cout 2. 查找元素位置endl;cout 3. 按位置查找元素endl;cout 4. 插入一个元素endl;cout 5. 删除一个元素endl;cout 6. 清空该线性表endl;cout 7. 显示该线性表endl;cout 0. 退出系统endl;menu2:coutn;if(strlen(n)=1)if(n07)cout您输入的操作不合法，请重新选择！endl;goto menu2;elsecout您输入的操作不合法，请重新选择！endl;goto menu2;switch(n0)case 1:coutm;InitList(t,m);InputList(t);coutendl;goto menu;case 2:FindList(t);coutendl;goto menu;case 3:DisplayList(t);coutendl;goto menu;case 4:InsertList(t);coutendl;goto menu;case 5:DeleteList(t);coutendl;goto menu;case 6:ClearList(t);coutendl;goto menu;case 7:DisplayAllList(t);coutendl;goto menu;case 0:break;default:cout您输入的操作有误，请重新输入：;goto menu2;int _tmain(int argc, _TCHAR* argv)menu();6、 调试及运行：1.在未创建一个线性表前，选择其它操作会提示“线性表为空，操作打败”的提示，如图2. 选择操作【1】.创建一个线性表，并输入11，22，33，44.如图3. 选择操作【7】，显示线性表，便于查找元素位置。选择【2】查找元素位置操作，查找失败后会提示“是否继续查找？（y/n）：”，选择“y”,会继续查找操作；选择“n”会返回菜单；输入其它字符串，会提示“您输入的操作无效！请重新选择：是否继续查找？（y/n）:”。4.选择操作【3】按位置查找元素，当输入的位置无效时，会提示无效信息，询问是否继续操作，输入“y”，继续操作；输入“n”,跳回主菜单；输入其它信息时，会提示操作非法，并询问是否继续查找。查找成功后跳回主菜单。如图所示：5.（1）选择【4】插入操作，输入0，则把线性表视为有序表，键入元素后，按升插入到线性表的相应位置，插入前后如图所示：5. （2）选择【4】插入元素操作后，若键入n，则在指定位置插入键入的相应的元素，如果n值逾越线性表的范围，会提示“位置值无效”，并提示是否继续插入操作，键入正确的位置后，就会把键入的相应的元素插入到指定的位置。如在第2个位置插入元素99，插入前后如图所示：6. （1）选择【5】删除一个元素操作，系统会提示删除方式，键入0，则按查找元素并删除，若输入的元素在线性表没有，如输入12345，则会提示“按查找删除，没有找到您要删除的元素”，并提示是否继续删除，再次选择删除方式。正确选择操作后，若要删除99，键入99后，提示删除成功，显示线性表，观察前后线性表的变化，如图所示：6. （2）选择【5】删除一个元素操作，系统会提示删除方式，若选择按指定位置删除，就键入要删除元素的位置，若键入的位置逾越了线性表的范围，如键入12345，系统会提示“位置值无效”，并会提示是否继续删除操作。现要删除第2个元素，键入2后。显示经性表，对比前后线性表的变化，发现线性表中的第2个元素22已经删除。如图所示：7. 选择【6】清空线性表，将会清空已经存在的线性表，再进行其实操作会提示“线性表为空，操作无效！”，如选择【2】查找操作和【7】显示线性表操作，都会提示线性表为空，清空前后，如图所示：8. 在选择操作时，或输入不合法的选择，系统会提示“操作不合法，请重新选择！”。选择【0】退出系统，则退出管理系统。如图所示：7、 实验分析与总结：1. 为了能循环操作，编写了一个菜单函数，利用switch 和goto语句来实现跳转和循环，为了可能会在主