C++ ÷àñò.5 (Ñâîáîäíà ïàìåò)

C++ » C++

fix3d   òðóäíîñò:    âèäÿí: 4892

Óïðàæíåíèå 5-3. Ðàçãëåäàéòå àðãóìåíòèòå çà è ïðîòèâ ïîääúðæàíåòî íà ñëåäíèÿ IntList ÷ëåí.

IntItem *endList;

Êàê òîâà ìîæå äà ñå îòðàçè íà ðåàëèçàöèÿòà íà append()?

Ïîòðåáèòåëèòå íà ñïèñú÷íèÿ êëàñ òðÿáâà äà áúäàò â ñúñòîÿíèå äà ïîêàçâàò åëåìåíòèòå íà ñïèñúêà. Òîâà å íàïðàâåíî ïîñðåäñòâîì ÷ëåí-ôóíêöèÿòà display(). Åëåìåíòèòå íà ñïèñúêà ñå ïîêàçâàò â ñêîáè, ïî 16 íà ðåä. Òîâà èçãëåæäà òàêà

#include <stream.h>

const int lineLength = 16;
IntList

display() { // display val member of list
if ( list == 0 ) {
cout << "( empty )n";
return 0;
}

cout << "( ";
int cnt = 0; // number of items displayed
IntItem *pt = list;
while ( pt ) {
if ( ++cnt % lineLength == 1 && cnt != 1 )
cout << "n ";
cout << pt->val << " "; pt = pt->next;
}

cout << ")n";
return cnt;
}

Ïðîâåðêàòà

if ( ++cnt % lineLength == 1&& cnt != 1 )

ñëóæè äà ñå èçáåãíå ïîÿâàòà íà äÿñíà çàòâàðÿùà ñêîáà íà âñåêè ðåä îò ñàìî ñåáå ñè. Ïúëíàòà ñïåöèôèêàöèÿ íà çàãëàâíèÿ ôàéë IntList.h äî òîçè ìîìåíò èçãëåæäà òàêà

class IntList; // forward declaration
class IntItem {
friend class IntList;
private
IntItem(int v=0) { val = v; next = 0; }
IntItem *next;
int val;
};

class IntList {
public IntList(int val){ list = new IntItem( val );}
IntList() { list = 0; )
display();
insert( int = 0 );
append( int = 0 );
private
IntItem *atEnd();
IntItem *list;
};

Ïîòðåáèòåëÿò òðÿáâà äà áúäå â ñúñòîÿíèå äà îòñòðàíÿâà åëåìåíòè îò ñïèñúêà èëè äà èçòðèâà öåëèÿ ñïèñúê. Îò ïðîåêòàíòà íà êëàñà çàâèñè äàëè îïèòà çà îòñòðàíÿâàíå íà åëåìåíò îò ïðàçåí ñïèñúê äà ñå îïðåäåëÿ êàòî ãðåøêà. Íî è â äâàòà ñëó÷àÿ íà ïîòðåáèòåëÿ íà êëàñà å íåîáõîäèìà ôóíêöèÿòà-ïðåäèêàò isEmpty()

class IntItem { /* ... */ ;
class IntList {
public isEmpty() { return list == 0; }
// ...private
IntItem *list;
);

Èçòðèâàíåòî íà öåëèÿ ñïèñúê ìîæå äà ñå ðåàëèçèðà òàêà. Çàáåëåæåòå, ÷å ôóíêöèÿòà âðúùà áðîÿ íà îòñòðàíåíèòå åëåìåíòè.

IntList
remove() {
// delete the entire list
IntItem *tmp, *pt = list;
int cnt = 0;
while ( pt ) {
tmp = pt;
pt = pt->next;
++cnt;
delete tmp;
}

list = 0;
return cnt;
}

Ñúîòâåòíî, ïîòðåáèòåëÿò ìîæå äà èñêà äà îòñòðàíè âñè÷êè åëåìåíòè, êîèòî ñúäúðæàò îïðåäåëåíà ñòîéíîñò. Åäèí îñîáåí ñëó÷àé ïðè èçâúðøâàíåòî íà òîâà, å ñëó÷àÿò, êîãàòî òðÿáâà äà áúäå îòñòðàíåí ïúðâèÿ åëåìåíò íà ñïèñúêà. Òîãàâà òðÿáâà äà áúäå èçìåíåí è ñàìèÿò ÷ëåí íà list.
IntList
remove( int val ) {
// delete all enries with value val
IntItem *prv, *tmp, *pt = list;
int cnt = 0;
while ( pt & pt->val == val )
// while the first item on list == val {
tmp = pt->next; // save pointer to next
delete pt;
++cnt;
pt = tmp;
};

if ( (list = pt) == 0 ) return cnt; // list empty
prv = pt;
pt = pt->next;
while ( pt ) {
// iterate through list
if ( pt->val == val ) {
tmp = prv->next = pt->next;
delete pt;
++cnt;
pt = tmp;
}

else {
prv = pt;
pt = pt->next;
}

}; // end, while (pt)
return cnt;
}

