六、连续存储数组

---

 

---

1.什么是线性结构？

把所有的结点用一根直线穿起来

 

2.线性结构分为几种？

连续存储【数组】

（1）什么叫数组

元素类型相同，大小相等

（2）数组的优缺点：

离散存储【链表】

arraylist是连续存储数组

linkedlist是离散存储链表

arraylist的方法

3.Arraylist的示例

头文件

1. #include <stdio.h>

2. #include <malloc.h>

3. #include <stdlib.h>

定义结构体

1. struct Arr

2. {

3. int * pBase;//存储的是数组第一个元素的地址

4. int len;//数组所能容纳的最大元素个数

5. int cnt;//当前数组有效元素的个数

6. };

定义抽象方法

1. void init_arr(struct Arr * pArr, int length);

2. bool append_arr(struct Arr * pArr, int val);

3. bool insert_arr(struct Arr * pArr, int pos, int val);

4. bool delete_arr(struct Arr * pArr, int pos, int * pVal);

5. int get(struct Arr * pArr, int pos);

6. bool is_empty(struct Arr * pArr);

7. bool is_full(struct Arr * pArr);

8. void sort_arr(struct Arr * pArr);

9. void show_arr(struct Arr * pArr);

10. void inversion_arr(struct Arr * pArr);

tips:

这样写无法改变arr中成员的值

所以应该使用指针来传参

如果内存满了，那么是无给配pBase分配动态内存

这时pBase为NULL

完成初始化，return可以终止程序

init_arr方法最终形式

1. void init_arr(struct Arr * pArr, int length)

2. {

3. pArr->pBase = (int )malloc(sizeof(int) length);

4. if (NULL == pArr->pBase)

5. {

6. printf(“动态内存分配失败！n”);

7. exit(-1); //终止整个程序

8. }

9. else

10. {

11. pArr->len = length;

12. pArr->cnt = 0;

13. }

14. return; //完成要return让人知道程序终止了

15. }

这里最好写地址，形参为指针类型只占4个字节

show_arr的思路

编写is_empty方法，如果有效个数cnt为0则为空

1. bool is_empty(struct Arr * pArr)

2. {

3. if (0 == pArr->cnt)

4. return true;

5. else

6. return false;

7. }

show_arr方法

1. void show_arr(struct Arr * pArr)

2. {

3. if (is_empty(pArr))

4. {

5. printf(“数组为空！n”);

6. }

7. else

8. {

9. for (int i = 0; i < pArr->cnt; ++i)

10. printf(“%d “,

    pArr->pBase[i]);//pBase是第一个元素的地址，所以pBase[i]得到的是第i个元素的值

11. printf(“n”);

12. }

13. }

full方法

1. bool is_full(struct Arr * pArr)

2. {

3. if (pArr->cnt == pArr->len)

4. return true;

5. else

6. return false;

7. }

append_arr方法

1. bool append_arr(struct Arr * pArr, int val)

2. {

3. //满时返回false

4. if (is_full(pArr))

5. return false;

6. //不满时追加

7. pArr->pBase[pArr->cnt] = val;

8. pArr->cnt++;

9. return true;

10. }

insert_arr方法

现将其他数往后移动，再插入数据

1. bool insert_arr(struct Arr * pArr, int pos, int val)

2. {

3. if (is_full(pArr))

4. return false;

5. if (pos < 1 || pos > pArr->cnt)

6. return false;

7. for (int i = pArr->cnt - 1; i >= pos - 1; i–)

8. {

9. pArr->pBase[i + 1] = pArr->pBase[i];

10. }

11. pArr->pBase[pos - 1] = val;

12. pArr->cnt++;

13. return true;

14. }

delete方法

1. bool delete_arr(struct Arr * pArr, int pos, int * pVal)

2. {

3. //如果数组为空则返回

4. if (is_empty(pArr))

5. return false;

6. //如果pos不在有效范围内返回

7. if (pos < 1 || pos > pArr->cnt)

8. return false;

9. *pVal = pArr->pBase[pos - 1];

10. for (int i = pos; i < pArr->cnt; i++)

11. {

12. pArr->pBase[i - 1] = pArr->pBase[i];

13. }

14. pArr->cnt–;

15. return true;

16. }

get方法

1. int get(struct Arr * pArr, int pos)

2. {

3. return pArr->pBase[pos - 1];

4. }

inversion_arr方法

1. void inversion_arr(struct Arr * pArr)

2. {

3. if (is_empty(pArr))

4. {

5. return;

6. }

7. int i = 0;

8. int j = pArr->cnt - 1;

9. //利用t来给它们互换

10. int t = 0;

11. //互换的之后两边依次接近中间的数，最后中间那个数是不用转换的！

12. while (i < j)

13. {

14. t = pArr->pBase[i];

15. pArr->pBase[i] = pArr->pBase[j];

16. pArr->pBase[j] = t;

17. i++;

18. j–;

19. }

20. return;

21. }

sort_arr方法

使用了冒泡pa

1. void sort_arr(struct Arr * pArr)

2. {

3. int i, j, t;

4. for (i = 0; i < pArr->cnt; i++)

5. {

6. for (j = i + 1; j < pArr->cnt; j++)

7. {

8. if (pArr->pBase[i] > pArr->pBase[j])

9. {

10. t = pArr->pBase[j];

11. pArr->pBase[j] = pArr->pBase[i];

12. pArr->pBase[i] = t;

13. }

14. }

15. }

16. return;

17. }