자료구조 과제3

IT 프로그래밍/자료구조

자료구조 과제3

기술1 2024. 10. 23. 22:29

자료구조 1번

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <vector>

using namespace std;


struct node
{
	int x, y, w, h;
	node* next;
};

node* head = nullptr;

void print_list()
{
	node* p = head;
	while (p != nullptr)
	{
		cout << p->x << " " << p->y << " " << p->w << " " << p->h << endl;
		p = p->next;
	}
}

void read_file()
{
	ifstream file("rects.txt");

	int n;
	file >> n; //사각형 개수 읽기
	int x, y, w, h;

	for (int i = 0; i < n; i++)
	{
		file >> x >> y >> w >> h;
		node* new_node = new node{ x, y, w, h, head }; // next를 이전 노드로 해주는 것이다
		head = new_node;
	}

	file.close();
}

void sort_by_area()
{
	if (!head) return;

	node* sorted = nullptr;

	while (head)
	{
		node* current = head;
		head = head->next;

		if (!sorted || current->w * current->h < sorted->w * sorted->h)
		{
			current->next = sorted;
			sorted = current;
		}
		else
		{
			node* p = sorted;
			while (p->next && p->next->w * p->next->h < current->w * current->h)
			{
				p = p->next;
			}
			current->next = sorted->next;
			p->next = current;

		}
	}

	head = sorted;
}

void remove_rects(int min_w, int min_h)
{
	node* current = head;
	node* prev = nullptr;

	while(current)
	{
		if(current->w <= min_w || current->h <= min_h)
		{
			if (prev)
				prev->next = current->next;
			else
				head = current->next;

			delete current;
			if (prev)
				current = prev->next;
			else
				current = head;
		}
		else
		{
			prev = current;
			current = current->next;
		}
	}
}

int main()
{
	// (1)
	read_file();
	print_list();

	cout << endl;

	// (2)
	sort_by_area();
	print_list();
	cout << endl;

	// (3)
	int min_w, min_h;
	cin >> min_w >> min_h;
	remove_rects(min_w, min_h);
	print_list();

	return 0;
	    
}

이 프로그램은 파일로부터 사각형들의 정보를 읽어들여, 리스트로 관리하고, 해당 사각형들을 면적에 따라 정렬하거나 특정 크기 이하의 사각형을 삭제하는 기능을 구현한 코드입니다. 각 기능을 하나씩 설명하겠습니다.

구조체 node:
- 각 사각형의 정보를 저장하는 구조체입니다. 사각형의 좌표 (x, y)와 크기 (w, h)를 저장하며, 다음 노드를 가리키는 포인터 next도 포함되어 있어 연결 리스트 구조로 사각형들을 저장합니다.
read_file 함수:
- rects.txt 파일로부터 사각형 정보를 읽어들입니다. 파일의 첫 번째 줄에는 사각형의 개수가 있고, 그 다음 줄들에는 각각 사각형의 좌표와 크기 (x, y, w, h)가 있습니다.
- 사각형 정보를 읽어들일 때마다 새로운 노드를 생성하고, 그 노드를 리스트의 맨 앞에 추가합니다. 따라서 이 함수가 완료되면 사각형 정보가 연결 리스트에 저장됩니다.
print_list 함수:
- 연결 리스트에 저장된 사각형들의 정보를 출력합니다. 각 노드를 순차적으로 방문하면서, 사각형의 좌표와 크기를 출력합니다.
sort_by_area 함수:
- 리스트에 저장된 사각형들을 면적(가로 w * 세로 h) 기준으로 오름차순 정렬합니다. 선택 정렬 방식을 사용하여 리스트의 각 노드를 순차적으로 정렬된 리스트에 삽입합니다.
- 정렬된 리스트는 sorted라는 새로운 리스트에 저장되며, 정렬이 완료되면 head는 정렬된 리스트를 가리키게 됩니다.
remove_rects 함수:
- 가로 길이 w 또는 세로 길이 h가 지정된 최소값 이하인 사각형들을 리스트에서 제거하는 함수입니다.
- 리스트를 순차적으로 탐색하면서 조건에 맞는 사각형을 삭제하고, 삭제된 후에도 리스트가 끊기지 않도록 포인터를 적절히 조정합니다.
main 함수:
- (1) 파일로부터 사각형 정보를 읽어와 리스트를 구성한 뒤 출력합니다.
- (2) 면적에 따라 사각형들을 정렬하고 다시 출력합니다.
- (3) 사용자로부터 최소 가로, 세로 길이를 입력받아 그 조건에 맞지 않는 사각형들을 리스트에서 삭제하고 최종 리스트를 출력합니다.

기능추가

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <vector>

using namespace std;

struct node
{
	int x, y, w, h;
	node* next;
};

node* head = nullptr;

void print_list()
{
	node* p = head;
	while (p != nullptr)
	{
		cout << "x: " << p->x << ", y: " << p->y << ", w: " << p->w << ", h: " << p->h << endl;
		p = p->next;
	}
}

void print_list_reverse(node* p)
{
	if (p == nullptr)
		return;
	print_list_reverse(p->next);
	cout << "x: " << p->x << ", y: " << p->y << ", w: " << p->w << ", h: " << p->h << endl;
}

void read_file()
{
	ifstream file("rects.txt");
	if (!file)
	{
		cout << "File not found!" << endl;
		return;
	}

	int n;
	file >> n; //사각형 개수 읽기
	int x, y, w, h;

	for (int i = 0; i < n; i++)
	{
		file >> x >> y >> w >> h;
		node* new_node = new node{ x, y, w, h, head }; // next를 이전 노드로 해주는 것이다
		head = new_node;
	}

	file.close();
}

void save_file()
{
	ofstream file("rects_output.txt");
	node* p = head;

	while (p != nullptr)
	{
		file << p->x << " " << p->y << " " << p->w << " " << p->h << endl;
		p = p->next;
	}

	file.close();
	cout << "File saved as rects_output.txt" << endl;
}

void sort_by_area()
{
	if (!head) return;

	node* sorted = nullptr;

	while (head)
	{
		node* current = head;
		head = head->next;

		if (!sorted || current->w * current->h < sorted->w * sorted->h)
		{
			current->next = sorted;
			sorted = current;
		}
		else
		{
			node* p = sorted;
			while (p->next && p->next->w * p->next->h < current->w * current->h)
			{
				p = p->next;
			}
			current->next = p->next;
			p->next = current;
		}
	}

	head = sorted;
}

void remove_rects(int min_w, int min_h)
{
	node* current = head;
	node* prev = nullptr;

	while (current)
	{
		if (current->w <= min_w || current->h <= min_h)
		{
			if (prev)
				prev->next = current->next;
			else
				head = current->next;

			delete current;
			if (prev)
				current = prev->next;
			else
				current = head;
		}
		else
		{
			prev = current;
			current = current->next;
		}
	}
}

void add_rectangle(int x, int y, int w, int h)
{
	node* new_node = new node{ x, y, w, h, head };
	head = new_node;
	cout << "Rectangle added: (" << x << ", " << y << ", " << w << ", " << h << ")" << endl;
}

void delete_rectangle(int x, int y)
{
	node* current = head;
	node* prev = nullptr;

	while (current)
	{
		if (current->x == x && current->y == y)
		{
			if (prev)
				prev->next = current->next;
			else
				head = current->next;

			delete current;
			cout << "Rectangle at (" << x << ", " << y << ") deleted." << endl;
			return;
		}
		prev = current;
		current = current->next;
	}
	cout << "No rectangle found at (" << x << ", " << y << ")" << endl;
}

void search_rectangle(int x, int y)
{
	node* current = head;

	while (current)
	{
		if (current->x == x && current->y == y)
		{
			cout << "Found rectangle: (" << current->x << ", " << current->y << ", " << current->w << ", " << current->h << ")" << endl;
			return;
		}
		current = current->next;
	}
	cout << "No rectangle found at (" << x << ", " << y << ")" << endl;
}

void change_size(int x, int y, int new_w, int new_h)
{
	node* current = head;

	while (current)
	{
		if (current->x == x && current->y == y)
		{
			current->w = new_w;
			current->h = new_h;
			cout << "Rectangle size changed to: (" << new_w << ", " << new_h << ")" << endl;
			return;
		}
		current = current->next;
	}
	cout << "No rectangle found at (" << x << ", " << y << ")" << endl;
}

void remove_duplicates()
{
	node* current = head;

	while (current && current->next)
	{
		node* prev = current;
		node* runner = current->next;

		while (runner)
		{
			if (current->x == runner->x && current->y == runner->y && current->w == runner->w && current->h == runner->h)
			{
				prev->next = runner->next;
				delete runner;
				runner = prev->next;
			}
			else
			{
				prev = runner;
				runner = runner->next;
			}
		}
		current = current->next;
	}
	cout << "Duplicates removed." << endl;
}

int main()
{
	// 이곳에서 필요한 함수 호출을 직접 실행

	// 예시: 파일에서 사각형 정보 읽기
	read_file();
	print_list();
	
	// 사각형 정렬
	sort_by_area();
	print_list();
	
	// 사각형 추가
	add_rectangle(15, 25, 30, 40);
	print_list();
	
	// 사각형 삭제
	delete_rectangle(15, 25);
	print_list();
	
	// 사각형 검색
	search_rectangle(10, 10);

	// 사각형 크기 변경
	change_size(10, 10, 50, 60);
	print_list();
	
	// 최소 크기 사각형 제거
	remove_rects(10, 10);
	print_list();

	// 중복 제거
	remove_duplicates();
	print_list();

	// 결과 파일 저장
	save_file();

	return 0;
}

사각형 추가 및 삭제 기능:

사용자가 직접 사각형을 추가할 수 있도록 하고, 특정 사각형을 삭제할 수 있는 기능을 추가합니다.

2. 파일 저장 기능:

현재 리스트에 저장된 사각형 정보를 파일로 저장할 수 있는 기능을 추가합니다.

3. 리스트 역순 출력 기능:

리스트를 역순으로 출력할 수 있는 기능을 추가합니다.

4. 사각형 중복 확인 및 제거 기능:

동일한 사각형이 중복으로 존재할 경우 중복을 제거하는 기능을 추가합니다.

5. 사각형 크기 변경 기능:

특정 사각형의 크기를 변경할 수 있는 기능을 추가합니다.

6. 사각형 검색 기능:

좌표나 크기 등을 기준으로 특정 사각형을 검색할 수 있는 기능을 추가합니다.

자료구조 2번

#include <iostream>
#include <list>
#include <fstream>
#include <sstream>
using namespace std;

struct Node
{
	string data;

	int frequency;
	Node* next;

};

void addword(Node*&head, const string& word)
{
	Node* newNode = new Node{ word, 1, nullptr };

	if (head == nullptr)
	{
		head = newNode;
		return;
	}

	//리스트 처음 삽입
	if (word < head->data)
	{
		newNode->next = head;
		head = newNode;
		return;
	}

	//리스트 중간 삽입
	Node* current = head;
	Node* prev = nullptr;

	while(current !=nullptr && current->data < word)
	{
		prev = current;
		current = current->next;
	}

	if(current != nullptr && current->data == word) // 데이터 있을 때++1
	{
		current->frequency++;
		delete newNode;
		return;
	}
	//삽입
	prev->next = newNode;
	newNode->next = current;
}

void printlist(Node *head)
{
	Node* current = head;
	int totalWord = 0;

	while(current!=nullptr)
	{
		cout << current->data << ": " << current->frequency << endl;
		totalWord++;
		current = current->next;
	}
	cout << totalWord << endl;
}


void removeWord(Node *& head)
{
	Node* current = head;
	Node* prev = nullptr;

	while(current != nullptr)
	{
		if(current->frequency <= 10)//10이하
		{
			if(prev == nullptr) //첫번째 노드(헤드일경우)
			{
				head = current->next; 
				delete current;
				current = head;
			}
			else //중간 or 마지막에 있을 경우 
			{
				prev->next = current->next;
				delete current;
				current = prev->next;
			}
		}
		else
		{
			prev = current;
			current = current->next;
		}
	}
}

Node* sortlist(Node* head)
{
	Node* sortedhead = nullptr;

	while (head != nullptr)
	{
		Node* maxNode = head;
		Node* prevmaxNode = nullptr;
		Node* current = head->next;
		Node* prev = head;

		while (current != nullptr)
		{
			// 빈도수가 크거나, 빈도수가 동일한 경우 사전식으로 비교하여 우선순위 설정
			if (current->frequency > maxNode->frequency || (current->frequency == maxNode->frequency && current->data < maxNode->data))
			{
				maxNode = current;
				prevmaxNode = prev;
			}
			prev = current;
			current = current->next;
		}

		// maxNode를 원래 리스트에서 제거
		if (prevmaxNode != nullptr)
		{
			prevmaxNode->next = maxNode->next;
		}
		else
		{
			head = maxNode->next;
		}

		// maxNode를 정렬된 리스트의 적절한 위치에 삽입 (맨 뒤로 삽입)
		if (sortedhead == nullptr)
		{
			sortedhead = maxNode;
			maxNode->next = nullptr;
		}
		else
		{
			Node* sortedCurrent = sortedhead;
			while (sortedCurrent->next != nullptr)
			{
				sortedCurrent = sortedCurrent->next;
			}
			sortedCurrent->next = maxNode;
			maxNode->next = nullptr;
		}
	}
	return sortedhead;
}


int main()
{
	ifstream infile("harry.txt");
	string word;
	Node* head = nullptr;

	while(infile >> word)
	{
		addword(head, word);
	}
	// (1) 
	printlist(head);


	removeWord(head);

	//(2)
	printlist(head);

	// (3) 빈도수 내림차순 및 동일 빈도는 사전순으로 정렬
	Node* sortedList = sortlist(head);
	printlist(sortedList);
	return 0;
}

주요 기능 설명:

