数据结构

4-1另类堆栈(10分)在栈的顺序存储实现中，另有一种方法是将Top定义为栈顶的上一个位置。请编写程序实现这种定义下堆栈的入栈、出栈操作。如何判断堆栈为空或者满？函数接口定义：boolPush(StackS,ElementTypeX);ElementTypePop(StackS);其中Stack结构定义如下：typedefintPosition;typedefstructSNode*PtrToSNode;structSNode{ElementType*Data;/*存储元素的数组*/PositionTop;/*栈顶指针*/intMaxSize;/*堆栈最大容量*/};typedefPtrToSNodeStack;注意：如果堆栈已满，Push函数必须输出“StackFull”并且返回false；如果队列是空的，则Pop函数必须输出“StackEmpty”，并且返回ERROR。裁判测试程序样例：#includestdio.h#includestdlib.h#defineERROR-1typedefintElementType;typedefenum{push,pop,end}Operation;typedefenum{false,true}bool;typedefintPosition;typedefstructSNode*PtrToSNode;structSNode{ElementType*Data;/*存储元素的数组*/PositionTop;/*栈顶指针*/intMaxSize;/*堆栈最大容量*/};typedefPtrToSNodeStack;StackCreateStack(intMaxSize){StackS=(Stack)malloc(sizeof(structSNode));S-Data=(ElementType*)malloc(MaxSize*sizeof(ElementType));S-Top=0;S-MaxSize=MaxSize;returnS;}boolPush(StackS,ElementTypeX);ElementTypePop(StackS);OperationGetOp();/*裁判实现，细节不表*/voidPrintStack(StackS);/*裁判实现，细节不表*/intmain(){ElementTypeX;StackS;intN,done=0;scanf(%d,&N);S=CreateStack(N);while(!done){switch(GetOp()){casepush:scanf(%d,&X);Push(S,X);break;casepop:X=Pop(S);if(X!=ERROR)printf(%disout\n,X);break;caseend:PrintStack(S);done=1;break;}}return0;}/*你的代码将被嵌在这里*/boolPush(StackS,ElementTypeX){if(S-Top==S-MaxSize){printf(StackFull\n);returnfalse;}else{S-Data[S-Top]=X;S-Top++;}returntrue;}ElementTypePop(StackS){if(S-Top==0){printf(StackEmpty\n);returnERROR;}else{S-Top--;}returnS-Data[S-Top];}4-2二叉搜索树的操作集(20分)本题要求实现给定二叉搜索树的5种常用操作。函数接口定义：BinTreeInsert(BinTreeBST,ElementTypeX);BinTreeDelete(BinTreeBST,ElementTypeX);PositionFind(BinTreeBST,ElementTypeX);PositionFindMin(BinTreeBST);PositionFindMax(BinTreeBST);其中BinTree结构定义如下：typedefstructTNode*Position;typedefPositionBinTree;structTNode{ElementTypeData;BinTreeLeft;BinTreeRight;};函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针；函数Delete将X从二叉搜索树BST中删除，并返回结果树的根结点指针；如果X不在树中，则打印一行NotFound并返回原树的根结点指针；函数Find在二叉搜索树BST中找到X，返回该结点的指针；如果找不到则返回空指针；函数FindMin返回二叉搜索树BST中最小元结点的指针；函数FindMax返回二叉搜索树BST中最大元结点的指针。裁判测试程序样例：#includestdio.h#includestdlib.htypedefintElementType;typedefstructTNode*Position;typedefPositionBinTree;structTNode{ElementTypeData;BinTreeLeft;BinTreeRight;};voidPreorderTraversal(BinTreeBT);/*先序遍历，由裁判实现，细节不表*/voidInorderTraversal(BinTreeBT);/*中序遍历，由裁判实现，细节不表*/BinTreeInsert(BinTreeBST,ElementTypeX);BinTreeDelete(BinTreeBST,ElementTypeX);PositionFind(BinTreeBST,ElementTypeX);PositionFindMin(BinTreeBST);PositionFindMax(BinTreeBST);intmain(){BinTreeBST,MinP,MaxP,Tmp;ElementTypeX;intN,i;BST=NULL;scanf(%d,&N);for(i=0;iN;i++){scanf(%d,&X);BST=Insert(BST,X);}printf(Preorder:);PreorderTraversal(BST);printf(\n);MinP=FindMin(BST);MaxP=FindMax(BST);scanf(%d,&N);for(i=0;iN;i++){scanf(%d,&X);Tmp=Find(BST,X);if(Tmp==NULL)printf(%disnotfound\n,X);else{printf(%disfound\n,Tmp-Data);if(Tmp==MinP)printf(%disthesmallestkey\n,Tmp-Data);if(Tmp==MaxP)printf(%disthelargestkey\n,Tmp-Data);}}scanf(%d,&N);for(i=0;iN;i++){scanf(%d,&X);BST=Delete(BST,X);}printf(Inorder:);InorderTraversal(BST);printf(\n);return0;}BinTreeInsert(BinTreeBST,ElementTypeX){if(!BST){BST=(BinTree)malloc(sizeof(structTNode));BST-Data=X;BST-Left=BST-Right=NULL;}else{if(XBST-Data){BST-Left=Insert(BST-Left,X);}elseif(XBST-Data){BST-Right=Insert(BST-Right,X);}}returnBST;}BinTreeDelete(BinTreeBST,ElementTypeX){PositionTmp;if(!BST)printf(NotFound\n);else{if(XBST-Data)BST-Left=Delete(BST-Left,X);elseif(XBST-Data)BST-Right=Delete(BST-Right,X);else{if(BST-Left&&BST-Right){Tmp=FindMin(BST-Right);BST-Data=Tmp-Data;BST-Right=Delete(BST-Right,BST-Data);}else{Tmp=BST;if(!BST-Left)BST=BST-Right;elseif(!BST-Right)BST=BST-Left;free(Tmp);}}}returnBST;}PositionFind(BinTreeBST,ElementTypeX){if(!BST)returnNULL;if(BST-Data==X)returnBST;if(XBST-Data)returnFind(BST-Right,X);if(XBST-Data)returnFind(BST-Left,X);}PositionFindMin(BinTreeBST){if(BST){while(BST-Left){BST=BST-Left;}}returnBST;}PositionFindMax(BinTreeBST){if(BST){while(BST-Right){BST=BST-Right;}}returnBST;}4-4求二叉树高度(20分)本题要求给定二叉树的高度。函数接口定义：intGetHeight(BinTreeBT);其中BinTree结构定义如下：typedefstructTNode*Position;typedefPositionBinTree;structTNode{ElementTypeData;BinTreeLeft;BinTreeRight;};要求函数返回给定二叉树BT的高度值。裁判测试程序样例：#includestdio.h#includestdlib.htypedefcharElementType;typedefstructTNode*Position;typedefPositionBinTree;structTNode{ElementTypeData;BinTreeLeft;BinTreeRight;};BinTreeCreatBinTree();/*实现细节忽略*/intGetHeight(BinTreeBT);intmain(){BinTreeBT=CreatBinTree();printf(%d\n,GetHeight(BT));return0;}/*你的代码将被嵌在这里*/输出样例（对于图中给出的树）：intGetHeight(BinTreeBT){intLD,RD;if(BT==NULL){return0;}else{LD=GetHeight(BT-Left);RD=GetHeight(BT-Right);return(LDRD?LD:RD)+1;}}4-5链表拼接(20分)本题要求实现一个合并两个有序链表的简单函数。链表结点定义如下：structListNode{intdata;structListNode*next;};函数接口定义：structListNode*mergelists(structListNode*list1,structListNode*list2);其中list1和list2是用户传入的两个按data升序链接的链表的头指针；函数mergelists将两个链表合并成一个按data升序链接的链表，并返回结果链表的头指针。裁判测试程序样例：#includestdio.h#includestdlib.hstructListNode{intdata;structListNode*next;};structL