C언어 13일차

ArrayList

 

#include<stdio.h>
#define MAX_LIST_SIZE 500

typedef int element;
typedef struct {
	element list[MAX_LIST_SIZE];
	int length;
}ArrayListType;

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

void Init(ArrayListType* pList)
{
	pList->length = 0;
}

int IsEmpty(ArrayListType* pList)
{
	return pList->length == 0;
}

int IsFull(ArrayListType* pList)
{
	return pList->length == MAX_LIST_SIZE;
}

void Add(ArrayListType* pList, int position, element item)
{
	if (!IsFull(pList) && (position >= 0) && (position <= pList->length))
	{
		for (int i = (pList->length - 1); i >= position; i--)
		{
			pList->list[i + 1] = pList->list[i];
		}
		pList->list[position] = item;
		pList->length++;
	}
}

element Delete(ArrayListType* pList, int position)
{
	element item;
	if (position < 0 || position >= pList->length)
	{
		Error("Index Error!!");
		return -1;
	}
	item = pList->list[position];
	for (int i = position ; i <= (pList->length - 1); i++)
	{
		pList->list[i] = pList->list[i+1];
	}
	pList->length--;
	return item;
}
void AddLast(ArrayListType* pList, element item)
{
	if (!IsFull(pList))
	{
		pList->list[pList->length] = item;
		pList->length++;
	}
	else
	{
		Error("List is full!!");
	}
}

void AddFirst(ArrayListType* pList, element item)
{
	if (!IsFull(pList))
	{
		Add(pList, 0, item);
	}
	else
	{
		Error("List is full!!");
	}
}
void DisplayList(ArrayListType* pList)
{
	for (int i = 0; i < pList->length; i++)
	{
		printf("%d ", pList->list[i]);
	}
	printf("\n");
}
void Clear(ArrayListType* pList)
{
	Init(pList);
}

void Replace(ArrayListType* pList, int position, element item)
{
	pList->list[position] = item;

}
int IsInList(ArrayListType* pList, element item)
{
	for (int i = 0; i < pList->length; i++)
	{
		if (pList->list[i] == item)
		{
			return i;
		}
	}
	return -1;
}

element GetEntry(ArrayListType* pList, int position)
{
	if (position >= pList->length || position < 0)
	{
		Error("Index Error!!");
		return -1;
	}
	return pList->list[position];
}
int GetLength(ArrayListType* pList)
{
	return pList->length;
}

int main(void)
{
	ArrayListType myList;
	Init(&myList);
	AddLast(&myList, 1);
	AddLast(&myList, 2);
	AddLast(&myList, 3);
	AddLast(&myList, 4);
	AddLast(&myList, 5);

	AddFirst(&myList, 99);
	Add(&myList, 2, 77);

	DisplayList(&myList);
	Delete(&myList, 6);
	DisplayList(&myList);

	Replace(&myList, 3, 55);
	DisplayList(&myList);

	printf("%d\n", IsInList(&myList, 88));
	printf("%d\n", GetEntry(&myList,3));
	printf("%d\n", GetLength(&myList));

	return 0;
}

 

LinkedList ( ListNode* GetLast(ListNode* pHead) 구현하기)

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

typedef int element;
typedef struct ListNode
{
	element data;
	struct ListNode* link;
}ListNode;

ListNode* CreateNode(element data)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = data;
	p->link = NULL;
	return p;
}

void InsertNode(ListNode* *pHead, ListNode* pNode, ListNode* newNode) //pNode: front node, newNode: node to be inserted
{
	if (*pHead == NULL)
	{
		*pHead = newNode;
		newNode->link = NULL;
	}
	else if (pNode == NULL)
	{
		newNode->link = *pHead;
		*pHead = newNode;
	}
	else
	{
		newNode->link = pNode->link;
		pNode->link = newNode;
	}


}

void RemoveNode(ListNode** pHead, ListNode* pNode, ListNode* removed) //pNode: front node, removed: node to be removed
{
	if (pNode == NULL)
	{
		*pHead = (*pHead)->link;
		//*pHead = removed->link;
	}
	else
	{
		pNode->link = removed->link;
	}
	free(removed);
}
void Display(ListNode* pHead)
{
	ListNode* p = pHead;
	while (p != NULL)
	{
		printf("%d->", p->data);
		p = p->link;
	}
	printf("\n");
}

ListNode* Search(ListNode* pHead, element x)
{
	ListNode* p = pHead;
	while (p != NULL)
	{
		if (p->data == x)
		{
			return p;
		}
		p = p->link;
	}
	return p;
}

ListNode* GetLast(ListNode* pHead)
{
	ListNode* p = pHead;
	while (p->link != NULL)
	{
		p = p->link;
	}
	return p;
}


int main(void)
{
	ListNode* pHead = NULL;
	ListNode* newNode = CreateNode(1);
	InsertNode(&pHead, NULL, newNode);

	newNode = CreateNode(2);
	InsertNode(&pHead, GetLast(pHead), newNode);
	newNode = CreateNode(3);
	InsertNode(&pHead, GetLast(pHead), newNode);
	newNode = CreateNode(4);
	InsertNode(&pHead, GetLast(pHead), newNode);
	newNode = CreateNode(5);
	InsertNode(&pHead, GetLast(pHead), newNode);

	Display(pHead);

	RemoveNode(&pHead, NULL, Search(pHead, 1));
	Display(pHead);

	RemoveNode(&pHead, Search(pHead,3), Search(pHead, 4));
	Display(pHead);
	return 0;
}