前言

写这篇文章的目的呢，主要是当做笔记了，现在都已经大二了数据结构与算法还是比较薄弱，感觉都不能叫菜了(哭，所以就写一篇相当于知识体系的博客吧，内容非常的基础，没什么亮点，~~也没什么看的价值~~。

首先我们理一理这个数据结构，从大一开始我们就知道什么栈啊表啊什么的，那在这我们做一个简单的总结吧，简单数据结构首先可以分为表栈队树图，当然我知道这么分很垃，但是总体上大概可以看成这几类，那我们就一种一种来看。

表

首先看表，表这种数据结构很直观，先进先出，也很好理解，这里就记录一下各种不同的表以及实现方式。

顺序表

首先我们先分配出一个数据结构

#define  Maxsize 100  //最大空间
typedef struct{//typedef的作用是把这个结构体等价于类型名SqList
	ElemType *elem;//自定义数据类型，动态分配方式
//  ElemType data[Maxsize]//静态分配方式  
	int length; // 顺序表的长度
}SqList;

顺序表的存储方式如下，它的特点是只要索引正确，可以立即找到相对应的数值，对比有指针的那位….另外，第i个元素的值为L,elem[i-1]，这个细节留意一下。

bool InitList(SqList &L) //构造一个空的顺序表L
{   //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效
//不加&内部改变，跳出函数后无效
    L.elem=new int[Maxsize];    //为顺序表分配Maxsize个空间
    if(!L.elem) return false;      //存储分配失败
    L.length=0;				//空表长度为0
    return true;
}

def __init__(self,size):  # initialization
    self.max=size        #表的最大值
    self.data=[None]*self.max #表的值
    self.num=0  #当前该顺序表的长度，空表为0

插，删，找

任何一个数据结构都会具备基本的增删改查功能，取值和查找基本相同就不赘述了，这里讲讲插入和删除，首先在顺序表中第i个位置之前插入一个元素e，需要从最后一个元素开始，后移一位，…，直到把第i个元素也后移一位，然后把e放入第i个位置。

bool ListInsert_Sq(SqList &L,int i,int e)
{
	if(i<1||i>L.length+1) return false;	 //i值不合法
	if(L.length==Maxsize) return false; //存储空间已满
	for(int j=L.length-1;j>=i-1;j--)
	    L.elem[j+1]=L.elem[j];   //从最后一个元素开始后移，直到第i个元素后移
	L.elem[i-1]=e;              //将新元素e放入第i个位置
	L.length++;		     	//表长增1
	return true;
}

def addnum(self,value,index):
    if index>self.max-1 or index<0:
        return False
    i=self.num
    while i>=index:
        self.data[i]=self.data[i-1]
        i-=1
    self.data[index-1]=value

而在顺序表中删除第i个元素，需要把该元素暂存到变量e，然后从i+1个元素开始前移，…，直到把第n个元素也前移一位，即可完成删除操作。

bool ListDelete_Sq(SqList &L,int i,int &e)
{
	if((i<1)||(i>L.length)) return false;	 //i值不合法
	e=L.elem[i-1];   //将欲删除的元素保留在e中
	for (int j=i;j<=L.length-1;j++)
		L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
	L.length--; //表长减1
	return true;
}

def deletenum(self,index):
    if index>self.max or index<1:#判断是否合法
        return False
    self.data[index-1]=None #删除元素
    for i in range(index,self.max):# 依次移动
        self.data[i-1]=self.data[i]
    self.data[self.num]=None #最后一个数字要变为None

链表

链表呢就是有指针的表了，它像链条一样链接起各个元素，特点是插入和删除数据十分方便，但是寻找和读取数据能力欠佳。

单链表

单链表的图示图下：

每一个单独结构可以分成两部分，数据部分和指针部分（也有表达为数据域和指针域的），

首先定义结构以及初始化，初始化的步骤呢就是先无中生有一个头节点，将他的指针域指向空即可。

typedef struct Lnode
{
	int data; //结点的数据域
	struct LNode *next; //结点的指针域
}Lnode, *Linklist//LinkList为指向结构体LNode的指针类型
    
bool InitList_L(LinkList &L)//构造一个空的单链表L
{
    L=new LNode;     //生成新结点作为头结点，用头指针L指向头结点
	if(!L)
      return false;  //生成结点失败
	L->next=NULL;   //头结点的指针域置空
	return true;
}

创建单链表

修改指针的顺序原则：先修改没有指针标记的那一端。

头（前）插法

这个呢代表着新的结构体是从头节点后面插入的，且每次插入都是从头节点插入，所以依次插入之后呢，结果会和插入的顺序相反，比如输入的序列是：1，2，3，4，那么实际生成的单链表是4->3->2->1。这里注意头节点是没有数据的噢~

void CreateList_H(LinkList &L)//前插法创建单链表
{
	int n;
	LinkList s; //定义一个指针变量
	L=new LNode;//新建头节点
	L->next=NULL; //先建立一个带头结点的空链表
	cin>>n;//n表示元素数量
	while(n--)
    {
		s=new LNode; //生成新结点s
		cin>>s->data; //输入元素值赋给新结点的数据域
		s->next=L->next;//先修改没有标记的一端（指没有头指针标记）
		L->next=s; //将新结点s插入到头结点之后
	}
}

尾插法

尾插法就是指每次插入都从最后一个结构后面插入，插入完毕后修改尾指针指向。

void CreateList_R(LinkList &L)//尾插法创建单链表
{
	int n;
	LinkList s, r;
	L=new LNode;
	L->next=NULL; //先建立一个带头结点的空链表
	r=L; //尾指针r指向头结点
	cin>>n;
	while(n--)
    {
		s=new LNode;//生成新结点
		cin>>s->data; //输入元素值赋给新结点的数据域
		s->next=NULL;
		r->next=s;//将新结点s插入尾结点*r之后
		r=s;//r指向新的尾结点s
	}
}

取值，查找

单链表的取值不可以像顺序表一样直接找到任意一个元素，它只能从第一个节点开始往后依次找，一直找到第n个节点。而查找的话，可以定义一个p指针指向第一个元素节点并比较节点的数据域是否等于value。

bool GetElem_L(LinkList L,int i,int &e)//单链表的取值
{
	//在带头结点的单链表L中查找第i个元素
	//用e记录L中第i个数据元素的值
	int j;
	LinkList p;
	p=L->next;//p指向第一个结点，
	j=1; //j为计数器
	while(j<i&&p) //顺链域向后扫描，直到p指向第i个元素或p为空
    {
		p=p->next; //p指向下一个结点
		j++; //计数器j相应加1
	}
	if(!p||j>i)
		return false; //i值不合法i＞n或i<=0
	e=p->data; //取第i个结点的数据域
	return true;
}
bool LocateElem_L(LinkList L, int e) //按值查找
{
	LinkList p;	//在带头结点的单链表L中查找值为e的元素
	p=L->next;
	while(p&&p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
		p=p->next; //p指向下一个结点
	if(!p)
        return false; //查找失败p为NULL
    return true;
}

树

二叉树，树，森林间的转换

树转二叉树

树所有相邻兄弟节点之间加虚线
树中每个节点只保留与长子（左孩子）的连线，删除与其他孩子的连线
以跟节点为轴心，整棵树顺时针转45°。

森林转二叉树

每棵树转二叉树
第一棵二叉树不动，第二棵树开始，依次把后一棵二叉树的根节点作为前一棵二叉树根节点的右孩子节点，直到所有二叉树连接在一起

二叉树还原成树

若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子等都与该结点的双亲结点用连线连起来
删除原二叉树中所有双亲结点与右孩子结点之间的连线
整理

二叉树还原成森林

切开根节点右链上所有“双亲-右孩子”的关系，分为若干二叉树
将这些二叉树还原为树

图

图分为节点结构和图结构，节点结构包括一条边的起点，终点和边的权重，图结构包括整个图的边数，节点数以及节点的集合。

typedef struct Node{
	char a,b;//起点和终点
	int w;//权
}Node;

typedef struct{
	int len,n;//长度和顶点个数
	Node *list;//节点集合
}Graph;

初始化和构建图

int initList(Graph &G){
	G.len=0;
	G.list=new Node[MAX];
	return 0;
}

int GetList(Graph &G)
{
	cin>>G.len>>G.n;
	for(int i=0;i<G.n;i++)
		cin>>node[i];//这一步是输入节点名称，需全局定义一个字符数组。
	G.list[0].w=0;
	for(int i=0;i<G.len;i++)
		cin>>G.list[i].a>>G.list[i].b>>G.list[i].w;
	return 0;
}