Operações com Lista Encadeada

Prévia do material em texto

Lista 4 – Busca e Ordenação de elementos Profa: Cristina Boeres (IC/UFF)
Lista 3
Estrutura de Dados: Lista encadeada
1. Considerando as seguintes declaração de uma lista encadeada, para representar o cadastro
de alunos de uma disciplina:
struct lista {
char nome[81];
char matricula[8];
char turma;
float p1;
float p2;
float p3;
struct lista* prox;
};
typedef struct lista Lista;
Implemente uma função que dada uma lista encadeada definida pela estrutura acima, ela
seja copiada para uma outra lista encadeada.
2. Considerando a estrutura especificada acima, especifique um algoritmo que crie uma nova
lista encadeada, com os elementos originais, mas ordenados de acordo com ordem cres-
cente de média do aluno, onde média do aluno é dada pela fórmula p1+p2+p33 .
3. Sejam duas listas encadeadas apontadas pelos ponteiros head1 e head 2. Especifique um
pseudo-algoritmo que identifique se as duas listas são iguais ou não. A estrutura de cada
elemento é:
typedef struct lista {
int valor;
struct lista* prox;
} Lista;
struct lista* head1;
struct lista* head2;
4. Seja a lista encadeada apontada por head1 conforme especificada no item anterior. Supo-
nha que a lista esteja ordenada. Especifique o pseudo-algoritmo de busca por valor. Se
existente, esse elemento deve ser atualizado para novo_valor. No entanto, para atualizar,
a lista encadeada ao final deve continuar ordenada.
Considere a seguinte estrutura: typedef struct no \{
(nas questões a seguir:) int v;
struct no* prox;
\} No;
5. Escreva uma função recursiva e outra não recursiva para contar o número de elementos na
lista encadeada apontada por p:
int nElementos(No* p);
1
Lista 4 – Busca e Ordenação de elementos Profa: Cristina Boeres (IC/UFF)
6. Escreva uma função recursiva e outra não recursiva que inverte a lista ligada apontada por
p. Nenhum nó auxiliar deve ser criado.
No* inverteLista(No* p);
7. Escreva uma função que recebe duas listas x = (x1, . . . , xn) e y = (y1, . . . , ym) como parâ-
metro e retorna uma lista formada pelos elementos de x e y intercalados. A lista resultante
será da forma (x1, y1, . . . , xm, ym, xm+1, ..., xn) se m < n ou (x1, y1, ..., xn, yn, yn+1, . . . ym)
se m > n. Nenhum nó adicional deve ser criado e as listas x e y devem ficar vazias ao final
(receber NULL).
No* intercalaListas(No** x, No** y);
Escreva uma versão recursiva e outra não recursiva.
2