《数据结构与算法之美》学习笔记 Day 1

数组的特点

数组是线性表，用一块连续的内存存一些相同类型的数据。

线性表意思是这个数据结构只有前后两个方向，所以树，图等这类不属于线性表。链表，队列，栈等也是线性表。和数组经常一块说的就是链表，链表的特点是插入删除方便，而数组的特点是随机访问。

连续的内存是为了数组内元素的随机访问，但是数组的插入和删除操作很费事，就是因为需要维护内存连续。假如说可以随意决定插入或删除的位置，那么肯定涉及到对应位置之前或之后整块内存内容的搬移，效率低就低在这里。如果数组是无序的，插入好办，直接在结尾添加新元素，删除的话还是得搬移。无序的数组里对于一段时间内的插入和删除，可以先记下需要插入的数据以及需要删除数据的位置，时间结束后把需要删除的数据位置上用需要插入的数据替换，然后位置不够的话新元素添加到结尾，位置还有剩的情况下只能搬移了，但是这样处理也比之前需要的搬移次数更少。再改进就是根据插入删除事件的多少，而不是给一个固定的时间，这样可以用一个正负数或者一个栈来表示状态。

相同类型的数据同样是为了数组内元素的随机访问，如果数据类型不同，一个元素占的空间就不一定一样，这样没法确保你推断的地址是一个元素的开头，也没办法确定你需要读连续的几个地址。变通一下，“数组”里存一个自己定义的数据结构，开头先说明是什么类型占多少内存，然后才是数据真正的内容，然后为了保证每个元素都是等长的，短的元素在数据真正的内容后面要附上一堆“0”。这样的坏处是如果插入了一个新的更长的元素，不仅要先空开给这个元素的位置，还需要给原来的每个元素后面都补上“0”，事情变得更麻烦了。这时候又有变通就是我这个“数组”只存指针，指针找那些非连续的内存不就好了吗？这个是可以的，但是又回到了原来的数组定义上，你的数组里存的实际上还是同一类型的数据。

实现

// Array_gp.h

#ifndef __ARRAY_H__
#define __ARRAY_H__

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

typedef struct Array
{
    // p指针的空间大小
    size_t size;
    // p指针已经使用的空间大小
    size_t len;
    // 数据类型的大小
    size_t typeSize;
    // 值复制函数
    void(*dup)(void *ptr, void *key);
    // 值释放函数
    void(*free)(void *ptr);
    // 值比较函数
    int(*match)(void *ptr, void *key);
    // 存放数据的指针
    void   *p;
}Array;

#define arraySetDupMethod(a, m) ((a)->dup = (m))
#define arraySetFreeMethod(a, m) ((a)->free = (m))
#define arraySetMatchMethod(a, m) ((a)->match = (m))

#define arrayGetDupMethod(a) ((a)->dup)
#define arrayGetFree(a) ((a)->free)
#define arrayGetMatchMethod(a) ((a)->match)

Array* arrayCreate();
void arrayInit(Array *array, int size, int typeSize);

int arrayInsert(Array *array, size_t pos, void *const value);
size_t arraySearchValue(Array *array, void* const value);
void* arrayIndex(Array *array, size_t index);
int arrayModify(Array *array, size_t pos, void *const value);

size_t arrayLen(Array *array);
size_t arraySize(Array *array);

void arrayEmpty(Array *array);
void arrayDelValue(Array *array, void *value);
void arrayDelIndex(Array *array, size_t pos);

#endif // !__ARRAY_H__

// Array_gp.c

#include "Array.h"

#include <string.h>
#include <stdbool.h>

Array* arrayCreate()
{
    struct Array *array = NULL;
    array = malloc(sizeof(*array));
    if (NULL == array)
    {
        return NULL;
    }

    array->p = NULL;

    array->size = 0;
    array->typeSize = 0;
    array->len = 0;

    array->dup = NULL;
    array->free = NULL;
    array->match = NULL;

    return array;
}

void arrayInit(Array *array, int size, int typeSize)
{
    if (NULL == array
        || typeSize <= 0
        || size < 0)
    {
        return;
    }

    void *p = calloc(1, size* typeSize);
    if (NULL == p)
    {
        return;
    }

    array->p = p;
    array->len = 0;
    array->size = size;
    array->typeSize = typeSize;
}

int arrayInsert(Array *array, size_t pos, void *const value)
{
    if (NULL == array)
    {
        return -1;
    }

    if (array->len >= array->size)
    {
        return -2;
    }

    if (pos > array->size || pos <= 0)
    {
        return -3;
    }

    char *pBegin = array->p;
    for (size_t i = array->len; i > pos - 1; --i)
    {
        void *pNew = pBegin + i * array->typeSize;
        void *pOld = pBegin + (i - 1) *array->typeSize;
        if (NULL != array->dup)
        {
            array->dup(pNew, pOld);
        }
        else
        {
            memcpy(pNew, pOld, array->typeSize);
        }
    }

    void *pCopy = (void*)(pBegin + ((pos - 1) * array->typeSize));
    if (NULL != array->dup)
    {
        array->dup(pCopy, value);
    }
    else
    {
        memcpy(pCopy, value, array->typeSize);
    }
    ++array->len;
    return 0;
}

size_t arraySearchValue(Array *array, void* const value)
{
    if (NULL == array)
    {
        return -1;
    }

    char *pBegin = array->p;
    size_t i = 0;
    for (; i < array->len; ++i)
    {
        int nCmp = 0;
        if (NULL != array->match)
        {
            nCmp = array->match(pBegin + i * array->typeSize, value);
        }
        else
        {
            nCmp = memcmp(pBegin + i * array->typeSize, value, array->typeSize);
        }

        if (nCmp == 0)
        {
            break;
        }
    }

    return i;
}

void* arrayIndex(Array *array, size_t index)
{
    if (NULL == array)
    {
        return NULL;
    }

    if (index > array->len
        || index <= 0)
    {
        return NULL;
    }

    char *pBegin = array->p;
    return pBegin + array->typeSize * (index - 1);
}

int arrayModify(Array *array, size_t pos, void *const value)
{
    if (NULL == array)
    {
        return -1;
    }
    if (pos > array->len
        || pos <= 0)
    {
        return -2;
    }

    char *pBegin = array->p;
    void *pOld = pBegin + (pos - 1) * array->typeSize;
    if (NULL != array->dup)
    {
        array->dup(pOld, value);
    }
    else
    {
        memcpy(pOld, value, array->typeSize);
    }

    return 0;
}

size_t arrayLen(Array *array)
{
    if (NULL == array)
    {
        return 0;
    }

    return array->len;
}

size_t arraySize(Array *array)
{
    if (NULL == array)
    {
        return 0;
    }

    return array->size;
}

void arrayEmpty(Array *array)
{
    if (NULL == array)
    {
        return;
    }

    free(array->p);
    array->p = NULL;
    free(array);
    array = NULL;
}

void arrayDelValue(Array *array, void *value)
{
    if (NULL == array)
    {
        return;
    }

    char* pBegin = array->p;
    bool bCopy = false;
    for (size_t i = 0; i < array->len; ++i)
    {
        if (!bCopy)
        {
            int nCmp = 0;
            if (NULL != array->match)
            {
                nCmp = array->match(pBegin + i * array->typeSize, value);
            }
            else
            {
                nCmp = memcmp(pBegin + i * array->typeSize, value, array->typeSize);
            }

            if (0 == nCmp)
            {
                bCopy = true;
                continue;
            }
        }
        else
        {
            void *pOld = pBegin + (i + 1) * array->typeSize;
            void *pNew = pBegin + i * array->typeSize;
            if (NULL != array->dup)
            {
                array->dup(pNew, pOld);
            }
            else
            {
                memcpy(pNew, pOld, array->typeSize);
            }
        }
    }

    if (bCopy)
    {
        --array->len;
    }
}

void arrayDelIndex(Array *array, size_t pos)
{
    if (NULL == array)
    {
        return;
    }

    if (pos > array->len || pos <= 0)
    {
        return;
    }

    char* pBegin = array->p;
    for (size_t i = pos - 1; i < array->len - 1; ++i)
    {
        void *pOld = pBegin + (i + 1) * array->typeSize;
        void *pNew = pBegin + i * array->typeSize;
        if (NULL != array->dup)
        {
            array->dup(pNew, pOld);
        }
        else
        {
            memcpy(pNew, pOld, array->typeSize);
        }
    }

    --array->len;
}

// array.c

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

struct array {
	int size;
	int used;
	int *arr;
};

void dump(struct array *array)
{
	int idx;

	for (idx = 0; idx < array->used; idx++)
		printf("[%02d]: %08d\n", idx, array->arr[idx]);
}

void alloc(struct array *array)
{
	array->arr = (int *)malloc(array->size * sizeof(int));
}

int insert(struct array *array, int elem)
{
	int idx;
	if (array->used >= array->size)
		return -1;

	for (idx = 0; idx < array->used; idx++) {
		if (array->arr[idx] > elem)
			break;
	}

	if (idx < array->used)
		memmove(&array->arr[idx+1], &array->arr[idx],
			(array->used - idx) * sizeof(int));

	array->arr[idx] = elem;
	array->used++;
	return idx;
}

int delete(struct array *array, int idx)
{
	if (idx < 0 || idx >= array->used)
		return -1;

	memmove(&array->arr[idx], &array->arr[idx+1],
		(array->used - idx - 1) * sizeof(int));
	array->used--;
	return 0;
}

int search(struct array *array, int elem)
{
	int idx;

	for (idx = 0; idx < array->used; idx++) {
		if (array->arr[idx] == elem)
			return idx;
		if (array->arr[idx] > elem)
			return -1;
	}

	return -1;
}

int main()
{
	int idx;
	struct array ten_int = {10, 0, NULL};

	alloc(&ten_int);
	if (!ten_int.arr)
		return -1;
	insert(&ten_int, 1);
	insert(&ten_int, 3);
	insert(&ten_int, 2);
	printf("=== insert 1, 3, 2\n");
	dump(&ten_int);

	idx = search(&ten_int, 2);
	printf("2 is at position %d\n", idx);
	idx = search(&ten_int, 9);
	printf("9 is at position %d\n", idx);

	printf("=== delete [6] element \n");
	delete(&ten_int, 6);
	dump(&ten_int);
	printf("=== delete [0] element \n");
	delete(&ten_int, 0);
	dump(&ten_int);
	return 0;
}