数据结构全实现

文章目录

目录一.线性表二.链表三.堆栈四.链栈五.队列六.链队列七.树八.哈夫曼树九.堆十.并查集十一.排序

一.线性表

#define MaxSize 10001
typedef int ElementType;
typedef int Position;
#include
using namespace std;

typedef struct LNode* List;
struct LNode
{
	ElementType Data[MaxSize];
	int Last;
};
//struct LNode L;		//访问下标为i的元素 Ptrl->Data[i]
//List Ptrl;


//初始化
List List_MakeEmpty()
{
	List Ptrl;
	Ptrl = (List)malloc(sizeof(struct LNode));
	Ptrl->Last = -1;
	return Ptrl;
}

//查找
int List_Find(ElementType x, List Ptrl)
{
	int i = 0;
	while (i <= Ptrl->Last && Ptrl->Data[i] != x)
	{
		i++;
	}
	if (i > Ptrl->Last)
	{
		cout << "没找到" << endl;
		return -1;
	}
	else {
		cout << "在" << i << "找到了" << endl;
		return i;
	}
}

//插入
bool List_Insert(ElementType x, Position P, List Ptrl)//P存储下标位置
{
	Position i;
	if (Ptrl->Last == MaxSize - 1)
	{
		cout << "表满" << endl;
		return false;
	}
	if (P < 0 || P > Ptrl->Last + 1) { 
		cout << "位置不合法" << endl;
		return false;
	}
	for (i = Ptrl->Last; i >= P; i--)
		Ptrl->Data[i + 1] = Ptrl->Data[i]; 
	Ptrl->Data[P] = x;  
	Ptrl->Last++;       
	return true;
}

//删除
bool List_Delete(List Ptrl, Position P)
{ 
	Position i;

	if (P < 0 || P > Ptrl->Last) { 
		cout << "位置" << P << "不存在元素" << endl;
		return false;
	}
	for (i = P + 1; i <= Ptrl->Last; i++)
		Ptrl->Data[i - 1] = Ptrl->Data[i]; 
	Ptrl->Last--; 
	return true;
}

二.链表

#include
using namespace std;
typedef int ElementType;

typedef struct link_List_Node {
	ElementType data; // 值 
	struct link_List_Node* Next; // 指向下一个结点 
};

//初始化
link_List_Node *link_List_MakeEmpty()
{
	link_List_Node* head = (link_List_Node*)malloc(sizeof(link_List_Node));	//声明头指针
	head ->data= NULL;
	head->Next = NULL;
	link_List_Node* First = (link_List_Node*)malloc(sizeof(link_List_Node));
	First->data = 1;
	First->Next = head->Next;
	head->Next = First;
	//cout << head->data << " " << head->Next->data << endl;
	return head;
}

//按值查找
link_List_Node* link_List_Find(ElementType x, link_List_Node* head)
{
	link_List_Node* ptr = head;
	bool flag = false;
	while (ptr->Next)
	{
		if (ptr->Next->data == x)
		{
			flag = true;
			cout << "找到了" << endl;
			return ptr->Next;
		}
		else
		{
			ptr = ptr->Next;
		}
	}
	if(flag == false)
	{
		cout << "没找到" << endl;
	}
	return head;
}

//按序号查找
link_List_Node* link_List_FindKth(int i, link_List_Node* head)
{
	link_List_Node *ptr = head;
	int j = 0;
	bool flag = false;
	while (ptr)
	{
		if (j == i)
		{
			flag = true;
			cout << "找到了" << endl;
			return ptr;
		}
		else
		{
			j++;
			ptr = ptr->Next;
		}
	}
	if (!flag)
	{
		cout << "没找到" << endl;
		return head;
	}
}

//插入
link_List_Node* link_List_Insert(link_List_Node* head, int i, ElementType x)
{
	link_List_Node *ptr = head;
	ptr = link_List_FindKth(i-1, head);
	link_List_Node* NewPtr = (link_List_Node*)malloc(sizeof(link_List_Node));
	NewPtr->data = x;
	NewPtr->Next = ptr->Next;
	ptr->Next = NewPtr;
	return NewPtr;
}

