西南科技大学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)带头节点的单链表是最适合用于链栈的存储结构。它的实现相对简单，而且能够方便地进行栈操作。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/196088.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

数据结构02附录01：顺序表考研习题[C++]

数据结构02附录01：顺序表考研习题[C++]

图源&#xff1a;文心一言 考研笔记整理~&#x1f95d;&#x1f95d; 之前的博文链接在此&#xff1a;数据结构02&#xff1a;线性表[顺序表链表]_线性链表-CSDN博客~&#x1f95d;&#x1f95d; 本篇作为线性表的代码补充&#xff0c;每道题提供了优解和暴力解算法&#xf…
阅读更多...
基于LeNet实现手写体数字识别实验

基于LeNet实现手写体数字识别实验

目录 1 数据 1.1 数据预处理 2 模型构建 2.1 自定义算子实现 2.2 Pytorch框架实现 2.3 测试两个网络的运算速度 2.4 两个网络加载同样的权重&#xff0c;两个网络的输出结果是否一致&#xff1f; 2.5 计算模型的参数量和计算量。 3 模型训练 4 模型评价 5 模型预测 总结…
阅读更多...
unity 烘焙的时候出现模型没有光影的情况

unity 烘焙的时候出现模型没有光影的情况

unity 烘焙的时候出现模型没有光影的情况 1.模型没有设置生成光照贴图 需要勾选模型的生成光照贴图UVs,然后应用 2.游戏对象没有勾选静态选项 点开静态下拉列表&#xff0c;选择 contribute GI
阅读更多...
百面深度学习-图神经网络

百面深度学习-图神经网络

百面深度学习-图神经网络部分 什么是图神经网络&#xff1f; 图神经网络&#xff08;Graph Neural Networks&#xff0c;GNNs&#xff09;是深度学习模型的一个类别&#xff0c;专门设计来处理图结构数据。在图结构数据中&#xff0c;实体以节点&#xff08;vertex&#xff0…
阅读更多...
mac清除所有数据，不抹除的情况下如何实现？

mac清除所有数据，不抹除的情况下如何实现？

mac清除所有数据是一个比较复杂的任务&#xff0c;尤其是在不进行系统抹除的情况下。但是&#xff0c;如果你想要将mac完全恢复到出厂设置的状态&#xff0c;同时保留数据&#xff0c;本文将介绍一些可行的方法&#xff0c;帮助您在不抹除硬盘数据的情况下&#xff0c;让mac清除…
阅读更多...
for,while,do-while,死循环,嵌套循环,跳转关键字,随机数

for,while,do-while,死循环,嵌套循环,跳转关键字,随机数

