c实现内存文件系统

        华为软件训练营的一个高级练习题，比较有意思，值得练习一下！

    题目不是很难，主要是考察一下几个知识点：

    （1）数据结构中树的操作，包括树的定义、树的遍历、节点的插入和删除，这里采用了带双亲的孩子兄弟表示法，实际上可以转换为二叉树，可以采用中序遍历的方式访问树的节点。

    （2）内存管理。树节点中存放有树的信息，在每次插入一个新节点的时候需要malloc内存，最后需要统一free。

    现将代码共享如下，希望能跟感兴趣的同学一起探讨：

    FileManager.h:

#ifndef _FILE_MANAGER_H_
#define _FILE_MANAGER_H_

//定义用于表示文件系统的树结构 
typedef struct CSNode{
	char * name;
	bool isDir;
	struct CSNode * firstChild, * nextSibling, * parent;
}CSNode, * CSTree;

int CreateDir(const char * ParentDirName, const char * DirName);

void DeleteDir(const char * DirName);

int MoveDir(const char * SrcDirName, const char * DestDirName);

int CreateFile(const char * DirName, const char * FileName);

void DeleteFile(const char * FileName);

unsigned int GetFileNum(const char * DirName);

void Clear(void);

#endif

FileManager.cpp:

/******************************************************************************

Copyright (C), 2001-2013, Huawei Tech. Co., Ltd.

******************************************************************************
File Name     :
Version       :
Author        :
Created       : 2013/9
Last Modified :
Description   :
Function List :

History       :
1.Date        : 2013/9
Author      :
Modification: Created file

******************************************************************************/
#include "FileManager.h"
#include <stdio.h>
#include <malloc.h>
#include <stddef.h>
#include <string.h>
#include <stack>

using namespace std;

CSNode *root = NULL;

void FreeCSTree(CSNode *root)
{
	if(root == NULL)
	{
		return;
	}
	FreeCSTree(root->firstChild);
	FreeCSTree(root->nextSibling);
	free(root);
}

CSNode * FindNode(CSNode * start, const char * nodeName, bool isDir)
{
	if (start == NULL || nodeName == NULL)
	{
		return NULL;
	}
	stack<CSNode *> s;
	CSNode * node = NULL;
	s.push(start);
	while (!s.empty())
	{
		CSNode *p;
		while((p = s.top()) && p) s.push(p->firstChild);
		s.pop();
		if (!s.empty())
		{
			p = s.top();
			s.pop();
			if (strcmp(p->name, nodeName) == 0)
			{
				if (isDir == p->isDir)
				{
					node = p;
					return node;
				}
			}
			s.push(p->nextSibling);
		}
	}
	return node;
}

int CreateDir(const char * ParentDirName, const char * DirName)
{
	if (strcmp(ParentDirName,"root") == 0)
	{
		if (root == NULL)
		{
			root = (CSNode *)malloc(sizeof(CSNode));
			memset(root, 0, sizeof(CSNode));
			root->firstChild = NULL;
			root->nextSibling = NULL;
			root->isDir = true;
			root->name = (char *)malloc(strlen(ParentDirName));
			strcpy(root->name,ParentDirName);
			root->parent = NULL;
		}
	}
	CSNode * parentDir = FindNode(root, ParentDirName, true);
	if (parentDir == NULL)
	{
		printf("The parent dir is non-existent!\n");
		return -1;
	}
	CSNode * dir = FindNode(root, DirName, true);
	if(dir != NULL)
	{
		printf("The directory being created already exists!\n");
		return -1;
	}
	CSNode * dirNode = (CSNode *)malloc(sizeof(CSNode));
	memset(dirNode,0,sizeof(CSNode));
	dirNode->name = (char *)malloc(strlen(DirName));
	strcpy(dirNode->name,DirName);
	dirNode->isDir = true;
	dirNode->nextSibling = NULL;
	dirNode->firstChild = NULL;
	dirNode->parent = parentDir;
	CSNode * p = parentDir->firstChild;
	if (p == NULL)
	{
		parentDir->firstChild = dirNode;
	}
	else
	{
		while(p->nextSibling != NULL)
		{
			p = p->nextSibling;
		}
		p->nextSibling = dirNode;
	}	
	//printf("成功创建文件夹:%s\n",DirName);
    return 0;
}

void DeleteDir(const char * DirName)
{
	CSNode * dir = FindNode(root, DirName, true);
	if(dir == NULL)
	{
		printf("The directory being deleted is non-existent!\n");
		return;
	}
	CSNode * parent = dir->parent;
	CSNode * p = parent->firstChild;
	if (strcmp(p->name, DirName) == 0)
	{
		parent->firstChild = dir->nextSibling;
		FreeCSTree(dir->firstChild);
		free(dir);
		return;
	}
	while(strcmp(p->nextSibling->name, DirName) != 0)
	{
		p = p->nextSibling;
	}
	p->nextSibling = p->nextSibling->nextSibling;
	FreeCSTree(dir->firstChild);
	free(dir);
    return;
}

