《数据结构题集》2.12

核心代码: int common_prefix(List LA,List LB) //找到最大前缀的下标 int compare(List LA,List LB,int prefix) //然后进行比较

int 
common_prefix(List LA,List LB)
{
	int i;
	int j = 0;
	int length;
	length = ( LA.length - LB.length ) ? LA.length : LB.length;
	for(i = 0;i<length;i++)
	{
		if(LA.elem[i] == LB.elem[i])
			j++;
	}
	return j;

}

int  
compare(List LA,List LB,int prefix)
{
	if(LA.length == prefix && LB.length == prefix)
		return 0;
	if(LA.elem[prefix] < LB.elem[prefix])
		return 1;
	if(LA.elem[prefix] > LB.elem[prefix])
		return 2;
	else
		return OK;
}

我看了一下网上别人的答案，觉得更简洁一些，它是一趟扫描下来的，列在下面：

int compare(List LA,List LB)
{
	int i = 0;
	while(i<LA.length && i < LB.length)
	{
		if(LA.elem[i] > LB.elem[i])
			return 2;
		else if(LA.elem[i] < LB.elem[i])
			return 1;
		else
			i++;
	}

	if(i < LA.length)
		return 2;
	else if(i < LB.length)
		return 1;
	else 
		return 0;
}

对返回值的说明

switch(choose)
	{
		case 0:
			printf("A = B
");
			break;
		case 1:
		    printf("A < B
");
		    break;
		case 2:
		    printf("A > B
");
		    break;
		default:
		printf("no compare!!!
");

	}

全部代码

#include<stdio.h>
#include<stdlib.h>

#define ERROR -1
#define OK 1

#define LIST_INT_SIZE 100
#define LISTINCREMENT 10


typedef struct 
{
	int * elem;
	int length;
	int size;
	
}List;


int
InitList(List *L)
{
	(*L).elem = (int *)malloc(LIST_INT_SIZE * sizeof(int));
	if(!(*L).elem)
		exit(ERROR);
	(*L).length = 0;
	(*L).size = LIST_INT_SIZE;
	return OK;
}

int 
InsertList(List * L,int i,int e)
{
	int * newbase,*q,*p;
	//int list1[5] = {3,5,7,9,11};
	if(i<1 || i>(*L).length+1)
		return ERROR;
	if( (*L).length > (*L).size)
	{
		newbase = (int *)realloc((*L).elem, (LISTINCREMENT + (*L).size ) * sizeof(int));
		if(!newbase)
			exit(ERROR);
		(*L).elem = newbase;
		(*L).size = LISTINCREMENT + (*L).size;
	}
	
	q = (*L).elem + i -1;


	//也就是插入点后面的元素都要往后挪一位

	for( p = (*L).elem + (*L).length-1 ;p>=q;--p)
	{
		*(p+1) = *p;

	}
	*q = e;

    ++ (*L).length;

	return OK;

}

int
define_create(List *L,int n)
{
	int i,j;
	int e;
	InitList(L);
	printf("please enter %d elements: ",n);
	scanf("%d",&e);
	InsertList(L,1,e);//if dont write like this divided,we cant get the result.
	for(i = 1;i<n;i++) //modify
	{
		scanf("%d",&e);

		// for(j = 0;j<(*L).length;j++)
		//  	if(e <= *((*L).elem + j) )
		//  		break;      
	    //InsertList(L,j+1,e);   //like this add order

	    InsertList(L,i+1,e);

	}

	return OK;
}

void
ListTraverse(List L,void(*visit)(int *))
{
	int * q;
	q = L.elem;

	//for(;(q ++)!= NULL;)
	for(int i = 1;i<=L.length;i++)
	{
		visit(q++);
	}

	printf("
");

}

void visit(int * c)
{
	printf(" %d ", *c );
}

int 
common_prefix(List LA,List LB)
{
	int i;
	int j = 0;
	int length;
	length = ( LA.length - LB.length ) ? LA.length : LB.length;
	for(i = 0;i<length;i++)
	{
		if(LA.elem[i] == LB.elem[i])
			j++;

	}

	return j;

}

int 
compare(List LA,List LB,int prefix)
{
	if(LA.length == prefix && LB.length == prefix)
		return 0;
	if(LA.elem[prefix] < LB.elem[prefix])
		return 1;
	if(LA.elem[prefix] > LB.elem[prefix])
		return 2;
	else
		return OK;
}

int main(int argc, char const *argv[])
{
	int n;
	int choose;
	List LA,LB;
	int prefix;
	printf("please enter the List A number: ");
	scanf("%d",&n);
	define_create(&LA,n);

	printf("please enter the List B number: ");
	scanf("%d",&n);
	define_create(&LB,n);

	ListTraverse(LA,visit);
	ListTraverse(LB,visit);


	prefix = common_prefix(LA,LB);
	choose = compare(LA,LB,prefix);

	switch(choose)
	{
		case 0:
			printf("A = B
");
			break;
		case 1:
		    printf("A < B
");
		    break;
		case 2:
		    printf("A > B
");
		    break;
		default:
		printf("no compare!!!
");

	}
		
	return 0;
}