구조체 Node:
- 단어와 그 단어의 출현 빈도를 저장하는 구조체입니다. 각 노드는 단어를 나타내는 data, 출현 빈도를 나타내는 frequency, 그리고 다음 노드를 가리키는 포인터 next를 포함하고 있습니다.
addword 함수:
- 이 함수는 주어진 단어를 연결 리스트에 삽입하는 역할을 합니다.
- 단어가 이미 리스트에 존재하면, 해당 단어의 출현 빈도 frequency를 1 증가시킵니다.
- 리스트는 단어를 사전순으로 정렬된 상태로 유지하며, 새로 추가된 단어는 적절한 위치에 삽입됩니다.
printlist 함수:
- 연결 리스트의 각 노드를 출력하는 함수입니다.
- 리스트를 순차적으로 순회하면서 각 단어와 그 출현 빈도를 출력하며, 총 단어의 개수도 함께 출력합니다.
removeWord 함수:
- 출현 빈도가 10 이하인 단어를 리스트에서 삭제하는 함수입니다.
- 첫 번째 노드(헤드)에 해당하는 단어부터 차례로 빈도수가 10 이하인 경우 리스트에서 제거합니다.
sortlist 함수:
- 리스트에 있는 단어들을 출현 빈도 기준으로 내림차순 정렬하는 함수입니다.
- 빈도수가 같을 경우에는 사전순으로 정렬합니다.
- 정렬된 새로운 리스트를 반환합니다.
main 함수:
- main 함수는 텍스트 파일("harry.txt")에서 단어를 읽어 리스트에 추가한 후, 세 가지 기능을 차례대로 수행합니다:
  1. 리스트 출력: 파일로부터 읽은 단어 리스트와 빈도를 출력합니다.
  2. 출현 빈도가 10 이하인 단어 제거: 빈도가 10 이하인 단어들을 리스트에서 삭제하고, 다시 출력합니다.
  3. 빈도수 기준 정렬: 남은 단어들을 빈도수 내림차순(빈도가 같을 경우 사전순)으로 정렬하고 출력합니다.

프로그램 실행 순서:

파일에서 단어 읽기:
- 프로그램은 "harry.txt" 파일에서 단어를 하나씩 읽어들여 리스트에 저장합니다.
리스트 출력 (1):
- 파일에서 읽은 단어와 그 빈도를 출력합니다.
빈도 10 이하 단어 제거:
- removeWord 함수를 호출하여, 빈도수가 10 이하인 단어들을 리스트에서 제거합니다.
리스트 출력 (2):
- 빈도 10 이하 단어가 제거된 상태에서 남은 단어들을 다시 출력합니다.
리스트 정렬 및 출력:
- sortlist 함수를 통해 빈도수 기준 내림차순(동일 빈도는 사전순)으로 단어들을 정렬하고, 다시 출력합니다.

문제 1: 대소문자 무시하고 단어 빈도 계산하기

#include <iostream>
#include <fstream>
#include <string>
#include <cctype> // for tolower
using namespace std;

struct Node
{
    string data;
    int frequency;
    Node* next;
};

void toLowercase(string& word)
{
    for (char& c : word)
        c = tolower(c); // 모든 문자를 소문자로 변환
}

void addword(Node*& head, const string& word)
{
    string lowerWord = word;
    toLowercase(lowerWord); // 단어를 소문자로 변환

    Node* newNode = new Node{ lowerWord, 1, nullptr };

    if (head == nullptr)
    {
        head = newNode;
        return;
    }

    // 리스트 처음 삽입
    if (lowerWord < head->data)
    {
        newNode->next = head;
        head = newNode;
        return;
    }

    // 리스트 중간 삽입
    Node* current = head;
    Node* prev = nullptr;

    while (current != nullptr && current->data < lowerWord)
    {
        prev = current;
        current = current->next;
    }

    if (current != nullptr && current->data == lowerWord) // 데이터 있을 때 ++1
    {
        current->frequency++;
        delete newNode;
        return;
    }
    // 삽입
    prev->next = newNode;
    newNode->next = current;
}

void printlist(Node* head)
{
    Node* current = head;
    int totalWord = 0;

    while (current != nullptr)
    {
        cout << current->data << ": " << current->frequency << endl;
        totalWord++;
        current = current->next;
    }
    cout << "Total unique words: " << totalWord << endl;
}

int main()
{
    ifstream infile("harry.txt");
    string word;
    Node* head = nullptr;

    while (infile >> word)
    {
        addword(head, word);
    }

    printlist(head);
    return 0;
}

문제 2: 구두점 제거 후 단어 빈도 계산하기

#include <iostream>
#include <fstream>
#include <string>
#include <cctype> // for ispunct
using namespace std;

struct Node
{
    string data;
    int frequency;
    Node* next;
};

void removePunctuation(string& word)
{
    string cleanWord = "";
    for (char c : word)
    {
        if (!ispunct(c)) // 구두점이 아니면 단어에 추가
            cleanWord += c;
    }
    word = cleanWord;
}

void addword(Node*& head, const string& word)
{
    string cleanWord = word;
    removePunctuation(cleanWord); // 구두점 제거

    Node* newNode = new Node{ cleanWord, 1, nullptr };

    if (head == nullptr)
    {
        head = newNode;
        return;
    }

    // 리스트 처음 삽입
    if (cleanWord < head->data)
    {
        newNode->next = head;
        head = newNode;
        return;
    }

    // 리스트 중간 삽입
    Node* current = head;
    Node* prev = nullptr;

    while (current != nullptr && current->data < cleanWord)
    {
        prev = current;
        current = current->next;
    }

    if (current != nullptr && current->data == cleanWord) // 데이터 있을 때 ++1
    {
        current->frequency++;
        delete newNode;
        return;
    }
    // 삽입
    prev->next = newNode;
    newNode->next = current;
}

void printlist(Node* head)
{
    Node* current = head;
    int totalWord = 0;

    while (current != nullptr)
    {
        cout << current->data << ": " << current->frequency << endl;
        totalWord++;
        current = current->next;
    }
    cout << "Total unique words: " << totalWord << endl;
}

int main()
{
    ifstream infile("harry.txt");
    string word;
    Node* head = nullptr;

    while (infile >> word)
    {
        addword(head, word);
    }

    printlist(head);
    return 0;
}

문제 3: 파일에서 가장 많이 등장한 단어 찾기

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

struct Node
{
    string data;
    int frequency;
    Node* next;
};

void addword(Node*& head, const string& word)
{
    Node* newNode = new Node{ word, 1, nullptr };

    if (head == nullptr)
    {
        head = newNode;
        return;
    }

    // 리스트 처음 삽입
    if (word < head->data)
    {
        newNode->next = head;
        head = newNode;
        return;
    }

    // 리스트 중간 삽입
    Node* current = head;
    Node* prev = nullptr;

    while (current != nullptr && current->data < word)
    {
        prev = current;
        current = current->next;
    }

    if (current != nullptr && current->data == word) // 데이터 있을 때 ++1
    {
        current->frequency++;
        delete newNode;
        return;
    }
    // 삽입
    prev->next = newNode;
    newNode->next = current;
}

