[SOS CLASS] 자료구조기초 - 4차시

 

---

✅ 오늘의 진도 (2022/04/15)

1. 연결 자료구조와 연결 리스트의 이해

 

2. 단순 연결 리스트

- 단순 연결 리스트의 개념

- 단순 연결 리스트의 삽입과 삭제

- 단순 연결 리스트의 알고리즘

 

3. 원형 연결 리스트

 

4. 이중 연결 리스트

 

5. 연결 리스트의 응용 및 구현

---

 ✅ 연결 리스트 구조

---

✅ 단순 연결 리스트에서 원소 삽입

1. 삽입할 노드 준비 : 공백 노드를 가져와 포인터 변수 new가 가리키게 함

2. 새 노드의 데이터 필드 값 저장 : new의 데이터 필드에 "수"를 저장

3. 새 노드의 링크 필드 값 지정

4. 리스트의 앞 노드에 새 노드 연결

 

⚡ 단순 연결 리스트의 노드 삽입 알고리즘

---

✅ 단순 연결 리스트에서 원소 삭제

 

1. 앞 노드를 찾음

2. 앞 노드에 삭제할 노드의 링크 필드 값 저장 (월의 링크에 수의 링크 200 저장)

3. 삭제한 노드의 앞뒤 노드 연결

 

⚡ 단순 연결 리스트의 노드 삭제 알고리즘

---

✅ 원형 연결 리스트

⚡ 원형 연결 리스트의 첫 번째 노드 삽입 알고리즘

 

⚡ 원형 연결 리스트의 첫 번째 노드 삽입 알고리즘

 

⚡ 원형 연결 리스트의 노드 삭제 알고리즘

---

✅ 이중 연결 리스트

⚡ 이중 연결 리스트의 노드 구조와 구조체

 

⚡ 이중 원형 연결 리스트

 

⚡ 이중 연결 리스트에 노드 삽입 알고리즘

 

⚡ 이중 연결 리스트에 노드 삭제 알고리즘

 

---

✅ 연결 리스트의 응용 및 구현

⚡ 다항식 노드를 사용한 표현

ex) A(x) = 4x^3 + 3x^2 + 2 

 

⚡ 다항식 끝에 항 추가 알고리즘

 

---

 ✅ 관련 코드

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

typedef struct ListNode{
	char data[10];
	struct ListNode* link;
} ListNode;

typedef struct{
	listNode* head;
} linkedList_h;

linkedList_h* createLinkedList_h(void);
void freeLinkedList_h(linkedList_h*);
void addLastNode(linkedList_h*, char*);
void reverse(linkedList_h*);
void deleteLastNode(linkedList_h*);
void printList(linkedList_h*);


linkedList_h* createLinkedList_h(void){
	linkedList_h* L;
	L = (linkedList_h*)malloc(sizeof(linkedList_h));
	L -> head = NULL;
	return L;
}

void addLastNode(linkedList_h* L, char* x){
	listNode* newNode;
	listNode* p;
	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);
	newNode->link= NULL;
	if (L->head == NULL){
		L->head = newNode;
		return;
	}
	p = L->head;
	while (p->link != NULL) {
		p = p->link;
	}
	p ->link = newNode;
}

void reverse(linkedList_h * L){
	listNode* p;
	listNode* q;
	listNode* r;

	p = L->head;
	q=NULL;
	r=NULL;

	while (p!= NULL){
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}
	L->head = q;

}

void deleteLastNode(linkedList_h * L){
	listNode* previous;
	listNode* current;
	if (L->head == NULL) return;
	if (L->head->link == NULL) {
		free(L->head);
		L->head = NULL;
		return;
	}
	else {
		previous = L->head;
		current = L->head->link;
		while(current ->link != NULL){
			previous = current;
			current = current->link;
		}
	free(current);
	previous->link = NULL;
	}
}

void freeLinkedList_h(linkedList_h* L){
	listNode* p;
	while(L->head != NULL){
		p = L->head;
		L->head = L->head->link;
		free(p);
		p=NULL;
	}
}


void printList(linkedList_h* L){
	listNode* p;
	printf("L = (");
	p= L->head;
	while(p != NULL){
		printf("%s", p->data);
		p = p->link;
		if(p != NULL){
			printf(", ");
		}
	}
	printf(") \n");
}


int main(){
	linkedList_h* L;
	L = createLinkedList_h();
	printf("(1) 공백리스트 생성하기! \n");
	printList(L); getchar();

	printf("(2) 리스트에 3개의 노드 추가하기! \n");
	addLastNode(L, "월");
	addLastNode(L, "수");
	addLastNode(L, "금");	
	printList(L);  getchar();

	printf("(3) 리스트 마지막에 노드 한개 추가하기! \n");
	addLastNode(L, "일");	
	printList(L); getchar();

	printf("(4) 마지막 노드 삭제하기! \n");
	deleteLastNode(L);
	printList(L);  getchar();

	printf("(5) 리스트 원소를 역순으로 변환하기! \n");
	reverse(L);	
	printList(L);  getchar();

	printf("(6) 리스트 공간을 해제하여, 공백리스트 상태로 만들기! \n");
	freeLinkedList_h(L);
	printList(L);

	getchar();
	return 0;
}

 

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

typedef struct ListNode{
	float coef;
	int expo;
	struct ListNode* link;
} ListNode;

typedef struct ListHead{
	ListNode* head;
} ListHead;


ListHead* createLinkedList(void)
{
	ListHead* L;
	L = (ListHead *)malloc(sizeof(ListHead));
	L->head = NULL;
	return L;
}

void addLastNode(ListHead* L, float coef, int expo)
{
	ListNode* newNode;
	ListNode* p;
	newNode = (ListNode *)malloc(sizeof(ListNode));
	newNode->coef = coef;
	newNode->expo = expo;
	newNode->link = NULL;
	if(L->head == NULL){
		L->head = newNode;
		return;
	}
	else {
		p = L->head;
		while(p->link != NULL) {
			p = p->link;
		}
		p->link = newNode;
	}
}

void addPoly(ListHead* A, ListHead* B, ListHead* C)
{
	ListNode* pA = A->head;
	ListNode* pB = B->head;
	float sum; 

	while(pA && pB){
		if(pA->expo == pB->expo){
			sum = pA->coef + pB->coef;
			addLastNode(C, sum, pA->expo);
			pA=pA->link;   pB=pB->link;
		}
		else if(pA->expo > pB->expo){			
			addLastNode(C, pA->coef, pA->expo);
			pA=pA->link; 
		}
		else {			
			addLastNode(C, pB->coef, pB->expo);
			pB=pB->link; 
		}
	} 

	for( ; pA!=NULL; pA=pA->link)
		addLastNode(C, pA->coef, pA->expo);

	for( ; pB!=NULL; pB=pB->link)
		addLastNode(C, pB->coef, pB->expo);
}

void printPoly(ListHead* L)
{
	ListNode* p = L->head;
	for(;p;p=p->link){
		printf("%3.0fx^%d", p->coef, p->expo);
	}
}

void main(void){
	ListHead *A, *B, *C;

	A = createLinkedList();
	B = createLinkedList();
	C = createLinkedList();

	addLastNode(A, 4,3);
	addLastNode(A, 3,2);
	addLastNode(A, 5,1);
	printf("\n A(x)=");
	printPoly(A);

	addLastNode(B, 3,4);
	addLastNode(B, 1,3);
	addLastNode(B, 2,1);
	addLastNode(B, 1,0);
	printf("\n B(x)=");
	printPoly(B);

	addPoly(A, B, C);
	printf("\n C(x)=");
	printPoly(C);

	getchar();
}

 

---

✅ 오늘의 과제

SOS CLASS 자료구조기초 - 4차시 과제.hwp

0.03MB