연결 리스트

• 리스트 자료구조

데이터 연산 설명

 

스택	int stact[100];
(10,30,40,20)	push(35);
y=pop();
…	삽입과 삭제가 한쪽 끝
큐	int queue[100];
(10,30,40,20)	insert(35);
y=delete();
…	삽입과 삭제가 양쪽 끝
리스트	int mylist[100];
(10,30,40,20)	intsert(45);
y=delete();	삽입과 삭제가 아무 곳에서나 일어난다.
(문제점)→ 데이터가 많으면 순서를 유지하기 위하여 데이터 이동이 많아진다.

 

동적 데이터의 관리

프로그램 실행 중 데이터가 이동을 많이 한다면?

• 데이터가 움직이지 않으면 검색을 빨리할 수 있다.
  • ex) 공룡에 대한 데이터 타입
• 데이터는 삽입 삭제 연산에 의하여 위치와 개수가 변한다
• 데이터가 변경되어 위치가 바뀌면 검색을 빨리 하기 위한 재배치를 해야한다

포인터 타입

💡 연결리스트는 기억장소의 임의의 구조체로 구현된 노드를 서로 연결하여 리스트를 만든다. 따라서 다음 데이터가 저장된 노드의 기억장소를 저장하는 값이 필요하다. 기억장소의 주소값을 저장하는 데이터 타입을 포인터 타입이라고 한다.

• 사용 예시

int x;
int *y;
int z;

x=10;
y=&x;
z=*y;   /*y가 가리키는 곳의 내용을 저장, z=x*/

int a[10]; /* 배열 변수 a는 주소값으로 처리*/ 

#include <stdio.h>

