プログラミング練習(3)

ツリーの深さと幅を求めます
二叉木の深さと幅を求めて、深さは最も深い層の数で、幅は最も広い層の幅です;

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

typedef struct tagBiNode 
{
	char data;
	struct tagBiNode *left;
	struct tagBiNode *right;
} BiNode;

int getWidth(BiNode* head) 
{
	if (head == NULL)
		return 0;
	queue<BiNode*> q;
	q.push(head);
	int width = 1, current = 1;
	while (!q.empty()) {
		while (current--) {
			if (q.front()->left != NULL)
				q.push(q.front()->left);
			if (q.front()->right != NULL)
				q.push(q.front()->right);
			q.pop();
		}
		current = q.size();
		width = max(width, current);
	}
	return width;
}

int getHeight(BiNode* head) 
{
	if (head == NULL)
		return 0;
	return max(getHeight(head->left), getHeight(head->right)) + 1;
}

int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth,	unsigned int *pulHeight) 
{
	*pulWidth = getWidth(&head);
	*pulHeight = getHeight(&head);
	return 0;
}

メモリファイルシステム
メモリファイルシステム、シミュレーションファイルとフォルダの作成、移動、削除;ルートディレクトリはrootで、デフォルトは存在し、ディレクトリ名とファイル名はグローバルに一意です.

#include <iostream>
#include <string>
#include <map>
using std::map;
using std::string;
class Dir;
class File;

class Dir {
public:
	Dir(const string dirName):dirName(dirName) {
		parent = NULL;
	}
public:
	Dir *parent;
	string dirName;
	map<string, Dir*> subDirs;
	map<string, File*> subFiles;
};

class File {
public:
	File(const string fileName):fileName(fileName) {
		parent = NULL;
	}
public:
	Dir *parent;
	string fileName;
};

Dir *root = new Dir("root");
map<string, Dir*> dirs;
map<string, File*> files;

Dir* findDir(const string& dirName) {
	if (dirName == "root")
		return root;
	map<string, Dir*>::iterator it = dirs.find(dirName);
	if (it == dirs.end())
		return NULL;
	return it->second;
}

File* findFile(const string& fileName) {
	map<string, File*>::iterator it = files.find(fileName);
	if (it == files.end())
		return NULL;
	return it->second;
}

Dir* removeFile(const string fileName) {
	File *pFile = findFile(fileName);
	if (pFile == NULL)
		return NULL;
	Dir *parent = pFile->parent;
	files.erase(fileName);
	return parent;
}

Dir* removeDir(const string dirName) {
	Dir *pDir = findDir(dirName);
	if (pDir == NULL)
		return NULL;
	if (!pDir->subDirs.empty()) {
		map<string, Dir*>::iterator iterDir = pDir->subDirs.begin();
		for (; iterDir != pDir->subDirs.end(); ++iterDir) {
			removeDir(iterDir->first);
		}
	}
	map<string, File*>::iterator iterFile = pDir->subFiles.begin();
	for (; iterFile != pDir->subFiles.end(); ++iterFile) {
		removeFile(iterFile->first);
	}
	Dir *parent = pDir->parent;
	delete pDir;
	dirs.erase(dirName);
	return parent;
}

int CreateDir(const char * ParentDirName, const char * DirName) {
	string parentDirName = ParentDirName;
	Dir *parentDir = findDir(parentDirName);
	if (parentDir == NULL)
		return -1;
	string dirName = DirName;
	if (findDir(dirName) != NULL)
		return -1;
	Dir *newDir = new Dir(dirName);
	parentDir->subDirs[dirName] = newDir;
	newDir->parent = parentDir;
	dirs[dirName] = newDir;
	return 0;
}

void DeleteDir(const char * DirName) {
	string dirName = DirName;
	Dir *parent = removeDir(dirName);
	if (parent != NULL) {
		parent->subDirs.erase(dirName);
	}
	return;
}

int MoveDir(const char * SrcDirName, const char * DestDirName) {
	string src = SrcDirName;
	string des = DestDirName;
	Dir *srcDir = findDir(src);
	Dir *desDir = findDir(des);
	if (srcDir == NULL || desDir == NULL) {
		return -1;
	}
	if (srcDir->parent == desDir) {
		return -1;
	}
	Dir *desDirCheck = desDir;
	while (desDirCheck != root) {
		if (desDirCheck == srcDir) {
			return -1;
		}
		desDirCheck = desDirCheck->parent;
	}
	Dir *srcParent = srcDir->parent;
	srcParent->subDirs.erase(srcDir->dirName);
	srcDir->parent = desDir;
	desDir->subDirs[srcDir->dirName] = srcDir;
	return 0;
}

