数据结构C-数组-顺序表（三）

作者: 江海大初学者 | 来源:发表于2019-01-18 13:43 被阅读0次

数据结构中有一种结构叫顺序结构，这种结构的数据在内存中是连续的。

图1 顺序表的内存示意图

其实这种结构就是数组。我们都知道，当你创建一个数组的时候，那么计算机就会在内存中开辟一个连续的空间。比如，int a[5]，那么计算机就会在内存中开辟一个5个连续的空间用来存储数据。

数组的特点就是长度固定，可以通过索性快速搜索。但是数组也有缺点，比如我们定义的数组长度为5，那么我们就无法为他添加第6个数据，所以为了解决这个问题，我们要重新开辟一个具有6个长度的数组。所以我们需要对数组重新封装，封装出一个功能强大的数组，而这个强大的数组就是我们要学习的顺序表。

既然是数据结构，那么肯定是要定义结构体的。那么第一点就是如何定义出需要的结构体。首先我们先定义一个最简单的数组，比如：int arr[5]，那这个就定义了一个数组。其次我们如何知道数组中元素的个数呢？我们在添加一个size变量即可，默认的时候size为0，每添加一个元素就执行size++，删除一个元素就执行size--。这样我们就定义出结构体了。

typedef struct {
    int array[5];
    int length;
} SeqList;

为了让这个结构体的可读性更好，我们把数字提取出来，作为全局常量来使用。

const int CAPACITY = 5;  //CAPACITY是容量的意思

typedef struct {
    int array[CAPACITY];
    int length;
} SeqList;

定义好了结构体，我们就需要使用结构体了，首先我们需要声明这个结构体变量

    SeqList list;

1. 初始化这个结构体init()

当我们声明SeqList的时候，编译器已经为list和length分配内存空间了，但是此时里面都是垃圾值，而list我们后面会通过操作把里面的值替换掉，所以不用初始化它，故我们只需要把这个length设为0即可。

void init(SeqList * list) {
    list-> length = 0;
}

2. 判断顺序表是否为空isEmpty()

顺序表是否为空的标识是顺序的长度是否为0即可。返回布尔值，等于0为true，等于1为false。由于返回的是的布尔值，而c语言中没有bool类型，以及关键词true和false，所以我们需要自己定义。

#define true 1
#define false 0

typedef int bool;

bool isEmpty(SeqList * list) {
    return list->length == 0;
}

3. 判断线性表是否已满isFull()

判断顺序表是否为满，只需要判断顺序表长度是否等于顺序表的容量

bool isFull(SeqList * list) {
  return list->length == CAPACITY;
}

4. 获得元素get()

获得某个元素只需要使用数组下标即可

int get(SeqList * list, int index) {
  return list->array[index];
}

如果要快速获得第一个或者最后一个元素，我们可以在添加以下两个方法

//获得第一个元素
int getFirst(SeqList * list) {
  return list->array[0];
}
//获得最后一个元素
int getLast(SeqList * list) {
  return list->array[list->length-1];
}

5.查找元素的下标

有时候我们需要根据元素来查找下标，如果找到则返回响应的下标，否则返回-1。
查找算法只需要从第一个元素开始，依次与e进行比较。

int locateElem(SeqList * list, int e) {
  for(int i=0; i<list->length; i++) {
     if(list->array[i] == e) {
       return i; 
     }
  }
  return -1;
}

6. 插入元素

插入操作就是在顺序表的第index位置插入新的元素e。
在第index位置插入元素e，只需要把从第i个元素依次往后移动一个位置，然后把元素e赋值给第index位置的元素。移动元素时，先移动最后一个元素，再移动倒数第二个元素，以此类推。

例如有一个顺序表，[6,2,3,1]

顺序表[6,2,3,1]

如果我们要在第1的位置插入元素5（最小是第0个元素，符合计算机内部逻辑）

在第1的位置插入元素5
这个时候我们只需将1往后移动一个位置，3再往后移动一个位置，2往后移动一个位置，最后把5赋值给1的位置。

操作过程

当然，在这个操作前，我们必须首先判断index的值是否合法，不合法直接报错，然后还有判断这个线性表是否为满，满了也是不能添加的。

