[데이터 구조] DLL 응용문제/데이터 빈도 출력

DLL응용문제

 

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

//node 구조체정의
struct node {
	int data;
	struct node *next;
	struct node *prev;
};
struct node* head = 0;

struct statNode{
	int data;
	int freq;
	struct statNode *prev;
	struct statNode *next;
};
struct statNode *shead = 0;


//returns the pointer to the node which has bigger data than _data
//returns null if _data is the biggest
struct statNode *whoIsBigger(int _data)
{
	struct statNode *temp = shead;

	while (temp != 0) {
		if (temp -> data > _data) {
			break;
		}
		temp = temp->next;
	}
	return temp;

}

//returns the pointer to the node which has _data
//returns null if no node has _data
struct statNode* whereIsNode(int _data)
{
	struct statNode *temp = shead;

	while (temp != 0) {
		if (temp->data == _data) {
			break;
		}
		temp = temp->next;
	}
	return temp;
}

void showstatDLL() 
{
	struct statNode *temp = shead;
	while (temp != 0) {
		printf("%d %d ", temp->data, temp->freq);
		temp = temp->next;
	}
}

void addToStatDLL(int _data)
{
	//1.determine which node has _data
	struct statNode *temp;

	temp = whereIsNode(_data);
	if (temp != 0) {//temp is pointing to the node having _data
		temp->freq += 1;
		return;
	}
	else { //no node has _data
		struct statNode *cur;
		cur = (struct statNode*)malloc(sizeof(struct statNode));
		cur->data = _data;
		cur->freq = 1;
		cur->next = cur->prev = 0;

		if (shead == 0) {

			shead = cur;
			return;
		}
		else {
			struct statNode *temp;
			temp = whoIsBigger(_data);

			if (temp == 0) {//_data is the biggest

				//add to the last location
				struct statNode *final = shead;
				while (final->next != 0)
				{
					final = final->next;
				}
				final->next = cur;
				cur->prev = final;
				return;

			}
			else {
				if (temp == shead) { //_data is the smallest

					//add to the first location
					cur->next = shead;
					shead = cur;
					cur->next->prev = cur;
					return;
				}
				else {

					//insert _data before temp
					cur->next = temp;
					cur->prev = temp->prev;
					temp->prev = cur;
					cur->prev->next = cur;
				}
			}

		}
	}
}


//DLL에 추가하는함수
void addToDLL(int data)
{
	struct node *cur;
	cur = (struct node*)malloc(sizeof(struct node));
	cur->data = data;
	cur->next = cur->prev = 0;;

	//1.DLL이 empty
	if (head == 0) {

		head = cur;
		return;
	}
	//2 else
	//2.1끝을찾자
	//2.2끝에 붙이자
	{
		struct node* temp = head;
		while (temp->next != 0)
		{
			temp = temp->next;
		}
		temp->next = cur;
		cur->prev = temp;
		return;
	}
}



//DLL에 들어있는 데이터를 앞에서부터 차례로출력
void showDLL()
{
	struct node *cur = head;

	while (cur != 0) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
	return;
}


int main(void)
{
	int num, data;
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		scanf("%d", &data);
		addToDLL(data);
	}

	struct node *temp = head;
	while (temp != 0) {
		addToStatDLL(temp->data);
		temp = temp->next;
	}
	showstatDLL();
	return 0;
}