p=p→next;++j;
}
if（!
p||j>i）returnERROR;//第i个元素不存在
elsee=p→data; //取第i个元素
returnOK;
}//GetElem_L
五、问题讨论
1、单链表具有什么优缺点？
2、单链表的定义与顺序表的定义有什么区别？
3、逆序创建单链表有什么好处？
4、为什么单链表中取元素、插入和删除操作在开始不判断给定位置i的合法性？
5、当给定位置大于单链表长度时，取元素、插入和删除操作分别是如何执行的？
6、如何改进单链表的定义，使其可以在操作前判断判断给定位置i的合法性？
六、实验报告内容
1、实验目的
2、实验内容和具体要求
3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法
4、程序清单
5、所输入的数据及相应的运行结果6、问题回答7、实验心得
实验二、栈和队列的应用
一、实验目的
1、掌握栈的特点（先进后出FILO）及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。
2、掌握队列的特点（先进先出FIFO）及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵。
二、实验内容
1．顺序栈的实现和运算
2．链栈的实现和运算
3．顺序队列的实现和运算
4．链式队列的实现和运算
5．循环队列的实现和运算
三、实验要求
1．用C++/C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
四、程序实现
写出每个操作的算法（操作过程）
程序运行情况
五、写出输入数据及运行结果
六、源程序清单。
程序1：
顺序栈的实现和运算
#include
#defineMAXN26
charstack[MAXN];
inttop=0;
intpush（charx）
{if（top>=MAXN）
return
（1）;
stack[top++]=x;
return（0）;
}
intpop（char*p_y）
{if（top==0）
return
（1）;
*p_y=stack[--top];
return（0）;
}
voidmain（）
{inti;
charch_x,ch_y;
printf（"inputthecharyouwanttopush\n"）;
scanf（"%c",&ch_x）;
while（ch_x!
='0'）
if（push（ch_x）==1）printf（"failure!
\n"）;
else
{printf（"success!
\n"）;
printf（"inputacharforch_xtopush\nch_x="）;
getchar（）;
scanf（"%c",&ch_x）;}
i=0;
while（stack[i]!
='\0'）
{printf（"%c",stack[i]）;
i++;}
if（pop（&ch_y）==1）printf（"failure!
\n"）;
else
{printf（"success!
\n"）;
printf（"Thepopcharis%c\n",ch_y）;}
for（i=top-1;i>=0;i--）
printf（"%c",stack[i]）;
}
程序2：
链栈的实现和运算
#include
#include
structnode{chardata;
structnode*link;
};
typedefstructnodeNODE;
NODE*top=NULL;
voidpush_l（charx）
{NODE*p;
p=（NODE*）malloc（sizeof（NODE））;
p->data=x;
p->link=top;
top=p;
}
intpop_l（char*p_y）
{NODE*p;
if（top==NULL）
return
（1）;
*p_y=top->data;
p=top;
top=top->link;
free（p）;
return（0）;
}
voidmain（）
{NODE*p;
charch_x,ch_y;
printf（"inputthecharyouwanttopush\n"）;
scanf（"%c",&ch_x）;
while（ch_x!
='0'）
{push_l（ch_x）;
getchar（）;
scanf（"%c",&ch_x）;}
p=（NODE*）malloc（sizeof（NODE））;
p=top;
while（p!
=NULL）
{printf（"%c",p->data）;
p=p->link;}
printf（"\n"）;
if（pop_l（&ch_y）==1）printf（"failure!
\n"）;
else
{printf（"success!
\n"）;
printf（"Thepopcharis%c\n",ch_y）;}
p=（NODE*）malloc（sizeof（NODE））;
p=top;
while（p!
=NULL）
{printf（"%c",p->data）;
p=p->link;}
printf（"\n"）;
}
程序3：
顺序队列的实现和运算
#include
#defineMAXN26
charq[MAXN];
inthead=-1,tail=-1;
inten_queue（charx）
{if（tail==MAXN-1）
return
（1）;
q[++tail]=x;
return（0）;
}
intde_queue（char*p_y）
{if（head==tail）
return
（1）;
*p_y=q[++head];
return（0）;
}
voidmain（）
{inti;
charch_x,ch_y;
printf（"inputthecharyouwanttoenqueue\n"）;
scanf（"%c",&ch_x）;
while（ch_x!
='0'）
if（en_queue（ch_x）==1）printf（"failure!
\n"）;
else
{printf（"success!
\n"）;
printf（"inputacharforch_xtoenqueue\nch_x="）;
getchar（）;
scanf（"%c",&ch_x）;}
i=1;
while（q[i]!
='\0'）
{printf（"%c",q[i]）;
i++;}
if（de_queue（&ch_y）==1）printf（"failure!
\n"）;
else
{printf（"success!
\n"）;
printf（"Thedequeuecharis%c\n",ch_y）;}
for（i=head+1;i<=tail;i++）
printf（"%c",q[i]）;
}
程序4：
链式队列的实现和运算
#include
#include"
structnode{chardata;
structnode*link;
};
typedefstructnodeNODE;
NODE*head,*tail;
voiden_queue_l（charx）
{NODE*p;
p=（NODE*）malloc（sizeof（NODE））;
p->data=x;
p->link=NULL;
if（head==NULL）
head=p;
else
tail->link=p;
tail=p;
}
intde_queue_l（char*p_y）
{NODE*p;
if（head==NULL）
return
（1）;
*p_y=head->data;
p=head;
head=head->link;
free（p）;
return（0）;
}
voidmain（）
{NODE*p;
charch_x,ch_y;
printf（"inputthecharyouwanttoenqueue\n"）;
scanf（"%c",&ch_x）;
while（ch_x!
='0'）
{en_queue_l（ch_x）;
getchar（）;
scanf（"%c",&ch_x）;}
p=（NODE*）malloc（sizeof（NODE））;
p=head;
while（p!
=NULL）
{printf（"%c",p->data）;
p=p->link;}
printf（"\n"）;
if（de_queue_l（&ch_y）==1）printf（"failure!
\n"）;
else
{printf（"success!
\n"）;
printf（"Thedequeuecharis%c\n",ch_y）;}
p=（NODE*）malloc（sizeof（NODE））;
p=head;
while（p!
=NULL）
{printf（"%c",p->data）;
p=p->link;}
printf（"\n"）;
}
程序5：
循环队列的实现和运算
#include
#include
#defineMAXN26
charq[MAXN];
inthead=0,tail=0;
inten_c_q（charx）
{tail=（tail+1）%MAXN;
if（tail==head）
{if（tail==0）tail=MAXN-1;
elsetail--;
return
（1）;}
q[tail]=x;
return（0）;
}
intde_c_q（char*p_y）
{if（head==tail）
return
（1）;
head=（head+1）%MAXN;
*p_y=q[head];
return（0）;}
voidmain（）
{inti;
charch_x,ch_y;
printf（"inputthecharyouwanttoenqueue\n"）;
scanf（"%c",&ch_x）;
while（ch_x!
='0'）
if（en_c_q（ch_x）==1）printf（"failure!
\n"）;
else
{printf（"success!
\n"）;
printf（"inputacharforch_xtoenqueue\nch_x="）;
getchar（）;
scanf（"%c",&ch_x）;}
i=1;
while（q[i]!
='\0'）
{printf（"%c",q[i]）;
i++;}
if（de_c_q（&ch_y）==1）printf（"failure!
\n"）;
else
{printf（"success!
\n"）;
printf（"Thedequeuecharis%c\n",ch_y）;}
for（i=head+1;i<=tail;i++）
printf（"%c",q[i]）;
}
实验三、二叉树的遍历
一、实验目的
1、掌握二叉树的特点及其存储方式。
2、掌握二叉树的创建。
3、掌握二叉树前序、中序、后序遍历的基本方法及应用。
二、实验内容
1、用前序方法建立一棵二叉树。
2、编写前序遍历二叉树的程序。
3、编写中序遍历二叉树的程序。
4、编写后序遍历二叉树的程序。
5、编写统计二叉树叶子结点个数的程序
三、实验环境
TC或VC++
四、实验步骤
1、二叉树的二叉链表存储类型定义
typedefstructBiTNode
{datatypedata;
structBiTNode*lchild,*rchild;
}BiTNode，*BiTree;
2、建立下图所示的二叉树
以字符串的形式“根左子树右子树”定义一棵二叉树时，创建二叉树的算法如下：
StatusCreateBiTree（BiTree&T）{
scanf（&ch）;
if（ch==''）T=NULL;
else{
if（!
（T=newBiTNode））
exit（OVERFLOW）;
T->data=ch;//生成根结点
CreateBiTree（T->lchild）;//构造左子树
CreateBiTree（T->rchild）;//构造右子树
}
returnOK;}//CreateBiTree
3、编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列
（1）先序遍历二叉树的递归算法如下：
voidPreorder（BiTreeT,void（*visit）（TElemType&e））
{//先序遍历二叉树
if（T）{
visit（T->data）;//访问结点
Preorder（T->lchild,visit）;//遍历左子树
Preorder（T->rchild,visit）;//遍历右子树
}
}
（2）中序遍历二叉树的递归算法如下：
voidInorder（BiTreeT,void（*visit）（TElemType&e））
{//中序遍历二叉树
if（T）{
Inorder（T->lchild,visit）;//遍历左子树
visit（T->data）;//访问结点
Inorder（T->rchild,visit）;//遍历右子树
}
}
（3）后序遍历二叉树的递归算法如下：
voidPostorder（BiTreeT,void（*visit）（TElemType&e））
{//后序遍历二叉树
if（T）{
Postorder（T->lchild,visit）;//遍历左子树
Postorder（T->rchild,visit）;//遍历右子树
visit（T->data）;//访问结点
}
}
（4）先序遍历二叉树的非递归算法如下：
StatusPreOrderTraverse（BiTreeT,Status（*visit）（TElemType&e））{
InitStack（S）;p=T;
While（p||!
StackEmpty（S））{
if（p）{if（!
visit（p->data））returnERROR;
Push（S,p）;p=p->lchild;}
else{
Pop（S,p）;
p=p->rchild;
}//else
}//while
returnOK;
}
（5）中序遍历二叉树的非递归算法如下：
StatusInOrderTraverse（BiTreeT,Status（*visit）（TElemType&e））{
InitStack（S）;p=T;
While（p||!
StackEmpty（S））{
if（p）{Push（S,p）;p=p->lchild;}
else{
Pop（S,p）;
if（!
visit（p->data））returnERROR;
p=p->rchild;
}//else
}//while
returnOK;
}
4、统计以上二叉树中叶子结点的个数
算法基本思想:
先序（或中序或后序）遍历二叉树，在遍历过程中查找叶子结点，并计数。
由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为:
若是叶子，则计数器增1。
算法如下：
voidCountLeaf（BiTreeT,int&count）{
if（T）{
if（（!
T->lchild）&&（!
T->rchild））
count++;//对叶子结点计数
CountLeaf（T->lchild,count）;
CountLeaf（T->rchild,count）;
}//if
}//CountLeaf
五、问题讨论
1、先序、中序、后序遍历二叉树的区别？
2、在先序、中序非递归算法中为什么使用栈？
能不能借助其它数据结构来实现？
六、实验报告内容
1、实验目的
2、实验内容和具体要求
3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法
4、程序清单
5、所输入的数据及相应的运行结果
6、问题回答
7、实验心得
实验四图的遍历操作
一、实验目的：
1.掌握图的含义。
2.掌握用邻接矩阵和邻接表的方法描述图的存储结构。
3.理解并掌握深度优先遍历和广度优先遍历的存储结构。
二、实验内容：
从以下1、2和3、4中各选择一项内容
1.建立无向图的邻接矩阵，并实现插入、删除边的功能。
2.建立有向
升级会员 