中北大学 算法与数据结构实验报告Word格式.docx
《中北大学 算法与数据结构实验报告Word格式.docx》由会员分享，可在线阅读，更多相关《中北大学 算法与数据结构实验报告Word格式.docx（100页珍藏版）》请在冰点文库上搜索。
#include<
stdlib.h>
iostream.h>
conio.h>
voidCreateList_L（LinkList&
L,intn）
{//逆位序输入n个数据元素的值，建立带头结点的单链表L
inti;
LNode*p;
L=（LinkList）malloc（sizeof（LNode））;
L->
next=NULL;
//先建立一个带头结点的空链表
cout<
<
"
请输入创建的单链表中的数据:
<
如：
34,67,3,-9,45,...>
endl;
for（i=n;
i>
0;
--i）
{
p=（LinkList）malloc（sizeof（LNode））;
//生成新结点
cin>
>
p->
data;
p->
next=L->
next;
//将新结点插入到单链表的头
next=p;
//修改单链表头结点的指针域
}//for结束
if（n）cout<
成功创建一个单链表!
elsecout<
创建了一个空链表!
}
voidmain（）
{
LinkListL;
intInitLNodeNum;
CreateList_L.cpp"
endl<
================"
请输入创建的单链表中的数据个数:
"
;
InitLNodeNum;
CreateList_L（L,InitLNodeNum）;
OK...!
getch（）;
}//endofmain（）function
4、实现单向线性链表取元素
#defineElemTypeint
#defineLIST_MAX_LENGTH100//LIST_MAX_LENGTH是单链表L的最大长度
{ElemTypedata;
{//创建一个带头结点的单链表L
}
}
intGetElem_L（LinkListL,inti,int&
e）//GetElem_L（）function
{//L为带头结点的单链表的头指针，当第i个元素存在时，其值赋给e并返回OK，
//否则返回Error
intj=1;
p=L->
//初始化，p指向链表第一个结点，j为计数器
while（p&
&
j<
i）//顺指针向后查直到P指向第i个元素或为空
{p=p->
++j;
if（!
p||j>
i）
{cout<
这个元素"
i<
不存在!
exit（0）;
}//结束if
e=p->
return（e）;
}//结束单链表的取元素
voidmain（）//main（）function
inte;
//ecanbeEveryDataType
inti,LListNodeNum;
//jisacounterforcycle
GetElem_L.cpp"
==============="
请输入创建的单链表的大小:
LListNodeNum;
CreateList_L（L,LListNodeNum）;
成功创建一个单链表L!
你想提取哪一个位置上的数据？
:
i;
//输入要提取的数据
if（i>
LListNodeNum）cout<
输入错误!
GetElem_L（L,LListNodeNum-i+1,e）;
位置"
在单链表中的数据是:
e;
...OK...!
5、实现单向线性链表遍历
stdio.h>
#defineLIST_INIT_LENGTH10//LIST_INIT_LENGTHistheInit_Define_LengthofLinkList
typedefintElemType;
intdata;
L,intn）//CreatList_L（）subfunction
{//ToCreatreaLinkListLwithHeadNode
intarray[LIST_INIT_LENGTH];
printf（"
Pleaseinputthenodesdata:
eg.34,20,2,3,10,51,12,...>
\n"
）;
for（i=0;
n;
i++）//inputthedatatocreatetheLinkList
scanf（"
%d"
&
array[i]）;
++i）
data=array[i];
//forexampletoaCreateList
}//endoffor
}//endofCreateList_L（）function
voidContray（LinkList&
head）//Contray（）function
{//DeletetheNO.ielementofLinkListandreturnbyvariablee
LNode*p,*q;
p=head;
head=NULL;
while（p）
q=p;
p=p->
q->
next=head;
head=q;
}//endofwhile
SuccesstoContraytheLinkList!
}//endofContray（）function
inti,LNodeNum;
//jisjustacounterforcycle
Contray.cpp"
============"
Howmanynodesdoyouwanttocreate?
eg.7>
LNodeNum;
CreateList_L（L,LNodeNum）;
p=L;
Thenextone'
sInsertedDirectionisalwaysinfrontofthis."
data<
//outputtheLinkListbeforeContray
}
------------------------------<
Contray（L）;
//callfunctionContray（）;
theLinkListaftercontrayis:
["
L->
//outputtheLinkListafterContray
L=L->
]"
6、实现单向线性链表插入
#include<
malloc.h>
#defineINIT_LENGTH10
#defineOK1
#defineERROR0
typedefstructLNode//defineLNodestructure
}LNode,*Linklist;
intListInsert_L（Linklist&
L,inti,inte）
{//在带头结点的单链线性表L中第i个位置之前插入元素e
LNode*p=L;
intj=0;
i-1）//寻找第i-1个结点
{p=p->
++j;
i-1）//i小于1或i大于表长
错误!
这个位置不存在!
return（ERROR）;
LNode*s;
s=（Linklist）malloc（sizeof（LNode））;
s->
data=e;
next=p->
next=s;
return（OK）;
}//ListInsert_L（）end
voidmain（）//main（）function
{inti,j,e;
LNodenode[10];
LNode*L,*p;
intarray[INIT_LENGTH+1]={5,8,12,18,25,30,37,46,51,89};
L=node;
L=（Linklist）malloc（sizeof（LNode））;
for（i=10;
i--）
{p=（Linklist）malloc（sizeof（LNode））;
data=array[i-1];
ListInsert_L.cpp"
cout<
原来的单链线性表L为:
INIT_LENGTH;
i++）
请输入要插入的位置"
j;
请输入要插入的元素:
if（ListInsert_L（L,j,e））
{cout<
新的单链线性表L为:
11;
...OK!
..."
7、实现单向线性链表删除
L,intn）//CreateList_L（）function
{//创建一个带头结点的单链表L
}//结束for
}//endofCreateList（）function
intListDelete_L（LinkList&
L,inti,int&
e）//ListDelete_L（）function
{//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
while（p->
next&
i-1）//删除位置不合理
的数据不存在!
return（0）;
q=p->
//用指针q指向被删除的结点
next=q->
//删除第i个结点
e=q->
//取出第i个结点数据域值
free（q）;
//释放第i个结点
}//结束删除元素
inti,j;
intLListNodeNum;
ListDelete_L.cpp"
请输入创建的单链表的结点个数:
请输入创建的单链表中的数据"
成功创建一个带头结点的单链表L:
while（p）//输出创建的单链表
}//endoffor
你想删除单链表中哪个位置上的数据？
//输入要删除的位置
if（i<
=LListNodeNum）
数据"
已经被删除"
ListDelete_L（L,i,e）<
for（j=1;
++j）
//输出新的单链表
}//结束for
InputError!
【实验结果】
1、写出实验的总结与体会，要简洁、真实、深刻；
忌空话、套话
2、单向链表和双向链表在实现时的区别
3、单向链表如何修改实现循环链表
实验二链表的应用
（二）栈的应用
1、实现单向链栈的抽象数据类型
2、实现单向链栈的建立、销毁、取栈顶元素、压栈、弹栈的运算
3、给出包含括号和+、-、*、\四则运算的运算符优先级表
4、创建运算符栈和运算数栈
5、实现有一定通用性的程序，实现一个四则运算表达式的求解
6、设计测试用的运算表达式，通过键盘输入进行测试
1、构造空链式队列算法
#defineMAXQSIZE100
typedefintQElemType;
typedefstructSqQueue//创建一个头结点
{QElemType*base;
intfront;
intrear;
}SqQueue;
intInitQueue（SqQueue&
Q）
{Q.base=（QElemType*）malloc（MAXQSIZE*sizeof（QElemType））;
Q.base）//存储空间分配失败
Overflow!
Q.front=Q.rear=0;
}//InitQueue（）end
voidmain（）//mainfunction
{SqQueueQ;
InitQueue.cpp"
============="
if（InitQueue（Q））
成功!
链式队列已被构造!
}//main（）end
2、销毁链式队列算法
typedefstructQNode//definestructureQNode
{QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstructLinkQueue//definestructureLinkQueue
{QueuePtrfront;
QueuePtrrear;
}LinkQueue;
intEnQueue（LinkQueue&
Q,QElemTypee）//构造队列
{QNode*p;
p=（QueuePtr）malloc（sizeof（QNode））;
p）
if（Q.front==NULL）//newQNode
{Q.front=Q.rear=p;
Q.rear->
Q.rear=p;
}//EnQueue（）end
intDestroyQueue（LinkQueue&
Q）//销毁队列Q
{while（Q.front）
{Q.rear=Q.front->
free（Q.front）;
Q.front=Q.rear;
}//DestroyQueue（）end
voidmain（）//main（）function
{inti,e=1;
LinkQueueQ;
QNode*q;
Q.front=Q.rear=NULL;
DestroyQueue.cpp"
while（e）
请输入队列当中的数据（如58到0或exit）:
if（e）
EnQueue（Q,e）;
升级会员 