hsd数据结构期末考

hsd数据结构期末考

考题1:有序表归并算法实现

问题描述：对任意输入的两个按值非递减有序的整数序列，写一程序将它们归并成一个按值非递减有序序列

输入描述：文本文件&#"中保存了n个测试用例，文件以-1结束。每个用例的第一行m1表示第一个待归并有序序列的元素个数，第二行为该序列的m1个元素，第三行m2表示第二个待归并有序序列的元素个数，第四行为该序列的m2个元素

输出描述：输出结果保存在文本文件&#"中。对于每个测试用例均有二行输出，第一行输出"Case #:##"，#表示用例的编号(1…n)，##表示归并后有序序列的元素个数；第二行输出##个按值非递减有序元素

输入示例：

​ 5

​ 1 4 8 10 30

​ 7

​ 2 4 20 35 50 60 86

​ 3

​ 38 45 100

​ 4

​ 38 45 100 120

​ -1

输出示例：

​ Case 1:12

​ 1 2 4 4 8 10 20 30 35 50 60 86

​ Case 2:7

​ 38 38 45 50 100 100 120

本题使用 有序表 相关知识

SqList.h

#ifndef SQLIST_H
#define SQLIST_H
#include"Public.h"
#define LIST_INIT_SIZE 2000
#define LISTINCREMENT 100typedef int Elemtype;
typedef struct{ElemType* elem;int length;int listsize;
}SqList;void MergeList1(SqList La,SqList Lb,SqList& Lc);
Status InitList_Sq(SqList& L);
void GetElem(SqList L,int i,ElemType& e);
Status ListInsert_Sq(SqList& L,int i,Element e);
void FPrint(SqList L,int CaseID,FILE* fout);
int FRead(SqList& L,FILE* fin);
void DestroyList_Sq(SqList& L);
#endif

SqList.cpp

#include<stdio.h>
#include<stdlib.h>
#include "Public.h"
#include "SqList.h"Status InitList_Sq(SqList& L)
{MALLOC(L.elem,LIST_INIT_SIZE * sizeof(ElemType),ElemType*);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK;
}int FRead(SqList& L,FILE* fin)
{int n;fscanf(fin,"%d",&n);if(-1 == n) return n;L.length = n;for(int i = 0;i < n;i++){fscanf(fin,"%d",&L.elem[i]);  }return OK;
}void MergeList1(SqList La,SqList Lb,SqList& Lc)
{int i,j,k,La_len,Lb_len;ElemType ai,bj;La_len = La.length;Lb_len = Lb.length;i = j = 1;k = 0;while(i <= La_len && j < Lb_len){GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai <= bj){ListInsert_Sq(Lc,++k,ai);++i;}else{ListInsert_Sq(Lc,++k,bj);++j}}while(i <= La_len){GetElem(La,i++,ai);ListInsert_Sq(Lc,++k,ai);}while(j <= Lb_len){GetElem(Lb,j++,bj);ListInsert_Sq(Lc,++k,bj);}
}void GetElem(SqList L,int i,ElemType& e)
{e = L.elem[i-1];
}Status ListInsert_Sq(SqList& L,int i,ElemType e)
{//在顺序线性表L中第i个位置之前插入新的元素eElemType* p,* q,* newBase;if(i<1 || i>L.length+1) return ERROR;if(L.length >= L.listsize){newBase = (ElemType*)realloc(L.elem,(L.listsize + LISTINCREMENT)*sizeof(ElemType));if(!newBase)exit(OVERFLOW);L.elem = newBase;L.listsize += LISTINCREMENT;}q = &(L.elem[i-1]);			//q指示插入位置for(p = &(L.elem[L.length - 1]);p >= q; --p)*(p+1) = *p;					//插入位置及之后的元素右移*q = e;++L.length;							//表长增加1return OK;
}void FPrint(SqList L,int CaseID,FILE* fout)
{fprintf(fout,"Case &d:%dn",CaseID,L.length);for(int i = 0;i < L.length;i++){fprintf(fout,"%d",L.elem[i]);}fprintf(fout,"n");
}void DestroyList_Sq(SqList& L)
{FREE(L.elem);L.length = 0;
}

