1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| // HeapSortSPO.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <conio.h>
#include <Windows.h>
//Программа 5.2
#define KEY_SIZE 8
typedef struct _TreeNode {/* Описание структуры узла. */
struct _TreeNode *Left, *Right;
TCHAR Key[KEY_SIZE];
LPTSTR pData;
} TREENODE, *LPTNODE, **LPPTNODE;
#define NODE_SIZE sizeof(TREENODE)
#define NODE_HEAP_ISIZE 0x8000
#define DATA_HEAP_ISIZE 0x8000
#define MAX_DATA_LEN 0x1000
#define TKEY_SIZE KEY_SIZE * sizeof(TCHAR)
LPTNODE FillTree(HANDLE, HANDLE, HANDLE);
BOOL Scan(LPTNODE);
int KeyCompare(LPCTSTR, LPCTSTR), iFile;
BOOL InsertTree(LPPTNODE, LPTNODE);
int _tmain(int argc, LPTSTR argv[]) {
HANDLE hIn, hNode = NULL, hData = NULL;
LPTNODE pRoot;
CHAR ErrorMessage[256];
int iFirstFile = Options(argc, argv, _T("n"), &NoPrint, NULL);
/* Обработать все файлы, указанные в командной строке. */
for (iFile = iFirstFile; iFile < argc; iFile++) __try {
/* Открыть входной файл. */
hIn = CreateFile(argv[iFile], GENERIC_READ, 0, NULL, OPEN_EXISTING, 0, NULL);
if (hIn == INVALID_HANDLE_VALUE) RaiseException(0, 0, 0, NULL);
__try { /* Распределить две кучи. */
hNode = HeapCreate(HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE, NODE_HEAP_ISIZE, 0);
hData = HeapCreate(HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE, DATA_HEAP_ISIZE, 0);
/* Обработать входной файл, создавая дерево. */
pRoot = FillTree(hIn, hNode, hData);
/* Отобразить дерево в порядке следования ключей. */
_tprintf(_T("Сортируемый файл: %s\n"), argv[iFile]);
Scan(pRoot);
} _finally { /* Кучи и дескрипторы файлов всегда закрываются.
/* Уничтожить обе кучи и структуры данных. */
if (hNode != NULL) HeapDestroy(hNode);
if (hNode != NULL) HeapDestroy(hData);
hNode = NULL;
hData = NULL;
if (hIn != INVALID_HANDLE_VALUE) CloseHandle(hIn);
}
} /* Конец основного цикла обработки файлов и try-блока. */
__except (EXCEPTION_EXECUTE_HANDLER) {
_stprintf(ErrorMessage, _T("\n%s %s"), _T("sortBT, ошибка при обработке файла:"), argv[iFile]);
ReportError(ErrorMessage, 0, TRUE);
}
return 0;
}
LPTNODE FillTree(HANDLE hIn, HANDLE hNode, HANDLE hData)
/* Заполнение дерева записями из входного файла. Используется обработчик исключений вызывающей программы. */
{
LPTNODE pRoot = NULL, pNode;
DWORD nRead, i;
BOOL AtCR;
TCHAR DataHold[MAX_DATA_LEN];
LPTSTR pString;
while (TRUE) {
/* Разместить и инициализировать новый узел дерева. */
pNode = HeapAlloc(hNode, HEAP_ZERO_MEMORY, NODE_SIZE);
/* Считать ключ из следующей записи файла. */
if (!ReadFile(hIn, pNode->Key, TKEY_SIZE, &nRead, NULL) || nRead != TKEY_SIZE) return pRoot;
AtCR = FALSE; /* Считать данные до конца строки. */
for (i = 0; i < MAX_DATA_LEN; i++) {
ReadFile(hIn, &DataHold[i], TSIZE, &nRead, NULL);
if (AtCR && DataHold[i] == LF) break; //Это вроде '\n'
AtCR = (DataHold[i] == CR); // а это '\r'
}
DataHold[i–1] = '\0';
/* Объединить ключ и данные — вставить в дерево. */
pString = HeapAlloc(hData, HEAP_ZERO_MEMORY, (SIZE_T)(KEY_SIZE + _tcslen(DataHold) + 1) * TSIZE);
memcpy(pString, pNode->Key, TKEY_SIZE);
pString[KEY_SIZE] = '\0';
_tcscat(pString, DataHold);
pNode->pData = pString;
InsertTree(&pRoot, pNode);
} /* Конец цикла while (TRUE). */
return NULL; /* Ошибка */
}
BOOL InsertTree(LPPTNODE ppRoot, LPTNODE pNode)
/* Добавить в дерево одиночный узел, содержащий данные. */
{
if (*ppRoot == NULL) {
*ppRoot = pNode;
return TRUE;
}
/* Обратите внимание на рекурсивные вызовы InsertTree. */
if (KeyCompare(pNode->Key, (*ppRoot)->Key) < 0) InsertTree(&((*ppRoot)->Left), pNode);
else InsertTree(&((*ppRoot)->Right), pNode);
}
static int KeyCompare(LPCTSTR pKey1, LPCTSTR pKey2)
/* Сравнить две записи, состоящие из обобщенных символов. */
{
return _tcsncmp(pKey1, pKey2, KEY_SIZE);
}
static BOOL Scan(LPTNODE pNode)
/* Рекурсивный просмотр и отображение содержимого бинарного дерева. */
{
if (pNode == NULL) return TRUE;
Scan(pNode->Left);
_tprintf(_T("%s\n"), pNode->pData);
Scan(pNode->Right);
return TRUE;
} |
(