//删除
link_List_Node* link_List_Delete(link_List_Node* head, int i)
{
	link_List_Node* ptr = head;
	ptr = link_List_FindKth(i - 1, head);
	link_List_Node* p = ptr->Next; // p是要删除的结点
	ptr->Next = ptr->Next->Next;
	free(p);
	return head;
}

三.堆栈

#include
using namespace std;
#define Stack_MaxSize 10001
typedef int ElementType;

typedef struct SNode* Stack;
struct SNode
{
	ElementType Data[Stack_MaxSize];
	int Top;
};

//初始化
Stack Create_Stack()
{
	Stack SNode_1 = (Stack)malloc(sizeof(SNode));
	SNode_1->Top = -1;
	return SNode_1;
}

//判断栈满
bool Stack_IsFull(Stack ptr)
{
	if (ptr->Top == Stack_MaxSize - 1)
	{
		cout << "栈满" << endl;
		return true;
	}
	else
	{
		cout << "栈未满" << endl;
		return false;
	}
}

//入栈
void Stack_Push(Stack ptr, ElementType item)
{
	if (Stack_IsFull(ptr))
	{
		return;
	}
	else
	{
		ptr->Data[++(ptr->Top)] = item;
		return;
	}
}

//判断栈空
bool Stack_IsEmpty(Stack ptr)
{
	if (ptr->Top == -1)
	{
		cout << "栈空" << endl;
		return true;
	}
	else
	{
		cout << "栈不空" << endl;
		return false;
	}
}

//出栈
ElementType Stack_Pop(Stack ptr)
{
	if (Stack_IsEmpty(ptr))
	{
		return 0;
	}
	else {
		return(ptr->Data[ptr->Top--]);
	}
}

四.链栈

typedef int ElementType;
#include
using namespace std;

typedef struct link_SNode* link_Stack;
struct link_SNode
{
	ElementType Data;
	link_Stack Next;
};

//创建空链表
link_Stack link_Stack_CreateStack()
{
	link_Stack S;
	S = (link_Stack)malloc(sizeof(link_SNode));
	S->Next = NULL;
	return S;
}

//判空
bool link_Stack_IsEmpty(link_Stack S)
{
	if (S->Next == NULL)
	{
		cout << "链栈空" << endl;
		return true;
	}
	else
	{
		cout << "链栈不空" << endl;
		return false;
	}
}

//入栈
void link_Stack_Push(ElementType item, link_Stack S)
{
	link_Stack TmpCell;
	TmpCell = (link_Stack)malloc(sizeof(link_SNode));
	TmpCell->Data = item;
	TmpCell->Next = S->Next;
	S->Next = TmpCell;
}

//出栈
ElementType link_Stack_Pop(link_Stack S)
{
	link_Stack First_Cell;
	ElementType TopElem;
	if (link_Stack_IsEmpty(S))
	{
		return 0;
	}
	else {
		First_Cell = S->Next;
		S->Next = First_Cell->Next;
		TopElem = First_Cell->Data;
		free(First_Cell);
		return TopElem;
	}
}

五.队列

#define Queue_MaxSize 10001
#include
typedef int ElementType;
using namespace std;

struct QNode
{
	ElementType Data[Queue_MaxSize];
	int rear;
	int front;
};
typedef struct QNode* Queue;

//初始化
Queue Creat_Queue()
{
	Queue Q_1 = (Queue)malloc(sizeof(QNode));
	Q_1->front = -1;
	Q_1->rear = -1;
	//cout << "创建完毕" << endl;
	return Q_1;
}

//判断队满
bool Queue_IsFull(Queue Q)
{
	if ((Q->rear+1)%Queue_MaxSize == Q->front)
	{
		cout << "队满" << endl;
		return true;
	}
	else {
		cout << "队未满" << endl;
		return false;
	}
}

//判断队空
bool Queue_IsEmpty(Queue Q)
{
	if (Q->front == Q->rear)
	{
		cout << "队空" << endl;
		return true;
	}
	else
	{
		cout << "队不空" << endl;
		return false;
	}
}

