TECH GUIDE BLOG

Let’s get to the point, what’s the different beetwen Circular and Linear? Just like previous post, the different is the head is always move around or you can say dynamic. The first and the last data is likely become linked to another one. If we do enqueue, the tail will be point to the new data. If you can see the picture below, you will know that the data are never move like linear queue, but the head node. This head node always move when you do dequeue and enqueue new data.

Circular Queue

While we using circular queue, we can use mod (%) to help us for the head movement. Here is the example of Circular Queue. This code is the class of Queue, it’s just made for keep integer data up to small size, it’s just for simple example program of Circular Queue.

#include <iostream.h>
#include <conio.h>
#include <windows.h>

#define MAX 5

class Cqueue
{
private:
	int element[MAX];
	int head;
	int tail;
public:
	Cqueue()
	{
		head=0;
		tail=0;
	}
	void enqueue(int x)
	{
		if(!full())
		{
			element[(head+tail)%MAX]=x;
			tail++;
		}
	}
	int dequeue()
	{
		if(!empty())
		{
			int temp;
			temp=element[head];
			head++;
			head=head%MAX;
			tail--;
			return temp;
		}
	}
	int full()
	{
		if(tail==MAX)
			return 1;
		else
			return 0;
	}
	int empty()
	{
		if(tail==0)
			return 1;
		else
			return 0;
	}
	void view()
	{
		for(int i=0;i<tail;i++)
			cout<<element[(i+head)%MAX]<<endl;
		getch();
	}
};

Popularity: 43% [?]

This time, we will talk about Boyer Moore string searching. It’s not like brute-force, it will search a substring from the back and go forward till the first char of string. For example, we search a substring EXAMPLE within HERE IS A SIMPLE EXAMPLE string. I can’t explain it well, so this below maybe rather confusing.

EXAMPLE
HERE IS A SIMPLE EXAMPLE
's' is not in EXAMPLE substring, jump for EXAMPLE length = 7
       EXAMPLE
HERE IS A SIMPLE EXAMPLE
'e' is not same as 'p', so jump for the last char of EXAMPLE to 'p' EXAMPLE = 2
         EXAMPLE
HERE IS A SIMPLE EXAMPLE
'a' != 'i', jump for distance from 'e' SIMPLE to the front 'e' EXAMPLE sub string = 6
               EXAMPLE
HERE IS A SIMPLE EXAMPLE
'e' is not same as 'p', so jump for the last char of EXAMPLE to 'p' EXAMPLE = 2
                 EXAMPLE
HERE IS A SIMPLE EXAMPLE
compare till end, found.

For the code, it’s a little weird, made by myself with many helps. It just find the index of string if it found the sub string within the string. You can use a table to save all chars shift value.

#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <windows.h>

void main()
{
	char string[1000], substring[1000];
	int strvalue[256], i, j, diff = 0, count = 0;

	printf("Input string: ");
	gets(string);
	printf("Input substring: ");
	gets(substring);
	for (i = 0; i < 256; i++)
	{
		strvalue[i] = -1;
	}
	for (i = strlen(substring) - 1; i >= 0 ; i--)
	{
		if (strvalue[substring[i]] == -1)
			strvalue[substring[i]] = i;
	}
	for (i = 0; i < 256; i++)
	{
		if (strvalue[substring[i]] == -1)
			strvalue[substring[i]] = strlen(substring);
	}
	i = strlen(substring) - 1;
	while (true)
	{
		for (j = strlen(substring) - 1; j >= 0 ; j--)
		{
			if (substring[j] == string[i - diff])
			{
				count++;
				diff++;
			}
			else
				break;
			if (count == strlen(substring))
			{
				printf("%d", i - diff + 2);
				getch();
				exit(0);
			}
		}
		diff = strlen(substring) - strvalue[string[i - diff]] - 1 - count;
		if (diff > 0)
		{
			i = i + diff;
			diff = 0;
			count = 0;
		}
		else
			i++;
		if (i > strlen(string) + strlen(substring) + 2)
			exit(0);
	}
}

Popularity: 49% [?]

This part of Linear Single Linked List will tell you how to delete a node at any index. It’s simple like adding a data, you just have to change the node pointer to other that next to the node that you want to delete. If you want to delete the most front data, you have to set the head onto the next node and delete the first node. Looks like front, when we want to delete the last node, we have to set the 2nd node from the last to tail and delete the last data/ node.

Delete any index in Single Linked List

Delete first data on Single Linked List

Delete the last index of Single Linked List

The code is quite simple rather than add code, I think. Human kind is rather destroying than creating and managing these days.

void DeleteLastIndex()
{
node *temp;
temp=head;
while(temp->nget()!=tail)
{
temp=temp->nget();
}
delete tail;
tail = temp;
tail->nset(NULL);
}

void DeleteAnyIndex(int index)
{
node *temp,*dnew;
temp=head;
dnew=head;
int i=0;
for(i=0;i<index;i++)
{
temp=temp->nget();
}
for(i=0;i<x+1;i++)
{
dnew=dnew->nget();
}
temp->nset(dnew->nget());
delete dnew;
}

void DeleteFront()
{
node *temp;
temp=head;
head=head->nget();
delete temp;
}

I think this code should works fine…. I think, LoL.

Popularity: 51% [?]