void findMostFrequent(Node* head)
{
    if (head == nullptr)
    {
        cout << "List is empty." << endl;
        return;
    }

    Node* current = head;
    Node* mostFrequent = head;

    while (current != nullptr)
    {
        if (current->frequency > mostFrequent->frequency)
        {
            mostFrequent = current;
        }
        current = current->next;
    }

    cout << "Most frequent word: " << mostFrequent->data << " with frequency: " << mostFrequent->frequency << endl;
}

int main()
{
    ifstream infile("harry.txt");
    string word;
    Node* head = nullptr;

    while (infile >> word)
    {
        addword(head, word);
    }

    findMostFrequent(head);

    return 0;
}

문제 4: 단어 길이 기준으로 정렬하기

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

struct Node
{
    string data;
    int frequency;
    Node* next;
};

void addword(Node*& head, const string& word)
{
    Node* newNode = new Node{ word, 1, nullptr };

    if (head == nullptr)
    {
        head = newNode;
        return;
    }

    // 리스트 처음 삽입
    if (word < head->data)
    {
        newNode->next = head;
        head = newNode;
        return;
    }

    // 리스트 중간 삽입
    Node* current = head;
    Node* prev = nullptr;

    while (current != nullptr && current->data < word)
    {
        prev = current;
        current = current->next;
    }

    if (current != nullptr && current->data == word) // 데이터 있을 때 ++1
    {
        current->frequency++;
        delete newNode;
        return;
    }
    // 삽입
    prev->next = newNode;
    newNode->next = current;
}

Node* sortlistByLength(Node* head)
{
    Node* sortedhead = nullptr;

    while (head != nullptr)
    {
        Node* maxNode = head;
        Node* prevmaxNode = nullptr;
        Node* current = head->next;
        Node* prev = head;

        while (current != nullptr)
        {
            // 단어 길이가 더 짧거나, 길이가 같다면 사전순으로 비교
            if (current->data.length() < maxNode->data.length() ||
                (current->data.length() == maxNode->data.length() && current->data < maxNode->data))
            {
                maxNode = current;
                prevmaxNode = prev;
            }
            prev = current;
            current = current->next;
        }

        // maxNode를 원래 리스트에서 제거
        if (prevmaxNode != nullptr)
        {
            prevmaxNode->next = maxNode->next;
        }
        else
        {
            head = maxNode->next;
        }

        // maxNode를 정렬된 리스트의 적절한 위치에 삽입 (맨 뒤로 삽입)
        if (sortedhead == nullptr)
        {
            sortedhead = maxNode;
            maxNode->next = nullptr;
        }
        else
        {
            Node* sortedCurrent = sortedhead;
            while (sortedCurrent->next != nullptr)
            {
                sortedCurrent = sortedCurrent->next;
            }
            sortedCurrent->next = maxNode;
            maxNode->next = nullptr;
        }
    }
    return sortedhead;
}

void printlist(Node* head)
{
    Node* current = head;
    int totalWord = 0;

    while (current != nullptr)
    {
        cout << current->data << ": " << current->frequency << endl;
        totalWord++;
        current = current->next;
    }
    cout << "Total unique words: " << totalWord << endl;
}

int main()
{
    ifstream infile("harry.txt");
    string word;
    Node* head = nullptr;

    while (infile >> word)
    {
        addword(head, word);
    }

    // 단어 길이로 정렬
    Node* sortedList = sortlistByLength(head);
    printlist(sortedList);

    return 0;
}

문제 5: 가장 적게 등장한 단어 제거하기

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

struct Node
{
    string data;
    int frequency;
    Node* next;
};

void addword(Node*& head, const string& word)
{
    Node* newNode = new Node{ word, 1, nullptr };

    if (head == nullptr)
    {
        head = newNode;
        return;
    }

    // 리스트 처음 삽입
    if (word < head->data)
    {
        newNode->next = head;
        head = newNode;
        return;
    }

    // 리스트 중간 삽입
    Node* current = head;
    Node* prev = nullptr;

    while (current != nullptr && current->data < word)
    {
        prev = current;
        current = current->next;
    }

    if (current != nullptr && current->data == word) // 데이터 있을 때 ++1
    {
        current->frequency++;
        delete newNode;
        return;
    }
    // 삽입
    prev->next = newNode;
    newNode->next = current;
}

void removeLeastFrequent(Node*& head)
{
    if (head == nullptr)
        return;

    // 가장 적은 빈도수를 찾는다
    Node* current = head;
    int minFrequency = current->frequency;

    while (current != nullptr)
    {
        if (current->frequency < minFrequency)
        {
            minFrequency = current->frequency;
        }
        current = current->next;
    }

    // 최소 빈도수를 가진 단어를 제거한다
    current = head;
    Node* prev = nullptr;

    while (current != nullptr)
    {
        if (current->frequency == minFrequency)
        {
            if (prev == nullptr) // 첫 번째 노드 제거
            {
                head = current->next;
                delete current;
                current = head;
            }
            else
            {
                prev->next = current->next;
                delete current;
                current = prev->next;
            }
        }
        else
        {
            prev = current;
            current = current->next;
        }
    }
}

void printlist(Node* head)
{
    Node* current = head;
    int totalWord = 0;

    while (current != nullptr)
    {
        cout << current->data << ": " << current->frequency << endl;
        totalWord++;
        current = current->next;
    }
    cout << "Total unique words: " << totalWord << endl;
}

int main()
{
    ifstream infile("harry.txt");
    string word;
    Node* head = nullptr;

    while (infile >> word)
    {
        addword(head, word);
    }

    // 가장 적은 빈도수의 단어 제거
    removeLeastFrequent(head);
    printlist(head);

    return 0;
}

문제 6: 사용자가 지정한 범위의 빈도수를 가진 단어만 출력하기

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

struct Node
{
    string data;
    int frequency;
    Node* next;
};

void addword(Node*& head, const string& word)
{
    Node* newNode = new Node{ word, 1, nullptr };

    if (head == nullptr)
    {
        head = newNode;
        return;
    }

    // 리스트 처음 삽입
    if (word < head->data)
    {
        newNode->next = head;
        head = newNode;
        return;
    }

    // 리스트 중간 삽입
    Node* current = head;
    Node* prev = nullptr;

    while (current != nullptr && current->data < word)
    {
        prev = current;
        current = current->next;
    }

    if (current != nullptr && current->data == word) // 데이터 있을 때 ++1
    {
        current->frequency++;
        delete newNode;
        return;
    }
    // 삽입
    prev->next = newNode;
    newNode->next = current;
}

void printInRange(Node* head, int minFreq, int maxFreq)
{
    Node* current = head;
    int totalWord = 0;

    while (current != nullptr)
    {
        if (current->frequency >= minFreq && current->frequency <= maxFreq)
        {
            cout << current->data << ": " << current->frequency << endl;
            totalWord++;
        }
        current = current->next;
    }
    cout << "Total words in range: " << totalWord << endl;
}

int main()
{
    ifstream infile("harry.txt");
    string word;
    Node* head = nullptr;

    while (infile >> word)
    {
        addword(head, word);
    }

    int minFreq, maxFreq;
    cout << "Enter the minimum frequency: ";
    cin >> minFreq;
    cout << "Enter the maximum frequency: ";
    cin >> maxFreq;

    printInRange(head, minFreq, maxFreq);

    return 0;
}

