级数据结构验证性实验指导书新版1文档格式.docx
《级数据结构验证性实验指导书新版1文档格式.docx》由会员分享，可在线阅读，更多相关《级数据结构验证性实验指导书新版1文档格式.docx（33页珍藏版）》请在冰点文库上搜索。
L.listsize=LIST_INIT_SIZE;
return
（1）;
}//endofInitList_Sq（）function
/*从顺序表中查找与给定元素值相同的元素在顺序表中的位置*/
intLocateElem_Sq（SqListL,ElemTypee）//LocateElem_Sq（）sub-function
{inti=1;
int*p=L.elem;
while（i<
=L.length&
&
*p++!
=e）
++i;
if（i<
=L.length）
return（i）;
else
return（ERROR）;
}//LocateElem_Sq（）end
/*向顺序表中插入元素*/
intListInsert_sq（SqList&
L,inti,inte）//ListInsert_sq（）
{if（i<
1||i>
L.length+1）//i（location）isillegal
{cout<
<
"
Initialfailure!
endl;
getch（）;
}
if（L.length>
=L.listsize）//insertintotheendoftheSqlist
{int*Newbase;
Newbase=（int*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（int））;
if（!
Newbase）
{cout<
Overflow!
getch（）;
return（ERROR）;
L.elem=Newbase;
L.listsize+=LISTINCREMENT;
int*p,*q;
q=&
（L.elem[i-1]）;
//qpointattheelementbeforetheinsertedone
for（p=&
（L.elem[L.length-1]）;
p>
=q;
--p）//movetheelement
*（p+1）=*p;
*q=e;
++L.length;
return（OK）;
}//ListInser_sq（）end
/*从顺序表中删除元素*/
voidListDelete_Sq（SqList&
L,inti,int&
e）//ListDelete_Sq（）function
{
if（（i<
1）||（i>
L.length））
{cout<
i<
isOverFlow!
exit（0）;
}
p=&
e=*p;
q=L.elem+L.length-1;
for（++p;
p<
++p）
*（p-1）=*p;
--L.length;
cout<
SuccesstoDeleteSq_list!
}//endofListDelete_Sq（）function
/*有序顺序表的合并*/
intMerge_Sq（SqList&
A,SqList&
B,SqList&
C）//Merge_Sq（）function
{//MergetheSqListAandBtoC
C.listsize=C.length=A.length+B.length;
C.elem=（ElemType*）malloc（C.listsize*sizeof（ElemType））;
C.elem）
{cout<
OverFlow!
//failuretoallocateroominRAM
return（0）;
};
inti=0,j=0;
//iandjistheSubscriptofA.elem[]andB.elem[]
intk=0;
//kistheSubscriptofC.elem[]
while（（i<
A.length）&
（j<
B.length））//Tomergewheni<
=A.lengthandj>
=B.length
if（A.elem[i]<
=B.elem[j]）
{C.elem[k]=A.elem[i];
i++;
k++;
}//endofif
{C.elem[k]=B.elem[j];
j++;
}//endofelse
A.length）//inserttherestofSqListA
{C.elem[k]=A.elem[i];
i++;
}//endofwhile
while（j<
B.length）//inserttherestofSqListB
{C.elem[k]=B.elem[j];
j++;
SuccesstoMergeAandB!
return
（1）;
}//endofMerge_Sq（）function
1、顺序表基本操作的实现。
要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。
2、已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc，lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表。
3.从有序顺序表A中删除那些在顺序表B和顺序表C中都出现的元素.
4、将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。
若输入：
1230050478
则输出：
1235478000
实验二单链表实验
1、掌握用VisualC++6.0上机调试单链表的基本方法
2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现
3、进一步掌握循环单链表的插入、删除、查找算法的实现
二、实现内容
下面是链表的部分基本操作实现的算法，请同学们自己设计主函数和部分算法，调用这些算法，完成下面的实验任务。
/*链式存储类型*/
typedefstructLNode
{ElemTypedata;
structLNode*next;
}LNode,*LinkList;
/*
单链表的取元素*/
intGetElem_L（LinkListL,inti,int&
e）//GetElem_L（）function
{//ListheHeadPointerofLinkListwithHeadNode,whentheNo.iexist,assignthe
//valuetovariableeandreturn"
OK!
otherwisereturn"
Error!
LNode*p;
intj=1;
p=L->
next;
while（p&
j<
i）
{p=p->
++j;
}
p||j>
i）
TheNO."
elementisnotexist!
exit（0）;
}//endofif
e=p->
data;
return（e）;
}//endofGetElem_L（）function
/*单链表的插入元素*/
intListInsert_L（Linklist&
L,inti,inte）//ListInsert_L（）sub-function
{LNode*p=L;
intj=0;
i-1）//findthelocation
{p=p->
++j;
i-1）//outoflocation
Errer!
Thelocationisillegal!
LNode*s;
s=（Linklist）malloc（sizeof（LNode））;
//createnewLNode
s->
data=e;
next=p->
p->
next=s;
}//ListInsert_L（）end
/*单链表的删除元素*/
intListDelete_L（LinkList&
L,inti,int&
e）//ListDelete_L（）function
{//DeletetheNO.ielementofLinkListandreturnbyvariablee
LNode*p,*q;
p=L;
while（p->
next&
i-1）
i-1）
return（0）;
q=p->
next=q->
//deletetheNO.iNode
e=q->
free（q）;
}//endofListDelete（）function
单链表的建立（头插法）*/
voidCreateList_L（LinkList&
L,intn）//CreateList_L（）function
{//ToCreatreaLinkListLwithHeadNode
inti;
L=（LinkList）malloc（sizeof（LNode））;
L->
next=NULL;
PleaseinputthedataforLinkListNodes:
"
for（i=n;
i>
0;
--i）
{
p=（LinkList）malloc（sizeof（LNode））;
cin>
>
p->
//ReverseorderinputingforCreatingaLinkList
next=L->
next=p;
}//endoffor
if（n）cout<
SuccesstoCreateaLinkList!
elsecout<
ANULLLinkListhavebeencreated!
}//endofCreateList（）function
1、单链表基本操作的实现。
要求生成单链表时，可以键盘上读取元素，用链式存储结构实现存储。
2、已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。
要求①不破坏la表和lb表的结构。
②破坏la表和lb表的结构。
3、编程实现两个循环单链表的合并。
4、将一循环单链表就地逆置
实验三栈、队列的实现及应用
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2、掌握栈和队列的特点，即先进后出与先进先出的原则。
3、掌握栈和队列的基本操作实现方法。
下面是栈和队列的部分基本操作实现的算法，请同学们自己设计主函数和部分算法，调用这些算法，完成下面的实验任务。
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineMAXQSIZE100
/*定义SElemType为int或别的自定义类型*/
typedefintSElemType;
/*顺序栈的存储类型*/
typedefstruct//definestructureSqStack（）
{SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
/*构造空顺序栈*/
intInitStack（SqStack&
S）//InitStack（）sub-function
{S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
S.base）
endl<
Allocatespacefailure!
;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}//InitStack（）end
/*取顺序栈顶元素*/
intGetTop（SqStackS,SElemType&
e）//GetTop（）sub-function
{if（S.top==S.base）
It'
saemptySqStack!
//ifemptySqStack
e=*（S.top-1）;
}//GetTop（）end
/*将元素压入顺序栈*/
intPush（SqStack&
S,SElemTypee）//Push（）sub-function
{if（S.top-S.base>
S.stacksize）
{S.base=（SElemType*）realloc（S.base,（S.stacksize+
STACKINCREMENT*sizeof（SElemType）））;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
*S.top++=e;
}//Push（）end
将元素弹出顺序栈*/
intPop（SqStack&
S,SElemType&
e）//Pop（）sub-function
saemptySqStack!
e=*--S.top;
}//Pop（）end
/*利用顺序栈实现对于输入的任意一个非负十进制整数，输出与其等值的八进制数。
*/
voidConversion（）//Conversion（）function
{
SqStackS;
//SisaSqStack
SElemTypeN,e;
InitStack（S）;
//constructeaemptystackS
printf（"
PleaseinputtheDeca.numberN=?
:
<
eg.1348>
）;
scanf（"
%d"
&
N）;
while（N）
{Push（S,N%8）;
N=N/8;
ConversedtoOct.number=:
while（!
StackEmpty（S））//noemptythenoutput
{Pop（S,e）;
e）;
}//endofconversion（）function
/*链式栈的存储类型*/
typedefstructSNode//definestructureLinkStack
{SElemTypedata;
structSNode*next;
}SNode,*LinkStack;
/*取链式栈顶元素*/
intGetTop_L（LinkStacktop,SElemType&
e）//GetTop_L（）sub-function
{if（!
top->
next）
It'
sanemptyLinkStack!
{e=top->
next->
}//GetTop_L（）end
将元素压入链式栈*/
intPush_L（LinkStack&
top,SElemTypee）//Push_L（）sub-function
{SNode*q;
q=（LinkStack）malloc（sizeof（SNode））;
q）
Overfolow!
Allocatespacefailure!
q->
next=top->
top->
next=q;
}//Push_L（）end
/*将元素弹出链式栈*/
intPop_L（LinkStack&
top,SElemType&
e）//Pop_L（）sub-function
e=top->
q=top->
}//Pop_L（）end
/*定义QElemType为int或别的自定义类型*/
typedefintQElemType;
/*顺序队列的存储类型*/
typedefstructSqQueue//definestructureSqQueue
{QElemType*base;
intfront;
intrear;
}SqQueue;
构造空顺序队列*/
intInitQueue（SqQueue&
Q）//InitQueue（）sub-function
{Q.base=（QElemType*）malloc（MAXQSIZE*sizeof（QElemType））;
Q.base）
Overflow!
Q.front=Q.rear=0;
}//InitQueue（）end
求顺序队列长度*/
intQueueLength（SqQueueQ）//QueueLength（）sub-function
{return（（Q.rear-Q.front+MAXQSIZE）%MAXQSIZE）;
/*在顺序队列尾插入新元素*/
intEnQueue（SqQueue&
Q,QElemTypee）//EnQueue（）sub-function
{if（（Q.rear+1）%MAXQSIZE==Q.front）
Errer!
TheSqQeueuisfull!
Q.base[Q.rear]=e;
Q.rear=（Q.rear+1）%MAXQSIZE;
}//EnQueue（）end
/*在顺序队列头删除旧元素*/
intDeQueue（SqQueue&
Q,QElemType&
e）//DeQueue（）sub-function
{if（Q.front==Q.rear）
sempty!
e=Q.base[Q.front];
Q.front=（Q.fro
升级会员 