How to become an author
Search
Write a publication
Pull to refresh

Список списков на C/С++

Lumber room
Invite pending
Задача: Создание программы реализующая список списков.

Требование: можно использовать любой язык для структурного программирования, кроме ассемблера,
в котором есть явное распределение памяти, явное освобождение памяти, не должно быть
сборщиков мусора. Поэтому был выбран язык С/С++.





Основной список выполнен в виде односвязного списка, подсписок — двунаправленный.
Так же у каждого подсписка имеется дополнительный список как стек.
Вставка:
  1. Вставка элемента в основной список производиться всегда после последнего.
  2. Вставка элемента в подсписок может производиться как до так и после заданного элемента.

Удаление:
  1. При удалние элемента из основного списка, удаляется его подсписок и дополнительный список.
  2. При удалении элемента из подсписка можно этот элемент перенести в дополнительный список или освободить память.

Код программы:
Header главного списка
#ifndef _wList_H
#define _wList_H
#include "wList.h"

namespace mainList1
{
	enum result_Add {NOT_FOUND, ADD_TRUE, ADD_FALSE};
	
	typedef struct mainList 
	{
		int inf;
		mainList *ptrNext;
		wList1::wList *ptrSub;
		wList1::wList *	ptrAuxSub;
	}_mainList;

	extern mainList *ptrHead;
	static mainList *ptrAux;
	void initMainList ();
	mainList *afterSearchInMainList (const int &id);
	mainList *beforeSearchInMainList (const int &id);
	result_Add pushAfterInMainList (const int &id);
	result_Add pushBeforeInMainList(const int &id);
	void showMainList ();	
	void popInMainList(const int &id);
	void menuMainList();
}
#endif


Header подсписка
#ifndef _mainList_H
#define _mainList_H
namespace wList1
{
	typedef struct wList 
	{
		int inf;
		wList *ptrLeft;
		wList *ptrRight;		
	}_wList;
	static wList *ptrHead;
	static wList *ptrAux;
	void initializeHead(wList1:: wList *);
	void initializeAux (wList1:: wList *);
	wList *getPtrHead();
	wList *getPtrAux();
	wList *rightSearch(const int &id);
	wList *reverseSearch (const int &id);
	void pushAfter(const int &id);
	void pushBefore(const int &id);
	void showRight ();
	void showReverse ();
	void showAux();
	void popBranch();
	void popAux();
	void pop(const int &id);
	void menu (wList1::wList *, wList1:: wList *);
}
#endif


Cpp файл гланвого списка
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include "mainList.h"
using namespace mainList1;

mainList1::mainList *mainList1::ptrHead = (mainList*)malloc(sizeof(mainList));	

void mainList1::initMainList ()
{
	ptrHead->inf = 9999999;
	ptrHead->ptrNext = 0;
	ptrHead->ptrSub = 0;
	ptrHead->ptrAuxSub = 0;
}

mainList1::mainList *mainList1::afterSearchInMainList (const int &id)
{
	mainList *ptrCurrent = ptrHead->ptrNext;
	if (!ptrCurrent)
	{
		return ptrHead;
	}
	while (ptrCurrent)
	{
		if (ptrCurrent-> inf == id )
		{
			return ptrCurrent;
		}
		ptrCurrent = ptrCurrent->ptrNext;
	}
	return 0;
}
mainList1::mainList *mainList1::beforeSearchInMainList (const int &id)
{
	mainList *ptrPrev = ptrHead;
	mainList *ptrCurrent = ptrHead->ptrNext;
	if (!ptrCurrent)
	{
		return ptrHead;
	}
	while (ptrCurrent)
	{
		if (ptrCurrent->inf == id)
		{
			return ptrPrev;
		}
		ptrPrev = ptrCurrent;
		ptrCurrent = ptrCurrent->ptrNext;
	}
	return 0;
}
result_Add mainList1::pushAfterInMainList (const int &id)
{	
	int key;
	int number;
	mainList *ptrTemp;
	mainList *ptrCurrent;

	ptrCurrent = afterSearchInMainList(id);
	if (!ptrCurrent)			
		return NOT_FOUND;	
	else 
	{
		loop2:
		printf("\n1-Create new element\n2-Enter element from auxiliary list");
		scanf("%d", &key);
		switch(key)
		{
			case 1:
				ptrTemp = (mainList*)malloc(sizeof(mainList));
				if(ptrTemp)
				{
					printf("\nEnter element\n");
					scanf("%d", &number);
					ptrTemp->inf = number;
					ptrTemp->ptrNext = ptrCurrent->ptrNext;	
					ptrTemp->ptrSub = 0;
					ptrTemp->ptrAuxSub = 0;
					ptrCurrent->ptrNext = ptrTemp;	
					return ADD_TRUE;
				}
				else if (!ptrTemp)				
					return ADD_FALSE;			
			case 2:
				if (ptrAux)
				{			
					mainList *ptrTemp;
					ptrTemp = ptrAux->ptrNext;			
					ptrAux->ptrNext = ptrCurrent->ptrNext;
					ptrAux->ptrSub = 0;
					ptrAux->ptrAuxSub = 0;
					ptrCurrent->ptrNext = ptrAux;			
					ptrAux = ptrTemp;
					return ADD_TRUE;
				}
				else if (!ptrAux)
				{
					printf("\nauxiliary list empty\n");
					goto loop2;
				}
			default :		
				goto loop2;
		}
	}
}
result_Add mainList1::pushBeforeInMainList(const int &id)
{
	int key;
	int number;
	mainList *ptrTemp;
	mainList*ptrPrev;
	mainList *ptrCurrent = ptrHead;
	

	ptrPrev = mainList1::beforeSearchInMainList(id);
	if (!ptrPrev)		
		return NOT_FOUND;

	ptrCurrent = ptrPrev->ptrNext;
	loop2:
	printf("\n1-Create new element\n2-Enter element from auxiliary list");
	scanf("%d", &key);
	switch(key)
	{
	case 1:
		ptrTemp = (mainList *)malloc(sizeof(mainList));
		if(!ptrTemp)					
			return ADD_FALSE;
		if (ptrTemp)
		{
			printf("\nEnter element\n");
			scanf("%d", &number);
			ptrTemp->inf = number; 
			ptrTemp->ptrSub = 0;
			ptrTemp->ptrAuxSub = 0;
			ptrTemp->ptrNext = ptrCurrent;
			ptrPrev->ptrNext = ptrTemp;
			return ADD_TRUE;
		}		
	case 2:
		if (ptrAux)
		{
			ptrPrev->ptrNext = ptrAux;
			ptrTemp = ptrAux->ptrNext;
			ptrAux->ptrNext = ptrCurrent;	
			ptrAux->ptrSub = 0;
			ptrAux->ptrAuxSub = 0;
			ptrAux = ptrTemp;
			return ADD_TRUE;
		}
		else if (!ptrAux)
		{
			printf("\nAux list empty\n");
			goto loop2;
		}
		
	default : goto loop2;
		break;
	}


}
void mainList1::showMainList ()
{
	mainList *ptrCurrent = ptrHead->ptrNext;

	if(!ptrCurrent)
	{
		printf("\nList empty\n");
		return;
	}
	while(ptrCurrent)
	{
		printf("\n%d", ptrCurrent->inf);
		ptrCurrent = ptrCurrent->ptrNext;
	}
}
void mainList1::popInMainList(const int &id)
{
	int key;
	int number;

	mainList *ptrTemp;
	mainList *ptrCurrent;
	mainList *ptrPrev;


	ptrPrev = beforeSearchInMainList(id);
	if(!ptrPrev)
	{
		printf("\nElement not found\n");
		return;
	}
	if (!ptrPrev->ptrNext)
	{
		printf("\nMain list empty\n");
		return;
	}

	ptrCurrent = ptrPrev->ptrNext;

	if (!ptrCurrent->ptrSub)
	{
		ptrPrev->ptrNext = ptrCurrent->ptrNext;
		free(ptrCurrent);
		return;
	}
	else
	{
		wList1::initializeHead(ptrCurrent->ptrSub);
		wList1::initializeAux(ptrCurrent->ptrAuxSub);
		wList1::popBranch();
		wList1::popAux();
		ptrPrev->ptrNext = ptrCurrent->ptrNext;
		free(ptrCurrent);
	}
}
void mainList1::menuMainList()
{
	printf ("\n-------------------------------------------\nMENU MAIN LIST \n");
	int key;
	int number;	
	printf("\n1-push after element\n2-push before element\n3-show base list(easy flow direction)\n5-popInMainList\n8-exit\n");
	scanf("%d", &key);
	while (1)
	{
	switch(key)
	{
		case 1:
			printf("\nEnter element\n");
			scanf("%d", &number);
			if(mainList1::pushAfterInMainList(number) == ADD_TRUE)
				return;
			if (mainList1::pushAfterInMainList(number) == ADD_FALSE)
			{
				printf ("\nERROR\n");
				break;
			}
			if (mainList1::pushAfterInMainList(number) == NOT_FOUND)
			{
				printf("\nElement not found\n");
				break;
			}
		case 2:
			printf("\nEnter element\n");
			scanf("%d", &number);
			if(mainList1::pushBeforeInMainList(number) == ADD_TRUE)
				return;
			if (mainList1::pushBeforeInMainList(number) == ADD_FALSE)
			{
				printf ("\nERROR\n");
				break;
			}
			if (mainList1::pushBeforeInMainList(number) == NOT_FOUND)
			{
				printf("\nElement not found\n");
				break;
			}
		case 3:
			showMainList();
			break;
		case 5:
			printf("\nEnter element for find\n");
			scanf("%d", &number);
			mainList1::popInMainList(number);
			break;

		case 8:
			printf("\nBye\n");
			return;
		default : 
			break;			
	}
	printf("\n1-push after element\n2-push before element\n3-show base list(easy flow direction)\n5-popInMainList\n8-exit\n");
	scanf("%d", &key);
	}
}