int CreateFile(const char * DirName, const char * FileName) {
	string fileName = FileName;
	File *pFile = findFile(fileName);
	if (pFile != NULL) {
		return -1;
	}
	string dirName = DirName;
	Dir *pDir = findDir(dirName);
	if (pDir == NULL) {
		return -1;
	}
	pFile = new File(fileName);
	files[fileName] = pFile;
	pFile->parent = pDir;
	pDir->subFiles[fileName] = pFile;
	return 0;
}

void DeleteFile(const char * FileName) {
	string fileName = FileName;
	Dir *parent = removeFile(fileName);
	if (parent != NULL) {
		parent->subFiles.erase(fileName);
	}
	return;
}

unsigned int GetFileNum(const char * DirName) {
	string dirName = DirName;
	Dir *pDir = findDir(dirName);
	if (pDir == NULL) {
		return 0;
	}
	unsigned int fileNum = pDir->subFiles.size();
	map<string, Dir*>::iterator it = pDir->subDirs.begin();
	for (; it != pDir->subDirs.end(); ++it) {
		fileNum += GetFileNum(it->first.c_str());
	}
	return fileNum;
}

void Clear(void) {
	dirs.clear();
	files.clear();
	root->subDirs.clear();
	root->subFiles.clear();
	return;
}

int main() {
	CreateFile("root", "hi1");
	CreateFile("root", "hi2");
	CreateFile("root", "hi3");
	CreateDir("root","a1");
	CreateFile("a1","h4");
	CreateFile("a1","h5");
	CreateFile("a1","h6");
	CreateDir("a1","b1");
	CreateFile("b1","h7");
	std::cout << GetFileNum("root") << "
"; // 7
	std::cout << GetFileNum("a1") << "
";  // 4
	CreateDir("root", "a2");
	CreateFile("a2","hi8");
	MoveDir("a2","b1");
	std::cout << GetFileNum("a1") << "
";  // 5
	removeDir("a1");
	std::cout << GetFileNum("root") << "
";     //3
	DeleteFile("hi3");
	std::cout << GetFileNum("root") << "
";     //2

}

楽しい明ちゃん(01リュック)
価格が総金額を超えない場合、選択した物品の価格に価値を乗じた総和が最大となるように求める.パラメータの2次元配列の最初の行は、合計金額と合計品目の種類を表し、以下は各品目の価格と価値です.

#include <iostream>
#include <stdlib.h>
#include <algorithm>
using std::max;

struct Goods {
	int price;
	int value;
};

void GetResult(int *p, int& Get_Result) {
	int money = p[0], num = p[1];
	struct Goods goods[25]; //       < 30000
	int i, j;
	for (i = 0; i < num; ++i) {
		goods[i].price = p[(i + 1) * 2];
		goods[i].value = p[(i + 1) * 2 + 1];
	}
	int table[30000]; //     < 30000
	memset(table, 0, 30000);
	for (i = 0; i < num; ++i) {
		for (j = money; j >= goods[i].price; --j) {
			table[j] = max(table[j], table[j - goods[i].price] + goods[i].price * goods[i].value);
		}
	}
	Get_Result = table[money];
}

int main() {
	int a[6][2] = { { 1000, 5 }, { 800, 2 }, { 400, 5 }, { 300, 5 }, { 400, 3 }, { 200, 2 } };
	int *p = &a[0][0];
	int GetNumber = 0;
	GetResult(p, GetNumber);
	std::cout << GetNumber; // 3900
	return 0;
}

整数ソート
「1,2,3,15,7,6」のようなカンマ間隔の文字列を入力します.ソートされた数値、スペース間隔を出力します.連続する数値は先頭のみ(1,2,3,4,5は1,5のみ)です.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	string str;
	getline(cin, str);
	vector<int> ve;
	unsigned int i, num = 0;
	for (i = 0; i < str.length(); ++i) {
		if (str[i] != ',') {
			num = num * 10 + str[i] - '0';
		} else {
			ve.push_back(num);
			num = 0;
		}
	}
	ve.push_back(num);
	sort(ve.begin(), ve.end());
	cout << ve[0] << " ";
	for (i = 1; i < ve.size() - 1; ++i) {
		if (ve[i] == ve[i - 1] + 1 && ve[i] == ve[i + 1] - 1)
			continue;
		cout << ve[i] << " ";
	}
	cout << ve[ve.size() - 1];
	return 0;
}

鉄道スタック問題
列車は番号1から9の自然数順にスタックに入り、指定されたスタックの順番にスタックを出ることができるかどうかを判断する.

#include <iostream>
#include <stack>
using namespace std;

