数据结构和算法

我会带着你远行 2023-06-25 06:24 14阅读 0赞

# 时间复杂度和空间复杂度 #

语句总的执行次数T（n）是关于问题规模n的函数；  
记做T（n）=O（f（n））增长最慢的为最优算法；  
用常数1取代运行时间中的所有加法常数；  
在函数中只保留最高项；  
常数阶；线性阶；平方阶；对数阶；nlogn阶；立方阶；指数阶；

# 线性表 #

是一个序列；

## 抽象数据类型 ##

### Data ###

#### datatype ####

元素的数据类型

### Operation ###

#### initlist ####

#### listempty ####

布尔值

#### clearlist ####

#### getelem ####

给序号返回值

#### locateelem ####

给值返回序号

#### listinsert ####

#### listdelete ####

#### listlength ####

## 顺序结构 ##

在内存中依次存放数据元素;

### 顺序结构封装的三个属性： ###

起始位置；  
最大储存容量；  
当前长度；  
读取的时间复杂度是O（1）；  
插入删除为O（n）

### 优点 ###

1.无需为逻辑关系增加存储空间  
2.快速读取

### 缺点 ###

1.插入和删除复杂  
2.当长度较大时，难以确定储存空间容量  
3.容易造成储存空间“碎片”

## 链式存储结构 ##

用一组任意的存储单元存储线性表的数据元素；  
除了要存储元素信息外，还要存储后继元素的指针；  
存储数据元素信息的域成为数据域；  
把存储位置的域成为指针域；  
此链表的每个节点只储存一个后继元素的指针；，最后一个节点的指针为空null；

# 栈和队列 #

栈：后进先出；  
栈的操作只能在线性表的表尾进行；  
对于栈来说，表尾成为栈的栈顶，表头成为栈底；  
一般用顺序表实现；

队列：只允许一段插入，一端删除；  
一般用链表实现；

# 递归 #

自己调用自己；  
每一个递归必须有一个停止条件，没有条件就像无限for循环一样了；  
迭代使用的循环结构，递归使用的是选择结构；  
递归的逻辑会清晰，但大量的递归调用会占用大量资源（调用阶段）；  
递归有调用和回退阶段，互为逆序；

编写函数使输入的任意长度的字符串反向输出

void print()
    {
        
    	char a;
    	scanf("%c", &a);
    	if (a != '#') # 如果没到最后一个字符#，则一直处于调用自己的状态，当达到停止条件后，回退的时候会反向输出字符串
    		print();
    	if (a = '#')
    		printf("%c" , a);
    }

## 分治思想 ##

汉诺塔

#include <stdio.h>
    
    void move(int n, char x, char y, char z)
    {
        
    	if (1 == n)
    		printf("%c-->%c\n",x,z);
    	else
    	{
        
    	move(n-1,x,y,z);
    	printf("%c-->%c\n",x,z);
    	move(n-1,y,x,z);
    	}
    }
    int main()
    {
        
    	int n;
    	printf("请输出层数：");
    	scanf("%d", &n);
    	move(n,'x','y','z');
    }

八皇后问题

#include <stdio.h>
    
    int count;
    int notDanger(int row, int j, int(*chess)[8])
    {
        
    	int i;
    	for(i=0; i<8; i++)
    	{
        
    		if(*(*chess+i)+j) !=0)
    		{
        
    		flag1 = 1;
    		}
    	}
    	//判断完列还需要左下方左下方
    }
    EightQueen(int row, int n, int (*chess)[8]) # 起始行，列数，指向棋盘每一行的指针
    {
        
    	int chess2[][], i, j;
    	for (i=0; i<8; i++)
    	{
        
    		for (j=0; j<8; j++)
    		{
        
    			chess2[i][j] = chess[i][j];
    		}
    	
    	}
    	if (8 == row)
    	{
        
    	print(count+1);
    	for (i=0; i<8; i++)
    	{
        
    		for (j=0; j<8; j++)
    		{
        
    			printf("%d", *(*(chess2+i)+j));
    		}
    	
    	}
    	else
    	{
        
    	for(j=0; j<n; j++)
    	{
        
    		if(notDanger(row, j , chess))
    		{
        
    			for (i=0; i<0; i++)
    			{
        
    				*(*(chess2+row)+i) = 0;
    			}
    			*(*(chess2+row)+j) = 1;
    			EgihtQueen(row+1, n, chess2)
    		}
    	}
    	}
    	}
    }
    int main()
    {
        
    	int chess[8][8], i, j;
    	for (i=0; i<8; i++)
    	{
        
    		for (j=0; j<8; j++)
    		{
        
    			chess[i][j] = 0;
    		}
    	
    	}
    	EightQueen()
    }

# 字符串 #

比较相等

## BF算法 ##

最朴素的模式匹配算法：一个一个进行比较

## KMP算法 ##

# 树 #

根节点唯一；  
同一层的节点不能相交；  
一个节点只能有一个根节点；  
根节点、内部节点、叶节点（度=0）；  
节点拥有的子树数成为度；  
树的度就是度的最大值；  
孩子、双亲、兄弟、祖先；  
最大层数为深度；  
从左至右为有序的为有序树，否则为无序树；

## 储存结构 ##

### 双亲表示法 ###

每个节点指向它的双亲（维护一个数组）

### 孩子表示法 ###

每个节点指向一个孩子，这个孩子又指向另一个孩子，直到最后空指针为止（维护一个数组和数个链表）