一、大O表示法
判断一个算法的效率
难点
二、线性表
1.定义
2.数学定义
线性表是具有相同类型的n（n>=0）个数据元素的有限序列（a0,a1,a2,...,an）,ai是表项，n是表长度
3.性质
4.线性表的基本操作
1.创建线性表
2.销毁线性表
3.清空线性表
4.将元素插入线性表
5.将元素从线性表中操作
6.将元素从线性表中删除
7.获取线性表中某个位置的元素
8.获取线性表的长度
4.存储方式
4.1 顺序存储
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素
动态数组案例
当插入一个新的元素时，空间不足？
1.申请一块更大的内存空间
2.将原空间的数据拷贝到新的空间
3.释放旧的空间
4.将元素放入新的空间
三、动态数组代码实现
0、定义动态数组的结构体
//定义动态数组的结构体 typedef struct DYNAMICARRY { int* pAddr;//存放数据的地址 int size;//当前有多少元素 int capacity;//容量，容器当前最大容纳元素 }Dynamic_Array;
1、动态数组的初始化
//动态数组的初始化 Dynamic_Array* Init_Array() { //申请内存 Dynamic_Array* myArray = (Dynamic_Array*)malloc(sizeof(Dynamic_Array)); //初始化 myArray->size = 0; myArray->capacity = 20; //动态分配内存 myArray->pAddr = (int*)malloc(sizeof(int) * myArray->capacity); return myArray; }
2、插入新数据
//插入 value 插入的值 void PushBack_Array(Dynamic_Array* arr, int value) { //判断数组长度是否为0 if (arr == NULL) { return; } //判断空间是否足够 capacity记录当前数组空间长度 size==capacity数组已满 if (arr->size == arr->capacity) { //第一步 申请一块更大的内存空间 默认新空间是旧空间的两倍 int* newSpace = (int*)malloc(sizeof(int) * arr->capacity * 2); //第二步 拷贝数据到新的空间 newSpace新空间 arr->pAddr旧空间 memcpy(newSpace, arr->pAddr, arr->capacity * sizeof(int)); //第三步 释放旧的内存 free(arr->pAddr); //经过上述步骤 释放完毕 //更新容量 旧空间到新空间 arr->capacity = arr->capacity * 2; arr->pAddr = newSpace; } //插入元素 size记录当前数组中具体的元素个数 arr->pAddr[arr->size] = value; arr->size++; }
3、根据元素位置删除
//根据位置删除 void RemoveByPos_Array(Dynamic_Array* arr, int pos) { if (arr == NULL) { printf("数组为空\n"); return; } //判断位置是否有效 if (pos < 0||pos>=arr->size) { printf("数组位置无效\n"); return; } else { //删除元素 pos是被删除位置 从被删除位置向后遍历 将元素往后更新 for (int i = pos; i < arr->size-1; i++) { arr->pAddr[i] = arr->pAddr[i + 1]; } //当前数组存储元素数减一 arr->size--; } }
4、根据元素值删除第一次该值出现的位置
//根据值删除value第一次出现的位置 void RemoveByValue_Array(Dynamic_Array* arr, int value) { //判空操作 if (arr == NULL) { return; } //找到值的位置 找到value值在数组arr中第一次出现的位置 int pos = -1; for (int i = 0; i < arr->size; i++) { if (arr->pAddr[i] == value) { pos = i; break; } } // 根据value值出现的位置删除位置删除 RemoveByPos_Array(arr, pos); }
5、查找
//查找 int Find_Array(Dynamic_Array* arr, int value) { //对数组进行判空 if (arr == NULL) { return -1; } //查找 //找到值的位置 int pos = -1; for (int i = 0; i < arr->size; i++) { if (arr->pAddr[i] == value) { pos = i; break; } } for (int i = 0; i < arr->size; i++) { if (arr->pAddr[i] == value) { pos = i; break; } } return pos; }
6、打印
//打印 void Print_Array(Dynamic_Array* arr) { if (arr == NULL) { return; } for (int i = 0; i < arr->size; i++) { printf("%d ", arr->pAddr[i]); } printf("\n"); }
7、释放动态数组的内存
//释放动态数组的内存 void FreeSpace_Array(Dynamic_Array* arr) { if (arr == NULL) { return; } if (arr->pAddr != NULL) { free(arr->pAddr); } free(arr); }
8、清空数组
//清空数组 void Clear_Array(Dynamic_Array* arr) { if (arr == NULL) { return; } //pAddr指向的空间直接为0 arr->size = 0; }
9、获得动态数组的容量capacity
//获得动态数组容量 int Capacity_Array(Dynamic_Array* arr) { if (arr == NULL) { return -1; } return arr->capacity; }
10、获得动态数组当前元素个数
//获得动态数组当前元素个数 int Size_Array(Dynamic_Array* arr) { if (arr == NULL) { return -1; } return arr->size; }
11、根据位置，获得数组中某个位置的元素
//根据位置 获得某个位置的元素 int At_Array(Dynamic_Array* arr, int pos) { return arr->pAddr[pos]; }
四、函数测试
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdlib.h> #include <time.h> #include <string.h> #include <stdio.h> #include <limits.h> #include <ctype.h> #include <math.h> #include "动态数组.h"//方法定义在源文件动态数组.c中 //11.12 动态数组 //动态增长内存，将存放的数据放在堆上 //动态数组 申请内存 拷贝数据 释放内存 插入多一个元素 //容量capacity 表示我的这块内存空间一共可以存放多少元素 //size概念 记录当前数组中具体的元素个数 void test01() { //初始化一个动态数组 Dynamic_Array* myArray = Init_Array(); //打印数组容量 printf("数组容量:%d\n", Capacity_Array(myArray)); printf("数组大小:%d\n", Size_Array(myArray)); //插入元素 for (int i = 0; i < 30; i++) { PushBack_Array(myArray , i); } printf("数组容量:%d\n", Capacity_Array(myArray)); printf("数组大小:%d\n", Size_Array(myArray)); //打印 Print_Array(myArray); //根据位置删除value第一次出现的位置 RemoveByPos_Array(myArray, 0); Print_Array(myArray); //根据值删除元素 RemoveByValue_Array(myArray, 28); Print_Array(myArray); //打印 //查找第五个位置的元素 int pos=Find_Array(myArray,5); printf("5查找到:pos:%d %d\n", pos, At_Array(myArray, pos)); //销毁 FreeSpace_Array(myArray); } int main() { test01(); system("pause"); return 0; }
测试结果
