stucture small problem

Sep 19, 2012 at 5:06am
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
 
int ReverseString(char *);
 
struct node {
	node *prev;
	char c;
	node *next;
};
 
// detects if a word is a palindrome
void makeList(const char candidate[], node* &head, node* &tail) {
 
        // get the length of the c-string
        int len = strlen(candidate);
 
 
        node* first = NULL;
        node* temp = NULL;
 
        //make first link
        first = new node;
        first->prev = NULL;
        first->next = NULL;
        first->c = candidate[0];
 
        //make head and tail point to it
        head = first;
        tail = first;
 
        //make the list
 
        for(int i = 1; i < len; i++)
        {
                //make a new link for each character left
                temp = new node;
 
                //make a link that goes back to tail
                temp->prev = tail;
 
                //link forward is null
                temp->next=NULL;
 
                temp->c = candidate[i];
 
                //set up link backward to end of list
                tail->next = temp;
 
                //new tail is now last element
                tail = temp;
        }
}
 
bool isPalindrome(node * head, node * tail) {

        while(head != tail && head < tail)
        {
                if(head->c == tail->c)
                {
                        head = head->next;
                        tail = tail->prev;
                }

                else return false;
        }

        return true;
}
// reads in the list of words
// prints out word if it is a palendrome
int main() {
 
        node *head = NULL;
        node *tail = NULL;
		char words[100];

		cout << "Enter text : ";
		cin.getline(words,100);
 
		makeList(words, head, tail);
        // use our function to check if it's a palindrome
        if (isPalindrome(head, tail)==true) {
            cout << "Forward: "<< words << endl;
			cout << "Reverse: ";  
			ReverseString(words);
			cout << endl;
			cout << "It's a palindrome !"<<endl;
        }
		else{
			cout << "Forward: "<< words << endl;
			cout << "Reverse: ";  
			ReverseString(words);
			cout << endl;
			cout << "Not a palindrome !"<<endl;
		}

		cin.get();
		return 0;
 
}

int ReverseString(char *rev){

	if(*rev!='\0')
    {
		ReverseString(rev + 1);
        putchar(*rev);//change this.
			   
	}
	return 0;
}


So here is the code , done it , but can I ask if inside my structure

1
2
3
4
5
struct node {
	node *prev;
	char c;
	node *next;
};


Instead I wan to cancel the node*prev as my question i should not add it inside . i should only have this only
1
2
3
4
struct node {
	char c;
	node *next;
};


SO my question is , how i create the *prev ? for all my code above those using it?
senior help . thanks
Last edited on Sep 19, 2012 at 5:49am
Sep 19, 2012 at 6:40am
In order to allow each node(except head) to have a pointer to the previous node, you must include it in the structure
Sep 19, 2012 at 8:52am
mean i mus hve? my friend did it using only 1 pointer , but now I'm using two pointer already , any suggestions ?
Sep 19, 2012 at 9:53am
Was using a linked list part of your assignment? Because it doesn't really offer much in this situation and is completely unnecessary except in complicating what should be a simple solution, assuming all you're after is determining if your input is a palindrome.
Sep 19, 2012 at 10:10am
ya . im using the linked list . my fren did it without using 2 pointer . he just use this and done the palindrome

1
2
3
4
struct node {
	char c;
	node *next;
};


but i have to use 2 pointer to did it. and I hope that i learn from here . thats why asking some senior to teach me the way and provide the example .

Since that i no want just copy and paste. learn nothing
Sep 19, 2012 at 10:16am
Ok. then use one pointer.
Did your friend have a node *prev in his code?
cause I also normally use one pointer, that is to the next node.
Last edited on Sep 19, 2012 at 10:17am
Sep 19, 2012 at 10:22am

Read word into string, check it against its own reverse.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string one;
node currentLetter; // set to starting letter

while (1)
{
  one += currentLetter.c;
  if (currentLetter.node == 0) // no more letters
  { break;}
  else
  { currentLetter = currentLetter->next; 
}

string reverse = one;
reverse(reverse.begin(), reverse.end());
if ( one == reverse)
{  cout << "Palindrome"; }


Requires inclusion of <algorithm>



Sep 19, 2012 at 10:40am
@mos .

i have to add inside where?

Sep 19, 2012 at 12:23pm
1
2
3
4
5
struct node
{
	char c ;
	node *next ;
};

Testing if the singly linked list is a palidrome in O(N) time and O(N) space is trivial:
1
2
3
4
5
6
7
8
9
#include <string>
#include <algorithm>

bool is_palindrome( const node* first )
{
    std::string str ;
    for( ; first ; first = first->next ) str += first->c ;
    return std::equal( str.begin(), str.begin() + str.size()/2, str.rbegin() ) ;
}

Doing it in O(N) time and O(1) space is more interesting. This is a common approach:

1. Reverse the second half of the list (the part of the list just after its mid-point)
2. Compare if the first half of the list to the second half
3. Undo step 1. to restore the original list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int size( const node* first )
{
    int n = 0 ;
    while(first) { ++n ; first = first->next ; }
    return n ;
}

// get the node just after the mid point of the list
node* middle( node* first, int sz )
{
    int n = sz/2 + sz%2 ;
    while( n-- ) first = first->next ;
    return first ;
}

node* reverse( node* first )
{
    node* prev = nullptr ;
    while(first)
    {
        node* next = first->next ;
        first->next = prev ;
        prev = first ;
        first = next ;
    }
    return prev ;
}

bool is_palindrome( node* first )
{
    bool palindrome = true ;

    // reverse the subsequence just after the middle of the list
    node* mid = reverse( middle( first, size(first) ) ) ;

    // compare first half of list with the second half
    for( node* p = mid ; p && palindrome ; first = first->next, p = p->next )
        if( first->c != p->c ) palindrome = false ;

    reverse( mid ) ; // restore the original list
    return palindrome ;
}
Sep 19, 2012 at 2:31pm
@JL

but how i pass my word to it?

1
2
3
char words[100];

cin.getline(words,100);


then how i gonna pass by input to the function? because i see that all your function is point to structure , but none of is is pass by input d??

sorry cause i'm newbie in programming.
Sep 19, 2012 at 3:37pm
Do you understand how your linked list actually works? How to hold the letters in it?
Sep 19, 2012 at 4:00pm
Try writing these two functions first.

1
2
3
4
5
6
7
// given a string, make a singly linked list of chars
// allocate nodes for each char in the string and link them up
// return the first node of the list (which holds the first char)
node* make_list( const std::string& str ) ;

// given the first node of a list, print out the sequence of chars in the list
void print_list( const node* first ) ;


Once you have done that, write a main() which accepts a string from the user, calls make_list() to create a list, and then calls print_list() to print out the list. Make sure that this is working correctly; and then we can move forward.
Topic archived. No new replies allowed.