目录 文章目录
目录一.线性表二.链表三.堆栈四.链栈五.队列六.链队列七.树八.哈夫曼树九.堆十.并查集十一.排序 一.线性表
#define MaxSize 10001typedef int ElementType;typedef int Position;#includeusing 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;}
二.链表
#includeusing 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;}
三.堆栈
#includeusing namespace std;#define Stack_MaxSize 10001typedef 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;#includeusing 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#includetypedef 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;}}
六.链队列
#includetypedef 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;}
九.堆
#includeusing namespace std;#define MaxData 10001typedef 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);}}
十.并查集
#includeusing namespace std;typedef int ElementType;#define SetType_MaxSize 10001typedef 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#includeusing 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 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);}