第五周：C语言数据结构 动态数组

basketball610

1.如何定义一个指向函数的指针类型：
typedef int arr_cmp(const void *, const void *)

2. 动态数组 （老师代码）：
::::::::::::::
darr.c
::::::::::::::
#include <stdlib.h>
#include <string.h>
#include "darr.h"


DARR *darr_create(int size)
{
    DARR *new;

    new = malloc(sizeof(*new));
    if(new == NULL)
        return NULL;
    new->size = size;
    new->num = 0;
    new->arr = NULL;

    return new;
}
int darr_insert(DARR *ptr , const void *data,int ind)
{
    void *tmp;
    tmp = realloc(ptr->arr ,ptr->size * (ptr->num + 1));
    if(tmp == NULL)
        return -1;
    ptr->arr = tmp;

    if(ind == DARR_BACKWARD || ind >= ptr->num)
    {
        memcpy(ptr->arr + ptr->num * ptr->size,data,ptr->size);
        ptr->num ++;
        return 0;
    }
    else
        if(ind == DARR_FORWARD)
            ind = 0;

    memmove(ptr->arr + ptr->size *(ind +1),ptr->arr + ptr->size * ind , ptr-
>size * (ptr->num - ind));
    memcpy(ptr->arr + ptr->size * ind ,data,ptr->size);
    ptr->num ++;
    return 0;

}
void darr_travel(DARR *ptr,darr_op *op)
{
    int i;
    for(i = 0 ; i < ptr->num ; i++)
        op(ptr->arr + i * ptr->size);

}

int darr_delete(DARR *ptr,const void *key, darr_cmp *cmp)
{
    int i;

    for(i = 0 ; i < ptr->num ; i++)
    {
        if(cmp(key, ptr->arr + i * ptr->size) == 0)
        {
            memmove(ptr->arr + ptr->size *i,ptr->arr + ptr->size * (
i + 1),ptr->size * (ptr->num - i - 1));
           
            ptr->arr = realloc(ptr->arr, ptr->size * (ptr->num - 1))
;
            ptr->num --;

            if(ptr->num == 0)
                ptr->arr = NULL;
            return 0;

        }
    }
    return -1;


}

void *darr_find(DARR *ptr,const void *key, darr_cmp *cmp)
{
    int i;
    for(i = 0 ; i < ptr->num ; i++)
        if(cmp(key,ptr->arr + ptr->size * i) == 0)
            return (ptr->arr + ptr->size * i);
    return NULL;


}

void darr_destroy(DARR *ptr)
{
    free(ptr->arr);
    free(ptr);
}















::::::::::::::
darr.h
::::::::::::::
#ifndef _DARR_H_
#define _DARR_H_

#define DARR_FORWARD -1
#define DARR_BACKWARD -2

typedef struct
{
    int size;
    int num;
    char *arr;
}DARR;

typedef void  darr_op(void *);
typedef int darr_cmp(const void *,const void *);

DARR *darr_create(int size);
int darr_insert(DARR *ptr , const void *data,int ind);
void darr_travel(DARR *ptr,darr_op *op);

int darr_delete(DARR *ptr,const void *key, darr_cmp *cmp);
void darr_destroy(DARR *ptr);
void *darr_find(DARR *ptr,const void *key, darr_cmp *cmp);







#endif










::::::::::::::
main.c
::::::::::::::
#include <stdio.h>
#include "darr.h"

#define NAMESIZE 32

struct score
{
    int id;
    char name[NAMESIZE];
    int math;
};

static void print_s(void *record)
{
    struct score *d = record;
    printf("%d %s %d\n",d->id,d->name,d->math);
}

static int id_cmp(const void *key , const void *record)
{
    const int *k = key;
    const struct score *r = record;
    return (*k - r->id);
}
static int name_cmp(const void *key,const void *record)
{
    const char *k = key;
    const struct score *r = record;
    return (strcmp(k,r->name));
}
int main()
{
    int i;
    DARR *handle;
    struct score tmp, *datap;
    char str[] = "stu5";//str[] = "2";

    handle = darr_create(sizeof(struct score));
    if(handle == NULL)
        return -1;

    for(i = 0 ; i < 7 ; i++)
    {
        tmp.id = i;
        tmp.math = 100 - i;
        snprintf(tmp.name , NAMESIZE,"stu%d",i);

        darr_insert(handle,&tmp,DARR_FORWARD);
    }

    darr_travel(handle,print_s);
    printf("\n\n");
   
    i = 2;

//    darr_delete(handle,&i,id_cmp);
//    darr_delete(handle,str,name_cmp);
//    darr_travel(handle,print_s);
   
    datap = darr_find(handle,str,name_cmp);
    if(datap == NULL)
        printf("NO found!\n");
    else
        print_s(datap);

    return 0;
}