专门做网站开发的公司,jn建站系统,公司网页介绍模板,wordpress多梦C语言数据结构与算法
线性表
顺序表(静态分配内存)
#include stdio.h
#include stdbool.h
//静态顺序表
#define MAX_SIZE 8
//顺序表储存的数据类型
typedef int ElemType;
typedef struct {ElemType data[MAX_SIZE];int length;
}SeqList;
//初始化顺序表…C语言数据结构与算法
线性表
顺序表(静态分配内存)
#include stdio.h
#include stdbool.h
//静态顺序表
#define MAX_SIZE 8
//顺序表储存的数据类型
typedef int ElemType;
typedef struct {ElemType data[MAX_SIZE];int length;
}SeqList;
//初始化顺序表
void initSeqList(SeqList *L){for (int i 0; i MAX_SIZE; i) {L-data[i] 0; // 将数组中的所有元素初始化为0}L-length 0; // 将顺序表的长度初始化为0
}
//数组创建顺序表
bool createSeqList(SeqList *L,ElemType array[],int l){if(l0||lMAX_SIZE){return false;}for(int i0;il;i){L-data[i]array[i];L-length;}return true;
}
//打印顺序表里面的元素
void printSeqList(SeqList *L){for(int i0;iL-length;i){printf(%d ,L-data[i]);};
}
//获得顺序表长度
int SeqListSize(SeqList *q){return q-length;
}
//尾插
bool tailInsert(SeqList *L,ElemType e){if(L-length1MAX_SIZE){return false;}else{L-data[L-length]e;L-lengthL-length1;return true;}
}
//i位置插入e
bool SeqListInsert(SeqList *L,int i,ElemType e){if(i1||iMAX_SIZE){return false;}else{for(int j L-length;ji;j--){L-data[j]L-data[j-1];}L-data[i-1]e;L-lengthL-length1;}
}
//i位置删除e
bool SeqListDelete(SeqList *L,int i){if(i1||iMAX_SIZE){return false;}else{for(int j i-1;jL-length;j){L-data[j]L-data[j1];}L-lengthL-length-1;}
}int main() {//定义SeqList L;//初始化initSeqList(L);ElemType a[5]{2,3,1,6,7};//创建createSeqList(L,a,5);//输出printSeqList(L);//获取顺序表长度printf(顺序表长度%d\n, SeqListSize(L));//尾插ElemType e 10;tailInsert(L,e);printSeqList(L);printf(顺序表长度:%d\n,SeqListSize(L));//选择位置插入printf(----------\n);SeqListInsert(L,2,5);printSeqList(L);printf(顺序表长度:%d\n,SeqListSize(L));//选择位置删除printf(----------\n);SeqListDelete(L,2);printSeqList(L);printf(顺序表长度:%d\n,SeqListSize(L));return 0;
}顺序表动态分配内存
#include stdio.h
#include stdlib.h typedef struct { int *data; // 指向动态分配数组的指针 int size; // 当前数组的大小 int capacity; // 数组的总容量
} SequentialList; // 初始化顺序表
SequentialList* initSequentialList() { SequentialList *list (SequentialList*)malloc(sizeof(SequentialList)); if(list) { list-data NULL; list-size 0; list-capacity 0; } return list;
} // 向顺序表添加元素如果容量不足则扩大容量
int addElement(SequentialList *list, int element) { if(list-size list-capacity) { // 如果容量不足扩大容量 list-capacity list-capacity 0 ? 1 : list-capacity * 2; list-data (int*)realloc(list-data, list-capacity * sizeof(int)); // 使用realloc来重新分配内存 if(!list-data) { // 如果realloc失败返回错误 printf(Realloc failed.\n); return -1; } } list-data[list-size] element; // 添加元素到数组末尾并增加size return 0;
} // 打印顺序表的所有元素
void printList(SequentialList *list) { for(int i 0; i list-size; i) { printf(%d , list-data[i]); } printf(\n);
} // 销毁顺序表释放动态分配的内存
void destroySequentialList(SequentialList *list) { if(list) { free(list-data); // 释放动态分配的数组 free(list); // 释放顺序表结构体本身的内存 }
} int main() { SequentialList *list initSequentialList(); for(int i 0; i 10; i) { // 向顺序表添加10个元素 addElement(list, i); } printList(list); // 打印顺序表的所有元素 destroySequentialList(list); // 销毁顺序表释放动态分配的内存 return 0;
}单链表(不带头)
#include stdio.h
#include stdbool.h
#include malloc.h
//单链表储存的数据类型
typedef int ElemType;
typedef struct {ElemType data;struct LNode *next;
}LNode;int ListSize(LNode *ptr);//初始化单链表
void InitList(LNode *L){L (LNode*)malloc(sizeof(LNode));L-nextNULL;
}
//数组创建顺序表
LNode *ArrayToList(ElemType array[],int l){// 如果数组为空则返回空链表if (array NULL || l 0) {return NULL;}//定义头节点LNode *head(LNode*)malloc(sizeof(LNode));head-data0;head-nextNULL;LNode *temphead;for(int i0;il;i){LNode *Node(LNode*)malloc(sizeof(LNode));Node-dataarray[i];Node-nextNULL;temp-nextNode;tempNode;}//不带头单链表所以返回头的下一个节点return head-next;
}
//单链表长度
int ListSize(LNode *L){LNode *pL;int length 0;while(p!NULL){length;pp-next;}return length;
}
//头插
void InsertAtHead(LNode **L,ElemType e){if(eNULL){printf(插入数据为空);}else if(LNULL){LNode *Node (LNode*)malloc(sizeof(LNode));Node-datae;Node-nextNULL;LNode;}else{LNode *Node (LNode*)malloc(sizeof(LNode));Node-datae;Node-next*L;*LNode;}
}
//头删
void DeletedFirstNode(LNode **L){if(LNULL){printf(单链表为空);}else{LNode *first*L;*Lfirst-next;free(first);}
}
//尾插
void InsertAtTail(LNode **L,ElemType e){if(eNULL){printf(插入数据为空);}else if(LNULL){LNode *Node (LNode*)malloc(sizeof(LNode));Node-datae;Node-nextNULL;*LNode;}else{LNode *Node (LNode*)malloc(sizeof(LNode));Node-datae;Node-nextNULL;//找到原来最后一个LNode *P *L;while (P-next!NULL){PP-next;}P-nextNode;}
}
//尾删
void DeleteLastNode(LNode **L){if(LNULL){printf(单链表为空);}else{LNode *prev NULL;LNode *curr *L;while (curr-next!NULL){prevcurr;currcurr-next;}prev-nextNULL;free(curr);}
}
//第i位置插入
void InsertAtI(LNode **L,int i,ElemType e){if(iListSize(*L)1||i0){printf(插入位置必须大于0小等于单链表长度\n);}else if(i1){InsertAtHead(L,e);}else if(i ListSize(*L)1){InsertAtTail(L,e);}else{int index 1;LNode *p NULL;LNode * q *L;while (index i){pq;qp-next;index;}LNode *s (LNode *)malloc(sizeof(LNode));s-datae;s-nextq;p-nexts;}}
//第i个位置删除
void DeleteAtI(LNode **L,int i){if(iListSize(*L)||i1){printf(插入位置必须大于0小等于单链表长度);}else{int index 1;LNode *p NULL;LNode * q *L;while (index ! i){pq;qp-next;index;}p-nextq-next;q-nextNULL;free(q);}}//打印单链表里面的元素
void PrintList(LNode *L){LNode *p L;while (p!NULL){printf(%d ,p-data);pp-next;}
}// 得到第i个位置的元素
void getAtINodeData(LNode **L,int i){if(i1||i ListSize(*L)){printf(查找位置不存在);}else{LNode *p*L;int index 1;while(indexip-next!NULL){pp-next;index;}printf(%d位置的元素是%d\n,i,p-data);}
}
//获得某个元素的位置
int GetPosition(LNode **L,ElemType e){int index 1;LNode *t *L;while(t-next!NULL){if(t-datae){break;}index;tt-next;}return index;
}int main() {ElemType a[5]{2,3,1,6,7};//数组转换为单链表LNode *L ArrayToList(a,5);//输出PrintList(L);printf(\n);//链表长度printf(不带头单链表长度%d\n, ListSize(L));//头插InsertAtHead(L,1);printf(头插后\n);PrintList(L);//头删DeletedFirstNode(L);printf(头删后\n);PrintList(L);//尾插InsertAtTail(L,8);printf(尾插后\n);PrintList(L);//尾删DeleteLastNode(L);printf(尾插后\n);PrintList(L);//第三位置插入InsertAtI(L,3,4);printf(插入后\n);PrintList(L);//第三位置删除DeleteAtI(L,3);printf(删除后\n);PrintList(L);//InsertAtI(L,6,4);printf(插入后\n);PrintList(L);//查找某个位置上的元素printf(\n);getAtINodeData(L,2);//查找元素的位置ElemType e 7;int index GetPosition(L,e);printf(%d元素位置在%d\n,e,index);return 0;
}单链表带头
#include stdio.h
#include stdbool.h
#include malloc.h
#include stdlib.h//单链表储存的数据类型
typedef int ElemType;
typedef struct {ElemType data;struct LNode *next;
}LNode;//初始化单链表
void InitList(LNode *L){L (LNode*)malloc(sizeof(LNode));L-nextNULL;
}
//创建头节点
LNode *CreateHeadNode(){LNode *head(LNode*)malloc(sizeof(LNode));if (head NULL) {printf(创建失败\n);exit(1);}head-data 0; // 头节点数据域随意赋值此处为0head-next NULL;return head;
}
//数组创建顺序表
LNode *ArrayToList(ElemType array[],int l){// 如果数组为空则返回空链表if (array NULL || l 0) {return NULL;}//定义头节点LNode *head(LNode*)malloc(sizeof(LNode));head-data0;head-nextNULL;LNode *temphead;for(int i0;il;i){LNode *Node(LNode*)malloc(sizeof(LNode));Node-dataarray[i];Node-nextNULL;temp-nextNode;tempNode;}//带头节点返回头节点return head;
}
//单链表长度
int ListSize(LNode *head){LNode *phead-next;int length 0;while(p!NULL){length;pp-next;}return length;
}
//打印单链表里面的元素
void PrintList(LNode *head){LNode *p head-next;while (p!NULL){printf(%d ,p-data);pp-next;}
}
//头插
void InsertAtHead(LNode *head,ElemType e){if(eNULL){printf(插入数据为空);}else if(headNULL){printf(单链表为空);}else{LNode *Node (LNode*)malloc(sizeof(LNode));Node-datae;Node-nexthead-next;head-nextNode;}
}
//头删
void DeletedFirstNode(LNode *head){if(headNULL){printf(单链表为空);}else{LNode *firsthead-next;head-nextfirst-next;first-dataNULL;free(first);}
}
//尾插
void InsertAtTail(LNode *head,ElemType e){if(eNULL){printf(插入数据为空);}else if(headNULL){printf(单链表为空);}else{LNode *Node (LNode*)malloc(sizeof(LNode));Node-datae;Node-nextNULL;//找到原来最后一个LNode *p head;while (p-next!NULL){pp-next;}p-nextNode;}
}
//尾删
void DeleteLastNode(LNode *head){if(headNULL){printf(单链表为空);}else{LNode *prev NULL;LNode *curr head;while (curr-next!NULL){prevcurr;currcurr-next;}prev-nextNULL;free(curr);}
}
//第i位置插入
void InsertAtI(LNode *head,int i,ElemType e){if(iListSize(head)1||i0){printf(插入位置必须大于0小等于单链表长度\n);}else if(i1){InsertAtHead(head,e);}else if(i ListSize(head)1){InsertAtTail(head,e);}else{int index 1;LNode *p NULL;LNode * q head-next;while (index i){pq;qp-next;index;}LNode *s (LNode *)malloc(sizeof(LNode));s-datae;s-nextq;p-nexts;}}
//第i个位置删除
void DeleteAtI(LNode *head,int i){if(iListSize(head)||i1){printf(插入位置必须大于0小等于单链表长度);}else{int index 1;LNode *p NULL;LNode * q head;while (index ! i){pq;qp-next;index;}p-nextq-next;q-nextNULL;free(q);}
}
// 得到第i个位置的元素
void getAtINodeData(LNode *head,int i){if(i1||i ListSize(head)){printf(查找位置不存在);}else{LNode *phead-next;int index 1;while(indexip-next!NULL){pp-next;index;}printf(%d位置的元素是%d\n,i,p-data);}
}
//获得某个元素的位置
int GetPosition(LNode *head,ElemType e){int index 0;LNode *t head;while(t-next!NULL){if(t-datae){break;}index;tt-next;}return index;
}int main() {ElemType a[5]{2,3,1,6,7};//数组转换为单链表LNode *L ArrayToList(a,5);//输出PrintList(L);printf(\n);//链表长度printf(不带头单链表长度%d\n, ListSize(L));//头插InsertAtHead(L,1);printf(头插后\n);PrintList(L);//头删DeletedFirstNode(L);printf(头删后\n);PrintList(L);//尾插InsertAtTail(L,8);printf(尾插后\n);PrintList(L);//尾删DeleteLastNode(L);printf(尾删后\n);PrintList(L);//第三位置插入InsertAtI(L,3,4);printf(插入后\n);PrintList(L);//第三位置删除DeleteAtI(L,3);printf(删除后\n);PrintList(L);//查找某个位置上的元素printf(\n);getAtINodeData(L,3);//查找元素的位置ElemType e 2;int index GetPosition(L,e);printf(%d元素位置在%d\n,e,index);return 0;
}
排序算法
插冒龟稳定选冒插平方
选择排序-O(n^2)
第一个与后面比较大交换
#include stdio.h
int main() {int array [8]{4,1,6,8,2,3,9,5};int l sizeof (array)/sizeof (int);printf(选择排序前);for(int i0;il;i){printf(%d ,array[i]);};for(int i 0;il-1;i){for(int j i1;jl-i;j){if(array[i]array[j]){int temp array[i];array[i]array[j];array[j]temp;}}};printf(选择排序后);for(int i0;il;i){printf(%d ,array[i]);};return 0;
}冒泡排序-O(n^2)
两两比较–比它大交换–第一次循环找出最大
#include stdio.h
int main() {int array [8]{4,1,6,8,2,3,9,5};int l sizeof (array)/sizeof (int);printf(冒泡排序前);for(int i0;il;i){printf(%d ,array[i]);};for(int i 0;il;i){for(int j 0;jl-i-1;j){if(array[j]array[j1]){int temp array[j];array[j]array[j1];array[j1]temp;}}};printf(冒泡排序后);for(int i0;il;i){printf(%d ,array[i]);};return 0;
}
直接插入排序-O(n^2)
元素移动位置
#include stdio.h
int main() {int array [8]{1,5,6,4,3,2,9,8};int l sizeof (array)/sizeof (int);printf(插入排序前);for(int i0;il;i){printf(%d ,array[i]);};for(int i 1;il;i){//从第一个与前面已经排好序从第一个开始int j i-1;int temp array[i];while(j0array[j]temp){//循环判断比i位置大的都后移已经排好序可以直接后移动一位array[j1]array[j];j--;};//循环结束后的当前j的后一位是i位置的值array[j1]temp;};printf(插入排序后);for(int i0;il;i){printf(%d ,array[i]);};return 0;
}希尔排序-O(n^1.3~1.5)
按照距离d进行插入排序
#include stdio.h
void shellSort(int arr[], int n) {// 定义增量gapfor (int gap n / 2; gap 0; gap / 2) {// 对每个子数组进行插入排序for (int i gap; i n; i) {int temp arr[i];int ji-gap;while (j0arr[j]temp){arr[jgap]arr[j];jj-gap;}arr[jgap]temp;}}
}int main() {int arr[] {12, 34, 54, 2, 3};int n sizeof(arr) / sizeof(arr[0]);printf(Original array: );for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);shellSort(arr, n);printf(Sorted array: );for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;}归并排序-O(nlogn)
已尽排好序合并为一个例子a,b比较第一个谁大放入新合并数组依次比较
#include stdio.h
//合并方法
void
merge(int arr[], int left[], int left_size, int right[], int right_size) {int i 0, j 0, k 0;while (i left_size j right_size) {if (left[i] right[j]) {//先赋值//k,i在自增arr[k] left[i];} else {arr[k] right[j];}}//两个数组长度不一样剩余直接加while (i left_size) {arr[k] left[i];}while (j right_size) {arr[k] right[j];}
}
//分数组分为左数组右数组
void mergeSort(int arr[], int size) {if (size 2) {return;}int mid size / 2;int left[mid], right[size - mid];for (int i 0; i mid; i) {left[i] arr[i];}for (int i mid; i size; i) {right[i - mid] arr[i];}//继续分mergeSort(left, mid);mergeSort(right, size - mid);//先1234合并//12合并后整体与34和并后的整体在进行合并merge(arr, left, mid, right, size - mid);
}int main() {int arr[] {12, 34, 54, 2, 3};int size sizeof(arr) / sizeof(arr[0]);printf(Original array: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);mergeSort(arr, size);printf(Sorted array: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);return 0;
}快速排序O(nlogn)
//找第一个为基准比它大的在右边小的左边
//递归
#include stdio.h
void quickSort(int arr[], int left, int right) {if (left right) {return;}int pivot arr[left];int i left, j right;while (i j) {while (i j arr[j] pivot) {j--;}arr[i] arr[j];while (i j arr[i] pivot) {i;}arr[j] arr[i];}arr[i] pivot;quickSort(arr, left, i - 1);quickSort(arr, i 1, right);
}int main() {int arr[] {12, 34, 54, 2, 3};int size sizeof(arr) / sizeof(arr[0]);printf(Original array: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);quickSort(arr, 0, size - 1);printf(Sorted array: );for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);return 0;
}堆排序-O(nlogn)
大根堆根右孩子、左孩子
大根堆根右孩子、左孩子
步骤构建堆取根放数组最后取最后叶子节点放根调整堆
#include stdio.h
// 调整堆
void heapify(int arr[], int n, int i) {int largest i; // 初始化根节点索引为最大值int left 2 * i 1; // 左子节点索引int right 2 * i 2; // 右子节点索引// 如果左子节点比根节点大更新最大值索引if (left n arr[left] arr[largest]) {largest left;}// 如果右子节点比当前最大值大更新最大值索引if (right n arr[right] arr[largest]) {largest right;}// 如果最大值不是根节点交换它们的值并递归调整堆if (largest ! i) {int temp arr[i];arr[i] arr[largest];arr[largest] temp;heapify(arr, n, largest);}
}// 堆排序函数
void heapSort(int arr[], int n) {// 从最后一个非叶子节点开始逐个调整堆for (int i n / 2 - 1; i 0; i--) {heapify(arr, n, i);}// 从堆顶开始取出元素放到末尾并调整堆for (int i n - 1; i 0; i--) {int temp arr[0];arr[0] arr[i];arr[i] temp;heapify(arr, i, 0);}}int main() {int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr) / sizeof(arr[0]);printf(Original array: );for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);heapSort(arr, n);printf(Sorted array: );for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}查找算法
二分查找 折半查找又称二分查找是一种在有序数组中查找特定元素的搜索算法。通过每次与中间元素比较可以确定要查找的元素是在中间元素的左侧还是右侧从而将搜索范围减半直到找到目标元素或搜索范围为空。对于数组 a[12](15,26,34,39,45,56,58,63,74,76,83,94)1. 查找元素 34第一次比较中间元素是 3934小于39所以在左侧区间(15,26,34)查找。第二次比较中间元素是 2634大于26所以在区间(26,34)查找。第三次比较找到元素 34。总共比较次数3次。
2. 查找元素 56第一次比较中间元素是 3956大于39所以在右侧区间(45,56,58,63,74,76,83,94)查找。第二次比较中间元素是 5856小于58所以在区间(45,56)查找。第三次比较找到元素 56。总共比较次数3次。
3. 查找元素 58第一次比较中间元素是 3958大于39所以在右侧区间查找。第二次比较中间元素是 58找到元素 58。总共比较次数2次。
4. 查找元素 63第一次比较中间元素是 3963大于39所以在右侧区间查找。第二次比较中间元素是 5863大于58所以在区间(58,63,74,76,83,94)查找。第三次比较找到元素 63。总共比较次数3次。
5. 查找元素 94第一次比较中间元素是 3994大于39所以在右侧区间查找。第二次比较中间元素是 7694大于76所以在区间(76,83,94)查找。第三次比较找到元素 94。总共比较次数3次。#include stdio.hint binarySearch(int arr[], int left, int right, int target) {//首位值和尾位置while (left right) {//中间位置int mid left (right - left) / 2;if (arr[mid] target) {return mid;//如果目标小于中间尾部位置是中间位置减一} else if (arr[mid] target) {right mid - 1;//如果目标小于中间尾部位置是中间位置减一} else {left mid 1;}}return -1; //目标元素不存在}int main() {int arr[] {1, 3, 5, 7, 9};int n sizeof(arr) / sizeof(arr[0]);int target 5;int index binarySearch(arr, 0, n - 1, target);if (index -1) {printf(目标元素不存在\n);} else {printf(目标元素的下标为%d\n, index);}return 0;}二分查找判定树平衡树
每次选二分那个点的为根节点只有两个节点时选择第一个节点 栈
顺序表实现
#include stdio.h
#include stdbool.h
#include malloc.h
#define MAX_SIZE 10
typedef int ElemType;
typedef struct {ElemType data[MAX_SIZE];int top;
}Stack;
//初始化
void InitStack(Stack *stack){int length sizeof(stack-data)/ sizeof(ElemType);for (int i 0; i length; i) {stack-data[i]0;}stack-top-1;
}// 判断栈是否为空
int isStackEmpty(Stack *stack) {return stack-top -1;}// 判断栈是否已满
int isStackFull(Stack *stack) {return stack-top MAX_SIZE - 1;
}
// 入栈操作
void push(Stack *stack, int value) {if (isStackFull(stack)) {printf(栈已满\n);return;}stack-top;stack-data[stack-top] value;}// 出栈操作
int pop(Stack *stack) {if (isStackEmpty(stack)) {printf(栈已空\n);return -1;}int value stack-data[stack-top];stack-top--;return value;
}// 获取栈顶元素
int getTop(Stack *stack) {if (isStackEmpty(stack)) {printf(栈已空\n);return -1;}return stack-data[stack-top];
}int main() {//声明Stack s;//初始化InitStack(s);//入栈push(s,1);push(s,2);push(s,3);push(s,4);//获取栈顶printf(栈顶元素%d\n, getTop(s));//出栈printf(%d\n, pop(s));printf(%d\n, pop(s));printf(%d\n, pop(s));printf(%d\n, pop(s));return 0;
}链表实现
#include stdio.h
#include stdbool.h
#include malloc.h
typedef struct {int data;struct Node *next;
}Node;
//初始化
void InitStack(Node *head){head-data0;head-nextNULL;
}
//// 入栈操作--头插
void push(Node *stack, int e) {Node *temp (Node*)malloc(sizeof(Node));temp-datae;temp-nextstack-next;stack-nexttemp;
}// 出栈操作
int pop(Node *stack) {Node *tempstack-next;int valuetemp-data;stack-nexttemp-next;free(temp);return value;
}// 获取栈顶元素
int getTop(Node *stack) {if (stack NULL) {printf(空栈\n);return -1;}Node *temp stack-next;int value temp-data;return value;
}int main() {//声明Node s;//初始化InitStack(s);//入栈push(s,1);push(s,2);push(s,3);push(s,4);//获取栈顶printf(栈顶元素%d\n, getTop(s));//出栈printf(%d\n, pop(s));printf(%d\n, pop(s));printf(%d\n, pop(s));printf(%d\n, pop(s));return 0;
}优先级
假设表达式中允许包含 3种括号:圆括号、方括号和大括号。设计算法判断给定表达式中的括号是否正确配对。
#include stdio.h
#include stdlib.h #define MAX_SIZE 100 char expression[MAX_SIZE]; // 检查括号是否匹配
int isMatch(char a, char b) { if (a ( b )) return 1; if (a [ b ]) return 1; if (a { b }) return 1; return 0;
} // 检查表达式中的括号是否配对
int checkBrackets(char* exp) { int top -1; for (int i 0; exp[i]; i) { if (exp[i] ( || exp[i] [ || exp[i] {) { // 如果是左括号则入栈 if (top MAX_SIZE - 1) { printf(堆栈溢出表达式错误\n); return -1; } else { top; expression[top] exp[i]; } } else if (exp[i] ) || exp[i] ] || exp[i] }) { // 如果是右括号则检查栈顶元素是否与之匹配 if (top -1) { printf(表达式中的括号不匹配\n); return -1; } else if (!isMatch(expression[top], exp[i])) { printf(表达式中的括号不匹配\n); return -1; } else { top--; } } } // 如果栈为空则括号都匹配 if (top -1) { printf(表达式中的括号都匹配\n); return 1; } else { printf(表达式中的括号不匹配\n); return -1; }
} int main() { char exp[MAX_SIZE]; printf(请输入一个包含括号的表达式); fgets(exp, MAX_SIZE, stdin); // 从标准输入读取表达式 checkBrackets(exp); // 检查表达式中的括号是否配对 return 0;
}队列
循环队列数组实现
#include stdio.h
#define QUEUE_SIZE 5
//循环队列
typedef struct Queue {int data[QUEUE_SIZE];int front; // 队头索引int rear; // 队尾索引
} Queue;
// 初始化队列
void init(Queue* queue) {queue-front 0;queue-rear 0;
}// 判断队列是否为空
int is_empty(Queue* queue) {return queue-front queue-rear;
}// 判断队列是否已满
int is_full(Queue* queue) {return (queue-rear 1) % QUEUE_SIZE queue-front;
}// 入队操作
void enqueue(Queue* queue, int data) {if (is_full(queue)) {printf(队列已满\n);return;}queue-data[queue-rear] data;queue-rear (queue-rear 1) % QUEUE_SIZE;}// 出队操作
int dequeue(Queue* queue) {if (is_empty(queue)) {printf(队列为空\n);return -1; // 返回一个错误码表示队列为空}int data queue-data[queue-front];queue-front (queue-front 1) % QUEUE_SIZE;return data;}
int main (){Queue q;init(q);enqueue(q,1);enqueue(q,2);enqueue(q,3);enqueue(q,4);return 0;
}队列链表实现
#include stdio.h
#include stdlib.htypedef struct node {int data;struct node *next;
} Node;typedef struct queue {Node *front; // 队头指针Node *rear; // 队尾指针
} Queue;// 初始化队列
void init_queue(Queue *q) {q-front NULL;q-rear NULL;
}// 判断队列是否为空
int is_queue_empty(Queue *q) {return q-front NULL;}// 入队操作
void enqueue(Queue *q, int value) {Node *new_node (Node*) malloc(sizeof(Node));new_node-data value;new_node-next NULL;//空队列首尾指针都指向if (is_queue_empty(q)) {q-front new_node;q-rear new_node;} else {//原来尾指针指向的下一个是插入节点q-rear-next new_node;//现在尾部指针指向插入节点q-rear new_node;}}// 出队操作
int dequeue(Queue *q) {if (is_queue_empty(q)) {printf(Queue is empty!\n);return -1;}int value q-front-data;Node *temp q-front;//首指针现在指向是原来指向节点的下一个节点q-front q-front-next;free(temp);return value;}// 获取队头元素
int get_front(Queue *q) {if (is_queue_empty(q)) {printf(Queue is empty!\n);return -1;}return q-front-data;}// 获取队列长度
int get_queue_length(Queue *q) {int length 0;Node *current q-front;while (current ! NULL) {length;current current-next;}return length;}// 打印队列元素
void print_queue(Queue *q) {if (is_queue_empty(q)) {printf(Queue is empty!\n);return;}printf(Queue elements: );Node *current q-front;while (current ! NULL) {printf(%d , current-data);current current-next;}printf(\n);}
int main (){Queue q;init_queue(q);enqueue(q,1);enqueue(q,2);enqueue(q,3);enqueue(q,4);printf(现在队头%d\n, get_front(q));printf(现在长度%d\n, get_queue_length(q));//出队dequeue(q);printf(现在队头%d\n, get_front(q));printf(现在长度%d\n, get_queue_length(q));return 0;
}树
二叉树顺序实现
在C语言中可以使用数组来存储二叉树。一般来说二叉树在数组中的存储方式是基于二叉树的层序遍历。对于任意一个节点如果它在数组中的下标为i那么它的左孩子的下标就是2*i1右孩子的下标就是2*i2
数组下标0开始
根0左孩子1右孩子2
这种方式有一个缺点那就是对于空节点也要分配存储空间造成空间的浪费。在上述例子中我们为8个节点分配了空间但实际上只有7个节点。
二叉树链表实现
满二叉树一个二叉树如果每一个层级的节点数都达到最大则这个二叉树就是满二叉树。也就是说每个节点要么是叶节点没有子节点要么就有两个子节点。这种类型的二叉树具有最大的节点数对于给定的层数。也就是说对于任何一层i节点的数量是2^i。
完全二叉树对于深度为h的二叉树如果第0层至第h-1层的节点数达到最大且第h层所有的节点都连续集中在最左边那么这就是一棵完全二叉树。也就是说完全二叉树除了最底层外其它各层的节点数都达到最大且最底层尽可能地向左填充。
#include stdio.h
#include stdlib.h
//定义节点
typedef struct node {int data;struct node *left;struct node *right;
} Node;
//创建节点
Node * CreateNode(int e){Node *node (Node *)malloc(sizeof(Node));node-datae;node-leftNULL;node-rightNULL;return node;
}
//插入二叉树
Node *InsertNode(Node *tree,int e){//父节点为空if(treeNULL){return CreateNode(e);}else if(etree-data){ //左孩子值比父节点的值小,tree-left InsertNode(tree-left,e);}else{ //右孩子值比父节点的值大tree-right InsertNode(tree-right,e);}
}
//先序遍历--根左右
void preorder_traversal(Node *tree){if(tree ! NULL){printf(%d ,tree-data);preorder_traversal(tree-left);preorder_traversal(tree-right);}
}
//中序遍历--左根右
void inorder_traversal(Node *root) {if (root ! NULL) {inorder_traversal(root-left);printf(%d , root-data);inorder_traversal(root-right);}
}// 后序遍历二叉树
void postorder_traversal(Node *root) {if (root ! NULL) {postorder_traversal(root-left);postorder_traversal(root-right);printf(%d , root-data);}}
//求树的深度
int TreeDeep(Node *root)
{int deep0;if(root!NULL){//求左右子树的深度int leftdeepTreeDeep(root-left);int rightdeepTreeDeep(root-right);//比较左右子树子树深度加上根总深度deepleftdeeprightdeep?leftdeep1:rightdeep1;}return deep;
}
//采用深度优先搜索获得二叉树的深度
int getDepth(Node* root) {if (root NULL) {return 0;}int level 1;Node* current root;while(current-left ! NULL ) {level;if(current-left ! NULL) {current current-left;} else {break;}}levellevel1;return level;}
//递归获得二叉树的总节点
int countNodes(Node * root){if(rootNULL){return 0;}//总结点根节点左子树节点右子树节点return 1 countNodes(root-left) countNodes(root-right);
}
//计算叶子节点个数
int countYNodes(Node * root){if(root NULL){return 0;}else if(root-left NULL root-right NULL){return 1;}return countNodes(root-left) countNodes(root-right);
}int main (){Node *tree CreateNode(1);tree InsertNode(tree,2);tree InsertNode(tree,3);tree InsertNode(tree,4);tree InsertNode(tree,5);tree InsertNode(tree,6);tree InsertNode(tree,7);tree InsertNode(tree,8);printf(\n先序遍历:);preorder_traversal(tree);printf(\n中序遍历:);inorder_traversal(tree);printf(\n后序遍历:);postorder_traversal(tree);int deep TreeDeep(tree);printf(树的深度%d\n,deep);int deep1 getDepth(tree);printf(树的深度%d\n,deep1);int countcountNodes(tree);printf(总节点:%d,count);int ycount countYNodes(tree);printf(叶子节点个数%d,ycount);return 0;
}二叉树查找最小值
char findMin(TreeNode* root) { // 如果根节点为空返回空字符或者你可以定义一个默认值 if (root NULL) { return \0; } // 当前节点的值 char current root-val; // 如果左子树存在递归查找左子树的最小值 if (root-left ! NULL) { char left_min findMin(root-left); // 如果左子树的最小值小于当前值则当前最小值应为左子树的最小值 if (left_min current) { current left_min; } } // 如果右子树存在递归查找右子树的最小值 if (root-right ! NULL) { char right_min findMin(root-right); // 如果右子树的最小值小于当前值则当前最小值应为右子树的最小值 if (right_min current) { current right_min; } } // 返回最小值 return current;
}二叉排序树二叉查找树BST
左子树所有节点值小于根节点值小于右子树所有节点值
中序遍历就是一个有序
已知后序画图
例子
一棵以字母为关键字的二叉排序树的后序遍历序列为:ACDBFIJHGE
完成以下问题
(1)画出该二叉排序树:
(2)计算在等概率下查找成功的平均比较次数:
(3)计算在等概率下查找不成功的平均比较次数
二叉排序树中序就是有序ABCDEFGHIJ
中后画出 查找成功的平均查找长度为∑本层高度*本层元素个数/节点总数
查找不成功的平均查找长度∑本层高度*本层补上的叶子个数/补上的叶子总数 平衡二叉树AVL
左子树所有节点值小于根节点值小于右子树所有节点值,左右子树高度差小于等于1
why:使它的平均查找次数:以2为底的对数
四种调整
LL A的左孩子的左子树插入节点导致不平衡
LR: A的左孩子的右子树插入节点导致不平衡
RR: A的右孩子的右子树插入节点导致不平衡
RL: A的右孩子的左子树插入节点导致不平衡
例子
给出序列(5893247)构造平衡二叉树的过程
红黑树
B树
B树
图
无向图
有向图
邻接矩阵转无向图
邻接矩阵 做辅助判断有几个顶点 构建无向图 深度优先搜索随便写个人习惯选择权重最小
例子
链栈结构
在链栈的实现中我们通常需要一个指针来指向栈顶元素。考虑到这个需求下面分析这三种结构的适用性(1)带头节点的单链表这种结构适合用于链栈。由于链栈通常需要在栈顶进行操作如入栈、出栈而头节点可以用来指向栈顶元素这样可以方便地进行栈操作。另外头节点不存储数据可以作为一个哨兵节点简化链表为空或满的判断条件。(2)不带头结点的循环单链表这种结构也可以用于链栈但是相对于带头节点的单链表它实现起来更为复杂。因为循环链表的头结点就是栈顶元素对于空栈的判断以及插入和删除操作都需要更为复杂的指针操作。此外如果链表为空还需要特殊处理。(3)带头节点的双链表双链表在插入和删除时需要维护两个方向的指针这会增加实现的复杂性。而且对于链栈来说通常只需要一个方向的链表就足够了即只需要从栈顶到栈底的链表。因此使用双链表有些过于复杂而且可能会浪费空间。综上所述(1)带头节点的单链表是最适合用于链栈的存储结构。它的实现相对简单而且能够方便地进行栈操作。
