数据结构基础

数据结构 绪论 0、数据

数据就是能够输入计算机中，并被计算机识别、存储、处理、显示的信息

数据是由数据元素组成

数据元素：是数据的基本单位，数据元素有由若干数据项构成，数据项就是数据元素的最小单位，可以用基本数据类型表示信息的一个属性

1、数据结构的定义

数据结构：研究数据与数据之间的逻辑结构，并研究如何在计算机中存储这种有关系和有关系的数据（存储结构），以及对这些有关系的数据进行操作

2、数据之间的关系分类

分类一

线性关系 (排队)

层次关系 (上下级)

网状关系(地铁线路)

3、数据结构研究内容

研究：逻辑结构、存储结构、数据运算

关系-------逻辑结构

逻辑结构是数据之间的抽象关系

四种逻辑结构：集合结构、线性结构、树形结构、图形结构

集合结构

所有数据元素之间没有任何关系，只不过这些数据元素有共同的属性、特点以及同属于一个整体

线性结构

数据元素之间存在先后顺序。最多1个前驱，一个后继

树形结构

数据元素之间是一种层次关系。一个前驱，n个后继

图形结构

数据元素之间存在多个关系。n个前驱、n个后继

存储--------存储结构

数据逻辑结构在计算机中的映射。就是在计算机中存储数据，并表示出这些数据之间关系

顺序存储---------连续内存空间

将数据元素存储在一段连续的空间中，也就是说这些数据在内存中的存储地址是连续的，只需要知道第一个数据元素的地址，就可以知道其他数据元素的地址。例如数组

将数据元素按照逻辑顺序存储在内存中一段连续的空间，利用内存空间的地址来表示先后顺序

链式存储------------数据的存储空间是随机的

数据元素在内存中的存储地址是随机的，不一定是连续的，（所以不需要一次性全部申请空间，根据需要来申请空间）需要通过在存储数据元素的同时，将下一个数据元素的地址一并存上。这样任然能够表示数据元素之间的关系。

链式存储 : 存储数据元素 + 关系

索引存储

在存储数据元素的同时，还要存储数据的索引在一个索引表中，可以通过索引表得到数据元素之间的关系。例如：电话簿

散列存储

通过数元素中的部分关键字，进行某种运算得到该数据元素的地址。

运算--------数据操作

增、删、该、查

算法 算法定义

算法就是解决某个问题的方法步骤

在计算机中算法是一个有限的语句集合

算法与程序的区别

算法就是解决某个问题的方法步骤，程序是在计算机中以计算机语言具体实现

区别：算法不一定要依赖计算机语言，是一种描述方式。程序是必须要依赖计算机语。算法是有限的，程序可以是无穷的。

算法与数据结构

算法设计：依赖于数据结构的逻辑结构

算法的实现：依赖于数据结构的存储结构

程序=数据结构+算法

算法的好坏判断

1. 正确性
2. 效率：消耗时间多少、消耗空间多少
3. 编程：算法结构好、易于、理解、编写、调试

算法的效率度量 时间复杂度

时间计算：

1. 事后统计法

   把算法实现，进行运行，得到算法运行消耗的时间。

   **缺陷：**依赖于特定的计算机软硬件，进行大量的统计

2. 事先估计法

   假设所有计算机执行一条指令的时间都是一致的，只需要统计出执行的语句的次数

   语句频度：算法中一条语句的重复次数

   时间复杂度T(n)：所有语句频度之和就是算法的语句执行次数

   在循环中一条语句，执行次数不确定，就用问题规模n来表示

   通常利用事先估计法来表示算法时间。

计算时间复杂度

1. T(n)表示法：每条语句的语句频度 * 语句条数

2. 大O表示法O(n)：n代表无穷大，并且取T(n)表达式的最高次幂。如果语句执行次数为常数次，那么O(n)=1；

空间复杂度S(N)

占用空间的大小

一、线性表 线性表概念

多个数据元素的逻辑结构为线性关系，这些数据元素之间存在先后顺序，就叫做线性结构，即是线性表。数组就是一个

线性关系：中有且仅有“第一个数据元素”和一个“最后一个数据元素”，中间的数据元素只有一个前驱和一个后继

在存储线性表时，既需要存储具有线性表的数据元素，也需要存储元素数据之间的关系。

总而言之，线性表就是一种逻辑结构为线性结构关系的逻辑结构

线性表的存储结构

线性表的顺序存储：存储数据元素时，把数据元素按照逻辑关系（先后顺序），依次存储在一段连续的内存空间，借助元素在这段连续空间的地址，来表示数据间的先后顺序，这就是顺序结构

