C语言(二)

单链表的新建查找

链表的实现

链表的实现需要定义结点的结构体类型，例如：

struct node {
    int data; // 数据域
    struct node *next; // 指针域
};

然后需要创建一个头指针，用于指向链表的第一个结点，例如：

1	struct node *head = NULL; // 创建一个空链表

接下来，可以通过动态分配内存的方式，创建新的结点，并将它们链接起来，例如：

struct node *p = (struct node *)malloc(sizeof(struct node)); // 创建一个新结点
p->data = 10; // 给数据域赋值
p->next = NULL; // 给指针域赋值
head = p; // 将头指针指向新结点

这样就实现了一个只有一个结点的链表。如果要添加更多的结点，可以重复上述过程，并将新结点的地址赋给前一个结点的指针域，例如：

struct node *q = (struct node *)malloc(sizeof(struct node)); // 创建另一个新结点
q->data = 20; // 给数据域赋值
q->next = NULL; // 给指针域赋值
p->next = q; // 将前一个结点的指针域指向新结点

链表的删除-插入-查找

例如，如果要删除链表中的第三个结点，可以用以下代码实现：

struct node *temp = head; // temp 指向头结点
temp = temp->next; // temp 指向第二个结点
struct node *del = temp->next; // del 指向要删除的第三个结点
temp->next = del->next; // 将第二个结点的指针域指向第四个结点
free(del); // 释放第三个结点的内存空间

例如，如果要在链表中的第三个结点后插入一个新的结点，可以用以下代码实现：

struct node *new = (struct node *)malloc(sizeof(struct node)); // 申请一个新的结点
new->data = x; // 将要插入的数据赋值给新结点的数据域
struct node *temp = head; // temp 指向头结点
temp = temp->next->next; // temp 指向第三个结点
new->next = temp->next; // 将新结点的指针域指向第四个结点
temp->next = new; // 将第三个结点的指针域指向新结点

例如，如果要在链表中查找第一个值为 x 的结点，可以用以下代码实现：

struct node *p = head->next; // p 指向首元结点
int i = 1; // i 记录当前结点的位置
while (p != NULL) { // 遍历链表
    if (p->data == x) { // 如果找到值为 x 的结点
        return i; // 返回位置
    }
    p = p->next; // p 指向下一个结点
    i++; // i 加一
}
return -1; // 如果遍历到尾部，仍未找到，返回 -1

实现顺序表插入删除

#include <stdio.h>  
  
#define MaxSize 100  
typedef int ElemType;  
typedef struct {  
    ElemType data[MaxSize];  
    int length;  
}SqList;  
  
//插入到第二个的函数  
void Put_arry(SqList &L,ElemType e){  
    int i = L.data[1];  
    int j;  
    for(j=L.length;j>1;j--){  
        L.data[j]=L.data[j-1];  
    }  
    L.data[i]=e;  
    L.length++;  
}  
  
//打印顺序表的方法  
void print_arr(SqList L){  
    int i;  
    for(i=0;i<L.length;i++){  
        printf("%3d ",L.data[i]);//"%3表示打印的数字占3个空格  
    }  
    printf("\n");  
}  
  
//删除元素方法  
void Delet_arry(SqList &L,ElemType e){  
    int i;  
    for(i=e;i<L.length;i++){  
        L.data[i-1]=L.data[i];  
    }  
    L.length--;  
}  
  
  
int main() {  
    SqList L;  
    L.data[0]=1;  
    L.data[1]=2;  
    L.data[2]=3;  
    L.length=3;  
    ElemType e;  
    scanf("%d",&e);  
    Put_arry(L,e);  
    print_arr(L);  
  
    ElemType del;  
    scanf("%d",&del);  
    Delet_arry(L,del);  
    print_arr(L);  
    return 0;  
}

头插法新建链表

这段代码，实现头插法新建一个链表，每次新建一个结点，都是放到第一个结点（注意头结点不是第一个结点，头结点指向第一个结点），该链表存储int类型数据，通过scanf输入建立对应的存储结点，直到输入9999,结束创建，并且不会包含9999

#include <stdio.h>  
#include <stdlib.h>  
  
typedef int ElemType;  
//定义结点结构体  
typedef struct LNode{  
    ElemType data;//数据域  
    struct LNode *next;//指针域  
}LNode,*LinkList;  

//头插法新建链表
//定义一个方法，申请头结点的空间  
//LNode*是结构体指针，与LinkList是完全等价的  
void list_head_insert(LNode* &L){  
    L= (LinkList)malloc(sizeof(LNode));//给L申请一个头结点结点空间  
    L->next=NULL;  
    ElemType x;//读取的第一个元素  
    LinkList s;//用来指向新节点  
    scanf("%d",&x);  
    while (x!=9999){  
        s=(LinkList) malloc(sizeof (LNode));//给s申请一个新的空间  
        s->data=x;  
        s->next=L->next;//实现头插法，s成为第一个结点  
        L->next=s;//L作为头结点，任然指向第一个结点  
        scanf("%d",&x);//读取x的值  
    }  
}  
  
void print_LinKlist(LinkList L){  
    L=L->next;  
    while(L!=NULL){  
        printf("%3d",L->data);  
        L=L->next;  
    }  
}  
  
int main() {  
    LinkList L;//定义链表的头指针  
    list_head_insert(L);  
    print_LinKlist(L);  
    return 0;  
}

尾插法新建链表

#include <stdio.h>  
#include <stdlib.h>  

typedef int ElemType;  
//定义结点结构体  
typedef struct LNode{  
    ElemType data;//数据域  
    struct LNode *next;//指针域  
}LNode,*LinkList;  
  
//尾插法新建链表  
void list_tail_insert(LinkList &L){  
    L=(LinkList) malloc(sizeof (LNode));  
    L->next=NULL;  
    ElemType x;  
    LNode *s,*r=L;//s指向新节点，r指向尾结点 ,将L赋给s,r ,相当于s,r,L都是头结点
    scanf("%d",&x);  
    while(x!=9999){  
        s=(LinkList) malloc(sizeof (LNode));  
        s->data=x;  
        r->next=s;  
        r=s;  //将s赋给r,r重新指向尾结点
        scanf("%d",&x);  
    }  
    r->next=NULL;  
}  
  
void print_LinKlist(LinkList L){  
    L=L->next;  
    while(L!=NULL){  
        printf("%3d",L->data);  
        L=L->next;  
    }  
}  
  
int main() {  
    LinkList L;//定义链表的头指针  
    list_tail_insert(L);  
    print_LinKlist(L);  
    return 0;  
}

链表-按值查找-按位置查找

#include <stdio.h>  
#include <stdlib.h>  
  
typedef int ElemType;  
//定义结点结构体  
typedef struct LNode{  
    ElemType data;//数据域  
    struct LNode *next;//指针域  
}LNode,*LinkList;  
  

//尾插法新建链表  
void list_tail_insert(LinkList &L){  
    L=(LinkList) malloc(sizeof (LNode));  
    L->next=NULL;  
    ElemType x;  
    LNode *s,*r=L;//s指向新节点，r指向尾结点  
    scanf("%d",&x);  
    while(x!=9999){  
        s=(LinkList) malloc(sizeof (LNode));  
        s->data=x;  
        r->next=s;  
        r=s;  
        scanf("%d",&x);  
    }  
    r->next=NULL;  
}  
  
void print_LinKlist(LinkList L){  
    L=L->next;  
    while(L!=NULL){  
        printf("%3d",L->data);  
        L=L->next;  
    }  
}  
  
//按位置查找  
 LinkList GetEle_by_pos(LinkList L,int pos){  
 //说明：L头结点的位置是0
    if(pos<1){  
        return NULL;  
    }  
    if(pos==0){  
        return L;  
    }  
    int i=0;  
    while(L&&i<pos){  
        L=L->next;  
        i++;  
    }  
    return L;  
}  
  
//按值查找  
LinkList GetEle_by_value(LinkList L,int value){  
  
    while(L){//表示L不为空，循环  
        if(L->data!=value){  
            L=L->next;  
        }if(L->data==value){  
            return L;  
        }  
    }  
    return NULL;  
  
}  
int main() {  
    LinkList L;//定义链表的头指针  
    list_tail_insert(L);  
    print_LinKlist(L);  
  
    LinkList pNode1 = GetEle_by_pos(L,3);  
    if(pNode1!=NULL){  
        printf("\nsearch by postion success\n");  
        printf("the value is %d\n",pNode1->data);  
    }  
  
  
    LinkList pNode2 = GetEle_by_value(L, 8);  
    if(pNode2!=NULL){  
        printf("search by value success\n");  
        printf("the value is %d\n",pNode2->data);  
    }  
  
    return 0;  
}

链表往第i 个位置插入元素

#include <stdio.h>  
#include <stdlib.h>  
  
typedef int ElemType;  
//定义结点结构体  
typedef struct LNode{  
    ElemType data;//数据域  
    struct LNode *next;//指针域  
}LNode,*LinkList;  
  
//尾插法新建链表  
void list_tail_insert(LinkList &L){  
    L=(LinkList) malloc(sizeof (LNode));  
    L->next=NULL;  
    ElemType x;  
    LNode *s,*r=L;//s指向新节点，r指向尾结点  
    scanf("%d",&x);  
    while(x!=9999){  
        s=(LinkList) malloc(sizeof (LNode));  
        s->data=x;  
        r->next=s;  
        r=s;  
        scanf("%d",&x);  
    }  
    r->next=NULL;  
}  
//打印链表的方法
void print_LinKlist(LinkList L){  
    L=L->next;  
    while(L!=NULL){  
        printf("%3d",L->data);  
        L=L->next;  
    }  
}  
  
