Standard ISO C90 nie zezwala na definiowanie tablic o rozmiarze, który jest zmienną, a nie stałą. Bardziej elastyczne tablice potrzebne są m.in. gdy: (1) tworzymy tablicę o rozmiarze określonym w czasie wykonywania, (2) tworzymy tablicę o dużym rozmiarze. Za pomocą jawnej alokacji pamięci możemy w języku C ominąć ograniczenie stałego rozmiaru tablicy.
#include <stdlib.h> /* malloc(), calloc() */
#include <string.h> /* memset() */
#define MAXLINE 80
int n; /* dynamiczny rozmiar tablicy jednowymiarowej */
int *tablica; /* wskaznik do poczatku tablicy */
char line[MAXLINE];
/* Wczytanie rozmiaru tablicy. */
printf("Podaj rozmiar tablicy: ");
fgets(line, sizeof(line), stdin);
sscanf(line, "%d", &n);
/* Alokacja pamięci na tablicę. */
tablica = (int *) malloc(n * sizeof(int));
/* malloc() NIE inicjalizuje pamięci zerami.
Można od razu wymusić inicjalizację zerami:
tablica = (int *)calloc(n, sizeof(int));
Możemy też ręcznie wstawić zera do danego obszaru
pamięci (funkcja memset jest bardzo szybka):
memset(tablica, '\0', n*sizeof(int));
*/
if (tablica == NULL) {
fprintf(stderr, "Error: brakuje pamieci\n");
exit(1);
}
/* Zwolnienie pamięci. */
free(tablica);
tablica = NULL; /* dobry zwyczaj */
Zastosowanie funkcji scanf() - brak kontroli nad wielkością wczytywanego napisu. Funkcja scanf() jako granice napisu przyjmuje białe znaki. Problem: czytamy tylko jedno pole/słowo; w stdin ZAWSZE zostaje znak nowej linii i następne słowa.
#define MAXLINE 80
char imie[MAXLINE];
scanf("%s", line);
Zastosowanie fgets() [kontrola ilości wczytywanych znaków; wczytujemy też znak końca linii, jeżeli się zmieści] i ręczne usuwanie znaku nowej linii [ale jeżeli znak nowej linii nie zmieścił się w tablicy, to usuniemy czarny znak na końcu]. Problem: w stdin mogą zostać nieprzeczytane znaki, jeżeli się nie zmieszczą w macierzy.
#define MAXLINE 80 char imie[MAXLINE]; fgets(imie, sizeof(imie), stdin); imie[strlen(imie)-1] = '\0'; /* obcinamy '\n' */
Zastosowanie fgets() [kontrola ilości wczytywanych znaków] do wczytywania znaków do tymczasowej macierzy, a następnie bezpieczne czytanie jednego słowa za pomocą sscanf() Problem: w stdin mogą zostać nieprzeczytane znaki, jeżeli się nie zmieszczą w macierzy.
#define MAXLINE 80 char line[MAXLINE]; /* tymczasowa macierz */ char imie[MAXLINE]; fgets(line, sizeof(line), stdin); sscanf(line, "%s", imie); /* to już jest bezpieczne */
Bardziej elastyczne rozwiązanie to funkcja wczytująca całą linię do dynamicznego bufora, który powiększa się w czasie wczytywania znaków. Znak końca wiersza '\n' jest również wczytywany, a cały napis jest zakończony znakiem '\0'. W razie niepowodzenia z alokacją pamięci funkcja zwraca NULL.
#include <stdlib.h>
char *read_string(void)
{
int i, c;
int size = 2; /* aktualny rozmiar bufora */
char *p, *q; /* bufory na dane */
p = (char *) malloc(size * sizeof(char)); /* poczatkowy bufor */
if (p == NULL) {
return NULL;
}
i = 0;
while ((c = fgetc(stdin)) != EOF) {
p[i] = c;
++i;
if (i == size) {
size *= 2;
q = realloc(p, size*sizeof(char));
if (q == NULL) {
free(p); /* zwalniamy to co juz mamy */
return NULL;
} else {
p = q;
}
}
if (c == '\n') break; /* dla bezpieczenstwa na koncu po realloc() */
}
p[i] = '\0';
return p;
}
/* Korzystanie z funkcji
char *napis;
napis = read_string();
...
free(napis); Zwalniamy pamięć
napis = NULL; Dobry zwyczaj
*/
W katalogu domowym utworzyć podkatalog wektory. Utworzyć w nim pliki Makefile i main.c postaci:
/*
* main.c
*
* Program ilustrujacy korzystanie z tablic.
*/
#include <stdio.h>
void wczytaj(int v[], int n)
{
int i;
for (i = 0; i < n; ++i) {
printf("Podaj kolejny element tablicy: ");
scanf("%d", &v[i]);
}
return;
}
void wypisz(int v[], int n)
{
int i;
for (i = 0; i < n; ++i)
printf("v[ %d ]= %d\n", i, v[i]);
return;
}
int main(void)
{
const int N = 5;
int tablica[N];
wczytaj(tablica, N);
printf("\nPodales nastepujace liczby:\n");
wypisz(tablica, N);
return 0;
}
Skompilować i uruchomić program.
Zamiast wczytywać elementy macierzy, wypełnić ją kolejnymi liczbami całkowitymi (kolejnymi potęgami dwójki, wartościami silni, liczbami Fibonacciego).
W programie z poprzedniego zadania wszystkie funkcje umieścić w osobnych plikach i zmodyfikować plik Makefile.
Poprawić program dopisując następujące funkcje:
Deklaracje funkcji powinny mieć postać:
int suma(int v[], int n); int minimum(int v[], int n); int maksimum(int v[], int n); void odwracanie(int v[], int n);
Rozważyć iteracyjne i rekurencyjne wersje funkcji.
W katalogu domowym utworzyć podkatalog sortowanie. Utworzyć w nim pliki bubblesort.c i shellsort.c z funkcjami służącymi do sortowania tablic.
/*
* bubblesort.c
*
* Sortowanie tablicy metoda babelkowa (v[] rosnaco).
*/
#include "main.h"
void bubblesort(int v[], int n)
{
int i, j, tmp;
for (i = 1; i < n; ++i)
for (j = 1; j < n; ++j)
if (v[j-1] > v[j]) {
tmp = v[j-1];
v[j-1] = v[j];
v[j] = tmp;
}
return;
}
/*
* shellsort.c
*
* Porzadkowanie v[] rosnaco.
* Autor algorytmu: D. L. Shell (1959).
* W fazie poczatkowej porownuje sie elementy oddalone od siebie,
* a nie sasiadujace, jak w prostych metodach zamiany.
* Celem jest wyeliminowanie duzego balaganu, aby w pozniejszych
* fazach bylo mniej do zrobienia. Odlegosci miedzy porownywanymi
* elementami zmniejszaja się stopniowo do 1 i od tej chwili
* mamy metode sasiednich zamian.
*/
#include "main.h"
void shellsort(int v[], int n)
{
int gap; /* odstep pomiedzy porownywanymi elementami */
int i, j, tmp;
for (gap = n/2; gap > 0; gap /= 2)
for (i = gap; i < n; ++i) /* wzdluz elementow tablicy */
/* porownywanie pary elementow oddalonych od siebie o "gap" */
for (j = i-gap; j >= 0; j -= gap)
if (v[j] > v[j+gap]) {
tmp = v[j];
v[j] = v[j+gap];
v[j+gap] = tmp;
}
return;
}
Stworzyć odpowiednie pliki main.c, main.h i Makefile, aby powstał program sortujący tablice jedną z dostępnych metod. Wczytywanie tablicy i wypisywanie zawartości tablicy zapisać jako osobne funkcje.
W programach bardziej zaawansowanych do sortowania można wykorzystać biblioteczną funkcję qsort() po zadeklarowaniu
#include <stdlib.h> # Sortowanie przez qsort(). qsort(v, N, sizeof(int), cmp_int);
Potrzebna jest dodatkowa funkcja porównująca liczby całkowite.
/*
* cmp_int.c
*/
#include "main.h"
int cmp_int(const void *data1, const void *data2)
{
int *d1 = (int *) data1;
int *d2 = (int *) data2;
if (*d1 < *d2)
return -1;
else if (*d1 > *d2)
return 1;
else
return 0;
}
W katalogu domowym utworzyć podkatalog getline. Utworzyć w nim pliki Makefile i getline.c postaci:
/*
* getline.c
*
* Program czyta zbior wierszy i wypisuje najdluzszy. K i R str. 53.
*/
#include <stdio.h>
int getline(char napis[], int limit);
void copy(char dest[], char source[]);
int main(void)
{
const int MAXLINE = 80; /* dozwolona dlugosc wiersza */
int len; /* dlugosc biezacego wiersza */
int best; /* poprzednia maksymalna dlugosc */
char line[MAXLINE]; /* biezacy wiersz z wejscia */
char bestline[MAXLINE]; /* przechowywany maksymalny wiersz */
best = 0;
while ((len = getline(line, MAXLINE)) > 0)
if (len > best) {
best = len;
copy(bestline, line);
}
if (best > 0) /* znaleziono wiersz */
printf("%s", bestline);
printf("\n%d\n", best);
return 0;
}
/*
* Wczytuje wiersz do s[], podaje jego dlugosc.
* Wczytywanie bedzie przerwane po wypelnieniu tablicy.
*/
int getline(char napis[], int limit)
{
int c, i;
for (i = 0; (i < limit-1) && (c = fgetc(stdin)) != EOF
&& (c != '\n'); ++i)
napis[i] = c;
if (c == '\n') {
napis[i] = c;
++i;
}
napis[i] = '\0';
return i;
}
/* Przepisuje source[] do dest[]. */
/* dest[] musi byc dostatecznie duze. */
void copy(char dest[], char source[])
{
int i;
i = 0;
while ((dest[i] = source[i]) != '\0')
++i;
return;
}
Skompilować i uruchomić program.
Poprawić funkcję getline() tak, aby program zawsze poprawnie wypisywał rozmiar dowolnie długich wierszy i tylko tyle tekstu, ile jest możliwe.
W katalogu domowym utworzyć podkatalog komentarz. Utworzyć w nim pliki Makefile i komentarz.c z programem usuwającym wszystkie komentarze z dowolnego programu w języku C. Należy pamiętać o właściwym traktowaniu stałych znakowych i napisowych. Komentarze języka C nie mogą być zagnieżdżone.
W katalogu domowym utworzyć podkatalog napisy. Utworzyć w nim pliki Makefile, main.h, main.c, stringlen.c i reverse.c postaci:
/*
* main.c
*/
#include "main.h"
int main(void)
{
char zdanie[] = "abcdefgh"; /* inicjalizowanie tablicy znakowej */
printf("%s\n", zdanie);
reverse(zdanie);
printf("%s\n", zdanie);
return 0;
}
/*
* stringlen.c
*
* Funkcja zwracajaca dlugosc stringu. K i R str. 65.
*/
#include "main.h"
int stringlen(char s[])
{
int i = 0;
while (s[i] != '\0')
++i;
return i;
}
/*
* reverse.c
*
* Funkcja odwracajaca napis. K i R str. 93.
*/
#include "main.h"
void reverse(char s[])
{
int znak, i, j;
for (i = 0, j = stringlen(s)-1; i < j; ++i, --j) {
znak = s[i];
s[i] = s[j];
s[j] = znak;
}
return;
}
/* * main.h * * Plik naglowkowy. */ #include <stdio.h> int stringlen(char s[]); void reverse(char s[]);
Skompilować i uruchomić program. Poprawić program, aby wypisywał komunikaty informacyjne.
Poprawić program, aby prosił użytkownika o podanie napisu. W tym wypadku należy wcześniej ustalić rozmiar tablicy zdanie. Zbadać ograniczenia wywołania scanf("%s", zdanie). Zbadać, co mówią o wielkości napisu funkcje stringlen() i sizeof().