24/07/11Estrutura de dados (6.1215) lista dupla vinculada implementação-pilha implementação

24/07/11Estrutura de dados (6.1215) implementação de pilha de implementação de lista dupla vinculada

2024-07-12

Assim como escrever algumas interfaces funcionais para listas vinculadas individualmente, vamos primeiro escrever algumas interfaces para listas duplamente vinculadas para nos familiarizarmos com sua estrutura principal:

#incluir<stdio.h>
#incluir<stdlib.h>

typedef int LDataType;

//O nó da lista vinculada circular bidirecional
typedef struct ListaNode{
LDataType _dados;
//Aponta para a posição inicial do próximo nó
estrutura ListNode* _próximo;
//Aponta para a posição inicial do nó anterior
estrutura LIst* _anterior;
}ListNode;

//Lista vinculada circular bidirecional
typedef struct Lista{
estrutura ListNode* _cabeçalho;
}Lista;

estrutura ListNode* createListNode(LDataType val){
struct ListNode* nó = (struct ListNode*)malloc(sizeof(struct ListNode));
nó->_dados = val;
nó->_next = NULL;
nó->_prev = NULL;
}

void ListInit(Lista* lst){
//Lista vinculada vazia
lst->_head = criarListNode(0);
lst->_head->_next = lst->_head->_prev = lst->_head;

}
//Inserção final O(1) //Inserir um dado na frente do cabeçalho ListInsert(lst, lst->_head, val);
void ListpushBack(Lista* lst, LDataType val){
se (lst == NULL){
retornar;
struct ListNode* último = lst->_head->_prev;
struct ListNode* novoNode = criarListNode(val);
//_head ... último novo nó
último->_próximo = novoNó;
newNode->_prev = último;

novoNode->_next = lst->_head;
lst->_head->_prev = novoNó;
}
}

//Tail delete://Exclui o nó anterior do cabeçalho ListErase(lst, lst->_head->_prev);
void ListPopBack(Lista* lst){
se (lst == NULL)
retornar;
//Determina se a lista vinculada está vazia
se (lst->_head->_next == lst->_head)
retornar;
struct ListNode* último = lst->_head->_prev;
struct ListNode* prev = último->_prev;

livre(último);

lst->_head->_prev = anterior;
anterior->_próximo = lst->_head;
}

vazio printList(Lista* lst){
estrutura ListNode* cur = lst->_head->_next;
enquanto (cur != lst->_head){
printf("%d", cur->_data);
cur = cur->_next;
}
printf("n");
}

//Inserção de cabeçalho//ListInsert(lst,lst->_head->_next,val);
void ListPushFront(Lista* lst, LDataType val){
se (lst == NULL)
retornar;
struct ListNode* próximo = lst->_head->_next;
struct ListNode* novoNode = criarListNode(val);

//_head, novoNode, próximo
lst->_head->_next = novoNó;
novoNode->_prev = lst->_head;

newNode->_next = próximo;
próximo->_anterior = novoNó;
}

//Excluir cabeçalho//ListErase(lst,lst->_head->_next);
void ListPopFront(Lista* lst){
se (lst == NULL || lst->_head == lst->_head)
retornar;
struct ListNode* próximo = lst->_head->_next;
struct ListNode* nextnext = próximo->_próximo;

próximopróximo->_anterior = próximo->_próximo;
lst->_head->_next = próximopróximo;

livre(próximo);

}

void ListErase(Lista* lst, struct ListNode* nó){
//Não é possível excluir o nó principal
se (lst == NULL || lst->_head == nó)
retornar;
//anterior, nó, próximo
struct ListNode* anterior = nó->_anterior;
struct ListNode* próximo = nó->_próximo;

anterior->_próximo = próximo;
próximo->_anterior = anterior;

livre(nó);

}

void ListInsert(Lista* lst, struct ListNode* nó, LDataType val){
se (lst == NULL)
retornar;
struct ListNode* anterior = nó->_anterior;
struct ListNode* novoNode = criarListNode(val);

//anterior novo nó Node
anterior->_próximo = novoNó;
novoNode->_prev = prev;

novoNode->_next = nó;
nó->_prev = novoNó;
}

//destruir
ListaDestoty(Lista* lst){
se (lst){
se (lst->_head){
estrutura ListNode* cur = lst->_head->_next;
enquanto (cur != lst->_head){
struct ListNode* próximo = cortar->_próximo;
livre(atual);
cur = próximo;
}

livre(lst->_head);
}
}
}

