数据结构代码合集
一、排序算法
1、插入排序
1.1 直接插入排序
void InsertSort(int A[],int n){int temp,i,j; for( i = 1;i<n;i++){ //外循环，每个元素都要进行排序 if(A[i-1]>A[i]){ //前面元素比后面元素大的话 temp = A[i];for( j = i-1; A[j]>temp && j>=0;j--){A[j+1] = A[j];}}//该趟排序结束找到temp该插入的位置A[j + 1] = temp; }
}1.2、折半查找排序（直接插入算法的改进）
void sort(int A[], int n) {int mid, temp, j;for (int i = 1; i < n; i++) {temp = A[i];int low = 0;int high = i - 1; // 注意是 i-1while (low <= high) { // 注意是 <=保证稳定性mid = (low + high) / 2;if (A[mid] > temp) { //表示插入元素在左边high = mid - 1;} else {low = mid + 1;}}将low到i-1的元素全部右移for (j = i - 1; j >= low; j--) {A[j + 1] = A[j];}A[low] = temp;}
}
1.3、希尔排序
void ShellSort(int A[], int n) {int i,temp,j,d;for(d = n/2;d>=1;d = d/2){ //每次循环的增量 for(i=d;i<n;i++){ //每组循环 temp = A[i];for(j = i;j>=d && A[j-d] > temp;j-=d){A[j] = A[j-d];} A[j] = temp;}}
}2、交换排序
2.1 冒泡排序
void Swap(int &a, int &b) {int temp = a;a = b;b = temp;
}
void BubbleSort(int A[], int n) {int i ,j;bool flag;for( i = n-1;i>=0;i--){flag = false;for(j = 0;j<i;j++){if(A[j] < A[j+1]){ //冒小泡 >就是冒大泡，大的在后面 Swap(A[j],A[j+1]);flag = true;}}if(flag == false){break;}}
}
2.2 快速排序
int Partition(int A[],int low,int high){int pivot = A[low];while(low < high){while(low < high && A[high] >= pivot){high --;}A[low] = A[high];while(low < high && A[high] <= pivot){low++;}A[high] = A[low];}A[low] = pivot;return low;
}void QuickSort(int A[],int low,int high) {if(low < high){int pivotos = Partition(A,low,high);QuickSort(A,low,pivotos-1);QuickSort(A,pivotos+1,high);}
}3、选择排序
3.1 简单选择排序
void Swap(int &a, int &b) {int temp = a; a = b;b = temp;
}void SelectSort(int A[], int n) {for (int i = 0; i < n - 1; i++) { //遍历数组，直到倒数第二个元素。int min = i; // 记录此轮选择的最小元素的索引for (int j = i + 1; j < n; j++) { //遍历当前未排序的部分（即从索引i+1到n-1），寻找最小元素。if (A[j] < A[min]) {min = j; // 更新最小元素的位置}}// 交换选中的最小元素到排序序列的前端if (min != i) {Swap(A[i], A[min]); // 传递数组元素的地址}}
}3.2 堆排序
//先调整以k为根节点的树成为大根堆
void HeadJust(int A[],int k,int n){int temp = A[k];//1.找到该节点的左右孩子中最大的那个 for(int i = 2*k;i<=n;i*=2){if(i<n && A[i+1] > A[i]){i++;}//2.找到更大的元素后判断最大位置的元素和k位置上的元素大小 if(temp >=A[i]){break;} else{//3.将该位置的元素赋值到k位置上A[k] = A[i];k = i; //因为i位置上的元素已经保存到k位置上了因此这里需要将k指向i位置，以该节点为根节点继续调整 } }A[k] = temp; //k位置不存在左右孩子因此将元素放到K位置
} //确定k
void build(int A[],int n){for(int i = n/2;i>=1;i--){ //因为数组的开始下标是1HeadJust(A,i,n); }
}//堆排序
void sort(int A[],int n){build(A,n);for(int i = n;i>1;i--){ swap(A[i],A[1]);HeadJust(A,1,i-1); //1是最大的元素，和最小的元素交换位置 }
} 4、归并排序
int* B = (int *)malloc(10 * sizeof(int)); // 辅助数组B// 合并两个有序数组的函数
void Merge(int A[], int low, int mid, int high) {int i, j, k;// 将A中所有元素复制到B中for (k = low; k <= high; k++) {B[k] = A[k];}// 使用for循环将较小值复制到A中for (i = low,j = mid + 1, k = i; i <= mid && j <= high; k++) {if (B[i] <= B[j]) {A[k] = B[i++];} else {A[k] = B[j++];}}// 复制剩余的元素while (i <= mid) {A[k++] = B[i++];}while (j <= high) {A[k++] = B[j++];}
}// 归并排序函数
void MergeSort(int A[], int low, int high) {if (low < high) {int mid = (low + high) / 2;// 对左半部分归并排序MergeSort(A, low, mid);// 对右半部分归并排序MergeSort(A, mid + 1, high);// 归并Merge(A, low, mid, high);}
}
5、基数排序（略）
二、查找
1、顺序查找和折半查找
1.1 折半查找
int Binary_Search(int A[], int n, int x) {int low = 0;int high = n - 1;int mid;while (low <= high) {mid = (low + high) / 2;if (A[mid] == x) {return mid;} else if (A[mid] > x) {high = mid - 1;} else {low = mid + 1;}}return -1;
}2、树形查找
2.1 二叉排序树（BST）
二叉排序树非递归算法查找
BiTree BST_Search(BiTree T,int key){while(T != NULL && key != T->data){if(key < T->data){ //去左子树查找 T = T->lchild; }else{T = T->rchild;}}return T;
} 二叉排序树的递归查找
//BST中序遍历是有序的,先序后序都行
BiTree BST_Search(BiTree T,int key){if(T == NULL){return NULL; } BST_Search(T->lchild,key);if(T->data == key){return T;}BST_Search(T->rchild,key);
}二叉排序树的递归插入
int BST_Insert(BiTree &T,int key){if(T == NULL){T = new BiTNode;T->data = key;T->rchild = T->lchild = NULL;return 1;}else if(key == T->data){return 0; //存在相同值的节点插入失败 }else if(key < T->data){return BST_Insert(T->lchild,key);} else{return BST_Insert(T->rchild,key);}
} 二叉排序树的非递归插入
不想写，暂略。
判断给定的二叉树是不是二叉排序树
int pre = -100; //记忆指针
int BST_Judge(BiTree T){int L,R;if(T == NULL){return 1; //空树也是二叉排序树 } L = BST_Search(T->lchild,key);if(L == 0 || T->data < pre){ //若左子树返回0或者前驱大于当前结点 return 0;}pre = T->data; R = BST_Search(T->rchild,key);return R;
}如果不好想的话，可以中序遍历放到数组中，然后挨个比较。
int data[100] = {0}; // 假设数组足够大
int index = 0;
void Mid(BiTree T) {if (T == NULL) {return; // 空树也是二叉排序树}Mid(T->lchild);data[index++] = T->data;Mid(T->rchild);
}bool Judge_BST() {for (int i = 0; i < index - 1; i++) {if (data[i] >= data[i + 1]) {return false; // 不是二叉排序树}}return true; // 是二叉排序树
}求二叉排序树中最大值和最小值
//最大值在最右边
ElemType getMax(BiTree T){if(T->rchild != NULL){T = T->rchild;}return T->data;
}//最小值在最左边
ElemType getMin(BiTree T){if(T->lchild != NULL){T = T->lchild;}return T->data;
}想不到的话还能用数组。
// 中序遍历二叉树，并将元素存储到数组中
ElemType data[100] = {0};
int index = -1;
void Mid(BiTree T) {if (T == NULL) {return;} else {Mid(T->lchild);data[++index] = T->data;Mid(T->rchild);}
}void getMaxAndMin(){cout<<"最小值是:"<<data[0]<<" 最大值是:"<<data[index];
}从大到小输出二叉排序树中值不小于K的元素
还是使用数组。详细过程略 。
2.2 二叉平衡树
判断二叉树是不是二叉平衡树
//求二叉树高度
int getHight(BiTree T){int hl,hr;if(T == NULL){return 0; }else{hl = getHight(T->lchild);hr = getHight(T->rchild);if(hl > hr){return hl+1; //1是当前节点本身高度 }else{return hr+1;}}
}//判断一颗二叉树是否为平衡二叉树
bool isBlance(BiTree T){int hight_l; //左子树高度int hight_r; //右子树高度 if(T == NULL){return true; //空树也是个平衡二叉树 }else{hight_l = getHight(T->lchild); //求左子树高度 hight_r = getHight(T->rchild); //求右子树高度 if(abs(hight_l-hight_r) <= 1){return isBlance(T->lchild) && isBlance(T->rchild);}else{ //根节点不是二叉树 return false;}}
}三、图
1、图的遍历
1.1 邻接矩阵
邻接矩阵的BFS
下面的BFS算法都适用于有向图和无向图的邻接矩阵
// 找某个顶点的第一个邻居
int firstNeighbor(Graph G, int v) {for (int i = 0; i < G.vexsnum; i++) {if (G.maxarcs[v][i] != maxweight) {return i; }}return -1; // 没有邻居时返回-1
}// 找到v1顶点除了邻居v2的其他邻居,返回的是第一个邻居的下标
int nextNeighbor(Graph G, int v1, int v2) {for (int i = v2 + 1; i < G.vexsnum; i++) {if (G.maxarcs[v1][i] != maxweight) {return i; }}return -1; // 没有其他邻居时返回-1
}// 访问标记数据
bool visited_BFS[100];// 广度优先遍历算法
void BFS(Graph G, int v) { visit(G.maxvexs[v]);visited_BFS[v] = true;Queue Q;initQueue(Q);push(Q, v);while (Q.front != Q.rear) {int u;pop(Q, u); for (int w = firstNeighbor(G, u); w >= 0; w = nextNeighbor(G, u, w)) { // 找到u顶点的全部的邻居if (!visited_BFS[w]) { visited_BFS[w] = true;visit(G.maxvexs[w]);push(Q, w);}} }
}// 广度优先遍历所有连通分量
void BFSTraverse(Graph G){for(int i = 0; i < G.vexsnum; ++i){visited_BFS[i] = false;}for(int i = 0; i < G.vexsnum; ++i){if(!visited_BFS[i]){BFS(G, i); // 传递顶点的索引}}
}邻接矩阵的DFS
同样下面的DFS算法都适用于有向图和无向图的邻接矩阵。
// 找某个顶点的第一个邻居
int firstNeighbor(Graph G, int v) {for (int i = 0; i < G.vexsnum; i++) {if (G.maxarcs[v][i] != maxweight) {return i; }}return -1; // 没有邻居时返回-1
}// 找到v1顶点除了邻居v2的其他邻居,返回的是第一个邻居的下标
int nextNeighbor(Graph G, int v1, int v2) {for (int i = v2 + 1; i < G.vexsnum; i++) {if (G.maxarcs[v1][i] != maxweight) {return i; }}return -1; // 没有其他邻居时返回-1
}//访问标记数组
bool visited_DFS[100];// 深度优先遍历算法
void DFS(Graph G, int v) {visited_DFS[v] = true;visit(G.maxvexs[v]);for (int w = firstNeighbor(G, v); w != -1; w = nextNeighbor(G, v, w)) {if (!visited_DFS[w]) {DFS(G, w);}}
}// 深度优先遍历所有连通分量
void DFSTraverse(Graph G){for(int i = 0; i < G.vexsnum; i++){visited_DFS[i] = false;}for(int i = 0; i < G.vexsnum; ++i){if(!visited_DFS[i]){DFS(G, i); // 传递顶点的索引}}
}1.2 邻接表
邻接表的BFS
// 找到某个顶点的第一个邻居
int firstNeighbor(Graph G, int v) {ArcNode *p = G.vertices[v].firstarc;if (p) return p->adjvex;return -1; // 没有邻居时返回-1
}// 找到v1顶点除了邻居v2的其他邻居,返回的是第一个邻居的下标
int nextNeighbor(Graph G, int v, int v2) {ArcNode *p = G.vertices[v].firstarc;while (p) {if (p->adjvex != v2) return p->adjvex;p = p->nextarc;}return -1; // 没有其他邻居时返回-1
}// 广度优先遍历算法
void BFS(Graph G, int v) {visit(G.vertices[v].data);visited[v] = true;Queue Q;initQueue(Q);push(Q, v);while (Q.front != Q.rear) {int u;pop(Q, u);for (int w = firstNeighbor(G, u); w >= 0; w = nextNeighbor(G, u, w)) {if (!visited[w]) {visited[w] = true;visit(G.vertices[w].data);push(Q, w);}}}
}邻接表的DFS
// 找到某个顶点的第一个邻居
int firstNeighbor(Graph G, int v) {ArcNode *p = G.vertices[v].firstarc;if (p) return p->adjvex;return -1; // 没有邻居时返回-1
}// 找到v1顶点除了邻居v2的其他邻居,返回的是第一个邻居的下标
int nextNeighbor(Graph G, int v, int v2) {ArcNode *p = G.vertices[v].firstarc;while (p) {if (p->adjvex != v2) return p->adjvex;p = p->nextarc;}return -1; // 没有其他邻居时返回-1
}void DFS(Graph G, int v) {visited[v] = true;visit(G.vertices[v].data);for (int w = firstNeighbor(G, v); w >= 0; w = nextNeighbor(G, v, w)) {if (!visited[w]) {DFS(G, w);}}
}不管是邻接表还是邻接矩阵在实现上都差不多主要是firstNeibor和nextNeibor有点不同。
1.3 习题
判断一个无向图是不是一颗树
条件：无回路连通图或n-1边的连通图
// 访问标记数组
bool visited[max] = {false}; //访问标记数组 // 深度遍历（DFS）
void DFS(Graph &G, int v, int &vexnum, int &arcnum) {cout << v << " ";visited[v] = true;vexnum++; // 顶点数量++for (ArcNode* p = G.vertice[v].firstArc; p != NULL; p = p->nextArc) {if (!visited[p->index]) { // 判断当前p指针指向的节点是不是被访问过arcnum++; // 边++DFS(G, p->index, vexnum, arcnum);}}
} // 判断图是不是树
bool isTree(Graph &G, int start) {int vexnum = 0;int arcnum = 0;DFS(G, start, vexnum, arcnum);return vexnum == G.vexnum && arcnum == G.vexnum - 1;
} 四、树和二叉树
二叉树的先、中、后代码略。
1 二叉树求高度
//递归实现
int lh = 0;
int rh = 0;
int getHigh(BiTree T){if(T == NULL){return 0;}else{lh = getHigh(T->lchild);rh = getHigh(T->rchild);return 1+(lh>rh?lh:rh);}
} //求二叉树的高度（非递归）
int getHigh2(BiTree T){if( T == NULL){return 0;} int h = 0; //树的高度 //初始化队列Queue Q;Q.front= Q.rear = -1;int p = 0; //工作指针指向该层的最后一个节点，front指针和p指针重合的时候树的高度++ enqueue(Q,T);BiTree e; //出队接受元素 while(!isEmpty(Q)){ // 队列不空出队，然后将其孩子节点入队dequeue(Q,e); visit(e->data); if(e->lchild != NULL){enqueue(Q,e->lchild);}if(e->rchild != NULL){enqueue(Q,e->rchild);}//判断front和p是不是相等if(p == Q.front){p = Q.rear;h++;} }return h;
}非递归主要是判断当前是第几层。
2、计算二叉树的全部双分支节点个数
// 计算二叉树所有双分支结点个数的函数
int DNode(BiTree T) {if (T == NULL) {return 0;} else {// 判断当前节点是不是存在左右孩子节点int count = (T->lchild != NULL && T->rchild != NULL) ? 1 : 0;return count + DNode(T->lchild) + DNode(T->rchild);}
}3、求二叉树的叶子节点个数
//求叶子结点个数
int leavel(BiTree T){if(T ==NULL){return 0;}else{//判断当前节点的左后孩子是不是空.如果为空的话表示当前节点是个叶子节点 int lcount = (T->lchild == NULL && T->rchild == NULL)?1:0;return lcount+=leavel(T->lchild)+leavel(T->rchild);}
}4、求二叉树全部节点的个数
int AllNode(BiTree T) {// 函数出口if (T == NULL) {return 0;} else if (T->lchild == NULL && T->rchild == NULL) {// 如果节点是叶子节点return 1;} else {// 递归计算左子树和右子树的节点数，然后加1（当前节点）return 1 + AllNode(T->lchild) + AllNode(T->rchild);}
}5、先序遍历二叉树找第K个元素
// 二叉树先序遍历中第 K 个元素
int n = 0;
void preTree_K(BiTree T, int k) {if (T == NULL) {return;} else {++n; // 注意这个 n++ 一定是写在递归函数执行之前，要不然不准。// 判断当前的节点是不是第 k 个节点if (k == n) {printf("第%d个节点是%d", k, T->data);return;}preTree_K(T->lchild, k); // 递归遍历左子树preTree_K(T->rchild, k); // 递归遍历右子树}
}6、二叉树交换所有结点的左右子树
void swap(BiTree T){if(T == NULL){return;}else{BiTree p;p = T->lchild;T->lchild = T->rchild;T->rchild = p;swap(T->lchild);swap(T->rchild);}
}7、二叉树中打印值为X结点的所有祖先
int top = -1;
int p[20];
void allparent(BiTree T, ElemType x) {if (T == NULL) {return;} else {// 入栈++top;p[top] = T->data;// 先递归左子树allparent(T->lchild, x);// 如果当前节点是目标节点，则打印所有祖先if (T->data == x) {for (int i = 0; i <= top; i++) { // 注意这里应该是小于等于top，因为数组下标是从0开始的cout << p[i] << " ";}cout << endl;}// 再递归右子树allparent(T->rchild, x);// 出栈--top;}
}
8、给定结点在二叉排序树中的层次
int level_x(BiTree T, int x) {int level = 1; // 初始化层次计数器BiTree p = T; // 初始化工作指针为树的根节点if (T == NULL) {return -1; // 如果树为空，返回-1}while (p != NULL && p->data != x) { // 当前节点不为空且数据不等于要找的数据时循环if (x < p->data) { // 如果要找的数据小于当前节点的数据，向左子树移动p = p->lchild;} else { // 否则，向右子树移动p = p->rchild;}level++; // 每移动一次，层次计数器加1}if (p == NULL) {return -1; // 如果最终p为NULL，表示x不在树中，返回-1}return level; // 返回节点的层次
}9、判断是否为完全二叉树
bool is_Complete(BiTree T) {BiTree t = T;SqQueue q;initSqQueue(q); // 队列初始化if (T == NULL) {return true; // 如果树为空，返回true} else {push(q, t); // 根节点入队bool meetNull = false; // 用于标记是否遇到空节点while (!isEmpty(q)) { // 队列不空pop(q, t); // 根节点出队if (t == NULL) {meetNull = true; // 标记遇到了空节点} else {if (meetNull) { // 如果已经遇到过空节点，再次遇到非空节点，不是完全二叉树return false;}push(q, t->lchild); // 左右孩子入队push(q, t->rchild);}}}return true; // 所有检查通过，是完全二叉树
}10、逆层序遍历二叉树
void level(BiTree T) {if (T == NULL) {return;}SqQueue Q; // 初始化队列initSqQueue(Q);SqStack S; // 初始化栈initSqStack(S);BiTree e; // 接受出队元素pushSqQueue(Q, T); // 根节点入队while (!isEmptySqQueue(Q)) { // 当队列不为空时popSqQueue(Q, e); // 队头出队pushSqStack(S, e); // 队头入栈if (e->lchild) {pushSqQueue(Q, e->lchild); // 左孩子入队}if (e->rchild) {pushSqQueue(Q, e->rchild); // 右孩子入队}}while (!isEmptySqStack(S)) { // 当栈不为空时popSqStack(S, e); // 栈顶出栈printf("%d ", e->data); // 输出节点数据}
}11、递归求树的宽度
// 递归求树宽度
int width[10] = {0}; // 层数
void pre(BiTree T, int level) { // level 标注当前节点是第几层的if (T == NULL) {return;} else {// 第一次访问节点，当前层数的节点数+1width[level]++;pre(T->lchild, level + 1);pre(T->rchild, level + 1);}
}void getWidth(BiTree T) {int max = 0;pre(T, 0);for (int i = 0; i < 10; i++) {if (max < width[i]) {max = width[i];}}printf("二叉树的宽度是:%d", max);
}12、 满二叉树已知先序序列，求后序序列
13、 已知先序和中序建立二叉链表
// 定义创建二叉树的函数，接受先序和中序遍历数组及其索引范围
BiTree createTree(int pre[], int mid[], int l1, int h1, int l2, int h2) {// 如果先序或中序数组的索引范围无效，则返回NULL，表示没有树可以创建if (l1 > h1 || l2 > h2) {return NULL;}// 先创建根节点BiTree T = new BiTNode; // 分配新的二叉树节点T->data = pre[l1]; // 先序遍历的第一个元素是根节点的值// 在中序遍历中找到根节点的位置int i;for (i = l2; i <= h2; i++) {if (mid[i] == T->data) {break; // 找到根节点在中序遍历中的位置}}// 计算左子树和右子树的长度int left_len = i - l2; // 左子树的长度int right_len = h2 - i; // 右子树的长度// 递归创建左子树if (left_len != 0) {T->lchild = createTree(pre, mid, l1 + 1, l1 + left_len, l2, i - 1); // 先序和中序的左子树范围} else {T->lchild = NULL; // 如果没有左子树，则设置为空}// 递归创建右子树if (right_len != 0) {T->rchild = createTree(pre, mid, l1 + left_len + 1, h1, i + 1, h2); // 先序和中序的右子树范围} else {T->rchild = NULL; // 如果没有右子树，则设置为空}// 返回创建的二叉树的根节点return T;
}14、树与二叉树-以兄弟链表存储，用递归求树的深度
// 定义计算二叉树高度的函数，接受二叉树的根节点作为参数
int getHight(BiTree T) {int left; // 左子树的高度int right; // 右子树的高度// 如果树为空（即根节点为空），则高度为0if (T == NULL) {return 0;} else {// 递归计算左子树的高度left = getHight(T->lchild);// 递归计算右子树的高度right = getHight(T->rchild);}// 比较左右子树的高度，取较大的高度，并加1（当前节点的高度）if (left + 1 > right) {return left + 1; // 如果左子树的高度大于右子树，则返回左子树高度加1} else {return right + 1; // 如果右子树的高度大于或等于左子树，则返回右子树高度加1}
}15、 将给定的表达式树转中缀表达式
// 将给定的表达式树转换为中缀表达式
void convert(BiTree T, int deep) {// 如果当前节点为空，直接返回if (T == NULL) {return;}// 如果当前节点是叶子节点（没有左右子节点）else if (T->lchild == NULL && T->rchild == NULL) {// 输出叶子节点的数据cout << T->data;}// 如果当前节点不是叶子节点else {// 如果当前节点的深度大于1，输出左括号if (deep > 1) {cout << "(";}// 递归转换左子树，深度加1convert(T->lchild, deep + 1);// 输出当前节点的数据cout << T->data;// 递归转换右子树，深度加1convert(T->rchild, deep + 1);// 如果当前节点的深度大于1，输出右括号if (deep > 1) {cout << ")";}}
}两层加括号
16、中序线索二叉树找后序前驱
17、将叶节点按从左到右的顺序连成单链表
// 将二叉树的叶节点按从左到右的顺序链接成单链表
void Link(BiTree T, BiTree& Head, BiTree& tail) {// 如果当前节点不为空if (T) {// 如果当前节点是叶子节点（既没有左孩子也没有右孩子）if (T->lchild == NULL && T->rchild == NULL) {// 如果链表为空（还没有头节点）if (Head == NULL) {Head = T; // 当前节点成为链表的头节点tail = T; // 当前节点也成为链表的尾节点} else { // 如果链表不为空tail->rchild = T; // 将当前节点链接到链表的尾节点tail = T; // 更新尾节点为当前节点}}// 递归处理左子树Link(T->lchild, Head, tail); // 递归处理右子树Link(T->rchild, Head, tail);}
}18、求WPL
// 初始化加权路径长度为0
int wpl = 0;// 定义一个函数preTree，用于计算二叉树的加权路径长度（WPL）
int preTree(BiTree T, int dep) {// 如果当前节点为空，返回0，不增加路径长度if (T == NULL) {return 0;} else {// 如果当前节点是叶子节点if (T->lchild == NULL && T->rchild == NULL) {// 计算当前叶子节点的加权路径长度，并累加到wpl// 这里假设T->data存储的是字符形式的数字，需要转换为整数wpl += (dep - 1) * (T->data);}// 如果当前节点不是叶子节点，则递归计算左右子树的WPLelse {preTree(T->lchild, dep + 1); // 递归左子树，深度加1preTree(T->rchild, dep + 1); // 递归右子树，深度加1}}// 返回当前节点的加权路径长度return wpl;
}19、删除树中以x为根节点的子树，并释放空间
// 删除二叉树节点，并释放其占用的内存空间
void del(BiTree &T) {// 如果当前节点为空，直接返回，不进行任何操作if (T == NULL) {return;} else {// 递归删除当前节点的左子树del(T->lchild);// 递归删除当前节点的右子树del(T->rchild);// 释放当前节点的内存free(T);// 将当前节点指针设置为NULL，避免野指针T = NULL;}
}// 删除二叉树中所有以x为根节点的子树
void del_allx(BiTree &T, int x) {// 如果当前节点为空，直接返回，不进行任何操作if (T == NULL) {return;} else {// 判断当前节点是否是要删除的节点if (T->data == x) {// 如果是，递归调用del函数删除该节点及其所有子节点del(T);// 删除完成后返回，不再继续遍历return;}// 递归检查左子树中是否包含要删除的节点del_allx(T->lchild, x);// 递归检查右子树中是否包含要删除的节点del_allx(T->rchild, x);}
}20、寻找两个节点的公共祖先
// 定义一个函数findLCA，用于在二叉树中寻找两个节点p和q的最近公共祖先
BiTree findLCA(BiTree root, ElemType p, ElemType q) {// 如果当前节点为空，或者当前节点就是p或q，那么返回当前节点if (root == NULL || root->data == p || root->data == q) {return root;}// 递归在左子树中查找p和q的最近公共祖先BiTree left = findLCA(root->lchild, p, q);// 递归在右子树中查找p和q的最近公共祖先BiTree right = findLCA(root->rchild, p, q);// 如果在左右子树中都找到了目标节点，说明当前节点是p和q的最近公共祖先if (left != NULL && right != NULL) {return root;}// 如果只在一边找到了目标节点，那么返回找到的那一边的最近公共祖先// left != NULL ? left : right 是一个三元运算符，如果left不为空则返回left，否则返回rightreturn left != NULL ? left : right;
}想不到的话还有笨方法。
BiTree data[maxsize] = {NULL}; // 初始化一个数组，用于存储二叉树的节点，初始值设为NULL
int index = 0; // 用于数组data的下标，表示当前存储的节点位置// 定义一个函数levelOrder，用于进行二叉树的层序遍历，并找出两个节点p和q的最近公共祖先
void levelOrder(BiTree T, ElemType p, ElemType q) {// 初始化队列QQueue Q;Q.front = Q.rear = 0;int _p, _q; // 用于存储p和q节点在数组data中的下标// 如果根节点不为空，则将其入队if (T != NULL) {enqueue(Q, T);}// 当队列不为空时，进行循环while (!isEmpty(Q)) {BiTree node;// 从队列中出队一个节点dequeue(Q, node);// 将出队的节点存储到数组data中，并更新下标indexdata[++index] = node;// 如果当前节点的数据等于p，则记录p的下标if (node->data == p) {_p = index;}// 如果当前节点的数据等于q，则记录q的下标if (node->data == q) {_q = index;}// 如果当前节点不为空，则访问该节点，并将其左右孩子入队（如果它们不为空）if (node != NULL) {visit(node->data); // 访问该节点，例如打印节点数据if (node->lchild != NULL) {enqueue(Q, node->lchild);}if (node->rchild != NULL) {enqueue(Q, node->rchild);}}}// 通过下标计算p和q的最近公共祖先的下标while (_p != _q) {_p /= 2; // _p除以2，相当于在层序遍历的数组中向上移动一层_q /= 2; // _q除以2，同理}// 输出p和q的最近公共祖先的节点数据cout << p << "和" << q << "元素的祖先是:" << data[_p]->data << endl;
}五、串的基本操作
结构体
typedef struct str { // 顺序串的结构体char ch[MAXSIZE + 1];int length;
} str;1、赋值操作
// 定义一个函数StrAssign，用于将字符数组chs的值赋给串S
void StrAssign(str &S, char chs[]) {int i = 0; // 初始化索引变量i，用于遍历字符数组chs// 循环遍历字符数组chs，直到遇到字符串结束符'\0'while (chs[i] != '\0') {// 将字符数组chs中的字符逐个赋值给串S的数据成员chS.ch[i] = chs[i];// 索引i自增，移动到字符数组的下一个字符i++;}// 当循环结束时，索引i等于字符数组chs的长度// 将计算出的长度赋值给串S的长度成员lengthS.length = i;
}2、复制操作
// 定义一个函数StrCopy，用于将串T的值复制到串S中
void StrCopy(str &S, str &T) {// 使用for循环遍历串T中的每个字符for (int i = 0; i < T.length; i++) {// 将串T中的字符逐个复制到串S的对应位置S.ch[i] = T.ch[i];}// 在串S的字符数组的末尾添加字符串结束符'\0'，确保字符串正确结束S.ch[T.length] = '\0';// 将串T的长度复制到串S的长度成员中S.length = T.length;
}3、判断字符串是不是空串
// 判断字符串是不是空串
bool IsStrEmpty( str &S) {return S.length == 0;
}
4、比较操作
// 定义一个函数StrCompare，用于比较两个字符串S和T的大小
int StrCompare(str &S, str &T) {// 循环比较两个字符串中对应位置的字符for (int i = 0; i < S.length && i < T.length; i++) {// 如果S中的字符ASCII值大于T中的字符ASCII值，返回1if (S.ch[i] > T.ch[i]) return 1;// 如果S中的字符ASCII值小于T中的字符ASCII值，返回-1if (S.ch[i] < T.ch[i]) return -1;}// 如果S的长度大于T的长度，返回1if (S.length > T.length) return 1;// 如果S的长度小于T的长度，返回-1if (S.length < T.length) return -1;// 如果上述条件都不满足，说明两个字符串相等，返回0return 0;
}5、求串长
//求字符串的长度
int StrLength( str S) {return S.length;
}6、求子串
// 定义一个函数SubSting，用于从字符串S中提取从位置pos开始的长度为len的子串，并存储到Sub中
void SubSting(str &Sub, str S, int pos, int len) {// 首先检查字符串S是否为空if (IsStrEmpty(S)) {return;}// 检查pos和len是否合理，即pos是否在字符串范围内，len是否非负，以及子串是否会超出原字符串的范围if (pos < 1 || pos > S.length || len < 0 || (pos + len - 1 > S.length)) {cout << "输入有误！" << endl; // 如果输入有误，输出错误信息return;}int i, j; // 定义两个索引变量i和j，i用于遍历原字符串S，j用于遍历子串Sub// 循环从S中提取子串，i从pos-1开始（因为数组索引从0开始），j从0开始for (i = pos - 1, j = 0; i < pos + len - 1 && i < S.length; i++, j++) {Sub.ch[j] = S.ch[i]; // 将S中的字符赋值给Sub}Sub.ch[j] = '\0'; // 在Sub的末尾添加字符串结束符'\0'，确保子串正确结束Sub.length = j; // 更新Sub的长度为实际提取的字符数
}7、串连接
// 定义一个函数Concat，用于将两个字符串S3和S4连接起来，并将结果存储在T1中
void Concat(str &T1, str &S3, str &S4) {// 如果S3和S4都是空串，那么T1也将是一个空串if (IsStrEmpty(S3) && IsStrEmpty(S4)) {T1.length = 0; // 设置T1的长度为0T1.ch[0] = '\0'; // 确保空串以'\0'结尾return; // 结束函数执行}int i; // 定义索引变量i，用于遍历S3// 将S3中的字符复制到T1中for (i = 0; i < S3.length; i++) {T1.ch[i] = S3.ch[i];}int j; // 定义索引变量j，用于遍历S4// 将S4中的字符复制到T1中，紧接在S3的字符之后for (j = 0; j < S4.length; j++, i++) { // j从0开始，i从S3.length开始T1.ch[i] = S4.ch[j];}T1.ch[i] = '\0'; // 在T1的末尾添加字符串结束符'\0'，确保连接后的串正确结束T1.length = i; // 更新T1的长度，i此时是连接后字符串的最后一个字符的索引
}8、定位
// 定义一个函数Index，用于在字符串S5中查找子串S6的起始位置
int Index(str &S5, str &S6) {// 如果S6是空串或者S5的长度小于S6的长度，则返回0或-1if (IsStrEmpty(S6) || S5.length < S6.length) {return -1; // 返回-1表示子串不在主串中}int i = 0, j = 0; // i用于遍历S5，j用于遍历S6// 使用while循环进行查找while (i < S5.length && j < S6.length) {// 如果S5和S6在当前位置的字符相同，则两个索引都向前移动if (S5.ch[i] == S6.ch[j]) {i++;j++;} else {// 如果字符不匹配，i保持不变，j重置为0，重新开始匹配S6的起始字符j = 0;}}// 如果j等于S6的长度，说明S6已经在S5中完全匹配if (j == S6.length) {return i - j; // 返回匹配的起始位置，注意这里的返回值应该是i - j，因为i和j在最后一次匹配时是同步的} else {// 如果S6没有在S5中找到，返回-1return -1;}
}六、栈、队列和数组
1、链式栈(带头)
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <cstdlib>using namespace std;typedef struct LinkNode{int data; // 栈顶元素 struct LinkNode* next; // 栈顶指针
}LinkNode,*LinkStack; // 链栈初始化(带头节点)
LinkStack Init(){// 创建头节点LinkStack S = (LinkStack) malloc(sizeof(LinkNode));S->data = 0;S->next = NULL; return S; // 返回头节点
} // 判断链式栈是不是空
bool isEmpty(LinkStack S){if(S->next == NULL){return true;}return false;
} // 链栈入栈
void push(LinkStack &S, int data){// 创建新节点LinkStack p = (LinkStack)malloc(sizeof(LinkNode));p->data = data;p->next = S->next;S->next = p;
} // 链式栈出栈
void pop(LinkStack &S){// 链式栈不需要沾满判断LinkStack p = S->next;if(p==NULL){cout<<"当前栈为空"<<endl;}else{cout<<"栈顶元素出栈:"<<p->data<<endl;S->next = p->next;free(p);}
} //链式栈取栈顶元素
int getTop(LinkStack &S){LinkStack p = S->next;if(isEmpty(S)){cout<<"链式栈为空"<<endl; }else{return p->data;}
} //链式栈求栈的长度（元素的个数）
int getCount(LinkStack S){int count = 0;LinkStack p = S->next;while(p!=NULL){count++;p = p->next;}return count;
} int main(){LinkStack S;S = Init(); // 初始化链栈并接收返回值push(S, 2);push(S, 3);push(S, 9);push(S, 7);
// while(!isEmpty(S)) pop(S); // 循环直到栈为空cout<<"栈顶元素是:"<<getTop(S)<<endl;cout<<"栈中元素个数:"<<getCount(S)<<endl;return 0;
}
2、链式栈(无头)
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <cstdlib>using namespace std;typedef struct LinkNode{int data; // 栈顶元素 struct LinkNode* next; // 栈顶指针
}LinkNode,*LinkStack; // 链栈初始化(带头节点)
void Init(LinkStack &S){S = NULL;
} // 判断链式栈是不是空
bool isEmpty(LinkStack S){if(S == NULL){return true;}return false;
} // 链栈入栈
void push(LinkStack &S, int data){// 创建新节点LinkStack p = (LinkStack)malloc(sizeof(LinkNode));p->data = data;p->next = S;S = p;
} // 链式栈出栈
void pop(LinkStack &S){// 链式栈不需要沾满判断LinkStack p = S;if(p==NULL){cout<<"当前栈为空"<<endl;}else{cout<<"栈顶元素出栈:"<<p->data<<endl;S = p->next;free(p);}
} //链式栈取栈顶元素
int getTop(LinkStack &S){LinkStack p = S;if(isEmpty(S)){cout<<"链式栈为空"<<endl; }else{return p->data;}
} //链式栈求栈的长度（元素的个数）
int getCount(LinkStack S){int count = 0;LinkStack p = S;while(p!=NULL){count++;p = p->next;}return count;
} int main(){LinkStack S;Init(S); // 初始化链栈并接收返回值push(S, 2);push(S, 3);push(S, 9);push(S, 7);
// while(!isEmpty(S)) pop(S); // 循环直到栈为空cout<<"栈顶元素是:"<<getTop(S)<<endl;cout<<"栈中元素个数:"<<getCount(S)<<endl;return 0;
}
3、链式队列
#include <iostream>
#include <cstdlib>using namespace std;// 定义链式队列的节点结构体
typedef struct QueueNode {int data;struct QueueNode* next;
} QueueNode;// 定义链式队列的类型
typedef struct {QueueNode* front; // 队列头指针QueueNode* rear; // 队列尾指针
} LinkQueue;// 初始化链式队列
void init(LinkQueue* L) {L->front = L->rear = (QueueNode*)malloc(sizeof(QueueNode));if (!L->front) {cout << "内存分配失败！" << endl;exit(1);}L->front->next = NULL;
}// 判断链式队列是否为空
bool isEmpty(LinkQueue L) {return L.front == L.rear;
}// 入队操作
void push(LinkQueue* L, int data) {QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode));if (!p) {cout << "内存分配失败！" << endl;exit(1);}p->data = data;p->next = NULL;L->rear->next = p;L->rear = p;
}// 出队操作
bool pop(LinkQueue* L, int& data) {if (isEmpty(*L)) {cout << "队列为空，无法出队！" << endl;return false;}QueueNode* temp = L->front->next;data = temp->data;L->front->next = temp->next;if (L->rear == temp) { // 如果移除的是最后一个节点，更新rear指针L->rear = L->front;}free(temp);return true;
}// 销毁链式队列，释放内存
void destroy(LinkQueue* L) {while (!isEmpty(*L)) {pop(L, data);}free(L->front);L->front = L->rear = NULL;
}// 主函数，用于演示链式队列的操作
int main() {LinkQueue L;init(&L);push(&L, 1);push(&L, 2);push(&L, 3);int data;while (pop(&L, data)) {cout << "出队元素: " << data << endl;}destroy(&L);return 0;
}七、线性表
1、逆转顺序表中的所有元素
// 函数reserve用于将数组A的元素逆序存储到数组B中，并打印结果
void reserve(int A[], int n) {int i, j;int B[n]; // 定义辅助数组B，大小与A相同// 逆序复制A中的元素到B中for (i = n - 1; i >= 0; i--) {B[n - 1 - i] = A[i];}// 打印数组B中的元素for (j = 0; j < n; j++) {printf("%d ", B[j]);}printf("\n"); // 打印换行符，使输出更清晰
}2、删除给定值的元素
// 删除顺序表L中值为e的元素
int del(SqList &L, int e) {// 判断当前的顺序表是不是空的if (L.len <= 0) {return 0; // 如果顺序表为空，直接返回0}// 遍历顺序表for (int i = 0; i < L.len; i++) { // 注意这里的循环条件应该是 i < L.len// 如果找到值为e的元素if (e == L.elem[i]) {// 将找到的元素后面的所有元素向前移动一位，覆盖要删除的元素for (int j = i + 1; j < L.len; j++) {L.elem[j - 1] = L.elem[j];}L.len--; // 顺序表长度减1return 1; // 删除成功，返回1}}return 0; // 如果没有找到值为e的元素，返回0
}3、删除给定范围值的元素
// 删除顺序表L中，值在给定范围s到t之间的所有元素（假设t > s）
void del(SqList &L, int s, int t) {// 判断顺序表是否为空if (L.length <= 0) {printf("不存在元素");return;}// 检查s和t的值是否合法，即t是否大于sif (!(t > s)) {printf("元素位置不合法");return;}int j = 0; // j用于记录新顺序表的长度// 遍历顺序表for (int i = 0; i < L.length; i++) {// 判断当前元素是否不在s到t的范围内if (!(L.elem[i] >= s && L.elem[i] <= t)) {L.elem[j] = L.elem[i]; // 将不在范围内的元素复制到前面j++; // 新顺序表长度加1}}L.length = j; // 更新顺序表的长度为新长度
}4、从有序顺序表中删除其值重复的元素
// 删除有序顺序表中重复的元素
void del(SqList &L) {// 健壮性检查：如果顺序表长度小于等于0，直接返回if (L.length <= 0) {return;}int count = 0; // 记录出现重复元素的次数// 从第二个元素开始遍历顺序表for (int i = 1; i < L.length; i++) {// 如果当前元素与前一个元素相等，说明是重复元素if (L.elem[i] == L.elem[i - 1]) {count++; // 重复元素计数加1} else {// 如果当前元素与前一个元素不相等，将当前元素复制到前一个元素的位置L.elem[i - count] = L.elem[i];}}// 更新顺序表的长度，减去重复元素的数量L.length -= count;
}5、带头结点的单链表“就地”逆置。
// 带头节点的单链表就地反转
LinkList reserve(LinkList &L) {LinkList beg = L->next; // 指向原链表的第一个有数据的节点LinkList end = L->next->next; // 指向原链表的第二个有数据的节点// 当beg的下一个节点不为空时，进行反转操作while (beg->next != NULL) {beg->next = end->next; // 将beg的下一个节点指向end的下一个节点，实现反转end->next = L->next; // 将end的下一个节点指向头节点，更新end的next为原头节点L->next = end; // 更新头节点的next为end，即新的头节点end = beg->next; // 更新end为新的节点，准备下一轮反转}// 反转完成后，返回新的头节点return L->next;
}
6、按序号奇偶,拆分单链表
// 定义一个函数，用于将链表L中的节点按照奇数和偶数位置分离到两个新链表中
void aaa(LinkList &L) {LinkList p = L->next; // 指向链表的第一个数据节点// 创建两个新的头节点，用于构建奇数和偶数链表LinkList headA = (LinkList)malloc(sizeof(LNode)); // 奇数链表的头节点LinkList headB = (LinkList)malloc(sizeof(LNode)); // 偶数链表的头节点LinkList Aa = headA; // 用于构建奇数链表的当前节点LinkList Bb = headB; // 用于构建偶数链表的当前节点headA->next = NULL; // 初始化奇数链表的头节点的next为NULLheadB->next = NULL; // 初始化偶数链表的头节点的next为NULLint index = 1; // 用于记录当前节点的位置，1表示第一个节点，即奇数位置// 当p不为空，即链表未遍历完while (p != NULL) {if (index % 2 == 1) { // 如果当前是奇数个节点Aa->next = p; // 将当前节点p链接到奇数链表的末尾Aa = Aa->next; // 移动Aa指针到奇数链表的末尾L->next = p->next; // 将原链表的当前节点的next移动到下一个节点p->next = NULL; // 将当前节点p的next设置为NULL，断开与原链表的连接p = L->next; // 移动p指针到原链表的下一个节点} else { // 如果当前是偶数个节点Bb->next = p; // 将当前节点p链接到偶数链表的末尾Bb = Bb->next; // 移动Bb指针到偶数链表的末尾L->next = p->next; // 将原链表的当前节点的next移动到下一个节点p->next = NULL; // 将当前节点p的next设置为NULL，断开与原链表的连接p = L->next; // 移动p指针到原链表的下一个节点}index++; // 节点位置计数加1}// 打印奇数序列printf("奇数序列:\n");printList(headA); // 假设printList是一个打印链表的函数printf("\n");// 打印偶数序列printf("偶数序列:\n");printList(headB); // 假设printList是一个打印链表的函数
}7、链表中的节点交替逆序排列
// 定义一个函数，用于对单链表L进行重排序
void reSort(LinkList &L) {// 初始化指针p和q，p走一步，q走两步LinkList p = L->next;LinkList q = L->next;LinkList r;// 当q未走到链表尾部时，继续循环while (q->next != NULL) {p = p->next; // p走一步q = q->next; // q走一步// 如果q还有下一个节点，q再走一步if (q->next != NULL) {q = q->next;}}// 此时，q指向链表的尾部，p指向链表的中间位置// 创建一个新节点作为重排序后链表的头节点q = p->next;p->next = NULL; // 断开原链表，准备重排序// 使用前插法逆置q指向的链表后半段while (q != NULL) {r = q->next; // 保存q的下一个节点q->next = p->next; // 将q的下一个节点指向p的下一个节点p->next = q; // 将p的下一个节点指向qq = r; // q移动到下一个节点}// 将逆置后的后半段链表与前半段链表合并LinkList s = L->next;p->next = q; // 将前半段链表的末尾节点指向逆置后的后半段链表的头节点p->next = NULL; // 重置p的next为NULL，准备合并前半段链表while (q != NULL) {r = q->next; // 保存q的下一个节点q->next = s->next; // 将q的下一个节点指向s的下一个节点s->next = q; // 将s的下一个节点指向qs = q->next; // s移动到下一个节点q = r; // q移动到下一个节点}// 打印重排序后的链表printList(L);
}8、单链表找倒数第k个位置上的结点
// 定义一个函数Search_K，用于在单链表L中查找倒数第k个元素
int Search_K(LinkList L, int k) {LinkList p = L->next, q = L->next; // 初始化两个指针p和q，都指向链表的第一个数据节点int count = 0; // 用于记录步数// 当p不为空时，继续循环while (p != NULL) {if (count < k) {count++; // 增加步数p = p->next; // p先走k步，使得p和q之间相差k个元素} else {q = q->next; // p走完k步后，q开始移动，与p一起往后走p = p->next;}}// 如果count小于k，说明在走到k步之前链表已经结束，不存在倒数第k个节点if (count < k) {return 0; // 返回0表示未找到} else {// 打印倒数第k个元素的数据printf("倒数第%d个元素是%d", k, q->data);return 1; // 返回1表示找到}
}9、单链表,删除绝对值相等的结点，只保留第一次出现的
// 定义一个函数aaa，用于删除单链表L中的重复元素
void aaa(LinkList &L) {// 创建辅助数组，用于标记元素是否已经出现过int fuzhu[20] = {0}; // 默认数组中每个元素的值是0，表示元素未出现过// 初始化指针p指向链表的头节点LinkList p = L;LinkList r = NULL; // 指向要删除的节点int index; // 数组下标// 循环遍历链表，直到p的下一个节点为空while (p->next != NULL) {// 取出data转为正数，用于作为辅助数组的下标index = (p->next->data < 0) ? (-(p->next->data)) : (p->next->data);// 如果该元素未在辅助数组中标记为出现过if (fuzhu[index] == 0) {fuzhu[index] = 1; // 标记该元素已出现p = p->next; // 移动p到下一个节点} else { // 如果该元素已经出现过，即第二次出现r = p->next; // 保存要删除的节点p->next = r->next; // 删除元素，将p的next指向r的下一个节点free(r); // 释放要删除节点的内存}}// 打印单链表，显示删除重复元素后的结果printList(L);
}10、按递增顺序输出单链表元素,并删除最小元素
// 定义一个函数minDel，用于按递增顺序输出单链表L的元素，并删除最小元素
void minDel(LinkList &L) {LinkList pre = NULL; // pre指向被删除元素的前驱节点LinkList p = NULL; // 工作指针，用于遍历链表LinkList q = NULL; // 指向待删除的节点// 当链表不为空时，执行循环while (L->next != NULL) {pre = L; // pre初始化指向链表的头节点p = pre->next; // p初始化指向链表的第一个数据节点// 遍历链表，寻找最小元素while (p->next != NULL) {// 如果找到更小的元素，更新pre指向更小元素的前驱节点if (p->next->data < pre->next->data) {pre = p;}p = p->next; // 移动p指针到下一个节点}// 输出最小元素printf("本次最小的节点是: %d\n", pre->next->data);// 删除最小元素q = pre->next; // q指向最小元素pre->next = q->next; // 从链表中删除最小元素free(q); // 释放最小元素节点的内存// 输出链表，显示删除最小元素后的结果printList(L);printf("\n"); // 打印换行符，为下一次输出做准备}
}11、递归删除不带头结点单链表中值为x的结点
// 定义一个函数Del_x，用于在单链表L中删除值为x的所有节点
void Del_x(LinkList &L, int x) {LinkList p; // 定义一个指针p，用于指向要删除的节点// 如果链表为空，直接返回if (L == NULL) {return;}// 如果当前节点的数据等于xif (L->data == x) {p = L; // 将p指向要删除的节点L = L->next; // 将头指针L移动到下一个节点，绕过要删除的节点free(p); // 释放要删除节点的内存Del_x(L, x); // 递归调用Del_x，继续在剩余链表中查找并删除值为x的节点} else {// 如果当前节点的数据不等于x，递归调用Del_x，继续在下一个节点中查找Del_x(L->next, x);}
}12、给定两个升序单链表 ，将其合并后仍为升序并输出。
// 假设L1、L2有头节点
void resort(LinkList &L1, LinkList &L2) {// p1指向L1的第一个数据节点LinkList p1 = L1->next;// p2指向L2的第一个数据节点LinkList p2 = L2->next;// q1和q2用于临时存储节点的下一个节点LinkList q1, q2;// 遍历L2，直到p2为NULL，即L2的末尾while(p2 != NULL) {// 如果p2指向的节点的数据大于等于p1指向的节点的数据if(p2->data >= p1->data) {// 保存p1的下一个节点q1 = p1->next;// 将p2插入到p1的前面p1->next = p2;// 保存p2的下一个节点q2 = p2->next;// 将p2的next指向q1，即p1原来指向的节点p2->next = q1;}// p1移动到下一个节点p1 = q1;// p2移动到下一个节点p2 = q2;}
}代码中可能存在一些不足之处，仅供您参考。非常感谢您的宝贵意见和建议，以便我们能够不断改进和完善。