main.cpp

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#inlcude"SqList.h"
void main()
{int ID = 1;SqList La,Lb,Lc;InitList_Sq(La);InitList_Sq(Lb);InitList_Sq(Lc);FILE* fin,* fout;fin = fopen(&#","r");fout = fopen(&#","w");while(FRead(La,fin) == OK){FRead(Lb,fin);MergeList1(La,Lb,Lc);FPrint(Lc,++ID,fout);DestroyList_Sq(La);DestroyList_Sq(Lb);DestroyList_Sq(Lc);}fclose(fout);fclose(fin);system("pause"); 
}

考题3:二叉树的中序非递归遍历算法实现

问题描述：对任意输入的表示某二叉树的字符序列，实现二叉树的中序非递归遍历算法，并输出其遍历结果

输入描述：从键盘上输入一串字符串，该字符串为二叉树的带#号的先序遍历结果，其中如果遍历到空树时用字符#代替

输出描述：从键盘输出二叉树的中序遍历结果

输入与输出示例：

​ 输入：

​ +A##/*B##C##D##

​ 输出：

​ A+B*C/D

​ 输入：

​ ABD##GJ###CFH##I###

​ 输出：

​ DBJGAHFIC

本题用到堆栈 和 树 相关知识

BiTree.h 文件

#ifndef BITREE_H
#define BITREE_H
struct node;
typedef struct node *treePointer;
typedef struct node{char data;treePointer leftChild,rightChild;
};
treePointer Create();
void iterInorder(treePointer node);
#endif

SqStack.h文件

#ifndef SQSTACK_H
#define SQSTACK_H
#include "Public.h"
#include "BiTree.h"
typedef treePointer element;
int Push_Sq(element item,element* stack,int& top);
int Pop(element* stack,int& top,element& item);
#endif

BiTree.cpp文件

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"BiTree.h"
#include"SqStack.h"treePointer Create()
{treePointer bt;char ch;scanf("%c",&ch);if(ch == '#') bt = NULL;else{MALLOC(bt,sizeof(struct node),treePointer);bt->data = ch;bt->leftChild = Create();bt->rightChild = Create();}return bt;
}void iterInorder(treePointer node)
{int top = -1;element stack[MAX_STACK_SIZE];for(;;){for(;node = node->leftChild)Push_Sq(node,stack,top);int Flag = Pop(stack,top,node);if(!Flag) break;printf("%c",node->data);node = node->rightChild;}
}

SqStack.cpp文件

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"SqStack.h"
#include"BiTree.h"int Push_Sq(element item,element* stack,int& top)
{if(top >= MAX_STACK_SIZE - 1){return FALSE;}stack[++top]  = item;return TRUE;
}int Pop(element* stack,int& top,element& item)
{if(top == -1) return FALSE;item = stack[top--];return TRUE;
}

main.cpp文件

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"BiTree.h"
#include"SqStack.h"void main()
{treePointer bt;bt = Create();iterInorder(bt);printf("n");system("pause");
}

考题4：二叉树层次遍历算法实现

问题描述：对任意输入的表示某二叉树的字符序列，实现二叉树的层次遍历算法，并输出其遍历结果

输入描述：从键盘上输入一串字符串，该字符串为二叉树的带#号的先序遍历结果，其中如果遍历到空树时用字符#代替

输出描述：从键盘输出二叉树的按层次遍历结果

输入与输出示例

​ 输入：

​ +A##/*B##C##D##

​ 输出：

​ +A/*DBC

​ 输入：

​ ABD##GJ###CFH##I###

​ 输出：

​ ABCDGFJHI

本题用 堆栈 和 二叉树 相关知识

BiTree.h

#ifndef BITREE_H
#define BITREE_H
struct node;
typedef struct node *treePointer;
typedef struct node{char data;treePointer leftChild,rightChild;
};
treePointer Create();
void levelOrder(treePointer ptr);
#endif

SqStack.h

#ifndef SQSTACK_H
#define SQSTACK_H
#include "Public.h"
#include "BiTree.h"
typedef treePointer,element;
int AddQ(element item,element *queue,int front,int &rear);
int DeleteQ(element *queue,int &front,int rear, element &item);
#endif

BiTree.cpp

#include<stdio.h>
#include<stdlib.h>
#include "Public.h"
#include "BiTree.h"
#include "SqStack.h"treePointer Create()
{treePointer bt;char ch;scanf("%c",&ch);if(ch == '#') bt = NULL;else{MALLOC(bt,sizeof(struct node),treePointer);bt->data = ch;bt->leftChild = Create();bt->rightChild = Create();}return bt;
}void levelOrder(treePointer ptr)
{int front = 0,rear = 0;element queue[MAX_QUEUE_SIZE];if(!ptr) return ;										/* empty tree */AddQ(ptr,queue,front,rear);					/* push the root onto queue */for(;;){int Flag = DeleteQ(queue,front,rear,ptr);				/* pop one node from queue */if(Flag){printf("%c",ptr->data);/* if leftChild is not NULL,push it onto queue*/if(ptr->leftChild) AddQ(ptr->leftChild,queue,front,rear); /* if rightChild is not NULL,push it onto queue*/if(ptr->rightChild) AddQ(ptr->rightChild,queue,front,rear);}else break;}
}

SqStack.cpp

