Question

求问一道数据结构的算法

int LocateElem_Sq(SqList,ElemType e,Status(*compare)(ElemType,ElemType))
i=1;
p=L.elem;
while(i<=L.length&&!(*compare)(*p++,e)) ++i;
if(i<=L.length) return i;
else return 0;
}
这个compare函数返回值是什么啊，网上查到是相等返回0，不等的话1或-1，如果这样的话不是只有相等的时候++i才会执行吗？那样不是在指针查到相等之前i一直是1？

Answer 1

函数compare()是一个自定义函数,其作用是比较两个数值是否相等.
如果两个数值相等,则compare()的返回值是1
如果两个数值不相等,则compare()的返回值是0

所以,只要两个数值不相等, i<=L.length是真, !(*compare)(*p++,e))也是真, 那么变量i会自动加1

以下是C语言程序的测试结果:

数组里的数据有: a b c d e

查找数据 c 在数组里的位置, 在第 3 位.


//C语言程序
#include <stdio.h>
#include <stdlib.h>

#define OVERFLOW -1
#define error     0
#define OK        1
#define LIST_INIT_SIZE 100

typedef char ElemType;
typedef int Status;

typedef struct
{
    ElemType *elem;
    int length;     //动态数组存有多少个数据
    int listsize;   //动态数组的最大长度
}SqList;

//比较两个数值是否相等
Status compare(ElemType a,ElemType b)
{
    if(a==b)
    {
        return OK; //两个数值相等,则返回OK=1
    }
    else
    {
        return error; //两个数值不等,则返回error=0
    }
}

//动态数组初始化
Status InitList_Sq(SqList *L)
{
    (*L).elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if( (*L).elem == NULL )
    {
        printf("\n分配内存错误.\n");
        exit(OVERFLOW);
    }
    (*L).length=0;
    (*L).listsize=LIST_INIT_SIZE;
    return OK;
}

//插入一个数据e,保持数组有序(所有数据从小到大排列)
Status Insert_Sort(SqList *L,ElemType e)
{
    int i;
    if((*L).length == 0)
    {
        (*L).elem[0]=e;
        (*L).length++;
        return OK;
    }
    for(i=(*L).length-1 ; i>=0 ; i--)
    {
        if(i==0 && (*L).elem[i]>e)
        {
            (*L).elem[i+1]=(*L).elem[i];
            (*L).elem[i]=e;
            break;
        }
        if((*L).elem[i]<e)
        {
            (*L).elem[i+1]=e;
            break;
        }
        else
        {
            (*L).elem[i+1]=(*L).elem[i];
        }
    }
    (*L).length++;

    return OK;
}

//找到数据e在数组里的位置
int LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType,ElemType))
{
    int i=1;
    ElemType *p;
    p=L.elem;

    while(i <= L.length && !(*compare)(*p++,e))
        ++i;

    if(i <= L.length)
        return i;
    else
        return 0;
}

//打印数组
void DispList_Sq(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
    {
        printf("%c ",L.elem[i]);
    }
    printf("\n");
}

//往数组里填入数据
void OrigList_Sq(SqList *L)
{
    char index;

    for(index='a'; index<='e'; index++)
    {
        Insert_Sort(L,index);
    }
}

int main()
{
    SqList L;
    ElemType x;
    int pos;

    InitList_Sq(&L);

    OrigList_Sq(&L);

    printf("数组里的数据有: ");
    DispList_Sq(L);

    x='c';
    pos=LocateElem_Sq(L,x,compare);
    if(pos==0)
    {
       printf("\n查找数据 %c 在数组里的位置, 没有找到.\n",x);
    }
    else
    {
       printf("\n查找数据 %c 在数组里的位置, 在第 %d 位.\n",x,pos);
    }

    return 0;
}