当添加了一个元素后，它的长度要加1。

void insert(SeqList * list, int index, int e) {
  if(index<0 || index>list->length) {
    printf("Insert failed! Index is out of range!");
    exit(-1);
  }
  if(isFull(list)) {
    printf("Insert failed! The SeqList is full!");
    exit(-1);
  }
  for(int i=list->length-1; i>index; i--) {
    list->array[i+1] = list->array[I];
  }
  list->array[index] = e;
  list->length++;
}

7. 删除元素

删除元素就是删除线性表中第index个位置上的元素。假设我们要删除索引为2的元素，那么我们只需把后一个元素一次往前移动一个位置即可。

删除索引为2的元素

int deleteEl(SeqList * list, int index) {
  if(index < 0 || index > list->length) {
    printf("DeleteEl failed! Index error\n");
    exit(-1);
  }
  int delEl = list->array[index];
  for(int i = index; i< list->length-1; i--) {
    list->array[i] = list->array[i+1];
  }
  list->length--;
  return delEl;
}

基本代码：

//
//  main.c
//  SeqList
//
//  Created by 季晓东 on 2019/3/26.
//  Copyright © 2019 季晓东. All rights reserved.
//

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

#define true 1
#define false 0

const int CAPACITY = 5;  //CAPACITY是容量的意思

typedef int bool;

typedef struct {
    int array[CAPACITY];
    int length;
} SeqList;


void init(SeqList * list);
bool isEmpty(SeqList * list);
bool isFull(SeqList * list);
int get(SeqList * list, int index);
int getFirst(SeqList * list);
int getLast(SeqList * list);
int locateElem(SeqList * list, int e);
void insert(SeqList * list, int index, int e);
int deleteEl(SeqList * list, int index);

void init(SeqList * list) {
    list-> length = 0;
}

bool isEmpty(SeqList * list) {
    return list->length == 0;
}

bool isFull(SeqList * list) {
    return list->length == CAPACITY;
}

int get(SeqList * list, int index) {
    return list->array[index];
}

int getFirst(SeqList * list) {
    return list->array[0];
}

int getLast(SeqList * list) {
    return list->array[list->length-1];
}

int locateElem(SeqList * list, int e) {
    for(int i=0; i<list->length; i++) {
        if(list->array[i] == e) {
            return i;
        }
    }
    return -1;
}

void insert(SeqList * list, int index, int e) {
    if(index<0 || index>list->length) {
        printf("Insert failed! Index is out of range!");
        exit(-1);
    }
    if(isFull(list)) {
        printf("Insert failed! The SeqList is full!");
        exit(-1);
    }
    for(int i=list->length-1; i>index; i--) {
        list->array[i+1] = list->array[i];
    }
    list->array[index] = e;
    list->length++;
}

int deleteEl(SeqList * list, int index) {
    if(index < 0 || index > list->length) {
        printf("DeleteEl failed! Index error\n");
        exit(-1);
    }
    int delEl = list->array[index];
    for(int i = index; i< list->length-1; i++) {
        list->array[i] = list->array[i+1];
    }
    list->length--;
    return delEl;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    SeqList list;
    init(&list);
    
    for (int i=0; i<3; i++) {
        insert(&list, i, i+11);
    }
    
    for (int i=0; i<3; i++) {
        printf("%d,",get(&list, i));
    }
    printf("\n");
    
    deleteEl(&list, 1);
    
    for (int i=0; i<list.length; i++) {
        printf("%d,",get(&list, i));
    }
    printf("\n");
    
    return 0;
}

改进代码：

//
//  main.c
//  Array用来对数组进行封装，更好的实现对数组的操作
//s
//  代码规范：
//  1.  自定义bool数据类型及其值
//      typedef int bool;
//      #define true 1
//      #define false 0
//
//  2.  指针变量前加p
//      如 int *pArr;
//
//  3.  逗号后面加空格，左大括号左边加空格，&&或||两边加空格，等号两边加空格
//
//
//  算法：
//      1.获得数组的有效的个数
//      2.获得数组的容量
//      3.判断数组是否为空
//      4.判断数组是否已满
//      5.插入某个元素
//      6.查找某个元素
//      7.修改某个元素
//      8.删除某个元素
//      9.是否包含某个元素
//      10.查找某个元素的位置
//
//

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

//定bool类型的值true|false
#define true 1
#define false 0

#define EXIT -1
#define ZERO 0

//自定义bool数据类型
typedef int bool;

/**
 自定义结构体数据类型Array
 如：Array arr等价于struct Array arr
 */
typedef struct Array{
    //数组的第一个元素
    int *pBaseArray;
    
    //数组的有效元素个数
    int size;
    
    //数组的总容量   0 <= size <= capacity
    int capacity;
}Array;

//----------------------------------------------函数声明----------------------------------------------------------------

//初始化数组, capacity为数组的总容量
void init(Array *pArr, int capacity);

//获得有效元素的个数
int getSize(Array *pArr);

//获得数组的容量
int getCapacity(Array *pArr);

//判断数组是否为空
bool isEmpty(Array *pArr);

//判断数组是否已满
bool isFull(Array *pArr);

//在第index位置添加元素e，index从0开始
void add(Array *pArr, int index, int e);

//在数组最前添加元素
void addFirst(Array *pArr, int e);

//在数组最后添加元素
void addLast(Array *pArr, int e);

//查找第index位置上的元素，index从0开始
int get(Array *pArr, int index);

//查找第一个元素
int getFirst(Array *pArr);

//查找最后一个元素
int getLast(Array *pArr);

//修改元素
void set(Array *pArr, int index, int e);

//判断数组中是否包含元素e
bool contains(Array *pArr, int e);

//删除index位置上的元素，index从0开始
int delete(Array *pArr, int index);

//删除第一个元素
int deleteFirst(Array *pArr);

//删除最后一个元素
int deleteLast(Array *pArr);

//查找第一个元素e的位置，没有查到则返回-1
int indexOf(Array *pArr, int e);

//销毁数组
void destory(Array *pArr);

//显示数组信息
void show(Array *pArr);

//自定义错误提示
void error(char* msg);

//自定义警告提示
void warning(char* msg);

//----------------------------------------------函数实现----------------------------------------------------------------

void init(Array *pArr, int capacity) {
    //为pBaseArray分配sizeof(int) * capacity个内存空间
    pArr->pBaseArray = (int *)malloc(sizeof(int) * capacity);
    
    //如果pBaseArray为空,则内存分配失败，退出程序
    if (pArr->pBaseArray == NULL) {
        error("Array memory allocation failed.");
        exit(EXIT);
    }
    
    //初始条件总容量是用户传进来的总容量
    pArr->capacity = capacity;
    
    //初始条件元素个数为0
    pArr->size = 0;
}

int getSize(Array *pArr) {
    return pArr->size;
}

int getCapacity(Array *pArr) {
    return pArr->capacity;
}

bool isEmpty(Array *pArr) {
    return pArr->size == ZERO;
}

bool isFull(Array *pArr) {
    return pArr->size == pArr->capacity;
}

void add(Array *pArr, int index, int e) {
    //判断数组是否已满，不满才可以添加
    if (isFull(pArr)) {
        warning("Array is full.");
        return;
    }
    
    for (int i = pArr->size; i>index; i--) {
        pArr->pBaseArray[i] = pArr->pBaseArray[i-1];
    }
    pArr->pBaseArray[index] = e;
    
    //维护size
    pArr->size++;
}

void addFirst(Array *pArr, int e) {
    add(pArr, ZERO, e);
}

void addLast(Array *pArr, int e) {
    //判断数组是否已满，不满才可以添加
    if (isFull(pArr)) {
        warning("Array is full.");
        return;
    }
    
    //在数组后面添加就是在size的位置添加元素e
    pArr->pBaseArray[pArr->size] = e;
    
    //维护size
    pArr->size++;
}

int get(Array *pArr, int index) {
    if (index<0 && index>=pArr->size) {
        error("Index out of range.");
        exit(EXIT);
    }
    if (isEmpty(pArr)) {
        error("Array is empty.");
        exit(EXIT);
    }
    return pArr->pBaseArray[index];
}

int getFirst(Array *pArr) {
    if (isEmpty(pArr)) {
        error("Array is empty.");
        exit(EXIT);
    }
    return pArr->pBaseArray[ZERO];
}

int getLast(Array *pArr) {
    if (isEmpty(pArr)) {
        error("Array is empty.");
        exit(EXIT);
    }
    return pArr->pBaseArray[pArr->size-1];
}

void set(Array *pArr, int index, int e) {
    if (index<0 && index>=pArr->size) {
        error("Index out of range.");
        exit(EXIT);
    }
    if (isEmpty(pArr)) {
        error("Array is empty.");
        exit(EXIT);
    }
    pArr->pBaseArray[index] = e;
}

bool contains(Array *pArr, int e) {
    for (int i=0; i<pArr->size; i++) {
        if (pArr->pBaseArray[i] == e) {
            return true;
        }
    }
    return false;
}

int delete(Array *pArr, int index) {
    if (index<0 && index>=pArr->size) {
        error("Index out of range.");
        exit(EXIT);
    }
    if (isEmpty(pArr)) {
        error("Array is empty.");
        exit(EXIT);
    }
    int delArr = pArr->pBaseArray[index];
    for (int i=index; i<pArr->size-1; i++) {
        pArr->pBaseArray[i] = pArr->pBaseArray[i+1];
    }
    pArr->size--;
    return delArr;
}

int deleteFirst(Array *pArr) {
    return delete(pArr, ZERO);
}

int deleteLast(Array *pArr) {
    if (isEmpty(pArr)) {
        error("Array is empty.");
        exit(EXIT);
    }
    pArr->size--;
    return pArr->pBaseArray[pArr->size-1];
}

int indexOf(Array *pArr, int e) {
    for (int i=0; i<pArr->size; i++) {
        if (pArr->pBaseArray[i] == e) {
            return I;
        }
    }
    return -1;
}

void destory(Array *pArr) {
    free(pArr);
    pArr=NULL;
}

void show(Array *pArr) {
    printf("Array: capacity=%d, size=%d, ", pArr->capacity, pArr->size);
    printf("[");
    for (int i=0; i<pArr->size; i++) {
        printf("%d", pArr->pBaseArray[I]);
        if (i != pArr->size-1) {
            printf(", ");
        }
    }
    printf("]\n ");
    return;
}

void error(char* msg) {
    printf("\n---------------------------------------------------------------------------\n");
    printf("ERROR: %s", msg);
    printf("\n---------------------------------------------------------------------------\n\n");
}

void warning(char* msg) {
    printf("\n---------------------------------------------------------------------------\n");
    printf("WARNING: %s", msg);
    printf("\n---------------------------------------------------------------------------\n\n");
}

//----------------------------------------------main函数----------------------------------------------------------------

int main(int argc, const char * argv[]) {
    
    Array array;
    
    init(&array, 5);
    
    for (int i=0; i<4; i++) {
        add(&array, i, i);
        show(&array);
    }
    
    if (contains(&array, 0)) {
        printf("true\n");
    }else{
        printf("false\n");
    }
    
    printf("get 1: %d\n", get(&array, 1));
    
    printf("getFirst: %d\n", getFirst(&array));
    
    printf("getLast: %d\n", getLast(&array));
    
    printf("indexOf 3: %d\n", indexOf(&array, 3));
    
    set(&array, 2, 1000);
    show(&array);
    
    addFirst(&array, -1);
    show(&array);
    
    delete(&array, 0);
    show(&array);
    
    deleteFirst(&array);
    show(&array);
    
    deleteLast(&array);
    show(&array);
    
    addLast(&array, 10);
    show(&array);
    
//    destory(&array);
    
    addLast(&array, 10);
    show(&array);
    
    return 0;
}

Screen Shot 2019-01-18 at 2.05.43 PM.png

Screen Shot 2019-01-18 at 2.08.00 PM.png

数据结构C-数组-顺序表（三）

1. 初始化这个结构体init()

2. 判断顺序表是否为空isEmpty()

3. 判断线性表是否已满isFull()

4. 获得元素get()

5.查找元素的下标

6. 插入元素

7. 删除元素

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读