//入队
void Queue_AddQ(Queue Ptrle, ElementType item)
{
	if (!Queue_IsFull(Ptrle))
	{
		Ptrle->rear = (Ptrle->rear + 1) % Queue_MaxSize;
		Ptrle->Data[Ptrle->rear] = item;
	}
}

//出队
ElementType Queue_Delete(Queue Q)
{
	if (!Queue_IsEmpty(Q))
	{
		Q->front = (Q->front + 1) % Queue_MaxSize;
		return Q->Data[Q->front];
	}
	else
	{
		return 0;
	}
}

六.链队列

#include
typedef int ElementType;
using namespace std;

struct Node
{
	ElementType Data;
	struct Node* Next;
};
struct link_QNode 
{
	struct Node* rear;
	struct Node* front;
};
typedef struct Node* link_Node;
typedef struct link_QNode* link_Queue;

//初始化
link_Queue link_Queue_MakeEmpty()
{
	link_Queue link_Q = (link_Queue)malloc(sizeof(link_QNode));
	//link_Q->front = (link_Node)malloc(sizeof(Node));
	//link_Q->rear = (link_Node)malloc(sizeof(Node));
	link_Node link_Q_Head = (link_Node)malloc(sizeof(Node));
	link_Q->front = link_Q_Head;
	link_Q->rear = link_Q_Head;
	link_Q_Head->Next = NULL;
	cout << "创建成功" << endl;
	return link_Q;
}

//判断队空
bool link_Queue_IsEmpty(link_Queue link_Q)
{
	if (link_Q ->front->Next == NULL)
	{
		cout << "链队列空" << endl;
		return true;
	}
	else
	{
		cout << "链队列不空" << endl;
		return false;
	}
}

//入队
void link_Queue_Add(link_Queue link_Q, ElementType x)
{
	link_Node link_Q_1 = (link_Node)malloc(sizeof(Node));
	link_Q_1->Data = x;
	link_Q_1->Next = NULL;
	link_Q->rear->Next = link_Q_1;
	link_Q->rear = link_Q_1;
}

//出队
ElementType link_Queue_Delete(link_Queue link_Q)
{
	link_Node FrontCell;
	ElementType FrontElem;
	if (!link_Queue_IsEmpty(link_Q))
	{
		FrontCell = link_Q->front->Next;
		FrontElem = FrontCell->Data;
		link_Q->front->Next = FrontCell->Next;
		if (FrontCell == link_Q ->rear)
		{
			link_Q->rear = link_Q->front;
		}
		free(FrontCell);
		cout << FrontElem << endl;
		return FrontElem;
	}
	return 0;
}

七.树

#include
#include"Stack.h"
#include"Queue.h"


typedef int ElementType;
using namespace std;

typedef struct TreeNode* BinTree;
typedef BinTree Position;

struct TreeNode
{
	ElementType Data;
	BinTree Left;
	BinTree Right;
};

//初始化
BinTree BinTree_MakeEmpty(ElementType x)
{
	BinTree BT = (BinTree)malloc(sizeof(TreeNode));
	BT->Data = x;
	BT->Left = NULL;
	BT->Right = NULL;
	cout << "创建成功" << BT->Data << endl;
	return BT;
}

//先序遍历
void Pre_Order_Traversal(BinTree BT)
{
	if (BT)
	{
		cout << BT->Data << endl;
		Pre_Order_Traversal(BT->Left);
		Pre_Order_Traversal(BT->Right);
	}
}

//中序遍历
void In_Order_Traversal(BinTree BT)
{
	if (BT)
	{
		In_Order_Traversal(BT->Left);
		cout << BT->Data << endl;
		In_Order_Traversal(BT->Right);
	}
}

//后序遍历
void Post_Order_Traversal(BinTree BT)
{
	if (BT)
	{
		Post_Order_Traversal(BT->Left);
		Post_Order_Traversal(BT->Right);
		cout << BT->Data << endl;
	}
}

//非递归实现

void In_Oeder_Traversal_Stack(BinTree BT)
{
	BinTree T = BT;
	Stack S = Create_Stack();
	while (T || Stack_IsEmpty(S))
	{
		while (T)
		{
			Stack_Push(S, T->Data);
			T = T->Left;
		}
		if (!Stack_IsEmpty(S))
		{
			T->Data = Stack_Pop(S);
			cout << T->Data << endl;
			T = T->Right;
		}
	}
}