1.for循环 public class ForDemo1 {public static void main(String[] args) {for (int i 0; i < 5; i) {System.out.println("HelloWorld");}System.out.println("--------------------------------------------");for (int i 1; i <10 ; i) {Sy…
阅读更多...
ChatGPT暂时停止开通puls，可能迎来封号高峰期

ChatGPT暂时停止开通puls，可能迎来封号高峰期

前言： 前两日，chat gpt的创始人 San Altman在网上发表了，由于注册的使用量超过了他们的承受能力，为了确保每个人的良好使用体验，chat gpt将暂时停止开通gpt plus。 情况： 前段时间好像出现了官网崩溃的情况，就连api key都受到了影响，所以现在就开始了暂时停止puls的注…
阅读更多...
百度飞浆环境安装

百度飞浆环境安装

前言&#xff1a; 在安装飞浆环境之前得先把pytorch环境安装好&#xff0c;不过关于pytorch网上教程最多的都是通过Anaconda来安装&#xff0c;但是Anaconda环境安装容易遇到安装超时导致安装失败的问题&#xff0c;本文将叫你如何通过pip安装的方式快速安装&#xff0c;其实这…
阅读更多...
Elasticsearch搜索分析引擎本地部署与远程访问

Elasticsearch搜索分析引擎本地部署与远程访问

文章目录 系统环境1. Windows 安装Elasticsearch2. 本地访问Elasticsearch3. Windows 安装 Cpolar4. 创建Elasticsearch公网访问地址5. 远程访问Elasticsearch6. 设置固定二级子域名 Elasticsearch是一个基于Lucene库的分布式搜索和分析引擎&#xff0c;它提供了一个分布式、多…
阅读更多...
打开PDF文件之后不能编辑,有哪些原因？

打开PDF文件之后不能编辑,有哪些原因？

打开PDF文件之后发现没有办法编辑PDF文件&#xff0c;都有哪些原因呢&#xff1f; 首先我们可以考虑一下&#xff0c;PDF文件中的内容是否是图片&#xff0c;如果确认是图片文件&#xff0c;那么我们想要编辑&#xff0c;就可以先使用PDF编辑器中的OCR扫描功能&#xff0c;将图…
阅读更多...
OpenCV快速入门：绘制图形、图像金字塔和感兴趣区域

OpenCV快速入门：绘制图形、图像金字塔和感兴趣区域

文章目录 前言一、绘制图形1. 绘制直线2. 绘制圆3. 绘制矩形4. 绘制椭圆5. 绘制多边形6. 绘制文字7. 可选参数8. 手工绘制OpenCV的logo 二、图像金字塔1. 高斯金字塔2. 拉普拉斯金字塔 三、感兴趣区域&#xff08;ROI&#xff09;数组切片方式OpenCV截取方式 总结 前言 OpenCV…
阅读更多...
Vatee万腾的科技征程：Vatee数字化创新的前沿探讨

Vatee万腾的科技征程：Vatee数字化创新的前沿探讨

在Vatee万腾的科技征程中&#xff0c;我们目睹了一场数字化创新的引领之旅&#xff0c;探讨了Vatee在科技前沿的独到见解。Vatee万腾不仅仅是一家科技公司&#xff0c;更是一支前行不辍的冒险队伍&#xff0c;通过不断突破自我&#xff0c;探索未知领域&#xff0c;引领着数字化…
阅读更多...
【Hello Go】Go语言工程管理

【Hello Go】Go语言工程管理

工程管理 工作区工作区介绍GOPATH设置 包自定义包main包main函数和init函数导入包点操作别名操作_操作 测试案例GOPATH配置go install使用 在我们实际的工作中 直接运用到编译器进行编译链接的场景少之又少 这是因为 在工程中不会只有一个源文件 并且源文件之间也有着相互依赖…
阅读更多...
数据科学家应该知道的 10 个高级深度学习架构！

数据科学家应该知道的 10 个高级深度学习架构！

一、介绍 跟上深度学习的最新进展变得非常困难。几乎每天都会出现深度学习的新创新或新应用。然而&#xff0c;这些进步大部分都隐藏在 ArXiv / Springer 等媒体上发表的大量研究论文中。 本文包含深度学习的一些最新进展以及 keras 库中的实现代码。我还提供了…
阅读更多...
浙大恩特客户资源管理系统CustomerAction.entphone；.js 接口任意文件上传漏洞复现 [附POC]

浙大恩特客户资源管理系统CustomerAction.entphone；.js 接口任意文件上传漏洞复现 [附POC]

文章目录 浙大恩特客户资源管理系统CustomerAction.entphone;.js 接口任意文件上传漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 0x06 修复建议 浙大恩特客户资源管理系统CustomerAction.entphone;.js 接口任…
阅读更多...
Apache Doris (五十四）： Doris Join类型 - Bucket Shuffle Join

Apache Doris (五十四）： Doris Join类型 - Bucket Shuffle Join

🏡 个人主页：IT贫道_大数据OLAP体系技术栈,Apache Doris,Clickhouse 技术-CSDN博客 🚩 私聊博主：加入大数据技术讨论群聊，获取更多大数据资料。 🔔 博主个人B栈地址：豹哥教你大数据的个人空间-豹哥教你大数据个人主页-哔哩哔哩视频 目录
阅读更多...
2023/11/15JAVA学习(线程池,Executors,网络编程,InetAddress,UDP,TCP,DatagramSocket)

2023/11/15JAVA学习(线程池,Executors,网络编程,InetAddress,UDP,TCP,DatagramSocket)

如何多开一个程序
阅读更多...
【测试功能篇 01】Jmeter 压测接口最大并发量、吞吐量、TPS

【测试功能篇 01】Jmeter 压测接口最大并发量、吞吐量、TPS

压力测试&#xff0c;我们针对比较关键的接口&#xff0c;可以进行相应的压力测试&#xff0c;主要还是测试看看接口能抗住多少的请求数&#xff0c;TPS稳定在多少&#xff0c;也就是吞吐量多少 安装 Jmeter的安装很简单&#xff0c;官网下载地址 http://jmeter.apache.org/ &…
阅读更多...
笔记53：torch.nn.rnn() 函数详解

笔记53：torch.nn.rnn() 函数详解

参数解释&#xff1a; &#xff08;1&#xff09;input_size()&#xff1a;即输入信息 Xt 的每个序列的独热编码向量的长度&#xff0c;即 len(vocab) &#xff08;2&#xff09;hidden_size()&#xff1a;即隐变量 h 的维度&#xff08;维度是多少&#xff0c;就代表用几个数…
阅读更多...
go语言学习之旅之Go语言数据类型

go语言学习之旅之Go语言数据类型

学无止境&#xff0c;今天学习Go 语言数据类型 Go&#xff08;或Golang&#xff09;是一种静态类型语言&#xff0c;这意味着变量的数据类型必须显式声明&#xff0c;并且在运行时不能更改。以下是Go中的一些基本数据类型&#xff1a; 这里仅介绍最常用的类型 数值类型: int: …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023