Реализовать в виде класса абстрактный тип данных ..., C++ Опции

[KerK]

Помогите разобраться с задачей, хотя бы алгоритм...

Реализовать в виде класса на языке С++ абстрактный тип данных множество с операциями добавления элемента, удаления, проверки наличия и т.д. Для хранения элементов множества использовать хеш-таблицу, элементами множества являются строки ограниченной длины.

[Алена]

Вот набросок без использования STL:

#include <string.h>
#include <assert.h>
#include <iostream.h>


class theString {

  friend ostream& operator << (ostream&, const theString&);

public:
  theString();
  theString(int length = 50);
  theString(const char *s);
  theString(const theString &s);

  operator == (const theString &s) {
    return (strcmp(str, s.str) == 0);
  }

private:
  int len;
  char *str;
};

ostream& operator << (ostream &os, const theString &s) {
  os << s.str;
  return os;
}

theString :: theString(int length) {

  str = new char[ (len = length) + 1];
  assert(str != 0);
  str[0] = '\0';

}
theString :: theString(const char *s) {

  str = new char[ (len = strlen(s)) + 1];
  assert(str != 0);
  strcpy(str, s);

}
theString :: theString(const theString &s) {

  str = new char[ (len = s.len) + 1 ];
  assert(str != 0);
  strcpy(str, s.str);

}

/* ***** */

class theSet {

  friend ostream& operator << (ostream&, const theSet&);
public:
  theSet()
  {
  }

  void operator += (const theString &s) {
    if(!info.isPresent(s)) info.append(s);
  }
  void operator -= (const theString &s) {
    info.remove(s);
  }
  int operator == (const theString &s) {
    return info.isPresent(s);
  }
  int operator != (const theString &s) {
    return (!(info.isPresent(s)));
  }

private:

  class List {

    friend ostream& operator << (ostream&, const List&);
  public:
    List() {
      start = 0; finish = 0;
    }
    ~List();

    void append(const theString &s);
    void remove(const theString &s);

    int isPresent(const theString &s);

    void print();

  private:

    class ListItem {
    public:
      ListItem(const theString &s, ListItem *item = 0) :
        value(s), next(item)
        {
        }

      theString value;
      ListItem *next;
    };

    ListItem *start, *finish;
  };

  List info;

};

theSet :: List :: ~List() {

  theSet :: List :: ListItem *pt = start;
  while(pt) {
    ListItem *p = pt;
    pt = pt -> next;
    delete p;
  }
  start = finish = 0;

}

void theSet :: List :: append(const theString &s) {

  theSet :: List :: ListItem *pt;
  pt = new theSet :: List :: ListItem(s);
  assert(pt != 0);

  if(start == 0) start = pt;
  else finish -> next = pt;

  finish = pt;

}
void theSet :: List :: remove(const theString &s) {

  theSet :: List :: ListItem *pt;
  pt = start;
  while(pt && pt -> value == s) {
    theSet :: List :: ListItem *T = pt -> next;
    delete pt;
    pt = T;
  }

  if(!(start = pt)) {
    finish = 0;
    return;
  }

  theSet :: List :: ListItem *prv = pt;
  pt = pt -> next;
  while(pt) {
    if(pt -> value == s) {

      prv -> next = pt -> next;
      if(finish == pt) finish = prv;
      delete pt;
      pt = prv -> next;

    }
    else {
      prv = pt;
      pt = pt -> next;
    }
  }
}
int theSet :: List :: isPresent(const theString &s) {

  if(start == 0) return 0;
  if(start -> value == s || finish -> value == s) return 1;

  theSet :: List :: ListItem *pt;
  pt = start -> next;
  for(; pt && pt != finish; pt = pt -> next)
    if(pt -> value == s) return 1;

  return 0;

}

ostream& operator << (ostream &os, const theSet :: List &lst) {

  os << "[ ";
  for(theSet :: List :: ListItem *pt = lst.start;
      pt; pt = pt -> next) os << pt -> value << " ";
  os << "]" << endl;

  return os;
}

ostream& operator << (ostream &os, const theSet &set) {

  os << set.info;
  return os;
}




int main() {

  theSet my_set;
  my_set += "first";
  my_set += "second";
  my_set += "third";
  my_set += "fourth";

  cout << my_set;
  my_set -= "second";
  cout << my_set;

  if(my_set == "third")
    cout << "present" << endl;

  if(my_set != "_third")
    cout << "not present" << endl;

  return 0;

}

Здесь элементы theSet хранятся в виде односвязного списка, просто замени List на HashTable (ссылку тебе дали выше, реализация - за тобой...), и все... Можно класс theSet сделать шаблонным, кстати, чтоб можно было работать и со строками, и с числами, и вообще со всем, с чем хочется...

Опять же, можно разнести эту программу по разным файлам, я привела "все в одном" только для облегчения тестирования...