//层次遍历
void Level_Order_Traversal(BinTree BT)
{
	Queue Q; BinTree T;
	if (!BT)
	{
		return;
	}
	Q = Creat_Queue();
	Queue_AddQ(Q, BT->Data);
	
	while (!Queue_IsEmpty(Q))
	{
		T->Data = Queue_Delete(Q);
		cout << T->Data << endl;
		if (T->Left)
		{
			Queue_AddQ(Q, T->Left->Data);
		}
		if (T->Right)
		{
			Queue_AddQ(Q, T->Right->Data);
		}
	}
}


//二叉搜索树
Position Bst_Find(ElementType x, BinTree BST)
{
	if (!BST)
	{
		return NULL;
	}
	if (x > BST->Data)
	{
		return Bst_Find(x, BST->Right);
	}
	else if (x < BST->Data)
	{
		return Bst_Find(x, BST->Left);
	}
	else
	{
		return BST;
	}
}

//找最小值
Position Bst_FindMin(BinTree BST)
{
	if (!BST)
	{
		return NULL;
	}
	else if (!BST->Left)
	{
		return BST;
	}
	else {
		return Bst_FindMin(BST->Left);
	}
}

//找最大值
Position Bst_FindMax(BinTree BST)
{
	if (!BST)
	{
		return NULL;
	}
	else if (!BST->Right)
	{
		return BST;
	}
	else
	{
		return Bst_FindMax(BST->Right);
	}
}

//插入
BinTree Bst_Insert(ElementType x, BinTree BST)
{
	if (!BST)
	{
		BST = (BinTree)malloc(sizeof(TreeNode));
		BST->Data = x;
		BST->Left = NULL;
		BST->Right = NULL;
	}
	else
	{
		if (x < BST->Data)
		{
			BST->Left = Bst_Insert(x, BST->Left);
		}
		else if (x > BST->Data)
		{
			BST->Right = Bst_Insert(x, BST->Right);
		}
	}
	return BST;
}

//删除
BinTree Bst_Delete(ElementType x, BinTree BST)
{
	Position Tmp;
	if (!BST)
	{
		cout << "删除的元素未找到" << endl;
	}
	else if (x < BST->Data)
	{
		BST->Left = Bst_Delete(x, BST->Left);
	}
	else if (x > BST->Data)
	{
		BST->Right = Bst_Delete(x, BST->Right);
	}
	else
	{
		if (BST->Left && BST->Right)		//左右子树都不为空
		{
			Tmp = Bst_FindMin(BST->Right);
			BST->Data = Tmp->Data;
			BST->Right = Bst_Delete(BST->Data, BST->Right);
		}
		else
		{
			Tmp = BST;
			if (!BST->Left)
			{
				BST = BST->Right;
			}
			else if (!BST->Right)
			{
				BST = BST->Left;
			}
			free(Tmp);
		}
	}
	return BST;
}

八.哈夫曼树

#include
#include"Heap.h"
using namespace std;

typedef struct HuffmanTreeNode* HuffmanTree;
struct HuffmanTreeNode
{
	int weight;
	HuffmanTree Left, Right;
};

HuffmanTree Huffman(MinHeap H)
{
	int i; HuffmanTree T;
	Build_MinHeap(H);
	for ( i = 1; i < H->size; i++)
	{
		T = (HuffmanTree)malloc(sizeof(HuffmanTreeNode));
		T->Left->weight = Heap_Delete(H);
		T->Right->weight = Heap_Delete(H);
		T->weight = T->Left->weight + T->Right->weight;
		Heap_insert(H, T->weight);
	}
	T->weight = Heap_Delete(H);
	return T;
}

九.堆

#include
using namespace std;
#define MaxData 10001
typedef int ElementType;
typedef struct HeapStruct* MaxHeap;
typedef struct HeapStruct* MinHeap;
struct HeapStruct
{
	ElementType* Elements;
	int size;
	int Capacity;
};