顺序表

顺序表 = 数据元素逻辑结构为线性表 + 存储结构为顺序存储。

数组就是一个顺序表

顺序表的运算

1. 添加

2. 删除

3. 修改

4. 查找

5. 判断满

6. 判断空

7. 求表长

8. 创建表

9. 清空表

顺序表的实现

1. 申请一段连续的内存空间来存储数据，通过地址来表示先后关系
2. 记录表中元素的个数

顺序存储的缺陷

1. 要申请一段连续的内存空间，申请的时候大小就已经固定了，空间不能动态的添加、删除，这样比较占用内存资源
2. 插入、删除操作比较麻烦，需要移动整片空间

#include 
#include 
struct array
{
    int num;
    //struct book Book[50];     //表示为申请了50个连续的空间，每个元素为book
    int no[20];                 //定义一个，int类型的数组来存储每一本书的编号    
    
};

//在堆中动态创建结构体，并返回结构体在堆中的首地址
struct array * creat()
{                                  
    struct array * p=malloc(sizeof(struct array));
    if(p==NULL)
    {
        printf("内存空间申请失败!n");
        return NULL;
    }
    p->num=0;    
    return p;
}

//判断结构体空间是否为空
int empty(struct array *p)
{
    if(p->num == 0)
    {
        printf("空间为空n");
        return 1;      //空间为空返回1
    }
    return 0;
}

//判断是否空间是否满了
int full(struct array *p)
{
    if(p->num == 20)
    {
        printf("空间已满n");         //空间如果满了返回1
        return 1;
    }
    return 0;                       //空间如果没满返回0
}

//添加新的元素
void add(struct array * p,int pos,int shu) //传入结构体的首地址和需要添加元素的位置、添加的元素的值
{
    //判断空间是否为满了
    if(full(p))
    {
        return ;            //如果空间满了，那就自接退出，不操作
    }
    
    //判断空间是否为空
    if(empty(p))          //空间为空，那么就将插入的数据添加到no数组第0个元素位置
    {
        p->no[0]=shu;
        p->num ++;
        return  ;
    }
    
    //判断插入下标是否越界
    if(pos > p->num -1 )
    {
        printf("现在有%d个数据，下标范围是0~%dn",p->num,(p->num) -1);
        printf("插入的数据下标为%d超出下标范围,将该数据加在最后一个数据元素后面n",pos);
        putchar('n');
        p->no[p->num]=shu;      //越界了要将数据添加在最后一个元素后面，而不是覆盖最后一个元素p->no[p->num-1]
        p->num ++;
        return ;         //插入元素下标越界，结束添加功能
    }
         for(int i = p->num - 1;i >= pos ;i--)     //将pos处以及之后的元素后一位，空出来给添加的元素
    	{
        	p->no[i+1]=p->no[i];
    	}
        p->no[pos]=shu;
    	p->num ++;
}

//删除执行位置的数据元素
 void del(struct array *p,int pos,int * k)
{
     //判断是否为空
    if(empty(p))
    {
        return ;
    }
    
     //判断下标是否越界
    if(pos >= p->num -1)
    {
        printf("现在有%d个数据，下标范围是0~%dn",p->num,(p->num) -1);
        printf("删除的数据下标为%d超出下标范围，将k的值赋值为0n",pos);
        putchar('n');
        *k=0;
        return ;         //插入元素下标越界，结束添加功能
    }
    
     *k=p->no[pos];
      printf("需要删除下标为%d，数据为%dn",pos,*k);       
    for(int i=pos;i< p->num-1;i++)        //将pos之后的第一个元素赋值给pos的位置，其他元素一次前移一个位置
    {                        //检验判断的条件是，将条件带入到式子中，最后一次前移是，p->nos[num-2]=p->nos[num-1];
        p->no[i]=p->no[i+1];
    }
     printf("删除成功n");
     p->num --;
}

//查找数据元素
void reserch(struct array *p,int pos)
{
    //判断查看的下标是否越界
    if(pos > p->num -1)
    {
        printf("现在有%d个数据，下标范围是0~%dn",p->num,(p->num) -1);
        printf("查看的数据下标为%d超出下标范围，自接退出查找n",pos);
        putchar('n');
        return ;         //插入元素下标越界，结束添加功能
    }
    printf("查看的数据元素是下标为%d的元素数据%dn",pos,p->no[pos]);
}

