2022年数据结构编程题 .pdf

《2022年数据结构编程题 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构编程题 .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一，归并排序/* alg10-10.c 归并排序，包括算法10.12 10.14 */ #include typedef int InfoT ype; /* 定义其它数据项的类型*/ #includec9-7.h #includec10-1.h void Merge(RedType SR,RedT ype TR,int i,int m,int n) /* 将有序的SRi.m和 SRm+1.n 归并为有序的TRi.n 算法 10.12 */ int j,k,l; for(j=m+1,k=i;i=m&j=n;+k) /* 将 SR 中记录由小到大地并入TR */ if LQ(SRi.key ,S

2、Rj.key) TRk=SRi+; else TRk=SRj+; if(i=m) for(l=0;l=m-i;l+) TRk+l=SRi+l; /* 将剩余的SRi.m 复制到 TR */ if(j=n) for(l=0;l=n-j;l+) TRk+l=SRj+l; /* 将剩余的SRj.n复制到TR */ void MSort(RedT ype SR,RedT ype TR1,int s, int t) /* 将 SRs.t归并排序为TR1s.t 。算法 10.13 */ int m; RedType TR2MAX_SIZE+1;if(s=t) TR1s=SRs; else m=(s+t)/

3、2; /* 将 SRs.t平分为 SRs.m和 SRm+1.t */ MSort(SR,TR2,s,m); /* 递归地将SRs.m归并为有序的TR2s.m */ MSort(SR,TR2,m+1,t); /* 递归地将SRm+1.t 归并为有序的TR2m+1.t */ Merge(TR2,TR1,s,m,t); /* 将 TR2s.m 和 TR2m+1.t 归并到TR1s.t */ void MergeSort(SqList *L) /* 对顺序表L 作归并排序。算法10.14 */ MSort(*L).r ,(*L).r,1,(*L).length); void print(SqList

4、L) int i; for(i=1;i=L.length;i+) printf(%d,%d),L.ri.key,L.ri.otherinfo); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - printf(n); #define N 7 void main() RedType dN=49,1,38,2,65,3,97,4,76,5,13,6,27,7; SqList l; int i; for(i=0;iN;i+) l.ri

5、+1=di; l.length=N; printf( 排序前 :n); print(l); MergeSort(&l); printf( 排序后 :n); print(l); 快速排序/* algo10-5.c 调用算法10.6(a)的程序*/ #include typedef int InfoT ype; /* 定义其它数据项的类型*/ #includec10-1.h int Partition(SqList *L,int low ,int high) /* 交换顺序表L 中子表L.rlow.high的记录，使枢轴记录到位，*/ /* 并返回其所在位置，此时在它之前(后)的记录均不大(小 )

6、于它。算法10.6(a) */ RedType t; KeyType pivotkey; pivotkey=(*L).rlow.key; /* 用子表的第一个记录作枢轴记录*/ while(lowhigh) /* 从表的两端交替地向中间扫描*/ while(low=pivotkey) -high; t=(*L).rlow; /* 将比枢轴记录小的记录交换到低端*/ (*L).rlow=(*L).rhigh; (*L).rhigh=t; while(lowhigh&(*L).rlow.key=pivotkey) +low; t=(*L).rlow; /* 将比枢轴记录大的记录交换到高端*/ (*

7、L).rlow=(*L).rhigh; (*L).rhigh=t; return low; /* 返回枢轴所在位置*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - #includebo10-2.c #define N 8 void main() RedType dN=49,1,38,2,65,3,97,4,76,5,13,6,27,7,49,8; SqList l; int i; for(i=0;iN;i+) l.ri+1

8、=di; l.length=N; printf( 排序前 :n); print(l); QuickSort(&l); printf( 排序后 :n); print(l); /* algo10-6.c 调用算法10.6(b)的程序 (算法 10.6(a)的改进 ) */ #include typedef int InfoT ype; /* 定义其它数据项的类型*/ #includec10-1.h int Partition(SqList *L,int low ,int high) /* 交换顺序表L 中子表rlow.high的记录，枢轴记录到位，并返回其*/ /* 所在位置，此时在它之前(后 )

