数据结构编程题

/* alg10-10.c 归并排序，包括算法10.12～10.14 */ #include

typedef int InfoType; /* 定义其它数据项的类型 */ #include\"c9-7.h\" #include\"c10-1.h\"

void Merge(RedType SR[],RedType TR[],int i,int m,int n)

{ /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 */ int j,k,l;

for(j=m+1,k=i;i<=m&&j<=n;++k) /* 将SR中记录由小到大地并入TR */ if LQ(SR[i].key,SR[j].key) TR[k]=SR[i++]; else

TR[k]=SR[j++]; if(i<=m)

for(l=0;l<=m-i;l++)

TR[k+l]=SR[i+l]; /* 将剩余的SR[i..m]复制到TR */ if(j<=n)

for(l=0;l<=n-j;l++)

TR[k+l]=SR[j+l]; /* 将剩余的SR[j..n]复制到TR */ }

void MSort(RedType SR[],RedType TR1[],int s, int t) { /* 将SR[s..t]归并排序为TR1[s..t]。算法10.13 */ int m;

RedType TR2[MAX_SIZE+1]; if(s==t)

TR1[s]=SR[s];

else {

m=(s+t)/2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */

MSort(SR,TR2,s,m); /* 递归地将SR[s..m]归并为有序的TR2[s..m] */

MSort(SR,TR2,m+1,t); /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */ Merge(TR2,TR1,s,m,t); /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */ }

}

void MergeSort(SqList *L)

{ /* 对顺序表L作归并排序。算法10.14 */ MSort((*L).r,(*L).r,1,(*L).length); }

