Sponsored Content
Top Forums Programming c++ code to check whether a list is circular or not Post 302447034 by Praveen_218 on Friday 20th of August 2010 04:00:32 PM
Old 08-20-2010
Quote:
Originally Posted by binlib
This will not detect the case when it loops back to the middle of the list. You can have two pointers starting at the head, advance one by one step, two for the other. Check if they meet.
I think that what you mentioned is a list having a loop in it.

Out of curiosity , I decided to look at the standard definition of what exactly we mean by the term Circular list.

Below is what I found:

Quote:
Definition: A variant of a linked list in which the nominal tail is linked to the head. The entire list may be accessed starting at any item and following links until one comes to the starting item again.
Some url for the reference:
Hence the above pseudo code, by Corona, prefectly hold true in context to this thread question.

---------- Post updated at 01:30 AM ---------- Previous update was at 12:59 AM ----------

Definitions apart, a practical approach.

The circular list is a specilized version of the linear linked list with a loop into it, hence a small edition to the above pseudo code (per binlib) :
Code:
typedef struct node list;
typedef NULL END;

bool is_circular(list l)
{
        a=l.head;
        b=(a->next)->next;

        while((b != END) && (a != b))
        {

                if((b == l) || (a == l)) {
                   /*
                   ** Perfect circular, as per the standard definition.
                   */
                   return 1;
                }

                if (END != b->next) {
                   b=(b->next)->next;
                }
                else {
                   /*
                   ** The list is a linear one.
                   */
                   return 0;
                }
                a=a->next;
        }

        if (END == b) {
           return 0;  //Linear case.
        }
        else { 
           /*
           ** Some kind of loop
           */
           return 1; 
        }

}


Last edited by Praveen_218; 08-21-2010 at 12:10 AM..
This User Gave Thanks to Praveen_218 For This Post:
 

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Circular reference

I might know the answer to this, but I just want to see if any of you know any work arounds before I go and re-write the whole thing. I have a script as follow: $ cat testing #! /usr/bin/ksh f () { echo "Type \"y\" \c" read value if ; then ... (1 Reply)
Discussion started by: fidodido
1 Replies

2. HP-UX

Password cannot be circular shift of logonid

Hi , I am getting the below error if i am trying to set the passwd of a user: New password: Password cannot be circular shift of logonid. is there a way thru which i can set the passwd of the user same as the username. Thanks & regards, Sagar. (2 Replies)
Discussion started by: sag71155
2 Replies

3. Shell Programming and Scripting

check a list of vars

I have about 20 different variables that I need to check for null values then replace with a specific string if they are null. I've been doing this via 20 different if then statements like this: if ; then WIND="UUU" fi Is there a more elegant way to do this? The vars aren't sequential in... (6 Replies)
Discussion started by: audiophile
6 Replies

4. Shell Programming and Scripting

monitoring a circular file

I have an event log which is a circular file. I would like to be able to see real-time updates of that event log. Kind of the equivalent of a 'tail -f'. But obviously 'tail -f' won't work if my circular file has already cycled over. Any ideas as to how I can do this? Let me know if I am clear.... (10 Replies)
Discussion started by: sdilucca
10 Replies

5. Programming

c++ function to convert a linear list to circular list

hi all, i need a c++ function which converts a linear list to circular. presently i am working with two files. i.e., one linear list file. and one circular list file to do some operations. i thought it will be helpful if there is a function that converts a linear list to circular n undo the... (1 Reply)
Discussion started by: vidyaj
1 Replies

6. UNIX for Dummies Questions & Answers

Filewatch job in autosys in circular way

I have box created with filewatch job as the first job follwed by 2 other jobs . For the time period of 8:00 am to 8:00 pm,we can get files anytime , with out any restriction on the number of times we get the file. So for this I need to make this box work in circular fashion i.e. once the box... (5 Replies)
Discussion started by: nishantrk
5 Replies

7. Shell Programming and Scripting

Perl code to check date and check files in particular dir

Hi Experts, I am checking how to get day in Perl. If it is “Monday” I need to process…below is the pseudo code. Can you please prove the code for below condition. if (today=="Monday" ) { while (current_time LESS THAN 9:01 AM) ... (1 Reply)
Discussion started by: ajaypatil_am
1 Replies

8. Shell Programming and Scripting

DNS circular verify script

I have modified a script to do a circular DNS look up. The theory is this for a given subnet build a range if IP's do a reverse look up on those IP's take the output of the reverse look up then and do a forward look up If the returns match up give a good status If not return a fail... (1 Reply)
Discussion started by: snoman1
1 Replies

9. Shell Programming and Scripting

Help with defining a consition within a circular boundary

Hi Help, I am trying to create something like --- Suppose, I have grid origin at X=600000.0 & Y=90000.0. For any values of X, Y values lying within a circular periphery defined by circle of radius R=500m;X=599500.0 & 600500.0 ;Y=90500.0 & 89500.0should have a default=0or else it should... (4 Replies)
Discussion started by: Indra2011
4 Replies

10. Programming

Code review: recursion in circular array, reduce two functions to one?

Hello, I think there's an easier way to do this but can't seem to recall but given an array of animals and an initial value is a random index in the array, here it's 3. 3,4,5,4,3,2,1,0,1,2,3,4,5,4,3,2,1,0... inifinite repeat a quick brute force solution i came up with was two functions, i... (6 Replies)
Discussion started by: f77hack
6 Replies
All times are GMT -4. The time now is 04:11 PM.
Unix & Linux Forums Content Copyright 1993-2022. All Rights Reserved.
Privacy Policy