//修改数据元素
void change(struct array *p,int pos,int shu)
{
    //判断查看的下标是否越界
    if(pos > p->num -1)
    {
        printf("现在有%d个数据，下标范围是0~%dn",p->num,(p->num) -1);
        printf("查看的数据下标为%d超出下标范围，自接退出修改n",pos);
        putchar('n');
        return ;         //插入元素下标越界，结束添加功能
    }
    printf("修改前:%dn",p->no[pos]);
    p->no[pos]=shu;
    printf("修改完成n");
    printf("修改后:%dn",p->no[pos]);
}

//数据显示
void show(struct array *p)
{
    for(int i=0;inum;i++)
    {
        printf("%d  ",p->no[i]);
    }
    putchar('n');
}

int main()
{
    int k=0;
    struct array *p=creat();
    	show(p);
        add(p,10,1);
        add(p,10,2);
    	add(p,10,3);
    	add(p,10,4);
    	add(p,10,5);
    	add(p,10,6);
        show(p);
    	del(p,0,&k);
    	show(p);
    	add(p,4,7);
    	show(p);
    	reserch(p,5);
    	change(p,0,8);
    	show(p);
}

链表

链式存储：是一种不需要连续空间存储数据的数据结构，需要动态存储数据内容和数据之间的先后关系。

总而言之：链表就是一种

链表的概念

链表是一种数据结构，它的逻辑结构为线性表，存储结构为链式存储。数据元素之间的位置是任意的（需要有这个元素才动态申请存储空间），一个数据元素由数据内容+关系组成。其中关系是通过指针来表示，这个指针存储下一个数据元素的地址。

链表 = 线性表 + 链式存储

链表组成

1. 头指针：是一个指针，存储链表中第一个元素的地址，方便指名链表的位置，之后可以通过这个指针来访问其他数据元素。

2. 首元素节点

   真正存储数据的节点

3. 头节点

   在链表，通常会添加一个不存储数据的节点，就是空节点，作为链表的开始节点，真正存储数据的节点是第二个节点。这样的话就可以解决删除和添加数据元素到首节点位置时，要改变头指针指向。加了头节点的话删除首节点就和删除其他节点一样，只需要改变数据元素中的指针的指向。

链表的创建 链表元素的插入和删除位置固定

链表元素的插入和删除都是第一个元素位置。这时就不需要

利用for循环去找插入位置前一个元素的地址。因为for循环的时间赋复杂度为n，字节添加和删除首节点位置数据元素的操作时间复杂度为1

#include 
#include 
#include 

//声明结构体
struct node
{
	char name[20];
	struct node *prior ,* next;
};

//常见链表的头节点
struct node *  create()
{

	struct node * head = malloc(sizeof(struct node));

	if(head == NULL)
	{
		printf("malloc linklist errorn");
		return NULL;
	}

	head->prior = NULL;
	head->next = NULL;

	return head;
}


//添加数据元素
void insert_list(struct node * head,int pos,char * data)
{

	struct node * p = head;
    
    //寻找pos-1的位置地址------------如果选择添加在首节点位置，那么可以不需要写这些
	
    
    struct node * new = malloc(sizeof(struct node ));
	new->next = p->next;
	p->next = new;
	new->prior = p;

	strcpy(new->name,data);

}

//判断是否空间没有存储数据元素
int empty(struct node * head)
{

	if(head->next == NULL)
	{
		printf("is emptyn");
		return 1;
	}
	
	return 0;
}


//删除数据元素
void delete_list(struct node * head,int pos)
{	

	if(empty(head))
	{
		return ;
	}

	struct node * p = head;

	struct node * q = p->next;
	p->next = q->next;
	if(q->next != NULL)
	{
		q->next->prior = p;
	}

	printf("delete data is : %sn",q->name);
	free(q);

}

//修改数据元素------通过查询位置编号
void update_pos_list(struct node * head,int pos ,char * newdata)
{

	struct node * p = head;
	int i = 0;
	while(i < pos)
	{
		p = p->next;
		if(p == NULL)
		{
			printf("error posn");
			return ;
		}
		i++;
	}
	
	strcpy(p->name,newdata);
}

//修改数据元素----------通过查询数据元素内容
void update_data_list(struct node * head,char * data,char * newdata)
{
	

	struct node * p = head;

	while(p->next != NULL)
	{
	
		p = p->next;
		if( strcmp(p->name,data) == 0 )
		{
			strcpy(p->name,newdata);
		}
	}
}

//
void show_list(struct node * head)
{
	struct node * p = head;

	while(p->next != NULL)
	{
		p = p->next;
		printf("%st",p->name);
	}
	printf("n");
}