자료구조3번

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Term
{
	int coef;
	int expo;
	Term* next = nullptr;

	Term() {}

	Term(int c, int e) : coef(c), expo(e) {}
	Term(int c, int e, Term* p) : coef(c), expo(e), next(p) {}
};

struct Polynomial
{
	char name;
	Term* first = nullptr;
	int size = 0;
	Polynomial() {}
	Polynomial(char name) : name(name) {}
};

vector<Polynomial> polys;
void add_term(Polynomial& poly, int c, int e);
void print_term(Term* pTerm);
void print_poly(Polynomial& p);
void handle_print(char name);
vector<Polynomial>::iterator find_poly(char name);
int calc_term(Term* term, int x);
int calc_poly(Polynomial poly, int x);
void handle_calc(char name, int x);
void handle_add(char name, int c, int e);
void insert_polynomial(Polynomial p);
void clear_poly(Polynomial& p);
void add_polys(Polynomial& result, Polynomial& p1, Polynomial& p2);
void multiply_polys(Polynomial& result, Polynomial& p1, Polynomial& p2);
void handle_addpoly(char result_name, char name1, char name2);
void handle_multiplypoly(char result_name, char name1, char name2);
void handle_delete(char name);
void handle_copy(char new_name, char name);
void handle_differentiate(char name);
void handle_compare(char name1, char name2);
void handle_remove_constant(char name);
void handle_get_term(char name, int expo);
void handle_dividepoly(char result_name, char name1, char name2);

int main()
{
	string command, arg1, arg2, arg3;
	while (1)
	{
		cout << "$ ";
		cin >> command;
		if (command == "print")
		{
			cin >> arg1;
			handle_print(arg1[0]);
		}
		else if (command == "calc")
		{
			cin >> arg1 >> arg2;
			handle_calc(arg1[0], stoi(arg2));
		}
		else if (command == "define")
		{
			cin >> arg1;
			Polynomial pol(arg1[0]);
			insert_polynomial(pol);
		}
		else if (command == "add")
		{
			cin >> arg1 >> arg2 >> arg3;
			handle_add(arg1[0], stoi(arg2), stoi(arg3));
		}
		else if (command == "addpoly")
		{
			cin >> arg1 >> arg2 >> arg3;
			handle_addpoly(arg1[0], arg2[0], arg3[0]);
		}
		else if (command == "multiplypoly")
		{
			cin >> arg1 >> arg2 >> arg3;
			handle_multiplypoly(arg1[0], arg2[0], arg3[0]);
		}
		else if (command == "delete")
		{
			cin >> arg1;
			handle_delete(arg1[0]);
		}
		else if (command == "copy")
		{
			cin >> arg1 >> arg2;
			handle_copy(arg1[0], arg2[0]);
		}
		else if (command == "differentiate")
		{
			cin >> arg1;
			handle_differentiate(arg1[0]);
		}
		else if (command == "compare")
		{
			cin >> arg1 >> arg2;
			handle_compare(arg1[0], arg2[0]);
		}
		else if (command == "remove_constant")
		{
			cin >> arg1;
			handle_remove_constant(arg1[0]);
		}
		else if (command == "get_term")
		{
			cin >> arg1 >> arg2;
			handle_get_term(arg1[0], stoi(arg2));
		}
		else if (command == "dividepoly")
		{
			cin >> arg1 >> arg2 >> arg3;
			handle_dividepoly(arg1[0], arg2[0], arg3[0]);
		}
		else if (command == "exit")
			break;
	}
}

void add_term(Polynomial& poly, int c, int e)
{
	if (c == 0)
		return;
	Term* p = poly.first, * q = nullptr;
	while (p != nullptr && p->expo > e)
	{
		q = p;
		p = p->next;
	}
	if (p != nullptr && p->expo == e)
	{
		p->coef += c;
		if (p->coef == 0)
		{
			if (q == nullptr)
				poly.first = p->next;
			else
				q->next = p->next;
			poly.size--;
			delete p;
		}
		return;
	}
	if (q == nullptr)
		poly.first = new Term(c, e, poly.first);
	else
		q->next = new Term(c, e, p);
	poly.size++;
}

void print_term(Term* pTerm, bool isFirst = false)
{
	if (!isFirst && pTerm->coef > 0)
		cout << "+";
	if (pTerm->expo == 0)
		cout << pTerm->coef;
	else if (pTerm->expo == 1)
		cout << pTerm->coef << "x";
	else
		cout << pTerm->coef << "x^" << pTerm->expo;
}

void print_poly(Polynomial& p)
{
	cout << p.name << " = ";
	Term* t = p.first;
	bool isFirst = true;
	while (t != nullptr)
	{
		print_term(t, isFirst);
		isFirst = false;
		t = t->next;
	}
	cout << endl;
}
void handle_print(char name)
{
	auto it = find_poly(name);
	if (it == polys.end())
		cout << "No such polynomial exists." << endl;
	else
		print_poly(*it);
}

vector<Polynomial>::iterator find_poly(char name)
{
	for (auto it = polys.begin(); it != polys.end(); it++)
	{
		if (it->name == name)
			return it;
	}
	return polys.end();
}

int calc_term(Term* term, int x)
{
	int result = term->coef;
	for (int i = 0; i < term->expo; i++)
	{
		result *= x;
	}
	return result;
}

int calc_poly(Polynomial poly, int x)
{
	int result = 0;
	Term* t = poly.first;
	while (t != nullptr)
	{
		result += calc_term(t, x);
		t = t->next;
	}
	return result;
}

void handle_calc(char name, int x)
{
	auto it = find_poly(name);
	if (it == polys.end())
		cout << "No such polynomial exists." << endl;
	else
		cout << calc_poly(*it, x) << endl;
}

void clear_poly(Polynomial& p)
{
	Term* t = p.first, * tmp;
	while (t != nullptr)
	{
		tmp = t;
		t = t->next;
		delete tmp;
	}
	p.first = nullptr;
}

void insert_polynomial(Polynomial p)
{
	auto it = find_poly(p.name);
	if (it == polys.end())
	{
		polys.push_back(p);
	}
	else
	{
		clear_poly(*it);
		*it = p;
	}
}

// 다항식에 항 추가
void handle_add(char name, int c, int e)
{
	auto it = find_poly(name);
	if (it == polys.end())
	{
		cout << "No such polynomial exists." << endl;
		return;
	}
	add_term(*it, c, e);
}

// 다항식 더하기
void add_polys(Polynomial& result, Polynomial& p1, Polynomial& p2)
{
	Term* t1 = p1.first;
	Term* t2 = p2.first;

	while (t1 != nullptr)
	{
		add_term(result, t1->coef, t1->expo);
		t1 = t1->next;
	}

	while (t2 != nullptr)
	{
		add_term(result, t2->coef, t2->expo);
		t2 = t2->next;
	}
}

// 다항식 곱하기
void multiply_polys(Polynomial& result, Polynomial& p1, Polynomial& p2)
{
	Term* t1 = p1.first;

	while (t1 != nullptr)
	{
		Term* t2 = p2.first;
		while (t2 != nullptr)
		{
			add_term(result, t1->coef * t2->coef, t1->expo + t2->expo);
			t2 = t2->next;
		}
		t1 = t1->next;
	}
}