//按位置查找  
 LinkList GetEle_by_pos(LinkList L,int pos){  
    if(pos<1){  
        return NULL;  
    }  
    if(pos==0){  
        return L;  
    }  
    int i=0;  
    while(i<pos){  
        L=L->next;  
        i++;  
    }  
    return L;  
}  
  
//插入方法，往第i个位置插入元素  
bool ListFrontInsert(LinkList L,int i,int insert){  
    //先找到链表第i-1个位置，并指向  
    LinkList p = GetEle_by_pos(L, i-1);  
    if(p==NULL){  
        return false;  
    }  
    //定义一个新的结点  
    LinkList q;  
    q = (LinkList) malloc(sizeof(LNode));  
    q->next=p->next;  
    q->data=insert;  
    p->next=q;  
    return true;
 }  
  
int main() {  
    LinkList L;//定义链表的头指针  

    list_tail_insert(L);  
    print_LinKlist(L);  

    printf("\n");  
    ListFrontInsert(L,2,80);  //往第二个位置，插入80
    print_LinKlist(L);  
    return 0;  
}

单链表的删除

单链表删除实战

#include <stdio.h>  
#include <stdlib.h>  
  
typedef int ElemType;  
//定义结点结构体  
typedef struct LNode{  
    ElemType data;//数据域  
    struct LNode *next;//指针域  
}LNode,*LinkList;  
  
//尾插法新建链表  
void list_tail_insert(LinkList &L){  
    L=(LinkList) malloc(sizeof (LNode));  
    L->next=NULL;  
    ElemType x;  
    LNode *s,*r=L;//s指向新节点，r指向尾结点  
    scanf("%d",&x);  
    while(x!=9999){  
        s=(LinkList) malloc(sizeof (LNode));  
        s->data=x;  
        r->next=s;  
        r=s;  
        scanf("%d",&x);  
    }  
    r->next=NULL;  
}  
//按位置查找  
LinkList GetEle_by_pos(LinkList L,int pos){  
    //说明：L头结点的位置是0  
    if(pos<1){  
        return NULL;  
    }  
    if(pos==0){  
        return L;  
    }  
    int i=0;  
    while(i<pos){  
        L=L->next;  
        i++;  
    }  
    return L;  
}  
//打印链表的方法  
void print_LinKlist(LinkList L){  
    L=L->next;  
    while(L!=NULL){  
        printf("%3d",L->data);  
        L=L->next;  
    }  
    printf("\n");  
}  
  
//单链表的删除方法  
bool delet_list(LinkList L,int pos){  //删除时，L是不会变得，所以不需要加引用
    if(pos>1){  
        LinkList p = GetEle_by_pos(L,pos - 1); //拿到哟啊删除结点的前一个结点指针
        LinkList q=p->next;  //拿到要删除的结点指针
        if(q!=NULL){  
            p->next=q->next;  
            free(q);  //释放被删除元素的空间
            return true;        
            }  
    }  
    return false;  
}  
  
int main() {  
    LinkList L;  
    list_tail_insert(L);  
    print_LinKlist(L);  
    delet_list(L,2);  
    print_LinKlist(L);  
    return 0;  
}

真题，链表转置实战

转置图示

合并图解

#include <stdio.h>  
#include <stdlib.h>  
  
typedef int ElemType;  
//定义结点结构体  
typedef struct LNode{  
    ElemType data;//数据域  
    struct LNode *next;//指针域  
}LNode,*LinkList;  
  
//尾插法新建链表  
void list_tail_insert(LinkList &L){  
    L=(LinkList) malloc(sizeof (LNode));  
    L->next=NULL;  
    ElemType x;  
    LNode *s,*r=L;//s指向新节点，r指向尾结点  
    scanf("%d",&x);  
    while(x!=9999){  
        s=(LinkList) malloc(sizeof (LNode));  
        s->data=x;  
        r->next=s;  
        r=s;  
        scanf("%d",&x);  
    }  
    r->next=NULL;  
}  
//打印链表的方法  
void print_LinKlist(LinkList L){  
    L=L->next;  
    while(L!=NULL){  
        printf("%3d",L->data);  
        L=L->next;  
    }  
    printf("\n");  
}  
  
//找中心结点  
//当链表奇数个结点取中间，偶数个结点取前一个  
void find_middle(LinkList L,LinkList &L2){//L表示第一条链表头结点，L2表示第二条链表头结点  
    L2=(LinkList) malloc(sizeof(LNode));  
    LinkList p,pp;//双指针  
    p=pp=L->next;  
    while(pp){  
        pp=pp->next;  
        if(pp==NULL){//必须判断每一步是否为空，防止崩溃  
            break;  
        }  
        pp=pp->next;  
        if(pp==NULL){  
            break;  
        }  
        p=p->next;  
    }  
    L2->next=p->next;  
    p->next=NULL;//链表最后一个结点next要为空  
}  
//找中心结点，while循环次数是n/2
  
//逆置方法  
void reverse(LinkList L2){//逆转是不改变头指针的  
    LinkList r,s,t;  
    r=L2->next;  
    if(r==NULL){//没有结点  
        return;  
    }  
    s=r->next;  
    if(s==NULL){//一个结点  
        return;  
    }  
    t=s->next;  
    while(t){  
        s->next=r;//逆转  
        r=s;  
        s=t;  
        t=t->next;  
    }  
    s->next=r;  
    L2->next->next=NULL;//逆置后原链表第一个结点，变成最后一个结点，它的next=NULL;  
    L2->next=s;  
}  
//逆转函数逆转的是L2链表，执行次数是n/2,

  //合并方法
void merge(LinkList L,LinkList L2){  
    LinkList pcur,p,q;  
    pcur=L->next;  
    p=pcur->next;  
    q=L2->next;  
    while(p!=NULL&&q!=NULL){  
        pcur->next=q;  
        q=q->next;  
        pcur=pcur->next;  
        pcur->next=p;  
        p=p->next;  
        pcur=pcur->next;  
    }  
}  
//上面merge函数的while循环遍历次数是n/2,所以时间复杂度是O(n)

int main() {  
    LinkList L;  
    LinkList L2;  
  
    list_tail_insert(L);  
    print_LinKlist(L);  
  
    find_middle(L,L2);  
    print_LinKlist(L);  
    print_LinKlist(L2);  
  
    reverse(L2);  
    print_LinKlist(L2);  
  
    merge(L,L2);  
    free(L2);  
    print_LinKlist(L);  
    return 0;  
//综上，merge、find_middle、reverse函数总的时间复杂度是1.5n,忽略首项系数O(n)
}

OJ测试

作业说明

#include <stdio.h>  
#include <stdlib.h>  
  
typedef int ElemType;  
  
typedef struct LNode{  
    ElemType data;  
    struct LNode* next;  
}LNOde,*Linklist;  
  
//尾插法新建链表  
void list_tail_insert(Linklist &L){  
    L=(Linklist) malloc(sizeof(LNode));  
    L->next=NULL;  
    Linklist s,r=L;  
    int x;  
    scanf("%d",&x);  
    while(x!=9999){  
        s=(Linklist) malloc(sizeof(LNode));  
        s->data=x;  
        r->next=s;  
        r=s;  
        scanf("%d",&x);  
    }  
    s->next=NULL;  
}  
  
//按位置查找的方法  
Linklist getEle_by_pos(Linklist L,int pos){  
    if(pos==0){  
        return L;  
    }  
    if(pos<1){  
        return NULL;  
    }  
    int i=0;  
    while(L&&i<pos){ //注意：while(i<pos){} 忽略了L为空 也不能循环 
        L=L->next;  
        i++;  
    }  
    return L;  
}  
  
//按位置插入的方法  
void list_insert(Linklist L,int i,int insert){  
    Linklist p = getEle_by_pos(L,i - 1);  
    if(p==NULL){  
        return;  
    }  
    Linklist s;  
  
    s=(Linklist) malloc(sizeof(LNode));  
    s->next=p->next;  
    s->data=insert;  
    p->next=s;  
}  
  
//打印链表的方法  
void print_list(Linklist L){  
    while(L){  
        L=L->next;  
        if(L==NULL){  
            break;  
        }  
        printf("%3d",L->data);  
    }  
    printf("\n");  
}  
  
int main() {  
    Linklist L;  
    list_tail_insert(L);  
    print_list(L);  
    list_insert(L,2,99);  
    print_list(L);  
    return 0;  
}

栈与队列

栈原理解析

//定义一个结构体(栈)
typrdef struct{
	Elemtype data[50];
	int top;
}SqStack;


//此时栈为空
S.top=-1;


//入栈操作
//前加加，先获取栈位置，在加元素
//S.top=S.top+1;
//S.data[S.top]=4;
S.data[++S.top]

//前加加-->先做加1，后做其他运算；
//后加加-->先做其他运算，在做加1；

//出栈操作
//后减减，先拿到取出的元素
//x=S.data[S.top];
//S.top=S.top-1;
x=S.data[S.top--]

初始化栈-入栈-出栈

#include <stdio.h>  
  
#define Maxsize 50  
  
typedef int ElemType;  
//定义栈结构体  
typedef struct{  
    ElemType data[Maxsize];//栈空间  
    int top;//栈针  
}SqStack;  
  
//初始化栈方法  
void innit(SqStack &S){  
    S.top=-1;  
}  
  
