重 庆 大 学基础性实践环节(数据结构)实践报告实践课程名称 数据结构与算法 开课 实 验 室 数学实验教学中心 学 院 数学与统计学院年 级 2009级 专 业 班 信息与计算科学01班学 生 姓 名 学 号 20092250 开 课 时 间 2011 至 2012 学年 第 一 学期总 成 绩教师签名实验一、单链表的基本操作一、实验目的1、掌握线性链表的操作特点，即指针是逻辑关系的映像。2、掌握动态产生单链表的方法。3、熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。二、实验内容1、动态创建单链表2、实现线性表链式存储结构中元素的插入。3、实现线性表链式存储结构中元素的删除。三、具体要求1、单链表的存储结构定义typedef struct LNode ElemType data; / 数据域 struct LNode *next; / 指针域 LNode, *LinkList;2、从键盘上依次输入21、18、30、75、42、56，逆序创建单链表，并输出单链表中的各元素值。3、分别在单链表的第3个位置和第9个位置插入67和10，给出插入成功或失败的信息，并输出单链表中的各元素值。4、删除单链表中的第6个数据元素和第8个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值。四、完成情况和实验记录1、由于程序要求的操作很多，而且C程序要求敏感，所以在编程过程中只有通过不断的修改，不断的尝试来克服遇到的很多错误和警告问题。在调试过程要有足够的耐心和发现错误的洞察力。五、完成情况和实验记录#include#include#include #include #define LEN sizeof(LNode) /定义LEN为一个节点的长度enum BOOLFalse,True; /定义BOOL型typedef struct nodeint data; /数据域 struct node *next;/指向下一个节点的指针LNode,*LinkList;void CreatList(LinkList &,int); /生成一个单链表BOOL ListInsert(LinkList &,int,int); /在单链表中插入一个元素BOOL ListDelete(LinkList &,int,int); /在单链表中删除一个元素void ListPrint(LinkList); /显示单链表所有元素void main()LinkList L; BOOL temp; int num,loc,flag=1,ch; char j; /程序说明 printf(单链表的基本操作。n); printf(可以进行逆置，插入，删除等操作。n); printf(请输入初始时链表长度:); /输入生成单链表时的元素个数 scanf(%d,&num); CreatList(L,num); /生成单链表 ListPrint(L); while(flag) printf(请选择:n); printf(1.显示所有元素n); /显示链表元素 printf(2.插入一个元素n); /插入链表元素 printf(3.删除一个元素n); /删除链表元素 printf(0.退出程序 n); /退出 scanf( %c,&j); switch(j) case 1:ListPrint(L); break; case 2:printf(请输入数据和要插入的位置-1:n);printf(格式：数据，位置；例如:12,3，（即把12插入到第3个位置之后，即第4个位置）n); scanf( %d,%d,&ch,&loc); /输入要插入的元素和要插入的位置 temp=ListInsert(L,loc,ch); /插入 if(temp=False) printf(插入失败!n); /插入失败 else printf(插入成功!n); /成功插入 ListPrint(L); break; case 3:printf(请输入要删除的元素所在位置-1：（输入2，即删除的是第3个元素）:); scanf(%d,&loc); /输入要删除的节点的位置 temp=ListDelete(L,loc,ch); /删除 if(temp=False)printf(删除失败!n); /删除失败 else printf(成功删除了一个元素:%dn,ch); /删除成功，显示该元素 ListPrint(L); break; default:flag=0;printf(程序结束，按任意键退出!n); getchar();void CreatList(LinkList &v,int n)/生成一个带头结点的有n个元素的单链表 int i; LinkList p; v=(LinkList)malloc(LEN); /生成头结点 v-next=NULL; printf(请输入%d个数据：例如：1 2 3n,n); getchar(); for(i=n;i0;-i) p=(LinkList)malloc(LEN); /生成新结点 scanf(%d,&p-data); p-next=v-next; v-next=p; BOOL ListInsert(LinkList &v,int i,int e)/在单链表的第i各位置插入元素e，成功返回True，失败返回False LinkList p,s; int j=0; p=v; while(p&jnext;+j; /查找第i-1个元素的位置 if(!p|ji) return False; /没有找到 s=(LinkList)malloc(LEN); /生成一个新结点 s-data=e; s-next=p-next; /将新结点插入到单链表中 p-next=s; return True;BOOL ListDelete(LinkList &v,int i,int e)/在单链表中删除第i个元素，成功删除返回True，并用e返回该元素值，失败返回False LinkList p,q; int j=0; p=v; while(p-next&jnext;+j; if(!(p-next)|ji) return False; /查找失败 q=p-next;p-next=q-next; /删除该元素 e=q-data; /e取得该元素值 free(q); /释放该元素空间 return True;void ListPrint(LinkList v) /显示链表所有元素 LinkList q; q=v-next; printf(逆置输出链表所有元素:); while(q!=NULL) printf(%d ,q-data);q=q-next; printf(n);六、所输入的数据及相应的运行结果实验二 栈、队列算法设计一、实验目的1、 熟悉栈这种特殊线性结构的特性；2、 熟练掌握栈在顺序存储结构和链表存储结构下的基本运算；3、 熟悉队列这种特殊线性结构的特性；4、 熟练掌握队列在链表存储结构下的基本运算。二、实验内容1、动态创建栈和队列2、实现实现栈和队列中元素的插入。3、实现实现栈和队列中元素的的删除。三、具体要求1、用顺序和链式存储结构分别实现栈的初始化、求长度、获取栈顶元素、压栈、出栈、判空、置空等操作，生成sqStack.h文件和LinkStack.h文件；编写main函数调用。四、程序清单顺序栈#include#include#includeconst int stackIncreament=20;const int maxSize=50;template class Stackpublic:Stack(int sz=50);Stack() deleteelements;void Push(const T& x);int Pop(); int getTop();bool IsEmpty() const return (top=-1)?true:false;bool IsFull() const return (top=maxSize-1)?true:false;int getSize() const return top+1;void MakeEmpty() top=-1;void print(Stack& s);void Meun();private:T *elements;int top;int maxSize;void overflowProcess();template Stack:Stack(int sz):top(-1),maxSize(sz)elements=new TmaxSize;assert(elements!=NULL);template void Stack:overflowProcess() T *newArray = new TmaxSize + stackIncreament; if (newArray=NULL) cerr存储分配失败!endl; exit(