//创建最大堆
MaxHeap MaxHeap_Create(int Heap_MaxSize)
{
	MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct));
	H->Elements = (ElementType*)malloc((Heap_MaxSize + 1) * sizeof(ElementType));
	H->size = 0;
	H->Capacity = Heap_MaxSize;
	H->Elements[0] = MaxData;
	cout << "创建成功" << endl;
	return H;
}

//创建最小堆
MinHeap MinHeap_Create(int Heap_MaxSize)
{
	MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct));
	H->Elements = (ElementType*)malloc((Heap_MaxSize + 1) * sizeof(ElementType));
	H->size = 0;
	H->Capacity = Heap_MaxSize;
	H->Elements[0] = MaxData;
	cout << "创建成功" << endl;
	return H;
}


//堆是不是满
bool Heap_IsFull(struct HeapStruct* H)
{
	if (H->size == H->Capacity)
	{
		cout << "堆满" << endl;
		return true;
	}
	else
	{
		cout << "堆未满" << endl;
		return false;
	}
}

//堆是不是空
bool Heap_IsEmpty(struct HeapStruct* H)
{
	if (H->size == 0)
	{
		cout << "堆空" << endl;
		return true;
	}
	else
	{
		cout << "堆不空" << endl;
		return false;
	}
}

//插入
void Heap_insert(struct HeapStruct* H, ElementType item)
{
	int i;
	if (Heap_IsFull(H))
	{
		return;
	}
	i = ++H->size;	//i指向插入后堆中最后一个元素的位置
	for(;H->Elements[i/2] < item; i/=2)
	{
		H->Elements[i] = H->Elements[i / 2];
	}
	H->Elements[i] = item;
}

//删除
ElementType Heap_Delete(struct HeapStruct* H)
{
	int Parent, Child;
	ElementType MaxItem, Temp;
	if (Heap_IsEmpty(H))
	{
		return 0;
	}
	MaxItem = H->Elements[1];
	Temp = H->Elements[H->size--];
	for (Parent = 1; Parent * 2 <= H->size; Parent = Child)
	{
		Child = Parent * 2;
		if ((Child!=H->size)&&(H->Elements[Child] < H->Elements[Child+1]))
		{
			Child++;
		}
		if (Temp >= H->Elements[Child])
		{
			break;
		}
		else {
			H->Elements[Parent] = H->Elements[Child];
		}
	}
	H->Elements[Parent] = Temp;
	return MaxItem;
}

//构建最大堆
void MaxHeap_PercDown(MaxHeap H, int p)
{
	int Parent, Child;
	ElementType x;
	x = H->Elements[p];
	for (Parent = p; Parent * 2 <= H->size; Parent = Child)
	{
		Child = Parent * 2;
		if ((Child != H->size)&&(H->Elements[Child] < H->Elements[Child+1]))
		{
			Child++;
		}
		if (x >= H->Elements[Child])
		{
			break;
		}
		else {
			H->Elements[Parent] = H->Elements[Child];
		}
	}
	H->Elements[Parent] = x;
}

void Build_MaxHeap(MaxHeap H)
{
	int i;
	for (i = H->size / 2; i > 0; i--)
	{
		MaxHeap_PercDown(H, i);
	}
}

//构建最小堆
void MinHeap_PercDown(MinHeap H, int p)
{
	int Parent, Child;
	ElementType x;
	x = H->Elements[p];
	for (Parent = p; Parent * 2 <= H->size; Parent = Child)
	{
		Child = Parent * 2;
		if ((Child != H->size)&&(H->Elements[Child] > H->Elements[Child+1]))
		{
			Child++;
		}
		if (x <= H->Elements[Child])
		{
			break;
		}
		else {
			H->Elements[Parent] = H->Elements[Child];
		}
	}
	H->Elements[Parent] = x;
}

void Build_MinHeap(MinHeap H)
{
	int i;
	for ( i = H->size/2; i > 0; i--)
	{
		MinHeap_PercDown(H, i);
	}
}

十.并查集

#include
using namespace std;
typedef int ElementType;
#define SetType_MaxSize 10001

typedef struct {
	ElementType Data;
	int Parents;
}SetType;

