| 2018软件工程 | https://edu.cnblogs.com/campus/zswxy/2018SE |
|---|---|
| 这个作业要求在哪里 | https://edu.cnblogs.com/campus/zswxy/2018SE/homework/11406 |
| 这个作业的目标 | 算法与数据结构 |
| 学号 | 20189666 |
第一题:
题目名称
题目是寻找数组中第K大数 考察算法：排序算法
解题思路
使用C语言,
先手动实现一个排序算法,我手动实现了一个C语言的选择排序.
其次用printf和scanf输入和输出,数组的索引是从0开始,所以要在索引数组的时候要改下.
最后输出索引时,需要将索引+1输出,才是需要的索引.
解题代码
#include <stdio.h>
void swap(int *a,int *b) //交換兩個變數
{
int temp = *a;
*a = *b;
*b = temp;
}
int * SortArrBySelect ( int arr[],int arr_len)
{
int i,i2;
int maxIndex,start;
int end = arr_len -1;
for (i = 0;i< end;i++){
maxIndex = i;
start = maxIndex + 1;
for(i2 = start;i2<arr_len;i2++)
// 遍历未排序的数组
{
int arrBymaxIndex = arr[maxIndex];
int arrByi2 = arr[i2];
// 找到arr[i2:]以后的最小索引
if(arrByi2 >arrBymaxIndex){
maxIndex = i2;
}
}
// 将arr[minIndex]和arr[i]元素交换
swap(&arr[maxIndex], &arr[i]);
// printf("=====================
");
// printf("%d=%d-%d
",arr[minIndex],arr[i],arr[minIndex]);
// arr[minIndex] = arr[i] - arr[minIndex];
// printf("%d=%d-%d
",arr[i],arr[i],arr[minIndex]);
// arr[i] = arr[i] - arr[minIndex];
// printf("%d=%d-%d
",arr[minIndex],arr[minIndex],arr[i]);
// arr[minIndex] = arr[minIndex] + arr[i];
// printf("=====================
");
}
return arr;
}
int Find( int arr[],int arr_len,int value)
{
int i;
int arrByi;
for(i=0;i< arr_len;i++){
arrByi=arr[i];
if(arrByi == value){
return i;
}
}
return -1;
}
void PrintArray(int arr[],int arr_len)
{
printf("
");
int i;
for (i = 0; i < arr_len; i++)
{
printf("%d ", arr[i]);
}
printf("
");
}
int main()
{
int arr_len;
scanf("%d", &arr_len);
int arr[arr_len];
int i;
for (i = 0; i < arr_len; i++)
{
scanf("%d", &arr[i]);
}
int question_arr_len1;
int question_arr_len2=3;
// 输入询问数组
scanf("%d",&question_arr_len1);
int question_arr[question_arr_len1][question_arr_len2];
int i2 = 0;
// 每行3个数，输入question_arr_len行
for (i = 0; i < question_arr_len1; i++)
{
for (i2 = 0; i2 < question_arr_len2; i2++)
{
scanf("%d", &question_arr[i][i2]);
}
}
int answer_arr[question_arr_len1];
int * arrAfterSoft;
for (i = 0; i < question_arr_len1; i++)
{
int start = question_arr[i][0]-1;
int end = question_arr[i][1]-1;
int keyIndex = question_arr[i][2]-1;
int tempArr_len = end-start+1;
int tempArr[tempArr_len];
for (i2 = start; i2 < tempArr_len; i2++)
{
tempArr[i2]=arr[i2];
}
arrAfterSoft=SortArrBySelect(tempArr,tempArr_len);
// printf("第 %d 大的值是: %d",keyIndex,arrAfterSoft[keyIndex-1]);
answer_arr[i]=Find(arr,arr_len,arrAfterSoft[keyIndex])+1;
}
return 0;
}
运行测试结果如下
第二题
题目名称:
题目名称是:二叉树的先、中、后 序遍历与层级遍历 考察算法： dfs + bfs搜索算法
解题思路
根据先序中序后序层次遍历的定义,使用Java语言实现三种方法.
解题代码
import java.util.LinkedList;
public class BinaryTreeDemo {
public static void main(String[] args) {
/*
作业要求：叉树的先、中、后 序遍历与层级遍历
自己实现四个方法，main方法中调用，将结果打印到控制台
*/
/* 二叉树的结构
A
/
T 6
/
D
/
N 5
/ /
B 4 1
9
*/
Node root = into();
// 先序遍历
System.out.println("
"+"前序遍历");
A(root);
// 中序遍历
System.out.println("
"+"中序遍历");
B(root);
// 后续遍历
System.out.println("
"+"后续遍历");
C(root);
// 层级遍历
System.out.println("
"+"层级遍历");
D(root);
}
private static void A(Node node) {
// TODO 先序遍历
System.out.print(node.data + " ");
if(node.l != null){
A(node.l);
}
if(node.r != null){
A(node.r);
}
}
private static void B(Node node) {
// TODO 中序遍历
if(node.l != null){
B(node.l);
}
System.out.print(node.data + " ");
if(node.r != null){
B(node.r);
}
}
private static void C(Node node) {
// TODO 后续遍历
if(node.l != null){
C(node.l);
}
if(node.r != null){
C(node.r);
}
System.out.print(node.data + " ");
}
private static void D(Node node) {
// TODO 层级遍历
if(node == null) {
return ;
}
LinkedList<Node> queue = new LinkedList<>();
Node current = null;
queue.offer(node);
while(!queue.isEmpty()) {
current = queue.poll();//出队队头元素并访问
System.out.print(current.data+ " ");
if(current.l != null) { //如果当前节点的左节点不为空入队
queue.offer(current.l);
}
if(current.r != null) {//如果当前节点的右节点不为空，把右节点入队
queue.offer(current.r);
}
}
}
// 构建一颗树，返回根节点
private static Node into(){
Node root = new Node("A");
Node node1 = new Node("T");
Node node2 = new Node("D");
Node node3 = new Node("N");
Node node4 = new Node("B");
Node node5 = new Node("6");
Node node6 = new Node("5");
Node node7 = new Node("4");
Node node8 = new Node("9");
Node node9 = new Node("1");
root.l = node1;
node1.l = node2;
node2.l = node3;
node2.r = node6;
node3.r = node7;
node7.r = node8;
node6.l = node9;
node3.l = node4;
root.r = node5;
return root;
}
// 节点
static class Node{
// 数据
Object data;
// 左孩子
Node l;
// 右孩子
Node r;
public Node(){}
public Node(Object data) {
this.data = data;
this.l = null;
this.r = null;
}
public Node(Object data, Node l, Node r) {
this.data = data;
this.l = l;
this.r = r;
}
}
}
运行结果:
