14. Други реализации на линейни структури от данни

  Едносвързан списък.
#include <iostream>
using namespace std;

struct Node { char data; Node *next;};
Node *top;

bool insert(Node *pt, char c)  // insert after *pt
{ if (pt == NULL) return false;
  Node *node=new Node;
  if (node == NULL) return false;
  node -> data = c;
  node -> next = pt -> next;
  pt -> next = node;
  return true;
}
bool erase(Node *pt)     // erase pt->next
{ if ((pt == NULL) || (pt->next==NULL)) return false;
  Node *node=pt->next;
  pt->next=node->next;
  delete node;
  return true;
}
void print()
{ Node *pt=top;
  while (pt!=NULL)
  {
   cout << pt->data;
   pt=pt->next;
  }
  cout << "\n";
}
void create()
{ char ch;
  Node *pt=NULL, *ptold=NULL;
  top=NULL;
  while (cin >> ch)
  {
   pt=new Node;
//  if (pt==NULL) break;
   pt->data = ch;
   pt->next = NULL;
   if (top==NULL) top = pt;
   else ptold->next = pt;
   ptold = pt;
  }
}
int main()
{ create();        print();
  Node *pt=top; pt=pt->next;
  insert(pt, 'A'); print();
  erase(pt);       print();
  return 0;
}

  Опашка.
#include <iostream>
using namespace std;

struct Node { char data; Node *next;};
Node *top, *end;

bool append(char c) // insert after last
{
 if (end==NULL) return false;
 Node *node=new Node;
 if (node == NULL) return false;
 node -> data = c;
 node -> next = NULL;
 end -> next = node;
 end = node;
 return true;
}
bool erase()       // erase first
{
 if (top==NULL) return false;
 Node *node=top;
 top=top->next;
 delete node;
 return true;
}
void print()
{
 Node *pt=top;
 while (pt!=NULL)
 {
  cout << pt->data;
  pt=pt->next;
 }
 cout << "\n";
}
void create()
{
 char ch;
 Node *pt=NULL, *ptold=NULL;
 top=NULL;
 while (cin >> ch)
 {
  pt=new Node;
//  if (pt==NULL) break;
  pt->data = ch;
  pt->next = NULL;
  if (top==NULL) top = pt;
  else ptold->next = pt;
  ptold = pt;
 }
 end = pt;
}
int main()
{ create();    print();
  append('A'); print();
  erase();     print();
  return 0;
}

Топологично сортиране.
Дадено е частично наредено множество, т.е. между някои от елементите му е дадена релация  R, със следните 3 свойства:
1. ако xRy и yRz, то xRz (транзитивност);
2. ако xRy, то yRx не е вярно (несиметричност);
3. xRx не е вярно (нерефлексивност).
Задачата е да се изрази частичната наредба с линейна, т.е. да се подредят елементите на множеството в редица, така, че ако xRy, то x е преди y в редицата.
Алгоритъмът за решаване на задачата е от Н. Вирт и използва свързани списъци.

#include <iostream.h>
struct Trailer;

struct Leader {
       int key, count;
       Trailer *tr;
       Leader *next;
};
struct Trailer {
       Leader *id;
       Trailer *next;
};
Leader *head=new Leader;

void Create();
Leader *L(int);
void Zero();
void Tsort();

void main()
{ Create();
  Zero();
  Tsort();
}
void Create()
{
 Leader *p, *q;
 int x, y;
 head=0;
 while (cin >> x && cin >> y && !cin.eof())
 { p = L(x); q = L(y);
   Trailer *t = new Trailer;
   t->id = q;
   t->next = p->tr;
   p->tr = t;
   (q->count)++;
 }
}
Leader *L(int x)
{
 Leader *p = head, *q;
 q = p; // q is the last element of the list
 while (p)
 {
  if ((p->key) == x) return p;
  q = p; p = p->next;
 }
 p = new Leader;
 p->key = x; p->count = 0; p->tr = 0; p->next = 0;
 if (q) q->next = p;
 else   head = p;
 return p;
}
void Zero()
{
 Leader *p = head, *q;
 head = 0;
 while (p)
 { q = p; p = p->next;
/* nova zadacha za poleto next i ukazatelia head */
   if (!(q->count)) { q->next = head; head = q; }
 }
}
void Tsort()
{
 Trailer *t;
 Leader *q = head, *p;
 while (q)
 { cout << (q->key) << ' ';
   t = q->tr;
   q = q->next;
   while (t)
   { p = t->id; (p->count)--;
     if (!(p->count)) { p->next = q; q = p; }
     t = t->next;
   }
 }
}