Homework 2 Solution

Problem 1 Solution:
========================================================================
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

struct node;
typedef node* List;
struct node{
       List next;
       int key;
};

void BuildList(List list,int s[],int l)
{
	List temp=list;
	list->key=s[0];
	for(int i=1;i<l;i++){
		List newnode=new node;
		     newnode->key=s[i];
			newnode->next=NULL;
				temp->next=newnode;
					temp=newnode;
					}
}

void PrintList(List list)
{    
     while(list){
	cout<<list->key<<" ";
			   list=list->next;
			   }
			   cout<<endl;
}

void merge(List list3, List list1, List list2)
{
	List temp=list3;
	while(list1||list2){
		List newnode=new node;
		     newnode->next=NULL;
			if((list1&&list2&&list1->key<list2->key)||(!list2)){
					newnode->key=list1->key;
							list1=list1->next;
								}
									else{
											newnode->key=list2->key;
													list2=list2->next;  
															    } 
															      temp->next=newnode;
															       temp=newnode;
															       }
}

void main()
{
	int a[5]={1,6,15,19,22};
	int b[5]={-5,0,6,17,50};
	List list1, list2, list3;
	list1=new node;
	list2=new node;
	list3=new node;
	BuildList(list1,a,5);
	BuildList(list2,b,5);
	merge(list3,list1,list2);
	list3=list3->next;
	cout<<"list1: "; PrintList(list1);
	cout<<"list2: "; PrintList(list2);
	cout<<"list3: "; PrintList(list3);
}
 

Problem 2 Solution:
========================================================================
#include <stdio.h>
#include <iostream.h>

struct node;
typedef node* List;
struct node{
       List next;
       char key;
};

class myString{
      private:
	List head,tail;
	     int length;
	     public:
		myString();		//constructor
					~myString();		//destructor
								bool IsEmpty();
								     int getLength();
									 void buildString(const char []);
									      void printString();
										   void concatenation(myString);
};

myString::myString()
{
	head=new node;
	tail=head;
}

myString::~myString()
{
	while(head){
		List temp=head;
		     head=head->next;
			delete temp;
			}
}

int myString::getLength()
{
	return length;
}

void myString::buildString(const char sur[])
{
	int i;
	List newnode,temp=head;
	length=strlen(sur);
	for(i=0;i<length;i++){
		newnode=new node;
			    newnode->next=NULL;
				newnode->key=sur[i];
					temp->next=newnode;
						temp=newnode;		
						}
						tail=temp;
						temp=head;
						head=head->next;
						delete temp;
}

void myString::printString()
{
	List temp=head;
	while(temp){
		cout<<temp->key;
			temp=temp->next;
			}
			cout<<endl;
}

void myString::concatenation(myString s)
{
	List temp=tail;
	List surList=s.head;
	List newnode;
	while(surList){
		newnode=new node;
			    newnode->next=NULL;
				newnode->key=surList->key;
					surList=surList->next;
						temp->next=newnode;
							temp=newnode;
							}
							tail=temp;
}

void main()
{
	myString str1;
	myString str2;
	str1.buildString("hello");
	str2.buildString(" world!");
	str1.concatenation(str2);
	str1.printString();
}

Problem 3 Solution:
====================================================================
#include <iostream.h>
#include <stdio.h>
#include <string.h>

bool IsPalindrome(char s[], int head, int tail)
{
	if(head==tail) return 1;
	else if(head>tail) return 1;
	else{
		if(s[head]>='A'&&s[head]<='Z') s[head]=s[head]-'A'+'a';
					       if(s[tail]>='A'&&s[tail]<='Z') s[tail]=s[tail]-'A'+'a';
									      if(!(s[head]>='a'&&s[head]<='z')) IsPalindrome(s, head+1, tail);
														else if(!(s[tail]>='a'&&s[tail]<='z')) IsPalindrome(s, head, tail-1);
														     else if(s[head]!=s[tail]) return 0;
															  else IsPalindrome(s, head+1, tail-1);
															  }
}

void main()
{
	char s[100];
	cout<<"Input a string: ";
	cin>>s;
	if(IsPalindrome(s,0,strlen(s)-1)) cout<<" It is a palindrome!"<<endl;
	else cout<<" It is not a palindrome!"<<endl;
}