9、的记录均不大(小 )于它。算法10.6(b) */ KeyType pivotkey; (*L).r0=(*L).rlow; /* 用子表的第一个记录作枢轴记录*/ pivotkey=(*L).rlow.key; /* 枢轴记录关键字*/ while(low high) /* 从表的两端交替地向中间扫描*/ while(low=pivotkey) -high; (*L).rlow=(*L).rhigh; /* 将比枢轴记录小的记录移到低端*/ while(lowhigh&(*L).rlow.key=pivotkey) +low; (*L).rhigh=(*L).rlow; /* 将比枢轴记录大

10、的记录移到高端*/ (*L).rlow=(*L).r0; /* 枢轴记录到位*/ return low; /* 返回枢轴位置*/ #includebo10-2.c #define N 8 void main() RedType dN=49,1,38,2,65,3,97,4,76,5,13,6,27,7,49,8; SqList l; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - int i; for(i=0;iN;i+) l

11、.ri+1=di; l.length=N; printf( 排序前 :n); print(l); QuickSort(&l); printf( 排序后 :n); print(l); 第三、二叉树排序/* bo6-1.c 二叉树的顺序存储(存储结构由c6-1.h定义 )的基本操作 (23 个) */ #define ClearBiTree InitBiT ree /* 在顺序存储结构中，两函数完全一样*/ #define DestroyBiTree InitBiT ree /* 在顺序存储结构中，两函数完全一样*/ void InitBiT ree(SqBiTree T) /* 构造空二叉树T。

12、因为T 是数组名，故不需要& */ int i; for(i=0;iMAX_TREE_SIZE;i+)Ti=Nil; /* 初值为空 (Nil 在主程中定义) */ void CreateBiTree(SqBiTree T) /* 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T */ int i=0; #if CHAR /* 结点类型为字符*/ int l; char sMAX_TREE_SIZE;InitBiT ree(T); /* 构造空二叉树T */ printf(请 按 层 序 输 入 结 点 的 值 ( 字 符 ) ， 空 格 表 示 空 结 点 ， 结 点

13、 数%d:n,MAX_TREE_SIZE); gets(s); /* 输入字符串*/ l=strlen(s); /* 求字符串的长度*/ for(;il;i+) /* 将字符串赋值给T */ Ti=si; #else /* 结点类型为整型*/ InitBiT ree(T); /* 构造空二叉树T */ printf( 请 按 层 序 输 入 结 点 的 值 ( 整 型 )， 0 表 示 空 结 点 ， 输999 结 束 。 结 点 数%d:n,MAX_TREE_SIZE); while(1) scanf(%d,&Ti); if(Ti=999) Ti=Nil; break; 名师资料总结 - -

14、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - i+; #endif for(i=1;i=0;i-) /* 找到最后一个结点*/ if(Ti!=Nil) break; i+; /* 为了便于计算*/ do j+; while(i=pow(2,j); return j; Status Root(SqBiTree T,TElemT ype *e) /* 初始条件：二叉树T 存在。操作结果：当T 不空，用e 返回 T的根，返回OK；否则返回 ERROR