int SetType_Find(SetType S[], ElementType x)
{
	int i;
	for ( i = 0; i < SetType_MaxSize && S[i].Data != x;i++)
	{
		if (i >= SetType_MaxSize)
		{
			return -1;
		}
		for (; S[i].Parents >= 0; i = S[i].Parents);
		return i;
	}
}

void Union(SetType S[], ElementType x1, ElementType x2)
{
	int Root1, Root2;
	Root1 = SetType_Find(S, x1);
	Root2 = SetType_Find(S, x2);
	if (Root1 != Root2)
	{
		S[Root2].Parents = Root1;
	}
}

十一.排序

#include
#include
#include
using namespace std;
typedef int ElementType;

//冒泡排序
void Bubble_sort(ElementType A[], int N)
{
	for (int p = N - 1; p >= 0; p--)
	{
		int flag = 0;
		for (int i = 0; i < p; i++)
		{
			if (A[i] > A[i + 1])
			{
				swap(A[i], A[i + 1]);
				flag = 1;
			}
		}
		if (flag = 0)
		{
			break;
		}
	}
}

//插入排序
void Insertion_sort(ElementType A[], int N)
{
	int i;
	for (int p = 1; p <	N; p++)
	{
		int Tmp = A[p];
		for (i = p; i > 0 && A[i - 1] > Tmp; i--)
		{
			A[i] = A[i - 1];
		}
		A[i] = Tmp;
		
	}
}

//希尔排序
void Shell_sort(ElementType A[], int N)
{
	int i;
	for (int D = N/2; D > 0; D/=2)
	{
		for (int p = 0; p < N; p++)
		{
			int Tmp = A[p];
			//插入排序
			for (i = p; i >= D && A[i-D] > Tmp; i-=D)
			{
				A[i] = A[i - D];
			}
			A[i] = Tmp;
		}
	}
}

//归并排序
void Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd)
{
	int LeftEnd = R - 1;
	int Tmp = L;
	int NumElements = RightEnd - L + 1;
	while (L <= LeftEnd && R <= RightEnd)
	{
		if (A[L] <= A[R])
		{
			TmpA[Tmp++] = A[L++];
		}
		else
		{
			TmpA[Tmp++] = A[R++];
		}
	}
	while (L <= LeftEnd)
	{
		TmpA[Tmp++] = A[L++];
	}
	while (R <= RightEnd)
	{
		TmpA[Tmp++] = A[R++];
	}
	for (int i = 0; i < NumElements; i++, RightEnd--)
	{
		A[RightEnd] = TmpA[RightEnd];
	}
}

void Mosrt(ElementType A[], ElementType TmpA[], int L,int RightEnd)
{
	int Center;
	if (L < RightEnd)
	{
		Center = (L + RightEnd) / 2;
		Mosrt(A, TmpA, L, Center);
		Mosrt(A, TmpA, Center + 1, RightEnd);
		Merge(A, TmpA, L, Center + 1, RightEnd);
	}
}

void Merge_sort(ElementType A[], int N)
{
	ElementType* TmpA;
	TmpA = (ElementType*)malloc(N * sizeof(ElementType));
	if (TmpA != NULL)
	{
		Mosrt(A, TmpA, 0, N - 1);
		free(TmpA);
	}
}

//快速排序
int partition(int l, int r,ElementType A[])            //实现算法思路第二步
{
	int mid = A[l + r >> 1];           //mid为分界点
	int i = l - 1, j = r + 1;          //i和j为左右指针

	while (i < j)                      //利用左右指针完成区间划分
	{
		do i++; while (A[i] < mid);
		do j--; while (A[j] > mid);
		if (i < j) swap(A[i], A[j]);
	}

	return j;
}

void Quicksort(int l, int r,ElementType A[])
{
	if (l == r) return;                //当区间中内只有一个数时返回

	int j = partition(l, r,A);           //将序列划分为左右两区间

	Quicksort(l, j,A);                   //递归处理左区间
	Quicksort(j + 1, r,A);               //递归处理右区间
}


void Quick_sort(ElementType A[], int N)
{
	Quicksort(0,N-1,A);
}

数据结构全实现

C/C++/C#相关栏目本月热门文章