给公司做网站需要多少钱,seo怎么做,wordpress自动缩进,wordpress过滤机制文章目录 线性表线性表的顺序实现结点结构结点初始化增配空间Inc打印顺序表show_list线性表长度length尾部插入push_back头部插入push_front尾部删除pop_back头部删除pop_front按位置插入insert_pos按值查找find按位置删除delete_pos按值删除delete_val排序sort(冒泡#xff1… 文章目录 线性表线性表的顺序实现结点结构结点初始化增配空间Inc打印顺序表show_list线性表长度length尾部插入push_back头部插入push_front尾部删除pop_back头部删除pop_front按位置插入insert_pos按值查找find按位置删除delete_pos按值删除delete_val排序sort(冒泡升序)逆置resver清除表clear销毁表destroy合并表merge 线性表
在数据元素的非空有限集中1存在唯一的一个被称做“第一个”的数据元素2存在唯一的一个被称做“最后一个”的数据元素3除第一个之外集合中的每个数据元素均只有一个前驱4除最后一个之外集合中每个数据元素均只有一个后继
线性表的顺序实现
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
结点结构
#define SEQLIST_INIT_SIZE 8typedef struct SeqList {ElemType *base; // 线性表首地址int capacity; // 开辟的内存空间int size; // 有效存储
} SeqList;结点初始化
开辟出一段空间给定空间大小
void InitSeqList(SeqList *list) {list-base (ElemType *) malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);//开辟空间assert(list-base ! NULL);list-capacity SEQLIST_INIT_SIZE;list-size 0;
}①malloc动态内存分配函数用于申请一块连续的指定大小的内存块区域以ElementType *类型返回分配的内存区域地址格式指针名(指针类型*mallocsizeof指针类型*数据数量
②如果表达式的结果为“假”assert()会打印出断言失败的信息Assertion failed:...并调用abort()函数终止程序的执行Process finished with exit code 3如果表达式的结果为“真”assert()就什么也不做程序继续往后执行
增配空间Inc
1.重新开辟内存空间并判断是否增配空间成功失败则增配失败返回false
2.更新结点线性表首地址和开辟的内存空间
3.之后每次插入数据操作前添加判断条件分配给表内存是否足够。不够则进行增配空间增配空间失败时才是真正的内存不足
#define INC_SIZE 3bool Inc(SeqList *list) {//对已有的空间进行分配原来表开辟内存8进行重新分配即开辟83内存ElemType *newbase (ElemType *) realloc(list-base, sizeof(ElemType) * (list-capacity INC_SIZE));if (newbase NULL) {printf(增配空间失败内存不足\n);return false;}list-base newbase;list-capacity INC_SIZE;return true;
}①realloc函数指向在堆区重新开辟的内存块的起始地址:realloc(先前开辟的内存块的指针--也就是malloc之前申请的那块内存空间即需要调整大小的内存空间,新开辟的那块内存空间的字节数)返回值为调整之后的内存的起始地址
打印顺序表show_list
void show_list(SeqList *list) {for (int i 0; i list-size; i) {printf(%d, list-base[i]);}printf(\n);
}线性表长度length
int length(SeqList *list) {return list-size;
}尾部插入push_back
插入6 7 9后顺序表中数据顺序为6 7 9
1.判断有效存储是否小于开辟的内存空间即判断开辟的空间是否已满满了不能插入数据
2.通过下标赋值即插入数据
3.更新顺序表有效存储长度
void push_back(SeqList *list, ElemType x) {if (list-size list-capacity !Inc(list)) {printf(顺序表空间已满%d不能尾部插入数据\n, x);return;}list-base[list-size] x;list-size;
}头部插入push_front
插入6 9 1后顺序表中数据顺序为1 9 6
1.判断有效存储是否小于开辟的内存空间即判断开辟的空间是否已满满了不能插入数据
2.size-1即表中最后一个数据的下标从最后一个数据开始依次向后移动
3.赋值到下标为0的地址即插入数据
4.更新顺序表有效存储长度
void push_front(SeqList *list, ElemType x) {if (list-size list-capacity !Inc(list)) {printf(顺序表空间已满%d不能头部插入数据\n, x);return;}for (int i list-size; i 0; i--) {list-base[i] list-base[i - 1];}list-base[0] x;list-size;
}尾部删除pop_back
有顺序表1 6 9进行尾部删除后1 6
1.判断size是否为0即表是否为空空表不能删除数据
2.有效长度减1
void pop_back(SeqList *list) {if (list-size 0) {printf(顺序表空间已空不能尾部删除数据\n);return;}list-size--;
}头部删除pop_front
有顺序表5 6 0进行头部删除后6 0
1.判断size是否为0即表是否为空空表不能删除数据
2.从第二个数据开始依次往前移动
3.有效长度减1
void pop_front(SeqList *list) {if (list-size 0) {printf(顺序表空间已空不能头部删除数据\n);return;}for (int i 0; i list-size - 1; i) {list-base[i] list-base[i 1];}list-size--;
}按位置插入insert_pos
在顺序表5 3 0下标为2的位置插入数据7为5 3 7 0
1.判断pos是否正确并小于有效存储长度即判断插入位置是否合法位置非法不能插入数据
2.判断有效存储是否小于开辟的内存空间即判断开辟的空间是否已满满了不能插入数据
3.从最后一个数据开始依次向后移动直到要插入数据的位置移动结束
4.通过下标赋值即插入数据
5.更新顺序表有效存储长度
void insert_pos(SeqList *list, int pos, ElemType x) {if (pos 0 || pos list-size) {printf(插入数据的位置非法不能插入数据\n);}if (list-size list-capacity !Inc(list)) {printf(顺序表空间已满%d不能按位置插入数据\n, x);return;}for (int i list-size; i pos; i--) {list-base[i] list-base[i - 1];}list-base[pos] x;list-size;
}特殊情况当要插入数据的位置有效存储长度时即尾部插入时不影响效率[特别注意]
按值查找find
第一个符合条件的
1.从顺序表第一个数据开始向后遍历
2.每次遍历判断该数据是否是要查找的数据查找成功返回当前下标
3.遍历结束即没查到数据返回-1
int find(SeqList *list, ElemType key) {for (int i 0; i list-size; i) {if (list-base[i] key)return i;}return -1;
}按位置删除delete_pos
顺序表5 3 0删除位置为1的数据后5 0
1.判断pos是否正确并小于有效存储长度即判断删除位置是否合法位置非法不能删除数据
2.从要删除的位置开始依次将后一个数据前移
3.更新顺序表有效存储长度
void delete_pos(SeqList *list, int pos) {if (pos 0 || pos list-size)printf(删除数据的位置非法不能删除数据\n);for (int i pos; i list-size - 1; i) {list-base[i] list-base[i 1];}list-size--;
}按值删除delete_val
顺序表5 3 0删除值为0的数据后5 3
1.判断要删除的数据是否存在即按值查找存在得到查找到的数据下标不存在得到-1
2.判断返回值是否是-1是则数据不存在无法删除否则按位置删除
void delete_val(SeqList *list, ElemType key) {int pos find(list, key);if (pos -1) {printf(要删除的数据不存在\n);return;}delete_pos(list, pos);
}排序sort(冒泡升序)
顺序表5 3 0 1 9 4排序后0 1 3 4 5 9
1.两层遍历依次比较两个数据前面数据大于后面数据则交换
void sort(SeqList *list) {for (int i 0; i list-size; i) {for (int j 0; j list-size - i - 1; j) {if (list-base[j] list-base[j 1]) {ElemType tmp list-base[j];list-base[j] list-base[j 1];list-base[j 1] tmp;}}}
}逆置resver
顺序表5 3 0 1 9 4逆置后4 9 1 0 3 5
1.判断顺序表长度是否可进行逆置操作操作长度为1或0时不需要
2.设置两个整型指针low和high分别指向第一个数据和最后一个数据low指针后移high指针前移每次将两个指针指向的数据对换直到low指针大于或等于high指针为止
void resver(SeqList *list) {if (list-size 0 || list-size 1)return;int low 0;int high list-size - 1;ElemType tmp;while (low high) {tmp list-base[low];list-base[low] list-base[high];list-base[high] tmp;low;high--;}
}清除表clear
void clear(SeqList *list) {list-size 0;
}销毁表destroy
void destroy(SeqList *list) {free(list-base);list-base NULL;list-capacity 0;list-size 0;
}①free函数必须和malloc函数同时使用
②free只能释放由malloc动态分配在堆内存的内存直接在主函数定义结构体变量是分配在栈内存里的内存所以释放不了
合并表merge
表A1 2 5 6表B3 4 7 9合并后1 2 3 4 5 6 9
1.设置ia、ib、ic三个整型指针分别用来遍历表A、B、合并表开辟存放合并表的内存空间并判断是否开辟成功
2.同时遍历表A和表B依次判断指针指向的A、B表的数据大小将较小的数据放入合并表每存入一个数据合并表和被存入的数据所在表的整型指针都向后移一次直到A、B有一个表遍历完
3.如果其中一个表遍历结束另一个表还有遍历完的数据则直接将剩余数据依次存入合并表
4.更新合并表有效存储长度
void merge(SeqList *lt, SeqList *la, SeqList *lb) {lt-capacity la-size la-size;lt-base (ElemType *) malloc(sizeof(ElemType)*lt-capacity);assert(lt-base ! NULL);int ia 0;int ib 0;int ic 0;while(iala-size iblb-size){if(la-base[ia] lb-base[ib])lt-base[ic] la-base[ia];elselt-base[ic] lb-base[ib];}while(ia la-size){lt-base[ic] la-base[ia];}while(ib lb-size){lt-base[ic] lb-base[ib];}lt-size la-size lb-size;
}