Åäíà îñîáåíî ïîëåçíà ÷ëåí ôóíêöèÿ e length(). length() âðúùà áðîÿ íà åëåìåíòèòå íà ñïèñúêà. Çà ïðàçíèÿ ñïèñúê, ðàçáèðà ñå, òðÿáâà äà áúäå âðúùàíà ñòîéíîñò 0.

IntList
length() {
int cnt = 0;
IntItem *pt = list;
for ( ; pt; pt = pt->next, ++cnt );
// null statement
return cnt;
}

Åòî åäíà âòîðà ìàëêà ïðîãðàìà, êîÿòî äåìîíñòðèðà òåçè ÷åòèðè ÷ëåí-ôóíêöèè. (ðàçøèðåíàòà ñïåöèôèêàöèÿòà íà çàãëàâíèÿ ôàéë IntList.h, áåøå îñòàâåíà êàòî óïðàæíåíèå çà ÷èòàòåëÿ).

#include "IntList.h"
#include <stream.h>

const SZ = 12;
const ODD = 1;

main() {
IntList i1; // empty lilst
if ( i1.isEmpty() &&i1.length() == 0 &&i1.remove() == 0)
// test that empty list is handled
cout << "Empty List ok.n";
// every odd item is set to value of ODD
for ( int i = 0; i < SZ; ++i )
i1.append( i%2 == 0 ? i ODD );
i1.display(); // illustrate remove( someValue );
cout << i1.remove( ODD ) << " items of value "
<< ODD << " removed ";
i1.display();// illustrate remove()
int len = i1.length();
if ( i1.remove() == len )
cout << "All " << len << " items removed ";
i1.display();
return 0;
}

Êîãàòî êîìïèëèðàìå è èçïúëíèì òàçè ïðîãðàìà ùå ïîëó÷èì ñëåäíèòå ðåçóëòàòè

Empty List ok.

( 0 1 2 1 4 1 6 1 8 1 10 1 )
6 items of value 1 removed

( 0 2 4 6 8 10 )
All 6 items removed

( empty )

Óïðàæíåíèå 5-4. Ðåàëèçèðàéòå IntList removeFirst(). Íåêà ñòîéíîñòòà, êîÿòî âðúùà òàçè ÷ëåí-ôóíêöèÿ å ñòîéíîñòòà íà ÷ëåíà val. Óâåðåòå ñå, ÷å îáðàáîòâàòå è ñëó÷àÿ íà ïðàçåí ñïèñúê.

Óïðàæíåíèå 5-5. Ðåàëèçèðàéòå IntList removeLast(). Íåêà îòíîâî, ñòîéíîñòòà, êîéòî âðúùà òàçè ÷ëåí-ôóíêöèÿ äà áúäå ñòîéíîñòòà íà ÷ëåíà val. Óâåðåòå ñå, ÷å îáðàáîòâàòå è ñëó÷àÿ íà ïðàçåí ñïèñúê.

Åäíà ìíîãî ðàçïðîñòðàíåíà îïåðàöèÿ íàä ñïèñúöè å îáåäèíåíèå. Ñàìàòà îïåðàöèÿ å ïðîñòà, íî ÷åñòî ñå ãðåøè ïðè ðåàëèçàöèÿòà é. Íàïèñàíîòî ïî-äîëó âåðîÿòíî ùå ïðè÷èíè íà ïîòðåáèòåëÿ èçâåñòíè íåïðèÿòíîñòè

#include "IntList.h"

void IntLIst
concat( IntList& i1 ) {
( atEnd() )->next = i1.list; }

