Insertion Sort

else { // se já houver raiz

// percorre a lista encadeada, comecando da raiz. Inicialmente, não

// há nó anterior

Anterior = NULL;

Atual = Raiz;

while (Atual!=NULL) {

if (strcmp(Atual->nome,nome)>=0) break; // se o nó atual é

// lexicograficamente superior,

// pára

else {

Anterior = Atual;

Atual = Atual->proximo;

}

}

if (Atual != NULL) // só faz a comparação abaixo se existe o nó Atual

if (strcmp(Atual->nome,nome)==0) {

printf ("Nome já existente!\n");

return;

}

// aloca memória para o novo nó

Inserido = (No *)malloc(sizeof(No));

// coloca o nó na lista encadeada, mudando o ponteiro para o próximo no

// do nó anterior

if (Atual != Raiz)

Anterior->proximo = Inserido;

else // se atual é nó raiz, atualiza raiz

Raiz = Inserido;

// coloca dados no nó Inserido

strcpy (Inserido->nome,nome);

strcpy (Inserido->telefone,telefone);

// indica que o próximo nó do nó inserido é o nó apontado por Atual

Inserido->proximo = Atual;

}

}