int main()
{

	struct node * head = create();

	delete_list(head,5);

	insert_list(head,10,"zhangsan");
	insert_list(head,10,"laoliu");
    insert_list(head,1,"wangwu");
    insert_list(head,1,"laozhang"); 
	show_list(head);
	
    delete_list(head,5);
    show_list(head);
    delete_list(head,5);
    show_list(head);
}

#include 
#include 

int m=0;
struct node 
{
    int date;
    struct node * next;
};

struct node * creat()
{
    struct node * p = malloc(sizeof(struct node));
    if(p == NULL)
    {
        printf("申请空间失败n");
        return NULL;      //可以写return head;      吗？
    }
    p->next = NULL;
    return p;
}

void add_list(struct node * head,int pos,int new_date)
{
    struct node * p = head;
    int i=0;
    while(inext != NULL)
    {
        p = p->next;
        i++;
    }
    
    struct node * new = malloc(sizeof(struct node ));
    new->next = p->next;
    p->next = new;
    new->date = new_date;
    m++;
    printf("m=%dn",m);
    return ;
}

void show_list(struct node * head)
{
    if(head->next == NULL)
    {
        printf("没有元素，无法显示n");
        return ;
    }
    
    struct node * p = head->next;
    while(p != NULL)
    {
        printf("%d  ",p->date);
        p = p->next;
    }
    putchar('n');
    return ;
}

//判断空间为空
int empty(struct node * head)
{
    if(head->next == NULL)
    {
        printf("空间为空n");
        return 1;
    }
    return 0;
}
//从小到大排序
void paixu(struct node * head)
{
    if(empty(head))
    {
        return ;
    }
    struct node * p = head->next;
    
    if(p->next == NULL)
    {
        printf("只有一个元素n");
        printf("%dn",p->date);
        return ;
    }
    for(int i=0;i
        for(int j=0;j
            if(p->date > p->next->date)
            {
                int a=0;
                a = p->date;
                p->date = p->next->date;
                p->next->date = a;
            }
            p = p->next;
            //printf("此时p指向的地址里面的值为%dn",p->date);
        }
        p=head->next;
    }
}

int main()
{
    struct node * head = creat();
    show_list(head);
    for(int i=0;i<10;i++)
    {
        int pos = 0,date = 0;
        printf("请输入需要添加的位置和数据n");
        scanf("%d%d",&pos,&date);
        add_list(head,pos,date);
    }
    show_list(head);
    paixu(head);
    show_list(head);
}

循环链表 循环链表的概念

最后一个数据元素指向的地址为头节点的地址

if(p->next == NULL)
{ 
    p->next = head;
}

//判断空
if(head->next == head)
{
    
}

//修改头节点的next和prior指向就行
struct node * creat()
{
    struct node * head = malloc(sizeof(struct node));
	//就不存在指针指向空的情况
	head -> next = head;
	head -> prior = head;
}

//以后在判断最后一个数据元素的时候只需要判断p->next是否为head，不在是判断为NULL

链表和顺序表的优缺点 线性表优点

1. 连续空间存储数据元素，可以通过地址来表示逻辑关系

2. 查看和修改数据元素的时候方便，只需要查看下标就行。

   //例如查看下标为pos这个元素
   
   p->nos[pos]，(前提是pos< p->num-1);
   
   //修改下标为pos这个元素
   
   p->nos[pos] = date;
   

线性表的缺点

1. 增加和删除元素，时间复杂度很高，O(n)。原因：
   1. 1 添加一个元素到pos这个位置，需要利用循环，从p->nos[p->num-1] 这个元素开始，直到p->nos[p->pos]为止，将每一个元素向后移动一位才行。
   2. 1同理删除pos这个位置的元素，需要利用循环，从p->nos[p->pos+1]这个元素开始，到p->nos[p->num-1]这个元素为止，将每一个元素向前移动一位

链表的优点

1. 添加和删除元素方便，时间复杂度为O(1)

   //添加一个元素------------默认是头插法，就是每次都是从头结点之后插入元素
   struct node * p = head;
   new->next = p->next;
   p->next = new;
   
   //删除一个元素----------头删法
   struct node * p = head;
   struct node *q = p->next;
   p->next = q->next;
   
   

2. 动态申请空间，不需要空间连续，元素多少可以随时变化，要多少空间就开辟多少空间

链表的缺点