// 두 다항식 더하기
void handle_addpoly(char result_name, char name1, char name2)
{
	auto it1 = find_poly(name1);
	auto it2 = find_poly(name2);

	if (it1 == polys.end() || it2 == polys.end())
	{
		return;
	}

	Polynomial result(result_name);
	add_polys(result, *it1, *it2);
	insert_polynomial(result);
}

// 두 다항식 곱하기
void handle_multiplypoly(char result_name, char name1, char name2)
{
	auto it1 = find_poly(name1);
	auto it2 = find_poly(name2);

	if (it1 == polys.end() || it2 == polys.end())
	{
		return;
	}

	Polynomial result(result_name);
	multiply_polys(result, *it1, *it2);
	insert_polynomial(result);
}

// 다항식 삭제
void handle_delete(char name)
{
	auto it = find_poly(name);
	if (it == polys.end())
	{
		cout << "No such polynomial exists." << endl;
		return;
	}
	clear_poly(*it);
	polys.erase(it);
	cout << "Polynomial " << name << " deleted." << endl;
}

// 다항식 복사
void handle_copy(char new_name, char name)
{
	auto it = find_poly(name);
	if (it == polys.end())
	{
		cout << "No such polynomial exists." << endl;
		return;
	}

	Polynomial new_poly(new_name);
	Term* t = it->first;
	while (t != nullptr)
	{
		add_term(new_poly, t->coef, t->expo);
		t = t->next;
	}

	insert_polynomial(new_poly);
}

// 다항식 미분
void handle_differentiate(char name)
{
	auto it = find_poly(name);
	if (it == polys.end())
	{
		cout << "No such polynomial exists." << endl;
		return;
	}

	Term* t = it->first;
	while (t != nullptr)
	{
		if (t->expo == 0)
		{
			t->coef = 0;
		}
		else
		{
			t->coef *= t->expo;
			t->expo--;
		}
		t = t->next;
	}
	cout << "Polynomial " << name << " differentiated." << endl;
}

// 두 다항식 비교
void handle_compare(char name1, char name2)
{
	auto it1 = find_poly(name1);
	auto it2 = find_poly(name2);

	if (it1 == polys.end() || it2 == polys.end())
	{
		cout << "One or both polynomials do not exist." << endl;
		return;
	}

	Term* t1 = it1->first;
	Term* t2 = it2->first;

	while (t1 != nullptr && t2 != nullptr)
	{
		if (t1->coef != t2->coef || t1->expo != t2->expo)
		{
			cout << "Polynomials are not equal." << endl;
			return;
		}
		t1 = t1->next;
		t2 = t2->next;
	}

	if (t1 == nullptr && t2 == nullptr)
	{
		cout << "Polynomials are equal." << endl;
	}
	else
	{
		cout << "Polynomials are not equal." << endl;
	}
}

// 상수항 제거
void handle_remove_constant(char name)
{
	auto it = find_poly(name);
	if (it == polys.end())
	{
		cout << "No such polynomial exists." << endl;
		return;
	}

	Term* t = it->first;
	Term* prev = nullptr;

	while (t != nullptr)
	{
		if (t->expo == 0)
		{
			if (prev == nullptr)
			{
				it->first = t->next;
				delete t;
				t = it->first;
			}
			else
			{
				prev->next = t->next;
				delete t;
				t = prev->next;
			}
		}
		else
		{
			prev = t;
			t = t->next;
		}
	}
	cout << "Constant terms removed from polynomial " << name << "." << endl;
}

// 특정 차수 항만 출력
void handle_get_term(char name, int expo)
{
	auto it = find_poly(name);
	if (it == polys.end())
	{
		cout << "No such polynomial exists." << endl;
		return;
	}

	Term* t = it->first;
	while (t != nullptr)
	{
		if (t->expo == expo)
		{
			print_term(t, true);
			cout << endl;
			return;
		}
		t = t->next;
	}

	cout << "No such term exists." << endl;
}

// 다항식 나누기 (몫과 나머지)
void handle_dividepoly(char result_name, char name1, char name2)
{
	auto it1 = find_poly(name1);
	auto it2 = find_poly(name2);

	if (it1 == polys.end() || it2 == polys.end())
	{
		cout << "One or both polynomials do not exist." << endl;
		return;
	}

	Polynomial result(result_name);
	Polynomial remainder = *it1;

	Term* t2 = it2->first;

	if (t2 == nullptr || t2->coef == 0)
	{
		cout << "Cannot divide by zero polynomial." << endl;
		return;
	}

	while (remainder.first != nullptr && remainder.first->expo >= t2->expo)
	{
		int coef = remainder.first->coef / t2->coef;
		int expo = remainder.first->expo - t2->expo;

		add_term(result, coef, expo);

		Polynomial temp;
		add_term(temp, coef, expo);
		Polynomial product;
		multiply_polys(product, temp, *it2);

		add_polys(remainder, remainder, product);
		clear_poly(product);
	}

	insert_polynomial(result);
	cout << "Polynomial division result stored as " << result_name << endl;
}

추가된 기능 설명:

다항식 삭제: 특정 다항식을 삭제합니다.
다항식 복사: 기존 다항식을 다른 이름으로 복사합니다.
다항식 미분: 다항식의 각 항을 미분합니다.
다항식 비교: 두 다항식을 비교하여 동일한지 확인합니다.
상수항 제거: 차수가 0인 상수항을 다항식에서 제거합니다.
특정 차수 항만 출력: 사용자가 원하는 차수에 해당하는 항을 출력합니다.
다항식 나누기: 두 다항식을 나누어 몫과 나머지를 구할 수 있습니다.

1. 다항식 생성 및 저장 (define)

설명: 새로운 다항식을 생성하여 polys 벡터에 저장합니다. 다항식은 이름을 기준으로 관리됩니다.
명령어: define [name]
예시: define A → 이름이 A인 새로운 다항식 생성.

2. 다항식에 항 추가 (add)

설명: 특정 다항식에 새로운 항을 추가합니다. 같은 차수의 항이 이미 존재하면 계수만 더해집니다.
명령어: add [name] [coef] [expo]
예시: add A 3 2 → A 다항식에 3x23x^2 항 추가.

3. 다항식 출력 (print)

설명: 다항식의 이름을 입력받아 해당 다항식을 출력합니다.
명령어: print [name]
예시: print A → A 다항식 출력.

4. 다항식 계산 (calc)

설명: 입력된 xx 값에 대해 다항식을 계산하여 결과를 출력합니다.
명령어: calc [name] [x]
예시: calc A 2 → A(2)A(2) 값 출력.

5. 다항식 더하기 (addpoly)

설명: 두 다항식을 더하여 결과를 새로운 이름으로 저장합니다.
명령어: addpoly [result_name] [name1] [name2]
예시: addpoly C A B → A와 B를 더한 결과를 C에 저장.

6. 다항식 곱하기 (multiplypoly)

