11/07/24데이터 구조(6.1215) 이중 연결 리스트 구현-스택 구현

11.24.07.자료구조(6.1215) 이중연결리스트 구현-스택 구현

2024-07-12

단일 연결 목록에 대한 일부 기능적 인터페이스를 작성하는 것처럼 먼저 이중 연결 목록에 대한 일부 인터페이스를 작성하여 기본 프레임워크에 익숙해지도록 하겠습니다.

#포함하다<stdio.h>
#포함하다<stdlib.h>

typedef int LDataType;

//양방향 순환 연결 리스트의 노드
typedef 구조체 ListNode{
LDataType _data;
//다음 노드의 시작 위치를 가리킨다.
구조체 ListNode* _next;
//이전 노드의 시작 위치를 가리킨다.
구조체 LIst* _prev;
}리스트노드;

//양방향 순환 연결 리스트
typedef 구조체 목록{
구조체 ListNode* _head;
}목록;

구조체 ListNode* createListNode(LDataType val){
구조체 ListNode* 노드 = (구조체 ListNode*)malloc(구조체 ListNode의 크기));
노드->_데이터 = val;
노드->_다음 = NULL;
노드->_이전 = NULL;
}

void ListInit(리스트* lst){
//빈 연결리스트
lst->_head = createListNode(0);
lst->_헤드->_다음 = lst->_헤드->_이전 = lst->_헤드;

}
//테일 삽입 O(1) //헤드 앞에 데이터를 삽입합니다. ListInsert(lst, lst->_head, val);
void ListpushBack(List* lst, LDataType val){
if (lst == NULL){
반품;
구조체 ListNode* last = lst->_head->_prev;
구조체 ListNode* newNode = createListNode(val);
//_head ... 마지막 newNode
마지막->다음 = 새 노드;
newNode->_prev = 마지막;

새로운 노드->_다음 = 첫 번째 노드->_헤드;
lst->_head->_prev = 새 노드;
}
}

//Tail delete://헤드의 이전 노드를 삭제합니다. ListErase(lst, lst->_head->_prev);
void ListPopBack(리스트* lst){
if (lst == NULL)
반품;
//연결리스트가 비어 있는지 확인
if (lst->_head->_next == lst->_head)
반품;
구조체 ListNode* last = lst->_head->_prev;
구조체 ListNode* 이전 = 마지막->_이전;

무료(마지막);

lst->_head->_이전 = 이전;
이전->다음 = 첫 번째->머리;
}

void printList(리스트* lst){
구조체 ListNode* cur = lst->_head->_next;
while (cur != lst->_head){
printf("%d", cur->_data);
커서 = 커서->다음;
}
printf("n");
}

//헤드 삽입//ListInsert(lst,lst->_head->_next,val);
void ListPushFront(목록 * lst, LDataType val){
if (lst == NULL)
반품;
구조체 ListNode* next = lst->_head->_next;
구조체 ListNode* newNode = createListNode(val);

//_head, newNode, 다음
lst->_head->_next = 새 노드;
새로운 노드->_이전 = 첫 번째 노드->_헤드;

newNode->_next = 다음;
다음->_이전 = 새 노드;
}

//헤더 삭제//ListErase(lst,lst->_head->_next);
void ListPopFront(리스트* lst){
if (lst == NULL || lst->_head == lst->_head)
반품;
구조체 ListNode* next = lst->_head->_next;
구조체 ListNode* nextnext = next->_next;

다음다음->_이전 = 다음->_다음;
lst->_head->_next = 다음다음;

무료(다음);

}

void ListErase(List* lst, struct ListNode* node){
//헤드 노드를 삭제할 수 없습니다.
if (lst == NULL || lst->_head == 노드)
반품;
//이전, 노드, 다음
구조체 ListNode* 이전 = 노드->_이전;
구조체 ListNode* next = node->_next;

이전->다음 = 다음;
다음->_이전 = 이전;

자유(노드);

}

void ListInsert(List* lst, struct ListNode* node, LDataType val){
if (lst == NULL)
반품;
구조체 ListNode* 이전 = 노드->_이전;
구조체 ListNode* newNode = createListNode(val);

//이전 newNode 노드
이전->다음 = 새 노드;
newNode->_prev = 이전;

newNode->_next = 노드;
노드->_이전 = 새 노드;
}

//파괴하다
ListDestoty(목록* lst){
만약 (첫번째){
if (lst->_head){
구조체 ListNode* cur = lst->_head->_next;
while (cur != lst->_head){
구조체 ListNode* next = cut->_next;
자유(개);
cur = 다음;
}

무료(lst->_head);
}
}
}