1. 修改和查询元素时间复杂度O(n)。需要利用循环从头开始取寻找需要修改或者查询的位置。

   //修改元素
   struct node * p = head;
   while(p->next !=  NULL)
   {
       p=p->next;
       p->date = new_date;
   }
   

二、栈与队列 栈的概念

栈就是一个只允许固定位置操作的线性表，允许操作的一端叫做栈顶，不允许操作的一端叫做栈底。遵循先进后出的原则。

每当操作(删除或者插入)一个栈顶元素，就会有一个新的栈顶元素。

顺序栈

逻辑结构： 栈

存储结构：顺序存储

顺序栈的概念

开辟一个连续的内存空间，规定一端为不可操作的栈底，将栈顶指向栈底的位置，这样添加数据元素的时候任然满足在栈顶操作，之后每添加一个元素，栈顶就加一，始终保持栈顶指向下一个将要添加的位置。如果想要删除操作，那么只需要将栈顶减1，因为此时的栈顶是指向下一个将要添加元素的位置，而且在栈顶减1后，栈顶指向被删除的元素的地址，下一次如果是添加元素，那么就会添加在当前栈顶的位置，也就是要被删除的元素的地址，这样添加的元素就会覆盖掉之前的要被删除的元素；如果是删除元素，任然需要先将栈顶地址减1，此时栈顶位置已经变了，不会在指向上一次要删除的元素的地址。

#include 
#include 

struct node 
{
  	int date[10];
    int top;          //这里是声明一个栈顶指针top,由于数组名加上下标(date+top)就是元素地址，所以没有用int * top的形式
};

//创建一个空栈，里面可以存10个int类型的数
struct node * creat()
{
    struct node * p = (struct node *)malloc(sizeof(struct node));
    p->top = 0;
    return p;
}

int full(struct node *p)
{
    if(p->top ==(sizeof(p->date) / sizeof(int)))
    {
        printf("栈空间已满n");
        return 1;
    }
    return 0;
}

//判断栈是否为空
int empty(struct node *p)
{
    if(p->top == 0)
    {
        printf("栈空间为空n");
        return 1;
    }
    return 0;
}
//从栈顶添加元素
void add_stack(struct node * p,int date)
{
    if(full(p))
    {
        return ;
    }
    p->date[p->top] = date;
    p->top ++;
}

//从栈顶出栈
void pop_stack(struct node * p)
{
    if(empty(p))
    {
        return ;
    }
    
    p->top --;
    printf("需要删除的元素为%dn",p->date[p->top]);
}

//显示栈顶
void show_top(struct node *p)
{
    printf("栈顶存放的元素是:%dn",p->date[p->top -1]);
    return ;
}

//遍历栈中所有元素
void show_stack(struct node * p)
{
    int i = p->top -1;
    while(i >= 0)
    {
        printf("%d  ",p->date[i]);
        i--;
    }
    putchar('n');
}

int main()
{
    struct node * p = creat();
    add_stack(p,10);
    add_stack(p,20);
    add_stack(p,30);
    add_stack(p,40);
    add_stack(p,50);
    show_top(p);
    show_stack(p);
    pop_stack(p);
    show_stack(p);
    
}

链式栈

链式栈的逻辑结构为：栈

存储结构为：链式存储

链式栈的栈顶在头节点之后的第一个元素位置，也就是head ->next

#include 
#include 
#include 

//声明结构体
struct node
{
    int date;
    struct node * next;
};

//创建空栈------头节点
struct node * creat()
{
    struct node * head = (struct node * )malloc(sizeof(struct node));
    if(head == NULL)
    {
        printf("空间申请失败n");
        return NULL;
    }
    head->next = NULL;
    return head;
}

//在栈顶添加元素-------------就是在head->next 指向的地址处进行操作
void add_stack(struct node * head,int date)
{
    struct node * new = (struct node *)malloc(sizeof(struct node));
    new->next = head->next;
    head->next = new;
    new->date = date;
}

//判断栈空间是否为空
int empty(struct node *head)
{
    if(head->next == NULL)
    {
        printf("栈空间为空，无法删除n");
        return 1;
    }
    return 0;
}
//删除元素
void pop_stack(struct node * head)
{
    if(empty(head))
    {
        return ;
    }
    
    struct node * q = head->next;
    head->next = q->next;
    free(q);
}

//遍历栈空间元素
void show_stack(struct node * head)
{
    struct node * p = head->next;
    while(p->next != NULL)
    {
        printf("%d  ",p->date);
        p = p->next;
    }
    putchar('n');
}


