Recursive Linked List

GreenDay2001 0 Tallied Votes 291 Views Share

This would let you store different things of same type into one data structure, here its a list. A good and popular example would be file and folder hierarchical structure in your computer. Perhaps this is what this code demonstrates.

The code has two classes File and Directory (derived from File). Directory uses a std::list to store pointer to Files. Since Directory is inherited from File the list could also store Directories. That's what the algo is. A virtual function named display() is called recursively to display them.

// 18/11/2006

/**
  * @author vishesh
  *
  * Recursive List Example
  * Demonstrate files and folder hierarchical structure
  **/


#include <iostream>
#include <string>
#include <list>

/** whiteSpace(unsinged int no)
  *
  * @param:
  *		unsigned int no:  factor which is multiplied by 2 give spaces
  * @return:
  *		char* which is basically consists of blank spaces
  *
  * This function is used in this program to leave some space
  * according to the depth of file while displaying output
  *
  */

inline char* whiteSpace(unsigned int no) {
	char *space = new char[no*2+2];
	for(unsigned int i=0; i<no*2+1; i++)
	{
		space[i] = ' ';
		space[i+1]='\0';
	}
	return space;
}

/** File class
  *
  * @param:
  *		none
  *		std::string name:  name of the file
  *
  * This class stores nothing but stores file names and
  * has a function to display that beautifully on monitor
  */
class File
{
protected:
	std::string name;				// name of file
public:
	File(){}						// just to satisfy compiler and inherited class
	File(std::string _name):name(_name){}	// store name of file
	~File(){}

	virtual void display(unsigned int depth) {

		// get no. of spaces according to depth
		char *spaces = whiteSpace(depth);	

		std::cout << "\n" << spaces << "File("	//display it
				  << depth <<"): " << name;
		delete[] spaces;			// free the memory taken by spaces
	}
};

/** Directory class, ingerited from File class
  *
  * @param:
  *		std::string name:  name of the dir
  *
  * This class nothing but stores files and
  * directories in a std::list class.
  */
class Directory:public File
{
protected:
	std::string  name;				// name of dir
	std::list<File*>	 files;		// so that it stores both files and dirs
public:
	Directory(std::string _name):name(_name) {}

	// destructor
	// delete everything, every file, every directory
	// and empty the list
	~Directory() {
		while(!files.empty())
		{
			delete files.back();
			files.pop_back();
		}
	}

	// display that
	void display(unsigned int depth=0) 
	{
		char *spaces = whiteSpace(depth);
		std::cout << "\n\n" << spaces << "Directory(" 
				  << depth  << "): " << name;

		for (std::list<File*>::iterator iter = files.begin(); 
			iter != files.end(); iter++) {
			// recursive call
			// depth to know how many spaces to leave
			(*iter)->display(depth+1);
		}

		std::cout << "\n";

		delete[] spaces;	// delete the memory taken by spaces
	}

	// add new item into list
	// takes pointer, so could take directory asd well as file
	void addFile(File *fle) {
		files.push_back(fle);
	}	
};

int main()
{
	Directory *root = new Directory("C");
	
	Directory *subDir1 = new Directory("Program Files");
	root->addFile(subDir1);

	Directory *subDir1D1 = new Directory("Winamp");
	subDir1D1->addFile(new File("winamp.exe"));
	subDir1D1->addFile(new File("winamptrat.exe"));
	subDir1D1->addFile(new File("somefile.dll"));
	subDir1->addFile(subDir1D1);

	Directory *subDir2 = new Directory("Develop");

	Directory *subDir2D1 = new Directory("C++");
	subDir2D1->addFile(new File("MinGW"));
	subDir2D1->addFile(new File("Visual C++"));
	subDir2D1->addFile(new File("Borland C++"));
	subDir2D1->addFile(new File("CodeBlocks"));
	subDir2->addFile(subDir2D1);

	Directory *subDir2D2 = new Directory("C#");
	subDir2D2->addFile(new File("Visual C#"));
	subDir2D2->addFile(new File("Borland C#"));
	subDir2->addFile(subDir2D2);

	Directory *subDir2D3 = new Directory("Web");
	subDir2D3->addFile(new File("HTML-Kit"));
	subDir2D3->addFile(new File("Dreamweaver"));
	subDir2D3->addFile(new File("Flash"));
	subDir2->addFile(subDir2D3);

	Directory *subDir2D3D1 = new Directory("Multimedia And Graphics");
	subDir2D3D1->addFile(new File("Flash"));
	subDir2D3D1->addFile(new File("Director"));
	subDir2D3D1->addFile(new File("Fireworks"));
	subDir2D3D1->addFile(new File("SVG"));
	subDir2D3->addFile(subDir2D3D1);

	root->addFile(subDir2);

	root->display();

	delete root;

	std::cin.get();
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.