（数据结构&C语言）顺序表

专业成都网站建设公司，做排名好的好网站，排在同行前面，为您带来客户和效益!成都创新互联为您提供成都网站建设，五站合一网站设计制作，服务好的网站设计公司，成都网站建设、成都网站设计负责任的成都网站制作公司!文章目录

• • （数据结构&C语言）顺序表
  • • 编写初始化操作
    • 编写插入操作
    • 编写删除操作
    • 获取指定位置上的元素
    • 查找指定元素的位置
    • 获取长度
    • 相关问题

线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据元素。

基于数组，编写一些额外的操作来强化为线性表，像这样底层以恶案采用顺序存储实现的线性表，称为顺序表。

从上图不难看出线性表的长度应始终小于数组的长度。

这里我们可以先定义一个新的结构体类型，将一些需要用到的数据保存在一起，这里我们以int类型的线性表为例：

struct List {int * array;
  int capacity;  //表示底层数组的初始容量
};
typedef struct List * ArrayList;  //为方便

编写初始化操作

_Bool initList(ArrayList list) {list->array = malloc(sizeof(int) * 10);
  if(list->array == NULL) return 0;  //需要判断如果申请的结果为NULL的话表示内存空间申请失败
  list->capacity = 10;  //容量设定为10
  list->size = 0;  //元素数量默认为0
  return 1
}

编写插入操作

void insertList(ArrayList list, int element, int index){//index表示插入位序
  if(index< 1 || index >list->size + 1) return 0;   //如果在非法位置插入，返回0表示插入操作执行失败
    for (int i = list->size; i >index - 1; --i)  
        list->array[i] = list->array[i - 1];//先使用for循环将待插入位置后续的元素全部挪到后一位
    list->array[index - 1] = element;    //挪完之后，位置就腾出来了，直接设定即可
    list->size++;  //元素数量+1
}

如果我们的表已经装满了，也就是说size已经达到申请的内存空间大的大小了，那么此时我们就需要考虑进行扩容：

_Bool insertList(ArrayList list, int element, int index){if(index< 1 || index >list->size + 1) return 0;
    if(list->size == list->capacity) {//size已经到达大的容量
        int newCapacity = list->capacity + (list->capacity >>1);   //先计算一下新的容量大小，这里我取1.5倍原长度，当然也可以想扩多少扩多少
        int * newArray = realloc(list->array, sizeof(int) * newCapacity);  //函数realloc重新申请更大的内存空间
        if(newArray == NULL) return 0;   //如果申请失败，那么就确实没办法插入了，只能返回0表示插入失败了
        list->array = newArray;
        list->capacity = newCapacity;
    }
    for (int i = list->size; i >index - 1; --i)
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;
    list->size++;
    return 1;
}

realloc函数可以做到控制动态内存开辟的大小，重新申请的内存空间大小就是我们指定的新的大小，并且原有的数据也会放到新申请的空间中。当然如果因为内存不足之类的原因导致内存空间申请失败，那么会返回NULL，所以也需要进行判断。

编写删除操作

_Bool deleteList(ArrayList list,int index) {if(index< 1 || index >list->size) return 0;
    for (int i = index - 1; i< list->size - 1; ++i)
      list->array[i] = list->array[i + 1]; //依次把后面的元素覆盖到前一个
  list->size--;
  return 1;
}

获取指定位置上的元素

int getList(ArrayList list, int index){if(index< 1 || index >list->size) return NULL;   //如果超出范围就返回NULL
    return list->array[index - 1];
}

查找指定元素的位置

int findList(ArrayList list, int element){for (int i = 0; i< list->size; ++i) {if(list->array[i] == element) return i + 1;  //直到找到指定元素，返回位序
    }
    return -1;  //如果遍历完了都没找到，那么就返回-1
}

获取长度

int sizeList(ArrayList list){return list->size;   //直接返回size
}

完整代码如下：

#include#includestruct List {int * array;
    int capacity;
    int size;
};
typedef struct List * ArrayList;

_Bool initList(ArrayList list) {list->array = malloc(sizeof(int) * 10);
    if(list->array == NULL) return 0;
    list->capacity = 10;
    list->size = 0;
    return 1;
}

_Bool insertList(ArrayList list,int element,int index) {if(index< 1 || index >list->size + 1) return 0;
    
    if(list->size == list->capacity) {int newCapacity = list->capacity + (list->capacity >>1);
        int * newArray = realloc(list->array, sizeof(int) * newCapacity);
        if(newArray == NULL) return 0;
        list->capacity = newCapacity;
        list->array = newArray;
    }
    
    for (int i = list->size; i >index - 1; --i)
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;
  list->size++;
    return 1;
}

_Bool deleteList(ArrayList list,int index) {if(index< 1 || index >list->size) return 0;
    
    for (int i = index - 1; i< list->size - 1; ++i)
        list->array[i] = list->array[i + 1];
    list->size--;
    return 1;
}

int getList(ArrayList list,int index) {if(index< 1 || index >list->size) return 0;
    return list->array[index - 1];
}

int findList(ArrayList list,int element) {for (int i = 0; i< list->size - 1; ++i)
        if(list->array[i] == element) return i + 1;
    return -1;
}

int sizeList(ArrayList list) {return list->size;
}

void printList(ArrayList list){//用于打印链表
    for (int i = 0; i< list->size; ++i)
        printf("%d ", list->array[i]);
    printf("\n");
}

int main() {struct List biao;  //创建一个结构体变量
    if(initList(&biao)) {//判断初始化是否成功
        for (int i = 0; i< 30; ++i)
            insertList(&biao, i * 10, i + 1);  //先插入30个
        deleteList(&biao,3);
        printList(&biao);
        printf("%d\n",getList(&biao,3));
        printf("%d\n",findList(&biao,150));
        printf("%d\n",sizeList(&biao));
    } else {printf("Failed");
    }
}

运行后，成功得到结果：

相关问题

值得注意的是：

• 插入：因为要将后续所有元素都向后移动，所以平均时间复杂度为 O ( n ) O(n) O(n)
• 删除：同上，因为要将所有元素向前移动，所以平均时间复杂度为 O ( n ) O(n) O(n)
• 获取元素：因为可以利用数组特性直接通过下标访问到对应元素，所以时间复杂度为 O ( 1 ) O(1) O(1)

顺序表底层是基于数组实现的，那么它肯定是支持随机访问的，因为我们可以直接使用下标想访问哪一个就访问哪一个，它并不需要按照顺序来进行存取，链表才是。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前名称：（数据结构&C语言）对顺序表的认识-创新互联
网页地址：http://chengdu.cdxwcx.cn/article/djcceo.html