时间空间复杂度

常对幂指阶
O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(2^n)<O(n!)<O(n^n)$

指针基础概念

&取地址符 *间接运算符

1
2
3

int number = 1;
int *p = &number;//声明一个int类型的指针指向number 存储着number的地址
printf("%d",*p);//输出指针p对应地址的值

malloc函数动态分配的空间需要手动free掉，属于内存中的堆区，系统不会自动回收空间，所以malloc和free的操作是成对出现的。

点操作符.与箭头操作符->的区别

相同点：两个都是二元操作符，其右操作符是成员的名称
不同点：点操作符左边的操作数是一个“结果为结构”的表达式；
箭头操作符左边的操作数是一个指向结构的指针

线性表

线性表的插入删除O(N)

void ListInsert(SqList *L,int i,int e){
    for(int j=L->length;j>=i;j--){
        L->data[j]=L->data[j-1];
    }
    L->data[i-1]=e;
    L->length++;
}
void ListDelete(SqList *L,int i){
    for(int j=i;j<L->length;j++){
        L->data[j]=L->data[j+1];
    }
    L->length--;
}

单链表

节点的创建

struct LNode{
    int val;
    struct LNode *next;
};
//typedef <数据类型> <别名>
typedef struct LNode Lnode,*LinkList;
bool InitList(LinkList L){
    L=(LNode*)malloc(sizeof(LNode));
    if(L==NULL)//内存不足
        return false;
    L->val=0;
    L->next=NULL;
    return true;
}
bool empty(LinkList L){
    if(L->next==NULL)
        return true;
    return false;
}

节点的插入

bool ListInsert(LinkList L,int i,int e){//在第i个结点插入值e
    if(i<1)return false;
    //返回第i-1个结点
    LNode *p=GetElem(L,i-1);
    //在结点p后面插入值为e的结点
    InsertNextNode(p,e);
}
bool InsertNextNode(LNode *p,int e){//在节点p后插元素e结点
    if(p==NULL)return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->val=e;
    s->next=p->next;
    p->next=s;
    return true;
}
bool InsertPriorNode(LNode *p,int e){//在p结点前e的结点
    if(p==NULL)return false;
    LNode *s=(LNode *)malloc(sizeof(e));
    if(s==NULL)return false;
    //在p结点之后插入值为e的结点 再交换p的值和e
    s-next=p->next;
    p->next=s;

    s->val=p->val;
    p->val=e;
}

单链表的查找

LNode *GetElem(LinkList L,int i){//返回第i个结点
    if(i==0)return L;
    int j=0;
    LNode *p=L->next;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    if(p==NULL)return NULL;
    return p;
}
LNode *LocateElem(LinkList L,int e){//返回数据域为e的结点
    int j=0;
    LNode *p=L->next;
    while(p!=NULL&&p->val!=e){
        p=p->next;
    }
    return p;
}

链表的头插法尾插法存储

头插法可以实现链表的逆置:

LinkList List_HeadInsert(LinkList L){
    L=(LNode *)malloc(sizeof(LNode));
    L->next=NULL;
    int t;
    while(scanf("%d")!=EOF){
        InsertNextNode(L,t);
    }
    
}

尾插法:

LinkList List_TailInsert(LinkList L){
    int t;
    L=(LNode *)malloc(sizeof(LNode));
    LNode *r=L;//表尾指针
    while(scanf("%d",&t)!=EOF){
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->val=t;
        r->next=s;
        r=s;
    }
    r->next=NULL;
    return L;
}

后缀表达式

将中缀表达式转换为后缀表达式

input:    2+3*(7-4)+8/4
output:   2 3 7 4 - * + 8 4 / +

从左到右遍历表达式中每个数字和符号，遇到数字就输出，若是符号则判断它与栈顶符号的优先级，如果是右括号或者优先级不高于（也就是<=）栈顶符号，则栈顶元素依次出栈，然后将当前符号进栈，一直到结束。

int opaIsBiggerThanopb(char a,char b){//判断符号a的优先级是否比b大
    if((a=='*'||a=='/')&&b!='*'&&b!='/'&&b!='('){
        return 1;
    }
    return 0;
}

双链表

初始化

typedef struct DNode{
    int val;
    struct DNode *next,*prior;

}DNode,*DLinkList;
bool InitDLinkList(DLinkList L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)return false;
    L->next=NULL;
    L->prior=NULL;
    return true;

}

双链表后插,前插操作

bool InsertNextDNode(DNode *p,DNode *s){//在p结点后插s结点
    if(p==NULL||s==NULL)return false;
    s->next=p->next;
    if(p->next!=NULL)
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}
bool InsertPriorDNode(DNode *p,DNode *s){//在p结点前插s结点
    if(p==NULL||s==NULL)return false;
    InsertNextDNode(p->next,s);
    return true;
}

双链表后删操作和链表清空操作

bool DeleteNextDNode(DNode *p){//删除p的后结点
    if(p==NULL||p->next==NULL)return false;
    DNode *s=p->next;
    if(s->next!=NULL)
        s->next->prior=p;
    p->next=s->next;
    free(s);
    return true;
}
void DestoryList(DlinkList L){//清空链表
    while(L->next!=NULL)
        DeleteNextDNode(L);
    free(L);
    L=NULL;
}

顺序表和链表的优劣

总结

顺序存储：占用空间连续，支持随机存取，查找O(1)改变容量不方便，增删操作O(N)
链式存储：离散小空间分配，增删O(1)不可随机存取，查找O(N)，数据密度低

初始化

顺序存储：预分配大片连续空间
静态分配：容量不可改变。系统自动回收空间
动态分配(malloc free)：容量可改变，但移动数据时间长。需要手动free
链式存储：只需要分配一个头指针

zhangas

Data structure