15、 ，e 无定义*/ if(BiTreeEmpty(T) /* T空*/ return ERROR; else *e=T0; return OK; TElemType Value(SqBiTree T,position e) /* 初始条件：二叉树T 存在， e 是 T 中某个结点 (的位置 ) */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - /* 操作结果：返回处于位置e(层 ,本层序号 )的结点的值*/ return

16、T(int)pow(2,e.level-1)+e.order-2; Status Assign(SqBiT ree T,position e,TElemType value) /* 初始条件：二叉树T 存在， e 是 T 中某个结点 (的位置 ) */ /* 操作结果：给处于位置e(层 ,本层序号 )的结点赋新值value */ int i=(int)pow(2,e.level-1)+e.order-2; /* 将层、本层序号转为矩阵的序号*/ if(value!=Nil&T(i+1)/2-1=Nil) /* 给叶子赋非空值但双亲为空*/ return ERROR; else if(value

17、=Nil&(Ti*2+1!=Nil|Ti*2+2!=Nil) /* 给双亲赋空值但有叶子(不空 ) */ return ERROR; Ti=value; return OK; TElemType Parent(SqBiTree T,TElemType e) /* 初始条件：二叉树T 存在， e 是 T 中某个结点*/ /* 操作结果：若e 是 T 的非根结点，则返回它的双亲，否则返回空*/ int i; if(T0=Nil) /* 空树*/ return Nil; for(i=1;i=MAX_TREE_SIZE-1;i+) if(Ti=e) /* 找到 e */ return T(i+1)/2

18、-1; return Nil; /* 没找到 e */ TElemType LeftChild(SqBiT ree T,TElemT ype e) /* 初始条件：二叉树T 存在， e 是 T 中某个结点。操作结果：返回e 的左孩子。若e 无左孩子 ,则返回 空 */ int i; if(T0=Nil) /* 空树*/ return Nil; for(i=0;i=MAX_TREE_SIZE-1;i+) if(Ti=e) /* 找到 e */ return Ti*2+1; return Nil; /* 没找到 e */ TElemT ype RightChild(SqBiT ree T,TEle

19、mType e) /* 初始条件：二叉树T 存在， e 是 T 中某个结点。操作结果：返回e 的右孩子。若e 无右孩子 ,则返回 空 */ int i; if(T0=Nil) /* 空树*/ return Nil; for(i=0;i=MAX_TREE_SIZE-1;i+) if(Ti=e) /* 找到 e */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - return Ti*2+2; return Nil; /* 没找到

20、 e */ TElemT ype LeftSibling(SqBiT ree T,TElemType e) /* 初始条件：二叉树T 存在， e 是 T 中某个结点*/ /* 操作结果：返回e 的左兄弟。若e 是 T 的左孩子或无左兄弟，则返回空*/ int i; if(T0=Nil) /* 空树*/ return Nil; for(i=1;i=MAX_TREE_SIZE-1;i+) if(Ti=e&i%2=0) /* 找到 e且其序号为偶数(是右孩子 ) */ return Ti-1; return Nil; /* 没找到 e */ TElemType RightSibling(SqBiT

21、ree T,TElemT ype e) /* 初始条件：二叉树T 存在， e 是 T 中某个结点*/ /* 操作结果：返回e 的右兄弟。若e 是 T 的右孩子或无右兄弟，则返回空*/ int i; if(T0=Nil) /* 空树*/ return Nil; for(i=1;i=MAX_TREE_SIZE-1;i+) if(Ti=e&i%2) /* 找到 e 且其序号为奇数(是左孩子 ) */ return Ti+1; return Nil; /* 没找到 e */ void Move(SqBiTree q,int j,SqBiT ree T,int i) /* InsertChild()用到

22、。加*/ /* 把从 q的 j 结点开始的子树移为从T 的 i 结点开始的子树*/ if(q2*j+1!=Nil) /* q的左子树不空*/ Move(q,(2*j+1),T ,(2*i+1); /* 把 q的 j 结点的左子树移为T 的 i 结点的左子树*/ if(q2*j+2!=Nil) /* q的右子树不空*/ Move(q,(2*j+2),T ,(2*i+2); /* 把 q的 j 结点的右子树移为T 的 i 结点的右子树*/ Ti=qj; /* 把 q的 j 结点移为T 的 i 结点*/ qj=Nil; /* 把 q的 j 结点置空*/ void InsertChild(SqBiT

23、ree T,TElemType p,int LR,SqBiT ree c) /* 初始条件：二叉树T 存在， p 是 T 中某个结点的值，LR 为 0 或 1，非空二叉树c与 T不相交且右子树为空*/ /* 操作结果 : 根据 LR 为 0 或 1,插入 c为 T 中 p结点的左或右子树。p 结点的原有左或右子树则成为c的右子树*/ int j,k,i=0; for(j=0;j(int)pow(2,BiT reeDepth(T)-1;j+) /* 查找 p的序号*/ if(Tj=p) /* j为 p的序号*/ break; k=2*j+1+LR; /* k为 p的左或右孩子的序号*/ 名师资料

24、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - if(Tk!=Nil) /* p原来的左或右孩子不空*/ Move(T,k,T,2*k+2); /* 把从 T的 k 结点开始的子树移为从k 结点的右子树开始的子树*/ Move(c,i,T,k); /* 把从 c的 i 结点开始的子树移为从T 的 k 结点开始的子树*/ typedef int QElemT ype; /* 设队列元素类型为整型(序号 ) */ #include c3-

25、2.h /* 链队列*/ #include bo3-2.c /* 链队列的基本操作*/ Status DeleteChild(SqBiTree T,position p,int LR) /* 初始条件：二叉树T 存在， p指向 T 中某个结点，LR 为 1 或 0 */ /* 操作结果：根据LR 为 1 或 0，删除T 中 p所指结点的左或右子树*/ int i; Status k=OK; /* 队列不空的标志*/ LinkQueue q; InitQueue(&q); /* 初始化队列，用于存放待删除的结点*/ i=(int)pow(2,p.level-1)+p.order-2; /* 将层

26、、本层序号转为矩阵的序号*/ if(Ti=Nil) /* 此结点空*/ return ERROR; i=i*2+1+LR; /* 待删除子树的根结点在矩阵中的序号*/ while(k) if(T2*i+1!=Nil) /* 左结点不空*/ EnQueue(&q,2*i+1); /* 入队左结点的序号*/ if(T2*i+2!=Nil) /* 右结点不空*/ EnQueue(&q,2*i+2); /* 入队右结点的序号*/ Ti=Nil; /* 删除此结点*/ k=DeQueue(&q,&i); /* 队列不空*/ return OK; void(*VisitFunc)(TElemT ype);

27、 /* 函数变量*/ void PreTraverse(SqBiTree T,int e) /* PreOrderT raverse() 调用*/ VisitFunc(Te); if(T2*e+1!=Nil) /* 左子树不空*/ PreTraverse(T,2*e+1); if(T2*e+2!=Nil) /* 右子树不空*/ PreTraverse(T,2*e+2); void PreOrderT raverse(SqBiTree T,void(*Visit)(TElemT ype) /* 初始条件：二叉树存在，Visit 是对结点操作的应用函数*/ /* 操作结果：先序遍历T，对每个结点调

28、用函数Visit 一次且仅一次*/ VisitFunc=Visit; if(!BiTreeEmpty(T) /* 树不空*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - PreTraverse(T,0); printf(n); void InTraverse(SqBiTree T,int e) /* InOrderT raverse()调用*/ if(T2*e+1!=Nil) /* 左子树不空*/ InTraverse(T

29、,2*e+1); VisitFunc(Te); if(T2*e+2!=Nil) /* 右子树不空*/ InTraverse(T,2*e+2); void InOrderT raverse(SqBiTree T,void(*Visit)(TElemT ype) /* 初始条件：二叉树存在，Visit 是对结点操作的应用函数*/ /* 操作结果：中序遍历T，对每个结点调用函数Visit 一次且仅一次*/ VisitFunc=Visit; if(!BiTreeEmpty(T) /* 树不空*/ InTraverse(T,0); printf(n); void PostTraverse(SqBiTre

30、e T,int e) /* PostOrderT raverse()调用*/ if(T2*e+1!=Nil) /* 左子树不空*/ PostTraverse(T,2*e+1); if(T2*e+2!=Nil) /* 右子树不空*/ PostTraverse(T,2*e+2); VisitFunc(Te); void PostOrderTraverse(SqBiTree T,void(*Visit)(TElemT ype) /* 初始条件：二叉树T 存在， Visit 是对结点操作的应用函数*/ /* 操作结果：后序遍历T，对每个结点调用函数Visit 一次且仅一次*/ VisitFunc=Vi

31、sit; if(!BiTreeEmpty(T) /* 树不空*/ PostTraverse(T,0); printf(n); void LevelOrderT raverse(SqBiTree T,void(*Visit)(TElemT ype) /* 层序遍历二叉树*/ int i=MAX_TREE_SIZE-1,j; while(Ti=Nil) i-; /* 找到最后一个非空结点的序号*/ for(j=0;j=i;j+) /* 从根结点起，按层序遍历二叉树*/ if(Tj!=Nil) Visit(Tj); /* 只遍历非空的结点*/ 名师资料总结 - - -精品资料欢迎下载 - - - -

32、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - printf(n); void Print(SqBiTree T) /* 逐层、按本层序号输出二叉树*/ int j,k; position p; TElemType e; for(j=1;j=BiT reeDepth(T);j+) printf( 第%d 层 : ,j); for(k=1;k=pow(2,j-1);k+) p.level=j; p.order=k; e=Value(T,p); if(e!=Nil) printf(%d:form ,k,e); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -