重庆分公司,新征程启航

为企业提供网站建设、域名注册、服务器等服务

(数据结构&C语言)对顺序表的认识-创新互联

(数据结构&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://cqcxhl.cn/article/djcceo.html

其他资讯

在线咨询
服务热线
服务热线:028-86922220
TOP