算法的概念和性质略过
算法的复杂度
| 例子 | 时间复杂度 | 术语 |
|---|---|---|
| 5201314 | O(1) | 常数阶 |
| 3n+4 | O(n) | 线性阶 |
| 3n2+4n+5 | O(n2) | 平方阶 |
| 3log2n+4 | O(logn) | 对数阶 |
| 2n+3nlog2n+14 | O(nlogn) | nlogn阶 |
| n3+2n2+4n+6 | O(n3) | 立方阶 |
| 2n | O(2n) | 指数阶 |
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < (nn)
复杂度分析法则
1）单段代码看高频：比如循环。
2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
3）嵌套代码求乘积：比如递归、多重循环等
4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。
时间复杂度分析
只关注循环执行次数最多的一段代码
加法法则：总复杂度等于量级最大的那段代码的复杂度
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
几个常见例子
线性阶
int i, n = 100, sum = 0;
for(i = 0; i<n; i++) {
sum = sum + i;
}
上面这段代码的循环复杂度为O(n)，因为循环体中的代码需要执行n次
平方阶
int i,j,n = 100;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
printf("aaaaaaaaaaaa\n");
}
}
上面这段代码的时间复杂度为O(n2)
int i,j,n = 100;
for(i = 0; i < n; i++) {
for(j = i; j < n; j++) {
pringtf("aaaaaaaaaaaaaa\n");
}
}
分析，由于当i=0时，内循环执行了n次，当i=1时，内循环则执行n-1次。。。。。。当i=n-1时，内循环执行1次，所以总的执行次数应该是n+(n-1)+(n-2)+...+1=n(n+1)/2用上面的简化方法来简化?n2+?n，这个式子中没有常数项不用考虑第一条，根据第二条只保留最高项，去掉?n这一项，根据第三条去掉与最高项相乘的常数?，最终得到O(n2)
对数阶
int i = 1, n = 100;
while(i < n) {
i = i*2;
}
由于每次i2之后就距离n更近一步，假设有x个2相乘后大于或等于n，则会退出循环。于是由2^x=n
得到x=log2n，所以这个循环的时间复杂度为O(logn)。
抽象数据类型的定义格式如下：
ADT抽象数据类型名{
数据对象：（数据对象的定义〉
数据关系：（数据关系的定义〉
基本操作：（基本操作的定义〉
}ADT抽象数据类型名
基本操作的定义格式为：
? 基本操作名（参数表）
? 初始条件：（初始条件描述〉
? 操作结果：（操作结果描述〉
基本操作有两种参数： 赋值参数只为操作提供输入值；引用参数以"&"打头，除可提供输
入值外，还将返回操作结果。
对非空的线性表或线性结构， 其特点是：
ADT List{
数据对象： D={ai|ai E ElemSet, i=l, 2, …n， n>=0}
数据关系： R=(<ai-1,ai> ai-1,aiE D, i=2, …, n}
基本操作：
InitList (&L)
操作结果：构造一个空的线性表L。
DestroyList(&L)
初始条件：线性表L已存在。
操作结果：销毁线性表L。
ClearList (&L)
初始条件：线性表L已存在。
操作结果：将L重置为空表。
ListEmpty(L)
初始条件：线性表L已存在。
操作结果：若L为空表， 则返回true, 否则返回false。
ListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中数据元素个数。
GetElem(L,i,&e)
初始条件：线性表L巳存在
操作结果：用e返回L中第i个数据元素的值。
LocateElem(L,e)
初始条件：线性表L已存在。
操作结果：返回L中第1个 值与e相同的元素在 L中的位置 。若这样的数据元素不存在 ， 则返回值为0。
PriorElem(r,,cur_e,&pre_e)
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义。
NextElem(L,cur_e,&next_e)
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义。
Listinsert(&L,i,e)
初始条件：线性表L已存在，且1:,s;i:os;ListLength (L) +l。
操作结果：在 L中第1个位置之前插入新的数据元素 e, L的长度加1。
ListDelete(&L,i)
初始条件：线性表L已存在且非空 ，且l:os;i:os;ListLength(L)。
操作结果：删除L的第1个数据元素，L的长度减1。
TraverseList(L)
初始条件：线性表L已存在。
操作结果：对线性表L进行遍历，在遍历过程中对 L的每个结点访问一次。
) ADT List
//－－－－－ 顺序表的存储结构－－－－－ //
#define MAXSIZE 100 //顺序表可能达到的最大长度
typedef struct {
ElemType *elem //声明了一个名为elem的长度不确定的数组，也叫“动态数组”,也可以声明为 //data[MAXSIZE];
int Length； //当前长度
}SqList； //顺序表的结构类型为SqList
算法步骤:：
算法描述:
Status InitList(SqList &L){
//构造一个空的顺序表
L.elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType)); //为顺序表分配空间,也可以用new
if (!L.elem) exit(OVERFLOW); //分配空间失败，退出
L.Length=0; //初始化长度为0
return OK;
}
算法步骤 ：
算法描述:
Status GetElem(SqList L,int i,ElemType &e){
if (i<1||i>L.Length) return ERROR； //判断数据不合理
e=L.elem[i-1];
return OK;
}
算法步骤 ：
从第一个元素起，依次和 e相比较，若找到与 e相等的元素 L.elem[i], 则查找成功，返回该元素的位置 i+l。
若查遍整个顺序表都没有找到，则查找失败， 返回0。
算法描述:
int LocateELem(SqList L,ElemType e){
//在顺序表1中查找值为e的数据元素， 返回其序号
for (i=0;i<L.Length;i++){
if (L.elem[i]==e) return i+1； //查找成功
}
return 0； //查找失败
}
算法步骤 ：
算法描述:
Status ListInit(SqList &L,int i,ElemType e){
if (i<1||i>L.Length+1) return ERROR; //插入位置不合理
if (L.Length==MaixSize) return ERROR; //顺序表已满
for (j=L.Length-1;j>=i-1;j--){
L.elem[j+1]= L.elem[j]; //从后向前依次后移
}
L.elem[i-1]=e //插入新元素
L.Length++; //长度加1
return OK;
}
算法步骤 ：
算法描述:
Status ListDelete(SqList &L,int i){
if (i<1||i>L.Length) return ERROR; //插入位置不合理
for (j=i;j<=L.Length-1;j++){
L.elem[j-1]=L.elme[j];
}
--L.Length;
return OK;
}
#include <stdio.h>
#include <stdlib.h>
#define Size 5
typedef struct Table{
int * head;
int length;
int size;
}table;
//初始化顺序表
table initTable(){
table t;
t.head=(int*)malloc(Size*sizeof(int));
if (!t.head)
{
printf("初始化失败");
exit(0);
}
t.length=0;
t.size=Size;
return t;
}
//添加元素
table addTable(table t,int elem,int add)
{
if (add>t.length+1||add<1) {
printf("插入位置有问题");
return t;
}
if (t.length>=t.size) {
t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));
if (!t.head) {
printf("存储分配失败");
}
t.size+=1;
}
for (int i=t.length-1; i>=add-1; i--) {
t.head[i+1]=t.head[i];
}
t.head[add-1]=elem;
t.length++;
return t;
}
//删除元素
table delTable(table t,int add){
if (add>t.length || add<1) {
printf("被删除元素的位置有误");
exit(0);
}
for (int i=add; i<t.length; i++) {
t.head[i-1]=t.head[i];
}
t.length--;
return t;
}
//查找元素
int selectTable(table t,int elem){
for (int i=0; i<t.length; i++) {
if (t.head[i]==elem) {
return i+1;
}
}
return -1;
}
//修改元素
table amendTable(table t,int elem,int newElem){
int add=selectTable(t, elem);
t.head[add-1]=newElem;
return t;
}
//遍历输出
void displayTable(table t){
for (int i=0;i<t.length;i++) {
printf("%d ",t.head[i]);
}
printf("\n");
}
int main(){
table t1=initTable();
for (int i=1; i<=Size; i++) {
t1.head[i-1]=i;
t1.length++;
}
printf("原顺序表：\n");
displayTable(t1);
printf("删除元素1:\n");
t1=delTable(t1, 1);
displayTable(t1);
printf("在第2的位置插入元素5:\n");
t1=addTable(t1, 5, 2);
displayTable(t1);
printf("查找元素3的位置:\n");
int add=selectTable(t1, 3);
printf("%d\n",add);
printf("将元素3改为6:\n");
t1=amendTable(t1, 3, 6);
displayTable(t1);
return 0;
}
输出：
原顺序表：
1 2 3 4 5
删除元素1:
2 3 4 5
在第2的位置插入元素5:
2 5 3 4 5
查找元素3的位置:
3
将元素3改为6:
2 5 6 4 5
原文：https://www.cnblogs.com/wind-zhou/p/12873273.html