Сплошное и связное представления

 

 

 

 

 

struct List{

int data;

List *next;

};

 

 

• Добавить q после p

q->next=p->next;

p->next=q;

 

• Добавить q перед p

q->next=p->next;

p->next=q;

q->data<->p->data

 

• Удалить после p

q=p->next;

p->next=q->next;

free(q);

 

• Стеки

• Очереди

 

• Двусвязные и кольцевые списки

• Списки на массивах

A c b

0	a	-1
1
2

0	a	1
1	c	-1
2

0	a	2
1	c	-1
2	b	1

Добавление с поиском

 

struct List{

       int data;

       List *next;

};

List* Add(List* p, int x)

{

       List *q=p;

       while (q!=NULL)

       {

                   if (q->data==x)

                              break;

                   else

                              q=q->next;

       }

       if (q==NULL)

              q=(List*)malloc(sizeof(List));

                   q->data=x;

                   q->next=p;

                   p=q;

       }

       return p;

}

Сортировка вставками

 

Самоорганизующийся список (программа с фиктивным элементом)

 

 

struct List{

       int key;

       List * next;

};

 

List* CreateList(void)

{

       int i;

       List *p=NULL, *q;

 

       for (i=10; i>0; i--)

       {

                   q=(List*)malloc(sizeof(List));

                   q->key=i;

                   q->next=p;

                   p=q;

       }

       q=(List*)malloc(sizeof(List));

       q->next=p;

       return q;

}

 

void PrintList(List *s)

{

       s=s->next;

       while (s!=NULL)

       {

             printf("%d ", s->key);

                   s=s->next;

       }

printf("\n");

}

 

List* Search(List *s, int key)

{

       List *p1, *p2;

           

       p2=s;

       p1=s->next;

       while (p1!=NULL)

       {

                   if (p1->key==key)

                              break;

                   p2=p1;

                   p1=p1->next;

       }

       if (p1!=NULL)

       {

                   p2->next=p1->next;

                   p1->next=s->next;

                   s->next=p1;

       }

       return p1;

}

 

int main(void)

{

       List *s=CreateList(), *q;

       PrintList(s);

       q=Search(s,5);

       if (q==NULL)

                   printf("Element is absent\n");

       else

                   printf("%d\n", q->key);

       PrintList(s);

       getch();

       return 0;

}

Подсчет числа вхождений слов в файле (программа с барьером)

Поиск 5

5

c

л

о

в

о

 

с

л

о

в

о

0

 

struct List{

       char *word;

       int count;

       List *next;

};

static List* Last;

 

List* InitList(void)

{

       List *s;

 

       Last=s=(List*)malloc(sizeof(List));

       s->next=NULL;

       return s;

}

 

List* Add2List(List* s, char* word)

{

       List *q=s;

 

       Last->word=word;

       while (strcmp(q->word,word))

                   q=q->next;

       if (q!=Last)

                   q->count++;

       else

       {

                   q=(List*)malloc(sizeof(List));

                   q->word=word;

                   q->count=1;

                   q->next=s;

                   s=q;

       }

       return s;

}

 

void PrintList(List *s)

{

       while (s!=Last)

       {

                   printf("%s %d\n", s->word, s->count);

                   s=s->next;

       }

}

 

int main(void)

{

       List *s=NULL;

       FILE *f;

       char buf[80];

       char *word;

 

       if((f = fopen("wordlist.txt", "r")) == NULL)

                   printf("The file 'WordList' was not opened\n");

       s=InitList();

          fscanf(f, "%s", buf);

       while (!feof(f))

       {

                   word = (char *)malloc(strlen(buf)+1);

                   strcpy(word, buf);

                   s=Add2List(s, word);

       fscanf(f, "%s", buf);

       }

 

       PrintList(s);

       getch();

       return 0;

}

Сложение двух полиномов

 

2x⁸⁵ + 5x³ + 1

 

3x⁴ + x³

 

 

struct List{

int coef;

int pow;

List *next;

};

 

struct Queue{

List *first, *last;

};

 

void InitQueue(Queue *q)

{

q->first=q->last=(List*)malloc(sizeof(List));

}

 

void Add2Queue(Queue *q, int coef, int pow)

{

List *p;

 

p=(List*)malloc(sizeof(List));

p->coef=coef;

p->pow=pow;

p->next=NULL;

q->last->next=p;

q->last=p;

}

 

void ReadPol(FILE *f, Queue *q)

{

char buf[6];

int coef, pow;

 

do {

fscanf(f,"%s", buf);

       coef=atoi(buf);

fscanf(f,"%s", buf);

       pow=atoi(buf);

       Add2Queue(q, coef, pow);

} while(!feof(f));

}

void PrintPol(Queue *q)

{

List *p=q->first;

while (p!=q->last)

{

       p=p->next;

       printf("%d %d ", p->coef, p->pow);

}

printf("\n");

}

 

void SupPol(Queue *q1, Queue *q2, Queue *q3)

{

List *p1=q1->first->next, *p2=q2->first->next;

int s;

 

while (p1!=NULL && p2!=NULL)

{

       if (p1->pow > p2->pow)

       {

             Add2Queue(q3, p1->coef, p1->pow);

             p1=p1->next;

       }

       else

       {

             if (p1->pow < p2->pow)

             {

                   Add2Queue(q3, p2->coef, p2->pow);

                   p2=p2->next;

             }

             else

             {

                   s=p1->coef+p2->coef;

                   if (s!=0)

                   {

                        Add2Queue(q3, s, p1->pow);

                        p1=p1->next;

                        p2=p2->next;

                   }

             }

}

}

while (p1!=NULL)

{

       Add2Queue(q3, p1->coef, p1->pow);

       p1=p1->next;

}

 

while (p2!=NULL)

{

       Add2Queue(q3, p2->coef, p2->pow);

       p2=p2->next;

}

}

 

int main(void)

{

FILE *f;

Queue q1, q2, q3;

 

if((f = fopen("pol1.txt", "r")) == NULL)

       printf("The file 'pol1' was not opened\n");

InitQueue(&q1);

ReadPol(f,&q1);

fclose(f);

PrintPol(&q1);

 

if((f = fopen("pol2.txt", "r")) == NULL)

       printf("The file 'pol2' was not opened\n");

InitQueue(&q2);

ReadPol(f,&q2);

fclose(f);

PrintPol(&q2);

 

InitQueue(&q3);

SupPol(&q1, &q2, &q3);

PrintPol(&q3);

 

getch();

return 0;

}