설명: 두 다항식을 곱하여 결과를 새로운 이름으로 저장합니다.
명령어: multiplypoly [result_name] [name1] [name2]
예시: multiplypoly D A B → A와 B를 곱한 결과를 D에 저장.

7. 다항식 삭제 (delete)

설명: 특정 다항식을 삭제합니다. 다항식을 삭제하면 해당 다항식의 모든 항이 메모리에서 제거됩니다.
명령어: delete [name]
예시: delete A → A 다항식 삭제.

8. 다항식 복사 (copy)

설명: 기존의 다항식을 다른 이름으로 복사하여 새로운 다항식을 만듭니다.
명령어: copy [new_name] [name]
예시: copy B A → A를 복사하여 B에 저장.

9. 다항식 미분 (differentiate)

설명: 다항식을 미분한 결과를 기존 다항식에 저장합니다. 각 항의 차수는 1씩 줄어들고, 계수는 차수에 곱해집니다.
명령어: differentiate [name]
예시: differentiate A → A 다항식을 미분.

10. 두 다항식 비교 (compare)

설명: 두 다항식을 비교하여 동일한지 여부를 확인합니다. 두 다항식이 동일하면 "Polynomials are equal", 다르면 "Polynomials are not equal"을 출력합니다.
명령어: compare [name1] [name2]
예시: compare A B → A와 B가 같은지 비교.

11. 다항식의 상수항 제거 (remove_constant)

설명: 차수가 0인 상수항을 다항식에서 제거합니다.
명령어: remove_constant [name]
예시: remove_constant A → A 다항식에서 상수항 제거.

12. 특정 차수의 항 출력 (get_term)

설명: 다항식에서 특정 차수의 항만 출력합니다. 해당 차수의 항이 없으면 "No such term exists."를 출력합니다.
명령어: get_term [name] [expo]
예시: get_term A 2 → A 다항식에서 x2x^2 항 출력.

13. 다항식 나누기 (dividepoly)

설명: 두 다항식을 나누어 몫을 새로운 다항식으로 저장합니다. 나눗셈 후 나머지는 계산되지 않고, 몫만 계산됩니다.
명령어: dividepoly [result_name] [name1] [name2]
예시: dividepoly E A B → A를 B로 나눈 몫을 E에 저장.

자료구조 4번

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

using namespace std;

struct Node
{
	string data;
	Node* prev, * next;
};

void ordered_insert(string item);
void remove_dup();
void print_list_twice();

Node* head = nullptr, * tail = nullptr;

int main()
{
	int n;
	string word;
	cin >> n;
	for(int i=0; i<n; i ++)
	{
		cin >> word;
		ordered_insert(word);
	}

	print_list_twice();
	remove_dup();
	print_list_twice();
	return 0;
}

void ordered_insert(string item)
{
	Node* new_node = new Node();
	new_node->data = item;
	new_node->prev = new_node->next = nullptr;

	if(head == nullptr) //리스트가 비어있을 때 
	{
		head = tail = new_node;
		return;
	}

	Node* current = head; 
	while(current!=nullptr && current->data < item) //current의 노드가 데이터 item보다 작을 때 
	{
		current = current->next;
	}

	if (current == head) //삽입 구간이 맨앞에 위치할 때
	{
		new_node->next = head;
		head->prev = new_node;
		head = new_node;
	}
	else if(current == nullptr) //맨뒤에 위치할 때
	{
		tail->next = new_node;
		new_node->prev = tail;
		tail = new_node;
	}
	else //리스트 중간 삽입
	{
		new_node->next = current;
		new_node->prev = current->prev;
		current->prev->next = new_node;
		current->prev = new_node;
	}

}

void remove_dup()
{
	if (head == nullptr) 
		return;

	Node* current = head;

	while(current != nullptr)
	{
		Node* runner = current->next;
		while (runner != nullptr && runner->data == current->data)
		{
			Node* delete_node = runner;
			runner = runner->next;

			if (delete_node->next != nullptr)
			{
				delete_node->next->prev = delete_node->prev;
			}
			else
				tail = delete_node->prev;

			delete_node->prev->next = delete_node->next;
			delete delete_node;
		}
		current = current->next;
	}
}

void print_list_twice()
{
	Node* p = head;
	while(p != nullptr)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;

	Node* q = tail;
	while(q != nullptr)
	{
		cout << q->data << " ";
		q = q->prev;


	}
	cout << endl;
}

문제 1: 문자열 길이를 기준으로 정렬하여 삽입

문제 설명: 문자열을 사전순이 아닌 길이 순서대로 삽입하도록 코드를 수정하세요. 문자열 길이가 같을 경우, 사전순으로 정렬합니다.

힌트: 기존의 ordered_insert 함수를 수정하여, item의 길이를 기준으로 먼저 비교하고, 길이가 같다면 사전순으로 비교해야 합니다.

#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string data;
    Node* prev, * next;
};

void ordered_insert_by_length(string item);
void print_list_twice();

Node* head = nullptr, * tail = nullptr;

int main()
{
    int n;
    string word;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> word;
        ordered_insert_by_length(word);
    }

    print_list_twice();
    return 0;
}

void ordered_insert_by_length(string item)
{
    Node* new_node = new Node();
    new_node->data = item;
    new_node->prev = new_node->next = nullptr;

    if (head == nullptr) // 리스트가 비어 있을 때
    {
        head = tail = new_node;
        return;
    }

    Node* current = head;
    while (current != nullptr && 
          (current->data.length() < item.length() || 
           (current->data.length() == item.length() && current->data < item)))
    {
        current = current->next;
    }

    if (current == head) // 맨 앞에 삽입
    {
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    }
    else if (current == nullptr) // 맨 뒤에 삽입
    {
        tail->next = new_node;
        new_node->prev = tail;
        tail = new_node;
    }
    else // 중간 삽입
    {
        new_node->next = current;
        new_node->prev = current->prev;
        current->prev->next = new_node;
        current->prev = new_node;
    }
}

void print_list_twice()
{
    Node* p = head;
    while (p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    Node* q = tail;
    while (q != nullptr)
    {
        cout << q->data << " ";
        q = q->prev;
    }
    cout << endl;
}

문제 2: 사전순으로 역순 정렬하여 삽입

문제 설명: 문자열을 오름차순이 아닌 내림차순으로 정렬하여 삽입하는 코드를 작성하세요. 즉, 알파벳 순서에서 뒤에 오는 문자열이 먼저 삽입되어야 합니다.

힌트: 기존의 ordered_insert 함수에서 문자열의 사전순 비교를 반대로 바꾸면 됩니다.

#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string data;
    Node* prev, * next;
};

void ordered_insert_reverse(string item);
void print_list_twice();

Node* head = nullptr, * tail = nullptr;

int main()
{
    int n;
    string word;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> word;
        ordered_insert_reverse(word);
    }

    print_list_twice();
    return 0;
}

