院 系： 计算机科学学院 专 业： 年 级： 2010 级 课程名称： 数据结构 学 号： 姓 名： 指导教师：2012年 6 月 1 日年级 2010 学号 专业 班号 2 班 姓名设计型 综合型 创新型实验名称 2 单链表的相关操作演示 实验类型实验目的或要求实验目的：通过上机实践，使学生进一步掌握线性表的逻辑定义、存储结构以及相关应用。 实验要求：自定义存储结构，用 C 或 C+语言编写程序，要求程序模块清晰，菜单界面，有运行结果。四个题目任选一个写入实验报告。实验原理（算法流程）1、单链表的相关操作演示：typedef struct LNodefloat data;struct LNode *next;LNode,*LinkList;/链表节点的定义void CreateList_L(LinkList &L,int n)逆序创建一个链表，L 为链表的头结点，n 为输入的元素的个数int Length_LinkList(LinkList L)将链表 L 中的节点个数输出出来（不包括头结点） ，返回值为输出的节点数；void InsertList_L(LinkList &L,int i,float e)将 e 插入链表 L 中的 i 号位置；核心算法是：现在链表中找到第 i-1 号位置，然后将要插入的 e 插到 i-1 的后面void DeleteList_L(LinkList &L,int i,float e)将链表 L 中的第 i 号位置的元素 e 删除；核心算法：从头结点开始往下找，找到第 i-1 号位置，然后将第 i 号节点删除，再把后面的节点接上void DemandList_L(LinkList &L,int i,float e)查询链表 L 中的第 i 号位置的元素 e；核心算法：找到第 i 号位置，然后输出出来 void OrderList_L(LinkList &L)将链表 L 中的数据递增排序；核心算法是：新申请一个头结点，将链表 L 中的元素进行比较，找到最大的元素所在的节点，将它取出来连接到新的头结点的 next 指针上，然后再找出次大的，再连接到头结点的 next 指针上，如此循环，直到链表 L 的 next 指向空即完成，然后将新的链表的头设置为 L，销毁新的头结点指针void PrintList_L(LinkList &L) 打印函数，一次将链表 L 中的内容输出出来void delLinkList_L(LinkList &L)释放链表 L组内分工（可选）无实验结果分析及心得体会心得体会：首先我觉得要注意的是创建链表的时候要注意将 next 指针赋值为空；插入、删除、查询函数关键就是位置的查找，找到后执行相应的操作就可以了，当然还要注意些地方，比如删除不能超出链表的长度，插入不能超出插入的范围等等；其他的一些就是细节上的问题，什么时候用引用传旨，什么时候用形参传值都是要注意的。成绩评定教师签名：2012 年 月 日备注：源代码附后，源代码要求有注释说明#include #include#includetypedef struct LNodefloat data;struct LNode *next;LNode,*LinkList;/链表节点的定义void CreateList_L(LinkList &L,int n)/逆序创建一个链表LinkList p,q;int i;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;q=L;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);coutp-data;coutnext=q-next;q-next=p;q=p;int Length_LinkList(LinkList L)/返回链表的长度的函数int i;LinkList p;p=L;for(i=0;p-next!=NULL;i+)p=p-next;coutnext)coutm+1&inext;+j;if(!p|ji-1)/判断是否到了链表的末尾coutdata=e;s-next=p-next;p-next=s;void DeleteList_L(LinkList &L,int i,float e)/删除在链表 L 第 i 个位置的元素 eLinkList p,q;int j,m;p=L;j=0;m=Length_LinkList(L);if(!L-next)coutm&inext;+j;if(!p|j=i)/当 i=0 时不可取coutnext;p-next=q-next;coutdatanext;j=1;m=Length_LinkList(L);if(!L-next)coutm&inext;+j;if(!p|ji)coutdatanext=NULL;I1=L;I2=L;p=L-next;q=L-next;if(!L-next)coutnext)/找到最大数，将其从链表中取出来放在新的头结点的后面while(q)/找到最大数if(p-data=q-data)I2=q;q=q-next;elsep=q;I1=I2;I2=q;q=q-next;I1-next=p-next;p-next=I-next;I-next=p;I1=L;I2=L;p=L-next;q=L-next;L-next=I-next;/将新形成的链表给 Lfree(I);coutnext)coutnext;i+)p=p-next;coutdatax;switch(x)case 1:coutn;CreateList_L(L,n);menu(L);break;case 2:coutie;InsertList_L(L,i,e);menu(L);break;case 3:coutie;DeleteList_L(L,i,e);menu(L);break;case 4:coutie;DemandList_L(L,i,e);menu(L);break;case 5:OrderList_L(L);menu(L);break;case 6:PrintList_L(L);menu(L);break;case 7:Length_LinkList(L);menu(L);break;case 8:exit(0);default:cout#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10using namespace std;typedef struct/字符结构体char *base;char *top;int stacksize;SqStack;typedef struct/数字结构体float *base;float *top;int stacksize;SzStack;int InitStack_q(SqStack &s)/构造一个 char 空栈s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!s.base)return 0;s.top=s.base;s.stacksize=STACK_INIT_SIZE;return 1;int InitStack_z(SzStack &s)/构造一个 float 空栈s.base=(float *)malloc(STACK_INIT_SIZE*sizeof(float);if(!s.base)return 0;s.top=s.base;s.stacksize=STACK_INIT_SIZE;return 1;char GetTop_q(SqStack s)/栈不空，取出栈顶元素char e;if(s.top=s.base)cout=s.stacksize)s.base=(char *)realloc(s.base,(s.stacksize+STACKINCREMENT) * sizeof(char);if(!s.base)cout=s.stacksize)s.base=(float *)realloc(s.base,(s.stacksize+STACKINCREMENT) * sizeof(float);if(!s.base)cout, :u=Pop_q(OPTR);b=Pop_z(OPND);/将字符数字转换为数字a=Pop_z(OPND);/将字符数字转换为数字Push_z(OPND,Operate(a,u,b);break;r=GetTop_z(OPND);return r;void main()float result;result=EvaluateExpression();cout#include #include #include #include using namespace std;#define OK 1#define FALSE 0#define TRUE 1typedef char TElemType;typedef int status;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/树节点的定义BiTNode *Left(BiTree e)/得到树的左孩子if(e-lchild)return e-lchild;elsereturn NULL;BiTNode *Right(BiTree e)/得到树的右孩子if(e-rchild)return e-rchild;elsereturn NULL;BiTNode * CreateBiTree()/先序输入；难点：定义结构体的一个指针的函数char ch;BiTNode *T=NULL;scanf(%c,if(ch= )/难点；没有的要附上一个 NULLT=NULL;elseT=(struct BiTNode*)(malloc(sizeof(struct BiTNode);T-data=ch;T-lchild=CreateBiTree();/递归创建左树T-rchild=CreateBiTree();/递归创建右树return T;void PreOrderTraverse(BiTree T)/递归先序输出if(T!=NULL)printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);void InOrderTraverse(BiTree T)/递归中序输出if(T!=NULL)InOrderTraverse(T-lchild);printf(%c,T-data);InOrderTraverse(T-rchild);void AfOrderTraverse(BiTree T)/递归后序输出if(T!=NULL)AfOrderTrav