Hashovací tabulka se separátním zřetězením – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Hashovací tabulka se separátním zřetězením – C / C++ – Fórum – Programujte.comHashovací tabulka se separátním zřetězením – C / C++ – Fórum – Programujte.com

 

Antonín Smékal
~ Anonymní uživatel
4 příspěvky
3. 5. 2018   #1
-
0
-

Dobrý den, máme za úkol navrhnout hashovací tabulku kde se kolize řeší zřetězením. Hashovací tabulku se mi povedlo funkčně sestavit, ale k tomu máme ještě udělat průměr a maximum uložených seznamů. Chtěl bych se Vás tedy zeptat zda byste mi neporadili jak na to. Předem děkuji za Váš čas. 

#include <stdio.h>
#include <string.h>
#include<stdlib.h>
#include<time.h>

#define min 5
#define max 20
#define M 10007
#define M2 10000

void InsertHash(char* str,unsigned int length,unsigned int i);
bool SearchHash(char* str,unsigned int length,unsigned int i);

struct ListItems
		{
			char* data;
			ListItems* next;
			ListItems* prev;
		};

struct List
{

		ListItems* head;

        List()
        {
            head = NULL;
        }


		bool Search(char* x)
		{
            ListItems* p;
            for (p = head; p != NULL; p = p->next)
                if (p->data == x)
                    return true;

            return false;
        }

		unsigned int  Insert(char *x)
            {

                    ListItems* p;
                    p = new ListItems;
                    p->data = x;
                    p->next = head;
                    if (head != NULL)
                        head->prev = p;
                    head = p;
                    p->prev = NULL;

            }

};

List HashTable[M];
List HashTable2[M2];

unsigned int DJBHash(const char* str,unsigned int length)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for (i = 0; i < length; ++str, ++i)
   {
      hash = ((hash << 5) + hash) + (*str);
   }

   return hash%M;

}

void InsertHash(char* str,unsigned int length ,unsigned int i )
{
	unsigned int hashKey = DJBHash(str,length);
	if(i==1)
        HashTable[hashKey].Insert(str);
    else if(i==2)
        HashTable2[hashKey].Insert(str);
}
bool SearchHash(char* str,unsigned int length,unsigned int i)
{
	unsigned int hashKey = DJBHash(str,length);
	if(i==1)
        return HashTable[hashKey].Search(str);
    if(i==2)
        return HashTable2[hashKey].Search(str);
}


char *stri(unsigned int length)
{
    static const char letters[] = "abcdefghijklmnopqrstuvwxyz";
	char *s = (char*)malloc((length + 1) * sizeof(char));
	for (unsigned int i = 0; i < length; ++i)
	{
		s[i] = letters[rand() % (sizeof(letters) - 1)];

	}

	s[length] = '\0';
	return s;


}

int tab1(void)
{
    unsigned int length,i,j,c;
    char *str;


	for (i = 0; i < 5004; i++)
	{
		length = min + rand() % (max + 1 - min);
        str = stri(length);

		if(SearchHash(str,strlen(str),1)==false)
        {
            InsertHash(str,strlen(str),1);

        }


	}

   for (i = 0; i < 2501; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),1)==false)
        {

            InsertHash(str,strlen(str),1);
        }



    }

     for (i = 0; i <2502 ; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),1)==false)
        {
            InsertHash(str,strlen(str),1);
        }



    }

    for (i = 0; i <2502 ; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),1)==false)
        {
            InsertHash(str,strlen(str),1);
        }



    }
    return 1;
}
int tab2(void)
{
    unsigned int length,i,j,c;
    char *str;

	for (i = 0; i < 5000; i++)
	{
		length = min + rand() % (max + 1 - min);
        str = stri(length);
		if(SearchHash(str,strlen(str),2)==false)
        {
            InsertHash(str,strlen(str),2);
        }

	}

   for (i = 0; i < 2500; i++)
    {
        length = min + rand() % (max+1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),2)==false)
        {
            InsertHash(str,strlen(str),2);
        }



    }

     for (i = 0; i <2500 ; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),2)==false)
        {
            InsertHash(str,strlen(str),2);
        }



    }

    for (i = 0; i <2500 ; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),2)==false)
        {
            InsertHash(str,strlen(str),2);
        }



    }
    return 1;
}

int main()
{
    srand(time(0));
    tab1();
    tab2();

	return 0;
}
Nahlásit jako SPAM
IP: 185.199.85.–
gna
~ Anonymní uživatel
1891 příspěvků
3. 5. 2018   #2
-
0
-

Tím se asi myslí maximum a průměr délek těch seznamů.

Takže si třeba do Listu přidej počitadlo vložených prvků.

Pak ještě tomu Listu doplň destruktor, ve kterém uvolníš alokovanou paměť (taky by bylo dobré pořešit kopírování). Z DJBHash vyhoď to modulo M, když zjevě používáš 2 různé hodnoty. A vykopej ty funkce InserHash/SearchHash a globální proměnné.

struct Table
{
	Table(size_t m)
	{
		lists.resize(m);
	}

	void Insert(char *str)
	{
		unsigned int hashKey = DJBHash(str, strlen(str)) % lists.size();
		lists[hashKey].Insert(str);
	}

	bool Search(char *str)
	{
		unsigned int hashKey = DJBHash(str, strlen(str)) % lists.size();
		return lists[hashKey].Search(str);
	}

	size_t MaxKeyUse()
	{
		size_t max = 0;
		for (List& list : lists)
			max = std::max(max, list.size);
		return max;
	}

private:
	std::vector<List> lists;
};

Table table1(M);
Table table2(M2);

table1.Insert(strdup("hrcprc"));
table1.MaxKeyUse();
Nahlásit jako SPAM
IP: 213.211.51.–
Antonín Smékal
~ Anonymní uživatel
4 příspěvky
3. 5. 2018   #3
-
0
-

#2 gna
Děkuji za odpověď, nešlo by to ale udělat bez použití vektorů. Vektory jsme ještě neměli nevím jestli by mi to uznali tu úlohu.

Nahlásit jako SPAM
IP: 185.199.85.–
gna
~ Anonymní uživatel
1891 příspěvků
3. 5. 2018   #4
-
0
-

Klidně tam udělej klasické pole, na tom nezáleží.

Nahlásit jako SPAM
IP: 213.211.51.–
gna
~ Anonymní uživatel
1891 příspěvků
3. 5. 2018   #5
-
0
-

   

struct Table
{
	Table(size_t m)
	{
		size = m;
		lists = new List[size];
	}

	~Table()
	{
		delete[] lists;
	}

	void Insert(char *str)
	{
		unsigned int hashKey = DJBHash(str, strlen(str)) % size;
		lists[hashKey].Insert(str);
	}

	bool Search(char *str)
	{
		unsigned int hashKey = DJBHash(str, strlen(str)) % size;
		return lists[hashKey].Search(str);
	}

	size_t MaxKeyUse()
	{
		size_t max = 0;
		for (size_t i = 0; i < size; i++)
			if (lists[i].size > max)
				max = lists[i].size;
		return max;
	}

private:
	List* lists;
	size_t size;
};
Nahlásit jako SPAM
IP: 213.211.51.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 37 hostů

Podobná vlákna

Tabulka — založil Jakub Vojáček

Tabulka — založil Karel

Tabulka — založil schokodidek

Tabulka — založil Karel

Tabulka — založil schokodidek

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý