[数据结构与算法] 顺序表-数据结构(C语言)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 顺序表-数据结构(C语言) -> 正文阅读

[数据结构与算法]顺序表-数据结构(C语言)

顺序表

顺序表的构造

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

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 <stdio.h>
#include <stdlib.h>

#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("%d\n", insert(a, 1, 0));
    printf("%d\n", insert(a, 0, 1));
    printf("%d\n", insert(a, 2, 1));
    printf("%d\n", insert(a, 1, 2));
    printf("%d\n", insert(a, 0, 3));
    clear(a);
    return 0;
}

顺序表的扩容

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

#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("%d\n", insert(a, 1, 0));
    printf("%d\n", insert(a, 0, 1));
    printf("%d\n", insert(a, 2, 1));
    printf("%d\n", insert(a, 1, 2));
    printf("%d\n", insert(a, 0, 3));
    clear(a);
    return 0;
}

顺序表的查找

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

#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("%d\n", insert(a, 1, 0));
    printf("%d\n", insert(a, 0, 1));
    printf("%d\n", insert(a, 2, 1));
    printf("%d\n", insert(a, 1, 2));
    printf("%d\n", insert(a, 0, 3));
    printf("%d\n", search(a, 1));
    printf("%d\n", search(a, 4));
    clear(a);
    return 0;
}

顺序表的删除

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

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

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

#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("%d\n", insert(a, 0, 1));
    printf("%d\n", insert(a, 0, 2));
    printf("%d\n", delete_node(a, 1));
    printf("%d\n", search(a, 0));
    printf("%d\n", search(a, 1));
    clear(a);
    return 0;
}

顺序表的遍历

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

#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("%d\n", insert(a, 0, 1));
    printf("%d\n", insert(a, 0, 2));
    print(a);
    printf("%d\n", delete_node(a, 1));
    print(a);
    printf("%d\n", search(a, 0));
    printf("%d\n", search(a, 1));
    clear(a);
    return 0;
}