Cpp подсписка
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include "wList.h"
#include "mainList.h"
using namespace wList1;

void wList1::initializeHead ( wList1::wList *ptrCurrentMain)
{
	ptrHead = ptrCurrentMain;
}
void wList1::initializeAux (wList1::wList *ptrAuxMain)
{
	ptrAux = ptrAuxMain;
}
wList1::wList *wList1::getPtrHead()
{
	return ptrHead;
}
wList1::wList *wList1::getPtrAux()
{
	return ptrAux;
}
wList1::wList *wList1::rightSearch(const int &id)
{
	wList *ptrTemp = ptrHead;
	if (ptrTemp->inf == id)
	{
		return ptrTemp;
	}
	if (ptrTemp->ptrLeft == ptrHead && ptrTemp->ptrRight == ptrHead)
	{
		return 0;
	}			
	
	ptrTemp = ptrHead->ptrRight;
	while (ptrTemp != ptrHead)
	{
		if (ptrTemp->inf == id)
		{
			return ptrTemp;
		}
		ptrTemp = ptrTemp->ptrRight;
	}	
	return 0;	
}
wList1::wList *wList1::reverseSearch(const int &id)
{
	wList *ptrTemp = ptrHead;
	
	if (ptrTemp->inf == id)
	{
		return ptrHead;
	}
	if (ptrTemp->ptrLeft == ptrHead && ptrTemp->ptrRight == ptrHead)
	{
		return 0;
	}
	ptrTemp = ptrTemp->ptrLeft;
	while(ptrTemp != ptrHead)
	{
		if(ptrTemp->inf == id)
		{
			return ptrTemp;
		}
		ptrTemp = ptrTemp->ptrLeft;
	}	
	return 0;
}
void wList1::pushAfter(const int &id)
{
	int key;
	int number;	
	wList *ptrTemp;
	wList *ptrCurrent;
	if (!ptrHead)
	{
		ptrTemp = (wList*)malloc(sizeof(wList));
		if (ptrTemp)
		{
			ptrHead = ptrTemp;
			printf("\nEnter number\n");
			scanf("%d", &number);
			ptrHead->inf = number;
			ptrTemp->ptrRight = ptrTemp;
			ptrTemp->ptrLeft = ptrTemp;
			return;
		}
		else 
		{
			printf ("\nERROR\n");
			return;
		}
	}
	loop1:
	printf ("\n1-right search\n2-reverse search");
	scanf("%d", &key);
	switch(key)
	{
	case 1:		
		ptrCurrent = wList1::rightSearch(id);				
		break;
	case 2:		
		ptrCurrent = wList1::reverseSearch(id);				
		break;
	default :
		goto loop1;
		break;
	}

	if (!ptrCurrent)
	{
		printf("\nElement not found\n");
		return;
	}
	loop2:
	printf("\n1-Create new element\n2-Enter element from auxiliary list");
	scanf("%d", &key);
	switch(key)
	{
	case 1:
		ptrTemp = (  wList*)malloc(sizeof(  wList));
		if(ptrTemp)
		{
			printf("\nEnter element\n");
			scanf("%d", &number);
			ptrTemp->inf = number;
			ptrTemp->ptrRight = ptrCurrent->ptrRight;
			ptrTemp->ptrLeft = ptrCurrent;			
			ptrCurrent->ptrRight->ptrLeft = ptrTemp;
			ptrCurrent->ptrRight = ptrTemp;	
			return;
		}
		else if (ptrTemp == NULL)
		{
			printf("\nERROR\n");
			return;
		}
		return;
	case 2:
		if (ptrAux)
		{
			ptrAux->ptrRight = ptrCurrent->ptrRight;
			ptrAux->ptrLeft = ptrCurrent;
			ptrCurrent->ptrRight->ptrLeft = ptrAux;
			ptrCurrent->ptrRight = ptrAux;
			ptrAux = ptrAux->ptrLeft;
			return;
		}
		else if (ptrAux == NULL)
		{
			printf("\nauxiliary list empty\n");
			goto loop2;
		}
	default :
		goto loop2;
		break;
	}
}
void wList1::pushBefore(const int &id)
{
	int key;
	int number;
	wList *ptrTemp;
	wList *ptrCurrent;
	if (!ptrHead)
	{
		ptrTemp = (wList*)malloc(sizeof(wList));
		if (ptrTemp)
		{
			printf("\nEnter element\n");
			scanf("%d", &number);
			ptrHead = ptrTemp;
			ptrHead->inf = number;
			ptrTemp->ptrRight = ptrTemp;
			ptrTemp->ptrLeft = ptrTemp;
			return;
		}
		else
		{
			printf ("\nERROR\n");
			return;
		}
	}

	loop1:
	printf ("\n1-right search\n2-reverse search");
	scanf("%d", &key);
	switch(key)
	{
	case 1:
		ptrCurrent = wList1::rightSearch(id);
		break;
	case 2:
		ptrCurrent = wList1::reverseSearch(id);
		break;
	default :
		goto loop1;
		break;
	}

	if (!ptrCurrent)
	{
		printf("\nElement not found\n");
		return;
	}
	loop2:
	printf("\n1-Create new element\n2-Enter element from auxiliary list");
	scanf("%d", &key);
	switch(key)
	{
	case 1:
		ptrTemp = (  wList *)malloc(sizeof(  wList));
		if (ptrTemp)
		{
			printf("\nEnter element\n");
			scanf("%d", &number);
			ptrTemp->inf = number; 
			ptrTemp->ptrLeft = ptrCurrent->ptrLeft;
			ptrTemp->ptrRight = ptrCurrent;
			ptrCurrent->ptrLeft->ptrRight = ptrTemp;
			ptrCurrent->ptrLeft = ptrTemp;
			if (ptrCurrent == ptrHead)
				ptrHead = ptrTemp;
			return;
		}
		else 
		{
			printf ("\nERROR\n");
			return;
		}
	case 2:
		if (ptrAux)
		{
			ptrCurrent->ptrLeft->ptrRight = ptrAux;
			ptrCurrent->ptrLeft = ptrAux;
			ptrTemp = ptrAux->ptrRight;
			ptrAux->ptrRight = ptrCurrent;
			ptrAux->ptrLeft = ptrCurrent->ptrLeft;
			ptrAux = ptrTemp;
			if (ptrCurrent == ptrHead)
				ptrHead = ptrTemp;
			return;
		}
		else if (ptrAux == NULL)
		{
			printf("\nAux list empty\n");
			goto loop2;
		}
		break;
	default :
		goto loop2;
	}
}
void wList1::showRight ()
{
	wList *ptrTemp = ptrHead;
	if (!ptrTemp)
	{
		printf ("wList empty");
		return;
	}
	printf("\n%d", ptrTemp->inf);

	if (ptrTemp->ptrLeft == ptrHead && ptrTemp->ptrRight == ptrHead)
		return;	

	ptrTemp = ptrHead->ptrRight;
	while (ptrTemp != ptrHead)
	{
		printf("\n%d", ptrTemp->inf);
		ptrTemp = ptrTemp->ptrRight;
	}
	
}
void wList1::showReverse ()
{
	wList *ptrTemp = ptrHead;
	if (!ptrTemp)
	{
		printf ("wList empty");
		return;
	}
	printf("\n%d", ptrTemp->inf);
	if (ptrTemp->ptrLeft == ptrHead && ptrTemp->ptrRight == ptrHead)
		return;

	ptrTemp = ptrTemp->ptrLeft;
	while(ptrTemp != ptrHead)
	{
		printf("\n%d", ptrTemp->inf);
		ptrTemp = ptrTemp->ptrLeft;
	}
}