teste vazio(){
Lista lst;
ListInit(&lst);
ListPushFront(&lst, 5);
imprimirLista(&lst);
ListPushFront(&lst, 1);
imprimirLista(&lst);
ListPushFront(&lst, 2);
imprimirLista(&lst);
ListPushFront(&lst, 3);
imprimirLista(&lst);
ListPushFront(&lst, 4);
imprimirLista(&lst);
ListarPopFront(&lst);
imprimirLista(&lst);
ListarPopFront(&lst);
imprimirLista(&lst);
ListarPopFront(&lst);
imprimirLista(&lst);

/*ListPopBack(&lst);
imprimirLista(&lst);
ListaPopBack(&lst);
imprimirLista(&lst);
ListaPopBack(&lst);
imprimirLista(&lst);
ListaPopBack(&lst);
imprimirLista(&lst);*/
}

int principal(){

teste();
sistema("pausa");
retornar 0;
}

A diferença e conexão entre lista de sequência e lista vinculada:

Vantagens e desvantagens da tabela de sequência: Excelente: o espaço é contínuo, suporta acesso aleatório, tem alta utilização de espaço e não é provável que cause fragmentação de memória e tem alta eficiência de inserção e exclusão de cauda.

Desvantagens: 1. A complexidade de tempo para inserir e excluir a parte central ou frontal é O(N) 2. O custo de expansão da capacidade é relativamente alto: solicite a liberação de cópia

Vantagens e desvantagens das listas vinculadas (listas vinculadas aleatórias bidirecionais)

Vantagens: 1. A complexidade de tempo de inserção e exclusão em qualquer posição é O(1) 2. Não há problema de expansão de capacidade, a inserção abre um espaço e a eficiência de inserção e exclusão em qualquer posição é alta

Desvantagens: É armazenado em unidades de nós, não suporta acesso aleatório e a baixa utilização do espaço pode facilmente causar fragmentação da memória.

pilhas e filas

Pilha: uma lista linear especial que permite apenas a inserção e exclusão de elementos em uma extremidade. A extremidade onde as operações de inserção e exclusão de dados são executadas é chamada de topo da pilha e a outra extremidade é chamada de parte inferior da pilha. na pilha segue o princípio LIFO (último a entrar, primeiro a sair)

Empurrando a pilha: a operação de inserção da pilha é chamada push/push/push, e os dados inseridos estão no topo da pilha

Pop: A operação de exclusão da pilha é chamada de popping, e os dados que estão sendo exibidos também ficam no topo da pilha.

Implementação da operação push push--->armazenar elementos do topo da pilha

Tabela de sequência: pode ser considerada uma operação de inserção final

Lista vinculada: (lista vinculada circular bidirecional) o topo da lista é considerado o topo da pilha, que é a inserção do cabeçalho, e o final da lista é considerado o topo da pilha, que é o inserção da cauda.

Operação pop pop ---> remover elementos do topo da pilha

Tabela de sequência: o final da tabela é considerado o topo da pilha e é considerado a operação de exclusão final.

Lista vinculada: (lista vinculada circular bidirecional) o topo da lista é considerado o topo da pilha, que é a exclusão do cabeçalho, e o final da lista é considerado o topo da pilha, que é o exclusão da cauda.

#incluir<stdio.h>
#incluir<stdlib.h>

typedef int STDataType;
//A tabela de sequência implementa uma pilha
typedef struct pilha{
STDataType* _dados;
int _tamanho;
int _capacidade;
}pilha;

void stackInit(pilha* st){
se (st == NULL)
retornar;
st->_data = NULO;
st->_tamanho = st->_capacidade = 0;
}

void checkCapacidade(pilha* st){
se (st->_tamanho == st->_capacidade){
int novaCapacidade = st->_capacidade == 0 ? 1 : 2 * st->_capacidade;
st->_data = (STDataType*)realloc(st->_data, tamanho(STDataType)* novaCapacidade);
st->_capacidade = novaCapacidade;
}

}

//Empurra para empilhar
void stackPush(pilha* st, STDataType val){
se (st == NULL)
retornar;
verificarCapacidade(st);
//Inserção de cauda
st->_data[st->_size++] = val;

}

//pop
void stackPop(pilha* st){
se (st == NULL)
retornar;
se (st->_size > 0)
st->_tamanho--;
}

STDataType pilhaTop(pilha* st){
retornar st->_data[st->_size - 1];
}

int stackSize(pilha* st){
se (st == NULL)
retornar 0;
retornar st->_size;
}

teste vazio(){
pilha st;
pilhaInit(&st);
pilhaPush(&st, 1);
pilhaPush(&st, 2);
empilharEmpurrar(&st, 3);
empilharEmpurrar(&st, 4);
para (int i = 0; i < 4; ++i){
printg("%d", stackTop(&st));
pilhaPop(&st);
}
printf("n");
}

int principal(){
teste();
sistema("pausa");
retornar 0;
}

Compartilhamento de tecnologia

24/07/11Estrutura de dados (6.1215) implementação de pilha de implementação de lista dupla vinculada

Perfil pessoal

minhas informações de contato