数据结构 纯千干千干货 总结!

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define OK 1
#define ERROR 0
 
typedef struct Node
{
	int data;
	struct Node* next;
} Node, *LinkList;
/*
创建循环链表
*/
int CreatCircleList(Node** circle_list,int n)
{
	
	printf("请输入%d个不同的数字：",n);
	int i = 0;
	//创建头结点
	Node* head = (Node*)malloc(sizeof(Node));
	Node* temp = head;//temp 移动指针，刚开始指向头结点
	while (i < n)
	{
		int data=0;
		scanf("%d",&data);
		//创建结点并初始化数据
		Node* node = (Node*)malloc(sizeof(Node));
		node->data = data;
		node->next = NULL;
		//将结点添加到循环链表中
		temp->next = node;
		temp = node;
 
		i++;
	}
	//循环结束 temp指向最后一个结点,让其指向第一个结点，形参循环列表
	temp->next = head->next;
	//循环链表指向第一个结点
	*circle_list = head->next;
	//释放头结点
	free(head);
	return OK;
 
}
//获取循环链表长度
int LengthCircleList(Node* circle_list)
{
	if (circle_list == NULL)
	{
		return 0;
	}
	int i = 1;
	Node* node = circle_list;//node为移动指针，node 开始指向循环链表第一个结点
	//循环链表遍历完判断，尾结点的指针域指向第一个结点
	while (node->next != circle_list)
	{
		node = node->next;
		i++;
	}
	return i;
}
/*
显示拉丁方阵
*/
int ShowLatin(Node* latin_list)
{
	int len = LengthCircleList(latin_list);
	Node* first = latin_list;
	for (size_t i = 0; i < len; i++)
	{
		Node* node = first;
		int j = 0;
		/*
		找到开始结点
		第一行 开始结点为 循环链表第1个位置结点
		第二行 开始结点为 循环链表第2个位置结点
		第N 行 开始结点为 循环链表第n个位置结点
		*/
		while(j < i)
		{
			node = node->next;
			j++;
		}
		Node * begin = node;
		int k = 0;
		//遍历完这个循环列表
		while(k<len)
		{
			printf("%d\t",begin->data); 
			begin = begin->next;
			k++;
		}
		printf("\n");
		
	}
 
	return OK;
}
//销毁链表释放内存
int DestroyCricleList(Node* circle_list)
{
	if (circle_list == NULL)
	{
		return ERROR;
	}
	Node* node = circle_list;//node为移动指针，node 开始指向循环链表第一个结点
	//循环链表遍历完判断，尾结点的指针域指向第一个结点
	while (node->next!= circle_list)
	{
		Node* temp = node;
		node = node->next;
		free(temp);
	}
	//释放最后一个结点
	free(node);
	return OK;
}
 
 
int main(int argc, char *argv[])
{
	Node* circle_list = NULL;
	while (1)
	{
		printf("请输入拉丁方阵的阶数(0退出)：");
		int n = 0;
		scanf("%d", &n);
		if (n == 0)
		{
			break;
		}
		CreatCircleList(&circle_list,n);
		ShowLatin(circle_list);
		DestroyCricleList(circle_list);
	}
	circle_list = NULL;
	return 0;
}

#include <stdio.h>
#include <malloc.h>
#define MAX 31 
int visited[MAX]; 

typedef struct ArcNode
{ 
	int adjvex;      //该弧指向的顶点的位置
	struct ArcNode *nextarc;  //指向下一条弧的指针
}ArcNode; 