int MoveDir(const char * SrcDirName, const char * DestDirName)
{
	// 目标目录是直接父目录
	if (strcmp(DestDirName, SrcDirName) == 0)
	{
		printf("The destination directory name is the same as the source!\n");
		return -1;
	}
	CSNode * srcDir = FindNode(root, SrcDirName, true);
	CSNode * destDir = FindNode(root, DestDirName, true);
	// 目标目录或者源目录为空
	if(srcDir == NULL || destDir == NULL)
	{
		printf("The directory is non-existed!\n");
		return -1;
	}
	CSNode * r = FindNode(srcDir->firstChild, DestDirName, true);
	// 目标目录是源目录的子目录
	if(r)
	{
		printf("The destination directory is wrong!\n");
		return -1;
	}
	CSNode * parent = srcDir->parent;
	CSNode * p;
	//被移动目录是父目录第一个孩子
	if (strcmp(parent->firstChild->name,SrcDirName) == 0)
	{
		parent->firstChild = srcDir->nextSibling;
	}
	else
	{
		p = parent->firstChild;
		while(strcmp(p->nextSibling->name, SrcDirName) != 0)
		{
			p = p->nextSibling;
		}
		p->nextSibling = p->nextSibling->nextSibling;
	}
	srcDir->nextSibling = NULL;
	srcDir->parent = NULL;
	if (destDir->firstChild == NULL)
	{
		destDir->firstChild = srcDir;
		srcDir->parent = destDir;
		return 0;
	}
	p = destDir->firstChild;
	while(p->nextSibling)
	{
		p = p->nextSibling;
	}
	p->nextSibling = srcDir;
	srcDir->parent = destDir;
    return 0;
}

int CreateFile(const char * DirName, const char * FileName)
{
	if (strcmp(DirName,"root") == 0)
	{
		if (root == NULL)
		{
			root = (CSNode *)malloc(sizeof(CSNode));
			memset(root, 0, sizeof(CSNode));
			root->firstChild = NULL;
			root->nextSibling = NULL;
			root->isDir = true;
			root->name = (char *)malloc(strlen(DirName));
			strcpy(root->name,DirName);
			root->parent = NULL;
		}
	}
	CSNode * parentDir = FindNode(root, DirName, true);
	if (parentDir == NULL)
	{
		printf("The parent dir is non-existent!\n");
		return -1;
	}
	CSNode * file = FindNode(root, FileName, false);
	if(file != NULL)
	{
		printf("The file being created already exists!\n");
		return -1;
	}
	CSNode * dirNode = (CSNode *)malloc(sizeof(CSNode));
	memset(dirNode,0,sizeof(CSNode));
	dirNode->name = (char *)malloc(strlen(FileName));
	strcpy(dirNode->name ,FileName);
	dirNode->isDir = false;
	dirNode->nextSibling = NULL;
	dirNode->firstChild = NULL;
	dirNode->parent = parentDir;
	CSNode * p = parentDir->firstChild;
	if (p == NULL)
	{
		parentDir->firstChild = dirNode;
	}
	else
	{
		while(p->nextSibling != NULL)
		{
			p = p->nextSibling;
		}
		p->nextSibling = dirNode;
	}	
	return 0;
}

void DeleteFile(const char * FileName)
{
	CSNode * dir = FindNode(root, FileName, false);
	if(dir == NULL)
	{
		printf("The file is non-existent!\n");
		return;
	}
	CSNode * parent = dir->parent;
	CSNode * p = parent->firstChild;
	if (strcmp(p->name, FileName) == 0)
	{
		parent->firstChild = dir->nextSibling;
		free(dir);
		return;
	}
	while(strcmp(p->nextSibling->name, FileName) != 0)
	{
		p = p->nextSibling;
	}
	p->nextSibling = p->nextSibling->nextSibling;
	free(dir);
	return;
}

int GetFileNumOfDir(CSNode * dir) 
{
	static int count = 0;
	if (dir == NULL)
	{
		return 0;
	}
	if (dir->isDir == false)
	{
		count++;
	}
	GetFileNumOfDir(dir->firstChild) + GetFileNumOfDir(dir->nextSibling);
	return count;
}

unsigned int GetFileNum(const char * DirName)
{
	CSNode * dir = FindNode(root, DirName, true);
	if(dir == NULL)
	{
		printf("The dir is non-existent!\n");
		return 0;
	}
	int i = 0;
	i = GetFileNumOfDir(dir->firstChild);
    return i;
}

void Clear(void)
{
	FreeCSTree(root->firstChild);
	free(root);
    return;
}

c实现内存文件系统,布布扣,bubuko.com

c实现内存文件系统

原文：http://blog.csdn.net/onejune2013/article/details/20650683