C/Funcións matriciais

C
	Funcións matriciais

Ordenar unha matriz

Para ordenar unha matriz, unha función só necesita saber a información básica dunha matriz, isto é: o seu enderezo e maila súa dimensión.

Método de busca sucesiva do mínimo

Este método consiste en percorrer a matriz e por cada posición (dende a primeira posición ata a penúltima) déixase ordenada esa posición. Compárase o dato nunha posición con todos os que lle seguen (é dicir, búscase o mínimo), e o mínimo almacénase na posición na que se está.

Buscar un elemento nunha matriz

No caso dunha función que busca un elemento nunha matriz, ademais do enderezo da matriz e maila súa dimensión, habemos de pasarlle o dato a buscar. E a función deberá devolver a posición do elemento (en caso de que o atope) ou informar de que non o atopou (mediante, por exemplo, "-1").

Busca secuencial

Un dos métodos para realizar a busca dun dato nunha matriz consiste en, partindo dunha matriz cuxos valores foron previamente ordenados de menor a maior, analizar as celas da matriz de principio a fin ata chegar a unha que non sexa menor que o dato a buscar. Chegados a este punto, compróbase se o dato da cela é o mesmo que o dato que se estaba buscando. Se o é, a matriz devolverá o número da cela do dato. Se non o é, a matriz devolverá -1. Se tras comprobar todas as celas resultou que todos os valores eran menores que o dato que se buscaba, a función devolverá tamén -1.

Este exemplo funciona para matrices do tipo float:

// Busca dun valor nunha matriz
// Asúmese que a matriz está ordenada de menor a maior
// A función devolve a posición do valor na matriz, ou se non o atopa: -1
unsigned short int BuscarNunhaMatriz(float * matriz, unsigned short int dimension, float dato)
{
  unsigned short int i;
  
  for(i=0;i<dimension;i++)
  {
    if(matriz[i]<dato);
    else
    {
      if(matriz[i]==dato) return i;
      else return -1;
    }
  }
  return -1;
}

Busca dicotómica

Existe outro algoritmo para buscar elementos nunha matriz, é a "busca dicotómica". A súa efectividade é superior á da "busca secuencial" no caso de matrices con moitas celas, por regra xeral. Para este método tamén fai falla que os valores da matriz estean ordenados de menor a maior. Cando máis tarda este algoritmo é cando o dato que se está buscando non está presente na matriz.

O método consiste en comparar o dato a buscar co elemento central da matriz. Nunha matriz con 10 elementos (0-9), o elemento central será o (9-0)/2, é dicir, o 4'5, que quedaría en 4. O algoritmo comparará o elemento número 4 co dato a buscar. Se o dato é maior, descartaranse os valores inferiores ao elemento co que se comparou. Se o dato é menor, descartaranse os valores superiores ao elemento co que se comparou. Deste xeito, descartaremos no primeiro paso a metade dos datos da matriz.

A continuación, cos restantes elementos (os que non foron descartados), procederase do mesmo xeito: seleccionarase o elemento central, compararase co dato a buscar, e de acordo co resultado da comparación, descartaranse uns elementos ou outros da matriz ordenada. Isto farase constantemente ata que, ou ben se atope un dato que sexa igual ao dato a buscar, ou ben o rango de posibles elementos iguais quede nun só elemento, e este elemento non sexa igual.

O seguinte código é un bo exemplo de dito algoritmo:

signed short int BuscaDicotomica(unsigned short int *matriz, unsigned short int dimension, unsigned short int dato)
{
  unsigned short int esquerda=0, dereita, pm;
  dereita=dimension-1;
  
  while(esquerda<=dereita)
  {
    pm=(esquerda+dereita)/2;
    if(matriz[pm]==dato) return pm;
    else
    {
      if(matriz[pm]>dato) dereita=pm-1;
      else esquerda=pm+1;
    }
  }
  return -1;
}

Buscar cantas veces aparece un certo carácter nunha cadea de texto

A seguinte función calcula o número de veces que un carácter aparece nunha cadea de caracteres.

unsigned short int OcorrenciasDunCaracter(char * cadea, char caracter)
{
	// Declaración de variables
	unsigned short int indice;
	unsigned short int ocorrencias;
	
	// Ciclo de busca do carácter
	for(i=0,ocorrencias=0;cadea[indice];indice++)
	{
		if(cadea[indice]=caracter) ocorrencias++;
	}
	
	// Devolución do resultado da busca
	return ocorrencias; // Veces que aparece o carácter
}

Nótese que non fai falla coñecer a dimensión da cadea de caracteres (matriz), dado que cando a cadea remate cadea[indice] vai ser igual a 0.

C
	Funcións matriciais