Структури - 2
Chapter 6 - Structures
6.5 Self-referential Structures
6.6 Table Lookup
6.7 Typedef
6.8 Unions
6.9 Bit-fields

Самосвързани структури

Двоично дърво, търсещи дървета (дървета за търсене)

struct tnode {     /* the tree node: */
    char *word;    /* points to the text */
    int count;     /* number of occurrences */
    struct *tnode;  /* left child */
    struct *tnode;  /* right child */
};


Пример:
Да се преброи по колко пъти се среща дума в даден низ (текст).

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAXWORD 100

struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);

/* word frequency count */
main()
{
    struct tnode *root;
    char word[MAXWORD];

    root = NULL;
    while (getword(word, MAXWORD) != EOF)
        if (isalpha(word[0]))
            root = addtree(root, word);
    treeprint(root);
    return 0;
}


struct tnode *talloc(void);
char *strdup(char *);

/* addtree: add a node with w, at or below p */
struct treenode *addtree(struct tnode *p, char *w)
{
    int cond;
    if (p == NULL) {     /* a new word has arrived */
        p = talloc();     /* make a new node */
        p->word = strdup(w);
        p->count = 1;
        p->left = p->right = NULL;
    }
    else if ((cond = strcmp(w, p->word)) == 0)
        p->count++;     /* repeated word */
    else if (cond < 0)  /* less than into left subtree */
        p->left = addtree(p->left, w);
    else                /* greater than into right subtree */
        p->right = addtree(p->right, w);
    return p;
}


/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}


#include <stdlib.h>

/* talloc: make a tnode */
struct tnode *talloc(void)
{
    return (struct tnode *) malloc(sizeof(struct tnode));
}


char *strdup(char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 for '\0' */
    if (p != NULL)
        strcpy(p, s);
    return p;
}

Таблица за справки
Речник и двойки (ключ, елемент), търсене и директен достъп (индекс)
Хеширане - хеш стойност, хеш таблица

Пример:
Да се реализира таблица за замени:  идентификатор - стойност.

struct nlist {          /* table entry */   
    struct nlist *next; /* next entry in chain */   
    char *name;         /* defined name */
    char *defn;         /* replacement text */

#define HASHSIZE 101

static struct nlist *hashtab[HASHSIZE]; /* pointer table */

/* hash: form hash value for string s */
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}


/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)    
        if (strcmp(s, np->name) == 0)
            return np; /* found */
    return NULL; /* not found */
}


struct nlist *lookup(char *);
char *strdup(char *);

/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) { /* not found */
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
            return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    }
    else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
        return NULL;
    return np;
}

Typedef

typedef struct tnode *Treeptr;

typedef struct tnode {  /* the tree node: */
    char *word;         /* points to the text */
    int count;          /* number of occurrences */
    struct *tnode;      /* left child */
    struct *tnode;      /* right child */
} Treenode;


/* talloc: make a tnode */
struct tnode *talloc(void)
{
    return (struct tnode *) malloc(sizeof(struct tnode));
}

Treeptr talloc(void)
{
    return (Treeptr) malloc(sizeof(Treenode));
}


Обединения

union u_tag {
    int ival;
    float fval;
    char *sval;
} u;

if (utype == INT)
    printf("%d\n", u.ival);
if (utype == FLOAT)
    printf("%f\n", u.fval);
if (utype == STRING)
    printf("%s\n", u.sval);
else
    printf("bad type %d in utype\n", utype);


Битови полета
Флагове и битови полета

#define KEYWORD
#define EXTRENAL
#define STATIC

enum { KEYWORD = 01, EXTERNAL = 02, STATIC = 04 };

flags |= EXTERNAL | STATIC;

flags &= ~(EXTERNAL | STATIC);

if ((flags & (EXTERNAL | STATIC)) == 0) ...


struct {
    unsigned int is_keyword : 1;
    unsigned int is_extern : 1; u
    nsigned int is_static : 1;
} flags;

flags.is_extern = flags.is_static = 1;

flags.is_extern = flags.is_static = 0;

if (flags.is_extern == 0 && flags.is_static == 0) ...

---

Упражнение.
Да се дефинира структура emp, съхраняваща име на човек и заплата.
Да се дефинира масив от такива структури, да се чете таблица - име, заплата и да се изведе такава таблица с отбелязана най-висока (!) и най-ниска (?) заплата. Да се изчисли и средната заплата от въведените.

1. вариант: програма emp1.c - името в структурата е в char name[50];, таблицата се чете в масив от структури:
struct emp tab[100];
emp1.c

2. вариант: програма emp2.c - името в структурата е в char *name;, таблицата се чете в масив от структури:
struct emp tab[100];
emp2.c

3. вариант: програма emp3.c - името в структурата е в char *name;, таблицата се чете в масив от указатели към структури:
struct emp *tab[100];

4. вариант: програма emp4.c - името в структурата е в char name[50];, таблицата се чете в свързан списък, в дефиницията на структурата се добавя:
struct emp *next;

5. вариант: програма emp5.c - името в структурата е в char *name;, таблицата се чете в свързан списък, в дефиницията на структурата се добавя:
struct emp *next;
emp5.c

---