int main(){
int i, *pi;
float f. *pf;
pi=&i; // i의 주소값
pf=%f; //j의 주소값
*pi=1024;
*pf=(float)3.14;
printf("an integet =%d, a float=%f\\n", *pi,*pf);

의자 4개가 있고 사람이 4명을 앉음

#include <stdio.h>
#include <malloc.h>

int main(){
int *pi;
float  *pf;
pi=(int *)malloc(sizeof(int));
pf=(float * )**malloc**(sizeof(float)); /*메모리에서 주소값을 가져오고 정수형 포인터를 갖고 오고 싶다.
주소값이 1000이다 그러면 pi에 1000을 저장한다.
기억장소를 배정받는다.*/

*pi=1024;
*pf=(float)3.14;
printf("an integet =%d, a float=%f\\n", *pi,*pf);
**free(pi);**
free(pf); //기억장소를 반납함

의자가 2개가 있고 의자 2개를 빌려와서 4명이 앉음

의자가 작을 때도 작업을 시작할 수 있으며 무한정 의자를 빌릴 수 있다.

 

출력 : a float=3.14

 

연결리스트를 만들기 위한 구조체 선언

• 자기참조구조체
• 동적인 자료의 할당과 해지를 위한 자료구조

struct node{
int data; //data
struct node *link;}; //another node 주소
typedef struct node list_node; //타입으로 선언하면 편리

typedef list_node * list_ptr;

리스트 자료의 예

list_node item1, item2, item3;
ltem1.data=10;
ltem2.data=20;
ltem3.data=30;
	ltem1.link=item2.link=item3.link=NULL;//포인터 초기값

• 접지 형식으로 표현하여 연결 주소값 자체를 초기화한다.

리스트 연결 예

item1.link=&item2;
item2.link=&item3;

• 다음 리스트를 연결함

program example

• 정적 기억장소에 데이터 저장

**프로그램1(p19)

// 연결리스트 프로그램1(p19)

#include <stdio.h>

#include <malloc.h>

struct node {

	int data; // 데이터

	struct node *link; // 다른 데이터 주소(포인터)

};

typedef struct node list_node;

typedef list_node * list_ptr;

 

int main(void)

{

	list_node item1, item2, item3;

	item1.data = 10;

	item2.data = 20;

	item3.data = 30;

	item1.link = item2.link = item3.link = NULL; // 포인터 초기값

	item1.link = &item2; item2.link = &item3; // 노드 연결

	printf("%d %d %d\\n", item1.data, item2.data, item3.data);

}

• 동적 기억장소에 데이터 저장

#include <stdio.h>
#include <malloc.h>

struct node{
int data; //data
struct node *link;}; //another node 주소
typedef struct node list_node; //타입으로 선언하면 편리
typedef list_node * list_ptr;

int main(void){
list_prt first, second, third;
first=(list_prt)malloc(sizeof(list_node)); //합 영역에 할당
second=(list_prt)malloc(sizeof(list_node));
third=(list_prt)malloc(sizeof(list_node));

third->link=NULL;
first -> data=19; second-> data =20; third-> data =30;
first->link=second;
second->link=third;//노드 연결

printf(%d %d %d \\n", first->data, second->data, third->data);
}

단순 연결리스트

• 연결리스트의 가장 간단한 형태로 그냥 연결리스트라고 부른다
• 노드들을 연결한 형태이며 노드는 데이터부분과 링크 부분으로 구성된다
• 데이터 부분은 한 개 혹은 여러개의 속성을 저장할 수 있다
• 링크 부분은 다음노드의 주소값을 가리킨다
• 동적 기억 할당과 해제가 가능하다.

단순 연결리스트

<그림 참조 - 21페이지>

예제

• 단순 연결리스트 노드의 선언과 생성

struct node{ int data;struct node *link;};
typedef struct node list_node;
typedef list_node * list_ptr;

• 빈리스트에 노드를 한 개 생성하여 50을 저장

<23페이지에 있음>

• 수정

• 삭제

• 생성함수

리스트 생성 시험 프로그램

리스트 생성 실험 프로그램 : 4개의 노드를 반복문으로 생성 (6-2)

#include <stdio.h>

#include <malloc.h>

struct node {

	int data;

	struct node * link;

};

typedef struct node list_node;

typedef list_node * list_ptr;

 

int main()

{

	list_ptr ptr = NULL, before = NULL; int i;

	for (i = 1; i <= 4; i++) {

		ptr = (list_ptr)malloc(sizeof(list_node));

		ptr->data = i * 10;

		ptr->link = before;

		before = ptr;

	}

	printf(" %d\\n", ptr->data);

	printf(" %d\\n", ptr->link->data);

 

	printf(" %d\\n", ptr->link->link->data);

	printf(" %d\\n", ptr->link->link->link->data);

}

연결리스트를 이용한 스택과 큐 구현

연결리스트를 이용한 스택의 구현

왜 스택으로 하는가? → 배열의 개수를 100개로 선언을 했으나 실질적으로 3~4 등과 같이 적은 공간만 쓰거나 공간보다 더 많이 사용할 경우 error가 된다.

연결리스트의 경우 동적할당이 가능하기 때문에 기억장소의 절약과 활용이 편리하다는 장점이 있다.

번거롭다는 단점이 있다.

스택의 상태

• 비어있는 상태 : top ==NULL
• 꽉 찬 상태
  • malloc() 함수 호출 시 기억 장소 공간이 부족할 때
•  

스택 test의 main 함수

/* 프로그램 6-3, 6-4 연결리스트를 이용한 스택 : linkedlist-stack.c */
#include <stdio.h>
#include <malloc.h>
#define MAX_STACK_SIZE 100

struct node {
    int item;
    struct node *link;
};
typedef struct node stacknode;
typedef stacknode *stacknode_ptr;

stacknode_ptr top=NULL;

void push(int data) {
   stacknode_ptr temp =
   (stacknode_ptr)malloc(sizeof (stacknode));
   if( !temp) {
	fprintf(stderr,"The memory is full\\n");
	exit(1);
   }
   temp->item=data;
   temp->link=top;
   top = temp;
}

int pop() {
   stacknode_ptr temp = top;
   int item;
   if( !temp ) {
	fprintf(stderr,"The stack is empty\\n");
	exit(1);
   }
   item=temp->item;
   top=temp->link;
   free(temp);
   return item;
}

int isempty()
{ if( top == NULL ) return(1); else return(0); }

int main()
{
	int e;
	push(20);
	push(40);
	push(60);

	printf(" Begin Stack Test ...\\n");

	while(!isempty())
	{
		e = pop();
		printf("value = %d\\n", e);
	}
}

연결리스트를 이용한 큐의 구현

• 앞은 삽입 삭제가 쉬우나 뒤는 삭제가 어렵고 삽입은 쉽다.
• ⇒ rear가 마지막 노드. front가 첫 번째 노드로 만들자!

큐의 상태

• 비어있는 큐 : front==null
• 꽉 찬 상태 : malloc()함수 호출 시 기억 장소 확보가 어려울 때

/* DBLAB linkedlist-queue.c */
#include <stdio.h>
#include <malloc.h>
#define MAX_QUEUES 10 /* m=MAX_QUEUES=10 */
typedef struct {
	int key;/* other fields */
} element;

struct node {
	element item;
	struct node* link;
};
typedef struct node queuenode;
typedef queuenode* queuenode_ptr;

void insertq(queuenode_ptr *front, queuenode_ptr *rear, element x) {
	queuenode_ptr temp = (queuenode_ptr)malloc(sizeof(queuenode));
	if( !temp ) {
		fprintf(stderr,"The memory is full\\n");
	exit(1);
	}
	temp->item=x;
	temp->link=NULL;
	if(*front) (*rear)->link=temp;
	else *front = temp;
	*rear = temp;
}

element deleteq(queuenode_ptr *front) {
	queuenode_ptr temp=*front;
	element x;
	if(!(*front)) {
		fprintf(stderr,"The queue is empty\\n");
		exit(1);
	}
	x=temp->item;
	*front=temp->link;
	free(temp);
	return x;
}

int main()
{
	queuenode_ptr front=NULL, rear=NULL;
	element x; x.key=50;
	insertq(&front, &rear, x);
	insertq(&front, &rear, x);
	insertq(&front, &rear, x);

	printf(" Begin Queue Test ...\\n");

	while(! front==NULL)
	{
		x = deleteq(&front);
		printf("value = %d\\n", x.key);
	}
}

6.2

#include <stdio.h>
#include <malloc.h>

struct node {
	int data;
	struct node * link;
};

typedef struct node list_node;
typedef list_node * list_ptr;

void print_list(list_ptr p);

int main() {
	list_ptr p;

	int n = 10;

	list_ptr temp = NULL;
	list_ptr before = NULL;
	for (int i = 1; i <= n; i++) {
		temp = (list_ptr)malloc(sizeof(list_node));
		temp->data = (n - i + 1) * 10;
		temp->link = before;
		before = temp;
	}
	p = temp;

	print_list(p);

	//find(p, 2);

	list_ptr head = p;
	int i = 0;
	int k = 1;
	for (int i = 0; i <k-1; i++) {
		head = head->link;
	}
	printf("ok %d\\n", head->data);

}

list_ptr creat(int n) {
	list_ptr first;
	list_ptr temp = NULL;
	list_ptr before = NULL;
	for (int i = 1; i <= n; i++){
		temp=(list_ptr)malloc(sizeof(list_node));
		temp->data = (n - i + 1) * 10;
		temp->link = before;
		before = temp;
	}
	first = temp; return first;
}

void print_list(list_ptr p) {
	list_ptr temp;
	for (temp = p; temp; temp = temp->link) {
		printf("%d\\n", temp->data);

	}
}

•  

6.4

• 실험 1
• 
• 실험 2

int elementcount(queuenode_ptr front, queuenode_ptr rear){
if(!front){return -1;}

/*여기 작성*/

return 0;
}

void main(){

printf(queue length = "%d", elementcount(front, rear));
}

/* DBLAB linkedlist-queue.c */
#include <stdio.h>
#include <malloc.h>
#define MAX_QUEUES 10 /* m=MAX_QUEUES=10 */
typedef struct {
	int key;/* other fields */
} element;

struct node {
	element item;
	struct node* link;
};
typedef struct node queuenode;
typedef queuenode* queuenode_ptr;

int elementcount(queuenode_ptr front, queuenode_ptr rear) {
	if (!front) { return -1; }

	else {
		return front-rear;

		//queue에 있는 원소의 수 세기 프로그램
		int count = 0, i=0;
		//while(!i) {
		//	i = front->link;
		//	count++;
		//}
		//return count;
	}

	return 0;
}

void insertq(queuenode_ptr* front, queuenode_ptr* rear, element x) {
	queuenode_ptr temp = (queuenode_ptr)malloc(sizeof(queuenode));
	if (!temp) {
		fprintf(stderr, "The memory is full\\n");
		exit(1);
	}
	temp->item = x;
	temp->link = NULL;
	if (*front) (*rear)->link = temp;
	else *front = temp;
	*rear = temp;
}

element deleteq(queuenode_ptr* front) {
	queuenode_ptr temp = *front;
	element x;
	if (!(*front)) {
		fprintf(stderr, "The queue is empty\\n");
		exit(1);
	}
	x = temp->item;
	*front = temp->link;
	free(temp);
	return x;
}

int main()
{
	queuenode_ptr front = NULL, rear = NULL;
	element x; x.key = 50;
	insertq(&front, &rear, x);
	insertq(&front, &rear, x);
	insertq(&front, &rear, x);

	printf(" Begin Queue Test ...\\n");

	printf("queue length = %d\\n", elementcount(front, rear));

	while (!front == NULL)
	{
		x = deleteq(&front);
		printf("value = %d\\n", x.key);
	}
}