void wList1::showAux()
{
	wList *ptrTemp = ptrAux;
	if(!ptrTemp)
	{
		printf("\nAux list empty\n");
		return;
	}
	while(ptrTemp)
	{
		printf("\nElement aux %d", ptrTemp->inf);
		ptrTemp = ptrTemp->ptrRight;
	}

}
void wList1::pop(const int &id)
{
	int key;	
	wList *ptrTemp;
	wList *ptrCurrent;
	if (!ptrHead)
	{
		printf("\nList empty\n");
		return;
	}
	loop1:
	printf ("\n1-right search\n2-reverse search");
	scanf("%d", &key);
	switch(key)
	{
	case 1:
		ptrCurrent = wList1::rightSearch(id);		
		break;
	case 2:
		ptrCurrent = wList1::reverseSearch(id);
		break;
	default :
		goto loop1;		
	}
	if (!ptrCurrent)
	{
		printf("\nElement not found\n");
		return;
	}
	loop2:
	printf("\n1-delete element with free\n2-transfer element in auxiliary list\n");
	scanf("%d", &key);
	switch(key)
	{
	case 1:
		ptrCurrent->ptrLeft->ptrRight = ptrCurrent->ptrRight;
		ptrCurrent->ptrRight->ptrLeft = ptrCurrent->ptrLeft;
		free(ptrCurrent);
		break;
	case 2:
		ptrCurrent->ptrLeft->ptrRight = ptrCurrent->ptrRight;
		ptrCurrent->ptrRight->ptrLeft = ptrCurrent->ptrLeft;
		ptrCurrent->ptrRight = ptrAux;
		ptrCurrent->ptrLeft = NULL;
		ptrAux = ptrCurrent;
		break;
	default :
		goto loop2;
		break;
	}
}
void wList1::popBranch()
{
	wList *ptrTemp = ptrHead->ptrLeft;
	ptrHead->ptrLeft = 0;
	wList *ptrDel;
	while (ptrTemp)
	{	
		ptrDel = ptrTemp;
		ptrTemp = ptrTemp->ptrLeft;
		free(ptrDel);		
	}
}
void wList1::popAux()
{
	if (ptrAux)
	{
		wList *ptrTemp = ptrAux->ptrRight;
		wList *ptrDel = ptrAux;
	
		while (ptrTemp)
		{
			free(ptrDel);
			ptrDel = ptrTemp;
			ptrTemp = ptrTemp->ptrRight;
		}
	}
}