#include<stdlib.h>
#include<stdio.h>
#include "Public.h"
#include "BiTree.h"
#include "SqStack.h"int AddQ(element item,element *queue,int front,int &rear)
{rear = (rear+1) % MAX_QUEUE_SIZE;if(front == rear) return FALSE;queue[rear] = item;return TRUE;
}int DeleteQ(element *queue,int &front,int rear,element &item)
{if(front == rear) return FALSE;front = (front + 1) % MAX_QUEUE_SIZE;item = queue[front];return TRUE;
}

main.cpp

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"BiTree.h"
#include"SqStack.h"void main()
{treePointer bt;bt = Create();levelOrder(bt);printf("n");system("pause");
}

考题5:堆排序算法实现

问题描述：对于任一无序正整数序列，写一程序用堆排序算法将其排序成按值非递减有序序列。

输入描述：文本文件“”中保存了n个测试用例，文件以-1结束。每个用例的第一行m表示待排序正整数序列的元素个数，第二行为该序列的m个正整数

输出描述：输出结果保存在文本文件“”中。对于每个测试用例均有二行输出，第一行输出“Case #:##”，#表示用例的编号（1…n），##表示排序后有序序列的元素个数，第二输出##个按值非递减有序元素

输入示例：

5

10 1 8 4 30

7

35 60 50 2 20 4 86

3

38 100 45

-1

输出示例：

​ Case 1:5

​ 1 4 8 10 30

​ Case 2:7

​ 2 4 20 35 50 60 86

​ Case 3:3

​ 38 45 100

本题考查堆排序算法

main.cpp

