#include<conio.h>
#include<iostream.h>
#include<iomanip.h>
void hanoi(int n,char A,char B, char C)
{ if(n==1)
cout<<n<<"r--"<<A<<"to"<<B<<endl;
else
{ hanoi(n-1,A,C,B);
cout<<n<<"r--"<<A<<"to"<<B<<endl;
hanoi(n-1,C,B,A);
}
}
void main()
{clrscr();
int n;
cout<<"n=";
cin>>n;
hanoi(n,'A','B','C');
getch();
}
Monday, March 14, 2011
RBTree
#include <vcl.h>
#pragma hdrstop
#include "RBTree.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <fstream.h>
#define Red 1 //define colors for tree nodes
#define Black 0
//---------------------------------------------------------------------------
#pragma package(smart_init)
TreeNode::TreeNode(char string[], int Location, TreeNode* NodeParent)
{
strcpy(DataString, string);
RecordLocation = Location;
Left = 0;
Right = 0;
Parent = NodeParent; //point the node to its parent
Duplicates = 0; //node initially has now duplicates
Color = Red; //new nodes start out red
Deleted = false; //the node is not deleted
}
void TrimSpaces(char destination[], const char source[])
{ //function to trim trailing spaces from a string
int i;
strcpy(destination, source);
for(i = (strlen(source)-1); destination[i] == ' '; i--)
{
if(destination[i] == '\0')
break;
}
destination[i+1] = '\0';
}
RBTree::RBTree()
{
Root = 0;
}
RBTree::~RBTree()
{
DeleteTree(Root); //make call to DeleteTree which will free all dynamic memory
}
void RBTree::DeleteTree(TreeNode* Node) //operates with a post-order traversal
{
if(Node!=0)
{
DeleteTree(Node->Left); //delete the left sub-tree
DeleteTree(Node->Right); //delete the right sub-tree
DeleteTree(Node->Duplicates);
delete Node;
}
Node = NULL; //Node is no longer in use
}
//3 cases may occur when inserting into tree.
//Case 1: New node and its uncle are both red
//Case 2: New node's parent is red and uncle is black & node is a left child
//Case 3: New node's parent is red and uncle is black & node is a right child
//Case 2 & 3 are opposite when node is in the right sub-tree
void RBTree::Insert(char string[], int FilePosition) //creates a new node for string
{
TreeNode* Node;
Node = InsertItem(string, FilePosition, Root); //insert string into the tree
if(Node==0)
return; //no changes to tree needed
while((Node != Root) && (Node->Parent->Color == Red))
{
if(Node->Parent == Node->Parent->Parent->Left ) //check to see if node
{ //is in the left sub-tree
TreeNode* Node2 = Node->Parent->Parent->Right; //make node2 the uncle of node
if(Node2!=0 && Node2->Color == Red) //if the uncle is red then it is case 1
{
Node->Parent->Color = Black; //change color of parent to black
Node2->Color = Black; //change color of uncle to black
Node->Parent->Parent->Color = Red; //make node's grandparent red
Node = Node->Parent->Parent; //move toward top of tree to make additional fixes
}
else //uncle is black, case 2 or 3
{
if(Node == Node->Parent->Right) //check for case 3
{
Node = Node->Parent; //node is a right child, so case 3
LeftRotation(Node); //which requires left rotation
}
Node->Parent->Color = Black; //adjustments for both case 2
Node->Parent->Parent->Color = Red; //and case 3
RightRotation(Node->Parent->Parent); //
}
}
else //node is in right sub-tree
{
TreeNode* Node2 = Node->Parent->Parent->Left; //make node2 the uncle of node
if(Node2!=0 && Node2->Color == Red) //if the uncle is red then it is case 1
{
Node->Parent->Color = Black; //change color of parent to black
Node2->Color = Black; //change color of uncle to black
Node->Parent->Parent->Color = Red; //make node's grandparent red
Node = Node->Parent->Parent; //move toward top of tree to make fixs
}
else //uncle is black, case 2 or 3
{
if(Node == Node->Parent->Left) //check for case 3 (left and right is inverted)
{
Node = Node->Parent; //node is a left child, so case 3
RightRotation(Node); //which requires right rotation
}
Node->Parent->Color = Black; //adjustments for both case 2
Node->Parent->Parent->Color = Red; //and case 3
LeftRotation(Node->Parent->Parent); //
}
}
}
Root->Color = Black; //Root must be black by the rule of red-black trees
}
TreeNode* RBTree::InsertItem(char string[], int FilePosition, TreeNode* Node)
{
if(Root == 0)
{
Root = new TreeNode(string, FilePosition, 0); //establish the root
Root->Color = Black; //Root must be black by the rule of red-black trees
return Root;
}
while(1)
{
char temp[20], temp_string[20];
TrimSpaces(temp, Node->DataString);
TrimSpaces(temp_string, string);
int comparison = strcmp(temp_string, temp);
if(Node->Deleted) //check to see if the node is deleted. If it is
{ //it may be possible to use the
bool GreaterThanLeft, LessThanRight; //deleted node to hold the new
if(Node->Left==0) //record if the new record falls
GreaterThanLeft = true; //between the two children
else
{
TrimSpaces(temp, Node->Left->DataString);
if(strcmp(string, temp) > 0)
GreaterThanLeft = true;
else
GreaterThanLeft = false; //string is not greater than the left child
} //so deleted node can't be used for new record
if(Node->Right==0)
LessThanRight = true;
else
{
TrimSpaces(temp, Node->Right->DataString);
if(strcmp(string, temp) > 0)
LessThanRight = true;
else
LessThanRight = false; //string is not less than the right child
} //so deleted node can't be used for new record
if(GreaterThanLeft && LessThanRight)
{
strcpy(Node->DataString, string); //deleted node can hold new record
Node->RecordLocation = FilePosition;
Node->Deleted = false; //node is no longer deleted
return 0; //return 0 to avoid adjustments to tree which are
} //not need since we just changed the contents of an
} //existing node
if(comparison < 0)
{
if(Node->Left == 0) //if Left is empty put the new node there
{
Node->Left = new TreeNode(string, FilePosition, Node); //add new node
return Node->Left; //as a left child
}
else
Node = Node->Left; //check left sub-tree
}
else if(comparison > 0)
{
if(Node->Right == 0) //if Right is empty put the new node there
{
Node->Right = new TreeNode(string, FilePosition, Node); //add new node
return Node->Right; //as a left child
}
else
Node = Node->Right; //check right sub-tree
}
else //node is a duplicate
{
TreeNode* TempNode = Node;
while(TempNode->Duplicates != 0) //find the end of the duplicate list
TempNode = TempNode->Duplicates;
TempNode->Duplicates = new TreeNode(string, FilePosition, TempNode);
return 0; //return 0 will prevent adjustments to tree
} //which won't be needed when inserting a duplicate
}
}
bool RBTree::Remove(char string[])
{
TreeNode *Node;
Node = SearchFirstMatch(string); //find the node in the tree
if(Node==0)
return false; //string could not be found
if(Node->Duplicates!=0)
{ //if there is duplicates then one of the
TreeNode* TempNode = Node; //duplicates can take the place of the
TreeNode* PreviousNode; //deleted record
while(TempNode->Duplicates!=0)
{
PreviousNode = TempNode;
TempNode = TempNode->Duplicates;
}
strcpy(Node->DataString, TempNode->DataString); //copy the contents of the last
Node->RecordLocation = TempNode->RecordLocation; //duplicate to the record to be
delete TempNode; //deleted
PreviousNode->Duplicates = 0; //terminate duplicate list
return true; //deletion was successful
}
else
Node->Deleted = true; //mark the node as deleted for lazy delete
return true;
}
int RBTree::Search(char string[])
{
TreeNode* Node = Root;
int comparison;
while(Node!=0)
{
char temp[20];
TrimSpaces(temp, Node->DataString);
comparison = strcmp(string, temp);
if(comparison < 0)
Node = Node->Left; //look at left sub-tree
else if(comparison > 0)
Node = Node->Right; //look at right sub-tree
else if(Node->Deleted) //check to see if the node is deleted
return -1; //if it is then the record is not in the tree
else
return Node->RecordLocation; //string has been found
}
return -1; // the record cannot be found
}
TreeNode* RBTree::SearchFirstMatch(char string[]) //returns a pointer to the first node
{ //that matches string
TreeNode* Node = Root;
int comparison;
while(Node!=0)
{
char temp[20];
TrimSpaces(temp, Node->DataString);
comparison = strcmp(string, temp);
if(comparison < 0)
Node = Node->Left; //look at left sub-tree
else if(comparison > 0)
Node = Node->Right; //look at right sub-tree
else if(Node->Deleted) //check to see if the node is deleted
return 0; //if it is then the record is not in the tree
else
return Node; //string has been found
}
return 0;
}
void RBTree::SaveToFile(char FileName[]) //save nodes to file in the order that they
{ //are outputed by a preorder traversal
FILE *OutputFile;
OutputFile = fopen(FileName, "w");
if(OutputFile == NULL)
return;
SaveNode(Root, OutputFile); //recursive funciton that will save each node to file
fclose(OutputFile);
}
void RBTree::SaveNode(const TreeNode* Node, FILE *OutputFile)
{
// % marks beginning of location number
if(Node!=0) // # marks and of node
{
if(!Node->Deleted) //only save node if it is not deleted
{
fputs(Node->DataString, OutputFile); //output the node's string to file
putc('%', OutputFile); //output flag
char temp[10];
itoa(Node->RecordLocation, temp, 10); //convert int so that it can be sent to file
fputs(temp, OutputFile);
putc('#', OutputFile);
}
SaveNode(Node->Left, OutputFile); //save nodes in left sub-tree
SaveNode(Node->Right, OutputFile); //save nodes in right sub-tree
}
}
void RBTree::LoadFromFile(char FileName[]) //nodes are added to the tree in the same
{ //order that they were outputed by the
fstream InputFile(FileName, ios::in); //pre-order traversal. As a result, the
char chr; //tree has the same structures as the time
char string[20]; //when it was saved to file
char Location[6];
int i;
for(InputFile.get(chr);!InputFile.eof(); InputFile.get(chr)) //read through the
{ //whole file
for(i=0;chr!='%'; i++) //input the node's string until
{ // % is reached
string[i] = chr;
InputFile.get(chr);
}
string[i] = '\0'; //terminate the string
InputFile.get(chr);
for(i=0;chr!='#'; i++)
{
Location[i] = chr; //input the node's location until
InputFile.get(chr); // # is reached
}
Location[i] ='\0';
Insert(string, atoi(Location)); //add the node to the tree
}
}
int RBTree::LeftDepth()
{
return TreeDepth(Root->Left); //measure the left sub-tree
}
int RBTree::RightDepth()
{
return TreeDepth(Root->Right); //measure the right sub-tree
}
int RBTree::TreeDepth(TreeNode *Node)
{
int left = 0;
int right = 0;
if(Node->Left != 0)
left = TreeDepth(Node->Left); //get the depth of the left sub-tree
if(Node->Right != 0)
right = TreeDepth(Node->Right); //get the depth of the right sub-tree
if( left > right) //check to see which sub-tree is deeper
return left+1; //return the depth of the left sub-tree plus 1
else
return right+1; //return the depth of the right sub-tree plus 1
}
int RBTree::NumberOfLeaves(TreeNode* Node)
{
int total = 0;
if(Node->Left == 0 && Node->Right == 0)
return 1; //the node is a leaf
if(Node->Left!= 0) //count the number of leaves in the
total += NumberOfLeaves(Node->Left); //left sub-tree
if(Node->Right!=0) //count the number of leaves in the
total += NumberOfLeaves(Node->Right); //right sub-tree
return total; //return the total of all the leaves in this sub-tree
}
void RBTree::LeftRotation(TreeNode* Node)
{
TreeNode* Right = Node->Right; //hold node's right child
Node->Right = Right->Left; //make the node's right child its right child's left child
if(Right->Left != 0)
Right->Left->Parent = Node; //point the child to its new parent
if(Right != 0)
Right->Parent = Node->Parent; //point the child to its new parent
if(Node->Parent != 0) //if node is not the root
{
if(Node == Node->Parent->Left) //if node is a left child
Node->Parent->Left = Right; //make node's right child its parent's left child
else
Node->Parent->Right = Right; //make node's right child its parent's right child
}
else
Root = Right; //node's right child is now the root
Right->Left = Node; //node becomes its right child's left child
if(Node != 0)
Node->Parent = Right; //point node to its new parent
}
void RBTree::RightRotation(TreeNode* Node)
{
TreeNode* Left = Node->Left; //hold node's left child
Node->Left = Left->Right; //make the node's left child its left child's right child
if(Left->Right != 0)
Left->Right->Parent = Node; //point the child to its new parent
if(Left != 0)
Left->Parent = Node->Parent; //point the child to its new parent
if(Node->Parent != 0) //if node is not the root
{
if(Node == Node->Parent->Right) //if node is a right child
Node->Parent->Right = Left; //make node's left child its parent's right child
else
Node->Parent->Left = Left; //make node's left child its parent's left child
}
else
Root = Left; //node's left child is now the root
Left->Right = Node; //node becomes its left child's right child
if(Node != 0)
Node->Parent = Left; //point node to its new parent
}
R
TreeMass
#include<iostream.h>
#include<iomanip.H>
#include<conio.h>
#include<stdlib.h>
int tree[100],data[100];
int insert(int f)
{if(tree[0])
{int i=0;
while(tree[i])
if(data[i]>f) i=i*2+1;
else i=i*2+2;
data[i]=f;tree[i]=1;
}
else {tree[0]=1;
data[0]=f;}
}
void move(int j,int k)
{if(tree[k]!=NULL)
{tree[k]=NULL;
data[j]=data[k];
tree[j]=1;
move(2*j+1,k*2+1);
move(2*j+2,k*2+2);
}
}
void delleft(int i)
{if(tree[2*i+2]!=NULL)
{int j=i*2+1;
while(tree[j*2+2]!=NULL)
j=j*2+2;
if(tree[j*2+1])
{tree[i]=tree[j];
data[i]=data[j];
move(j,j*2+1);}
else
{tree[i]=tree[j];
data[i]=data[j];
tree[j]=NULL;}
}
else {tree[i]=tree[2*i+1];
data[i]=data[2*i+1];
move(i,2*i+1); }
}
void delright(int i)
{tree[i]=tree[2*i+2];
data[i]=data[2*i+2];
move(i,2*i+2);
}
int find(int k)
{int i;
for(i=0;i<=100;i++)
if(tree[i]!=NULL)
if(data[i]==k)
return i;
else continue;
return (-1);
}
void deletetree(int k)
{int i=0;
i=find(k);
if(i>=0)
{if(tree[i*2+1]==NULL && tree[i*2+2]==NULL) tree[i]=NULL;
if(tree[i*2+1]) delleft(i);
else delright(i);
}
else cout<<"ene element alga baina."<<endl;
}
void printtree(int i, int ws) {
if (tree[i]!= NULL) {
printtree(i*2+2, ws+=6);
cout << setw(ws) << data[i] << " " << endl;
printtree(i*2+1, ws);
}
}
void print(int i)
{if(tree[i]!=NULL)
{print(i*2+1);
cout<<" "<<data[i];
print(i*2+2);
}
}
main()
{clrscr();
int item,i,n;
char s;
for(;;)
{cout<<"\n1:insert\n2:printtree\n3:print\n4:delete\n5:exit"<<endl;
cin>>s;
switch(s)
{case'1':{cout<<"oruulah elementiin too:";cin>>n;
for(i=1;i<=n;i++)
{cin>>item;
insert(item);}
}break;
case'2':printtree(0,0);break;
case'3':print(0);break;
case'4':cout<<"ustgah element:";cin>>n;
deletetree(n);break;
case'5':exit(0);break;
}
}
getch();
}
#include<iomanip.H>
#include<conio.h>
#include<stdlib.h>
int tree[100],data[100];
int insert(int f)
{if(tree[0])
{int i=0;
while(tree[i])
if(data[i]>f) i=i*2+1;
else i=i*2+2;
data[i]=f;tree[i]=1;
}
else {tree[0]=1;
data[0]=f;}
}
void move(int j,int k)
{if(tree[k]!=NULL)
{tree[k]=NULL;
data[j]=data[k];
tree[j]=1;
move(2*j+1,k*2+1);
move(2*j+2,k*2+2);
}
}
void delleft(int i)
{if(tree[2*i+2]!=NULL)
{int j=i*2+1;
while(tree[j*2+2]!=NULL)
j=j*2+2;
if(tree[j*2+1])
{tree[i]=tree[j];
data[i]=data[j];
move(j,j*2+1);}
else
{tree[i]=tree[j];
data[i]=data[j];
tree[j]=NULL;}
}
else {tree[i]=tree[2*i+1];
data[i]=data[2*i+1];
move(i,2*i+1); }
}
void delright(int i)
{tree[i]=tree[2*i+2];
data[i]=data[2*i+2];
move(i,2*i+2);
}
int find(int k)
{int i;
for(i=0;i<=100;i++)
if(tree[i]!=NULL)
if(data[i]==k)
return i;
else continue;
return (-1);
}
void deletetree(int k)
{int i=0;
i=find(k);
if(i>=0)
{if(tree[i*2+1]==NULL && tree[i*2+2]==NULL) tree[i]=NULL;
if(tree[i*2+1]) delleft(i);
else delright(i);
}
else cout<<"ene element alga baina."<<endl;
}
void printtree(int i, int ws) {
if (tree[i]!= NULL) {
printtree(i*2+2, ws+=6);
cout << setw(ws) << data[i] << " " << endl;
printtree(i*2+1, ws);
}
}
void print(int i)
{if(tree[i]!=NULL)
{print(i*2+1);
cout<<" "<<data[i];
print(i*2+2);
}
}
main()
{clrscr();
int item,i,n;
char s;
for(;;)
{cout<<"\n1:insert\n2:printtree\n3:print\n4:delete\n5:exit"<<endl;
cin>>s;
switch(s)
{case'1':{cout<<"oruulah elementiin too:";cin>>n;
for(i=1;i<=n;i++)
{cin>>item;
insert(item);}
}break;
case'2':printtree(0,0);break;
case'3':print(0);break;
case'4':cout<<"ustgah element:";cin>>n;
deletetree(n);break;
case'5':exit(0);break;
}
}
getch();
}
Мод жишээ код
Модтой жишээ: Энгийн
#include<stdlib.h>
#include<iostream.h>
#include<conio.h>
#include<time.h>
int i=0,d,k,el[100],n,x,y;
char ch;
class bintree { struct node { int data; node *r,*l;
node(int item) { data=item;l=r=NULL;}
};
node *root;
public:
bintree() {root=NULL;}
node *getroot() {return root;}
void insert(int d);
void print(node *p,int,int,int);
void find(int i) ;
};
void bintree::find(int i)
{node *p,*back;
p=root;
back=NULL;
while(p->data!=i)
{back=p;
if(p->data>i) p=p->l;
else p=p->r ;
}
node *temp;
if(p->r==NULL&&p->l==NULL)
if(back==NULL) root=NULL;
else if(back->r==p)
back->r=NULL;
else back->l=NULL;
else if(p->r!=NULL&&p->l!=NULL)
{ back=p;
temp=p->l;
while(temp->r!=NULL)
{ back=temp;
temp=temp->r;
}
p->data=temp->data;
if(back==p)
back->l=temp->l;
else back->r=temp->r;
p=temp;
}
else
if(p->r!=NULL)
if(back==NULL)
root=p->r;
else
if(back->r==p) back->r=p->r;
else back->l=p->l;
else
if(back==NULL)
root=p->l;
else
if(back->r==p) back->r=p->l;
else back->l=p->l;
free(p);
cout<<" ustaglaa ";
getch();
}
void bintree::insert(int d)
{ node *p=root,*b;
while(p) { b=p;
if(d<p->data) p=p->l;
else p=p->r;}
p=new node(d);
if(!root) {root=p;}
else { if(b->data>d) b->l=p;
else b->r=p;}
};
void bintree::print(node *p,int z,int x,int y)
{ if(p!=NULL) { print(p->l,z/2,x-z/2,y+1); gotoxy(x,y);
cout<<p->data<<endl;
print(p->r,z/2,x+z/2,y+2);
}
};
void menu()
{cout<<" tree tree tree tree tree tree treeee treee tree "<<endl;
cout <<" 1:nemeh 2:ustgah 3:hevleh 4:garah \n";
cout<<" tree tree tree tree tree tree treeee treee tree "<<endl;
}
void main()
{ clrscr();
bintree tree;
int i,n,m,k;
char ch;
for(;;)
{ clrscr();
menu();
cout<<endl;
ch=getch();
switch(ch){
case '1': {cout<<"too = "; cin>>m;tree.insert(m); break;}
case '2':{cout<<"ustgah too= "; cin>>n; tree.find(n);break;}
case '3':{tree.print(tree.getroot(),40,40,5); cout<<endl; getch();break;}
case '4':{tree.print(tree.getroot(),40,40,5); getch();exit(0);break;}
}
}
getch();
}
#include<stdlib.h>
#include<iostream.h>
#include<conio.h>
#include<time.h>
int i=0,d,k,el[100],n,x,y;
char ch;
class bintree { struct node { int data; node *r,*l;
node(int item) { data=item;l=r=NULL;}
};
node *root;
public:
bintree() {root=NULL;}
node *getroot() {return root;}
void insert(int d);
void print(node *p,int,int,int);
void find(int i) ;
};
void bintree::find(int i)
{node *p,*back;
p=root;
back=NULL;
while(p->data!=i)
{back=p;
if(p->data>i) p=p->l;
else p=p->r ;
}
node *temp;
if(p->r==NULL&&p->l==NULL)
if(back==NULL) root=NULL;
else if(back->r==p)
back->r=NULL;
else back->l=NULL;
else if(p->r!=NULL&&p->l!=NULL)
{ back=p;
temp=p->l;
while(temp->r!=NULL)
{ back=temp;
temp=temp->r;
}
p->data=temp->data;
if(back==p)
back->l=temp->l;
else back->r=temp->r;
p=temp;
}
else
if(p->r!=NULL)
if(back==NULL)
root=p->r;
else
if(back->r==p) back->r=p->r;
else back->l=p->l;
else
if(back==NULL)
root=p->l;
else
if(back->r==p) back->r=p->l;
else back->l=p->l;
free(p);
cout<<" ustaglaa ";
getch();
}
void bintree::insert(int d)
{ node *p=root,*b;
while(p) { b=p;
if(d<p->data) p=p->l;
else p=p->r;}
p=new node(d);
if(!root) {root=p;}
else { if(b->data>d) b->l=p;
else b->r=p;}
};
void bintree::print(node *p,int z,int x,int y)
{ if(p!=NULL) { print(p->l,z/2,x-z/2,y+1); gotoxy(x,y);
cout<<p->data<<endl;
print(p->r,z/2,x+z/2,y+2);
}
};
void menu()
{cout<<" tree tree tree tree tree tree treeee treee tree "<<endl;
cout <<" 1:nemeh 2:ustgah 3:hevleh 4:garah \n";
cout<<" tree tree tree tree tree tree treeee treee tree "<<endl;
}
void main()
{ clrscr();
bintree tree;
int i,n,m,k;
char ch;
for(;;)
{ clrscr();
menu();
cout<<endl;
ch=getch();
switch(ch){
case '1': {cout<<"too = "; cin>>m;tree.insert(m); break;}
case '2':{cout<<"ustgah too= "; cin>>n; tree.find(n);break;}
case '3':{tree.print(tree.getroot(),40,40,5); cout<<endl; getch();break;}
case '4':{tree.print(tree.getroot(),40,40,5); getch();exit(0);break;}
}
}
getch();
}
Стек
Програмчлалын хэлэнд өгөгдлийн бүтэцүүдийг ерөнхийд нь шугаман ба шугаман бус гэж хоёр ангилдаг. Үүний шугаман өгөгдлийн бүтцэд нь хамаарах бүтцийн нэг нь стек юм. Стек нь зөвхөн нэг талаасаа өгөгдлийг хийх ба авах үйлдэл хийдэг бөгөөд нь энэ сүүлд орсон нь эхэлж гарна. /LIFO/ гэсэн зарчмаар ажиллана.
Стекийг массиваар зохион байгуулах
Энд стекийг массиваар зохион байгуулна. Стекийг массиваар зохион байгуулахад класс ашиглах боловч стекийн хэмжээ тогтмол байдаг учир массиваар зохион байгуулах гэж хэлж болох юм.
- Стек үүсгэх
struct MStack create(struct MStack stack,int size)
{ if(stack.sp!=0) {
printf("\nStack is already created"); getch();
return(stack);
}
else { stack.item=(int *)malloc(size*2);
stack.size=size;
stack.sp=0;
return(stack);
}
}
- Стекийн оройн элемент шалгах
int top(struct MStack stack)
{ if(stack.sp=0) { printf("\nStack is Empty");
return(0);
}
else return(stack.item[stack.sp-1]);
}
- Стект элемент нэмэх
struct MStack Add(struct MStack stack,int item)
{ if(stack.sp==stack.size) { printf("\nStack is Full");
getch();
return(stack);
}
else stack.item[stack.sp++]=item;
return(stack);
}
- Стекээс элемент хасах
struct MStack Dell(struct MStack stack)
{ if(stack.sp==0) printf("\nStack is Empty");
else { stack.sp--;
printf("\nDeleted value is =%d,stack.item[stack.sp]");
getch();
} return(stack);
}
Дээрх функцуудийг ашигласан жишээ код :
#include<stdio.h>
#include<conio.h>
main()
{ struct MStack stack;
char key;
int val;
stack.sp=0;
do
{ clrscr();
printf("\n1 Add 2 Delete 3 Top 4 Create 0 Exit");
key=getch();
switch(key)
{ case'0':clrscr(); return(0);
case'1':printf("\nInput number=");
scanf("%d",&val);
stack=Add(stack,val); break;
case'2':stack=Del(stack); break;
case'3':printf("\nTop value is=%d",top(stack));
getch(); break;
case'4':printf("\nInput stack size=");
scanf("%d",&val);
stack=Create(stack,val);
break;
}
}while(l==1)
}
ЗААГЧ АШИГЛАН СТЕК ЗОХИОН БАЙГУУЛАХ
- Стект элемент нэмэх
void Add(int item)
{ N_Stack *p;
p=(N_stack)malloc(sizeof(N_Stack));
p->val=item;
p->next=q;
q=p;
}
- Стекийн оройн элемент харуулах
void top()
{ if(q!=NULL) printf("Top of stack %d",q->val);
getch();
}
void print()
{ if(q==NULL) { printf("\nStack is Empty"); getch(); }
else
{ printf("\nValue : %d",q->val);
getch();
q=q->next;
}
}
- Стек шалгах
void Empty()
{ if(q!=NULL) printf("\nStack is not Empty");
else printf("Empty stack");
getch();
}
Дээрхи функцуудыг ашигласан жишээ код :
#include<stdio.h>
typedef struct N_Stack
{ int val;
struct N_stack next;
}N_Stack;
N_Stack *q;
main()
{ int n=1,item;
char key;
q=NULL;
while(n)
{ clrscr();
printf("\nAdd 1: Top 2: Print&Del 3: Empty 4: Quit 5:");
key=getch();
switch(key)
{ case'1':printf("\nInput Value");
scanf("%d",item);
Add(item); break;
case'2':Top(); break;
case'3':print(); break;
case'4':Empty(); break;
case'5':exit(0);
}
}
}
ЖИШЭЭ - 1 : Хаалтны баланс шалгах
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct H
{ char data;
struct H *next;
}point;
void push(char);
char pop();
point *stack=NULL;
void main()
{ char *s;
int n;
s=(char *)malloc(20);
printf("\nInput Expression");
gets(s);
while(*s)
{ switch(*s)
{ case'[':case'(':case'{': push(*s); break;
case']':if(pop()!='[') printf("\nError"); break;
case')':if(pop()!='(') printf("\nError"); break;
case'}':if(pop()!='{') printf("\nError"); break;
}s++;
} if(stack) printf("\nstack is not Empty");
else printf("ok");
}
void push(char ch)
{ point *q;
q=(point *)malloc(sizeof(point));
q->data=ch;
q->next=stack;
stack=q;
}
char pop()
{ char ch;
point *q;
if(stack){ ch=stack->data;
q=stack;
stack=stack->next;
free(q);
return(ch);
}
return(0); }
Subscribe to:
Posts (Atom)