西南科技大学814考研二

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(l<0||l>MAX_SIZE){return false;}for(int i=0;i<l;i++){L->data[i]=array[i];L->length++;}return true;
}
//打印顺序表里面的元素
void printSeqList(SeqList *L){for(int i=0;i<L->length;i++){printf("%d ",L->data[i]);};
}
//获得顺序表长度
int SeqListSize(SeqList *q){return q->length;
}
//尾插
bool tailInsert(SeqList *L,ElemType e){if(L->length+1>MAX_SIZE){return false;}else{L->data[L->length]=e;L->length=L->length+1;return true;}
}
//i位置插入e
bool SeqListInsert(SeqList *L,int i,ElemType e){if(i<1||i>MAX_SIZE){return false;}else{for(int j = L->length;j>=i;j--){L->data[j]=L->data[j-1];}L->data[i-1]=e;L->length=L->length+1;}
}
//i位置删除e
bool SeqListDelete(SeqList *L,int i){if(i<1||i>MAX_SIZE){return false;}else{for(int j = i-1;j<L->length;j++){L->data[j]=L->data[j+1];}L->length=L->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->next=NULL;
}
//数组创建顺序表
LNode *ArrayToList(ElemType array[],int l){// 如果数组为空，则返回空链表if (array == NULL || l == 0) {return NULL;}//定义头节点LNode *head=(LNode*)malloc(sizeof(LNode));head->data=0;head->next=NULL;LNode *temp=head;for(int i=0;i<l;i++){LNode *Node=(LNode*)malloc(sizeof(LNode));Node->data=array[i];Node->next=NULL;temp->next=Node;temp=Node;}//不带头单链表，所以返回头的下一个节点return head->next;
}
//单链表长度
int ListSize(LNode *L){LNode *p=L;int length = 0;while(p!=NULL){length++;p=p->next;}return length;
}
//头插
void InsertAtHead(LNode **L,ElemType e){if(e==NULL){printf("插入数据为空");}else if(L==NULL){LNode *Node = (LNode*)malloc(sizeof(LNode));Node->data=e;Node->next=NULL;L=&Node;}else{LNode *Node = (LNode*)malloc(sizeof(LNode));Node->data=e;Node->next=*L;*L=Node;}
}
//头删
void DeletedFirstNode(LNode **L){if(L==NULL){printf("单链表为空！");}else{LNode *first=*L;*L=first->next;free(first);}
}
//尾插
void InsertAtTail(LNode **L,ElemType e){if(e==NULL){printf("插入数据为空");}else if(L==NULL){LNode *Node = (LNode*)malloc(sizeof(LNode));Node->data=e;Node->next=NULL;*L=&Node;}else{LNode *Node = (LNode*)malloc(sizeof(LNode));Node->data=e;Node->next=NULL;//找到原来最后一个LNode *P = *L;while (P->next!=NULL){P=P->next;}P->next=Node;}
}
//尾删
void DeleteLastNode(LNode **L){if(L==NULL){printf("单链表为空");}else{LNode *prev = NULL;LNode *curr = *L;while (curr->next!=NULL){prev=curr;curr=curr->next;}prev->next=NULL;free(curr);}
}
//第i位置插入
void InsertAtI(LNode **L,int i,ElemType e){if(i>ListSize(*L)+1||i<=0){printf("插入位置必须大于0小等于单链表长度\n");}else if(i==1){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){p=q;q=p->next;index++;}LNode *s = (LNode *)malloc(sizeof(LNode));s->data=e;s->next=q;p->next=s;}}
//第i个位置删除
void DeleteAtI(LNode **L,int i){if(i>ListSize(*L)||i<1){printf("插入位置必须大于0小等于单链表长度");}else{int index = 1;LNode *p = NULL;LNode * q = *L;while (index != i){p=q;q=p->next;index++;}p->next=q->next;q->next=NULL;free(q);}}//打印单链表里面的元素
void PrintList(LNode *L){LNode *p = L;while (p!=NULL){printf("%d ",p->data);p=p->next;}
}// 得到第i个位置的元素
void  getAtINodeData(LNode **L,int i){if(i<1||i> ListSize(*L)){printf("查找位置不存在");}else{LNode *p=*L;int index = 1;while(index<i&&p->next!=NULL){p=p->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->data==e){break;}index++;t=t->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->next=NULL;
}
//创建头节点
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->data=0;head->next=NULL;LNode *temp=head;for(int i=0;i<l;i++){LNode *Node=(LNode*)malloc(sizeof(LNode));Node->data=array[i];Node->next=NULL;temp->next=Node;temp=Node;}//带头节点，返回头节点return head;
}
//单链表长度
int ListSize(LNode *head){LNode *p=head->next;int length = 0;while(p!=NULL){length++;p=p->next;}return length;
}
//打印单链表里面的元素
void PrintList(LNode *head){LNode *p = head->next;while (p!=NULL){printf("%d ",p->data);p=p->next;}
}
//头插
void InsertAtHead(LNode *head,ElemType e){if(e==NULL){printf("插入数据为空");}else if(head==NULL){printf("单链表为空");}else{LNode *Node = (LNode*)malloc(sizeof(LNode));Node->data=e;Node->next=head->next;head->next=Node;}
}
//头删
void DeletedFirstNode(LNode *head){if(head==NULL){printf("单链表为空！");}else{LNode *first=head->next;head->next=first->next;first->data=NULL;free(first);}
}
//尾插
void InsertAtTail(LNode *head,ElemType e){if(e==NULL){printf("插入数据为空");}else if(head==NULL){printf("单链表为空！");}else{LNode *Node = (LNode*)malloc(sizeof(LNode));Node->data=e;Node->next=NULL;//找到原来最后一个LNode *p = head;while (p->next!=NULL){p=p->next;}p->next=Node;}
}
//尾删
void DeleteLastNode(LNode *head){if(head==NULL){printf("单链表为空");}else{LNode *prev = NULL;LNode *curr = head;while (curr->next!=NULL){prev=curr;curr=curr->next;}prev->next=NULL;free(curr);}
}
//第i位置插入
void InsertAtI(LNode *head,int i,ElemType e){if(i>ListSize(head)+1||i<=0){printf("插入位置必须大于0小等于单链表长度\n");}else if(i==1){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){p=q;q=p->next;index++;}LNode *s = (LNode *)malloc(sizeof(LNode));s->data=e;s->next=q;p->next=s;}}
//第i个位置删除
void DeleteAtI(LNode *head,int i){if(i>ListSize(head)||i<1){printf("插入位置必须大于0小等于单链表长度");}else{int index = 1;LNode *p = NULL;LNode * q = head;while (index != i){p=q;q=p->next;index++;}p->next=q->next;q->next=NULL;free(q);}
}
// 得到第i个位置的元素
void  getAtINodeData(LNode *head,int i){if(i<1||i> ListSize(head)){printf("查找位置不存在");}else{LNode *p=head->next;int index = 1;while(index<i&&p->next!=NULL){p=p->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->data==e){break;}index++;t=t->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 i=0;i<l;i++){printf("%d ",array[i]);};for(int i = 0;i<l-1;i++){for(int j = i+1;j<l-i;j++){if(array[i]>array[j]){int temp =array[i];array[i]=array[j];array[j]=temp;}}};printf("选择排序后：");for(int i=0;i<l;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 i=0;i<l;i++){printf("%d ",array[i]);};for(int i = 0;i<l;i++){for(int j = 0;j<l-i-1;j++){if(array[j]>array[j+1]){int temp =array[j];array[j]=array[j+1];array[j+1]=temp;}}};printf("冒泡排序后：");for(int i=0;i<l;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 i=0;i<l;i++){printf("%d ",array[i]);};for(int i = 1;i<l;i++){//从第一个与前面已经排好序，从第一个开始int j = i-1;int temp = array[i];while(j>=0&&array[j]>temp){//循环判断比i位置大的都后移（已经排好序可以直接后移动一位）array[j+1]=array[j];j--;};//循环结束后的当前j的后一位是i位置的值array[j+1]=temp;};printf("插入排序后：");for(int i=0;i<l;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 j=i-gap;while (j>=0&&arr[j]>temp){arr[j+gap]=arr[j];j=j-gap;}arr[j+gap]=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);//先1，2；3，4；合并//1，2合并后整体与3，4和并后的整体在进行合并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;
}

查找算法

二分查找

1. 折半查找，又称二分查找，是一种在有序数组中查找特定元素的搜索算法。通过每次与中间元素比较，可以确定要查找的元素是在中间元素的左侧还是右侧，从而将搜索范围减半，直到找到目标元素或搜索范围为空。对于数组 a[12]=(15,26,34,39,45,56,58,63,74,76,83,94)：1. 查找元素 34：第一次比较，中间元素是 39，34小于39，所以在左侧区间(15,26,34)查找。第二次比较，中间元素是 26，34大于26，所以在区间(26,34)查找。第三次比较，找到元素 34。总共比较次数：3次。
   2. 查找元素 56：第一次比较，中间元素是 39，56大于39，所以在右侧区间(45,56,58,63,74,76,83,94)查找。第二次比较，中间元素是 58，56小于58，所以在区间(45,56)查找。第三次比较，找到元素 56。总共比较次数：3次。
   3. 查找元素 58：第一次比较，中间元素是 39，58大于39，所以在右侧区间查找。第二次比较，中间元素是 58，找到元素 58。总共比较次数：2次。
   4. 查找元素 63：第一次比较，中间元素是 39，63大于39，所以在右侧区间查找。第二次比较，中间元素是 58，63大于58，所以在区间(58,63,74,76,83,94)查找。第三次比较，找到元素 63。总共比较次数：3次。
   5. 查找元素 94：第一次比较，中间元素是 39，94大于39，所以在右侧区间查找。第二次比较，中间元素是 76，94大于76，所以在区间(76,83,94)查找。第三次比较，找到元素 94。总共比较次数：3次。
   

#include <stdio.h>int 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->data=0;head->next=NULL;
}
//// 入栈操作--头插
void push(Node *stack, int e) {Node *temp = (Node*)malloc(sizeof(Node));temp->data=e;temp->next=stack->next;stack->next=temp;
}// 出栈操作
int pop(Node *stack) {Node *temp=stack->next;int value=temp->data;stack->next=temp->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.h>typedef 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*i+1，右孩子的下标就是2*i+2

数组下标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->data=e;node->left=NULL;node->right=NULL;return node;
}
//插入二叉树
Node *InsertNode(Node *tree,int e){//父节点为空if(tree==NULL){return CreateNode(e);}else if(e<=tree->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 deep=0;if(root!=NULL){//求左右子树的深度int leftdeep=TreeDeep(root->left);int rightdeep=TreeDeep(root->right);//比较左右子树，子树深度加上根=总深度deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;}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;}}level=level+1;return level;}
//递归获得二叉树的总节点
int countNodes(Node * root){if(root==NULL){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 count=countNodes(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的右孩子的左子树插入节点导致不平衡

例子：

给出序列(5，8，9，3，2，4，7)构造平衡二叉树的过程

红黑树

B树

B+树

图

无向图：

有向图：

邻接矩阵转无向图

邻接矩阵

做辅助判断有几个顶点

构建无向图

深度优先搜索随便写，个人习惯选择权重最小

例子

链栈结构

在链栈的实现中，我们通常需要一个指针来指向栈顶元素。考虑到这个需求，下面分析这三种结构的适用性：(1)带头节点的单链表：这种结构适合用于链栈。由于链栈通常需要在栈顶进行操作（如入栈、出栈），而头节点可以用来指向栈顶元素，这样可以方便地进行栈操作。另外，头节点不存储数据，可以作为一个哨兵节点，简化链表为空或满的判断条件。(2)不带头结点的循环单链表：这种结构也可以用于链栈，但是相对于带头节点的单链表，它实现起来更为复杂。因为循环链表的头结点就是栈顶元素，对于空栈的判断，以及插入和删除操作都需要更为复杂的指针操作。此外，如果链表为空，还需要特殊处理。(3)带头节点的双链表：双链表在插入和删除时，需要维护两个方向的指针，这会增加实现的复杂性。而且，对于链栈来说，通常只需要一个方向的链表就足够了（即只需要从栈顶到栈底的链表）。因此，使用双链表有些过于复杂，而且可能会浪费空间。综上所述，(1)带头节点的单链表是最适合用于链栈的存储结构。它的实现相对简单，而且能够方便地进行栈操作。