南昌大学数据结构实验

1目录实验1：线性表及其应用...............................................................................................实验2：栈.......................................................................................................................实验3：队列...................................................................................................................实验4：稀疏矩阵...........................................................................................................2实验1：线性表及其应用一、实验目的帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。二、问题描述1.构造一个空的线性表L。2.在线性表L的第i个元素之前插入新的元素e；3.在线性表L中删除第i个元素，并用e返回其值。三、实验要求1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境五、实验代码#ifndefSQLIST_H#defineSQLIST_H#includeD:\李雪刚\非循环单链表\SqList.h#endiftemplatetypenameElemTypeclassMySqList:publicSqListElemType{public:voidRandom();voiddisplay();voidkai_1(MySqListElemType&Sql);voidkai_2(MySqListElemType&Sql);voidkai_3(MySqListElemType&Sql);MySqList(ElemType*p,intnsize);3};//输出线性表templatetypenameElemTypevoidMySqListElemType::display(){inti;intn=getLength();printf(此时的线性表为\n);for(i=1;i=n;i++)cout[i];coutendl;for(i=0;in;i++)coutelem[i];coutendl;}//删除第i个元素templatetypenameElemTypevoidkai_1(MySqListElemType&Sql){cout*************删除第i个元素*****************endl;inti;inte;cout请输入要删去的序号:;cini;Sql.deleteElem(i,e);Sql.display();}//取第i个元素templatetypenameElemTypevoidkai_2(MySqListElemType&Sql){cout*****************取第i个元素*******************endl;inti;inte;cout请输入要取的数的序号:;cini;Sql.getElem(i,e);4cout[i]endl;couteendl;}//在第i个元素前插入一个元素templatetypenameElemTypevoidkai_3(MySqListElemType&Sql){cout*****在第i个元素前插入一个元素*****endl;inti;inte;cout插入前一个元素的序号:;cini;cout要插入的元素：;cine;Sql.insert(i,e);Sql.display();}templatetypenameElemTypeMySqListElemType::MySqList(ElemType*p,intnsize){elem=newElemType[LIST_MAX_SIZE];assert(elem!=0);n=nsize;for(inti=0;in;i++)elem[i]=p[i];}#includeiostreamusingnamespacestd;#ifndefMYSQLIST_H#defineMYSQLIST_H#includeD:\李雪刚\非循环单链表\MySqList.h#endifvoidmain(){intdata1[]={36,45,23,11};MySqListintSql(data1,sizeof(data1)/sizeof(int));Sql.display();5kai_1(Sql);kai_2(Sql);kai_3(Sql);}六、实验结果七、实验感想由于这个线性表是第一个实验，刚开始的时候，就只是输入书上面的基类程序，后面觉得摸不着头脑，特别是派生类和主程序的编写，感觉一头雾水的。不明白这些程序编写的原因，更加上刚开始并没有接触C++编程，后面自己慢慢琢磨，与同学多交流，还是把这个实验给做出来了。虽然花的时间比较多，但自己还是很有收获的，这毕竟是第一个实验，正所谓万事开头难。正通过这个实验的完成，我对后面的时候才打下了基础，能够循循渐进地了解这个课程，以及这些编程的技巧。6实验2：栈一、实验目的深入了解栈，学会在实际问题下灵活运用它们。二、问题描述表达式求值运算是实现程序设计语言的基本问题之一，也是栈应用的一个典型例子。设计并演示用算符优先级对算术表达式的求解过程。三、实验要求1、算法优先级别如下：'+','-','*','/','(',')','#''+''','','','','','','','-''','','','','','','','*''','','','','','','','/''','','','','','','','(''','','','','','=','',')''','','','','','','','#''','','','','','','='2、以字符序列的形式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境六、实验代码#ifndefSQSTACK_H#defineSQSTACK_H#includeSqStack.h#endiftemplatetypenameElemTypeclassMySqStack:publicSqStackElemType{public:MySqStack(ElemType*p,intnsize);MySqStack(){};voiddisplay();7};templatetypenameElemTypevoidMySqStackElemType::display(){if(isEmpty())cout空endl;else{inti;intlength=getLength();for(i=0;ilength;i++)cout*(base+i);coutendl;for(i=0;i=length;++i){if(i==0)cout↑;elseif(i==length)cout↑endl;elsecout;}for(i=0;i=length;++i){if(i==0)coutbase;elseif(i==length)couttop;elsecout;}coutendl;}}templatetypenameElemTypeMySqStackElemType::MySqStack(ElemType*p,intnsize){int*next=newElemType[100];assert(next!=0);intn=nsize;8if(n0)n=0;for(inti=0;in;i++){next[i]=p[i];}for(intj=0;jn;++j)*(base+j)=next[j];top=base+n;}#includeassert.h#includeiostreamusingnamespacestd;#ifndefMYSQSTACK_H#defineMYSQSTACK_H#includeMySqStack.h#endiftemplateMySqStackint;voidmain(){inte;intdata[]={43,87,67,77,93,23,85,45};MySqStackintstack1(data,sizeof(data)/sizeof(int));cout当前顺序栈中的元素为：endl;stack1.display();coutendl;cout**********操作1：弹出栈顶元素***********endl;intm;stack1.pop(m);cout弹出的栈顶元素为：mendlendl;cout弹出后顺序栈中的元素为：endl;stack1.display();coutendl;cout*****************************************endl;cout**********操作2：判断栈是否为空************endl;if(stack1.isEmpty())cout顺序栈为空;9elsecout顺序栈不为空;coutendlendl;cout当前顺序栈中的元素为：endl;stack1.display();coutendl;cout*****************************************endl;cout**********操作3：读取栈顶元素************endl;intn;stack1.getTop(n);cout读栈顶元素为：nendlendl;cout读取栈顶元素后，顺序栈中的元素为：endl;stack1.display();coutendl;cout*****************************************endl;cout**********操作4：栈顶压入元素***********endl;cout请输入你要在栈顶压入的元素：;cine;coutendl;stack1.push(e);cout压入元素e后，新顺序栈如下所示：endl;stack1.display();coutendl;cout*****************************************endl;}10七、实验结果八、实验心得栈的这个实验与前面的顺序表不同，其中涉及的出栈和入栈以及读取栈顶元素，所设计与以前的实验不同，而且栈是一个操作受限的顺序表，在编程上也有很大的不同，所以说这个不是以前那种编写方法，在编写方法上有点困难，但最后还是能够一步一步的解决问题，特别是最