C++ част.5 (Свободна памет)

fix3d трудност:

видян: 24145

Упражнение 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 »

Сподели урока:

C++ част.5 (Свободна памет)

Регистрирайте се, за да добавите коментар