//压栈方法  
bool Push(SqStack &S,ElemType e){  
    if(S.top==Maxsize-1){  
        return false;  
    }  
    //S.data[S.top++]=e; //先赋值，然后+
    S.data[++S.top]=e;  //先+，然后赋值
    return true;}  
  
//打印栈的方法  
void print_satck(SqStack S){  
    for(int i=0;i<S.top+1;i++){  
        printf("%3d",S.data[i]);  
    }  
    printf("\n");  
}  
  
//判断栈是否为空  
bool isEmpty(SqStack S){  
    if(S.top==-1){  
        return true;  
    }  
    return false;  
}  
  
//弹栈方法  
bool Pop(SqStack &S,ElemType &e){  
    if(isEmpty(S)){  
        return false;  
    }  
    e=S.data[S.top--];//拿完栈顶元素后，弹栈  
    return true;  
}  
  
int main() {  
    SqStack S;  
    innit(S);  
      
    Push(S,79);  
    Push(S,2);  
    Push(S,3);  
    print_satck(S);  
  
    ElemType e;  
    bool flag;  
    flag=Pop(S,e);  
    if(flag){  
        print_satck(S);  
    }  
    return 0;  
}

队列循环队列原理解析

队列

1
2
3

队列实现有两种常见方式：数组、链表

特点：允许头部删除，尾部增加

循环队列

1	循环队列实现是通过数组的方式

链式队列

1	链式队列的实现通过链表

循环队列数组实现

#include <stdio.h>  
  
#define Maxsize 5  
  
typedef int ElemType;  
//循环队列结构体  
typedef struct{  
    ElemType data[Maxsize];//数组，存储Maxsize-1个元素  
    int front,rear;//队列头，队列尾  
}SqQueue;  
  
//初始化队列方法  
void Innit(SqQueue &Q){  
    Q.rear=Q.front=0;  
}  
  
//入队列函数  
bool EnQueue(SqQueue &Q,ElemType e){  
    if((Q.rear+1)%Maxsize==Q.front){//判断队列是否满了  
        return false;  
    }  
    Q.data[Q.rear]=e;//放入元素  
    Q.rear=(Q.rear+1)%Maxsize;//改变队尾标记  
    return true;  
}  
  
//出队列函数  
bool OutQueue(SqQueue &Q,ElemType &x){  
    if(Q.rear==Q.front){  
        return false;  
    }  
    x=Q.data[Q.front];//拿到删除的元素  
    Q.front=(Q.front+1)%Maxsize;  
    return true;}  
  
//打印队列的方法  
void print_queue(SqQueue Q){  
    int i;  
    for(i=Q.front;i<Q.rear;i++){  
        printf("%3d",Q.data[i]);  
    }  
    printf("\n");  
}  
  
int main() {  
    SqQueue Q;  
    bool flag;
    ElemType e; 
    
    Innit(Q);  
    EnQueue(Q,29);  
    EnQueue(Q,39);  
    EnQueue(Q,9);  
    print_queue(Q);  
  
   
    flag=OutQueue(Q,e); 
    if(flag){
	    printf("Pop success ,the pop value is %d\n",e);
    } 
    print_queue(Q);  
  
    return 0;  
}

队列链表实现-1

这是带有头结点的方式实现

一般队列的头结点是否有数据取决于队列的实现方式：

-   如果队列是用数组实现的，那么头结点就是数组的第一个元素，它有数据；
-   如果队列是用链表实现的，那么头结点可以是一个空结点，也可以是链表的第一个元素，这取决于是否使用带头结点的链表。如果使用带头结点的链表，那么头结点没有数据，只是一个指针；如果使用不带头结点的链表，那么头结点就是链表的第一个元素，它有数据。

#include <stdio.h>  
#include <stdlib.h>  
  
typedef int Elemype;  
  
typedef struct LinkNode{  
    Elemype data;  
    struct LinkNode* next;  
}LinkNode,*LinkList;  
  
typedef struct {  
    LinkList front,rear;//链表头，链表尾  
}LinkQueue;  
  
//初始化链表的方法  
void innit(LinkQueue &Q){  
    Q.rear=Q.front=(LinkList) malloc(sizeof(LinkNode));  //这是一种带头结点的实现方式
    Q.rear->next
    =NULL;  
}  
  
//入队列函数,尾部插入法  
bool EnQueue(LinkQueue &Q,Elemype x){  
    LinkList s;  
    s=(LinkList) malloc(sizeof(LinkNode));  
    s->data=x;  
    Q.rear->next=s;  
    Q.rear=s;//注意这一步容易漏掉  
    s->next=NULL;  
    return true;}  
  
//出队列函数  
bool OutQueue(LinkQueue &Q){  
    if(Q.front->next==NULL){//判断一个元素也没有  
        return false;  
    }  
    LinkList s=Q.front->next;  
    Q.front->next=s->next;  
    if(Q.rear==s){//判断删除的是最后一个元素  
        Q.rear=Q.front;//队列为空  
    }  
    free(s);  
    return true;}  
  
int main() {  
    LinkQueue Q;  
    innit(Q);  
  
    EnQueue(Q,20);  
    EnQueue(Q,20);  
    EnQueue(Q,20);  
    EnQueue(Q,20);  
  
    bool ret;  
    ret= OutQueue(Q);  
    if(ret){  
        printf("Pop success");  
    }else{  
        printf("Pop fail");  
    }  
    return 0;  
}

队列链表的实现-2

带头结点的队列，队列的头指针和尾指针都指向一个空的头结点，头结点的next指针指向第一个元素，尾结点的next指针为NULL。
不带头结点的队列，队列的头指针指向第一个元素，尾指针指向最后一个元素，尾结点的
不带头结点

不带头结点的链表