void ordered_insert_reverse(string item)
{
    Node* new_node = new Node();
    new_node->data = item;
    new_node->prev = new_node->next = nullptr;

    if (head == nullptr) // 리스트가 비어 있을 때
    {
        head = tail = new_node;
        return;
    }

    Node* current = head;
    while (current != nullptr && current->data > item) // 내림차순 비교
    {
        current = current->next;
    }

    if (current == head) // 맨 앞에 삽입
    {
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    }
    else if (current == nullptr) // 맨 뒤에 삽입
    {
        tail->next = new_node;
        new_node->prev = tail;
        tail = new_node;
    }
    else // 중간 삽입
    {
        new_node->next = current;
        new_node->prev = current->prev;
        current->prev->next = new_node;
        current->prev = new_node;
    }
}

void print_list_twice()
{
    Node* p = head;
    while (p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    Node* q = tail;
    while (q != nullptr)
    {
        cout << q->data << " ";
        q = q->prev;
    }
    cout << endl;
}

문제 3: 특정 위치에 삽입

문제 설명: 입력받은 정수 위치에 따라 문자열을 삽입하는 코드를 작성하세요. 0번째 위치는 head이고, n번째 위치는 tail입니다. 예를 들어, 1번째 위치에 삽입하면 head의 바로 뒤에 삽입됩니다.

힌트: 새로운 매개변수로 위치를 받아서 리스트를 순차적으로 탐색하며 해당 위치에 삽입하는 기능을 추가해야 합니다.

#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string data;
    Node* prev, * next;
};

void insert_at_position(string item, int position);
void print_list_twice();

Node* head = nullptr, * tail = nullptr;

int main()
{
    int n, pos;
    string word;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> word >> pos;
        insert_at_position(word, pos);
    }

    print_list_twice();
    return 0;
}

void insert_at_position(string item, int position)
{
    Node* new_node = new Node();
    new_node->data = item;
    new_node->prev = new_node->next = nullptr;

    if (position == 0) // 첫 번째 위치에 삽입
    {
        if (head == nullptr) // 리스트가 비어 있을 때
        {
            head = tail = new_node;
        }
        else
        {
            new_node->next = head;
            head->prev = new_node;
            head = new_node;
        }
        return;
    }

    Node* current = head;
    int index = 0;

    while (current != nullptr && index < position)
    {
        current = current->next;
        index++;
    }

    if (current == nullptr) // 끝에 삽입 (position >= 리스트 길이)
    {
        tail->next = new_node;
        new_node->prev = tail;
        tail = new_node;
    }
    else // 중간에 삽입
    {
        new_node->next = current;
        new_node->prev = current->prev;
        current->prev->next = new_node;
        current->prev = new_node;
    }
}

void print_list_twice()
{
    Node* p = head;
    while (p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    Node* q = tail;
    while (q != nullptr)
    {
        cout << q->data << " ";
        q = q->prev;
    }
    cout << endl;
}

문제 4: 리스트에서 모든 문자열의 길이 출력

문제 설명: 리스트에 있는 모든 문자열의 길이를 출력하는 코드를 작성하세요. 순방향과 역방향 모두 출력되어야 합니다.

힌트: 각 노드의 문자열 data의 길이를 data.length()로 구할 수 있습니다.

#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string data;
    Node* prev, * next;
};

void ordered_insert(string item);
void print_length_twice();

Node* head = nullptr, * tail = nullptr;

int main()
{
    int n;
    string word;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> word;
        ordered_insert(word);
    }

    print_length_twice();
    return 0;
}

void ordered_insert(string item)
{
    Node* new_node = new Node();
    new_node->data = item;
    new_node->prev = new_node->next = nullptr;

    if (head == nullptr) // 리스트가 비어 있을 때
    {
        head = tail = new_node;
        return;
    }

    Node* current = head;
    while (current != nullptr && current->data < item)
    {
        current = current->next;
    }

    if (current == head) // 맨 앞에 삽입
    {
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    }
    else if (current == nullptr) // 맨 뒤에 삽입
    {
        tail->next = new_node;
        new_node->prev = tail;
        tail = new_node;
    }
    else // 중간 삽입
    {
        new_node->next = current;
        new_node->prev = current->prev;
        current->prev->next = new_node;
        current->prev = new_node;
    }
}

void print_length_twice()
{
    Node* p = head;
    while (p != nullptr)
    {
        cout << p->data.length() << " ";
        p = p->next;
    }
    cout << endl;

    Node* q = tail;
    while (q != nullptr)
    {
        cout << q->data.length() << " ";
        q = q->prev;
    }
    cout << endl;
}

문제 5: 중복 항목의 수 세기

문제 설명: 리스트에서 중복된 항목이 몇 번 등장했는지 세는 함수를 작성하세요.

힌트: remove_dup 함수의 구조를 응용하여, 중복된 항목이 등장할 때마다 카운트를 세면 됩니다.

#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string data;
    Node* prev, * next;
};

void ordered_insert(string item);
int count_duplicates();
void print_list_twice();

Node* head = nullptr, * tail = nullptr;

int main()
{
    int n;
    string word;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> word;
        ordered_insert(word);
    }

    print_list_twice();
    cout << "Total duplicates: " << count_duplicates() << endl;
    return 0;
}

void ordered_insert(string item)
{
    Node* new_node = new Node();
    new_node->data = item;
    new_node->prev = new_node->next = nullptr;

    if (head == nullptr) // 리스트가 비어 있을 때
    {
        head = tail = new_node;
        return;
    }

    Node* current = head;
    while (current != nullptr && current->data < item)
    {
        current = current->next;
    }

    if (current == head) // 맨 앞에 삽입
    {
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    }
    else if (current == nullptr) // 맨 뒤에 삽입
    {
        tail->next = new_node;
        new_node->prev = tail;
        tail = new_node;
    }
    else // 중간 삽입
    {
        new_node->next = current;
        new_node->prev = current->prev;
        current->prev->next = new_node;
        current->prev = new_node;
    }
}

int count_duplicates()
{
    if (head == nullptr)
        return 0;

    int count = 0;
    Node* current = head;

    while (current != nullptr)
    {
        Node* runner = current->next;
        while (runner != nullptr && runner->data == current->data)
        {
            count++;
            runner = runner->next;
        }
        current = current->next;
    }
    return count;
}

void print_list_twice()
{
    Node* p = head;
    while (p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    Node* q = tail;
    while (q != nullptr)
    {
        cout << q->data << " ";
        q = q->prev;
    }
    cout << endl;
}

'IT 프로그래밍 > 자료구조' 카테고리의 다른 글

자료구조 그룹액티비티 6 (2)	2024.12.15
자료구조 [예상] (0)	2024.10.23
[자료구조] 노래찾기 (2)	2024.10.23
[자료구조] 과제2 (2)	2024.10.23
[자료구조] 그룹 액티비티 4 (0)	2024.10.23

현재글자료구조 과제3

기술 블로그

따배시, 따배시 강의, 티스토리챌린지, 거듭제곱 구하는 법, 프로그래밍 예제, C++, 백준 10813, 녹색혁명, 빈곤의 원인, string 설명, x5x6, 오블완, 백준2284번, 빈곤이란, 따배시 강의 요약, 말레이시아 경제, 빈곤 정의, strtok기능, 빈곤이란 무엇인가?, 빈곤의 사회학적 정의,

기술 블로그