void print(SqList L) {

int i;

for(i=1;i<=L.length;i++)

printf(\"(%d,%d)\

printf(\"\\n\"); }

#define N 7 void main() {

RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7}}; SqList l; int i;

for(i=0;iMergeSort(&l);

printf(\"排序后:\\n\"); print(l); }

快速排序

/* algo10-5.c 调用算法10.6(a)的程序 */ #include

typedef int InfoType; /* 定义其它数据项的类型 */ #include\"c10-1.h\"

int Partition(SqList *L,int low,int high)

{ /* 交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位， */

/* 并返回其所在位置，此时在它之前(后)的记录均不大(小)于它。算法10.6(a) */ RedType t;

KeyType pivotkey;

pivotkey=(*L).r[low].key; /* 用子表的第一个记录作枢轴记录 */ while(low{ /* 从表的两端交替地向中间扫描 */

while(low=pivotkey) --high;

t=(*L).r[low]; /* 将比枢轴记录小的记录交换到低端 */ (*L).r[low]=(*L).r[high]; (*L).r[high]=t;

while(lowt=(*L).r[low]; /* 将比枢轴记录大的记录交换到高端 */ (*L).r[low]=(*L).r[high]; (*L).r[high]=t;

}

return low; /* 返回枢轴所在位置 */ }

#include\"bo10-2.c\"

#define N 8 void main() {

RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}}; SqList l; int i;

for(i=0;iQuickSort(&l);

printf(\"排序后:\\n\"); print(l); }

/* algo10-6.c 调用算法10.6(b)的程序(算法10.6(a)的改进) */ #include

typedef int InfoType; /* 定义其它数据项的类型 */ #include\"c10-1.h\"

int Partition(SqList *L,int low,int high)

{ /* 交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其 */ /* 所在位置，此时在它之前(后)的记录均不大(小)于它。算法10.6(b) */ KeyType pivotkey;

(*L).r[0]=(*L).r[low]; /* 用子表的第一个记录作枢轴记录 */ pivotkey=(*L).r[low].key; /* 枢轴记录关键字 */ while(low< high)

{ /* 从表的两端交替地向中间扫描 */

while(low=pivotkey) --high;

(*L).r[low]=(*L).r[high]; /* 将比枢轴记录小的记录移到低端 */ while(low++low;

(*L).r[high]=(*L).r[low]; /* 将比枢轴记录大的记录移到高端 */ }

(*L).r[low]=(*L).r[0]; /* 枢轴记录到位 */ return low; /* 返回枢轴位置 */ }

#include\"bo10-2.c\" #define N 8 void main()

{

RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}}; SqList l;

int i;

for(i=0;iprintf(\"排序前:\\n\"); print(l); QuickSort(&l); printf(\"排序后:\\n\"); print(l); }

󰀀第三、二叉树排序

/* bo6-1.c 二叉树的顺序存储(存储结构由c6-1.h定义)的基本操作(23个) */ #define ClearBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */ #define DestroyBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */ void InitBiTree(SqBiTree T)

{ /* 构造空二叉树T。因为T是数组名，故不需要& */ int i;

for(i=0;iT[i]=Nil; /* 初值为空(Nil在主程中定义) */ }

void CreateBiTree(SqBiTree T)

{ /* 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T */ int i=0;

#if CHAR /* 结点类型为字符 */ int l;

char s[MAX_TREE_SIZE];

InitBiTree(T); /* 构造空二叉树T */

printf(\"请按层序输入结点的值(字符)，空格表示空结点，结点数≤%d:\\n\ gets(s); /* 输入字符串 */

l=strlen(s); /* 求字符串的长度 */ for(;i#else /* 结点类型为整型 */

InitBiTree(T); /* 构造空二叉树T */

printf(\"请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\\n\ while(1) {

scanf(\"%d\ if(T[i]==999) {

T[i]=Nil; break;

}

i++; } #endif

for(i=1;iif(T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此非根结点(不空)无双亲 */ {

printf(\"出现无双亲的非根结点\"form\"\\n\ exit(ERROR); }

}

Status BiTreeEmpty(SqBiTree T)

{ /* 初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE，否则FALSE */

if(T[0]==Nil) /* 根结点为空，则树空 */ return TRUE; else

return FALSE; }

int BiTreeDepth(SqBiTree T)

{ /* 初始条件：二叉树T存在。操作结果：返回T的深度 */ int i,j=-1;

for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最后一个结点 */ if(T[i]!=Nil) break;

i++; /* 为了便于计算 */ do

j++;

while(i>=pow(2,j)); return j;

}

Status Root(SqBiTree T,TElemType *e)

{ /* 初始条件：二叉树T存在。操作结果：当T不空，用e返回T的根，返回OK；否则返回ERROR，e无定义 */ if(BiTreeEmpty(T)) /* T空 */ return ERROR; else {

*e=T[0]; return OK; }

}

TElemType Value(SqBiTree T,position e)

{ /* 初始条件：二叉树T存在，e是T中某个结点(的位置) */

/* 操作结果：返回处于位置e(层,本层序号)的结点的值 */ return T[(int)pow(2,e.level-1)+e.order-2]; }

Status Assign(SqBiTree 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==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /* 给双亲赋空值但有叶子(不空) */ return ERROR; T[i]=value; return OK; }

TElemType Parent(SqBiTree T,TElemType e)

{ /* 初始条件：二叉树T存在，e是T中某个结点 */

/* 操作结果：若e是T的非根结点，则返回它的双亲，否则返回＂空＂ */ int i;

if(T[0]==Nil) /* 空树 */ return Nil;

for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) /* 找到e */ return T[(i+1)/2-1]; return Nil; /* 没找到e */ }

TElemType LeftChild(SqBiTree T,TElemType e)

{ /* 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子,则返回\"空\" */ int i;

if(T[0]==Nil) /* 空树 */

return Nil;

for(i=0;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) /* 找到e */ return T[i*2+1]; return Nil; /* 没找到e */ }

TElemType RightChild(SqBiTree T,TElemType e)

{ /* 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子,则返回\"空\" */ int i;

if(T[0]==Nil) /* 空树 */

return Nil;

for(i=0;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) /* 找到e */

return T[i*2+2];

return Nil; /* 没找到e */ }

TElemType LeftSibling(SqBiTree T,TElemType e)

{ /* 初始条件：二叉树T存在，e是T中某个结点 */

/* 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回＂空＂ */ int i;

if(T[0]==Nil) /* 空树 */ return Nil;

for(i=1;i<=MAX_TREE_SIZE-1;i++)

if(T[i]==e&&i%2==0) /* 找到e且其序号为偶数(是右孩子) */ return T[i-1]; return Nil; /* 没找到e */ }

TElemType RightSibling(SqBiTree T,TElemType e) { /* 初始条件：二叉树T存在，e是T中某个结点 */

/* 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回＂空＂ */ int i;

if(T[0]==Nil) /* 空树 */ return Nil;

for(i=1;i<=MAX_TREE_SIZE-1;i++)

if(T[i]==e&&i%2) /* 找到e且其序号为奇数(是左孩子) */ return T[i+1];

return Nil; /* 没找到e */ }

void Move(SqBiTree q,int j,SqBiTree T,int i) /* InsertChild()用到。加 */ { /* 把从q的j结点开始的子树移为从T的i结点开始的子树 */

if(q[2*j+1]!=Nil) /* q的左子树不空 */

Move(q,(2*j+1),T,(2*i+1)); /* 把q的j结点的左子树移为T的i结点的左子树 */ if(q[2*j+2]!=Nil) /* q的右子树不空 */

Move(q,(2*j+2),T,(2*i+2)); /* 把q的j结点的右子树移为T的i结点的右子树 */ T[i]=q[j]; /* 把q的j结点移为T的i结点 */ q[j]=Nil; /* 把q的j结点置空 */ }

void InsertChild(SqBiTree T,TElemType p,int LR,SqBiTree 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,BiTreeDepth(T))-1;j++) /* 查找p的序号 */ if(T[j]==p) /* j为p的序号 */ break;

k=2*j+1+LR; /* k为p的左或右孩子的序号 */

if(T[k]!=Nil) /* p原来的左或右孩子不空 */

Move(T,k,T,2*k+2); /* 把从T的k结点开始的子树移为从k结点的右子树开始的子树 */

Move(c,i,T,k); /* 把从c的i结点开始的子树移为从T的k结点开始的子树 */ }

typedef int QElemType; /* 设队列元素类型为整型(序号) */ #include \"c3-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; /* 将层、本层序号转为矩阵的序号 */ if(T[i]==Nil) /* 此结点空 */ return ERROR;

i=i*2+1+LR; /* 待删除子树的根结点在矩阵中的序号 */ while(k) {

if(T[2*i+1]!=Nil) /* 左结点不空 */

EnQueue(&q,2*i+1); /* 入队左结点的序号 */ if(T[2*i+2]!=Nil) /* 右结点不空 */

EnQueue(&q,2*i+2); /* 入队右结点的序号 */ T[i]=Nil; /* 删除此结点 */

k=DeQueue(&q,&i); /* 队列不空 */ }

return OK; }

void(*VisitFunc)(TElemType); /* 函数变量 */ void PreTraverse(SqBiTree T,int e) { /* PreOrderTraverse()调用 */ VisitFunc(T[e]);

if(T[2*e+1]!=Nil) /* 左子树不空 */ PreTraverse(T,2*e+1);

if(T[2*e+2]!=Nil) /* 右子树不空 */ PreTraverse(T,2*e+2); }

void PreOrderTraverse(SqBiTree T,void(*Visit)(TElemType)) { /* 初始条件：二叉树存在，Visit是对结点操作的应用函数 */

/* 操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次 */ VisitFunc=Visit;

if(!BiTreeEmpty(T)) /* 树不空 */

PreTraverse(T,0);

printf(\"\\n\"); }

void InTraverse(SqBiTree T,int e) { /* InOrderTraverse()调用 */ if(T[2*e+1]!=Nil) /* 左子树不空 */ InTraverse(T,2*e+1);

VisitFunc(T[e]);

if(T[2*e+2]!=Nil) /* 右子树不空 */ InTraverse(T,2*e+2);

}

void InOrderTraverse(SqBiTree T,void(*Visit)(TElemType))

{ /* 初始条件：二叉树存在，Visit是对结点操作的应用函数 */

/* 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次 */ VisitFunc=Visit;

if(!BiTreeEmpty(T)) /* 树不空 */ InTraverse(T,0); printf(\"\\n\"); }

void PostTraverse(SqBiTree T,int e) { /* PostOrderTraverse()调用 */

if(T[2*e+1]!=Nil) /* 左子树不空 */ PostTraverse(T,2*e+1);

if(T[2*e+2]!=Nil) /* 右子树不空 */ PostTraverse(T,2*e+2); VisitFunc(T[e]);

}

void PostOrderTraverse(SqBiTree T,void(*Visit)(TElemType))

{ /* 初始条件：二叉树T存在，Visit是对结点操作的应用函数 */ /* 操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次 */ VisitFunc=Visit;

if(!BiTreeEmpty(T)) /* 树不空 */ PostTraverse(T,0); printf(\"\\n\"); }

void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType)) { /* 层序遍历二叉树 */

int i=MAX_TREE_SIZE-1,j; while(T[i]==Nil)

i--; /* 找到最后一个非空结点的序号 */

for(j=0;j<=i;j++) /* 从根结点起，按层序遍历二叉树 */ if(T[j]!=Nil)

Visit(T[j]); /* 只遍历非空的结点 */

printf(\"\\n\");

}

void Print(SqBiTree T)

{ /* 逐层、按本层序号输出二叉树 */ int j,k; position p; TElemType e;

for(j=1;j<=BiTreeDepth(T);j++) {

printf(\"第%d层: \ 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\" \ }

printf(\"\\n\"); } } 󰀀