typedef struct VNode
{ 
	char data;      //顶点信息
	struct ArcNode *firstarc;  //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX]; 

typedef struct 
{ 
	AdjList adjlist;
	int vexnum, arcnum;    //图的当前顶点数和弧数
}ALGraph; 


void CreateDG(ALGraph *G);   //创建邻接表
void DispAdj(ALGraph *G);   //输出邻接表
void DFS(ALGraph *G, int v);  //深度优先遍历
void BFS(ALGraph *G, int v);  //广度优先遍历

void CreateDG(ALGraph *G)
{ 
	int i, k, j, v1, v2; 
	ArcNode *p;
	printf("输入图的顶点数和弧数:" ); 
	scanf("%d,%d", &G->vexnum, &G->arcnum); 
	printf("\n");
	
	for(i = 1; i <= G->vexnum; i++)
	{
		printf("输入第%d个顶点信息:", i);
		scanf("%s", &G->adjlist[i].data); 
	}
	printf("\n");
	for(i = 1; i <= G->vexnum; ++i) 
		G->adjlist[i].firstarc = NULL;
	for(k = 1; k <= G->arcnum; ++k)
	{ 
		printf("输入第%d条弧的弧尾和弧头:", k); 
		scanf("%d,%d", &v1, &v2); 
		i = v1;
		j = v2; 
		p = (ArcNode *)malloc(sizeof(ArcNode)); 
		p->adjvex = j; 
		p->nextarc = G->adjlist[i].firstarc; 
		G->adjlist[i].firstarc = p; 
	}
	printf("\n");

}

void DispAdj(ALGraph *G)
{ 
	int i; 
	ArcNode *q; 
	for(i = 1; i <= G->vexnum; ++i)
	{ 
		q = G->adjlist[i].firstarc; 
		printf("%d", i);
		while(q != NULL)
		{ 
			printf("->%d", q->adjvex); 
			q = q->nextarc; 
		} 
		printf("\n"); 
	} 
} 

void DFS(ALGraph *G, int v)
{
	ArcNode *p; 
	visited[v] = 1; 
	printf("%3d", v); 
	for(p = G->adjlist[v].firstarc; p != NULL; )
	{ 
		if(!visited[p->adjvex]) 
            DFS(G, p->adjvex); 
		p = p->nextarc; 
	} 
}

void BFS(ALGraph *G, int v)
{ 
	
	ArcNode *p;
	int queue[MAX], w, i;
	int front = 0, rear = 0;
	for(i = 0; i < MAX; i++)
		visited[i] = 0;
	printf("%3d", v);
	visited[v] = 1;
	rear = (rear + 1) % MAX;
	queue[rear] = v;
	while(front != rear)
	{
		front = (front + 1) % MAX;
		w = queue[front];
		p = G->adjlist[w].firstarc;
		while(p != NULL)
		{
			if(visited[p->adjvex] == 0)
			{
				printf("%3d",p->adjvex);
				visited[p->adjvex] = 1;
				rear = (rear+1) % MAX;
				queue[rear] = p->adjvex;
			}
			p = p->nextarc;
		}
	}
	printf("%\n");
}

int main()
{
	//int i, j, k; 
	ALGraph *G;
	printf("\n"); 
	G=(ALGraph *)malloc(sizeof(ALGraph)); 
	CreateDG(G); 
	printf("图的邻接表为:\n"); 
	DispAdj(G); 
	printf("\n");
	printf("从顶点1开始的深度优先搜索:\n"); 
	DFS(G, 1); 
	printf("\n");
	printf("从顶点1开始的广度优先搜索:\n"); 
	BFS(G, 1); 
	printf("\n");
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode
{
    int data;
    int bf;
    struct BiTNode* lchild, *rchild;
}BiTNode, *BiTree;
typedef enum{false,true}bool;
//左旋转
void L_Rotate(BiTree *T)
{
    BiTree R = (*T)->rchild;
    (*T)->rchild = R->lchild;
    R->lchild = *T;
    *T = R;
    return;
}
//右旋转
void R_Rotate(BiTree *T)
{
    BiTree L = (*T)->lchild;
    (*T)->lchild = L->rchild;
    L->rchild = *T;
    *T = L;
    return;
}
#define LH +1
#define EH 0
#define RH -1
//T 的左边高，不平衡，使其平衡，右旋转，右旋转前先检查L->bf，
//如果为RH，L要先进行左旋转，使T->lchild->bf和T->bf一致
void LeftBalance(BiTree* T)
{
    BiTree L,Lr;
    L = (*T)->lchild;
    Lr = L->rchild;
    switch (L->bf)
    {
        case LH:
            L->bf = (*T)->bf =  EH;
            R_Rotate(T);
            break;
        case RH:
            switch (Lr->bf)
            {
                case LH:
                    L->bf = EH;
                    (*T)->bf = RH;
                    break;
                case EH:
                    L->bf = (*T)->bf = EH;
                    break;
                case RH:
                    L->bf = LH;
                    (*T)->bf = EH;
                    break;
            }
            Lr->bf = EH;
            L_Rotate(&L);
            R_Rotate(T);
            break;
    }
}
//T 的右边高，不平衡，使其平衡，左旋转，左旋转前先检查R->bf,
//如果为LH，R要先进行右旋转，使T->rchild->bf和T->bf一致
void RightBalance(BiTree* T)
{
    BiTree R,Rl;
    R = (*T)->rchild;
    Rl = R->lchild;
    switch(R->bf)
    {
        case RH:
            R->bf = (*T)->bf = EH;
            L_Rotate(T);
            break;
        case LH:
            switch(R->bf)
            {
                case LH:
                    R->bf = RH;
                    (*T)->bf = EH;
                    break;
                case EH:
                    R->bf = (*T)->bf = EH;
                    break;
                case RH:
                    R->bf = EH;
                    (*T)->bf = LH;
                    break;
            }
            Rl->bf = EH;
            R_Rotate(&R);
            L_Rotate(T);
            break;
    }
}
//往平衡二叉树上插入结点
bool InsertAVL(BiTree* T,int data,bool *taller)
{
    if(*T == NULL)  //找到插入位置
    {
        *T = (BiTree)malloc(sizeof(BiTNode));   
        (*T)->bf = EH;
        (*T)->rchild = (*T)->lchild = NULL;
        (*T)->data = data; 
        *taller = true;
    }
    else
    {
        if(data == (*T)->data)  //树中有相同的结点数据直接返回
        {
            *taller = false;
            return false;
        }
        if(data < (*T)->data)   //往左子树搜索进行插入
        {
            if(!InsertAVL(&(*T)->lchild,data,taller))   //树中有相同的结点
            {
                *taller = false;
                return false;
            }   
            if (*taller)
            {
                switch ((*T)->bf)               //T插入结点后，检测平衡因子，根据情况，做相应的修改和旋转
                {
                case LH:
                    LeftBalance(T);             //插入后左边不平衡了，让其左平衡
                    *taller = false;
                    break;
                case EH:
                    (*T)->bf = LH;
                    *taller = true;
                    break;
                case RH:
                    (*T)->bf = EH;
                    *taller = false;
                    break;
                }
            }
        }
        else                    //往右子树搜索进行插入
        {
            if(!Insert(&(*T)->rchild),data,taller)      //树中有相同的结点
            {
                *taller = false;
                return false;
            }
            if (*taller)        //插入到右子树中且长高了
            {
                switch ((*T)->bf)                       //T插入结点后，检测平衡因子，根据情况，做相应的修改和旋转
                {
                case LH:
                    (*T)->bf = EH;
                    *taller = false;
                    break;
                case EH:
                    (*T)->bf = RH;
                    *taller = true;
                    break;
                case RH:
                    R_Balance(T);                       //插入后右边不平衡了，让其右平衡
                    *taller = false;
                    break;
                }
            }
        }
    }
    return true;
}

1、2-3树
            每个节点都具有2个孩子（称之为2节点）或者3个孩子（称之为3节点）。
      一个2节点包含一个元素和两个孩子（或没有孩子）。

                              一个3节点包含两个元素和三个孩子（或没有孩子）。

1.对于空树 插入一个节点直接插入就好。

 2.插入节点到一个2节点的叶子上。  比如插入3

3.1要在3节点上插入，此时3节点的上面是2节点 则将 上面的2节点变成3节点  比如插入5

以前我们普通二叉树 插入时都是在叶子节点后添加，这样会导致二叉树的高度不断增加。查找困难。

     此时 我们用2-3树时重复分利用特性。 往上寻找有用空间 进行有效的利用

      3.3 要在3节点插入数据时  ，该3节点往上遍历都是3节点，这时要扩展高度了。

1.要删除的数位于3节点地址上。 3节点 ->2节点就好  比如删除6

1.此叶子节点上一级是2节点，但是他有一个3节点的有孩子。

5.  要删除的元素位于非叶子节点的分支上。

                 当是2节点时 则按照中序遍历 找此节点前面或者后面的数顶底

#include <stdio.h>
 
void InsertSort(int array[], int len)
{
    int i, j, temp;
 
    for(i = 1; i < len; i++)
    {
        temp = array[i];
 
        for(j = i - 1; j >= 0; j--)
        {
            if(temp < array[j])
            {
                array[j + 1] = array[j];
            }
            else
            {
                break;
            }
        }
        array[j + 1] = temp;
    }
}
 
int main()
{
    int i = 0;
    int a[] = {8, 2, 5, 3, 6, 7, 1, 9, 0};
    int length = sizeof(a) / sizeof(a[0]);
 
    InsertSort(a, length);
 
    for(i = 0; i < length; i++)
    {
        printf("%d ", a[i]);
    }
 
    return 0;
}

#include <stdio.h>
 
void ShellSort(int array[], int len)
{
    int i, j, temp, h;
 
    for(h = len / 2; h > 0; h = h / 2)
    {
        for(i = h; i < len; i++)
        {
            temp = array[i];
 
            for(j = i - h; j >= 0; j -= h)
            {
                if(temp < array[j])
                {
                    array[j + h] = array[j];
                }
                else
                {
                    break;
                }
            }
            array[j + h] = temp;
        }
    }
}
 
int main()
{
    int i = 0;
    int a[] = {8, 2, 5, 3, 6, 7, 1, 9, 0};
    int length = sizeof(a) / sizeof(a[0]);
 
    ShellSort(a, length);
 
    for(i = 0; i < length; i++)
    {
        printf("%d ", a[i]);
    }
 
    return 0;
}

#include <stdio.h>
 
void BubbleSort(int array[], int len)
{
	int i, j;
	int temp;
 
	for (i = 0; i < len -1; ++i)
	{
		for (j = len - 1; j > i; --j)
		{
			if (array[j] < array[j - 1])
			{
				temp = array[j];
				array[j] = array[j - 1];
				array[j - 1] = temp;
			}
		}
	}
}
 
int main()
{
	int i = 0;
	int a[] = {29, 18, 87, 56, 3, 27};
	int length = sizeof(a) / sizeof(a[0]);
 
	BubbleSort(a, length);
 
	for (i = 0; i < length; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
 
	return 0;
}

#include <stdio.h>
 
int a[30], n;
 
void QuickSort(int left, int right)
{
    int i, j, tmp, tmp1;
    i = left;
    j = right;
 
    if(left >= right)
    {
        return;
    }
 
    while(i < j)
    {
        while(a[j] >= a[left] && i < j) //left作为参考值
        {
            j--;
        }
 
        while(a[i] <= a[left] && i < j)
        {
            i++;
        }
 
        if(i < j)
        {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
 
    tmp1 = a[i];
    a[i] = a[left];
    a[left] = tmp1;
 
    QuickSort(left, i - 1);
    QuickSort(i + 1, right);
 
}
 
int main()
{
    int i;
 
    printf("Please input n:\n");
    scanf("%d", &n);
 
    printf("Please input number:\n");
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
 
    QuickSort(1, n);
 
    for(i = 1; i <= n; i++)
    {
        printf("%d ", a[i]);
    }
 
    return 0;
}

#include <stdio.h>
 
void SelectSort(int *num, int n)
{
    int i, j;
    int tmp = 0, min = 0;
 
    for(i = 0; i < n - 1; i++)
    {
        min = i;
 
        for(j = i + 1; j < n; j++)
        {
            if(num[j] < num[min])
            {
                min = j;
            }
        }
        if(min != i)
        {
            tmp = num[i];
            num[i] = num[min];
            num[min] = tmp;
        }
    }
}
 
int main()
{
    int i, len;
    int num[] = {4, 8, 2, 4, 0, 9, 1, 3, 5};
    len = sizeof(num) / sizeof(num[0]);
    
    SelectSort(num, len);
 
    for(i = 0; i < len; i++)
    {
        printf("%d ", num[i]);
    }
 
    return 0;
}

#include <stdio.h>//适用于数据量大的时候(构建浪费时间)
 
void AdjustMinHeap(int *array, int pos, int len)
{
    int tmp, child;
 
    for(tmp = array[pos]; 2 * pos + 1 <= len; pos = child)
    {
        child = 2 * pos + 1;
        if(child < len && array[child] > array[child + 1])
        {
            child++;
        }
 
        if(array[child] < tmp)
        {
            array[pos] = array[child];
        }
 
        else
        {
            break;
        }
    }
    array[pos] = tmp;
}
 
void Swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
void HeapSort(int *array, int len)
{
    int i;
 
    for(i = len/2 - 1; i >= 0; i--)
    {
        AdjustMinHeap(array, i, len - 1);
    }
 
    for(i = len - 1; i >= 0; i--)
    {
        Swap(&array[0], &array[i]);
        AdjustMinHeap(array, 0, i - 1);
    }
}
 
int main()
{
    int i;
    int array[] = {0, 13, 14, 1, 18, 27};
    int length = sizeof(array) / sizeof(array[0]);
 
    HeapSort(array, length);
 
    for(i = 0; i < length; i++)
    {
        printf("%d ", array[i]);
    }
 
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
 
void Merge(int array[], int start, int middle, int end)
{
	int i, j, k, n1, n2;
	
	n1 = middle - start + 1;              
	n2 = end - middle; 
 
	int *L = (int *)malloc(n1 * sizeof(int));
	int *R = (int *)malloc(n2 * sizeof(int));
 
	for (i = 0, k = start; i < n1; i++, k++)
	{
		L[i] = array[k];
	}
 
	for (i = 0, k = middle + 1; i < n2; i++, k++)
	{
		R[i] = array[k];
	}
 
	for (k = start, i = 0, j = 0; i < n1 && j < n2; k++)
	{
		if (L[i] < R[j])
		{
			array[k] = L[i];
			i++;
		}
		else
		{
			array[k] = R[j];
			j++;
		}
	}
 
	if (i < n1)
	{
		for (j = i; j < n1; j++, k++)
		{
			array[k] = L[j];
		}
	}
 
	if (j < n2)
	{
		for (i = j; i < n2; i++, k++)
		{
			array[k] = R[i];
		}
	}
}
 
void MergeSort(int array[], int start, int end)
{
	int middle;
	int i;
 
	if (start < end)
	{
		middle = (start + end) / 2;
		
		MergeSort(array, start, middle);
		MergeSort(array, middle + 1, end);
		Merge(array, start, middle, end);
	}
}
 
int main()
{
	int i = 0;
	int a[] = {49, 38, 65, 97, 76, 13, 27};
	int length = sizeof(a) / sizeof(a[0]);
 
	MergeSort(a, 0, length -1);
 
	for (i = 0 ; i < length; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
 
	return 0;
}