程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> PAT 05-樹6 Path in a Heap,pat05-

PAT 05-樹6 Path in a Heap,pat05-

編輯:關於C語言

PAT 05-樹6 Path in a Heap,pat05-


這次的作業完全是依葫蘆畫瓢,參照雲課堂《數據結構》(http://mooc.study.163.com/learn/ZJU-1000033001#/learn/content)中何欽銘老師課件中有關建堆及插入的內容,再加上自己寫的一個矬函數(竟然傳了4個參數),OK了!題設要求及代碼實現如下

  1 /*
  2     Name: 
  3     Copyright: 
  4     Author: 
  5     Date: 05/04/15 19:34
  6     Description: 
  7 Insert a sequence of given numbers into an initially empty min-heap H. Then for any given index i, you are supposed to print the path from H[i] to the root.
  8 
  9 Input Specification:
 10 
 11 Each input file contains one test case. For each case, the first line gives two positive integers N and M (<=1000) which are the size of the input sequence, and the number of indices to be checked, respectively. Given in the next line are the N integers in [-10000, 10000] which are supposed to be inserted into an initially empty min-heap. Finally in the last line, M indices are given.
 12 
 13 Output Specification:
 14 
 15 For each index i in the input, print in one line the numbers visited along the path from H[i] to the root of the heap. The numbers are separated by a space, and there must be no extra space at the end of the line.
 16 
 17 Sample Input:
 18 5 3
 19 46 23 26 24 10
 20 5 4 3
 21 Sample Output:
 22 24 23 10
 23 46 23 10
 24 26 10
 25 */
 26 
 27 #include <stdio.h>
 28 #include <stdlib.h>
 29 
 30 #define MinData -10001
 31 
 32 typedef struct HeapStruct
 33 {
 34     int * Elements;
 35     int Size;
 36     int Capacity;
 37 } * MinHeap;
 38 
 39 MinHeap Create(int MaxSize);
 40 void Insert(MinHeap H, int item);
 41 void Print(MinHeap H, int * a, int N, int M);
 42 
 43 int main()
 44 {
 45 //    freopen("in.txt", "r", stdin); // for test
 46     int N, M, i, item;
 47     MinHeap H;
 48     
 49     scanf("%d%d", &N, &M);
 50     
 51     H = Create(N);
 52     for(i = 0; i < N; i++)
 53     {
 54         scanf("%d", &item);
 55         Insert(H, item);
 56     }
 57     
 58     int a[M];
 59     
 60     for(i = 0; i < M; i++)
 61         scanf("%d", &a[i]);
 62         
 63     Print(H, a, N, M);
 64 //    fclose(stdin); // for test
 65     return 0;
 66 }
 67 
 68 MinHeap Create(int MaxSize)
 69 {
 70     MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct));
 71     H->Elements = (int *)malloc((MaxSize + 1) * sizeof(int));
 72     H->Size = 0;
 73     H->Capacity = MaxSize;
 74     H->Elements[0] = MinData;
 75     
 76     return H;
 77 }
 78 
 79 void Insert(MinHeap H, int item)
 80 {
 81     int i;
 82     
 83     i = ++H->Size;
 84     for(; H->Elements[i / 2] > item; i /= 2)
 85         H->Elements[i] = H->Elements[i / 2];
 86     H->Elements[i] = item;
 87 }
 88 
 89 void Print(MinHeap H, int * a, int N, int M)
 90 {
 91     int i;
 92     
 93     for(i = 0; i < M; i++)
 94     {
 95         if(a[i] <= N)
 96         {
 97             while(a[i])
 98             {
 99                 printf("%d", H->Elements[a[i]]);
100                 if(a[i] > 1)
101                     printf(" ");
102                 else
103                     printf("\n");
104                 a[i] /= 2;
105             }
106         }
107     }
108 }

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved