顺序表-数据结构(C语言)

#include 
#include 

typedef struct Vector {
	//  size 表示当前表中的最大容量 
	// length 表示当前顺序表中的元素的个数
    int size, length;
    // 定义一个int 类型的指针data , 用来指向存储元素的数组 
    int *data;
} Vector;
// 初始化函数  void init (Vector *vector ,int size)  表示构造一个容量为size 的顺序表
void init(Vector *vector, int size) {
	// 先把顺序表的容量vector->size 的值设为size;
	// 并把当前顺便表的元素个数 vector->lenght 设为0 
    vector->size = size;
    vector->length=0;
    // 将指向存储元素值的空间的指针初始化，让data 指向一段连续size 个 int 的空间。 
    vector->data = (int *)malloc(sizeof(int)  *size);
}


// 在函数结束前我们要释放占用的内存空间 ，否则会发生内存泄露
// 在 clear 函数中使用free 释放vector->data  以及指针vector指向的内存空间。
void clear(Vector *vector) {
    free(vector->data);
    free(vector);
}

int main() {
    Vector *a = (Vector *)malloc(sizeof(Vector));
    init(a, 100);
    clear(a);
    return 0;
}

#include 
#include 

#define ERROR 0
#define OK 1

typedef struct Vector {
    int size, length;
    int *data;
} Vector;

void init(Vector *vector, int size) {
    vector->size = size;
    vector->length = 0;
    vector->data = (int *)malloc(sizeof(int) * size);
}
//  插入函数已经定义好了， 有三个参数 vector、loc  和 value , 其中vector 指针表示茶树元素的顺序表， loc 表示将要插入的位置， value 表示插入的元素值。
// 也就意味着，在插入完成后 $data_loc$的值为value. 当插入到第i个位置后，需要将data loc 后面的所有元素向后顺次移动，并将顺序表的总长度增加 1 ， 如果插入成功，则返回 OK, 否则返回ERROR , 我们已将将OK ， 定义为 1 ，将ERROR 定义为0 了。
//  首先我们需要判断要插入的位置是否合法。记当前顺序表的长度len 为 vector->length , 那么当前 data0 到 datalen -1  都存储着元素，所以0 到 len 都是可以插入的位置。
//  如果传入的参数 loc 比 0 小， 或者 len 大， 那么直接返回ERROR 。

//  除了判断loc 是否合法， 我们还需要判断顺序表当前元素的个数是否已经达到容量的上限 。
//  如果已经达到了上限 ，也就是说 顺序表中数量 vector->length 大于等于 顺序表的容量 vector->size  那么就和上一步的操作一样，直接返回ERROR. 
int insert(Vector *vector, int loc, int value) {
    if(loc < 0 || loc > vector->length) {
      return  ERROR;
    }
    if(vector->length >= vector->size) {
        return ERROR;
    }
    // 在顺序表中，每次向指定位置 loc 插入一个元素之前，都要将loc 之后的所有元素顺次向后移动，从而给新的元素腾出一个空间。
    // 令循环变量 i  从 vector->length  循环到不大于 loc 退出， 将 vector->data[i-1] 的赋值给 vector->data[i].
    for(int i = vector->length; i > loc; --i) {
        vector->data[i] = vector->data[i-1];
        
    }
    // 将插入的元素值 value 赋值 给 vector->data[loc].
    vector->data[loc] = value;
    //  还需要将 顺序表中元素个数加 1 ，以便后续中的各种判断
    vector->length++;
    // 返回OK 
    return OK;
}

void clear(Vector *vector) {
    free(vector->data);
    free(vector);
}

int main() {
    Vector *a = (Vector *)malloc(sizeof(Vector));
    init(a, 100);
    printf("%dn", insert(a, 1, 0));
    printf("%dn", insert(a, 0, 1));
    printf("%dn", insert(a, 2, 1));
    printf("%dn", insert(a, 1, 2));
    printf("%dn", insert(a, 0, 3));
    clear(a);
    return 0;
}

#include 
#include 

#define ERROR 0
#define OK 1

typedef struct Vector {
    int size, length;
    int *data;
} Vector;

void init(Vector *vector, int size) {
    vector->size = size;
    vector->length = 0;
    vector->data = (int *)malloc(sizeof(int) * size);
}

// 请在下面实现扩容函数 expand
//  通常来讲， 每次扩容都是将容量修改为之前的两倍。 扩容时，要重新开辟一块空间，将原有的数据依次拷贝过去，再将原来的空间释放。
//   扩容函数的参数为 Vector 类型的指针变量 vector , 表示要处理的顺序表 函数没有返回值 。
// 首先 定义一个指向int 的指针 old_data， 并赋值为当前 vector->data  指向的空间地址。 
//  下面我们要 将 容量 vector->size  更新为原来的2 倍， 并借助 malloc 开辟一段 新容量大小的连续空间，vector->data  指向它的首地址。 
//  令循环变量 i 从  循环到不小于 vector->length 时退出，并将 old_data[i] 的值 复制到 vector->data[i] 里。 即使for  循环中只有一条语句， 也要记得加上大括号 。
//  在扩容函数最后 把旧的空间进行回收。 
// 我们把 insert 函数里判断是否达 容量上限里面的 return ERROR，  注释掉 
//  在刚刚注释的代码下面调用 扩容操作 。

void expand(Vector *vector) {
    int *old_data = vector->data; 
    vector->size = vector->size * 2;
    vector->data = (int *)malloc(sizeof(int) * vector->size); 
    // vector->data 
    for(int i = 0; i < vector->length; ++i) {
        vector->data[i] = old_data[i]; 
    }
    free(old_data);
    
        
}

int insert(Vector *vector, int loc, int value) {
    if (loc < 0 || loc > vector->length) {
         return ERROR;
    }
    if (vector->length >= vector->size) {
        // return ERROR;
        expand(vector);
    }
    for (int i = vector->length; i > loc; --i) {
        vector->data[i] = vector->data[i - 1];
    }
    vector->data[loc] = value;
    vector->length++;
    return OK;
}

void clear(Vector *vector) {
    free(vector->data);
    free(vector);
}

int main() {
    Vector *a = (Vector *)malloc(sizeof(Vector));
    init(a, 100);
    printf("%dn", insert(a, 1, 0));
    printf("%dn", insert(a, 0, 1));
    printf("%dn", insert(a, 2, 1));
    printf("%dn", insert(a, 1, 2));
    printf("%dn", insert(a, 0, 3));
    clear(a);
    return 0;
}

#include 
#include 

#define ERROR 0
#define OK 1

typedef struct Vector {
    int size, length;
    int *data;
} Vector;

void init(Vector *vector, int size) {
    vector->size = size;
    vector->length = 0;
    vector->data = (int *)malloc(sizeof(int) * size);
}

void expand(Vector *vector) {
    int *old_data = vector->data;
    vector->size = vector->size * 2;
    vector->data = (int *)malloc(sizeof(int) * vector->size);
    for (int i = 0; i < vector->length; ++i) {
        vector->data[i] = old_data[i];
    }
    free(old_data);
}

int insert(Vector *vector, int loc, int value) {
    if (loc < 0 || loc > vector->length) {
        return ERROR;
    }
    if (vector->length >= vector->size) {
        //return ERROR;
        expand(vector);
    }
    for (int i = vector->length; i > loc; --i) {
        vector->data[i] = vector->data[i - 1];
    }
    vector->data[loc] = value;
    vector->length++;
    return OK;
}
// 我们使用最朴素的查找算法，依次枚举所有顺序表中元素，判断元素的值是否和传入的参数 value 相等， 如果相等则直接返回对应的下标即可。
//  用 for 循环进行枚举，令循环变量i 从 0  循环到不小于 vector->length 时退出， 
// 在循环内部，对枚举的每一个下标i, 如果对应的vector->data[i] 和 value 的值相等， 那么直接返回下标i 的 值。  
int search(Vector *vector, int value) {
    for(int i = 0; i < vector->length; ++i) {
        if(vector->data[i] == value) {
            return i;
        }
        
    }
    //  如果在顺序表中没有找到和 value 的值相等的元素,直接返回 -1. 
    // 在主函数中调用 search() 
    return -1;
}

void clear(Vector *vector) {
    free(vector->data);
    free(vector);
}

int main() {
    Vector *a = (Vector *)malloc(sizeof(Vector));
    init(a, 100);
    printf("%dn", insert(a, 1, 0));
    printf("%dn", insert(a, 0, 1));
    printf("%dn", insert(a, 2, 1));
    printf("%dn", insert(a, 1, 2));
    printf("%dn", insert(a, 0, 3));
    printf("%dn", search(a, 1));
    printf("%dn", search(a, 4));
    clear(a);
    return 0;
}

顺序表的删除操作
顺序表的删除操作是指, 将顺序表中第i 个位置（0 < i < len ） 的元素从顺序表中删除，并将该元素之后的所有元素顺次向前移动一个位置，len 表示顺序表元素个数。
delete_nod 函数已经定义好了, 除了 Vector 类型的指针参数 vector , 还有一个参数 index ， 表示已经删除测下标 , 返回值为int 类型， 表示是否删除成功。

首先对传入参数的合法性进行判断， 如果传入的下标比0 小， 或者大于等于len , 那么直接返回 ERROR .

#include 
#include 

#define ERROR 0
#define OK 1

typedef struct Vector {
    int size, length;
    int *data;
} Vector;

void init(Vector *vector, int size) {
    vector->size = size;
    vector->length = 0;
    vector->data = (int *)malloc(sizeof(int) * size);
}

void expand(Vector *vector) {
    int *old_data = vector->data;
    vector->size = vector->size * 2;
    vector->data = (int *)malloc(sizeof(int) * vector->size);
    for (int i = 0; i < vector->length; ++i) {
        vector->data[i] = old_data[i];
    }
    free(old_data);
}

int insert(Vector *vector, int loc, int value) {
    if (loc < 0 || loc > vector->length) {
        return ERROR;
    }
    if (vector->length >= vector->size) {
        //return ERROR;
        expand(vector);
    }
    for (int i = vector->length; i > loc; --i) {
        vector->data[i] = vector->data[i - 1];
    }
    vector->data[loc] = value;
    vector->length++;
    return OK;
}

int search(Vector *vector, int value) {
    for (int i = 0; i < vector->length; ++i) {
        if (vector->data[i] == value) {
            return i;
        }
    }
    return -1;
}

int delete_node(Vector *vector, int index) {
    if (index < 0 || index >= vector->length) {
         return ERROR;
    }
    // 接下来 , 需要将index  后面的所有元素顺次向前移动， 令循环变量 i  从 index + 1  循环不小于 vector->length 时退出，将vector->data[i] 的值赋给 vactor->data[i-1]. 
    
    for(int i = index + 1;  i <  vector->length; ++i) {
          vector->data[i-1] = vector->data[i];
    }
    // 顺序表中实际上 剩下 vector->length - 1 个 元素了，接下来在delete_node 函数中将 vector->length 更新。 
    // 将 OK 作为 delete_node 函数的返回值返回。
    
    vector->length--;
    return OK;
}

void clear(Vector *vector) {
    free(vector->data);
    free(vector);
}

int main() {
    Vector *a = (Vector *)malloc(sizeof(Vector));
    init(a, 100);
    printf("%dn", insert(a, 0, 1));
    printf("%dn", insert(a, 0, 2));
    printf("%dn", delete_node(a, 1));
    printf("%dn", search(a, 0));
    printf("%dn", search(a, 1));
    clear(a);
    return 0;
}

#include 
#include 

#define ERROR 0
#define OK 1

typedef struct Vector {
    int size, length;
    int *data;
} Vector;

void init(Vector *vector, int size) {
    vector->size = size;
    vector->length = 0;
    vector->data = (int *)malloc(sizeof(int) * size);
}

void expand(Vector *vector) {
    int *old_data = vector->data;
    vector->size = vector->size * 2;
    vector->data = (int *)malloc(sizeof(int) * vector->size);
    for (int i = 0; i < vector->length; ++i) {
        vector->data[i] = old_data[i];
    }
    free(old_data);
}

int insert(Vector *vector, int loc, int value) {
    if (loc < 0 || loc > vector->length) {
        return ERROR;
    }
    if (vector->length >= vector->size) {
        //return ERROR;
        expand(vector);
    }
    for (int i = vector->length; i > loc; --i) {
        vector->data[i] = vector->data[i - 1];
    }
    vector->data[loc] = value;
    vector->length++;
    return OK;
}

int search(Vector *vector, int value) {
    for (int i = 0; i < vector->length; ++i) {
        if (vector->data[i] == value) {
            return i;
        }
    }
    return -1;
}

int delete_node(Vector *vector, int index) {
    if (index < 0 || index >= vector->length) {
        return ERROR;
    }
    for (int i = index + 1; i < vector->length; ++i) {
        vector->data[i - 1] = vector->data[i];
    }
    vector->length = vector->length - 1;
    return OK;
}
// 顺序表的遍历操作，是指将顺序表中 的所有元素顺次输出。 我们将会把顺序表的所有元素输出到一行中，并用空格分隔。Vector 的遍历函数 print  已经定义好了， 
//  我们在 print  函数中写好的输出所有元素的循环体， 令循环变量 i 从 0 循环到不小于vector->length 时退出，并协商一对 大括号。
//  在循环内部，我们先把输出的每个元素之间的空格输出.  如果不是在行首，也就是说，i 大于0  那么就输出一个空格， 使用 printf 输出。
// 输出完空格之后， 把当前第i个 元素也输出。 
//  输出完所有元素之后， 再输出一个空行。 

void print(Vector *vector) {
    for (int i = 0; i < vector->length; ++i) {
        if(i > 0) {
            printf(" ");
        }
        printf("%d",vector->data[i]);
    }
    printf("n");
    
}

void clear(Vector *vector) {
    free(vector->data);
    free(vector);
}

int main() {
    Vector *a = (Vector *)malloc(sizeof(Vector));
    init(a, 100);
    printf("%dn", insert(a, 0, 1));
    printf("%dn", insert(a, 0, 2));
    print(a);
    printf("%dn", delete_node(a, 1));
    print(a);
    printf("%dn", search(a, 0));
    printf("%dn", search(a, 1));
    clear(a);
    return 0;
}