C언어 14일차

DoubleLinkedList

#include<stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct DlistNode
{
	element data;
	struct DlistNode* lLink;
	struct DlistNode* rLink;

}DlistNode;

void DInsertNode(DlistNode* before, DlistNode* newNode)
{
	newNode->lLink = before;
	newNode->rLink = before->rLink;
	if (before->rLink != NULL)
	{
		before->rLink->lLink = newNode;
	}
	before->rLink = newNode;

}
void DRemoveNode(DlistNode* removed)
{
	removed->lLink->rLink = removed->rLink;
	if (removed->rLink != NULL)
	{
		removed->rLink->lLink = removed->lLink;
	}

}
void DRemoveAll(DlistNode* pHead)
{
	DlistNode* pNode = pHead->rLink;
	pHead->rLink = NULL;
	while (1)
	{
		if (pNode == NULL)
		{
			break;
		}
		DlistNode* pNext = pNode->rLink;
		free(pNode);
		pNode = pNext;
	}
}

DlistNode* DSearch(DlistNode* pHead, element x)
{
	DlistNode* p = pHead;
	while (p != NULL)
	{
		if (p->data == x)
		{
			return p;
		}
		p = p->rLink;
	}
	return p;
}
void DDisplay(DlistNode* pHead)
{
	DlistNode* p = pHead;
	while (p != NULL)
	{
		printf("%d->", p->data);
		p = p->rLink;
	}
	printf("\n");
}

int main(void)
{
	DlistNode head = { 0,NULL,NULL };
	DlistNode* before = &head;
	DlistNode* pNode;
	for (int i = 1; i < 11; i++)
	{
		pNode = (DlistNode*)malloc(sizeof(DlistNode));
		pNode->data = i * 10;
		DInsertNode(before, pNode);
		before = pNode;
	}
	DDisplay(&head);

	pNode = (DlistNode*)malloc(sizeof(DlistNode));
	pNode->data = 35;
	DInsertNode(DSearch(&head, 30), pNode);
	DDisplay(&head);
	
	pNode = DSearch(&head, 50);
	DRemoveNode(pNode);
	DDisplay(&head);

	DRemoveAll(&head);
	DDisplay(&head);

	return 0;
}

 

 

Stack

#include<stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100
typedef int element;
typedef struct StackNode
{
	element item;
	struct StackNode* link;
}StackNode;

typedef struct
{
	StackNode* top;
}LinkedStackType;

void Error(char* s)
{
	printf("---<%s>---\n", s);
}

LinkedStackType* CreateStack(void)
{
	LinkedStackType* p = (LinkedStackType*)malloc(sizeof(LinkedStackType));
	return p;
}
void InitStack(LinkedStackType* s)
{
	s->top = NULL;
}
int IsEmptyStack(LinkedStackType* s)
{
	return (s->top == NULL);
}

void Push(LinkedStackType* s, element item)
{
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
	if(temp == NULL)
	{
		Error("Memory allocation error!");
		return;
	}
	temp->item = item;
	temp->link = s->top;
	s->top = temp;
}

element Pop(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack Underflow");
		return -1;
	}
	StackNode* temp = s->top;
	element item = temp->item;
	s->top = s->top->link;
	free(temp);
	return item;
}
element PeekStack(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return -1;
	}
	return s->top->item;
}
void PrintStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return;
	}
	while (temp != NULL)
	{
		printf("%d\n", temp->item);
		temp = temp->link;
	}

}
void RemoveAllStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	StackNode* next;
	while (temp != NULL)
	{
		next = temp->link;
		free(temp);
		temp = next;
	}
	s->top = NULL;
}




int main(void)
{
	LinkedStackType* pStack = CreateStack();
	InitStack(pStack);

	Push(pStack, 10);
	Push(pStack, 20);
	Push(pStack, 30);
	Push(pStack, 40);
	Push(pStack, 50);
	PrintStack(pStack);

	printf("Pop() : %d\n", Pop(pStack));
	PrintStack(pStack);

	printf("Pop() : %d\n", Pop(pStack));
	printf("Pop() : %d\n", Pop(pStack));
	printf("Pop() : %d\n", Pop(pStack));
	printf("Pop() : %d\n", Pop(pStack));
	printf("Pop() : %d\n", Pop(pStack));
	PrintStack(pStack);

	Push(pStack, 10);
	Push(pStack, 20);
	Push(pStack, 30);
	Push(pStack, 40);
	Push(pStack, 50);
	PrintStack(pStack);

	RemoveAllStack(pStack);
	PrintStack(pStack);

	free(pStack);



	return 0;
}

 

Stack 과제

#include<stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100
typedef char element;
typedef struct StackNode
{
	element item;
	struct StackNode* link;
}StackNode;

typedef struct
{
	StackNode* top;
}LinkedStackType;

void Error(char* s)
{
	printf("---<%s>---\n", s);
}

LinkedStackType* CreateStack(void)
{
	LinkedStackType* p = (LinkedStackType*)malloc(sizeof(LinkedStackType));
	return p;
}
void InitStack(LinkedStackType* s)
{
	s->top = NULL;
}
int IsEmptyStack(LinkedStackType* s)
{
	return (s->top == NULL);
}

void Push(LinkedStackType* s, element item)
{
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
	if(temp == NULL)
	{
		Error("Memory allocation error!");
		return;
	}
	temp->item = item;
	temp->link = s->top;
	s->top = temp;
}

element Pop(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack Underflow");
		return -1;
	}
	StackNode* temp = s->top;
	element item = temp->item;
	s->top = s->top->link;
	free(temp);
	return item;
}
element PeekStack(LinkedStackType* s)
{
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return -1;
	}
	return s->top->item;
}
void PrintStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	if (IsEmptyStack(s))
	{
		Error("Stack is empty!");
		return;
	}
	while (temp != NULL)
	{
		printf("%d\n", temp->item);
		temp = temp->link;
	}

}
void RemoveAllStack(LinkedStackType* s)
{
	StackNode* temp = s->top;
	StackNode* next;
	while (temp != NULL)
	{
		next = temp->link;
		free(temp);
		temp = next;
	}
	s->top = NULL;
}
int CheckMatch(char* expression)
{
	LinkedStackType* pStack = CreateStack();
	InitStack(pStack);

	char* p = expression;
	int retVal = 1;
	// 여는 괄호 Push , 닫는 괄호일경우 pop , 문자열이 끝났을때 비워져있을 경우 참
	while (*p)
	{
		if (*p == '[' || *p == '{' || *p == '(')
		{
			Push(pStack, *p);
		}
		else
		{
			switch (*p)
			{
			case ']':
				if (IsEmptyStack(pStack) || Pop(pStack) != '[')
				{
					retVal = 0;
				}
				break;
			case '}':
				if (IsEmptyStack(pStack) || Pop(pStack) != '{')
				{
					retVal = 0;
				}
				break;
			case ')':
				if (IsEmptyStack(pStack) || Pop(pStack) != '(')
				{
					retVal = 0;
				}
				break;
			}
			
			if (!retVal)
			{
				RemoveAllStack(pStack);
				free(pStack);
				return retVal;

			}
		}
		p++;
	}
	if (!IsEmptyStack(pStack))
	{
		retVal = 0;
	}
	RemoveAllStack(pStack);
	free(pStack);
	return retVal;
}





int main(void)
{
	char exp1[] = { "[ a { b + c - ( a * 3 ) } + 4 ]" };
	char exp2[] = { "[ a { b + c - ( a * 3 ) + 4 ]" };

	printf("%d\n", CheckMatch(exp1));
	printf("%d\n", CheckMatch(exp2));


	return 0;
}