作者:
2016 年 10 月 27 日 20:13:13
数组是最常用的数据结构,在内存中连续存储,可以静态初始化(int a[2]={1,2}),可以动态初始化 malloc()。难点就是数组在删除或者插入元素的时候,要移动元素的坐标不好确定。规律:
1. 如果要在数组中第 pos 个位置插入一个元素(应该从后面开始移动)
- for (i = cnu; i >= pos; i--) pBase[i] = pBase[i - 1];
2. 删除数组第 pos 位置的元素
- for (i = pos + 1; i <= cnu; i--) pBase[i - 2] = pBase[i - 1];
使用 malloc 动态分配内存并将返回值赋给整形指针
int pBase=(int *)malloc(sizeof(int)len);// 分配 4*len 字节长度的内存
这是 pBase 可以指向数组中的第一个元素,可以作为数组变量名称使用。
优点:
存取速度快 o(1) 可以直接根据下标找到内存位置
缺点:
- #include < stdio.h > #include < malloc.h > #include < stdbool.h >
- /* 定义结构体 */
- struct Arr {
- int len; //数组能存取的最大元素个数
- int cnu; //数组中当前元素个数
- int * pBase; //存储指向数组的指针
- };
- /*初始化数组*/
- void init_Arr(struct Arr * pArray, int len) {
- pArray - >pBase = (int * ) malloc(sizeof(int) * len); //分配4*len字节长度的内存
- if (NULL == pArray - >pBase) {
- printf("动态分配内存失败\n");
- } else {
- pArray - >len = len;
- pArray - >cnu = 0;
- printf("动态分配内存成功 %d \n", pArray - >len);
- }
- }
- /*判断数组是否为空,传地址省内存4字节,传结构体变量需要进行拷贝,12字节*/
- bool isempty(struct Arr * pArray) {
- if (0 == pArray - >cnu) return true;
- else return false;
- }
- /*判断数组是否满了*/
- bool isfull(struct Arr * pArray) {
- if (pArray - >len == pArray - >cnu) return true;
- else return false;
- }
- /*显示数组内容*/
- void show_Arr(struct Arr * pArray) {
- if (isempty(pArray)) printf("数组为空!\n");
- else {
- for (int i = 0; i < pArray - >cnu; i++) {
- printf("%d \t\t %d \t\t %d \n", pArray - >pBase[i], pArray - >cnu, pArray - >len);
- }
- printf("------------------------------------\n");
- }
- }
- /*向数组追加元素*/
- bool append(struct Arr * pArray, int val) {
- if (isfull(pArray)) {
- printf("数组已经满了!\n");
- return false;
- } else {
- pArray - >pBase[pArray - >cnu] = val;
- pArray - >cnu++;
- }
- }
- /*向数组中插入元素,pos为数组中第几个位置,pos=3就是向a[2]插入元素*/
- bool insert(struct Arr * pArray, int pos, int val) {
- if (pos < 1 || pos > pArray - >len + 1) {
- printf("插入的位置输入的不合法\n");
- return false;
- }
- if (isfull(pArray)) {
- printf("数组已经满了,插入失败!\n");
- return false;
- } else {
- //printf("数组 %d \n",pArray->cnu);
- for (int i = pArray - >cnu; i >= pos; i--) { //循环将pos位置开始的数组后移
- pArray - >pBase[i] = pArray - >pBase[i - 1];
- }
- pArray - >pBase[pos - 1] = val;
- pArray - >cnu++;
- pArray - >len++;
- return true;
- }
- }
- /*删除数组中的第pos个元素,同时返回删除的元素的值*/
- bool delete(struct Arr * pArray, int pos, int * val) {
- if (pos < 1 || pos > pArray - >cnu) {
- printf("删除失败,位置不合法\n");
- return false;
- }
- if (isempty(pArray)) {
- printf("数组已经空,删除失败!\n");
- return false;
- } else { * val = pArray - >pBase[pos - 1];
- for (int i = pos + 1; i <= pArray - >cnu; i++) {
- pArray - >pBase[i - 2] = pArray - >pBase[i - 1];
- }
- pArray - >cnu--;
- return true;
- }
- }
- /*数组倒置*/
- bool inverse(struct Arr * pArray) {
- if (isempty(pArray)) {
- printf("倒置失败,因数组为空");
- return false;
- } else {
- int i = 0,
- j = pArray - >cnu - 1,
- temp;
- while (i < j) {
- temp = pArray - >pBase[i];
- pArray - >pBase[i] = pArray - >pBase[j];
- pArray - >pBase[j] = temp;
- i++;
- j--;
- }
- }
- return true;
- }
- int main() {
- struct Arr arr;
- init_Arr( & arr, 20);
- append( & arr, 1);
- append( & arr, 2);
- append( & arr, 3);
- append( & arr, 4);
- append( & arr, 5);
- show_Arr( & arr);
- insert( & arr, 2, 88);
- show_Arr( & arr);
- int val;
- delete( & arr, 1, &val);
- show_Arr( & arr);
- printf("删除了 %d\n", val);
- inverse( & arr);
- show_Arr( & arr);
- return 0;
- }
Success time: 0 memory: 2300 signal:0
- 动态分配内存成功20 1 5 20 2 5 20 3 5 20 4 5 20 5 5 20------------------------------------1 6 21 88 6 21 2 6 21 3 6 21 4 6 21 5 6 21------------------------------------88 5 21 2 5 21 3 5 21 4 5 21 5 5 21------------------------------------删除了1 5 5 21 4 5 21 3 5 21 2 5 21 88 5 21------------------------------------
结构体:结构体 (struct) 指的是一种数据结构,是 C 语言中聚合数据类型的一类。 结构体可以被声明为变量、指针或数组等,用以实现较复杂的数据结构。结构体的定义如下所示,
struct tag {member-list} variable-list ;
struct 为结构体关键字,tag 为结构体的标志,member-list 为结构体成员列表,其必须列出其所有成员;variable-list 为此结构体声明的变量。
思路:
例如:
- /* 定义结构体 */
- struct Arr {
- int len; //数组能存取的最大元素个数
- int cnu; //数组中当前元素个数
- int * pBase; //存储指向数组的指针
- };
初始化数组:
思路:
例如:
- /*初始化数组*/
- void init_Arr(struct Arr * pArray, int len) {
- pArray - >pBase = (int * ) malloc(sizeof(int) * len); //分配4*len字节长度的内存
- if (NULL == pArray - >pBase) {
- printf("动态分配内存失败\n");
- } else {
- pArray - >len = len;
- pArray - >cnu = 0;
- printf("动态分配内存成功 %d \n", pArray - >len);
- }
- }
判断数组是否为空:
- /*判断数组是否为空,传地址省内存4字节,传结构体变量需要进行拷贝,12字节*/
- bool isempty(struct Arr * pArray) {
- if (0 == pArray - >cnu) return true;
- else return false;
- }
判断数组是否为满:
例如:
- /*判断数组是否满了*/
- bool isfull(struct Arr * pArray) {
- if (pArray - >len == pArray - >cnu) return true;
- else return false;
- }
向数组追加元素:
例如:
- /*向数组追加元素*/
- bool append(struct Arr * pArray, int val) {
- if (isfull(pArray)) {
- printf("数组已经满了!\n");
- return false;
- } else {
- pArray - >pBase[pArray - >cnu] = val;
- pArray - >cnu++;
- }
- }
显示数组内容
例如:
- /*显示数组内容*/
- void show_Arr(struct Arr * pArray) {
- if (isempty(pArray)) printf("数组为空!\n");
- else {
- for (int i = 0; i < pArray - >cnu; i++) {
- printf("%d \t\t %d \t\t %d \n", pArray - >pBase[i], pArray - >cnu, pArray - >len);
- }
- printf("------------------------------------\n");
- }
- }
向数组中插入元素:pos 为数组中第几个位置,pos=3 就是向 a[2] 插入元素
例如:
- /*向数组中插入元素,pos为数组中第几个位置,pos=3就是向a[2]插入元素*/
- bool insert(struct Arr * pArray, int pos, int val) {
- if (pos < 1 || pos > pArray - >len + 1) {
- printf("插入的位置输入的不合法\n");
- return false;
- }
- if (isfull(pArray)) {
- printf("数组已经满了,插入失败!\n");
- return false;
- } else {
- //printf("数组 %d \n",pArray->cnu);
- for (int i = pArray - >cnu; i >= pos; i--) { //循环将pos位置开始的数组后移
- pArray - >pBase[i] = pArray - >pBase[i - 1];
- }
- pArray - >pBase[pos - 1] = val;
- pArray - >cnu++;
- pArray - >len++;
- return true;
- }
- }
删除数组中的第 pos 个元素:同时返回删除的元素的值
例如:
- /*删除数组中的第pos个元素,同时返回删除的元素的值*/
- bool delete(struct Arr * pArray, int pos, int * val) {
- if (pos < 1 || pos > pArray - >cnu) {
- printf("删除失败,位置不合法\n");
- return false;
- }
- if (isempty(pArray)) {
- printf("数组已经空,删除失败!\n");
- return false;
- } else { * val = pArray - >pBase[pos - 1];
- for (int i = pos + 1; i <= pArray - >cnu; i++) {
- pArray - >pBase[i - 2] = pArray - >pBase[i - 1];
- }
- pArray - >cnu--;
- return true;
- }
- }
数组倒置
例如:
- /*数组倒置*/
- bool inverse(struct Arr * pArray) {
- if (isempty(pArray)) {
- printf("倒置失败,因数组为空");
- return false;
- } else {
- int i = 0,
- j = pArray - >cnu - 1,
- temp;
- while (i < j) {
- temp = pArray - >pBase[i];
- pArray - >pBase[i] = pArray - >pBase[j];
- pArray - >pBase[j] = temp;
- i++;
- j--;
- }
- }
- return true;
- }
来源: http://www.cnblogs.com/baiboy/p/al1.html