搜索到
40
篇与
的结果
-
内部排序 内部排序#include <stdio.h> typedef int elementType; // 将需要操作的数据元素定义别名，方便修改 #define MAX_SIZE 100 // 初始化操作数组的最大容量 // 交换两个元素的值 void swap(elementType *a, elementType *b) { elementType temp = *a; *a = *b; *b = temp; } // 1.直接插入排序(将每个待排序的关键字插入前面已经有序的序列中) void insetSort(elementType A[], int len) { elementType temp; int i,j; for (i = 1; i < len; i++) // 依次检查A[1]~A[n-1] { if(A[i] < A[i-1]) // 若A[i]小于前驱则需要移动 { temp = A[i]; // 暂存当前元素 for (j = i-1; temp < A[j] && j >= 0; --j) A[j+1] = A[j]; // 不断向前遍历、移动，直到不小于左侧元素 A[j+1] = temp; // 复制到插入位置 } } } // 1.2折半插入排序(直接插入排序是边比较边移动元素，而折半插入是把比较和移动分离， // 即先用折半查找确定元素的待插入位置，然后统一移动待插入位置后的所有元素) void binaryInsertSort(elementType A[],int len) { elementType temp; // 定义临时变量暂存待插入元素 int low,high,mid; // 定义折半查找定位指针 for (int i = 1; i < len; i++) // 依次将A[1]~A[n-1]插入到前面的有序序列 { temp = A[i]; // 暂存待插入元素 low = 0,high = i-1; // 设置折半查找的范围 while (low <= high) { mid = (low+high)/2; if(A[mid] < temp) low = mid + 1; // 查找右子表 else high = mid -1; // 查找左子表 } for (int j = i-1; j > high; j--) A[j+1] = A[j]; // 统一后移元素，空出插入位置 A[high+1] = temp; // 插入到指定位置 } } // 2.希尔排序(把待排序序列中相隔某个”增量“的元素组成一个子表，对各个子表直接插入排序， // 当整个表已经基本有序时，再对全体记录进行一次直接插入排序。) void shellSort(elementType A[], int len) { elementType temp; // 临时变量暂存待插入元素 int d,i,j; // d为步长 for (d = len/2; d >= 1 ; d /=2) { for (i = d; i <= len; i++) { if(A[i] < A[i-d]) { temp = A[i]; for (j = i-d; j >=0 && temp < A[j]; j -= d) A[j+d] = A[j]; // 记录后移，更新插入位置 A[j+d] = temp; // 插入待插入元素 } } } } // 3.冒泡排序(从前往后或从后往前两两比较相邻元素的值，若为逆序，则交换它们，直到比较结束) void bubbleSort(elementType A[], int len) { int flag; // 标记某趟冒泡是否进行了交换 for (int i = 0; i < len-1 ; i++) { flag = 0; // 每趟冒泡前把flag置为false for (int j = len-1; j > i; j--) // 一趟冒泡 { if(A[j] < A[j-1]) //是否存在逆序 { swap(&A[j],&A[j-1]); flag = 1; // 发生交换动作后把flag置为true } } if(!flag) break; // 若某趟未进行交换操作，则排序结束 } } // 快排划分 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[low] <= pivot) ++low; A[high] = A[low]; // 比基准大的移动到右端 } A[low] = pivot; return low; // 返回存放基准的最终位置 } // 4.快速排序(快速排序是基于分治法的，在待排序表中任取一个元素作为枢纽或基准， // 通过一趟排序划分为两部分，小于基准的元素放到基准左边，大于的放到右边， // 这样就确定了一个元素的位置，不断划分，不断移动，递归上述过程直到有序。) void quickSort(int A[], int low, int high) { if (low < high) { int pivotPos = partition(A, low, high); // 划分 quickSort(A, low, pivotPos - 1); // 划分左子表 quickSort(A, pivotPos + 1, high); // 划分右子表 } } // 5.简单选择排序(每趟在后面n-i+1个待排序元素中选出最小的元素， // 作为有序子序列的第i个元素，直到n-1趟做完只剩1个，就不必再选了。) void selectSort(elementType A[], int len) { int i, j,min; for (i = 0;i < len-1;i++) // 最后剩一个不用处理，所以是i < n-1 { min = i; for ( j = i+1; j < len; j++) { if (A[j] < A[min]) min = j; } if (min != i) swap(&A[i],&A[min]); } } // 调整堆 void adjustHeap(elementType A[],int i,int len) { A[0] = A[i]; // 暂存根节点(若A[0]元素有实际意义，也可用临时变量) for (int k = 2*i; k <= len; k *=2) // k *=2表示沿着较大的子结点向下筛选 { if(k < len && A[k] < A[k+1]) k++; // 记录下最大的孩子结点的索引值 if(A[0] >= A[k]) break; // 如果满足大根堆(根节点不小于最大的孩子)则退出循环无需继续调整 A[i] = A[k]; // 将最大的元素调节到双亲节点上 i = k; // 修改索引，继续筛选 } A[i] = A[0]; // 将被筛选的结点放入最终位置 } // 建立大根堆 void buildMaxHeap(elementType A[],int len) { for (int i = len/2; i > 0; i--) adjustHeap(A,i,len); } // 6.堆排序(大根堆：二叉树根节点大于左右孩子，小根堆则小于；将数组视为顺序存储的树， // 利用堆这一特性，创建堆，调整堆，每调整一轮都从中选出了最大值，不断将堆顶元素放入堆底。) void heapSort(elementType A[],int len) { // 1.初始化大根堆 buildMaxHeap(A,len); // 2.不断的调整堆，并且把堆顶元素和堆底元素交换，堆不断缩小 for (int i = len; i > 1; i--) { swap(&A[1],&A[i]); //将大根堆堆顶元素放入堆底 adjustHeap(A,1,i-1); // 不断的调整缩小的堆，直到最大的元素依次在堆底 } } elementType B[MAX_SIZE]; // 定义一个辅助数组，用于归并排序的归并操作 // 归并操作 void merge(elementType A[],int low,int mid,int high) { int i,j,k; for (k = low;k <= high;k++) B[k] = A[k]; // 将A中的元素复制到B中 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表尾部 A[k++] = B[i++]; while (j<=high) // 若右表剩余，复制回A表尾部 A[k++] = B[j++]; } // 7.二路归并排序(归并排序是基于归并操作实现的，每次归并将相邻的两个有序序列归并成一个) void mergeSort(elementType 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); // 合并相邻的两个有序的序列 } } // 打印数组元素，从index下标开始打印len个长度 void printArray(elementType A[],int index,int len) { // 判断数组是否越界 if(index < 0 || index + len > MAX_SIZE) { printf("Array Index OutOf Bounds Exception!"); return; } for (int i = index; i < index + len; ++i) { printf("%d",A[i]); if(i < index + len - 1) printf(","); } printf("\n"); } int main() { // 1.直接插入排序 elementType A[MAX_SIZE] = {49,38,65,97,76,13,27,49}; insetSort(A,8); printArray(A,0,8); // 1.1折半插入排序 elementType A1[MAX_SIZE] = {49,38,65,97,76,13,27,49}; binaryInsertSort(A1,8); printArray(A1,0,8); // 2.希尔排序 elementType B[MAX_SIZE] = {0,49,38,65,97,76,13,27,49}; shellSort(B,8); printArray(B,1,8); // 3.冒泡排序 elementType C[MAX_SIZE] = {49,38,65,97,76,13,27,49}; bubbleSort(C,8); printArray(C,0,8); // 4.快速排序 elementType D[MAX_SIZE] = {49,38,65,97,76,13,27,49}; quickSort(D,0,7); printArray(D,0,8); // 5.简单选择排序 elementType E[MAX_SIZE] = {49,38,65,97,76,13,27,49}; selectSort(E,8); printArray(E,0,8); // 6.堆排序 elementType F[MAX_SIZE] = {0,49,38,65,97,76,13,27,49}; heapSort(F,8); printArray(F,1,8); // 7.归并排序 elementType G[MAX_SIZE] = {49,38,65,97,76,13,27,49}; mergeSort(G,0,7); printArray(G,0,8); return 0; } -
图的邻接表表示 图的邻接表表示#include <stdio.h> #include <stdlib.h> // 8.3.2 图的邻接表表示 #define MAX 20 // 预定义图的最大顶点数 typedef char dataType; // 顶点数据类型 typedef struct edgeNode // 边表结点 { int adjVex; // 邻接点(位序) struct edgeNode *next; // 与顶点邻接的下一结点 }eNode; typedef struct vertexNode // 头结点类型 { dataType vertex; // 顶点信息 eNode *firstEdge; // 邻接链表头指针 }vNode; typedef struct linkedGraph // 邻接表存储的图 { vNode adjList[MAX]; // 存放顶点的顺序表 int n,e; // 图的顶点数、边数 }graph; // 1. 建立图的邻接表 void createLinkedGraph(graph *g, int c) { int i, j, k; eNode *node = NULL; // 指向边表结点的指针 scanf("%d%d",&g->n,&g->e); // 输入顶点数、边数 if(g->n) { for (i = 0; i < g->n; ++i) { scanf("%1s",&g->adjList[i].vertex); // 输入顶点 g->adjList[i].firstEdge = NULL; // 边表初始化 } for (k = 0; k < g->e; ++k) { scanf("%d%d",&i,&j); // 输入边的信息 node = (eNode *) malloc(sizeof(eNode)); // 创建边 node->adjVex = j; node->next = g->adjList[i].firstEdge; g->adjList[i].firstEdge = node; // 头插法建立链表 if(c == 0) // 无向图 { node = (eNode *) malloc(sizeof(eNode)); node->adjVex = i; node->next = g->adjList[j].firstEdge; g->adjList[j].firstEdge = node; } } } } // 2. 输出邻接表表示的图 void print(graph g) { eNode *node = NULL; // 边表结点指针 for (int i = 0; i < g.n; ++i) { printf("%c->",g.adjList[i].vertex); node = g.adjList[i].firstEdge; while (node) { printf("%d->",node->adjVex); node = node->next; } printf("\n"); } printf("该图有%d个顶点，%d条边",g.n,g.e); } int main() { graph g; printf("请依次输入图的顶点数、边数，顶点信息和边信息\n"); createLinkedGraph(&g,1); // 0表示无向图，1表示有向图 printf("该图的邻接表表示如下：\n"); print(g); return 0; }
-
图的邻接矩阵表示 图的邻接矩阵表示#include <stdio.h> // 8.3.1 图的邻接矩阵表示 #define INFINITY 10000 // 定义无穷大 #define V_MAX 100 // 顶点最大数 typedef char vertexType; // 顶点数据类型 typedef struct graph // 图的邻接矩阵表示 { int n, e; // 顶点和边总数 vertexType vertex[V_MAX]; // 顶点集合 int edge[V_MAX][V_MAX]; // 邻接矩阵 }graph; // 1. 创建邻接矩阵表示的图 void create(graph *g, int c) { int i,j,k,w; scanf("%d%d",&g->n,&g->e); for (i = 0; i < g->n; ++i) scanf("%1s",&g->vertex[i]); for (i = 0; i < g->n; ++i) // 初始化邻接矩阵 { for (j = 0; j < g->n; ++j) { if(i == j) g->edge[i][j] = 0; else g->edge[i][j] = INFINITY; } } for (k = 0; k < g->e; ++k) { scanf("%d%d%d",&i,&j,&w); g->edge[i][j] = w; if(c == 0) g->edge[j][i] = w; // 无向图 } } // 2. 输出邻接矩阵表示的图 void print(graph g) { if(g.n > 0) { for (int i = 0; i < g.n; ++i) { for (int j = 0; j < g.n; ++j) printf("%d\t",g.edge[i][j]); printf("\n"); } } printf("该图有%d个顶点，%d条边",g.n,g.e); } int main() { graph g; printf("请依次输入图的定点数、边数，顶点信息和边信息\n"); create(&g,0); // 0表示无向图，1表示有向图 printf("该图的邻接矩阵表示如下：\n"); print(g); return 0; }
-
树形结构的其他运算 树形结构的其他运算#include <stdio.h> #include <stdlib.h> // 7.8 习题7 typedef char dataType; typedef struct treeNode { dataType data; // 数据域 struct treeNode *lChild,*rChild; // 左、右孩子指针域 }node,*binaryTree; // 顺序栈 #define MAX_SIZE 100 typedef struct stack { node *data[MAX_SIZE]; // 栈中存放的是二叉树结点指针 int top; // 栈顶指针 }seqStack; // 1.初始化栈 void init(seqStack *stack) { stack->top = 0; } // 2. 判断栈是否为空 int empty(seqStack stack) { return stack.top == 0; } // 3. 元素入栈 void push(seqStack *stack, node* n) { if(stack->top == MAX_SIZE-1) { printf("栈已满，无法入栈！\n"); exit(1); } stack->data[stack->top++] = n; } // 4. 读取栈顶元素 node *get(seqStack stack) { return stack.data[stack.top-1]; } // 5. 元素出栈 node* pop(seqStack *stack) { if(empty(*stack)) { printf("栈已空，无法出栈！\n"); exit(1); } return stack->data[--stack->top]; } // 6. 按照前序遍历的顺序创建一个二叉树 binaryTree createTree() { binaryTree tree; char c; if((c = getchar()) == '#') tree = NULL; else { tree = (node *) malloc(sizeof(node)); tree->data = c; tree->lChild = createTree(); tree->rChild = createTree(); } return tree; } // 7.1.13.1 递归方法求二叉树的叶子结点个数 int numLeaf(binaryTree tree) { if(!tree) return 0; // 空树 if(!tree->lChild && !tree->rChild) // 左右孩子都不存在 return 1; return numLeaf(tree->lChild) + numLeaf(tree->rChild); } // 7.1.13.2 非递归方法求二叉树的叶子结点个数 int numLeaf1(binaryTree tree) { int num = 0; seqStack stack; stack.top = 0; // 初始化栈 while (tree || !empty(stack)) // 树或栈非空 { if(tree) { if(!tree->lChild && !tree->rChild) num++; push(&stack,tree); // 进栈 tree = tree->lChild; // 一路向左 } else { tree = pop(&stack); // 出栈向右子树 tree = tree->rChild; } } return num; } // 7.1.14 求给定二叉树中序遍历序列的最后一个结点 node * inOrderLast(binaryTree tree) { while (tree && tree->rChild) tree = tree->rChild; return tree; } // 7.1.15 返回二叉树任意两结点p、q的共同祖先 node *seekAncestor(binaryTree t, node *p, node *q) { seqStack s, s1; // 声明顺序栈 init(&s), init(&s1); // 初始化栈 node *r = NULL; // 记录最近访问的结点 while (t || !empty(s)) // 树或栈非空 { if (t) // 一路向左直到左孩子为空 { push(&s,t); // 沿着根的左孩子依次入栈 t = t->lChild; } else { t = get(s); // 读取栈顶元素 if(t->rChild && t->rChild != r) // 右孩子存在且未访问 t = t->rChild; // 转向右孩子 else { pop(&s); // 出栈 if(t == p || t == q) { if(empty(s1)) // 栈s复制给栈s1 for (int i = s.top-1; i >= 0; i--) push(&s1,s.data[i]); else break; // p、q的祖先都已找到，退出循环 } r = t; // 记录最近访问的结点(关键步骤) t = NULL; // 结点访问后重置为空(关键步骤) } } } while (!empty(s)) // 寻找共同祖先 { t = pop(&s); for (int j = s1.top-1; j >= 0; j--) if(t == s1.data[j]) return t; } return NULL; } int main() { binaryTree tree; printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); tree = createTree(); // ABD#E##FG###C## printf("该二叉树叶子结点有%d个\n",numLeaf(tree)); printf("该二叉树叶子结点有%d个\n", numLeaf1(tree)); node *n = inOrderLast(tree); if(n) printf("该二叉树中序遍历序列的最后一个结点是%c",n->data); else printf("该二叉树为空！"); return 0; }
-
中序穿线二叉树的实现 中序穿线二叉树的实现#include <stdio.h> #include <stdlib.h> // 7.6.3 中序穿线二叉树(线索二叉树)的实现 typedef char dataType; // 线索二叉树的结点结构 typedef struct node { dataType data; // 数据域 struct node *lChild, *rChild; // 左、右孩子指针 int lTag, rTag; // 左、右指针是否是线索的标志 }treeNode, *binaryTree; // 1. 按前序遍历顺序建立二叉树 treeNode *createTree() { treeNode *tree; char c; if((c = getchar()) == '#') tree = NULL; else { tree = (treeNode *) malloc(sizeof(treeNode)); tree->data = c; tree->lChild = createTree(); tree->rChild = createTree(); } return tree; } // 2. 对二叉树中序线索化 treeNode *pre = NULL; // 初始化前驱结点指针 void inThread(binaryTree tree) { if(tree) { inThread(tree->lChild); // 左子树线索化 tree->lTag = tree->lChild ? 0:1; tree->rTag = tree->rChild ? 0:1; if(pre) // 对当前结点及前驱结点线索化 { if(tree->lTag) tree->lChild = pre; if(pre->rTag) pre->rChild = tree; } pre = tree; inThread(tree->rChild); // 右子树线索化 } } // 3. 建立中序线索二叉树 void createInThreadTree(binaryTree *tree) { *tree = createTree(); inThread(*tree); } // 4. 寻找中序线索二叉树中p结点的后继结点 treeNode *inNextNode(binaryTree p) { if(p->rTag == 1) return p->rChild; p = p->rChild; while (p->lTag == 0) p = p->lChild; return p; } // 5. 中序线索二叉树的中序遍历 void inOrder(binaryTree tree) { if(tree) { while (tree->lTag == 0) tree = tree->lChild; while (tree) { printf("%c ",tree->data); tree = inNextNode(tree); } } } int main() { binaryTree tree; // 声明二叉树 printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); createInThreadTree(&tree); //建立中序线索二叉树 ABD#E##FG###C## printf("中序线索二叉树的中序遍历\n"); inOrder(tree); return 0; }
