資料結構第四小考參考解答 2009/11/16

1. Write a C function to compare two character strings represented by linearly
   linked lists, which are implemented by dynamic variables. Each node of the
   lists stores one character. This function returns -1 if the character string
   represented by list1 is less than the string represented by list2, 0 if they
   are equal, and 1 if the string represented by list1 is greater.
   
Solution:
// (Comparison of vocabulary. Similar to int strcmp(const char *s1, const char *s2);
        　　　　struct nodetype {
			char info;
			struct nodetype *next;
		}
		int compare(struct nodetype *list1, struct nodetype *list2){
			struct nodetype *p;
			struct nodetype *q;
			p = list1;
			q = list2;

			while(p!=NULL && q!=NULL){
				/*Compare each pair of nodes */
				if(p->info < q->info)
					return -1;
				else if(p->info > q->info)
					return 1;
				else {
					p = p->next;
					q = q->next;
				}
			}

			if(p==NULL && q!=NULL)	return -1;
			else if(p==NULL && q==NULL)	return 0;
			else return 1;
		}
		

2. Write a C function to concatenate two circular linearly linked lists, which
   are implemented by arrays.

Solution:
//  The external pointer points to the tail, not the head, in a circular linked list.
//  “Concatenate” means “string concatenate”. 
//	Similar to int strcat(const char *s1, const char *s2);
        　　　　struct nodetype {
			int info;
			int next;
		}
		struct nodetype node[100];
		void concatenate(int *list1, int *list2)
                  // list1 points to the tail of the new list
		{
			int p;

			/*check whether each of the lists is empty*/
			if (*list1 == -1) {
				*list1 = *list2;
				return;
			}
			if (*list2 == -1)
				return;
			
			p = node[*list1].next;
			node[*list1].next = node[*list2].next;
			node[*list2].next = p;
                        list1 = list2;
 		}

		
3. Write a C function to delete the nth element from a circular doubly linked
   list, which is implemented by an array.
   
Solution:
//  The external pointer points to the tail, not the head, in a circular linked list.
//  Assume that n is less than or equal to the length of the list.

		struct nodetype {
			int info;
			int left, right;
		}
		struct nodetype node[100];
		void delete(int *list, int n)
		{
			int i, p, q, r;
			
			p = node[*list].right;   // point to the head  
                       if (p == *list) {   // only one node, delete the node
                            *list = -1; 
　　　　　            　　　freenode(p);
　　　　　　　　            return;
　　　　　　            }
			/* locate the nth node */
			for(i = 1; i < n; i++)
				p = node[p].right;
			
                        /*delete node p*/
			r = node[p].right;
                        q = node[p].left
			node[q].right = r;
			node[r].left = q;
			freenode(p);
               }