Êðàòêèå òåîðåòè÷åñêèå ñâåäåíèÿ

äâóõñâÿçàíûé ñïèñîê

            Íèæå ïðèâåäåí òåêñò ó÷åáíîé ïðîãðàììû ðàáîòû ñî ñâÿçàííûì ñïèñêîì. Ïðèíèìàÿ èìÿ ôàéëà â êà÷åñòâå ïàðàìåòðà êîìàíäíîé ñòðîêè, ïðîãðàììà ÷èòàåò ñîäåðæèìîå óêàçàííîãî ôàéëà è íà îñíîâå çàïèñåé ôîðìèðóåò äâóõñâÿçàííûé ñïèñîê. Çâåíî ñïèñêà çàäàåòñÿ ñòðóêòóðîé sp. Ñïèñîê ðàñïå÷àòûâàåòñÿ â ïðÿìîì è îáðàòíîì "íàïðàâëåíèè" è "óíè÷òîæàåòñÿ".

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

struct sp
{ sp * a_up; // óêàçàòåëü íà âûøå ñòîÿùåå çâåíî
  sp * a_down; // óêàçàòåëü íà íèæå ñòîÿùåå çâåíî
  char info[81]; // èíôîðìàöèîííàÿ ÷àñòü çâåíà
};

int main(int argv, char * * argc)
{
  int k_zap=0, k;
  char z;
  char nfile[80], buf[80];
  FILE *h;
  sp *first, *a_tek, *p, *a_next;
  if (argv > 1 ) strcpy(nfile,argc[1]);
  else { printf("Ïðè âûçîâå ïðîãðàììû íå óêàçàíî èìÿ ôàéëà äëÿ ÷òåíèÿ.....\n"); return -2;};


// èíèöèàëèçàöèÿ ñïèñêà.....
  first=NULL;
//======
  h=fopen(nfile, "r");
  if (h == NULL )
   { printf( "Cannot open input file <%s> \n", nfile); return -1; };
//======

next:
   if ( fgets(buf, 80, h) == NULL )
    { printf( "Êîíåö ôàéëà <%s> \n", nfile);
      goto endd;
    };
  k=strlen(buf)-1; if (k>=0) buf[k]='\0';
  k_zap++;
  printf("ïðî÷èòàëè %d <%s>\n", k_zap, buf);

// ïîìåñòèòü íîâóþ çàïèñü èç buf â ñïèñîê
  if (first == NULL )
   {
     p = new sp; // àäðåñ íîâîãî çâåíà
     p->a_up=NULL; // â íîâîì çâåíå óêàçàòåëè ââåðõ è âíèç - ïóñòûå
     p->a_down=NULL;
     p->info[0]='\0'; // â íîâîì çâåíå èíô. ñòðîêà ïóñòàÿ
     strcpy(p->info, buf); // çàïèñü èç áóôåðà â èíô. ñòðîêó ñïèñêà
     first=p; //ãîëîâà ñïèñêà

     printf("first=<%p>\n",first);
     printf("<%p><%p><%s>\n",p->a_up,p->a_down,p->info);
 
    }
  else
     {
// ïîèñê ïîñëåäíåãî çâåíà (ïîêàçàíî äëÿ ïðèìåðà, íà ïðàêòèêå â ýòîì íåò íåîáõîäèìîñòè)
       printf("***ïîèñê ïîñëåäíåãî çâåíà**\n");

       a_tek= first; // àäðåñ òåêóùåãî (ïåðâîãî) çâåíà
       p = a_tek->a_down; // àäðåñ "âíèç" èç òåêóùåãî çâåíà â óêàçàòåëå p
       printf("***òåêóùåå çâåíî <%p><%p><%s>\n",a_tek->a_up, a_tek->a_down, a_tek->info);
       printf("***óê. íà ñëåä. <%p>\n",p);
       while ( p != NULL )
         { a_tek=p; // àäðåñ ñëåäóþùåãî çâåíà
           p=a_tek->a_down; // àäðåñ "âíèç" èç òåêóùåãî çâåíà â óêàçàòåëå p
          };
// â a_tek - àäðåñ ïîñëåäíåãî çâåíà

       p = new sp; // àäðåñ íîâîãî çâåíà

       printf("tek=<%p> new=<%p>\n", a_tek, p);
       a_tek->a_down = p; //ññûëêà âíèç â ïðåäïîñëåäíåì çâåíå
       p->a_up= a_tek; //ññûëêà ââåðõ â ïîñëåäíåì (íîâîì) çâåíå
       p->a_down=NULL;
       strcpy(p->info, buf);
       printf("<%p><%p><%s>\n",p->a_up,p->a_down,p->info);

     };

goto next;


endd:
fclose(h);
getchar();
// ðàñïå÷àòêà ñïèñêà â ïðÿìîì íàïðàâëåíèè ......
clrscr();
a_tek= first;
printf("first=<%p>\n",first);
p = a_tek; // ->a_down;
while ( p != NULL )
{
printf("ADD=<%p> ZVENO=<%p><%p><%s>\n",p, p->a_up,p->a_down,p->info);
getchar();
a_tek= p;
p = a_tek->a_down;
};
getchar();


// ïîèñê ïîñëåäíåãî çâåíà (ïîêàçàíî äëÿ ïðèìåðà, íà ïðàêòèêå â ýòîì íåò íåîáõîäèìîñòè)
printf("***ïîèñê ïîñëåäíåãî çâåíà**\n");
a_tek= first; // àäðåñ òåêóùåãî (ïåðâîãî) çâåíà
p = a_tek->a_down; // àäðåñ "âíèç" èç òåêóùåãî çâåíà â óêàçàòåëå p
printf("***òåêóùåå çâåíî <%p><%p><%s>\n",a_tek->a_up, a_tek->a_down, a_tek->info);
printf("***óê. íà ñëåä. <%p>\n",p);
while ( p != NULL )
{ a_tek=p; // àäðåñ ñëåäóþùåãî çâåíà
p=a_tek->a_down; // àäðåñ "âíèç" èç òåêóùåãî çâåíà â óêàçàòåëå p
};
// â a_tek - àäðåñ ïîñëåäíåãî çâåíà

// ðàñïå÷àòêà ñïèñêà â îáðàòíîì íàïðàâëåíèè

p=a_tek->a_up; // àäðåñ "ââåðõ"
printf("*** ïîñëåäíåå çâ.<%p><%p><%s>\n",a_tek->a_up, a_tek->a_down, a_tek->info);
printf("***óê. íà ñëåä. ââåðõ <%p>\n",p);

while ( p != NULL )
{
printf("ADD=<%p> ZVENO=<%p><%p><%s>\n",p, p->a_up,p->a_down,p->info);
getchar();
a_tek= p;
p = a_tek->a_up;
};
getchar();

// óäàëèòü ñïèñîê èç ïàìÿòè
// ïîèñê ïîñëåäíåãî çâåíà
a_tek= first;
p = a_tek->a_down;
while ( p != NULL )
{
a_tek= p;
p = a_tek->a_down;

};

// â a_tek - àäðåñ ïîñëåäíåãî çâåíà
do
{
// àäðåñ ïðåäûäóùåãî çâåíà
a_next=a_tek->a_up;
delete a_tek;
a_tek=a_next;
}
while ( a_tek !=NULL);

printf("óñ¸¸¸¸\n");
return 0;
}