重 庆 大 学基础性实践环节(数据结构)实践报告实践课程名称 数据结构与算法 开课 实 验 室 数学实验教学中心 学 院 数学与统计学院年 级 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 BOOL{False,True}; //定义BOOL型typedef struct node{int 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("成功删除了一个元素:%d\n",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 3\n",n); getchar(); for(i=n;i>0;--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||j>i) 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)||j>i) 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 Stack{public: Stack(int sz=50); ~Stack() {delete[]elements;} 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 T[maxSize]; assert(elements!=NULL);};template void Stack::overflowProcess(){ T *newArray = new T[maxSize + stackIncreament]; if (newArray=NULL) { cerr<<"存储分配失败!"<