Dsa info programikes
Iš MIF SA wiki.
[redaguoti] Programykės
Keli programų archyvai:
Žodinių failų generatorius
#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
#define MAX_LENGTH 15;
#pragma hdrstop
#pragma argsused
int main(int argc, char* argv[]){
int wordCount;
char *symbols = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
ostringstream outstream;
if (argc != 3){
cout << "Usage : ./program filename wordcount" << endl;
return 1;
}
else{
if ((wordCount = atoi(argv[2])) == 0){
cout << "Usage : ./program filename wordcount" << endl;
return 1;
}
}
ofstream file(argv[1]);
srand((unsigned) time(NULL));
for (int count = 0; count < wordCount; count++){
int rnd = 1 + rand() % MAX_LENGTH;
for (int length = 0; length < rnd; length++){
outstream << symbols[rand() % strlen(symbols)];
}
file << outstream.str() << endl;
outstream.clear();
outstream.str("");
}
file.close();
return 0;
}
/*
Pirmoji DSA uzduotis (19numeris).
Uzduoties salyga:
"Parasyti programa iterpimo rusiavimo algoritmui, kuri dirba daug
kartu ir rusiuoja ivairiu dydziu failus, matuodama darbo laika,
skaiciuodama lyginimo operaciju kieki, ir sudaro tokiu darbo laiku
ir kiekiu pasiskirstyma."
*/
#include <iostream>
#include <string>
#include <fstream> /*Panaudojame ifstream ir ofstream.*/
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std; /*Panaudota standartinem klasem (vektor, string).*/
/*----------------------------------------------------------------------------*/
unsigned int InsertionSort(vector<string>& Vector){
string temp;
int j = 0;
unsigned int palyginimai = 0;
for (unsigned int i = 1; i < Vector.size(); ++i){
temp = Vector.at(i);
for (j = i - 1; (j >= 0) && (temp < Vector.at(j)); j--){
Vector.at(j + 1) = Vector.at(j);
/* Metodas .at(i) analogiskas [i]; skirias tik tuo, kad jis tikrina diapazona.*/
palyginimai++;
}
Vector.at(j + 1) = temp; /*Pereinam prie kito vektoriaus nario.*/
}
return palyginimai;
}
/*----------------------------------------------------------------------------*/
int main(int argc, char* argv[]){ /*Masyvu masyvas.*/
string readString; /*Eilute, kuria siuo metu nuskaitem is bylos.*/
vector<string> stringVector; /*Sis vektorius saugos eilutes is bylos.*/
/*Kintamo didzio masyvas, automatiskai keicia dydi.*/
if (argc != 3){
cout << "Aj aj aj! Klaida klaida klaida!: ./programa duom rez " << endl;
return 1;
}
ifstream inputFile(argv[1]); /*Input file stream.*/
if (!inputFile){
cout << "Nepavyko atidaryti bylos \"" << argv[1] << "\"" << endl;
return 1; /*Iseinam is programos.*/
}
while (inputFile >> readString){ /*Nuskaitom eilute.*/
stringVector.push_back(readString);
/*push_back- paskutiniaja nuskaityta eilute nukisa i vektoriaus gala.*/
}
inputFile.close(); /*Uzdarom byla.*/
ofstream statFile("Statistika", ios_base::app);
/*Parametras nurodantis kaip atidaryt byla.*/
/*ios_base::app reiskia kad irasome i bylos gala.*/
time_t start = time(NULL); /*NULL- paimt dabartini laika.*/
/*Struktura, sauganti laika.*/
statFile << "Rusiuojame " << stringVector.size() << " zodziu, palyginimu skaicius = " << InsertionSort(stringVector) << endl;
/*size metodas nurodo koks vektoriaus dydis.*/
statFile << "Truko " << difftime(time(NULL), start) << " sekundziu" << endl;
statFile.close();
ofstream outputFile(argv[2]);
for (int sz = 0; sz < stringVector.size(); sz++){
outputFile << stringVector.at(sz) << endl;
}
outputFile.close();
return 0;
}
Tik kaži ar tinkamai jinai veikia, nes, kažkokia chaoso teorija aprašytą :)
/*
Antroji DSA uzduotis (19 numeris).
Uzduoties salyga:
"Realizuoti skaitmenines paieskos medi kintamo ilgio zodziams."
*/
#include <iostream>
#include <fstream>
#include <string>
#include "2uzd_19var.h"
using namespace std;
/*----------------------------------------------------------------------------*/
int getBit(string key, int b){
int i = *((int*)&key);
return (i >> b) & 1;
}
/*----------------------------------------------------------------------------*/
RadixTree* RadixTreeCreate(){
RadixTree* newTree;
TreeNode* node;
//newTree = (RadixTree*) malloc(sizeof(RadixTree));
newTree = new RadixTree;
//node = newTree->z = (TreeNode*) malloc (sizeof(TreeNode));
node = newTree->z = new TreeNode;
node->left = node;
node->right = node;
//node = newTree->head = (TreeNode*) malloc (sizeof(TreeNode));
node = newTree->head = new TreeNode;
node->key = "";
node->right = newTree->z;
return newTree;
}
/*----------------------------------------------------------------------------*/
RadixTree* RadixInsert(string v, RadixTree* tree){
TreeNode* x;
TreeNode* p;
x = tree->head->right;
//int b;
int b = sizeof(string) * 8 - 1;
//b = maxb;
if ( x != tree->z ){ // jei medis ne tuscias!
do{
p = x;
if ( getBit(v,b)==0 ) x = x->left;
else x = x->right;
b--;
}
while ( x != tree->z );
}
//x = (TreeNode*) malloc (sizeof(TreeNode));
x = new TreeNode;
x->key = v;
x->left = tree->z;
x->right = tree->z;
if ( tree->head->right != tree->z ){
if ( getBit(v,b+1)==0 ) p->left = x;
else p->right = x;
}
else tree->head->right = x;
return tree;
}
/*----------------------------------------------------------------------------*/
TreeNode* RadixSearch(string v, RadixTree* tree){
TreeNode* x;
x = tree->head->right;
tree -> z -> key = v;
int b;
b = sizeof(string) * 8 - 1;
//b = maxb; // maxb konstanta, nusako kiek bitu maximum gali buti
if ( v != x->key ){
do{
if ( getBit(v,b)==0 ) x = x->left;
else x = x->right;
b--;
}
while ( v != x->key );
}
return x;
}
/*----------------------------------------------------------------------------*/
void printRadixTree(RadixTree* tree, TreeNode* x){
if (x != tree->z){
printRadixTree(tree, x->left);
cout << x->key << "\n";
printRadixTree(tree, x->right);
}
}
/*----------------------------------------------------------------------------*/
int main( ){
RadixTree* newtree;
TreeNode* x;
int size;
string zodis;
bool testi;
newtree = RadixTreeCreate();
ifstream inFile("duom.txt");
if ( !inFile ){
cout << inFile << " couldn't be opened for writing!\n";
exit(0);
}
inFile >> size;
for(int i=0; i < size; i++){
inFile >> zodis;
RadixInsert(zodis,newtree);
}
inFile.close();
printRadixTree(newtree, newtree->head->right);
while(testi){
cout << "Iveskite zodi, kuri pageidaujate rasti medyje: (0 - pabaiga!)\n";
cin >> zodis;
if(zodis == "0")
return 0;
x = RadixSearch(zodis,newtree);
if ( x!= newtree->z )
cout << "Elementas " << zodis << " yra medyje!" << "\n";
else cout << "Elemento " << zodis << " medyje nera!" << "\n";
}
return 0;
}
Headeris šios programos:
#include <string>
using namespace std;
const int maxb = 4;
typedef struct TreeNode {
string key;
struct TreeNode* left;
struct TreeNode* right;
}
TreeNode;
typedef struct RadixTree {
TreeNode* head;
TreeNode* z;
}
RadixTree;
