연결리스트 삽입, 삭제, 출력 Linked List insert delete print 구현하기

연결리스트 Linked List 

---

성균관대학교 소프트웨어학과 조대호 교수님의 2020년도 2학기 알고리즘 수업을 들으며 수행한 과제입니다. 

• problem 

Write functions which perform according to the following descriptions.

The input to each function is a linked list of integers.

 

a) insert - Inserts an integer x to the front of a linked list.

e.g.) insert(lst, x) where lst is a pointer to a linked list and x is an integer.

 

b) delete - Deletes 2 nd last integer x in the linked list. e.g.) delete(lst)

 

c) print - prints the content of a linked list in three lines as described below

• 1 st line : 1 st third of the list
• 2 nd line : 2 nd third of the list
• 3 rd line 3 rd third of the list 

e.g.) print(1st)

• input and output conditions 

1) Construct the linked list from a set of integers stored in an array using the insert function in a). Where the length of the array is 60 and should be filled by rand()%1000 (execute srand(time(NULL)) first). (Avoid same values when generating the values randomly.)

 

2) Then randomly select an integer from the array and delete this integer from the linked list using delete function in b).

 

3) Print the content of the linked list using print function in c). 4) Repeat 2) and 3) two more times.

• source code

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct node {
	char item;
	struct node* prev;
	struct node* next;
}Node;

int size;

void initList(Node *h, Node *t) {
	h->prev = NULL;
	h->next = t;
	t->prev = h;
	t->next = NULL;
	size = 0; // 노드 개수 
}

int insert(Node *h, int e){
	Node* newnode = (Node*)malloc(sizeof(Node));
	newnode->item = e;
	newnode->next = h->next;
	newnode->prev = h;
	h->next->prev = newnode;
	h->next = newnode;
	size ++;

	return 0;
}

int print(Node *h){
	int i, j;

	for (j = 0; j < 3; j++) {
		printf("line %d : ", j);
		for (i = 0; i < size/3; i++) {
			if (h->next == NULL)break;
			else {
				printf(" %d", h->next->item);
				h = h->next;
			}
		}
		printf("\n");
	}	
	return 0;
}

int delete(Node* h, int k) {
	int i;
	Node* temp = h->next;
	

	while (temp->item != k) {
		if (temp->next == NULL) {
			printf("There is no %d in the list\n", k);
			return 0;
		}
		else {
			temp = temp->next;
		}
	}
	printf("삭제할 노드 : %d\n", temp->item);

	
	(temp->prev)->next = temp->next;
	(temp->next)->prev = temp->prev;

	free(temp);

	size--;
	return 0;
}

int main() {
	int i;
	int item, k;
	int op;

	Node* h = (Node*)malloc(sizeof(Node));
	Node* t = (Node*)malloc(sizeof(Node));

	initList(h, t);
	
	srand(time(NULL));
	for (i = 0; i < 60; i++) {
		item = rand() % 1000;
		insert(h, item);
	}

	print(h);
	printf("the number of nodes in the list : %d\n", size);

	printf("enter delete number among the list:");
	scanf("%d", &k); 
	
	delete(h, k);

	print(h);
	printf("the number of nodes in the list : %d\n", size);

	return 0;


}

• result

1. 가장 먼저 연결 리스트가 생성되고, 랜덤 값들로 채워집니다. 60개의 랜덤 값이 삽입되고, 3 줄로 연결리스트를 출력합니다.
2. 그리고 나서 사용자가 정수를 입력합니다.
   1. 입력받은 정수가 연결리스트에 없다면 프로그램은 'There is no * among the list' 라는 문자열을 출력합니다.
   2. 입력받은 정수가 연결리스트에 있다면 해당하는 값을 연결리스트에서 삭제합니다. 
3. 마지막으로 프로그램이 연결 리스트에 있는 모든 값과 그 개수를 출력합니다. 

• First trial 

-114를 입력하여 line 2의 끝에서 두번째에 있는 값이 삭제됩니다. 그래서 전체 연결리스트의 노드 개수가 60에서 59로 감소한 것을 확인할 수 있습니다. 

• Second trial 

연결리스트에 없는 값인 123123을 입력합니다. 그러자 There is no 123123 in the list 라는 문자열을 출력합니다. 

연결리스트에 없는 값이기 때문에 삭제가 일어나지 않고 노드 개수는 여전이 60개로 동일합니다. 

 

• Thris trial