int JudgeTrainSequence(int maxNum, char *pOutSeq) {
	stack<int> theStack;
	theStack.push(1);
	char *p = pOutSeq;
	int k = 2;
	while (*p) {
		if (!theStack.empty() && theStack.top() == *p - '0') {
			theStack.pop();
			++p;
		} else {
			if (k == maxNum + 1) {
				return 0;
			}
			theStack.push(k++);
		}
	}
	if (theStack.empty()) {
		return 1;
	} else {
		return 0;
	}
}

int main() {
	int maxNum = 5;
	char *outSeq = "12534";
	cout << JudgeTrainSequence(maxNum, outSeq); // 0
	char *outSeq2 = "34215";
	cout << JudgeTrainSequence(maxNum, outSeq2); // 1
}

RTOSck-ソフトブレークスケジューラ
優先度割込みスケジューラをシミュレートし、優先度は0-31の間の数字で表され、数字が小さい優先度が高く、高い優先度は低い優先度を優先することができ、同じ優先度はFIFOでスケジューリングされる.

#include <iostream>
#include <queue>
#include <map>
using namespace std;

class Task {
public:
	Task() :swiId(0), prio(0), proc(NULL) {}
	Task(unsigned int swiId, unsigned int prio, void (*proc)(void)) :
			swiId(swiId), prio(prio), proc(proc) {}
	bool operator <(const Task& a) const {
		return prio > a.prio;
	}
public:
	unsigned int swiId;
	unsigned int prio;
	void (*proc)(void);
};

static priority_queue<Task> g_pri_queue;
static map<unsigned int, Task> g_tasks;
static int g_runID;

int SwiCreate(unsigned int swiId, unsigned int prio, void (*proc)(void)) {
	if (prio > 31 || proc == NULL || g_tasks.count(swiId))
		return -1;
	g_tasks[swiId] = Task(swiId, prio, proc);
	return 0;
}

int SwiActivate(unsigned int swiId) {
	if (!g_tasks.count(swiId))
		return -1;
	g_pri_queue.push(g_tasks[swiId]);
	while (!g_pri_queue.empty()) {
		Task t = g_pri_queue.top();
		if (g_runID != (int) t.swiId) {
			int preRunID = g_runID;
			g_runID = t.swiId;
			t.proc();
			g_runID = preRunID;
			g_pri_queue.pop();
		} else {
			break;
		}
	}
	return 0;
}

void Clear(void) {
	g_runID = -1;
	g_tasks.clear();
	while (!g_pri_queue.empty()) {
		g_pri_queue.pop();
	}

}

//---for test---
static unsigned int * schedTrace;
static unsigned int schedTraceCnt;
static unsigned int schedTraceSize;

void SchedTraceInit(unsigned int * p, unsigned int size) {
	schedTrace = p;
	schedTraceCnt = 0;
	schedTraceSize = size;
}

void SchedTraceRecord(unsigned int pid) {
	if (schedTraceCnt < schedTraceSize)
		schedTrace[schedTraceCnt++] = pid;
}

static void TestCase01_proc1() {
	SchedTraceRecord(1);
	SwiActivate(2);
	SchedTraceRecord(1);
}

static void TestCase01_proc2() {
	SchedTraceRecord(2);
	SwiActivate(3);
	SchedTraceRecord(2);
}
static void TestCase01_proc3() {
	SchedTraceRecord(3);
}

int main() {
	int ret;
	unsigned int trace[10];
	SchedTraceInit(trace, 10);
	Clear();
	ret = SwiCreate(1, 5, TestCase01_proc1);
	cout << ret; //0
	ret = SwiCreate(2, 3, TestCase01_proc2);
	cout << ret; //0
	ret = SwiCreate(3, 4, TestCase01_proc3);
	cout << ret; //0
	ret = SwiActivate(1);
	cout << ret; //0
	cout << schedTraceCnt << "
"; //5
	for (int i = 0; i < 5; ++i) {
		cout << trace[i] << " "; // 1, 2, 2, 3, 1
	}
	return 0;
}

Arrange an Array to Form a Smallest Digit
入力した配列を最小数に並べ、文字列として出力します.

#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <iostream>

int num(int a) {
	int num = 1;
	while (a != 0) {
		num *= 10;
		a /= 10;
	}
	return num;
}

bool comp(const int& a, const int& b) {
	return a * num(b) + b < b * num(a) + a;
}

int smallestDigit(int a[], int nCount, char * strRst) {
	std::sort(a, a + nCount, comp);
	char buffer[32];
	for (int i = 0; i < nCount; ++i) {
		sprintf(buffer, "%d", a[i]);
		strcat(strRst, buffer);
	}
	return 1;
}

int main() {
	int a[] = { 32, 321 };
	char szRst[10] = { 0 };
	smallestDigit(a, 2, szRst);
	std::cout << szRst;
}