무효 테스트(){
목록 lst;
리스트초기화(&lst);
ListPushFront(&lst, 5);
printList(&lst);
ListPushFront(&lst, 1);
printList(&lst);
ListPushFront(&lst, 2);
printList(&lst);
ListPushFront(&lst, 3);
printList(&lst);
ListPushFront(&lst, 4);
printList(&lst);
리스트팝프론트(&lst);
printList(&lst);
리스트팝프론트(&lst);
printList(&lst);
리스트팝프론트(&lst);
printList(&lst);

/*리스트팝백(&lst);
printList(&lst);
리스트팝백(&lst);
printList(&lst);
리스트팝백(&lst);
printList(&lst);
리스트팝백(&lst);
printList(&lst);*/
}

int 메인(){

시험();
시스템("일시 중지");
0을 반환합니다.
}

시퀀스 목록과 연결 목록의 차이점과 연결:

시퀀스 테이블의 장점과 단점: 우수함: 공간이 연속적이며, Random Access를 지원하고, 공간 활용도가 높으며, 메모리 조각화가 발생하지 않으며, Tail 삽입 및 Tail 삭제 효율성이 높습니다.

단점 : 1. 중간이나 앞 부분을 삽입하고 삭제하는 시간복잡도가 O(N) 2. 용량 증설 비용이 상대적으로 높음 : 카피 출시 신청

연결 목록(led 양방향 무작위 연결 목록)의 장점과 단점

장점: 1. 임의 위치에 삽입 및 삭제하는 시간 복잡도는 O(1)입니다. 2. 용량 확장 문제가 없으며, 하나를 삽입하면 공간이 열리고, 임의 위치에 삽입 및 삭제 효율성이 높습니다.

단점: 노드 단위로 저장되며, 랜덤 액세스를 지원하지 않으며, 공간 활용도가 낮아 메모리 조각화가 쉽게 발생할 수 있습니다.

스택과 큐

스택: 한쪽 끝에서만 요소의 삽입과 삭제를 허용하는 특수 선형 목록입니다. 데이터 삽입 및 삭제 작업이 수행되는 쪽을 스택의 맨 위, 다른 쪽 끝을 스택의 맨 아래라고 합니다. 스택에서는 LIFO(후입선출) 원칙을 따릅니다.

스택 푸시: 스택의 삽입 작업을 푸시/푸시/푸시라고 하며, 삽입된 데이터는 스택의 맨 위에 위치합니다.

팝(Pop): 스택의 삭제 작업을 팝핑(popping)이라고 하며, 팝되는 데이터도 스택의 맨 위에 있습니다.

푸시 작업 구현 push--->스택 상단의 요소 저장

시퀀스 테이블: 테일 삽입 작업으로 간주할 수 있습니다.

연결 리스트(Linked list): (양방향 방향 순환 연결 리스트) 리스트의 선두를 스택의 맨 위, 즉 헤드 삽입으로 간주하고, 리스트의 꼬리를 스택의 맨 위로 간주하여 삽입합니다. 꼬리 삽입.

Pop 연산 pop--->스택의 맨 위에서 요소를 제거합니다.

시퀀스 테이블: 테이블의 끝을 스택의 최상위로 간주하여 테일 삭제 작업으로 간주합니다.

연결 리스트(Linked list): (양방향 방향 순환 연결 리스트) 리스트의 선두를 스택의 최상위로 간주하는 헤드 삭제, 리스트의 꼬리를 스택의 최상위로 간주하는 삭제 꼬리 삭제.

#포함하다<stdio.h>
#포함하다<stdlib.h>

typedef int STDataType;
//시퀀스 테이블은 스택을 구현합니다.
typedef 구조체 스택{
STDataType* _데이터;
int _크기;
int _용량;
}스택;

void stackInit(스택* st){
만약 (st == NULL)
반품;
st->_data = NULL;
st->_크기 = st->_용량 = 0;
}

void checkCapcacity(스택*st){
(st->_size == st->_capacity)이면
int newCapacity = st->_capacity == 0 ? 1 : 2 * st->_capacity;
st->_data = (STDataType*)realloc(st->_data, STDataType의 크기* 새 용량);
st->_용량 = 새 용량;
}

}

//스택에 푸시
void stackPush(스택* st, STDataType val){
만약 (st == NULL)
반품;
용량 확인(st);
//꼬리 삽입
st->_데이터[st->_크기++] = 값;

}

//팝
void stackPop(스택* st){
만약 (st == NULL)
반품;
만약 (st->_size > 0)
st->_크기--;
}

STDataType stackTop(스택* st){
st->_data[st->_size - 1]을 반환합니다.
}

int stackSize(스택*st){
만약 (st == NULL)
0을 반환합니다.
st->_size를 반환합니다.
}

무효 테스트(){
스택 st;
스택 초기화(&st);
스택푸시(&st, 1);
스택푸시(&st, 2);
스택푸시(&st, 3);
스택푸시(&st, 4);
(int i = 0; i < 4; ++i)에 대하여{
printg("%d", stackTop(&st));
스택팝(&st);
}
printf("n");
}

int 메인(){
시험();
시스템("일시 중지");
0을 반환합니다.
}

기술나눔

11.24.07.자료구조(6.1215) 이중연결리스트 구현-스택 구현

개인 프로필

내 연락처 정보