aed1-1-q01.txt

Algoritmos e Estruturas de Dados 1
Atividade Avaliativa 1
Pilhas, Filas e Lista

Questão 1 (1.0 ponto): Supondo as operações básicas de pilha (LIFO
- Last In, First Out) e fila (FIFO - First In, First Out), você
precisa simular a sequência de operações dada e determinar o estado
final de cada estrutura de dados utilizada. Para isso, considere as
seguintes operações sendo realizadas em uma estrutura de dados
inicialmente vazia:

  1. Empilhar(5)     6. Enfileirar(15)
  2. Enfileirar(10)  7. Desenfileirar()
  3. Empilhar(3)     8. Empilhar(8)
  4. Enfileirar(20)  9. Desenfileirar()
  5. Desempilhar()  10. Desempilhar()

Após a execução de todas essas operações, descreva o estado final
da(s) estrutura(s) de dados envolvida(s). Se mais de uma estrutura
for usada, deixe claro qual estado pertence a qual estrutura.

==== RESPOSTA =====================================================

ESTADOS:

 1. Pilha: [5]; é empilhado 5 no topo da pilha.
 2. Fila:  [10]; é enfileirado 10 no final da fila.
 3. Pilha: [3,5]; é empilhado 3 no topo da pilha.
 4. Fila:  [10,20]; é enfileirado 20 no final da fila.
 5. Pilha: [5]; é desempilhado 3 do topo da pilha.
 6. Fila:  [10,20,15]; é enfileirado 15 no final da fila.
 7. Fila:  [20,15]; é desenfileirado 10 do início da fila.
 8. Pilha: [8,5]; é empilhado 8 no topo da pilha.
 9. Fila:  [15]; é desenfileirado 20 do início da fila.
10. Pilha: [5]; é desempilhado 3 do topo da pilha.
No estado final, a pilha contém o elemento 5 e a fila contém o elemento 15.

aed1-1-q02.c

/*
Algoritmos e Estruturas de Dados 1
Atividade Avaliativa 1
Pilhas, Filas e Lista

Questão 2 (2.0 pontos): Implemente em C uma função chamada
'inverterFilaComPilhas' que recebe uma fila F e retorna uma nova
fila com os elementos de F em ordem reversa, utilizando uma ou mais
pilhas como estrutura auxiliar. A fila original F não deve ser
modificada ao final da execução da função.
*/

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

/**** CÓDIGO DA FILA ****/

typedef struct NodeFila NodeFila;
struct NodeFila {
	int data;
	NodeFila *next;
};

typedef struct {
	NodeFila *front;
} Fila;

Fila *criarFila(void) {
	Fila *f;
	f = malloc(sizeof(Fila));
	f->front = NULL;
	return f;
}

void enfileirar(Fila *f, int data) {
	NodeFila *n, *new;
	new = malloc(sizeof(NodeFila));
	new->data = data;
	new->next = NULL;
	if (!f->front) {
		f->front = new;
		return;
	}
	for (n = f->front; n->next; n = n->next);
	n->next = new;
}

int desenfileirar(Fila *f) {
	NodeFila *n;
	int data;
	data = f->front->data;
	n = f->front->next;
	free(f->front);
	f->front = n;
	return data;
}

int filaVazia(Fila *f) {
	return !f->front;
}

void imprimirFila(Fila *f) { /* (omitido na prova) */
	NodeFila *n;
	if (filaVazia(f)) {
		puts("NULL");
		return;
	}
	for (n = f->front; n->next; n = n->next)
		printf("%d -> ", n->data);
	printf("%d -> NULL\n", n->data);
}

/**** CÓDIGO DA PILHA ****/

typedef struct NodePilha NodePilha;
struct NodePilha {
	int data;
	NodePilha *next;
};

typedef struct {
	NodePilha *top;
} Pilha;

Pilha *criarPilha(void) {
	Pilha *p;
	p = malloc(sizeof(Pilha));
	p->top = NULL;
	return p;
}

void empilhar(Pilha *p, int data) {
	NodePilha *n;
	n = malloc(sizeof(NodePilha));
	n->data = data;
	n->next = p->top;
	p->top = n;
}

int desempilhar(Pilha *p) {
	NodePilha *n;
	int data;
	data = p->top->data;
	n = p->top->next;
	free(p->top);
	p->top = n;
	return data;
}

int pilhaVazia(Pilha *p) {
	return !p->top;
}

/**** IMPLEMENTAÇÃO DE 'inverterFilaComPilhas' ****/

Fila *inverterFilaComPilhas(Fila F) {
	NodeFila *n;
	Fila *inv;
	Pilha *aux;
	inv = criarFila();
	aux = criarPilha();
	for (n = F.front; n; n = n->next)
		empilhar(aux, n->data);
	while (!pilhaVazia(aux))
		enfileirar(inv, desempilhar(aux));
	free(aux);
	return inv;
}

int main(void) {
	Fila *filaOriginal, *filaInvertida;
	NodeFila *atual, *temp;

	filaOriginal = criarFila();
	enfileirar(filaOriginal, 1);
	enfileirar(filaOriginal, 2);
	enfileirar(filaOriginal, 3);
	enfileirar(filaOriginal, 4);

	printf("Fila original:  ");
	imprimirFila(filaOriginal);

	filaInvertida = inverterFilaComPilhas(*filaOriginal);

	printf("Fila invertida: ");
	imprimirFila(filaInvertida);

	atual = filaInvertida->front;
	while (atual != NULL) {
		temp = atual;
		atual = atual->next;
		free(temp);
	}
	free(filaInvertida);

	atual = filaOriginal->front;
	while (atual != NULL) {
		temp = atual;
		atual = atual->next;
		free(temp);
	}
	free(filaOriginal);

	return 0;
}

/* Exemplo de compilação: cc -std=c89 -O0 -g -fsanitize=address,leak,undefined -Wall -Wextra -Wpedantic -Werror -Wno-unused-parameter aed1-1-q02.c && ./a.out */

