11-散列4 Hashing - Hard Version (30 分)

发布时间：2020-12-14 04:45:00 所属栏目：大数据来源：网络整理

导读：Given a hash table of size? N,we can define a hash function? (. Suppose that the linear probing is used to solve collisions,we can easily obtain the status of the hash table with a given sequence of input numbers. However,now you are asked

Given a hash table of size?

However,now you are asked to solve the reversed problem: reconstruct the input sequence from the given status of the hash table. Whenever there are multiple choices,the smallest number is always taken.

Input Specification:

Each input file contains one test case. For each test case,the first line contains a positive integer?

Output Specification:

For each test case,print a line that contains the input sequence,with the numbers separated by a space. Notice that there must be no extra space at the end of each line.

Sample Input:

11
33 1 13 12 34 38 27 22 32 -1 21

Sample Output:

1 13 12 21 33 34 38 27 22 32


发现元素的输入有先后关系，比如
1，13必须先12输出。
所以选用拓扑排序

  1 #include <cstdio>
  2 #include <stdlib.h>
  3 #define MAXVERTEXNUM 1001
  4 #define INFINITY 65536
  5 #define ElementType DataAndPos
  6 #define MINDATA -100
  7 
  8 typedef int Vertex;
  9 typedef int Position;
 10 
 11 
 12 struct HashNode {
 13     Vertex i;
 14     int Data;
 15 };
 16 typedef struct HashNode * DataAndPos;
 17 
 18 struct GNode {
 19     int Nv;
 20     int G[MAXVERTEXNUM][MAXVERTEXNUM];
 21     int Data[MAXVERTEXNUM];
 22 };
 23 typedef struct GNode * MGraph;
 24 
 25 struct HNode {
 26     ElementType Data[MAXVERTEXNUM];
 27     int Size;
 28 };
 29 typedef struct HNode * MinHeap;
 30 
 31 
 32 //Function Area
 33 MGraph buildGraph();
 34 MGraph createGraph();
 35 
 36 int TopSort(MGraph G,Vertex TopOrder[]);
 37 MinHeap createMinHeap();
 38 void Insert(MinHeap H,Vertex W,MGraph Graph);
 39 Vertex DeleteMin(MinHeap H);
 40 
 41 void ShowArray(int A[],int N);
 42 
 43 
 44 
 45 int main()
 46 {
 47     int TopOrder[MAXVERTEXNUM];
 48     int RealNum;
 49     
 50     MGraph G = buildGraph();
 51     RealNum = TopSort(G,TopOrder);
 52     ShowArray(TopOrder,RealNum);
 53     
 54 }
 55 
 56 
 57 MGraph buildGraph()
 58 {
 59     MGraph Graph = createGraph();
 60     Vertex P;
 61     
 62     for (P=0; P<Graph->Nv; P++) {
 63         if (Graph->Data[P] > 0) {
 64             if (Graph->Data[P] % Graph->Nv != P) {
 65                 for (Vertex W = Graph->Data[P] % Graph->Nv; W!=P; W = (W + 1) % Graph->Nv) {
 66                     Graph->G[W][P] = 1;
 67                 }
 68             }
 69         }
 70         
 71     }
 72     
 73     
 74     return Graph;
 75     
 76     
 77     
 78     
 79     
 80 }
 81 MGraph createGraph()
 82 {
 83     MGraph Graph;
 84     Graph = (MGraph) malloc( sizeof(struct GNode) );
 85     
 86     scanf("%d",&Graph->Nv);
 87     
 88     for (int i=0; i<Graph->Nv; i++) {
 89         for (int j=0; j<Graph->Nv; j++) {
 90             Graph->G[i][j] = INFINITY;
 91         }
 92     }
 93     
 94     for (int i=0; i<Graph->Nv; i++) {
 95         scanf("%d",&(Graph->Data[i]) );
 96     }
 97     return Graph;
 98 }
 99 
100 int TopSort( MGraph Graph,Vertex TopOrder[] )
101 {
102     int Indegree[MAXVERTEXNUM];
103     int cnt;
104     cnt = 0;
105     
106     Vertex V,W;
107     MinHeap H = createMinHeap();
108     
109     
110     for (W = 0; W<Graph->Nv; W++) {
111         if (Graph->Data[W] > 0) {
112             Indegree[W] = 0;
113         }
114         else Indegree[W] = -1;
115         
116     }
117     for (V = 0; V<Graph->Nv; V++) {
118         for (W=0; W<Graph->Nv; W++) {
119             if (Graph->G[V][W] == 1) {
120                 Indegree[W]++;
121             }
122         }
123     }
124     for (V = 0; V<Graph->Nv; V++) {
125         if (Indegree[V] == 0) {
126             Insert(H,V,Graph);
127         }
128     }
129 
130  
131     cnt = 0;
132     while (H->Size != 0) {
133         V = DeleteMin(H);
134         TopOrder[cnt++] = Graph->Data[V];
135         
136         for (W=0; W<Graph->Nv; W++) {
137             if (Graph->G[V][W] == 1) {
138                 if (--Indegree[W] == 0) {
139                     Insert(H,W,Graph);
140                 }
141             }
142             
143         }
144         
145     }
146     
147     return cnt;
148     
149     
150     
151 }
152 MinHeap createMinHeap()
153 {
154     MinHeap H = new HNode;
155     H->Size = 0;
156     DataAndPos Sentry = new HashNode;
157     Sentry->Data = MINDATA;
158     H->Data[0] = Sentry;
159     
160     return H;
161 }
162 void Insert(MinHeap H,MGraph Graph)
163 {
164     DataAndPos NewNode = new HashNode;
165     NewNode->Data = Graph->Data[W];
166     NewNode->i = W;
167     
168     int i;
169 
170     for (i = ++H->Size; H->Data[i/2]->Data > NewNode->Data ; i/=2) {
171         H->Data[i] = H->Data[i/2];
172     }
173     H->Data[i] = NewNode;
174     
175 }
176 
177 Vertex DeleteMin(MinHeap H)
178 {
179     ElementType first;
180     ElementType last;
181     int Parent,Child;
182     
183     first = H->Data[1];
184     last = H->Data[H->Size--];
185     for (Parent = 1; Parent * 2 <= H->Size; Parent = Child ) {
186         Child = Parent * 2;
187         if (Child < H->Size and H->Data[Child]->Data > H->Data[Child+1]->Data ) {
188             Child++;
189         }
190         if (H->Data[Child]->Data > last->Data) {
191             break;
192         }
193         else H->Data[Parent] = H->Data[Child];
194     }
195     H->Data[Parent] = last;
196     
197     return first->i;
198 }
199 
200 void ShowArray(int A[],int N)
201 {
202     for (int i=0; i<N; i++) {
203         if(i!=0) printf(" ");
204         printf("%d",A[i]);
205     }
206     printf("n");
207 }

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!