#include <stdio.h>
#include <stdlib.h>#define  MAX_SIZE 5000
#define SWAP(x,y,t) ( (t)=(x),(x)=(y),(y)=(t))
#define LeftChild(i) (2*(i)+1)
typedef int ElemType;
int FRead(FILE *fin,ElemType A[], int &N);
void FPrint(ElemType A[],int N,FILE*fout,int CaseID);	
void Heapsort (ElemType A[],int N);
void PercDown(ElemType A[],int i,int N);int main()
{ElemType A[MAX_SIZE];FILE *fin,*fout;int n;fin = fopen(&#","r");fout = fopen(&#","w");int CaseID = 0;while(1){if(FRead(fin,A,n) == -1) break;Heapsort(A,n);FPrint(A,n,fout,++CaseID);}fclose(fout);fclose(fin);system("pause");
}int FRead(FILE *fin,ElemType A[],int &N)
{fscanf(fin,"%d",&N);if(-1 == N) return N;for(int i = 0;i < N;i++)fscanf(fin,"%d",&A[i]);return 0;
}void FPrint(ElemType A[],int N,FILE *fout,int CaseID)
{fprintf(fout,"Case %d:%dn",CaseID,N);fprintf(fout,"%d",A[0]);for(int i = 1;i < N;i++) fprintf(fout,"%5d",A[i]);fprintf(fout,"n");
}void Heapsort(ElemType A[],int N)
{int i;ElemType temp;for(i = N / 2 - 1;i >= 0;i--)			//BuildHeapPercDown(A,i,N);for(i = N - 1;i > 0;i--){SWAP(A[0],A[i],temp);						//DeleteMaxPercDown(A,0,i);}
}void PercDown(ElemType A[],int i,int N)
{int Child;ElemType Temp;for(Temp = A[i];LeftChild(i) < N;i = Child){Child = LeftChild(i);if(Child != N - 1 && A[Child + 1] > A[Child])Child++;if(Temp < A[Child])A[i] = A[Child];elsebreak;}A[i] = Temp;
}

考题6：快速排序算法实现

问题描述：对于任意的无序正整数序列，写一程序用快速排序算法将其排序成按值非递减有序序列

输入描述：文本文件“”中保存了n个测试用例，文件以-1结束。每个用例的第一行m表示第一个待排序整数序列的元素个数，第二行为该序列的m个元素

输出描述：输出结果保存在文本文件“”中。对于每个测试用例均有二行输出，第一行输出“Case #:##”，#表示用例的编号（1…n），##表示排序后有序序列的元素个数，第二输出##个按值非递减有序元素

输入示例：

5

10 1 8 4 30

7

35 60 50 2 20 4 86

3

38 100 45

-1

输出示例：

​ Case 1:5

​ 1 4 8 10 30

​ Case 2:7

​ 2 4 20 35 50 60 86

​ Case 3:3

​ 38 45 100

本题考查快速排序算法

main.cpp

#include<stdio.h>
#include<stdlib.h>#define MAX_SIZE 5000
#define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t))
typedef int ElemType;
int FRead(FILE *fin,ElemType A[],int &N);
void FPrint(ElemType A[],int N,FILE *fout,int CaseID);
void quickSort(ElemType A[],int left,int right);
int Partition(ElemType A[],int left,int right);int main()
{ElemType A[MAX_SIZE];FILE *fin,*fout;int n;fin = fopen(&#","r");fout = fopen(&#","w");int CaseID = 0;while(1){if(FRead(fin,A,n) == -1) break;quickSort(A,0,n-1);FPrint(A,n,fout,++CaseID);}fclose(fout);fclose(fin);system("pause");
}int FRead(FILE *fin,ElemType A[],int &N)
{fscanf(fin,"%d",&N);if(-1 == N) return N;for(int i = 0;i < N;i++)fscanf(fin,"%d",&A[i]);return 0;
}void FPrint(ElemType A[],int N,FILE *fout,int CaseID)
{fprintf(fout,"Case %d:%dn",CaseID,N);fprintf(fout,"%d",A[0]);for(int i = 1;i < N;i++) fprintf(fout,"%5d",A[i]);fprintf(fout,"n");
}void quickSort(ElemType A[],int left,int right)
{if(left < right){int nextWhere = Partition(A,left,right);quickSort(A,left,nextWhere - 1);quickSort(A,nextWhere + 1,right);}
}int Partition(ElemType A[],int left,int right)
{ElemType pivot = A[left];ElemType temp;while(left < right){while(pivot < A[right]) --right;while(pivot > A[left]) ++left;SWAP(A[right],A[left],temp);}A[left] = pivot;return left;
}

考题7:深度优先搜索

问题描述：写一程序实现图的深度优先搜索算法（DFS），并对输入的有向网或无向网输出遍历结果

输入描述：文本文件“”中保存了一个有向网的输入，文件以-1结束。第一行表示该网的顶点数n(输入示例中为6)和弧数m(输入示例中为11)；接下去m行是用(i,j,e)表示的弧，它表示从顶点i出发到顶点j的权值为e的弧。最后几行分别表示从这些顶点出发进行DFS，输出它们的结果

输出描述：输出结果保存在文本文件“”中。对每个开始搜索的顶点，都有一行，该行表示从该顶点出发进行DFS的结果

输入示例：

​ 6 11

​ 0 1 50

​ 0 2 10

​ 0 4 45

​ 1 2 15

​ 1 4 10

​ 2 0 20

​ 2 3 15

​ 3 1 20

​ 3 4 35

​ 4 3 30

​ 5 3 3

​ 1

​ 3

​ -1

输出示例：

​ DFS From V1: V1 V4 V3 V2 V0

​ DFS From V3: V3 V4 V1 V2 V0

本题考查图 和 队列 相关知识

Graph.h

#ifndef GRAPH_H
#define GRAPH_H
#include"Public.h"struct node;
typedef struct node *nodePointer;
typedef struct node{int vertex;nodePointer next;int weight;
};void CreateGraph(FILE *fin,nodePointer graph[],int &n);
void PrintGraph(nodePointer graph[],int n);
void dfs(int v,nodePointer graph[],int n,short int visited[],FILE *fout);
#endif

Graph.cpp

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"Graph.h"
#include"SqQueue.h"int b,c,d;
int front = 0,rear = 0;
void CreateGraph(FILE *fin,nodePointer graph[],int &n)
{int a;fscanf(fin,"%d %d",&n,&a);int q = -1;for(int i = 0;i < a;i++){nodePointer m;MALLOC(m,sizeof(node),nodePointer);fscanf(fin,"%d %d %d",&b,&c,&d);m->vertex = c;m->weight = d;if(q == b){m->next = graph[b];graph[b] = m;}else{m->next = NULL;graph[b] = m;}q = b;}
}void PrintGraph(nodePointer graph[],int n)
{nodePointer p;for(int i = 0;i < n;i++){printf("%d:",i);p = graph[i];while(p){printf("%d ",p->vertex);p = p->next;}printf("n");}
}void dfs(int v,nodePointer graph[],int n,short int visited[],FILE *fout)
{nodePointer w;visited[v] = TRUE;fprintf(fout,"V%d ",v);for(w = graph[v];w;w = w->next)if(!visited[w->vertex])dfs(w->vertex,graph,n,visited,fout);
}

main.cpp

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include "Public.h"
#include "Graph.h"void main (){nodePointer graph[MAX_VERTICES];int n=0;short int visited[MAX_VERTICES];memset(visited,FALSE,sizeof(short int) * MAX_VERTICES);FILE *fin,*fout;int v0=0;fin=fopen(&#","r");fout=fopen(&#","w");CreateGraph(fin,graph,n);while(true){fscanf(fin,"%d",&v0);if(v0==-1)break;fprintf (fout, "DBS From V%d:",v0) ;memset(visited,FALSE,sizeof(short int) * MAX_VERTICES);dfs(v0,graph,n,visited,fout);fprintf (fout, "n" ) ;}PrintGraph(graph,6);fclose(fin);fclose(fout);system("pause");}