aed1-1-q03.c

/*
Algoritmos e Estruturas de Dados 1
Atividade Avaliativa 1
Pilhas, Filas e Listas

Questão 3 (2.5 pontos): Suponha uma lista simplesmente encadeada
de números inteiros. Escreva um algoritmo em C para verificar se
essa lista é uma palíndromo. Um palíndromo é uma sequência que é
lida da mesma forma da esquerda para a direita e da direita para
a esquerda (ex: 1 -> 2 -> 2 -> 1). Utilize uma pilha como
estrutura auxiliar.
*/

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

/**** CÓDIGO DA LISTA ENCADEADA ****/

typedef struct Node Node;
struct Node {
	int valor;
	Node *next;
};

typedef struct {
	Node *head;
} LinkedList;

LinkedList *criarLista(void) {
	LinkedList *lista;
	lista = malloc(sizeof(LinkedList));
	lista->head = NULL;
	return lista;
}

void inserirFinal(LinkedList *lista, int valor) {
	Node *n, *new;
	new = malloc(sizeof(Node));
	new->valor = valor;
	new->next = NULL;
	if (!lista->head) {
		lista->head = new;
		return;
	}
	for (n = lista->head; n->next; n = n->next);
	n->next = new;
}

void liberarLista(LinkedList *lista) {
	Node *n, *next;
	for (n = lista->head; n; n = next) {
		next = n->next;
		free(n);
	}
	free(lista);
}

void imprimirLista(LinkedList *lista) { /* (omitida da prova) */
	Node *n;
	if (!lista->head) {
		puts("NULL");
		return;
	}
	for (n = lista->head; n->next; n = n->next)
		printf("%d -> ", n->valor);
	printf("%d -> NULL\n", n->valor);
}

/**** CÓDIGO DA PILHA ****/

typedef struct StackNode StackNode;
struct StackNode {
	int valor;
	StackNode *next;
};

typedef struct {
	StackNode *top;
} Stack;

Stack *criarPilha(void) {
	Stack *pilha;
	pilha = malloc(sizeof(Stack));
	pilha->top = NULL;
	return pilha;
}

void empilhar(Stack *pilha, int valor) {
	StackNode *n;
	n = malloc(sizeof(StackNode));
	n->valor = valor;
	n->next = pilha->top;
	pilha->top = n;
}

int desempilhar(Stack *pilha) {
	StackNode *n;
	int valor;
	valor = pilha->top->valor;
	n = pilha->top->next;
	free(pilha->top);
	pilha->top = n;
	return valor;
}

bool pilhaVazia(Stack *pilha) {
	return !pilha->top;
}

void liberarPilha(Stack *pilha) {
	while (!pilhaVazia(pilha))
		desempilhar(pilha);
	free(pilha);
}

/**** CÓDIGO DO PALÍNDROMO ****/

bool ehPalindromoLista(LinkedList *lista) {
	Stack *pilha;
	Node *n;
	pilha = criarPilha();
	for (n = lista->head; n; n = n->next)
		empilhar(pilha, n->valor);
	for (n = lista->head; n; n = n->next) {
		if (n->valor != desempilhar(pilha)) {
			liberarPilha(pilha);
			return false;
		}
	}
	liberarPilha(pilha);
	return true;
}

int main(void) {
	LinkedList *lista1, *lista2, *lista3, *lista4, *lista5;

	/* Teste 1: palíndromo */
	lista1 = criarLista();
	inserirFinal(lista1, 1);
	inserirFinal(lista1, 2);
	inserirFinal(lista1, 2);
	inserirFinal(lista1, 1);
	printf("Lista 1 é palíndromo? %s\n",
			ehPalindromoLista(lista1) ? "Sim" : "Não");
	liberarLista(lista1);

	/* Teste 2: não palíndromo */
	lista2 = criarLista();
	inserirFinal(lista2, 1);
	inserirFinal(lista2, 2);
	inserirFinal(lista2, 3);
	printf("Lista 2 é palíndromo? %s\n",
			ehPalindromoLista(lista2) ? "Sim" : "Não");
	liberarLista(lista2);

	/* Teste 3: palíndromo com comprimento ímpar */
	lista3 = criarLista();
	inserirFinal(lista3, 1);
	inserirFinal(lista3, 2);
	inserirFinal(lista3, 1);
	printf("Lista 3 é palíndromo? %s\n",
			ehPalindromoLista(lista3) ? "Sim" : "Não");
	liberarLista(lista3);

	/* Teste 4: lista vazia */
	lista4 = criarLista();
	printf("Lista 4 é palíndromo? %s\n",
			ehPalindromoLista(lista4) ? "Sim" : "Não");
	liberarLista(lista4);

	/* Teste 5: lista com um elemento */
	lista5 = criarLista();
	inserirFinal(lista5, 5);
	printf("Lista 5 é palíndromo? %s\n",
			ehPalindromoLista(lista5) ? "Sim" : "Não");
	liberarLista(lista5);

	return 0;
}

aed1-1-q04-fila.c

/* (Isso é um código auxiliar para o arquivo aed1-1-q04.c) */

/**** CÓDIGO DA FILA DA Q2 ADAPTADO PARA Q4 ****/

typedef struct NodeFila NodeFila;
struct NodeFila {
	Tarefa *t;
	NodeFila *next;
};

typedef struct {
	NodeFila *front;
} Fila;

Fila *criarFila(void) {
	Fila *f;
	f = malloc(sizeof(Fila));
	f->front = NULL;
	return f;
}

void enfileirar(Fila *f, Tarefa *t) {
	NodeFila *n, *new;
	new = malloc(sizeof(NodeFila));
	new->t = t;
	new->next = NULL;
	if (!f->front) {
		f->front = new;
		return;
	}
	for (n = f->front; n->next; n = n->next);
	n->next = new;
}