Ïðîáëåìúò ñå ñúñòîè â òîâà, ÷å äâà IntList îáåêòà ùå ñî÷àò åäíà è ñúùà ïîñëåäîâàòåëíîñò îò åëåìåíòè. Ìíîãî å âåðîÿòíî äâàòà êëàñîâè îáåêòà äà òðèÿò åëåìåíòè ïî ðàçëè÷íî âðåìå â ïðîãðàìàòà. Àêî âòîðèÿò îáåêò ñå îïèòâà äà ïîëó÷è äîñòúï äî åëåìåíòè, êîèòî âå÷å ñà èçòðèòè, ùå ñå ïîÿâÿò âèñÿùè ïñåâäîíèìè (óêàçàòåëè), êîèòî âåðîÿòíî ùå ïðè÷èíÿò ãðåøêè ïî âðåìå íà èçïúëíåíèå íà ïðîãðàìàòà. Àêî òîâà íå ñå ñëó÷è, ñúùåñòâóâà âúçìîæíîñò âòîðèÿò îáåêò ïî-êúñíî äà ñå îïèòà äà èçòðèå åëåìåíò, ÷èÿòî ïàìåò âå÷å äà ñå îêàæå îòäåëåíà çà íÿêàêâà ñúâñåì ðàçëè÷íà öåë. Îòíîâî å ñúâñåì âåðîÿòíî ïðîãðàìàòà äà áúäå ïðåêúñíàòà ïî âðåìå íà èçïúëíåíèå. Åäíî îáùî ðåøåíèå å äà ñå îñèãóðè áðîÿ÷-ïñåâäîíèì, çà âñåêè åëåìåíò íà ñïèñúêà.

Âñåêè ïúò, êîãàòî ñå îòñòðàíÿâà åëåìåíò,áðîÿ÷úò-ïñåâäîíèì ñå íàìàëÿâà ñ 1. Êîãàòî òîé ñòàíå 0, åëåìåíòúò ìîæå äà áúäå èçòðèò ôàêòè÷åñêè. Åäíà àëòåðíàòèâíà ñòðàòåãèÿ å äà ñå êîïèðà âñåêè åëåìåíò, êîéòî ó÷àñòâóâà â îáåäèíåíèåòî. Òàçè âåðñèÿ íà concat() èçãëåæäà òàêà

void IntList
concat( IntList& i1)

{ // append i1.list to invoking list object
IntItem *pt = i1.list;
while ( pt ) {
append( pt->val );
pt = pr->next;
} }

Åäíà èíòåðåñíà îïåðàöèÿ íàä ñïèñúöè å îáðúùàíå.  òîçè ñëó÷àé ñïèñúêúò ñå îáðúùà êàòî ïîñëåäíèÿò åëåìåíò çàñòàâà â íà÷àëîòî è îáðàòíî. Âúïðåêè, ÷å ðåàëèçàöèÿòà íà îïåðàöèÿòà å êðàòêà, óêàçàòåëèòå ñå îáðàáîòâàò ïî èíòåðåñåí íà÷èí è å ëåñíî äà ñãðåøèòå àêî ñåãà çàïî÷âàòå äà ïðîãðàìèðàòå ñúñ ñïèñúöè. Åòî è ðåàëèçàöèÿòà

void IntList
reverse() {
IntItem *pt, *prv, *tmp;
prv = 0;
pt = list;
list = atEnd();
while ( pt != list ) {
tmp = pt->next;
pt->next = prv;
prv = pt;
pt = tmp;
}

list->next = prv;
}

Ñëåäíàòà ìàëêà ïðîãðàìà èëþñòðèðà concat() è reverse()

#include "IntList.h"
const SZ = 8;
main() {
IntLIst i1, i12;
for ( int i = 0; i < SZ/2; ++i ) i1.append( i );
for ( i = SZ/2; i < SZ; ++i ) i12.append( i );

i1.display();
i12.display();
i1.concat( i12 );
i1.display(); // concat
i1.reverse();
i1.display(); // reverse
return 0;
}

Êîãàòî êîìïèëèðàìå è èçïúëíèì òàçè ïðîãðàìà ùå ïîëó÷èì ñëåäíèÿ ðåçóëòàò

( 0 1 2 3 )
( 4 5 6 7 )
( 0 1 2 3 4 5 6 7 ) ( 7 6 5 4 3 2 1 0 )

Óïðàæíåíèå 5-6. Ðåàëèçèðàéòå ÷ëåí ôóíêöèÿ çà äîáàâÿíå íà åëåìåíò â ñïèñúêà, òàêà ÷å IntItem, êîéòî ãî ñëåäâà äà èìà ñòîéíîñò, êîÿòî äà å ïúðâàòà ñòîéíîñò â ñïèñúêà, ïî-ãîëÿìà îò ñòîéíîñòòà íà äîáàâÿíèÿ åëåìåíò.

Óïðàæíåíèå 5-7. Ïðîìåíåòå IntList, òàêà ÷å äà ïðèòåæàâà è åëåìåíò IntItem *endList; Êîãàòî èçìåíÿòå public ÷ëåí ôóíêöèè ñå óâåðåòå, ÷å íå íàðóøàâàòå íåùî â ñúùåñòâóâàùèÿ òåêñò (òðèòå ïðèìåðíè ïðîãðàìè â òîçè ðàçäåë).

Ñòðàíèöè: «1 2 3 4 5 6 »