Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
ЗВІТ
З лабораторної роботи №7,8,9,10
З дисципліни: «Програмування ч.4»
Мета:
7) Реалізувати ДЕК на основі масиву, тобто дек – це така структура даних яка поєднує в собі чергу і стек і додавати і вилучати елементи можна з двох кінців.
8) Підрахувати кількість вершин в дереві
9) Визначити чи в заданому графі присутній цикл з відємною сумою
10) З’ясувати чи присутнє слово «abcd» у введеному рядку
Блок-схема:
7)
8)
9)
10)
Лістинг програм:
CTree* tree; // pointer by CTree
CDec* dec; // pointer by CDec
int iCount = 0;
int iLeafs;
int* piTree[3];
int iRoot;
int* piDec;
case 7:
/*===============================[ LABA #7 ]====================*/
cout << endl;
cout << "\t\t\t\tLaboratory work #7" << endl;
cout << endl;
cout << "Реалiзувати ДЕК на масивi" << endl;
cout << endl;
/*===============================[ OBJECT-ORIENTED METHOD ]======*/
cout << endl;
cout << "\t\t\t\tObject-oriented method" << endl;
cout << endl;
cout << "n = ";
cin >> iN;
dec = new CDec(iN);
dec->DEC();
system("pause");
/*===============================[ PROCEDURE-ORIENTED METHOD ]===*/
cout << endl;
cout << "\t\t\tProcedure-oriented method" << endl;
cout << endl;
cout << "n = ";
cin >> iN;
piDec = new int[iN];
DEC(piDec, iN);
system("pause");
system("cls");
break;
/*===============================[ END LABA #7 ]================*/
case 8:
/*===============================[ LABA #8 ]====================*/
cout << endl;
cout << "\t\t\t\tLaboratory work #8" << endl;
cout << endl;
cout << "Пiдрахувати кiлькiсть вершин в деревi." << endl;
cout << endl;
/*===============================[ OBJECT-ORIENTED METHOD ]======*/
cout << endl;
cout << "\t\t\t\tObject-oriented method" << endl;
cout << endl;
cout << "n = ";
cin >> iN;
tree = new CTree(iN);
tree->show_tree();
iLeafs = tree->Seek_Leafs(tree->Get_root());
cout <<"Вершин: " << tree->Get_count()-iLeafs << endl;
system("pause");
/*===============================[ PROCEDURE-ORIENTED METHOD ]===*/
cout << endl;
cout << "\t\t\tProcedure-oriented method" << endl;
cout << endl;
cout << "n = ";
cin >> iN;
for (int i=0;i<3;i++)
{
piTree[i] = new int[iN];
}
Enter_tree(piTree,iN, &iRoot);
show_tree(piTree,iN);
iLeafs = Seek_Leafs(piTree,iRoot,&iCount);
cout <<"Кiлькiсть вершин: " << iCount-iLeafs << endl;
system("pause");
system("cls");
break;
case 9:
/*===============================[ LABA #9 ]====================*/
cout << endl;
cout << "\t\t\t\tLaboratory work #9" << endl;
cout << endl;
cout << "Умова: Перевiрити чи є відємний цикл." << endl;
cout << endl;
/*===============================[ OBJECT-ORIENTED METHOD ]======*/
cout << endl;
cout << "\t\t\t\tObject-oriented method" << endl;
cout << endl;
cout << "n = ";
cin >> iN;
graf = new CGraf(iN);
if (graf->Seek())
{
cout << "Є вiд'ємний шлях" << endl;
}
else
{
cout << "Немає вiд'ємного шляху" << endl;
}
system("pause");
/*===============================[ PROCEDURE-ORIENTED METHOD ]===*/
cout << endl;
cout << "\t\t\tProcedure-oriented method" << endl;
cout << endl;
cout << "n = ";
cin >> iN;
if (Graf(iN))
{
cout << "Є вiд'ємний шлях" << endl;
}
else
{
cout << "Немає вiд'ємного шляху" << endl;
}
system("pause");
system("cls");
break;
/*===============================[ END LABA #9 ]================*/
/*===============================[ END LABA #8 ]================*/
case 0:
/*===============================[ LABA #10 ]====================*/
cout << endl;
cout << "\t\t\t\tLaboratory work #10" << endl;
cout << endl;
cout << "Умова" << endl;
cout << endl;
/*===============================[ OBJECT-ORIENTED METHOD ]======*/
cout << endl;
cout << "\t\t\t\tObject-oriented method" << endl;
cout << endl;
cout << "Enter text:" << endl;
cin >> szText;
text = new CText(szText);
if (text->Seek_sub())
{
cout << "присутнє пiдслово \"abcd\"" << endl;
}
else
{
cout << "вiдсутнє пiдслово \"abcd\"" << endl;
}
system("pause");
/*===============================[ PROCEDURE-ORIENTED METHOD ]===*/
cout << endl;
cout << "\t\t\tProcedure-oriented method" << endl;
cout << endl;
cout << "Enter text:" << endl;
cin >> szText;
if (Seek_sub(szText))
{
cout << "присутнє пiдслово \"abcd\"" << endl;
}
else
{
cout << "вiдсутнє пiдслово \"abcd\"" << endl;
}
system("pause");
system("cls");
break;
/*===============================[ END LABA #10 ]================*/
/*===============================[ LABA #7 ]===================*/
/****************************************************************\
METHOD........: CDec
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - size of dec
RETURNS.......: None
\****************************************************************/
CDec::CDec(int iN)
{
m_piDec = new int[iN];
m_iFirst = iN/2+1;
m_iLast = iN/2;
m_bExit = true;
m_iN = iN;
for (int i=0;i<iN;i++)
{
m_piDec[i] = 0;
}
}
/****************************************************************\
METHOD........: DEC
DESCRIPTION...: Struct DEC
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
void CDec::DEC()
{
show_dec();
while(m_bExit)
{
cout << "0 - Додавання в дек" << endl;
cout << "Other - Видалення з стеку в дек" << endl;
cout << "Esc - завершення роботи з деком" << endl;
m_iNum = getch();
if(m_iNum == 27)
{
m_bExit = false;
continue;
}
if(!(m_iNum-48))
{
cout << endl;
cout << "0 - Додавання на початок" << endl;
cout << "Other - Додавання в кiнець" << endl;
m_iNum = getch();
if (!(m_iNum-48))
{
if (m_iFirst-1>0)
{
m_iFirst--;
cout << endl;
cout << "piDec[iFirst] = ";
cin >> m_piDec[m_iFirst];
cout << endl;
show_dec();
cout << endl;
}
else
{
cout << endl;
cout << "Дек повний" << endl;
cout << endl;
continue;
}
}
else
{
if (m_iLast+1<m_iN)
{
m_iLast++;
cout << endl;
cout << "piDec[iLast] = ";
cin >> m_piDec[m_iLast];
cout << endl;
show_dec();
cout << endl;
}
else
{
cout << endl;
cout << "Дек повний" << endl;
cout << endl;
continue;
}
}
}
else
{
cout << endl;
cout << "0 - Видалення з початок" << endl;
cout << "Other - Видалення з кiнець" << endl;
m_iNum = getch();
if (!(m_iNum-48))
{
if (m_iFirst!=m_iLast+1)
{
m_piDec[m_iFirst] = 0;
m_iFirst++;
cout << endl;
show_dec();
cout << endl;
}
else
{
cout << endl;
cout << "Дек порожнiй" << endl;
cout << endl;
continue;
}
}
else
{
if (m_iLast!=m_iFirst-1)
{
m_piDec[m_iLast] = 0;
m_iLast--;
cout << endl;
show_dec();
cout << endl;
}
else
{
cout << endl;
cout << "Дек порожнiй" << endl;
cout << endl;
continue;
}
}
}
}
}
/****************************************************************\
METHOD........: show_dec
DESCRIPTION...: Show array of dec
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: void
\****************************************************************/
void CDec::show_dec()
{
for(int i=0;i<m_iN;i++)
{
cout << m_piDec[i] << " ";
}
cout << endl;
}
/****************************************************************\
FUNCTION......: DEC
DESCRIPTION...: Show array of dec
ATTRIBUTES....: Public
ARGUMENTS.....:
piDec - array Dec
iN - size of dec
RETURNS.......: void
\****************************************************************/
void show_dec(int* piDec, int iN)
{
for(int i=0;i<iN;i++)
{
cout << piDec[i] << " ";
}
cout << endl;
}
/****************************************************************\
FUNCTION......: DEC
DESCRIPTION...: Struct DEC
ATTRIBUTES....: Public
ARGUMENTS.....:
piDec - array Dec
iN - size of dec
RETURNS.......: void
\****************************************************************/
void DEC(int* piDec, int iN)
{
int iFirst, iLast;
int iNum;
bool bExit = true;
for (int i=0;i<iN;i++)
{
piDec[i] = 0;
}
iFirst = iN/2+1;
iLast = iN/2;
show_dec(piDec,iN);
while(bExit)
{
cout << "0 - Додавання в дек" << endl;
cout << "Other - Видалення з стеку в дек" << endl;
cout << "Esc - завершення роботи з деком" << endl;
iNum = getch();
if(iNum == 27)
{
bExit = false;
continue;
}
if(!(iNum-48))
{
cout << endl;
cout << "0 - Додавання на початок" << endl;
cout << "Other - Додавання в кiнець" << endl;
iNum = getch();
if (!(iNum-48))
{
if (iFirst-1>0)
{
iFirst--;
cout << endl;
cout << "piDec[iFirst] = ";
cin >> piDec[iFirst];
cout << endl;
show_dec(piDec,iN);
cout << endl;
}
else
{
cout << endl;
cout << "Дек повний" << endl;
cout << endl;
continue;
}
}
else
{
if (iLast+1<iN)
{
iLast++;
cout << endl;
cout << "piDec[iLast] = ";
cin >> piDec[iLast];
cout << endl;
show_dec(piDec,iN);
cout << endl;
}
else
{
cout << endl;
cout << "Дек повний" << endl;
cout << endl;
continue;
}
}
}
else
{
cout << endl;
cout << "0 - Видалення з початок" << endl;
cout << "Other - Видалення з кiнець" << endl;
iNum = getch();
if (!(iNum-48))
{
if (iFirst!=iLast+1)
{
piDec[iFirst] = 0;
iFirst++;
cout << endl;
show_dec(piDec,iN);
cout << endl;
}
else
{
cout << endl;
cout << "Дек порожнiй" << endl;
cout << endl;
continue;
}
}
else
{
if (iLast!=iFirst-1)
{
piDec[iLast] = 0;
iLast--;
cout << endl;
show_dec(piDec,iN);
cout << endl;
}
else
{
cout << endl;
cout << "Дек порожнiй" << endl;
cout << endl;
continue;
}
}
}
}
}
/*===============================[ LABA #8 ]===================*/
/****************************************************************\
METHOD........: CTree
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - size of tree
RETURNS.......: None
\****************************************************************/
CTree::CTree(int iN)
{
m_iCount = 0;
m_iN = iN;
m_root = 0;
for (int i=0;i<3;i++)
{
m_piTree[i] = new int[iN];
}
m_bNext = true;
for(int i=0;i<3;i++)
{
for(int j=0;j<iN;j++)
{
m_piTree[i][j]=0;
}
}
for(int j=0,iTemp;j<iN;j++)
{
if (m_bNext)
for(int i=0;i<3;i++)
{
if (j == 0)
{
m_piTree[i][j] = 0;
continue;
}
if (i == 0)
{
m_piTree[i][j] = j;
}
if (j==1 && i==0)
{
cout << "Введiть корiнь дерева: ";
cin >> iTemp;
if (iTemp)
{
m_piTree[i][j]=iTemp;
m_root = iTemp;
continue;
}
else
{
m_bNext = false;
continue;
}
}
else
{
if (i==1)
{
cout << "Лiвий нащадок елемента " << j << ": ";
cin >> iTemp;
if (iTemp==-1)
{
m_piTree[i][j]=0;
m_bNext=false;
break;
}
else
{
m_piTree[i][j]=iTemp;
}
}
if (i==2)
{
cout << "Правий нащадок елемента " << j <<": ";
cin >> iTemp;
if (iTemp==-1)
{
m_piTree[i][j]=0;
m_bNext=false;
break;
}
else
{
m_piTree[i][j]=iTemp;
}
}
}
}
}
}
/****************************************************************\
METHOD........: show_tree
DESCRIPTION...: Show array of tree
ATTRIBUTES....: Public
ARGUMENTS.....: None
RETURNS.......: void
\****************************************************************/
void CTree::show_tree()
{
for(int i=0;i<3;i++)
{
for(int j=0, iNum;j<m_iN;j++)
{
cout << m_piTree[i][j] << " ";
}
cout << endl;
}
}
/****************************************************************\
METHOD........: Seek_Leafs
DESCRIPTION...: Comput the numbers of Leafs
ATTRIBUTES....: Public
ARGUMENTS.....:
iNext - next element of tree
RETURNS.......: int
\****************************************************************/
int CTree::Seek_Leafs(int iNext)
{
if (m_piTree[0][iNext] == 0)
{
return 0;
}
else
{
if (m_piTree[1][iNext]==0 && m_piTree[2][iNext]==0)
{
m_iCount++;
return 1;
}
else
{
m_iCount++;
return Seek_Leafs(m_piTree[1][iNext]) + Seek_Leafs(m_piTree[2][iNext]);
}
}
}
/****************************************************************\
METHOD........: Get_root
DESCRIPTION...: return root
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: int
\****************************************************************/
int CTree::Get_root()
{
return m_root;
}
/****************************************************************\
METHOD........: Get_count
DESCRIPTION...: return count
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: int
\****************************************************************/
int CTree::Get_count()
{
return m_iCount;
}
/****************************************************************\
FUNCTION......: Seek_Leafs
DESCRIPTION...: Comput the numbers of Leafs
ATTRIBUTES....: Public
ARGUMENTS.....:
ppiTree - tree
iNext - next element of tree
iCount - count of Leafs
RETURNS.......: int
\****************************************************************/
int Seek_Leafs(int **ppiTree, int iNext, int* iCount)
{
if (ppiTree[0][iNext] == 0)
{
return 0;
}
else
{
if (ppiTree[1][iNext]==0 && ppiTree[2][iNext]==0)
{
*iCount=*iCount+1;
return 1;
}
else
{
*iCount=*iCount+1;
return Seek_Leafs(ppiTree,ppiTree[1][iNext],iCount) + Seek_Leafs(ppiTree,ppiTree[2][iNext],iCount);
}
}
}
/****************************************************************\
FUNCTION......: show_tree
DESCRIPTION...: Show array of tree
ATTRIBUTES....: Public
ARGUMENTS.....:
ppiTree - tree
iN - size of tree
RETURNS.......: int
\****************************************************************/
void show_tree(int** ppiTree,int iN)
{
for(int i=0;i<3;i++)
{
for(int j=0, iNum;j<iN;j++)
{
cout << ppiTree[i][j] << " ";
}
cout << endl;
}
}
/****************************************************************\
FUNCTION......: Enter_tree
DESCRIPTION...: Enter elements of tree
ATTRIBUTES....: Public
ARGUMENTS.....:
ppiTree - tree
iN - size of tree
root - root of tree
RETURNS.......: int
\****************************************************************/
void Enter_tree(int** ppiTree, int iN, int* root)
{
bool bNext = true;
for(int i=0;i<3;i++)
{
for(int j=0, iNum;j<iN;j++)
{
ppiTree[i][j]=0;
}
}
for(int j=0,iTemp;j<iN;j++)
{
if (bNext)
for(int i=0;i<3;i++)
{
if (j == 0)
{
ppiTree[i][j] = 0;
continue;
}
if (i == 0)
{
ppiTree[i][j] = j;
}
if (j==1 && i==0)
{
cout << "Введiть корiнь дерева: ";
cin >> iTemp;
if (iTemp)
{
ppiTree[i][j]=iTemp;
*root = iTemp;
continue;
}
else
{
bNext = false;
continue;
}
}
else
{
if (i==1)
{
cout << "Лiвий нащадок елемента " << j << ": ";
cin >> iTemp;
if (iTemp==-1)
{
ppiTree[i][j]=0;
bNext=false;
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора