Skip to main content

Linked list sorted in an ascending order

Again to practice some of skills I wrote linked list sorted in an ascending order. It is very simple example and it performs only two operation:
  • inserting an item into the appropriate position in the list
  • printing the whole list on the screen
The following code is placed in the public domain. Use it as you wish. The code can be downloaded with the solution project file for MS Visual Studio 2008 from here.

// LinkedList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include

/*
The supplied C code fragment is intended to implement a linked list of
integers stored in ascending order. Each element of the list is a struct
of type Item holding the integer value, a pointer pred to the previous
element, if any, and a pointer succ to the succeeding element, if any. The
variable head points to the ?rst element in the list, and tail points to
the last element. Initially, both head and tail are NULL. The function
insert is intended to insert its argument x into the list. If x is already in
the list, insert should do nothing.
*/

using namespace std;

struct Item {
int value; // the integer value
Item* succ; // succeeding value
Item* pred; // preceding value
};

Item* head = NULL;
Item* tail = NULL;

Item* createItem(int x, Item* succ, Item* pred)
{
Item* item = new Item;
item->value = x;
item->succ = succ;
item->pred = pred;

return item;
}

/**
Insert x into linked list

There are 5 possible cases, any four of these will suffice
- list is initially empty
- x is smaller than any number in the list
- x is larger than any number in the list
- x is already in the list
- the normal case i.e. none of the above

*/

void insert(int x)
{
Item *p = head , *q;
if(!p) {
// add the first item
head = tail = createItem(x,NULL,NULL);
}
else if (x > tail->value){
// add the largest item in the list
tail->succ = createItem(x,NULL,tail);
tail = tail->succ;
}
else{
while (x > p->value)
p = p->succ;

if (x==p->value)
// do not add itme because it already exists
return;

// add the item before p because x < q =" createItem(x,">pred); // create item, pass the succesor and the predcesor
q->succ->pred = q; // modify the succesor of q so that it points to q
q->pred->succ = q; // modify the predcesor of q so that it points to q
}
}

void printList(void)
{
Item* p = head;
int counter = 0;

cout << "------------------------------------------------------------" <<>value << p =" p-">succ;
}
}

int _tmain(int argc, _TCHAR* argv[])
{
cout << "Ascending linked list demonstration." << i =" 0;">


The output of the program is as follows:

Ascending linked list demonstration.
--------------------------------------
Item number:0 Item value:1
--------------------------------------
Item number:0 Item value:1
Item number:1 Item value:10
--------------------------------------
Item number:0 Item value:1
Item number:1 Item value:5
Item number:2 Item value:10
--------------------------------------
Item number:0 Item value:1
Item number:1 Item value:5
Item number:2 Item value:10


Post a Comment

Popular posts from this blog

Viterbi Algorithm in C++ and using STL

To practice my C++ and STL skills, I implemented the Viterbi algorithm example from the Wikipedia page: http://en.wikipedia.org/wiki/Viterbi_algorithm. The original algorithm was implemented in Python. I reimplemented the example in C++ and I used STL (mainly vector and map classes).  This code is in public-domain. So, use it as you want. 
The complete solution for MS Visual C++ 2008 can be found at http://filip.jurcicek.googlepages.com/ViterbiSTL.rar

// ViterbiSTL.cpp : is an C++ and STL implementatiton of the Wikipedia example // Wikipedia: http://en.wikipedia.org/wiki/Viterbi_algorithm#A_concrete_example
// It as accurate implementation as it was possible

#include "stdafx.h"
#include "string" #include "vector" #include "map" #include "iostream"
using namespace std;
//states = ('Rainy', 'Sunny') //  //observations = ('walk', 'shop', 'clean') //  //start_probability = {'Rainy': 0.6, 'Sunny': 0.…

Temporal-Difference Learning Policy Evaluation in Python

In the code bellow, is an example of policy evaluation for very simple task. Example is taken from the book: "Reinforcement Learning: An Introduction, Surto and Barto".
#!/usr/local/bin/python

"""
This is an example of policy evaluation for a random walk policy.

Example 6.2: Random Walk from the book:
"Reinforcement Learning: An Introduction, Surto and Barto"

The policy is evaluated by dynamic programing and TD(0).

In this example, the policy can start in five states 1, 2, 3, 4, 5 and end in
two states 0 and 6. The allowed transitions between the states are as follwes:

0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6

The reward for ending in the state 6 is 1.
The reward for ending in the state 0 is 0.

In any state, except the final states, you can take two actions: 'left' and 'right'.
In the final states the policy and episodes end.

Because this example implements the random walk policy then both actions can be
taken with th…

how the make HCL and G graphs, and on the fly compositon of HCL and G for KALDI

Well, I had again to do something ;-) The task is to generate/create/update a decoding graph for KALDI on the fly. In my case, I aim at changing a G (grammar) in the context of a dialogue system.

One can generate a new HCLG but this would take a lot of time as this involves FST determinization, epsilon-removal, minimization, etc. Therefore, I tried to use on-the-fly composition of statically prepared HCL and G. At first, I struggled with it but later I made it work. See https://github.com/jpuigcerver/kaldi-decoders/issues/1

Here is a short summary:

At the end, I managed to get LabelLookAheadMatcher to work. It is mostly based on the code and examples in opendcd, e.g. https://github.com/opendcd/opendcd/blob/master/script/makegraphotf.sh.

First, Here is how I build and prepare the HCL and G. Please not that OpenFST must be compiled with --enable-lookahead-fsts, see http://www.openfst.org/twiki/bin/view/FST/ReadMe.

#--------------- fstdeterminize ${lang}/L_disambig.fst | fstarcsort >…