int main()
{
    struct node *head = creat();
    pop_stack(head);
    add_stack(head,10);
    add_stack(head,20);
    add_stack(head,30);
    add_stack(head,40);
    add_stack(head,50);
    
    show_stack(head);
    pop_stack(head);
    show_stack(head);
}

判断括号匹配问题 -------方式一：利用链式栈

#include 
#include 

struct node 
{
    char date;
    struct node *next;
};

int main()
{
    char str[10];
    int i=0;
    int num=0;
    printf("请输入:n");
    scanf("%s",str);
    printf("输入的结果%sn",str);
     while(str[i] != '')
    {
            if(str[i]!='[' || str[i]!='(' || str[i]!='<' || str[i]!='{'  )
        {
            num ++;
        }
        if(str[i]!=']' || str[i]!='}' || str[i]!='>' || str[i]!=')')
        {
            num ++;
        }
         i++;
    }
    if(num!= 0)
    {
         printf("不匹配n");
        return 0;
    }
    struct node * p = malloc(sizeof(struct node ));
    p->next = NULL;
   
    for(int i = 0;i < str[i] != '';i++ )
    {
    if(str[i] == '[' || str[i] == '{' || str[i] == '<' || str[i] =='(')
    {
        struct node *new = malloc(sizeof(struct node));
        new->next = p->next ;
        p->next = new;
        new->date = str[i];
        printf("添加%cn",new->date);
        continue;
    }
    else if(str[i] -1 != p->next->date  && str[i] -2 != p->next->date  )
    {
        printf("不匹配n");
        //printf("栈顶的元素%cn",p->next->date);
        break;
    }else if(p->next->date == '{' && str[i] == '}')         //配对{}
    {
        struct node * q = p->next;
        p->next = q->next;
        printf("%c出栈n",q->date);
        free(q);
        if(p->next == NULL)
        {
            printf("元素全部出栈，匹配成功n");
            break;
        }
        continue;
    }  //匹对[]
        else if(p->next->date == '[' && str[i] == ']')
    {
        struct node * q = p->next;
        p->next = q->next;
        printf("%c出栈n",q->date);
        free(q);
        if(p->next == NULL)
        {
            printf("元素全部出栈，匹配成功n");
            break;
        }
        continue;
    }       //匹对()
        else if(p->next->date == '(' && str[i] == ')')
    {
        struct node * q = p->next;
        p->next = q->next;
        printf("%c出栈n",q->date);
        free(q);
        if(p->next == NULL)
        {
            printf("元素全部出栈，匹配成功n");
            break;
        }
        continue;
    }
        //匹对<>
        else if(p->next->date == '<' && str[i] == '>')
    {
        struct node * q = p->next;
        p->next = q->next;
        printf("%c出栈n",q->date);
        free(q);
        if(p->next == NULL)
        {
            printf("元素全部出栈，匹配成功n");
            break;
        }
        continue;
    }
 
    }
}

判断括号匹配问题 -------方式二：利用顺序栈

#include 
#include 
struct stack
{
    int top;
    char str[10];
};

int main()
{
    char ch[10] ;
    struct stack * p = malloc(sizeof(struct stack));
    p->top = 0;
    printf("输入符号n");
    scanf("%s",p->str);
    
    for(int i=0;ch[i] != '';i++)
    {
    if(p->str[p->top]!= ']' && p->str[p->top] != '}' && p->str[p->top] != ')' && p->str[p->top] != '>')
    {
        p->str[p->top] = ch[i];
        p->top ++;
            
    }else
    {
        p->top --;
        if(ch[i]-1 != p->str[p->top] && ch[i]-2 != p->str[p->top])
        {
            printf("不匹配n");
            break;
        }
    }
    
    }
    
}

入栈出栈顺序

只能对栈顶进行操作。一组数据按照顺序入栈，但是出栈可以随时，就是说还有其他数据没有入栈，在栈中的数据就可以出栈。出栈n个数据之后继续入栈其他元素，中途又可以出栈。这样的话，最终出栈得到的元素序列就不定

队列

一种特殊的线性表，只允许在线性表两端进行操作，插入端称为队尾，删除端叫做队头。满足先进先出原则

链队列

逻辑结构为队列(线性表)

存储结构为链式存储--------------插入端称为队尾，删除端叫做队头。有一个对头指针和一个队尾指针，对头指针指向头节点，队尾指针指向需要添加的元素的前一个元素的地址。

在空链队列是，对头和队尾指针都指向头节点。之后每 添加一个元素都需要将队尾指针指向新添加的元素的地址。

三、树的基本操作 树相关的概念

