小公司网站维护,简易做网站,网站技术有哪些,怎么用自己主机做网站_基本概念#xff1a;
1、引入
程序数据结构算法
数据#xff1a;
数值数据#xff1a;能够直接参加运算的数据#xff08;数值#xff0c;字符#xff09;
非数值数据#xff1a;不能够直接参加运算的数据#xff08;字符串、图片等#xff09;
数据即是信息的载…基本概念
1、引入
程序数据结构算法
数据
数值数据能够直接参加运算的数据数值字符
非数值数据不能够直接参加运算的数据字符串、图片等
数据即是信息的载体能够被输入到计算机中存储识别和处理的符号总称
数据元素
数据的一个基本单位又叫做记录
数据类型
数据元素决定了数据的存储范围以及计算方法例如short x则这个x的取值范围【-3276832767】限定计算{ - * / %}
数据结构:
数据结构就是去探讨数据元素与数据元素之间的相互关系的学科
2、基本概念
逻辑结构数据元素之间的抽象关系相邻/隶属
存储结构在计算机中的具体实现方法
数据运算对数据进行的操作例如:增删改查
3、逻辑结构
集合gather数据元素在同一范围内部无其他关系
表list一对一例如线性表队列栈
树tree一对多
图graph多对多
4、存储结构
存储结构又叫做物理结构存放到地址上的关系
顺序存储sequence在存储器上按照顺序存放
链式存储link利用元素存储地址的指针来描述元素之间的关系
索引存储index在存储数据时额外提供一张索引表
散列存储hash先提供一个散列函数利用散列函数去计算存储位置
数据的逻辑结构与存储结构关系密切
算法的设计取决于决定的逻辑结构
算法的实现依赖与采用的存储结构
5、算法
算法是一个有穷规则语句、命令的有序集合它确定了解决某一个问题的一个运算序列。对于问题的初始输入通过算法的有限步的运行产生一个或多个输出。
算法的特性
1有穷性——算法执行的步骤是有限的
2确定性——每一个计算步骤是唯一的
3可行性——每个计算步骤能在有效的时间内完成
4输入——算法可以有零个或者多个外部输入
5输出——算法有一个或多个输出
算法的优劣
1消耗的时间的多少
2消耗的存储空间的多少
3容易理解容易实现调试和维护是否容易
6、时间复杂度T(n)
通过问题的规模算法所消耗的时间的多少
#include stdio.h
int main(int argc, char *argv[])
{for(int i0;in-1;i) //n-1{for(int j0;jn-1-i;j) //(n-1)/2{}}return 0;
}频度语句执行的次数
每一条语句的频度之和就是这个算法的时间复杂度
上述代码的时间复杂度为(n-1)*(n-1)/2 n²/2 - n 1/2 当n趋于无穷大时和n²为同阶无穷大
冒泡排序的时间复杂度o(n²)
7、空间复杂度D(n)
通过问题规模的扩大所需要的额外空间的量 8、线性表
线性表的特征
1对于非空表而言a0表头没有前驱
2an-1表尾没有后继
3对于其它的每一个元素ai有且仅有一个直接前驱和直接后继
9、数据结构创建表时之所以常在堆区开空间主要基于以下几点原因
1. 灵活性和动态性 动态内存分配堆区允许程序员在运行时动态地分配和释放内存这意味着可以根据实际需要调整数据结构的大小而无需在编译时就确定其大小。这对于链表、动态数组等需要频繁调整大小的数据结构尤为重要。 避免栈溢出栈区通常用于存储局部变量和函数调用信息其空间有限。如果数据结构过大或复杂可能会导致栈溢出。而在堆区分配内存可以避免这一问题因为堆区的空间相对较大且由程序员控制释放。
2. 内存管理灵活性 手动管理内存在堆区分配的内存需要程序员手动释放使用如free等函数这提供了更大的内存管理灵活性。程序员可以根据需要决定何时释放内存从而优化内存使用。 生命周期控制堆区分配的内存的生命周期由程序员控制这意味着可以在数据结构不再需要时立即释放内存减少内存泄漏的风险。
3. 链表等特殊数据结构的需要 链表节点链表节点通常需要在堆区分配内存因为链表节点的数量和位置在运行时是动态变化的。每个节点都包含数据域和指针域指向下一个节点的指针这些节点在内存中的位置不连续因此适合在堆区分配。 内存碎片化链表等数据结构能够很好地适应内存碎片化的情况因为它们在堆区分配内存时不需要连续的内存块。
4. 性能优化 局部性原理虽然堆区分配的内存可能不如栈区分配的内存那样具有局部性即内存访问的集中性但对于某些数据结构如哈希表、红黑树等其内存访问模式可能更适合在堆区分配内存。 减少栈空间占用将大型数据结构放在堆区可以减少栈空间的占用从而降低栈溢出的风险并提高程序的稳定性。 顺序表
顺序存储的线性表
顺序存储结构的特点
1逻辑上相邻的元素aiai1其存储位置也是相邻的
2对数据元素ai的存取为随机存取或按地址存取
3存储密度高存储密度数据结构中元素所占存储空间/整个数据结构所占空间
顺序存储结构的不足
1对表的插入和删除等运算的时间复杂度较差
2要求系统提供一片较大的连续存储空间
3插入、删除等运算耗时且存在元素在存储器中成片移动的现象
#ifndef _SEQLIST_H
#define _SEQLIST_H#include stdio.h
#include stdlib.htypedef int Type; //声明顺序表的数据类型
#define LEN 10 //顺序表的大小
#define OUT(A) {printf(%d ,A);} //宏函数最好加;和{}typedef struct{Type data[LEN]; //表的存储空间int count; //记录表的已存元素量
}list; //线性表结构体//创建
list *create_list(); //结构体指针
//判满满为0不满为1,错误为-1
int full_list(list *l);
//判空空为0非空为1错误为-1
int null_list(list *l);void whether_full(int a);//初始化
void init_list(list *l);
//求长度
int length_list(list *l);
//首插入
void head_insert_list(list *l,Type data);
//插入尾插
void insert_list(list *l,Type data);
//查找 按值找把找到值的下标返回
int search_list(list *l,Type data);
//更新 按值更新把原值改为新值
void update_list(list *l,Type oldData,Type newData);
//删除
void delete_list(list *l,Type data);
//遍历
void traverse_list(list *l);
//回收
void free_list(list **l);#endif顺序表的代码较多所以使用多文件封装来写比较清晰顺序表的存储既然是要连续的空间地址那么我们就使用数组来存储因为数组中的元素就是连续存储的一个顺序表中除了数组来存储元素外还需要一个变量来存储数组的长度因此我定义了一个结构体来存放这两个成员将结构体重命名为list方便后续使用。
#include seqlist.h
//创建
list *create_list()
{list *p (list *)malloc(sizeof(list));if(NULL p){perror(create malloc);return NULL;}return p;
}
//判满满为0不满为1,错误为-1
int full_list(list *l)
{if(NULL l){puts(list is NULL);return -1;}else if(LEN l-count){puts(表已放满);return 0;}else{//puts(表未满);return 1;}
}
//判空空为0非空为1错误为-1
int null_list(list *l)
{if(NULL l){puts(list is NULL);return -1;}return l-count0?0:1;
}void whether_full(int a)
{if(0 a)puts(表已满);else if(1 a)puts(表未满);
}
//初始化
void init_list(list *l)
{if(NULL l){puts(list is NULL);return;}l-count0;
}
//求长度
int length_list(list *l)
{if(NULL l){puts(list is NULL);return -1;}return l-count;// printf(index:%d\n,l-count);
}
//首插入
void head_insert_list(list *l,Type data)
{if(0 full_list(l))return;int n l-count;while(n){l-data[n] l-data[n-1];n--;}l-data[0] data;l-count;
}
//插入尾插
void insert_list(list *l,Type data)
{if(0 full_list(l))return;//if(full_list(l))//{//l-data[l-count] data;//l-count;//}l-data[l-count] data;l-count;
}
//查找 按值找把找到值的下标返回
int search_list(list *l,Type data)
{if(NULL l){puts(list is NULL);return -1;}for(int i0;il-count;i){//memcmp(data,l-data[i],sizeof(Type))0;if(data l-data[i])return i;}return -1;
}
//更新 按值更新把原值改为新值
void update_list(list *l,Type oldData,Type newData)
{
#if 1if(NULL l){puts(list is NULL);return;}for(int i0;il-count;i){if(oldDatal-data[i])l-data[i]newData;//break;}
#elseint t;while((tsearch_list(l,oldData))!-1)l-data[t]newData;
#endif
}
//删除
void delete_list(list *l,Type data)
{if(NULL l){puts(list is NULL);return;}
#if 0for(int i0;il-count;i){if(data l-data[i])for(int ji;jl-count-1;j){l-data[j] l-data[j1]}l-count--;i--;}
#elif 1int index 0;for(int i0;il-count;i){if(data ! l-data[i]) //不是要删的值就赋值是要删的就不赋直到是不删的数再把它放到之前要删那个数的位置相当于是以覆盖的形式删除{l-data[index]l-data[i];}}l-count index;
#endif
}
//遍历
void traverse_list(list *l)
{if(NULL l){puts(list is NULL);return;}for(int i0;il-count;i){OUT(l-data[i]);}puts();
}
//回收
void free_list(list **l) //传二级指针是为了让开辟空间所用的指针指向空 传参传指针的地址
{if(NULL l){puts(list is NULL);return;}free(*l);*lNULL;
}创建list *create_list() 创建一个顺序表在堆区开空间并且创建完之后我们需要拿到表的首地址因此函数的类型为list *型创建空间的大小就是结构体的大小结构体有多大就开多大的空间开完空间之后我们需要做一个简单的判断让我们知道开辟空间是否开辟成功不成功返回NULL成功返回首地址。
判断表是否放满int full_list(list *l) 对于顺序表来说因为在结构体里面我们有一个专门用来记录表中元素个数的变量因此判断表是否放满直接判断这个变量的值是否等于表的长度LEN即可满返回一个0不满返回一个1。
判断表是否为空int null_list(list *l) 判空跟判满其实差不多也是判断记录个数的变量的值是否为0为0就是空不为0就是非空。
顺序表的初始化和求长度也是跟判空一样的操作都是操作变量count初始化就直接把count置零就可以因为在后续插入内容的时候会将以前的内容覆盖求长度其实就是直接将count的值当做函数返回值反出去即可。
头部插入void head_insert_list(list *l,Type data) 对于插入函数来说我们需要操作表因此需要传参传入表的地址还有我们需要插入的元素首先需要判断这个表是否放满如果放满那就不可以继续再插入此时直接return即可为放满那就可以插入因为是头部插入因此在插入之前我们需要给要插入的元素把第一个位置空出来所以我们需要把表中已有的元素全部往后移动一位通过一个循环从最后一个元素开始移动有几个元素就移动几次移动完之后就可以把要放入的元素放入第一个位置之后一定不要忘记count要自增1。
尾部插入void insert_list(list *l,Type data) 尾部插入相对于头部插入就简单得多首先也是需要判断表满没满没满之后直接再最后一个元素后面放入要插入的元素即可l-data[l-count] data;之后count自增1。
查找int search_list(list *l,Type data) 查找传入的也是两个参数表和要查找的值返回值为该值的下标通过一个循环遍历的方式来查找我们所需要的元素的下标找到这个元素循环就结束如果循环结束都没有找到这个数那就返回一个-1代表表中没有这个数。
更新void update_list(list *l,Type oldData,Type newData) 更新函数不需要返回值传参的话就是表原值以及需要修改的值还是跟查找一样的使用循环的方法找到需要修改的值就直接将这个值修改为更新后的值即可在这里如果只想要更新查找到的第一个值的话就在循环里面加一个break即可这样查找到第一个之后就会结束循环。
删除void delete_list(list *l,Type data) 对于顺序表的删除我们有两个办法但是都需要使用到循环第一种方法是找到要删除的值之后就将它后面的每一个元素都往前移动一位将这个删除的值直接覆盖掉第二种方法也是覆盖首先定义一个变量作为赋值下标然后判断的条件是当元素不是我要删除的那个数时就给数组中的数赋值l-data[index]l-data[i];这里的index和i都是从0开始对于相同的值再赋值一遍也不会产生影响但是要是这个数是我们要删除的数那就不进行这一个赋值操作这时index的值就不会增加会停留在要删除的值的前一个但是i每次都会自增当下一次循环时i所对应的元素就是要删除的元素的后一个元素这时再将这个元素赋值给index下标对应的位置就可以将要删除的元素覆盖掉切记一定要在删除的同时count的值也要发生改变。 遍历void traverse_list(list *l) 顺序表的遍历其实也就是数组的遍历通过循环遍历数组再输出即可。
回收void free_list(list **l) 在回收的传参这里我们只传这个表是不行的我们需要释放这片空间地址并且还需要将指向这片空间的指针指向空因此必须传参传入指针的地址也就是传一个二级指针将这个空间free之后还需要将指针指向NULL这样回收才算结束。
#include seqlist.h
int main(int argc, char *argv[])
{list *p create_list();insert_list(p,1);insert_list(p,2);insert_list(p,3);puts(尾插入后);traverse_list(p);head_insert_list(p,4);head_insert_list(p,5);head_insert_list(p,6);puts(首插入后);traverse_list(p);printf(length%d\n,length_list(p));whether_full(full_list(p));printf(3的下标为%d\n,search_list(p,3));update_list(p,4,8);puts(将4更改为8后);traverse_list(p);delete_list(p,5);puts(删除5之后);traverse_list(p);puts(回收);free_list(p);printf(p%p\n,p);return 0;
}