Tarefa *desenfileirar(Fila *f) {
	NodeFila *n;
	Tarefa *t;
	t = f->front->t;
	n = f->front->next;
	free(f->front);
	f->front = n;
	return t;
}

int filaVazia(Fila *f) {
	return !f->front;
}

aed1-1-q04.c

/*
Algoritmos e Estruturas de Dados 1
Atividade Avaliativa 1
Pilhas, Filas e Listas

Questão 4 (4.5 pontos): Imagine que você precisa processar uma
série de tarefas. Algumas tarefas precisam ser processadas na
ordem em que chegam (como em uma fila), enquanto outras têm
prioridade e precisam ser processadas imediatamente (como em uma
pilha de interrupções).

É necessário utilizar uma estruturas de dados (ou uma combinação
de estruturas que possa lidar eficientemente com essa situação,
permitindo adicionar tarefas comuns e tarefas prioritárias, e
também remover a próxima tarefa a ser processada (dando
prioridade às tarefas prioritárias). Utilize a proposta abaixo
para a implementação.

Proposta de Estrutura de Dados:
- Use duas filas separadas:
  1. Fila de prioridade: Para as tarefas com alta prioridade.
  Novas tarefas prioritárias são adicionadas ao final desta fila
  (comportamento de fila dentro da prioridade).
  2. Fila comum: Para as tarefas regulares, adicionadas e
  removidas em ordem FIFO.

- Funcionamento:
  * Adicionar tarefa comum: A tarefa é enfileirada na fila comum.
  * Adicionar tarefa prioritária: A tarefa é enfileirada na fila
  de prioridade.
  * Remover próxima tarefa:
    1. Primeiro, verificamos se a fila de prioridade não está
    vazia. Se não estiver, desenfileiramos e retornamos a tarefa
    da frente desta fila (FIFO dentro da prioridade).
    2. Se a fila de prioridade estiver vazia, então
    desenfileiramos e retornamos a tarefa da frente da fila
    comum.
*/

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

/**** CÓDIGO DA FILA DE TAREFAS ****/

typedef struct Tarefa Tarefa;

/* Definições da estrutura de 'Fila' (reutilizando da Q2) */
#include "aed1-1-q04-fila.c"

struct Tarefa {
	char *descricao;
};

Fila *criarFilaTarefa(void) {
	return criarFila();
}

void enfileirarTarefa(Fila *f, char *descricao) {
	Tarefa *t;
	t = malloc(sizeof(Tarefa));
	t->descricao = malloc(strlen(descricao) + 1);
	strcpy(t->descricao, descricao);
	enfileirar(f, t);
}

Tarefa *desenfileirarTarefa(Fila *f) {
	return desenfileirar(f);
}

bool filaTarefaVazia(Fila *f) {
	return filaVazia(f);
}

/**** CÓDIGO DO GERENCIADOR ****/

typedef struct {
	Fila *com, *pri;
} GerenciadorTarefas;

GerenciadorTarefas *criarGerenciador(void) {
	GerenciadorTarefas *g;
	g = malloc(sizeof(GerenciadorTarefas));
	g->com = criarFilaTarefa();
	g->pri = criarFilaTarefa();
	return g;
}

void adicionarTarefaComum(GerenciadorTarefas *g, char *descricao) {
	enfileirarTarefa(g->com, descricao);
}

void adicionarTarefaPrioritaria(GerenciadorTarefas *g, char *descricao) {
	enfileirarTarefa(g->pri, descricao);
}

Tarefa *proximaTarefa(GerenciadorTarefas *g) {
	Tarefa *t = NULL;
	if (!filaTarefaVazia(g->pri)) {
		t = desenfileirarTarefa(g->pri);
	} else if (!filaTarefaVazia(g->com)) {
		t = desenfileirarTarefa(g->com);
	}
	return t;
}

void liberarGerenciador(GerenciadorTarefas *g) {
	Tarefa *tarefa;
	while ((tarefa = proximaTarefa(g)) != NULL) {
		free(tarefa->descricao);
		free(tarefa);
	}
	free(g->com);
	free(g->pri);
	free(g);
}

int main(void) {
	GerenciadorTarefas *gerenciador;
	Tarefa *tarefa;

	gerenciador = criarGerenciador();
	adicionarTarefaComum(gerenciador, "Atualizar relatório");
	adicionarTarefaPrioritaria(gerenciador, "Corrigir bug crítico");
	adicionarTarefaComum(gerenciador, "Enviar e-mails");
	adicionarTarefaPrioritaria(gerenciador, "Deploy da nova versão");

	while ((tarefa = proximaTarefa(gerenciador)) != NULL) {
		printf("%s\n", tarefa->descricao);
		free(tarefa->descricao);
		free(tarefa);
	}

	liberarGerenciador(gerenciador);
	return 0;
}

aed1-2-q01.c

/*
Algoritmos e Estruturas de Dados 1
Atividade Avaliativa 2
Algoritmos de Busca e Ordenação

Questão 1  (1.0  ponto):  Considere  a  necessidade  de  implementar  uma  lista
duplamente encadeada ordenada com alocação dinâmica de memória em  linguagem  C,
na qual será aplicada uma busca binária diretamente  sobre  os  nós  das  lista.

Sua implementação não deve trocar os  valores  das  chaves  dos  nós  durante  a
ordenação ou busca - ou seja, apenas os ponteiros dos nós podem ser  manipulados
para ordenar a lista.

Você deverá implementar as seguintes funcionalidades:
	1.  Uma rotina para inserção ordenada de um novo nó,  mantendo  a  lista
	    sempre não-decrescente.  Essa inserção deve respeitar a regra de não
            alterar o valor de chave dos nós existentes.
	2. Uma função que implementa  a busca binária sobre a lista,  retornando
	   o ponteiro para o nó com a chave buscada (ou NULL se não encontrado).
		* Lembre-se de que o acesso ao elemento do meio  da  lista  deve
		  ser feito percorrendo a lista, já que  não  há  acesso  direto
		  por índice.
	3. Demais rotinas necessárias para sua implementação.

Requisitos obrigatórios:
	* A lista deve manter-se sempre ordenada após cada inserção.
	* A busca binária deve ser implementada de forma iterativa, simulando  o
          acesso ao elemento do meio percorrendo a lista.
	* Não é permitido copiar ou trocar  valores  das  chaves  dos  registros
	  entre nós para ordenar a lista.

A implementação deve ser feita alterando o código abaixo apenas onde está
colocado: <O SEU CÓDIGO AQUI>
*/

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

typedef struct Node {
	int key; // chave de busca do registro
	struct Node *prev; // pto. para o nó anterior
	struct Node *next; // pto. para o nó posterior
} Node;

void list_InsertSorted(Node **head, int key)
{
	Node *n;
	if (!(*head)) {
		*head = calloc(1, sizeof(Node));
		(*head)->key = key;
		return;
	}
	if (key <= (*head)->key) {
		(*head)->prev = calloc(1, sizeof(Node));
		(*head)->prev->key = key;
		(*head)->prev->next = *head;
		*head = (*head)->prev;
		return;
	}
	for (n = (*head)->next; n; n = n->next) {
		if (key <= n->key) {
			n->prev->next = calloc(1, sizeof(Node));
			n->prev->next->key = key;
			n->prev->next->prev = n->prev;
			n->prev->next->next = n;
			n->prev = n->prev->next;
			return;
		} else if (!n->next) {
			n->next = calloc(1, sizeof(Node));
			n->next->key = key;
			n->next->prev = n;
			return;
		}
	}
}

// Exibe a lista
void list_Print(Node *head)
{
	Node *current = head;
	while (current) {
		printf("%d ", current->key);
		current = current->next;
	}
	printf("\n");
}

// Retorna o ponteiro para o nó da posição 'index'
Node *list_GetNodeAt(Node *head, int index)
{
	while (head && index >= 0) {
		if (!index)
			return head;
		head = head->next;
		--index;
	}
	return NULL;
}

// Retorna o tamanho da lista
int list_GetSize(Node *head)
{
	int size = 0;
	while (head) {
		size++;
		head = head->next;
	}
	return size;
}

// Busca binária na lista duplamente encadeada
Node *BinarySearch(Node *head, int key)
{
	Node *n;
	int l, r, mid;
	l = 0;
	r = list_GetSize(head)-1;
	while (l <= r) {
		mid = l + (r-l)/2;
		n = list_GetNodeAt(head, mid);
		if (n->key > key)
			r = mid-1;
		else if (n->key < key)
			l = mid+1;
		else
			return n;
	}
	return NULL;
}

void list_Free(Node *head)
{
	while (head) {
		Node *temp = head;
		head = head->next;
		free(temp);
	}
}

int main(void)
{
	Node *head = NULL;

	// Inserção de elementos
	list_InsertSorted(&head, 30);
	list_InsertSorted(&head, 10);
	list_InsertSorted(&head, 20);
	list_InsertSorted(&head, 40);
	list_InsertSorted(&head, 25);

	printf("Lista ordenada:\n");
	list_Print(head); // Saída Esperada: 10 20 25 30 40

	// Testes de busca binária
	int searchKeys[] = {25, 10, 35, 40, 5};
	for (int i = 0; i < 5; i++) {
		Node *result = BinarySearch(head, searchKeys[i]);
		if (result)
			printf("Chave %d encontrada no nó com endereço %p\n",
			       searchKeys[i], (void*)result);
		else
			printf("Chave %d não encontrada\n",
			       searchKeys[i]);
	}
	// Saída Esperada:
	// Chave 25 encontrada no nó com endereço 0x...320
	// Chave 10 encontrada no nó com endereço 0x...2c0
	// Chave 35 não encontrada
	// Chave 40 encontrada no nó com endereço 0x...300
	// Chave 5 não encontrada

	// Liberação de memória
	list_Free(head);

	return 0;
}

aed1-2-q02.c

/*
Algoritmos e Estruturas de Dados 1
Atividade Avaliativa 2
Algoritmos de Busca e Ordenação

Questão 2 (1.0 ponto):  A  Ordenação  Bolha  tradicional  é  conhecida  por  sua
simplicidade, porém, ela  é  ineficiente  para  listas  grandes,  principalmente
devido ao elevado número de trocas entre elementos adjacentes.   Para  contornar
esse problema, pode-se adotar uma técnica inspirada na Ordenação Shell,  onde  o
algoritmo  realiza  comparações  e  trocas  entre  elementos  separados  por  um
determinado intervalo (gap), que vai diminuindo  ao  longo  do  processo.   Esse
método híbrido,  chamado  Bubble-Shell  Sort,  utiliza  o  conceito  de  gap  da
Ordenação Shell, mas realiza as trocas  da  forma  característica  da  Ordenação
Bolha.  Isso reduz o número de trocas necessárias, principalmente em  sequências
parcialmente ordenadas.

Você deverá implementar as seguintes funcionalidades:
	1. O algoritmo Bubble-Shell Sort.
	2. Demais rotinas necessárias para a sua implementação.

A implementação deve ser feita alterando o código abaixo apenas onde está
colocado: <O SEU CÓDIGO AQUI>
*/

#include <stdio.h>

void BubbleShellSort(int n, int arr[])
{
	int i, s, h;
	int t;
	for (h = n/2; h > 0; h /= 2) {
		do {
			s = 0;
			for (i = 0; i < n-h; ++i) {
				if (arr[i] > arr[i+h]) {
					t = arr[i];
					arr[i] = arr[i+h];
					arr[i+h] = t;
					s = 1;
				}
			}
		} while (s);
	}
}