树是一种描述数据和数据之间的关系、存储、运算的数据结构。是节点数大于等于0的有限节点的集合，树只有一个根节点，其他的节点被分为互不相交的有限个集合，这些集合本身也是一颗树，这些树都是根的子树。

树描述的关系是一种层次关系，或者叫做从属关系

树有层次，最大的层叫做树的层

结点的子结点叫做该节点的度，整个树中最大的节点的度叫做树的度，度为0的节点叫做终端节点

每一个节点最多只有两个子节点的树

树中的每个元素都叫做结点

结点的度：一个结点包含的子树的个数

叶子结点（终端结点）：度为0的结点

子结点：结点有度，有子树，子树的根节点就是这个结点子结点父结点

兄弟结点：同属于一个父结点

树的度：在树中，最大结点的度，称为整棵树的度

结点的层次：从整棵树的根结点开始，叫做第一层，根的子结点就是第二层，依次加1

树的深度：树中结点层次最大的叫做树的深度

路径：从一个结点到另一个结点，经过的位置叫做路径

路径的边：

路径长度：经过的边的条数叫做路径长度

有序树：（兄弟结点不能交换顺序）根结点的子树不能交换

顺序树：就是一种一对多的关系，结点只有一个前驱，可以有多个后继

树的存储

链式存储：设计每个结点按照树的度设计指针空间（关系），来存储下一层的子结点的地址

二叉树的概念

对于树而言，存储过于繁琐，操作过于复杂，所以想设计一种简单的树来进行表示操作存储。只需要把普通的树转换为这种简单的二叉树就可以了。

二叉树树中的每个结点最多只有两个子树（两个子结点），且严格区分左右子树，不能交换

1. 二叉树的第i层，最多有2^(i-1)个结点

2. 深度为k的二叉树，最多有2^k - 1 个结点

3. 对于二叉树，叶子结点数n0，度为二的结点数n2，n2 = n0 - 1

4. 满二叉树：每层都是2^(i-1)个结点，每层都是最多结点

5. 完全二叉树：如果有k层，从第一层到k-1层，每一场都是2^(k-1)，第k层，一定是从左至右每个位置都有结点（不一定满）,也不一定是必须一左一右两个终端节点，也可以是一个左，但是这个节点就没有兄弟节点了，因为已经空了右节点。

二叉树的存储

在二叉树中，从下标为1开始存储，根结点存储下标为1位置，

当前结点的左孩子存储 2 * i(i就是结点的下标)，

结点右孩子存储在 2 * i + 1位置

父节点：当前结点的位置 / 2 ，就是父结点的位置

如果i从0开始，那么

当前结点的左孩子存储 2 * （i+1）-1==2i+1(i就是结点的下标)，

结点右孩子存储在 2 * (i + 1) +1 -1 == 2i +2位置

父节点：当前结点的位置 / 2 ，就是父结点的位置

二叉树的遍历

1. 顺序栈遍历：先将根节点遍历根节点（根节点出栈），把它左节点入栈，然后右节点入栈，之后右节点处于栈顶，先对器进行出栈，同理将有节点的左右子节点入栈，然后遍历右子节点（出栈），后续同上操作。直到所有节点全部遍历完（出栈）。
2. **顺序队列遍历（层次遍历）：**先遍历根节点（根节点出栈），
3. 先序遍历：根------左子树---------右子树
4. 中序遍历：左子树----根-----右子树
5. 后序遍历：左子树-------右子树------根

利用先序+中序 或者后序+中序的方式可以还原二叉树结构，得到另外一个遍历顺序的结果

具体方法是：

1. 利用先序的第一个元素就是根节点，找到根节点。
2. 然后再中序中判断其余元素是根的左子树还是由子树成员
3. 继续看先序中的下一个元素，并在中序中找到该元素，然后以它为根，利用左–根–右的顺序判断该元素两边的元素在该元素的左边还是右边
4. 继续看先序中的下一个元素，，并在中序中找到该元素，然后以它为根，利用左–根–右的顺序判断该元素两边的元素在该元素的左边还是右边
5. 直到全部元素遍历完

哈夫曼树

在树中，权值（比重）大的数据放在二叉树的最上层，权值小的放在二叉树的最下层。

带权路径长度：节点的权值 * 根节点到该节点的边数

带权路径长度就可以反应某个节点访问的难以程度

所有要访问的数据都是叶子节点（就是度为0的节点），其余节点就是这个树所占的权重。

四、图的概念 图的存储

邻接矩阵
邻接链表

五、查找、排序算法 计数排序

