级数据结构验证性实验指导书新版1.docx
- 文档编号:1579041
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:33
- 大小:24.80KB
级数据结构验证性实验指导书新版1.docx
《级数据结构验证性实验指导书新版1.docx》由会员分享,可在线阅读,更多相关《级数据结构验证性实验指导书新版1.docx(33页珍藏版)》请在冰点文库上搜索。
级数据结构验证性实验指导书新版1
实验一线性表的顺序存储实验
一、实验目的
1、掌握用VisualC++6.0上机调试顺序表的基本方法
2、掌握顺序表的基本操作,插入、删除、查找、以及有序顺序表的合并等算法的实现
二、实验内容
下面是顺序表的部分基本操作实现的算法,请同学们自己设计主函数和部分算法,调用这些算法,完成下面的实验任务。
/*常用的符号常量定义*/
#defineOK1
#defineERROR0
#defineMAXSIZE10
#defineLIST_INIT_SIZE10
#defineLISTINCREMENT10
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineSUCCESS1
#defineUNSUCCESS0
#defineDUPLICATE-1
#defineNULLKEY0//0为无记录标志
#defineN10//数据元素个数
#defineEQ(a,b)((a)==(b))
#defineLT(a,b)((a)<(b))
#defineLQ(a,b)((a)<=(b))
/*定义ElemType为int或别的自定义类型*/
typedefintElemType;
/*顺序存储类型*/
typedefstruct
{int*elem;
intlength;
intlistsize;
}SqList;
/*构造一个空线性表算法*/
intInitList_Sq(SqList&L)//InitList_Sq()function
{//InititialaSq_List
L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
if(!
L.elem)return(0);
L.length=0;
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!
"< getch(); return(ERROR); } 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 { int*p,*q; if((i<1)||(i>L.length)) {cout< "< exit(0); } p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;++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)); if(! C.elem) {cout<<"OverFlow! "< return(0); }; inti=0,j=0;//iandjistheSubscriptofA.elem[]andB.elem[] intk=0;//kistheSubscriptofC.elem[] while((i if(A.elem[i]<=B.elem[j]) {C.elem[k]=A.elem[i]; i++;k++; }//endofif else {C.elem[k]=B.elem[j]; j++;k++; }//endofelse while(i {C.elem[k]=A.elem[i]; i++;k++; }//endofwhile while(j {C.elem[k]=B.elem[j]; j++;k++; } cout<<"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、进一步掌握循环单链表的插入、删除、查找算法的实现 二、实现内容 下面是链表的部分基本操作实现的算法,请同学们自己设计主函数和部分算法,调用这些算法,完成下面的实验任务。 /*定义ElemType为int或别的自定义类型*/ typedefintElemType; /*链式存储类型*/ 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 {p=p->next;++j;} if(! p||j>i) {cout<<"TheNO."< "< getch(); 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; while(p&&j {p=p->next; ++j; } if(! p||j>i-1)//outoflocation {cout<<"Errer! Thelocationisillegal! "< return(ERROR); } LNode*s; s=(Linklist)malloc(sizeof(LNode));//createnewLNode s->data=e; s->next=p->next; p->next=s; return(OK); }//ListInsert_L()end /*单链表的删除元素*/ intListDelete_L(LinkList&L,inti,int&e)//ListDelete_L()function {//DeletetheNO.ielementofLinkListandreturnbyvariablee LNode*p,*q; intj=0; p=L; while(p->next&&j {p=p->next;++j; } if(! p||j>i-1) {cout<<"TheNO."< "< getch(); return(0); } q=p->next; p->next=q->next;//deletetheNO.iNode e=q->data; free(q); return(e); }//endofListDelete()function /* 单链表的建立(头插法)*/ voidCreateList_L(LinkList&L,intn)//CreateList_L()function {//ToCreatreaLinkListLwithHeadNode inti; LNode*p; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; cout<<"PleaseinputthedataforLinkListNodes: "< for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data;//ReverseorderinputingforCreatingaLinkList p->next=L->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 #defineOK1 #defineERROR0 /*定义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)); if(! S.base) {cout< "; return(ERROR); } S.top=S.base; S.stacksize=STACK_INIT_SIZE; return(OK); }//InitStack()end /*取顺序栈顶元素*/ intGetTop(SqStackS,SElemType&e)//GetTop()sub-function {if(S.top==S.base) {cout< ";//ifemptySqStack return(ERROR); } e=*(S.top-1); return(OK); }//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))); if(! S.base) {cout< "; return(ERROR); } S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return(OK); }//Push()end /* 将元素弹出顺序栈*/ intPop(SqStack&S,SElemType&e)//Pop()sub-function {if(S.top==S.base) {cout< "; return(ERROR); } e=*--S.top; return(OK); }//Pop()end /*利用顺序栈实现对于输入的任意一个非负十进制整数,输出与其等值的八进制数。 */ voidConversion()//Conversion()function { SqStackS;//SisaSqStack SElemTypeN,e; InitStack(S);//constructeaemptystackS printf("PleaseinputtheDeca.numberN=? : scanf("%d",&N); while(N) {Push(S,N%8); N=N/8; } printf("ConversedtoOct.number=: "); while(! StackEmpty(S))//noemptythenoutput {Pop(S,e); printf("%d",e); } }//endofconversion()function /*链式栈的存储类型*/ typedefstructSNode//definestructureLinkStack {SElemTypedata; structSNode*next; }SNode,*LinkStack; /*取链式栈顶元素*/ intGetTop_L(LinkStacktop,SElemType&e)//GetTop_L()sub-function {if(! top->next) {cout< It'sanemptyLinkStack! "; return(ERROR); } else {e=top->next->data; return(OK); } }//GetTop_L()end /* 将元素压入链式栈*/ intPush_L(LinkStack&top,SElemTypee)//Push_L()sub-function {SNode*q; q=(LinkStack)malloc(sizeof(SNode)); if(! q) {cout< Allocatespacefailure! "; return(ERROR); } q->data=e; q->next=top->next; top->next=q; return(OK); }//Push_L()end /*将元素弹出链式栈*/ intPop_L(LinkStack&top,SElemType&e)//Pop_L()sub-function {SNode*q; if(! top->next) {cout< It'sanemptyLinkStack! "; return(ERROR); } e=top->next->data; q=top->next; top->next=q->next; free(q); return(OK); }//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)); if(! Q.base) {cout< "; return(ERROR); } Q.front=Q.rear=0; return(OK); }//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) {cout<<"Errer! TheSqQeueuisfull! "; return(ERROR); } Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return(OK); }//EnQueue()end /*在顺序队列头删除旧元素*/ intDeQueue(SqQueue&Q,QElemType&e)//DeQueue()sub-function {if(Q.front==Q.rear) {cout< It'sempty! "; return(ERROR); } e=Q.base[Q.front]; Q.front=(Q.fro
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 级数 结构 验证 实验 指导书 新版