/*实现不带头结点的链式队列*/
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef bool Status;
/*0.定义链式队列的基本结构*/
typedef struct LinkNode {
    //链式队列结点
    ElemType data;
    struct LinkNode* next;
}LinkNode;
typedef struct {
    //链式队列
    LinkNode* front, * rear; //队列的队头和队尾指针
}LinkQueue;
/*1.初始化链式队列 (不带头结点)*/
void InitQueue(LinkQueue& Q) {//初始时，front、rear都指向NULL
    Q.front = NULL;
    Q.rear = NULL;
}
/*2.判断队列是为空（不带头结点）*/
Status IsEmpty(LinkQueue Q) {
    if (Q.front == NULL)
        return true;
    else
        return false;
}
/*3.入队 (不带头结点)*/
Status EnQueue(LinkQueue& Q, ElemType x) {
    LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    if (s == NULL)
        return false;
    s->data = x;
    s->next = NULL;
    if (Q.front == NULL) //在空的队列中插入第一元素
    {
        //不带头结点的队列，第一个元素入队时需要特别处理
        Q.front = s; //修改队头队尾指针
        Q.rear = s;
    }
    else {
        Q.rear->next = s; //新结点插入到rear之后
        Q.rear = s; //修改表尾指针
    }
    return true;
}
/*4.出队（不带头结点）*/
Status DeQueue(LinkQueue& Q, ElemType& x) {
    if (Q.front == NULL)
        return false; //空队
    LinkNode* p = Q.front; //p指向此次出队的结点
    x = p->data; //用变量x返回队头元素
    Q.front = p->next; //修改front指针
    if (Q.rear == p) //此次是最后一个结点出队
    {
        Q.front = NULL; //front指向NULL
        Q.rear = NULL; //rear指向NULL
    }
    free(p); //释放结点空间
    return true;
}
int main() {
    LinkQueue Q;
    ElemType x = -1;
    InitQueue(Q);
    EnQueue(Q, 3);
    EnQueue(Q, 6);
    EnQueue(Q, 8);
    EnQueue(Q, 9);
    EnQueue(Q, 7);
    EnQueue(Q, 5);
    for (int i = 1; i < 6; i++) {
        DeQueue(Q, x);

OJ测试

#include <stdio.h>  
#include <stdlib.h>  
  
#define MaxSize 5  
typedef int ElemType;  
//定义一个栈结构体  
typedef struct {  
    ElemType data[MaxSize];  
    int top;  
}SqStack;  
  
//定义一个循环队列结构体  
typedef struct {  
    ElemType data[MaxSize];  
    int front,rear;//队列头，队列尾  
}SqQueue;  
  
  
//初始化栈方法  
void initStack(SqStack &S){  
    S.top=-1;  
}  
  
//入栈方法  
bool Push(SqStack &S,ElemType e){  
    if(S.top==MaxSize-1){  
        return false;  
    }  
    S.data[++S.top]=e;  
    return true;}  
  
//出栈方法  
bool Pop(SqStack &S,ElemType &e){  
    if(S.top==-1){  
        return false;  
    }  
    e=S.data[S.top--];  
    return true;}  
  
//打印栈的方法  
void print_stack(SqStack S){  
    int i;  
    for(i=0;i<S.top+1;i++){  
        printf("%3d",S.data[i]);  
    }  
    printf("\n");  
}  
  
//初始化队列的方法  
void initQueue(SqQueue &Q){  
    Q.front=Q.rear=0;  
}  
  
//入队列方法  
bool EnQueue(SqQueue &Q,ElemType e){  
    if((Q.rear+1)%MaxSize==Q.front){//判断队列是否满  
        return false;  
    }  
    Q.data[Q.rear]=e;  
    Q.rear=(Q.rear+1)%MaxSize;  
    return true;}  
  
//出队列方法  
bool OutQueue(SqQueue &Q,ElemType &e){  
    if(Q.rear==Q.front){  
        return false;  
    }  
    e=Q.data[Q.front];  
    Q.front=(Q.front+1)%MaxSize;  
    return true;}  
  
//打印队列的方法  
void print_queue(SqQueue Q){  
    int i;  
    for(i=Q.front;i<Q.rear;i++){  
        printf("%3d",Q.data[i]);  
    }  
}  
  
int main() {  
    SqStack S;  
    initStack(S);  
  
    int i,num;  
  
    for(i=0;i<3;i++){  
        scanf("%d",&num);  
        Push(S,num);  
    }  
    print_stack(S);  
  
    ElemType m;//用来存放拿出来的元素  
    for(i=0;i<3;i++){  
        Pop(S,m);  
        printf("the ride num is %d\n",m);  
    }  
  
  
    SqQueue Q;  
    ElemType e;  
    initQueue(Q);  
  
    int i2,num2;  
    bool flag;  
    for(i2=0;i2<5;i2++){  
        scanf("%d",&num2);  
        flag=EnQueue(Q,num2);  
        if(!flag){  
            printf("flase Queue is full\n");  
        }  
    }  
  
    for(i2=0;i2<4;i2++){  
        OutQueue(Q,e);  
        printf("%3d",e);  
    }  
      
    return 0;  
}

二叉树的建树和遍历

树与二叉树原理解析

树原理解析

二叉树原理

1
2
3

1、满二叉树:每一层都放满了

2、完全二叉树:除了最后一层，前面层数全部放满，最后一层从左往右，只能是右侧有空

二叉树的层次建树

上面层次建树的实现通过辅助队列实现
每加一个元素，辅助队列就往队尾加一个元素
而pcur指针判断结点的左右两侧都放满了时，才往后移动
这样就实现了层次建树

以下代码实现了，输入abcdefgj一串连续字符，然后按层次建树存储

这里的辅助队列有四个指针：front-rear-listpnew-pcur 起初都赋值为NULL,就是没有头结点得方式创建队列

	front指向第一个结点
	rear指向末尾结点
	listpnew指向新加元素
	pcur指向当前结点

这里的二叉树有一个指针:pnew指向树的最新结点

头文件 function.h 代码如下

#include <stdio.h>  
#include <stdlib.h>  
  
typedef char ElenType;  

//二叉树的链表结点
typedef struct TNode{  
    ElenType c;//数据域  
    struct TNode *lift,*right;//指针域:左指针、右指针  
}BiTNode,*BiTree;  
  
//辅助队列的链表结点
typedef struct tag{  
    BiTree p;//p获取数的结点 
    struct tag *pnext;  
}tag,*ptag;

主文件 main.cpp 代码如下

#include "function.h"  
  
int main() {  
    BiTree pnew;//用来指向树的新节点  
    BiTree root=NULL;//赋值为NULL用于下面的if判断  
    //注意，树根不像链表头结点  
    //链表头结点用来指向第一个结点，里面可以不放东西  
    //但是二叉树没有头结点
    //第一个结点就是树根，用来存数据 
  
    char c;  
    ptag front=NULL,rear=NULL,listpnew=NULL,pcur=NULL;//队列头、队列尾、指向树的新节点、指向当前队列结点  
    while(scanf("%c",&c)){  
        if(c=='\n'){  
            break;  
        }  
        //calloc申请的空间大小是两个参数相乘，并且初始化空间，赋值为Null(左右指针赋值为Null)  
        pnew=(BiTree) calloc(1,sizeof (BiTNode));  
        pnew->c=c;  
        listpnew= (ptag)calloc(1,sizeof(tag));  
        listpnew->p=pnew;  
        //如果是树的第一个结点  
        if(root==NULL){  
            root=pnew;//root指向根结点  
            rear=front=listpnew;  
            pcur=listpnew;//pcur要指向要进入树的父亲元素(当前元素)  
        //if无论是否满足条件都会向下执行，else if只有在上一个条件不满足的情况下才会执行
        }else{  
            rear->pnext=listpnew;//入队列  
            rear=listpnew;  
            if(pcur->p->lift==NULL){//左为空，放入左  
                pcur->p->lift=pnew;  
            }else if(pcur->p->right==NULL){//右为空，放入右  
                pcur->p->right=pnew;  
                //此时结点满了  
                //pcur往后移一位  
                pcur=pcur->pnext;  
            }  
        }  
    }  
    return 0;  
}

二叉树的-前中后-序遍历

递归思想

1前序遍历:PreOrder 
    前序遍历也叫深度优先遍历
2中序遍历：InOrder
3后序遍历：PostOrder

function.h代码如下

#include <stdio.h>  
#include <stdlib.h>  
  
typedef char ElenType;  

//二叉树的链表结点
typedef struct TNode{  
    ElenType c;//数据域  
    struct TNode *lift,*right;//指针域:左指针、右指针  
}BiTNode,*BiTree;  
  
//辅助队列的链表结点
typedef struct tag{  
    BiTree p;//p获取数的结点 
    struct tag *pnext;  
}tag,*ptag;

main.cpp代码如下

#include "function.h"  
  
//前序遍历，先序遍历，也叫深度优先遍历  
void PreOrder(BiTree p){  
    if(p!=NULL) {  
        printf("%c", p->c);  
        PreOrder(p->lift);//打印左子树  
        PreOrder(p->right);//打印又子树  
    }  
}  
  
//中序遍历  
void InOrder(BiTree p){  
    if(p!=NULL) {  
        InOrder(p->lift);  
        printf("%c", p->c);  
        InOrder(p->right);  
    }  
}  
  
//后序遍历  
void  PostOrder(BiTree p){  
    if(p!=NULL){  
        PostOrder(p->lift);  
        PostOrder(p->right);  
        printf("%c",p->c);  
    }  
}  
  
int main() {  
    BiTree pnew;//用来指向树的新节点  
    BiTree root=NULL;//用来指向树根  
    //注意，树根不像链表头结点  
    //链表头结点用来指向第一个结点，里面可以不放东西  
    //根就相当于第一个结点，必须有数据  
  
    char c;  
    //队列头、队列尾、指向树的新节点、指向当前队列结点  
    ptag front=NULL,rear=NULL,listpnew=NULL,pcur;
    while(scanf("%c",&c)){  
        if(c=='\n'){  
            break;  
        }  
    //calloc申请的空间大小是两个参数相乘，并且初始化空间，赋值为Null(左右指针赋值为Null)  
        pnew=(BiTree) calloc(1,sizeof (BiTNode));  
        pnew->c=c;  
        listpnew= (ptag)calloc(1,sizeof(tag));  
        listpnew->p=pnew;  
        //如果是树的第一个结点  
        if(root==NULL){  
            root=pnew;//root指向根结点  
            rear=front=listpnew;  
            pcur=listpnew;//pcur要指向要进入树的父亲元素(当前元素)  
        }else{  
            rear->pnext=listpnew;//入队列  
            rear=listpnew;  
            if(pcur->p->lift==NULL){//左为空，放入左  
                pcur->p->lift=pnew;  
            }else if(pcur->p->right==NULL){//右为空，放入右  
                pcur->p->right=pnew;  
                //此时结点满了  
                //pcur往后移一位  
                pcur=pcur->pnext;  
            }  
        }  
    }  
  
    printf("=================\n");  
    PreOrder(root);  
    printf("\n");  
    InOrder(root);  
    printf("\n");  
    PreOrder(root);  
    return 0;  
}

二叉树的层次遍历

也称广度优先遍历

[二叉树的广度优先遍历是一种按层次遍历二叉树的方法，它的顺序是从上到下，从左到右，依次访问每一层的节点][。广度优先遍历的原则就是对每一层的节点依次访问，一层访问结束后，进入下一层，直到最后一个节点，每个节点都只访问一次]
[二叉树的广度优先遍历的实现需要借助队列（Queue）这种数据结构，它的特点是先进先出。首先将根节点入队，然后循环执行以下操作，直到队列为空：从队列中取出一个节点，访问它，然后将它的左右子节点（如果有的话）入队]。

例如，对于下图的二叉树，广度优先遍历的结果是 {1，2，3，4，5，6，7，8，9，10}，遍历过程如下：

1.  将根节点1入队，队列为【1】
2.  取出节点1，访问它，将它的左右子节点2和3入队，队列为【2，3】
3.  取出节点2，访问它，将它的左右子节点4和5入队，队列为【3，4，5】
4.  取出节点3，访问它，将它的右子节点6入队，队列为【4，5，6】
5.  取出节点4，访问它，将它的左右子节点8和9入队，队列为【5，6，8，9】
6.  取出节点5，访问它，将它的右子节点10入队，队列为【6，8，9，10】
7.  取出节点6，访问它，没有子节点，队列为【8，9，10】
8.  取出节点8，访问它，没有子节点，队列为【9，10】
9.  取出节点9，访问它，没有子节点，队列为【10】
10.  取出节点10，访问它，没有子节点，队列为空，遍历结束

代码采用3给文件

function.h代码如下

//  
// Created by 123 on 2023/3/11.  
//  
  
#ifndef INC_1_TREE_FUNCTION_H  
#define INC_1_TREE_FUNCTION_H  
  
#include <stdio.h>  
#include <stdlib.h>  
  
//树相关结构  
typedef char BiElemType;  
  
typedef struct BiTNode{  
    BiElemType c;  
    struct BiTNode *lift;  
    struct BiTNode *right;  
}BiTNode,*BiTree;  
  
//层次建树的辅助队列  
typedef struct tag{  
    BiTree p;//p获取数的结点  
    struct tag *pnext;  
}tag,*ptag;  
  
//层次遍历的辅助队列相关结构  
typedef BiTree ElemType;  
  
typedef struct LinkNode{  
    ElemType data;  
    struct LinkNode* next;  
}LinkNode,*LinkList;  
  
typedef struct {  
    LinkList front,rear;//链表头，链表尾  
}LinkQueue;  
  
//初始化队列  
void innit(LinkQueue &Q);  
//入队  
bool EnQueue(LinkQueue &Q,ElemType x);  
//出队  
bool OutQueue(LinkQueue &Q,ElemType &x);  
//判断是否为空  
bool IsEmpty(LinkQueue Q);  
  
#endif //INC_1_TREE_FUNCTION_H

Queue.cpp代码如下

//  
// Created by 123 on 2023/3/11.  
//  
#include "function.h"  
//初始化链表的方法  
void innit(LinkQueue &Q){  
    Q.rear=Q.front=(LinkList) malloc(sizeof(LinkNode));  
    Q.rear->next=NULL;  
}  
  
//入队列函数,尾部插入法  
bool EnQueue(LinkQueue &Q,ElemType x){  
    LinkList s;  
    s=(LinkList) malloc(sizeof(LinkNode));  
    s->data=x;  
    Q.rear->next=s;  
    Q.rear=s;//注意这一步容易漏掉  
    s->next=NULL;  
    return true;}  
  
//出队列函数  
bool OutQueue(LinkQueue &Q,ElemType &x){  
    if(Q.front->next==NULL){//判断一个元素也没有  
        return false;  
    }  
    LinkList s=Q.front->next;  
    x=s->data;  
    Q.front->next=s->next;  
    if(Q.rear==s){//判断删除的是最后一个元素  
        Q.rear=Q.front;//队列为空  
    }  
    free(s);  
    return true;}  
  
//判断是否为空  
bool IsEmpty(LinkQueue Q){  
    if(Q.rear==Q.front){  
        return true;  
    }  
    return false;  
}

main.cpp代码如下

#include "function.h"  
  
//前序遍历，先序遍历，也叫深度优先遍历  
void PreOrder(BiTree p){  
    if(p!=NULL) {  
        printf("%c", p->c);  
        PreOrder(p->lift);//打印左子树  
        PreOrder(p->right);//打印又子树  
    }  
}  
  
//中序遍历  
void InOrder(BiTree p){  
    if(p!=NULL) {  
        InOrder(p->lift);  
        printf("%c", p->c);  
        InOrder(p->right);  
    }  
}  
  
//后序遍历  
void  PostOrder(BiTree p){  
    if(p!=NULL){  
        PostOrder(p->lift);  
        PostOrder(p->right);  
        printf("%c",p->c);  
    }  
}  
  
//层次遍历（广度优先遍历）  
void LevelOrder(BiTree T){  
    //辅助队列  
    LinkQueue Q;  
    //初始化队列  
    innit(Q);  
    BiTree p;//获取出队元素  
    //树根入队  
    EnQueue(Q,T);  
    while(!IsEmpty(Q)){  
        //出队列的同时，判断出去的这个元素，左右子树是否存在，存在就入队  
        //循环这个过程，直到队列为空  
        OutQueue(Q,p);//出队函数，能获得出队元素，切将出队元素赋值给p  
        putchar(p->c);  
        if(p->lift!=NULL){//入队左子树  
            EnQueue(Q,p->lift);  
        }  
        if(p->right!=NULL){//入队右子树  
            EnQueue(Q,p->right);  
        }  
    }  
  
}  
int main() {  

//首先层次建树
    BiTree pnew;//用来指向树的新节点  
    BiTree root=NULL;//用来指向树根  
    //注意，树根不像链表头结点  
    //链表头结点用来指向第一个结点，里面可以不放东西  
    //根就相当于第一个结点，必须有数据  
  
    char c;  
    //队列头、队列尾、指向队列的新节点、指向当前队列结点  
    ptag front=NULL,rear=NULL,listpnew=NULL,pcur;
    while(scanf("%c",&c)){  
        if(c=='\n'){  
            break;  
        }  
        //calloc申请的空间大小是两个参数相乘，并且初始化空间，赋值为Null(左右指针赋值为Null)  
        pnew=(BiTree) calloc(1,sizeof (BiTNode));  
        pnew->c=c;  
        listpnew= (ptag)calloc(1,sizeof(tag));  
        listpnew->p=pnew;  
        //如果是树的第一个结点  
        if(root==NULL){  
            root=pnew;//root指向根结点  
            rear=front=listpnew;  
            pcur=listpnew;//pcur要指向要进入树的父亲元素(当前元素)  
        }else{  
            rear->pnext=listpnew;//入队列  
            rear=listpnew;  
            if(pcur->p->lift==NULL){//左为空，放入左  
                pcur->p->lift=pnew;  
            }else if(pcur->p->right==NULL){//右为空，放入右  
                pcur->p->right=pnew;  
                //此时结点满了  
                //pcur往后移一位  
                pcur=pcur->pnext;  
            }  
        }  
    }  
  
    printf("=================\n");  
    PreOrder(root);   //前序遍历（深度优先遍历）
	printf("\n"); 
    InOrder(root);    //中序遍历
    printf("\n");  
    PreOrder(root);   //后序遍历
    printf("\n");  
    LevelOrder(root);  //广度优先遍历
  
    return 0;  
}

真题-求带权路径长度

1	由于与深度有关，可采用深度优先遍历方式(可以获取深度)，最后返回wpl

function.h代码如下

#include <stdio.h>  
#include <stdlib.h>  
  
typedef char ElenType;  
  
//二叉树的链表结点  
typedef struct TNode{  
    ElenType c;//数据域  
    struct TNode *lift,*right;//指针域:左指针、右指针  
}BiTNode,*BiTree;  
  
//辅助队列的链表结点  
typedef struct tag{  
    BiTree p;//p获取数的结点  
    struct tag *pnext;  
}tag,*ptag;

main.cpp代码如下

#include "function.h"  
  
//int wpl=0;  
//全局变量，和静态局部变量都是放在数据段  
//静态局部变量只能局部访问，全局变量全局访问  
  
//前序遍历,参数增加一个深度deep  
int PreOrder(BiTree p,int deep){  
    //静态变量，只会初始化一次，递归的时候不会再次执行，直接访问  
    //只能局部访问，所以将其以返回值的形式返回  
    static int wpl=0;  
  
    if(p!=NULL) {  
        if(p->lift==NULL&&p->right==NULL){  
            wpl+=p->c*deep;  
        }  
        printf("ele%c---deep%d\n", p->c,deep);  
        PreOrder(p->lift,deep+1);//打印左子树  
        PreOrder(p->right,deep+1);//打印又子树  
    }  
    return wpl;  
}  
  
  
int main() {  
    BiTree pnew;//用来指向树的新节点  
    BiTree root=NULL;//这里赋值NULL用于下面的判断  
    //注意，树根不像链表头结点  
    //链表头结点用来指向第一个结点，里面可以不放东西  
    //根就相当于第一个结点，必须有数据  
  
    char c;  
    //队列头、队列尾、指向树的新节点、指向当前队列结点  
    ptag front=NULL,rear=NULL,listpnew=NULL,pcur;  
    while(scanf("%c",&c)){  
        if(c=='\n'){  
            break;  
        }  
        //calloc申请的空间大小是两个参数相乘，并且初始化空间，赋值为Null(左右指针赋值为Null)  
        pnew=(BiTree) calloc(1,sizeof (BiTNode));  
        pnew->c=c;  
        listpnew= (ptag)calloc(1,sizeof(tag));  
        listpnew->p=pnew;  
        //如果是树的第一个结点  
        if(root==NULL){  
            root=pnew;//root指向根结点  
            rear=front=listpnew;  
            pcur=listpnew;//pcur要指向要进入树的父亲元素(当前元素)  
        }else{  
            rear->pnext=listpnew;//入队列  
            rear=listpnew;  
            if(pcur->p->lift==NULL){//左为空，放入左  
                pcur->p->lift=pnew;  
            }else if(pcur->p->right==NULL){//右为空，放入右  
                pcur->p->right=pnew;  
                //此时结点满了  
                //pcur往后移一位  
                pcur=pcur->pnext;  
            }  
        }  
    }  
  
    printf("=================\n");  
    printf("wpl=%d",PreOrder(root,0));  
  
    return 0;  
}

OJ测试

代码实现

#include <stdio.h>  
#include <stdlib.h>  
  
typedef char ElemType;  
//二叉树结构体  
typedef struct TNode{  
    ElemType data;  
    struct TNode *lift;  
    struct TNode *right;  
}TNode,*BiTree;  
//辅助队列结构体  
typedef struct QNode{  
    BiTree p;  
    struct QNode *next;  
}QNode,*Queue;  
  
void PreOreder(BiTree T){  
    if(T!=NULL){  
        printf("%c",T->data);  
        PreOreder(T->lift);  
        PreOreder(T->right);  
    }  
}  
  
int main() {  
  
    ElemType c;  
    BiTree root=NULL;  
    BiTree pnew;  
  
    Queue front=NULL,rear=NULL,listpnew=NULL,pcur=NULL;  
    while(scanf("%c",&c)){  
        if(c=='\n'){  
            break;  
        }  
        pnew=(BiTree) calloc(1,sizeof (TNode));  
        pnew->data=c;  
        listpnew=(Queue) calloc(1, sizeof(QNode));  
        listpnew->p=pnew;  
        if(root==NULL){  
            root=pnew;  
            front=rear=pcur=listpnew;  
        }else{  
            rear->next=listpnew;  
            rear=listpnew;  
            if(pcur->p->lift==NULL){  
                pcur->p->lift=pnew;  
            }else if(pcur->p->right==NULL){  
                pcur->p->right=pnew;  
                pcur=pcur->next;  
            }  
        }  
  
    }  
    PreOreder(root);  
    return 0;  
}

查找算法

顺序表查找原理及实战

#include <stdlib.h>  
#include <stdio.h>  
#include <time.h>  
  
typedef int ELemType;  
typedef struct {  
    ELemType* elem;//整数型指针，申请的对空间起始地址存入elem  
    int TableLen;//存储动态数组里边元素的个数  
}SSTable;  
  
//初始化顺序表  
void st_init(SSTable &ST,int len){  
    //多申请一个位置，是为了存哨兵的，不用哨兵也可以的  
    ST.TableLen=len+1;  
    ST.elem= (ELemType*)malloc(sizeof (ELemType)*ST.TableLen);  
    int i;  
    srand(time(NULL));//随机数生成  
    for(i=1;i<ST.TableLen;i++){//因为第0个放的位置是哨兵，所以从1开始随机  
        ST.elem[i]=rand() % 100;//生成1-99之间的随机数  
    }  
}  
  
void st_print(SSTable ST){  
    int i;  
    for(i=1;i<ST.TableLen;i++){  
        printf("%3d",ST.elem[i]);  
    }  
    printf("\n");  
}  
  
int Search_Seq(SSTable ST,ELemType e){  
    int i;  
    for(i=ST.TableLen-1;ST.elem[i]!=e;--i){  
  
    }  
    return i;  
}  
  
int main() {  
    SSTable ST;  
    st_init(ST,9);  
    st_print(ST);  
    ELemType key;  
    int pos;  
    printf("please input search by\n");  
    scanf("%d",&key);  
    pos=Search_Seq(ST,key);  
    printf("the postion is %d",pos);  
  
    return 0;  
}

二分查找原理及实战

#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
  
typedef int ELemType;  
typedef struct{  
    ELemType* elem;  
    int Tablelen;  
}SSTable;  
  
  
//初始化的方法  
void st_init(SSTable &ST,int len){  
    ST.Tablelen=len;  
    ST.elem=(ELemType*) malloc(sizeof(ELemType)*ST.Tablelen);  
    int i;  
    srand(time(NULL));  
    for(i=0;i<ST.Tablelen;i++){  
        ST.elem[i]=rand() % 100;  
    }  
}  
  
//打印的方法  
void st_print(SSTable ST){  
    int i;  
    for(i=0;i<ST.Tablelen;i++){  
        printf("%3d",ST.elem[i]);  
    }  
    printf("\n");  
}  
  
//二分查找方法  
int binary_search(SSTable ST,int key){  
    int begin=0;  
    int mid;  
    int end=ST.Tablelen-1;  
    while(begin<=end){  
        mid=(begin+end)/2;  
        //注意：是else if 不能写成if，并且三个判断只能执行一个  
        if(key<ST.elem[mid]){  
            end=mid-1;  
        }else if(key>ST.elem[mid]){  
            begin=mid+1;  
        }else{  
            return mid;  
        }  
    }  
    return -1;  
}  
  
//函数名中存储的是函数入口地址，也是一个指针，是函数指针类型  
//qsort规定如果left指针指向的值，大于right指针指向的值,返回正值  
int compare(const void *left,const void *right){//固定形式，照着写就行  
    //要先强转成int类型指针然后取值 比较  
    return *(int*)left-*(int*)right;//从小到大排序  
    //return *(int*)right-*(int*)left;//从小到大排序  
}  
  
int main() {  
    SSTable ST;  
    int key;  
    st_init(ST,10);//初始化  
    st_print(ST);//打印  
    qsort(ST.elem,ST.Tablelen,sizeof (ELemType),compare);//升序排序  
    st_print(ST);//打印  
    int pos;  
    printf("please input the number that you want to search\n");  
    scanf("%d",&key);  
    pos=binary_search(ST,key);  
    if(pos==-1){  
        printf("false,the number is not exit");  
    }else{  
        printf("the pos is %3d",pos);  
    }  
    return 0;  
}

二叉排序树原理及建树

#include <stdio.h>  
#include <stdlib.h>  
  
typedef int ElemType;  
typedef struct BSNode{  
    ElemType key;  
    struct BSNode *lift;  
    struct BSNode *right;  
}BSNode,*BiTree;  
  
  
//二叉树元素插入  
void BST_insert(BiTree &T,ElemType k){  
    if(T==NULL){  
        T= (BiTree)calloc(1,sizeof (BSNode));  
        T->key=k;  
    }  
    BiTree p=T;//p是用来遍历的  
    BiTree parent;  
    while(p){  
        parent=p;//指向p的父节点，以便追加加点  
        if(k==p->key){  
            return;  
        }  
        else if(k<p->key){  
            p=p->lift;  
        }  
        else{  
            p=p->right;  
        }  
    }  
    //开始申请新节点的空间  
    BiTree pnew;  
    pnew=(BiTree) calloc(1,sizeof (BSNode));  
    pnew->key=k;  
    //判断是加在parent结点的左子节点还是右子节点  
    if(k<parent->key){  
        parent->lift=pnew;  
    }else{  
        parent->right=pnew;  
    }//不用判断等于的情况，因为上面遍历树的时候当结点值相等时，该方法就结束了  
}  
  
//创建二叉树  
void creat_bstree(BiTree &T,ElemType str[],int n){  
    T=NULL;  
    int i;  
    for(i=0;i<n;i++){  
        BST_insert(T,str[i]);  
    }  
}  
  
//中序遍历  
void InOrder(BiTree T){  
    if(T!=NULL) {  
        InOrder(T->lift);  
        printf("%3d", T->key);  
        InOrder(T->right);  
    }  
}  
  
int main() {  
    BiTree T;  
    ElemType str[9]={12,34,6,7,3,6,9,0,12};  
    creat_bstree(T,str,9);  
    InOrder(T);  
    return 0;  
}

二叉查找树的删除实战

#include <stdio.h>  //
#include <stdlib.h>  
  
typedef int ElemType;  
  
typedef struct BSNode{  
    ElemType key;  
    struct BSNode *left,*righr;  
}BSNode,*BiTree;  
  
//插入元素的方法  
void BST_insert(BiTree &T,ElemType k){  
    if(T==NULL){  
        T=(BiTree) calloc(1,sizeof (BSNode));  
        T->key=k;  
    }  
    BiTree p=T;  
    BiTree parent;  
    while(p){  
        parent=p;  
        if(k==p->key){  
            return;  
        }else if(k<p->key){  
            p=p->left;  
        }else{  
            p=p->righr;  
        }  
    }  
    //申请要加入元素的新节点空间  
    BiTree pnew;  
    pnew=(BiTree) calloc(1,sizeof (BSNode));  
    pnew->key=k;  
    if(k<parent->key){  
        parent->left=pnew;  
    }else{  
        parent->righr=pnew;  
    }  
}  
  
//创建二叉查找树的方法  
void creat_BSTree(BiTree &T,ElemType str[],int n){  
    T=NULL;  
    int i;  
    for(i=0;i<n;i++){  
        BST_insert(T,str[i]);  
    }  
}  
  
  
  
//中序遍历打印二叉树  
void InOrder(BiTree T){  
    if(T!=NULL){  
        InOrder(T->left);  
        printf("%3d",T->key);  
        InOrder(T->righr);  
    }  
}  
  
//二叉树的查找方法  
BiTree BS_Search(BiTree T,ElemType key){  
    while(T!=NULL&&key!=T->key){  
        if(key<T->key){  
            T=T->left;  
        }else{  
            T=T->righr;  
        }  
    }  
    return T;  
}  
  
//删除二叉排序树元素的方法  
void delete_BSNode(BiTree &root,ElemType x){  
    if(root==NULL){  
        return;  
    }  
    if(x<root->key){  
        delete_BSNode(root->left,x);  
    }else if(x>root->key){  
        delete_BSNode(root->righr,x);  
    }else{//查找到了要删的结点  
        //如果左子树为空，右结点顶上去  
        if(root->left==NULL){  
            BiTree tempNode=root;  
            root=root->righr;  
            free(tempNode);  
            //如果右子树为空，左节点顶上去  
        }else if(root->righr==NULL){  
            BiTree tempNode=root;  
            root=root->left;  
            free(tempNode);  
            //如果左右子树都不为空  
            //1-左子树最大顶上去；2-右子树最下顶上去  
        }else{  
            BiTree p=root->left;//遍历左子树，寻找左子树最大  
            while(p->righr!=NULL){  
                p=p->righr;  
            }  
            root->key=p->key;//将p的值赋给root  
            //然后删除p  
            delete_BSNode(root->left,p->key);  
                //这里得从左子树找，因为root的key也是和p一样  
                //这样可以略过根结点  
        }  
    }  
  
}  
  
int main() {  
  
    BiTree T;  
    ElemType str[8]={13,4,56,7,23,7,95,48};  
    ElemType key;  
  
    creat_BSTree(T,str,8);  
    InOrder(T);  
    ElemType x;  
    printf("\ndelet 23\n");  
  
    delete_BSNode(T,23);  
    InOrder(T);  
    return 0;  
}

OJ测试

#include <stdio.h>  
#include <stdlib.h>  
  
typedef int ElemType;  
typedef struct BSNode{  
    ElemType key;  
    struct BSNode *lift,*right;  
}BSNode,*Bitree;  
  
//插入元素的方法  
void BST_insert(Bitree &T,ElemType k){  
  
    if(T==NULL){  
        T=(Bitree) calloc(1,sizeof (BSNode));  
        T->key=k;  
    }  
    Bitree p;//p用来遍历树  
    p=T;  
    Bitree parent;  
    while(p){  
        parent=p;//用来指向p的父节点  
        if(k==p->key){  
            return;  
        }else if(k<p->key){  
            p=p->lift;  
        }else{  
            p=p->right;  
        }  
    }  
    Bitree pnew;  
    pnew=(Bitree) calloc(1,sizeof(BSNode));  
    pnew->key=k;  
    if(k<parent->key){  
        parent->lift=pnew;  
    }else{  
        parent->right=pnew;  
    }  
  
}  

//创建二叉排序树的方法  
void creat_bstree(Bitree &T,ElemType *str,int n){  
   T=NULL;  
   int i;  
   for(i=0;i<n;i++){  
       BST_insert(T,str[i]);  
   }  
}  
  
//中序遍历二叉树  
ElemType* InOrder(Bitree T){//无法直接返回数组形式，但是可以返回一个数组形式的指针  
    static ElemType str2[10];  
    static int i=0;  
    if(T!=NULL) {  
        InOrder(T->lift);  
        printf("%3d", T->key);  
        str2[i]=T->key;  
        i++;  
        InOrder(T->right);  
    }  
return str2;//返回一个指针  
}  
  
//二分查找的方法 ，返回元素下标 
int binary_search(ElemType str[],int x){  
    int begin=0,mid,end=10;  
    while(begin<=end){  
        mid=(begin+end)/2;  
        if(x==str[mid]){  
            return mid;  
        }  
        else if(x>str[mid]){  
            begin=mid;  
        }else{  
            end=mid;  
        }  
    }  
    return -1;  
}  
  
int main() {  
  
    Bitree root;//定义一个舒更  
    ElemType str[10];  
    int k;//存放输入的数据  
    int i;  
    for(i=0;i<10;i++){  
        scanf("%d",&k);  
        str[i]=k;  
    }  
    creat_bstree(root,str,10);//  
    ElemType *pInt = InOrder(root);//打印，并接收返回的排序后的数组指针  
  
    int pos;  
    pos=binary_search(pInt,6);  
    printf("\n%d",pos);  
  
    return 0;  
}

运行结果

排序算法

排序算法分类

排序算法分为 交换类排序、插入类排序、选择类排序、归并类排序

	交换类排序
			
		冒泡排序
			初冒泡排序,一般靠选择题，考大题几率小
		快速排序
			更重要，考大题
			
	插入类排序
			
		直接插入
			
		折半插入
			
		希尔排序，以上三种插入算法，一般考选择题，考大题概率低
	选择排序
			
		简单选择排序
			
		堆排序(重要)
			很有可能考大题

冒泡排序原理及实战

#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
  
typedef int ElemType;  
//定义顺序表结构体  
typedef struct {  
    ElemType *str;  
    int len;  
}SSTable;  
//顺序表初始化，添加随机数  
void init_table(SSTable &SST,int len){  
    srand(time(NULL));  
    SST.len=len;  
    SST.str=(ElemType*)malloc(sizeof (ElemType)*SST.len);  
    int i;  
    for(i=0;i<SST.len;i++){  
        SST.str[i]=rand()%100;  
    }  
}  
//打印顺序表  
void print_table(SSTable SST){  
    int i;  
    for(i=0;i<SST.len;i++){  
        printf("%3d",SST.str[i]);  
    }  
}  
//交换两个元素的方法  
void swap(ElemType &a,ElemType &b){  
    ElemType temp;  
    temp=a;  
    a=b;  
    b=temp;  
}  
//冒泡排序算法  
void bubble_sort(ElemType arr[],int n){  
    int i,j;  
    bool flag;  //用来标记是否发生了交换
    for(i=0;i<n-1;i++){//外层循环需要比较n-1次  
        flag=false;  
        for(j=n-1;j>i;j--){//内层循环  
            if(arr[j]<arr[j-1]){  
                swap(arr[j],arr[j-1]);  
                flag=true;//有交换就返回true  
            }  
        }  
        if(flag==false){//如果这一趟没有比较，直接结束无须比较  
            return;  
        }  
    }  
}  
  
int main() {  
    SSTable T;  
    int len=9;  
    init_table(T,len);  
    print_table(T);  
  
    printf("\n");  
    bubble_sort(T.str,T.len);  
    print_table(T);  
    return 0;  
}

快速排序原理及实战

一个顺序表
以第一个数为基准
定义两个指针i j
i从左往右找比3大的数，i停止
j从右往左找比3小的数，j停止
然后i j 对应的数完成一次交换，i j 继续前进
循环..直到ij相遇

代码实战

#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
  
typedef int ElemType;  
//定义顺序表结构体  
typedef struct {  
    ElemType *str;  
    int len;  
}SSTable;  
//顺序表添加随机数  
void init_table(SSTable &SST,int len){  
    srand(time(NULL));  
    SST.len=len;  
    SST.str=(ElemType*)malloc(sizeof (ElemType)*SST.len);  
    int i;  
    for(i=0;i<SST.len;i++){  
        SST.str[i]=rand()%100;  
    }  
}  
//打印顺序表  
void print_table(SSTable SST){  
    int i;  
    for(i=0;i<SST.len;i++){  
        printf("%3d",SST.str[i]);  
    }  
}  
  
//分割方法  
int partition(ElemType *str,int low,int high){  
    int temp;//用于存放分割界限数(选取数组第一个数）  
    temp=str[low];//相当于将low位置外一个坑，先让high往前放入元素  
    while(low<high){  
        //右指针用来找比分割数小的数  
        //停了说明找到了  
        while(low<high&&str[high]>=temp){  
            high--;//移动  
        }  
        str[low]=str[high];//将找到的值给str[low],因为这时的str[low]赋给了temp  
        //左指针，用来找比分割数大的数  
        while(low<high&&str[low]<=temp){  
            low++;  
        }  
        str[high]=str[low];  
    }  
    str[low]=temp;//结束时，low位置是空的  
    return low;  
}  
  
//快速排序方法  
void quick_sort(ElemType *str,int low,int high){  
    if(low<high) {//low high用来限定分割的范围  
        int postion = partition(str, low, high);//partition方法是核心方法，是每一次分割的方法  
        quick_sort(str, low, postion - 1);//递归左边的数组  
        quick_sort(str, postion + 1, high);//递归数组右边  
    }  
}  
  
int main() {  
    SSTable T;  
    int len=9;  
    init_table(T,len);  
    print_table(T);  
  
    printf("\n");  
    quick_sort(T.str,0,T.len-1);  
    print_table(T);  
    return 0;  
}

插入排序

//插入排序方法  
void insert_sort(ElemType *str,int n){ //n为数组长度 
    int i,j,temp;  
    for(i=1;i<n;i++){  
        temp=str[i];//暂时存目标元素  
        for(j=i-1;j>=0&&str[j]>temp;j--){//将比插入的数大的全部往后移一格  
            str[j+1]=str[j];  
        }  
        str[j+1]=temp;//j来到了插入位置，将temp插入  
    }  
}

OJ测试

#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
  
typedef int ElemType;  
//定义顺序表结构体  
typedef struct {  
    ElemType *str;  
    int len;  
}SSTable;  
  
//初始化顺序表，手动输入十个数  
void init_table(SSTable &T){  
    int i;  
    int x;  
    T.str=(ElemType*) malloc(sizeof(ElemType)*T.len);  
    for(i=0;i<T.len;i++){  
        scanf("%d",&x);  
        T.str[i]=x;  
    }  
}  
  
//打印顺序表  
void print_table(SSTable SST){  
    int i;  
    for(i=0;i<SST.len;i++){  
        printf("%3d",SST.str[i]);  
    }  
    printf("\n");  
}  
//================================================================================  
//交换的方法  
void swap(int &a,int &b){  
    int temp;  
    temp=a;  
    a=b;  
    b=temp;  
}  
  
//冒泡排序算法  
void bubble_sort(SSTable &T){  
    int i,j;  
    for(i=0;i<T.len-1;i++){  
        for(j=T.len-1;j>i;j--){  
            if(T.str[j]>T.str[j-1]){  
                swap(T.str[j],T.str[j-1]);  
            }  
        }  
    }  
}  
//==============================================================================
//分割方法  
int split(SSTable &T,int low,int high){  
    int temp;  
    temp=T.str[low];  
    while(low<high){  
        while(low<high&&T.str[high]>=temp){  
            high--;  
        }  
        T.str[low]=T.str[high];  
        while(low<high&&T.str[low]<=temp){  
            low++;  
        }  
        T.str[high]=T.str[low];  
    }  
    T.str[low]=temp;  
    return low;  
}  
  
//快速排序法  
void quick_sort(SSTable &T,int low,int high){  
    if(low<high){  
       int pos;  
       pos= split(T,low,high);  
        quick_sort(T,low,pos-1);  
        quick_sort(T,pos+1,high);  
    }  
}  
  
//================================================================================ 
//插入排序方法  
void insert_sort(SSTable &T){  
    int i,j,temp;  
    for(i=1;i<T.len;i++){  
        temp=T.str[i];  
        for(j=i-1;j>=0&&T.str[j]>temp;j--){  
            T.str[j+1]=T.str[j];  
        }  
        T.str[j+1]=temp;  
    }  
}  
  
  
int main() {  
    SSTable SST;  
    SST.len=10;  
    init_table(SST);  
    print_table(SST);  
  
/*  
 * //冒泡排序  
    bubble_sort(SST);    print_table(SST);*/  
  
/*  
    //快速排序  
    quick_sort(SST,0,9);    print_table(SST);*/  
  
    //插入排序  
    insert_sort(SST);  
    print_table(SST);  
    return 0;  
}

选择排序原理及实战

代码

#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
  
typedef int ElemType;  
//定义顺序表结构体  
typedef struct {  
    ElemType *str;  
    int len;  
}SSTable;  
//顺序表初始化，添加随机数  
void init_table(SSTable &SST,int len){  
    srand(time(NULL));  
    SST.len=len;  
    SST.str=(ElemType*)malloc(sizeof (ElemType)*SST.len);  
    int i;  
    for(i=0;i<SST.len;i++){  
        SST.str[i]=rand()%100;  
    }  
}  
//打印顺序表  
void print_table(SSTable SST){  
    int i;  
    for(i=0;i<SST.len;i++){  
        printf("%3d",SST.str[i]);  
    }  
    printf("\n");  
}  
//交换两个元素的方法  
void swap(ElemType &a,ElemType &b){  
    ElemType temp;  
    temp=a;  
    a=b;  
    b=temp;  
}  
  
//选择排序方法  
void select_sort(ElemType *A,int n){  
    int min,i,j;  
    for(i=0;i<n-1;i++){//外循环,i只需要进行n-1轮就可以了  
        min=i;  
        for(j=min+1;j<n;j++){//内循环，j从左到右遍历最小  
            if(A[j]<A[min]){//找到更小的  
                min=j;//交换下标数，意味着j下标表示的数更小，j赋值给min  
            }  
        }  
        swap(A[i],A[min]);  
    }  
}  
  
int main() {  
    SSTable T;//定义顺序表  
    init_table(T,10);//初始化  
    print_table(T);//打印  
  
    select_sort(T.str,10);//选择排序  
    print_table(T);//再次打印，看排序效果  
    return 0;  
}

堆排序原理及实战

1 2	实际上就是一个数组，并不是真正意义的树就是把数组，想象成一个树

若父结点的值恒大于等于子结点的值，则该堆称为最大堆（max heap）。堆中最顶端的那个结点称为根结点（root node），根结点本身没有父结点（parent node）。平时在工作中，我们将最小堆称为小根堆或小顶堆，把最大堆称为大根堆或大顶堆

堆排序步骤：
	堆排序的步骤是首先把堆调整为大根堆，然后我们交换根部元素也就是A[0]，和最后一个元素，这
	样最大的元素就放到了数组最后，接着我们将剩余 9 个元素继续调整为大根堆，然后交换 A[0]和
	9 个元素的最后一个，循环往复，直到有序

代码实现

#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
  
typedef int ElemType;  
//定义顺序表结构体  
typedef struct {  
    ElemType *str;  
    int len;  
}SSTable;  
//顺序表初始化，添加随机数  
void init_table(SSTable &SST,int len){  
    srand(time(NULL));  
    SST.len=len;  
    SST.str=(ElemType*)malloc(sizeof (ElemType)*SST.len);  
    int i;  
    for(i=0;i<SST.len;i++){  
        SST.str[i]=rand()%100;  
    }  
}  
//打印顺序表  
void print_table(SSTable SST){  
    int i;  
    for(i=0;i<SST.len;i++){  
        printf("%3d",SST.str[i]);  
    }  
    printf("\n");  
}  
//交换两个元素的方法  
void swap(ElemType &a,ElemType &b){  
    ElemType temp;  
    temp=a;  
    a=b;  
    b=temp;  
}  
  
//调整单个子树为大根堆的方法  
void adjust_down1(ElemType A[],int k,int len){//k表示父节点位置，开始调整的位置  
    int dad=k;//父节点的下标  
    int son=2*dad+1;//子节点的下标  
    while(son<len){  
        if(son+1<len&&A[son]<A[son+1]){//左节点应该比右结点小,son+1且不能越界  
            son++;  
        }  
        if(A[dad]<A[son]){  
            swap(A[son],A[dad]);  
            dad=son;  
            son=2*dad+1;  
        } else{  
            break;  
        }  
    }  
}  
  
//堆排序的方法  
void heap_sort(ElemType *A,int len){  
    int i;  
    for(i=len/2-1;i>=0;i--){//从最末尾的子树开始一个一个向前调整为大根堆  
        adjust_down1(A,i,len);  
    }  
    swap(A[0],A[len-1]);//交换根结点和尾结点  
    for(i=len-1;i>1;i--){//剩余的数组进入循环  
        adjust_down1(A,0,i);//从根结点开始重新调整为大堆根,此时数组长度变化-1  
        swap(A[0],A[i-1]);//交换根结点  
    }  
}  
int main() {  
    SSTable T;  
    init_table(T,10);  
    print_table(T);  
  
    heap_sort(T.str,10);  
    print_table(T);  
    return 0;  
}

归并排序原理及实战

1
2

归并排序是我们不断进行二分，最终各自剩余 1 个元素，自然有序，然后先将每两个元
素进行合并，变为有序，然后再将两个小组合并，变为有序，循环往复，直到整个数组有序

1	递归到最底部后，开始层层merge，low,high,mid任然对应分组时的位置

merge的时候，需要三个指针,i指向A的有序的前半段，j指向A有序的后半段，k指向放入的数组的当前位置

1、将A[] 元素全部复制放到B[] ，i ,j分别对应low\mid+1起始位置，k=i.

2、i j 先比较，小的放入A[k],i++,j不动，k++

3、直到有剩余，i到头了，j还没到头;或者j到头了，i还没到头。while循环将剩余的全部放入,k随着++

代码如下

#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
  
typedef int ElemType;  
//定义顺序表结构体  
typedef struct {  
    ElemType *str;  
    int len;  
}SSTable;  
//顺序表初始化，添加随机数  
void init_table(SSTable &SST,int len){  
    srand(time(NULL));  
    SST.len=len;  
    SST.str=(ElemType*)malloc(sizeof (ElemType)*SST.len);  
    int i;  
    for(i=0;i<SST.len;i++){  
        SST.str[i]=rand()%100;  
    }  
}  
//打印顺序表  
void print_table(SSTable SST){  
    int i;  
    for(i=0;i<SST.len;i++){  
        printf("%3d",SST.str[i]);  
    }  
    printf("\n");  
}  
//交换两个元素的方法  
void swap(ElemType &a,ElemType &b){  
    ElemType temp;  
    temp=a;  
    a=b;  
    b=temp;  
}  
  
//合并方法  
void merge(ElemType A[],int low,int mid,int high){  
    //用额外的空间存放，避免原数组交换次数过多  
    //static修饰防止递归时，重复加载  
    //因为申请了额外的空间，所以空间复杂度是O(n),n是元素个数  
    static ElemType B[10];  
    int i,j,k;  
    for(k=low;k<=high;k++){//复制元素到B中  
        B[k]=A[k];  
    }  
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++) {//合并两个有序数组  
        if (B[i] <= B[j]) {  
            A[k] = B[i];  
            i++;  
        } else {  
            A[k] = B[j];  
            j++;  
        }  
    }  
    while (i <= mid) {//如果左半边数组有剩余接着放入  
        A[k] = B[i];  
        k++;  
        i++;  
    }  
    while (j <= high) {//如果右半边数组有剩余接着放入  
        A[k] = B[j];  
        k++;  
        j++;  
    }  
  
    }  
  
  
  
//归并排序方法  
void merge_sort(ElemType A[],int low,int high){  
    if(low<high) {  
        int mid = (low + high) / 2;  
        merge_sort(A, low, mid);  
        merge_sort(A, mid+1,high);  
        merge(A,low,mid,high);  
    }  
}  
  
  
int main() {  
    SSTable T;  
    init_table(T,10);  
    print_table(T);  
  
    merge_sort(T.str,0,9);  
    print_table(T);  
    return 0;  
}

MergeSort 函数的递归 次数是 log 2 n， Merge 函数的循环了 n 次， 因此时间复杂度是 O(nlog 2 n)。
归并排序最好、最坏、平均时间复杂度都是 O(nlog 2 n)。
归并排序的空间复杂度是 O(n)，因为使用了数组 B，它的大小与 A 一样，占用 n 个元素的
空间。

单链表的新建查找

链表的实现

链表的删除-插入-查找

实现顺序表 插入 删除

头插法新建链表

尾插法新建链表

链表-按值查找-按位置查找

链表 往第i 个位置插入元素

单链表的删除

单链表删除实战

真题，链表转置实战

OJ测试

栈与队列

栈原理解析

初始化栈-入栈-出栈

队列循环队列原理解析

队列

循环队列

链式队列

循环队列数组实现

队列链表实现-1

队列链表的实现-2

OJ测试

二叉树的建树和遍历

树与二叉树原理解析

树原理解析

二叉树原理

二叉树的层次建树

二叉树的-前中后-序遍历

二叉树的层次遍历

真题-求带权路径长度

OJ测试

查找算法

顺序表查找原理及实战

二分查找原理及实战

二叉排序树原理及建树

二叉查找树的删除实战

OJ测试

排序算法

排序算法分类

冒泡排序原理及实战

快速排序原理及实战

插入排序

OJ测试

选择排序原理及实战

堆排序原理及实战

归并排序原理及实战

所有算法空间时间复杂度

实现顺序表插入删除

链表往第i 个位置插入元素