计数排序：利用待排序元素中最大的元素的值m，来创建一个m+1这么大的一个数组b，然后按顺序将待排序的元素的值，当做b数组的下标，找到该下标对应的元素，对其加1。如果在待排序元素中一个数出现n次，那么就需要将b数组中该元素值为下标的数加n。待排序元素中没有的数，在数组b中就是0；所有带排序元素都遍历完后，将数组b遍历。利用for循环判断条件是b[ i ] != 0,就打印下标 i， 之后b[ i ] - - ，直到不满足条件

#include 

int main()
{
    int a[5] = {4,2,6,4,90};
    int max=0;
    for(int i = 0; i< sizeof(a) / sizeof(int) ;i++)
    {
        if(a[i] > max)
        {
            max = a[i];
        }
    }
    printf("max=%dn",max);
    int n=max+1;
    int b[n];
    bzero(b,n*4);           //关键之处，不能将int b[n];写成int b[n]就不管了，因为此时数组大小是个未知数，这种定义方式无异于int b[];这种方式，都是不允许的。需要利用bzero()函数加数组中的所有元素都赋值为0
    
    for(int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        if(a[i] >= 0)
        {
            b[a[i]]++;
        }
    }
    
    for(int i = 0; i
		while(b[i] != 0)
        {
            printf("%d ",i);
            b[i]--;
        }
    }
    putchar('n');
}

选择排序

一种与冒泡排序很像的排序。他是将第一个元素和该元素之后的每一个元素进行比较，如果被比较的元素大于(小于)比较的元素，那么就交换值的大小，之后被比较元素继续用新的值和之后的元素比较，直到它和所有元素都比完。此时被比较元素一定是所有比较元素中最小的。之后利用该方法，取出第二个元素，然它和它之后的每一一个元素比较，方法一样。

和冒泡拍序不同之处在于，里层循环的条件是从i+1开始，小于带比较元素的个数

#include 

int main()
{
    int a[5] = {1,4,6,3,7};
    for(int i = 0; i < sizeof(a)/sizeof(int ) - 1; i++)
    {
        for(int j = i+1; j
            if(a[i] > a[j])
            {
                int b = a[i];
                a[i] = a[j];
                a[j] = b;
            }
        }
    }
    
    for(int i = 0;i < sizeof(a) / sizeof(int);i++)
    {
        printf("%d ",a[i]);
    }
    putchar('n');
}

冒泡排序

从第零个元素开始，将前一个元素和它后面一个元素进行比较，如果前一个元素大于后一个元素，那么交换位置（交换值），依次类推，直到倒数第二个元素和倒数第一个元素比较完，此时最后一个元素一定是所有元素中最大的。之后在进行第二轮，从第零个元素开始，前一个元素和它后面一个元素进行比较，如果前一个元素大于后一个元素，那么交换位置（交换值），依次类推，直到倒数第二个元素和倒数第一个元素比较完（为了减小时间复杂度，需要减i

），此时最后一个元素一定是所有元素中最大的

#include 

int main()
{
    int a[5] = {2,6,3,5,1};
    for(int i =0;i
        for(int j = 0;j < sizeof(a) / sizeof(int) -1 -i; j++)       
        {
            if(a[j] > a[j+1])
            {
                int b = a[j];
                a[j] = a[j+1];
                a[j+1] = b;
            }
        }
    }
    for(int i = 0; i < sizeof(a) / sizeof(int) ; i++)
    {
        printf("%d ",a[i]);
    }
    putchar('n');
}

插入排序

#include 

int main()
{
    int a[5] = {2,1,4,23,5};
    for(int i = 1;i < sizeof(a) / sizeof(int );i++)
    {
        int temp = a[i];
        int j = i;
        while(j >0)
        {
            if(a[j-1] > temp)
            {
                a[j] = a[j-1];
            }else
            {
                break;
            }
            j--;
        }
        a[j] = temp;
    }
    for(int i=0 ; i
        printf("%d ",a[i]);
    }
    putchar('n');
}

折半查找

#include 

int main()
{
    int a[10] = {1,4,6,2,7,3,8,4,5,3};
    int i = 0,j = 9;
    int mid = (i + j) / 2;
    int num =0;
    scanf("%d",&num);
    
    while(i <= j)
    {
        if(num == a[mid])
        {
            printf("找到，位置为%dn",mid);
            break;
        }
        else if(num > a[mid])
        {
            i = mid +1;
        }else
        {
            j = mid -1;
        }
        mid = (i + j) / 2;
    }
}