void wList1::menu (wList1::wList * ptrCurrentMain, wList1::wList *ptrAux)
{
	initializeHead(ptrCurrentMain);
	initializeAux(ptrAux);

	int key;
	int number;
	
	printf("\n1-push after element\n2-push before element\n3-show base list(easy flow direction)\n4-show base list (reverse)\n5-pop\n6-show auxiliary list\n7-exit\n");
	scanf("%d", &key);
	while (1)
	{
	switch(key)
	{
		case 1:
			printf("\nEnter element\n");
			scanf("%d", &number);
			pushAfter(number);
			break;
		case 2:
			printf("\nEnter element\n");
			scanf("%d", &number);
			pushBefore(number);
			break;
		case 3:
			showRight();
			break;
		case 4:
			showReverse();
			break;
		case 5:
			printf("\nEnter element for find\n");
			scanf("%d", &number);
			pop(number);
			break;
		case 6:
			showAux();
			break;
		case 7:
			printf("\nBye\n");
			return;
		default : 
			break;			
	}
	printf("\n1-push after element\n2-push before element\n3-show base list(easy flow direction)\n4-show base list (reverse)\n5-pop\n6-show auxiliary list\n7-exit\n");
	scanf("%d", &key);
	}
}

Tags:
Hubs:
You can’t comment this publication because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author’s username will be hidden by an alias.

Your account

Sections

Information

Services

Support
© 2006–2025, Habr