void PrintArray(int n, int arr[])
{
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

int main(void)
{
	int arr[] = {64, 34, 25, 12, 22, 11, 90};
	int n = 7;

	printf("Array original: \n");
	PrintArray(n, arr);

	BubbleShellSort(n, arr);

	printf("Array ordenado com Bubble-Shell Sort:\n");
	PrintArray(n, arr);

	// Saída Esperada:
	// Array original:
	// 64 34 25 12 22 11 90
	// Array ordenado com Bubble-Shell Sort:
	// 11 12 22 25 34 64 90

	return 0;
}

aed1-2-q03.c

/*
Algoritmos e Estruturas de Dados 1
Atividade Avaliativa 2
Algoritmos de Busca e Ordenação

Questão 3 (1.0  ponto):  Considere  a  implementação  de  uma  lista  duplamente
encadeada com alocação dinâmica de memória  em  linguagem  C.   Seu  objetivo  é
desenvolver um algoritmo capaz de ordenar os elementos dessa lista utilizando  o
algoritmo de ordenação Bubble Sort.

Sua implementação não deve trocar os  valores  das  chaves  dos  nós  durante  a
ordenação ou busca - ou seja, apenas os ponteiros dos nós podem ser  manipulados
para ordenar a lista.

Você deverá implementar as seguintes funcionalidades:
	1. Rotinas para inserção no final da lista.
	2. O algoritmo Bubble Sort aplicável diretamente sobre a lista.
	3. Demais rotinas necessárias para a sua implementação.

Requisitos obrigatórios:
	* Não é permitido copiar ou trocar  valores  das  chaves  dos  registros
	  entre nós para ordenar a lista.

A implementação deve ser feita alterando o código abaixo apenas onde está
colocado: <O SEU CÓDIGO AQUI>
*/

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

typedef struct Node {
	int key; // chave de busca do registro
	struct Node *prev; // pto. para o nó anterior
	struct Node *next; // pto. para o nó posterior
} Node;

// Insere no final da lista
void list_InsertRear(Node **head, int key)
{
	Node *n;
	if (!*head) {
		*head = calloc(1, sizeof(Node));
		(*head)->key = key;
		return;
	}
	for (n = *head; n->next; n = n->next);
	n->next = calloc(1, sizeof(Node));
	n->next->key = key;
	n->next->prev = n;
}

// Exibe a lista
void list_Print(Node *head)
{
	Node *current = head;
	while (current) {
		printf("%d ", current->key);
		current = current->next;
	}
	printf("\n");
}

// Bubble Sort com manipulação de ponteiros
void BubbleSort(Node **head)
{
	int swapped;
	Node *n, *next;
	if (!*head)
		return;
	do {
		n = *head;
		swapped = 0;
		while (n->next) {
			if (n->key > n->next->key) {
				next = n->next;
				if (next->next)
					next->next->prev = n;
				if (n->prev)
					n->prev->next = next;
				else
					*head = next;
				n->next = next->next;
				next->prev = n->prev;
				next->next = n;
				n->prev = next;
				swapped = 1;
			} else {
				n = n->next;
			}
		}
	} while (swapped);
}

void list_Free(Node *head)
{
	while (head) {
		Node *temp = head;
		head = head->next;
		free(temp);
	}
}

void Test(const char *desc, int size, int values[])
{
	printf("Teste: %s\n", desc);

	Node *l = NULL;
	for (int i = 0; i < size; i++) {
		list_InsertRear(&l, values[i]);
	}

	printf("Lista original: ");
	list_Print(l);

	BubbleSort(&l);

	printf("Lista ordenada: ");
	list_Print(l);

	list_Free(l);
	printf("--------------------------------------------------\n");
}

int main(void)
{
	int reverseList[] = {5, 4, 3, 2, 1};
	Test("Lista em ordem reverse", 5, reverseList);

	int duplicates[] = {4, 2, 4, 3, 2};
	Test("Lista com elementos repetidos", 5, duplicates);

	//int emptyList[] = {}; XXX
	Test("Lista vazia", 0, NULL);

	return 0;
}

aed1-2-q04.c

/*
Algoritmos e Estruturas de Dados 1
Atividade Avaliativa 2
Algoritmos de Busca e Ordenação

Questão 4 (2.0 pontos): Considere o seguinte trecho de código, que implementa  o
algoritmo de ordenação Quicksort de  forma  iterativa,  com  base  na  abordagem
apresentada por Tenembaum, Langsam e Augenstein em Estruturas de Dados Usando C.

a) (Vale 0.5) Explique com suas próprias palavras:
	i)  Qual é o  papel  da  pilha  na  função  Quicksort.   Por  que  ela é
	    necessária nessa versão do algoritmo?
	ii) Quais seriam as principais vantagens de usar a versão  iterativa  do
	    Quicksort em comparação com a versão recursiva?

b) (vale 0.5) Descreva o que acontece passo a passo quando a função Quicksort  é
chamada com o vetor  int v[] = {10, 7, 8, 9, 1, 5};.   Lembre-se  de  mostrar  o
estado da pilha durante a execução do algoritmo.

c) (vale 1.0) Complemente a implementação iterativa do  algoritmo  Quicksort  em
C, conforme o modelo apresentado no livro  Estruturas  de  Dados  Usando  C,  de
Tenembaum.
*/

#include <stdio.h>

#define MAX 100

int Partition(int arr[], int low, int high)
{
	// <O SEU CÓDIGO AQUI>
	return 0;
}

void Quicksort(int n, int arr[])
{
	// Declaração de variáveis
	// <O SEU CÓDIGO AQUI>

	// Empilha os índices no intervalo inicial do arranjo
	// <O SEU CÓDIGO AQUI>

	// Enquanto a pilha não estiver vazia
	while (1) {
		// <O SEU CÓDIGO AQUI>

		// Particiona o intervalo no topo da pilha e retorna a posição do pivô
		// <O SEU CÓDIGO AQUI>

		// Se há elementos à esquerda do pivô, empilha intervalo
		// <O SEU CÓDIGO AQUI>

		// Se há elementos à direita do pivô, empilha intervalo
		// <O SEU CÓDIGO AQUI>
	}
}

void PrintArray(int n, int arr[])
{
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

int main(void)
{
	int v[] = {29, 10, 14, 37, 13, 5, 2, 18};
	int n = 8;

	printf("Vetor original:\n");
	PrintArray(n, v);

	Quicksort(n, v);

	printf("Vetor ordenado:\n");
	PrintArray(n, v);

	return 0;
}

big-sum-circular.c

/* SOMA DE INTEIROS POSITIVOS LONGOS USANDO LISTAS CIRCULARES

Exemplo: ./big-sum-circular 18446744073709551616 81553255926290448384
*/

#include <inttypes.h>           /* para PRIu32 */
#include <stdint.h>             /* para uint32_t e UINT32_MAX */
#include <stdio.h>              /* para printf() */
#include <stdlib.h>             /* para malloc() e free() */

#define BIGINT_DATA_HEADER (UINT32_MAX) /* Valor usado para distinguir
                                           o cabeçalho dos outros nós. */
#define BIGINT_DATA_MAX (999999999) /* Valor máximo inteiro sem sinal
                                       que cada nó pode manter. */

typedef uint32_t u32;

typedef struct BigInt BigInt;
struct BigInt {
  u32 data;
  BigInt *next;
};

BigInt *bigint_new(void) {
  BigInt *x;

  x = malloc(sizeof(*x));
  x->data = BIGINT_DATA_HEADER;
  x->next = x;
  return x;
}

void bigint_prepend(BigInt *a, u32 data) {
  BigInt *x;

  x = bigint_new();
  x->data = data;
  x->next = a->next;
  a->next = x;
}

void bigint_append(BigInt *a, u32 data) {
  BigInt *x;

  if (a->next == a) {
    bigint_prepend(a, data);
    return;
  }

  for (x = a->next; x->next != a; x = x->next)
    ;

  x->next = bigint_new();
  x->next->data = data;
  x->next->next = a;
}

void bigint_delete(BigInt *a) {
  if (a->next->data != BIGINT_DATA_HEADER)
    bigint_delete(a->next);
  free(a);
}

u32 bigint_strlen(const char *s) {
  u32 len = 0;

  while (*s++)
    ++len;
  return len;
}

BigInt *bigint_from_str(const char *s) {
  BigInt *x;
  u32 len, val, unit, c;

  x = bigint_new();
  len = bigint_strlen(s);

  while (len > 0) {
    val = 0;
    for (unit = 1; unit < BIGINT_DATA_MAX && len > 0; unit *= 10, --len) {
      c = s[len-1];
      if (c < '0' || c > '9') {
        bigint_delete(x);
        return NULL;
      }
      val += unit * (c-'0');
    }
    bigint_append(x, val);
  }

  return x;
}

BigInt *bigint_add(BigInt *a, BigInt *b) {
  BigInt *x;
  u32 carry, total;

  x = bigint_new();
  a = a->next;
  b = b->next;
  carry = 0;

  while (a->data != BIGINT_DATA_HEADER &&
         b->data != BIGINT_DATA_HEADER) {
    total = a->data + b->data + carry;
    bigint_prepend(x, total % (BIGINT_DATA_MAX+1));
    x = x->next;
    a = a->next;
    b = b->next;
    carry = total / (BIGINT_DATA_MAX+1);
  }

  while (a->data != BIGINT_DATA_HEADER) {
    total = a->data + carry;
    bigint_prepend(x, total % (BIGINT_DATA_MAX+1));
    x = x->next;
    a = a->next;
    carry = total / (BIGINT_DATA_MAX+1);
  }

  while (b->data != BIGINT_DATA_HEADER) {
    total = b->data + carry;
    bigint_prepend(x, total % (BIGINT_DATA_MAX+1));
    x = x->next;
    b = b->next;
    carry = total / (BIGINT_DATA_MAX+1);
  }

  if (carry > 0) {
    bigint_prepend(x, carry);
    x = x->next;
  }

  return x->next;
}

#define bigint_print(a) bigint_print_(a->next)
void bigint_print_(BigInt *a) {
  if (a->next->data != BIGINT_DATA_HEADER)
    bigint_print_(a->next);
  printf("%09"PRIu32" ", a->data);
}

int main(int argc, char **argv) {
  BigInt *a, *b, *sum;

  if (argc != 3) {
    printf("Utilização: %s <NÚMERO-A> <NÚMERO-B>\n", argv[0]);
    return 1;
  }

  a = bigint_from_str(argv[1]);
  b = bigint_from_str(argv[2]);
  if (!a || !b) {
    printf("ERRO: Número inválido, certifique-se de que contém apenas dígitos decimais.\n");
    return 2;
  }

  sum = bigint_add(a, b);

  printf("a   = ");
  bigint_print(a);

  printf("\nb   = ");
  bigint_print(b);

  printf("\na+b = ");
  bigint_print(sum);
  printf("\n");

  bigint_delete(a);
  bigint_delete(b);
  bigint_delete(sum);
  return 0;
}

binarysearch.c

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

int
binarysearch(int *arr, int len, int val)
{
	int l, r, mid;
	l = 0;
	r = len-1;
	while (l <= r) {
		mid = l + (r-l)/2;
		if (arr[mid] > val)
			r = mid-1;
		else if (arr[mid] < val)
			l = mid+1;
		else
			return mid;
	}
	return -1;
}

int
linearsearch(int *arr, int len, int val)
{
	int i;
	for (i = 0; i < len; ++i)
		if (arr[i] == val)
			return i;
	return -1;
}

#define BEGIN_TIME begtm = (double)clock() / (CLOCKS_PER_SEC/1000)
#define END_TIME elapsedtm = (double)clock() / (CLOCKS_PER_SEC/1000) - begtm

int
main(int argc, char **argv)
{
	int *arr, len, i;
	double begtm, elapsedtm;

	if (argc != 3)
		return 1;
	len = atoi(argv[1]);
	arr = malloc(len * sizeof(int));
	for (i = 0; i < len; ++i)
		arr[i] = i;

	BEGIN_TIME;
	printf("bin: index %d\n", binarysearch(arr, len, atoi(argv[2])));
	END_TIME;
	printf("bin: %.4f ms\n", elapsedtm);

	BEGIN_TIME;
	printf("lin: index %d\n", linearsearch(arr, len, atoi(argv[2])));
	END_TIME;
	printf("lin: %.4f ms\n", elapsedtm);

	free(arr);
	return 0;
}

FooBar.c

#include <stdio.h>

int main(void)
{
	printf("hello, world!\n");
	return 0;
}

/* C operator precedence (RL is right-to-left associativity instead of LR)
+------------+---------------------------------------+
| precedence | operator                              |
+------------+---------------------------------------+
|  1         | x++ x-- x() x[] . -> (type){list}     |
|  2 (RL)    | ++x --x +x -x ! ~ (type) *x &x sizeof |
|  3         | * / %                                 |
|  4         | + -                                   |
|  5         | << >>                                 |
|  6         | < <= > >=                             |
|  7         | == !=                                 |
|  8         | &                                     |
|  9         | ^                                     |
| 10         | |                                     |
| 11         | &&                                    |
| 12         | ||                                    |
| 13 (RL)    | ?:                                    |
| 14 (RL)    | = += -= *= /= %= <<= >>= &= ^= |=     |
| 15         | ,                                     |
+----------------------------------------------------+

Floating-point numbers rules of thumb:
  - 'float' is generally 32 bits and can precisely hold
     approximately 7 decimal digits.
  - 'double' is generally 64 bits and can precisely
    hold approximately 15 decimal digits.
  - If you need exact decimal precision (e.g., for money),
    use integers or decimal libraries.
  - Floating-point is great for scientific calculations
    where small errors are acceptable.
*/

queue-simple-moving.c

#include <stddef.h>

int   printf(const char *fmt, ...);
void *malloc(size_t size);
void  free(void *p);

typedef struct {
  int *items;
  unsigned int rear, capacity;
} Queue;

void newq(Queue *q, unsigned int capacity) {
  q->rear = 0;
  q->capacity = capacity;
  q->items = malloc(capacity * sizeof(q->items[0]));
}

void delq(Queue *q) {
  free(q->items);
}

void enqueue(Queue *q, int val) {
  q->items[q->rear++] = val;
}

int dequeue(Queue *q) {
  unsigned int i;
  int val;

  val = q->items[0];
  for (i = 0; i < q->rear-1; ++i) {
    q->items[i] = q->items[i+1];
  }
  --q->rear;
  return val;
}

unsigned int lengthq(Queue *q) {
  return q->rear;
}

int emptyq(Queue *q) {
  return lengthq(q) == 0;
}

void printq(Queue *q) {
  unsigned int i;

  printf("[");
  if (!emptyq(q)) {
    for (i = 0; i < q->rear-1; ++i) {
      printf("%d,", q->items[i]);
    }
    printf("%d", q->items[i]);
  }
  printf("] (%u/%u)\n", lengthq(q), q->capacity);
}

int main(void) {
  Queue q;
  int i;

  newq(&q, 10);
  printq(&q);

  enqueue(&q, 0);
  printq(&q);

  enqueue(&q, 1);
  printq(&q);

  for (i = 2; i < 8; ++i)
    enqueue(&q, i);
  printq(&q);

  printf("-> %d\n", dequeue(&q));
  printf("-> %d\n", dequeue(&q));
  printq(&q);

  enqueue(&q, 8);
  enqueue(&q, 9);
  enqueue(&q, 10);
  enqueue(&q, 11);
  printq(&q);

  delq(&q);
  return 0;
}

queue-simple.c

#include <stddef.h>

int   printf(const char *fmt, ...);
void *malloc(size_t size);
void  free(void *p);

typedef struct {
  int *items;
  unsigned int front, rear, capacity;
} Queue;

void newq(Queue *q, unsigned int capacity) {
  q->front = q->rear = 0;
  q->capacity = capacity;
  q->items = malloc(capacity * sizeof(q->items[0]));
}

void delq(Queue *q) {
  free(q->items);
}

void enqueue(Queue *q, int val) {
  q->items[q->rear++] = val;
}

int dequeue(Queue *q) {
  return q->items[q->front++];
}

unsigned int lengthq(Queue *q) {
  return q->rear - q->front;
}

int emptyq(Queue *q) {
  return lengthq(q) == 0;
}

void printq(Queue *q) {
  unsigned int i;

  printf("[");
  if (!emptyq(q)) {
    for (i = q->front; i < q->rear-1; ++i) {
      printf("%d,", q->items[i]);
    }
    printf("%d", q->items[i]);
  }
  printf("] (%u/%u)\n", lengthq(q), q->capacity);
}

int main(void) {
  Queue q;
  int i;

  newq(&q, 10);
  printq(&q);

  enqueue(&q, 0);
  printq(&q);

  enqueue(&q, 1);
  printq(&q);

  for (i = 2; i < 8; ++i)
    enqueue(&q, i);
  printq(&q);

  printf("-> %d\n", dequeue(&q));
  printf("-> %d\n", dequeue(&q));
  printq(&q);

  enqueue(&q, 8);
  enqueue(&q, 9);
  printq(&q);

  delq(&q);
  return 0;
}

sort.c

#define N 10000
#define ORDER ORDER_RAND
/*
10000 integers in pseudorandom order
bubble             ...
bubble     105.2140 ms
insertion          ...
insertion   35.1320 ms
selection          ...
selection   50.3950 ms
shell              ...
shell        1.2220 ms
quick              ...
quick        0.6840 ms
qsort              ...
qsort        0.8410 ms
*/

#include <stdio.h>
#include <time.h>

#define ORDER_ASC 0
#define ORDER_DESC 1
#define ORDER_RAND 2

void
bubblesort(int *arr, unsigned int n)
{
	unsigned int i, j;
	int t;
	for (i = 0; i < n-1; ++i) {
		for (j = 0; j < n-i-1; ++j) {
			if (arr[j] > arr[j+1]) {
				t = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = t;
			}
		}
	}
}

void
insertionsort(int *arr, unsigned int n)
{
	unsigned int i, j;
	int t;
	for (i = 1; i < n; ++i) {
		j = i;
		t = arr[j];
		while (j >= 1 && t < arr[j-1]) {
			arr[j] = arr[j-1];
			--j;
		}
		arr[j] = t;
	}
}

void
selectionsort(int *arr, unsigned int n)
{
	unsigned int i, j, min;
	for (i = 0; i < n; ++i) {
		min = i;
		for (j = min+1; j < n; ++j)
			if (arr[j] < arr[min])
				min = j;
		if (min != i) {
			j = arr[i];
			arr[i] = arr[min];
			arr[min] = j;
		}
	}
}

void
shellsort(int *arr, unsigned int n)
{
	unsigned int i, j, h;
	int t;
	for (h = n/2; h; h /= 2) {
		for (i = h; i < n; ++i) {
			j = i;
			t = arr[j];
			while (j >= h && t < arr[j-h]) {
				arr[j] = arr[j-h];
				j -= h;
			}
			arr[j] = t;
		}
	}
}

unsigned int
partition(int *arr, unsigned int l, unsigned int r)
{
	unsigned int i, j;
	int t;
	i = l;
	for (j = l; j < r; ++j) {
		if (arr[j] <= arr[r]) {
			t = arr[j];
			arr[j] = arr[i];
			arr[i] = t;
			++i;
		}
	}
	t = arr[i];
	arr[i] = arr[r];
	arr[r] = t;
	return i;
}

void
quicksort_rec(int *arr, unsigned int l, unsigned int r)
{
	unsigned int i;
	if (l >= r)
		return;
	i = partition(arr, l, r);
	if (i > 0)
		quicksort_rec(arr, l, i-1);
	quicksort_rec(arr, i+1, r);
}

void quicksort(int *arr, unsigned int n) { quicksort_rec(arr, 0, n-1); }

unsigned int
rng(unsigned int seed)
{
	return (unsigned long long)seed * 48271 % 0x7fffffff; /* Park-Miller RNG */
}

unsigned int rand_seed;

void
genarr(int *arr, unsigned int n)
{
#if ORDER == ORDER_ASC
	while (n--)
		arr[n] = n;
#elif ORDER == ORDER_DESC
	unsigned int i = n-1;
	while (n--)
		arr[n] = i-n;
#elif ORDER == ORDER_RAND
	arr[n-1] = rng(rand_seed);
	while (--n)
		arr[n-1] = rng(arr[n]);
#endif
}

int
sorted(int *arr, unsigned int n)
{
	while (--n)
		if (arr[n] < arr[n-1])
			return 0;
	return 1;
}

#define LENGTH(arr) (sizeof(arr)/sizeof(arr[0]))

#define BEGIN_TIME begtm = (double)clock() / (CLOCKS_PER_SEC/1000)
#define END_TIME elapsedtm = (double)clock() / (CLOCKS_PER_SEC/1000) - begtm

int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; }

int
main(void)
{
	int arr[N];
	double begtm, elapsedtm;

	rand_seed = time(NULL);

#if ORDER == ORDER_ASC
	printf("%zu integers in ascending order\n", LENGTH(arr));
#elif ORDER == ORDER_DESC
	printf("%zu integers in descending order\n", LENGTH(arr));
#elif ORDER == ORDER_RAND
	printf("%zu integers in pseudorandom order\n", LENGTH(arr));
#else
#error "Order not defined"
#endif

	printf("bubble             ...\n");
	genarr(arr, LENGTH(arr));
	BEGIN_TIME; bubblesort(arr, LENGTH(arr)); END_TIME;
	printf("bubble    %9.4f ms\n", elapsedtm);
	if (!sorted(arr, LENGTH(arr)))
		return 1;

	printf("insertion          ...\n");
	genarr(arr, LENGTH(arr));
	BEGIN_TIME; insertionsort(arr, LENGTH(arr)); END_TIME;
	printf("insertion %9.4f ms\n", elapsedtm);
	if (!sorted(arr, LENGTH(arr)))
		return 1;

	printf("selection          ...\n");
	genarr(arr, LENGTH(arr));
	BEGIN_TIME; selectionsort(arr, LENGTH(arr)); END_TIME;
	printf("selection %9.4f ms\n", elapsedtm);
	if (!sorted(arr, LENGTH(arr)))
		return 1;

	printf("shell              ...\n");
	genarr(arr, LENGTH(arr));
	BEGIN_TIME; shellsort(arr, LENGTH(arr)); END_TIME;
	printf("shell     %9.4f ms\n", elapsedtm);
	if (!sorted(arr, LENGTH(arr)))
		return 1;

	printf("quick              ...\n");
	genarr(arr, LENGTH(arr));
	BEGIN_TIME; quicksort(arr, LENGTH(arr)); END_TIME;
	printf("quick     %9.4f ms\n", elapsedtm);
	if (!sorted(arr, LENGTH(arr)))
		return 1;

	void qsort(void *arr, size_t n, size_t sz, int (*cmp)(const void *, const void *));
	printf("qsort              ...\n");
	genarr(arr, LENGTH(arr));
	BEGIN_TIME; qsort(arr, LENGTH(arr), sizeof(int), cmp); END_TIME;
	printf("qsort     %9.4f ms\n", elapsedtm);
	if (!sorted(arr, LENGTH(arr)))
		return 1;

	return 0;
}