搜索到
13
篇与
的结果
-
二叉树的非递归遍历和相关运算 #include <stdio.h> #include <stdlib.h> // 7.4.3 二叉树的非递归遍历 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; // 顺序循环队列：用于层序(层次)遍历 typedef struct { node *data[MAX_SIZE]; int front,rear; // 队头、队尾指针 }queue; // 1.栈初始化 void initStack(seqStack *stack) { stack->top = 0; } // 2. 判断栈是否为空 int emptyStack(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(emptyStack(*stack)) { printf("栈已空，无法出栈！\n"); exit(1); } return stack->data[--stack->top]; } // 6.队列初始化 void initQueue(queue *q) { q->front = q->rear = 0; } // 7.判断队列是否为空 int emptyQueue(queue q) { return q.rear == q.front; } // 8.入队 void enQueue(queue *q, node *n) { if((q->rear+1)%MAX_SIZE == q->front) { printf("队列满，无法入队！\n"); exit(1); } q->data[q->rear] = n; q->rear = (q->rear + 1)%MAX_SIZE; } // 9.出队 node *deQueue(queue *q) { if(emptyQueue(*q)) { printf("队列为空，无法出队！\n"); exit(1); } node *n = q->data[q->front]; q->front = (q->front+1)%MAX_SIZE; return n; } // 10. 按照前序遍历的顺序创建一个二叉树 binaryTree createTree() { binaryTree t; char c; if((c = getchar()) == '#') t = NULL; else { t = (node *) malloc(sizeof(node)); t->data = c; t->lChild = createTree(); t->rChild = createTree(); } return t; } // 11. 非递归前序遍历 void preOrder(binaryTree t) { seqStack stack; // 声明顺序栈 stack.top = 0; // 初始化栈 while (t || !emptyStack(stack)) // 树非空或栈非空 { if(t) // 一路向左直到左孩子为空 { printf("%c ",t->data); // 先访问根节点 push(&stack,t); t = t->lChild; // 再访问左孩子 } else { t = pop(&stack); t = t->rChild; // 再访问右孩子 } } } // 12.非递归中序遍历 void inOrder(binaryTree t) { seqStack stack; // 声明顺序栈 stack.top = 0; // 初始化栈 while (t || !emptyStack(stack)) { if(t) // 一路向左直到左孩子为空 { push(&stack,t); t = t->lChild; } else { t = pop(&stack); printf("%c ",t->data); t = t->rChild; } } } // 13.非递归后序遍历 void postOrder(binaryTree t) { seqStack stack; // 声明顺序栈 stack.top = 0; // 初始化栈 node *r = NULL; // 记录最近访问的结点 while (t || !emptyStack(stack)) { if (t) // 一路向左直到左孩子为空 { push(&stack,t); // 沿着根的左孩子依次入栈 t = t->lChild; } else { t = stack.data[stack.top-1]; // 读取栈顶元素 if(t->rChild && t->rChild != r) // 右孩子存在且未访问 t = t->rChild; // 转向右孩子 else { pop(&stack); // 出栈 printf("%c ", t->data); r = t; // 记录最近访问的结点(关键步骤) t = NULL; // 结点访问后重置为空(关键步骤) } } } } // 14. 二叉树层次遍历 seqStack nodeStack; void levelOrder(binaryTree t) { if(!t) { printf("二叉树为空！\n"); return; } queue q; // 声明队列 initQueue(&q); // 初始化队列 enQueue(&q,t); // 根节点入队 initStack(&nodeStack); while (!emptyQueue(q)) // 队列非空 { t = deQueue(&q);; // 出队并访问 push(&nodeStack,t); printf("%c ",t->data); if(t->lChild) // 左孩子入队 enQueue(&q,t->lChild); if(t->rChild) // 右孩子入队 enQueue(&q,t->rChild); } } // 15. 非递归求二叉树层数(深度或高度) int level(binaryTree t) { queue q; // 声明队列 initQueue(&q); // 初始化队列 int level = 0, first = 0; // first指向每层最左侧结点 if(!t) return 0; enQueue(&q,t); // 根结点入队 while (!emptyQueue(q)) // 队列非空 { if(first == q.front) // 当队首结点是某层的第一个结点时 { level++; // 层数累加 first = q.rear; // 更新first指针指向下一层的第一个结点位置 } t = deQueue(&q); // 出队并将孩子结点入队 if(t->lChild) // 左孩子入队 enQueue(&q,t->lChild); if(t->rChild) // 右孩子入队 enQueue(&q,t->rChild); } return level; } // 16.非递归求二叉树最大宽度 int width(binaryTree t) { queue q; // 声明循环队列 initQueue(&q); // 初始化队列 int i = 1, width = 0, first = 0; // i初值为1，处理只有一个结点的树 if(!t) return 0; // 树为空时 enQueue(&q,t); // 根节点入队 while (!emptyQueue(q)) // 队列非空时 { if(first == q.front) // 当first指向每层第一个节点时 { if(i > width) width = i; // 更新最大宽度 first = q.rear; // 更新first指针 i = 0; // 重置i，以计算该层宽度 } t = deQueue(&q); // 元素出队 i++; // 计算该层宽度 if(t->lChild) enQueue(&q,t->lChild); // 左孩子入队 if(t->rChild) enQueue(&q,t->rChild); // 右孩子入队 } return width; } // 17.返回二叉树任意两结点p、q的共同祖先 node *seekAncestor(binaryTree t, node *p, node *q) { seqStack s, s1; // 声明顺序栈 initStack(&s), initStack(&s1); // 初始化栈 node *r = NULL; // 记录最近访问的结点 while (t || !emptyStack(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 (emptyStack(s1)) for (int i = s.top - 1; i >= 0; i--) push(&s1, s.data[i]); else break; } r = t; // 记录最近访问的结点(关键步骤) t = NULL; // 结点访问后重置为空(关键步骤) } } } while (!emptyStack(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 t; // 声明二叉树 printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); t = createTree(); // ABD#E##FG###C## printf("前序遍历\n"); preOrder(t); printf("\n中序遍历\n"); inOrder(t); printf("\n后序遍历\n"); postOrder(t); printf("\n层序遍历\n"); levelOrder(t); printf("\n树的高度为%d", level(t)); node *p = nodeStack.data[2], *q = nodeStack.data[6], *n; n = seekAncestor(t,p,q); if(n) printf("\n结点%c和结点%c的共同祖先是%c",p->data,q->data,n->data); else printf("\n结点%c和结点%c没有共同祖先",p->data,q->data); printf("\n该二叉树的宽度为%d", width(t)); return 0; -
链式队列及其实现 #include <stdio.h> #include <stdlib.h> typedef int dataType; // 3.7 链式队列 typedef struct linkQueueNode { dataType data; struct linkQueueNode *next; }node,*linkQueue; // 链式队列头指针和尾指针 typedef struct { linkQueue front,rear; }queue; // 1.初始化链式队列 void init(queue *qu) { qu->front = qu->rear = NULL; } // 2.判断队列是否为空 int empty(queue qu) { return !qu.front; } // 3.读队首元素的值 dataType read(queue qu) { if(empty(qu)) { printf("队列为空！\n"); exit(1); } return qu.front->data; } // 4.输出队列元素的值 void display(queue qu) { node *p = qu.front; if(!p) { printf("队列为空！\n"); return; } while (p) { printf("%d ",p->data); p = p->next; } printf("\n"); } // 5.入队 void insert(queue *qu, dataType x) { node *q; q = (node*) malloc(sizeof(node)); q->data = x; q->next = NULL; if(empty(*qu)) // 队列为空时 qu->front = q; else qu->rear->next = q; qu->rear = q; // 更新尾指针 } // 6.出队 void del(queue *qu) { node *p = qu->front; if(p == qu->rear) // 只有一个结点或队列空 { if(!p) { printf("队列为空，无法出队！\n"); return; } qu->front = qu->rear; // 更新头指针 free(p); return; } // 队列非空时更新队头指针并释放结点空间 qu->front = p->next; free(p); } int main() { queue qu; // 定义一个指向队列的头指针和尾指针 init(&qu); // 初始化队列 display(qu); // 输出队列元素 printf("入队！\n"); for (int i = 1; i <= 5; i++) insert(&qu,i); // 入队 display(qu); printf("队首元素为%d\n",read(qu)); printf("出队！\n"); del(&qu); display(qu); return 0; }
-
链式栈及其实现 #include <stdio.h> #include <stdlib.h> typedef int dataType; // 3.6 链式栈 typedef struct linkStackNode { dataType data; struct linkStackNode *next; }node,*linkStack; // 1.初始化链式栈 void init(linkStack *top) { *top = NULL; } // 2.判断栈是否为空 int empty(linkStack top) { return !top; } // 3. 读取栈顶结点 node *read(linkStack top) { return top; } // 4.输出链式栈中各结点值 void display(linkStack top) { if(!top) { printf("栈空，无法输出结点！\n"); return; } while (top) { printf("%d ",top->data); top = top->next; } printf("\n"); } // 5.入栈 void push(linkStack *top, dataType x) { node *q = (node*) malloc(sizeof(node)); q->data = x; q->next = *top; // 新结点放在栈顶元素上面 *top = q; // 栈顶指针指向新结点 } // 6.出栈 void pop(linkStack *top) { if(!*top) { printf("栈空，无法出栈！\n"); return; } node *p = *top; *top = p->next; // 更新栈顶指针 free(p); } int main() { linkStack top; // 声明一个栈顶指针 init(&top); // 初始化链式栈 display(top); // 输出栈中各元素的值 dataType a = 1,b = 2; printf("元素%d入栈\n",a); push(&top,a); // 入栈 display(top); printf("元素%d入栈\n",b); push(&top,b); display(top); printf("出栈\n"); pop(&top); // 出栈 display(top); return 0; }
-
双链表及其实现 #include <stdio.h> #include <stdlib.h> typedef int dataType; // 3.5 双链表 typedef struct dLinkNode { dataType data; struct dLinkNode *lLink,*rLink; }dNode,*dLinkList; // 1.初始化不带头结点的双链表 void init(dLinkList *head) { *head = NULL; } // 2.输出双链表各结点的值 void display(dLinkList head) { dNode *p = head; if(!p) { printf("双链表为空！\n"); return; } do { printf("%d ",p->data); p = p->rLink; } while (p); printf("\n"); } // 3.查找双链表中第i个结点 dNode *find(dLinkList head, int i) { dNode *p = head; if(i < 1) { printf("非法的索引！\n"); return NULL; } if(!p) { printf("双链表为空！\n"); return NULL; } int j = 1; while (p->rLink && i != j) { p = p->rLink; j++; } if(i > j) return NULL; return p; } // 4.找到双链表的尾结点 dNode *rear(dLinkList head) { dNode *p = head; if(!p) return NULL; while (p->rLink) p = p->rLink; return p; } // 5.在双链表尾部插入值为x的结点 void rearInsert(dLinkList *head, dataType x) { dNode *p = *head,*q; q = (dNode*) malloc(sizeof(dNode)); q->data = x; q->rLink = NULL; if(!p) // 链表为空时 { *head = q; q->lLink = NULL; } else { p = rear(p); p->rLink = q; q->lLink = p; } } // 6.在双链表的第i个结点后插入值为x的新结点 void insert(dLinkList *head, int i, dataType x) { if(i < 0) { printf("非法的插入位置！\n"); return; } dNode *p = *head,*q; q = (dNode*) malloc(sizeof(dNode)); q->data = x; q->rLink = NULL; if(i == 0) // 在表头插入 { if(p) // 链表非空时 { q->rLink = *head; (*head)->lLink = q; *head = q; } q->lLink = NULL; *head = q; return; } p = find(*head,i); if(p) { if(p->rLink) // 如果p不是尾结点 p->rLink->lLink = q; q->rLink = p->rLink; // 以下两行不可换位置 q->lLink = p; p->rLink = q; } else printf("插入索引越界！\n"); } // 7.双链表中删除一个值为x的结点 void del(dLinkList *head, dataType x) { dNode *p = *head; if(!p) { printf("链表为空，无法删除！\n"); return; } while (p) // 寻找要删除的p结点 { if(p->data == x) break; p = p->rLink; } if(p) { if(!p->lLink && !p->rLink) // 只有一个结点时 { free(p); *head = NULL; return; } if(!p->lLink) // 如果删除首结点 { *head = p->rLink; p->rLink->lLink = NULL; free(p); return; } if(!p->rLink) // 如果删除尾结点 { p->lLink->rLink = NULL; free(p); return; } // 中间结点的删除 p->lLink->rLink = p->rLink; p->rLink->lLink = p->lLink; free(p); return; } else printf("没有找到这样的结点，无法删除！\n"); } int main() { dLinkList list; // 声明指向双链表的头指针 init(&list); // 初始化双链表 display(list); // 输出双链表 for (int i = 1; i <= 5; i++) rearInsert(&list,i); // 插入结点 display(list); int i = 5; dataType x = 6; dNode *n = find(list,i); if(n) printf("链表的第%d个元素是%d\n",i,n->data); else printf("链表访问越界！\n"); printf("在第%d个位置后面插入元素%d\n",i,x); insert(&list,i,x); display(list); printf("删除一个值为%d的元素\n",x); del(&list,x); display(list); return 0; }
-
循环单链表及其实现 #include <stdio.h> #include <stdlib.h> typedef int dataType; typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化不带头结点的循环单链表 void init(linkList *head) { *head = NULL; } // 2.获取循环单链表的尾结点 node *rear(linkList head) { node *p = head; while (p) { if(p->next == head) break; p = p->next; } return p; } // 3.输出循环单链表各结点的值 void display(linkList head) { node *p = head; if(!p) { printf("循环单链表为空！\n"); return; } while (p->next != head) { printf("%d ",p->data); p = p->next; } printf("%d\n",p->data); } // 4.查找值为x的结点 node* findX(linkList head, dataType x) { node *p = head; if(!p) { printf("循环单链表为空！\n"); return head; } while (p->next != head) { if(p->data == x) return p; p = p->next; } if(p->data == x) return p; else return NULL; } // 5.查找第i个结点 node *find(linkList head, int i) { node *p = head; if(i < 1) { printf("索引非法！\n"); return NULL; } if(!p) { printf("循环单链表为空！\n"); return head; } int j = 1; while (p->next != head && i != j) { p = p->next; j++; } if(i == j) return p; return NULL; } // 6.循环单链表的尾部插入结点 void rearInsert(linkList *head, dataType x) { node *p = *head,*q; q = (node*) malloc(sizeof(node)); q->data = x; if(!p) { q->next = q; *head = q; return; } p = rear(*head); p->next = q; q->next = *head; } // 7.在循环单链表的第i个位置后插入元素x void insert(linkList *head, int i, dataType x) { if(i < 0) { printf("非法的插入位置，无法插入！\n"); return; } node *p = *head,*q,*r; q = (node*) malloc(sizeof(node)); q->data = x; if(i == 0) // 当要在链表最前方插入时 { if(!p) // 链表为空时 { *head = q; (*head)->next = *head; return; } // 链表非空时 r = rear(*head); // 找到尾结点 q->next = *head; r->next = q; *head = q; return; } p = find(*head,i); // 其他位置插入则需要找到插入位置 if(!p) printf("非法的位置，无法插入！\n"); else { if(p->next == (*head)) // 如果在尾结点后插入 { p->next = q; q->next = *head; return; } q->next = p->next; // 中间的位置插入 p->next = q; } } // 6.删除循环单链表中值为x的元素 void del(linkList *head, dataType x) { node *p = *head,*q; if(!p) { printf("链表为空，无法删除！\n"); return; } p = findX(p,x); if(!p) { printf("未找到这样的结点，无法删除！\n"); return; } if((*head)->next == *head) // 只有一个结点时 { free(p); *head = NULL; return; } if(p->next == *head) // 如果是删除最后一个结点 { if(p == (*head)->next) // 只有两个结点时 { (*head)->next = *head; free(p); } else // 多于两个结点时 { p->data = p->next->data; q = p->next; p->next = p->next->next; *head = p; free(q); return; } } else { p->data = p->next->data; // 中间结点的删除 q = p->next; p->next = p->next->next; free(q); } } int main() { linkList list; // 声明循环单链表 init(&list); // 初始化空的不带头结点的循环单链表 display(list); // 输出单链表 for (int i = 1; i <= 5; i++) rearInsert(&list,i); display(list); int i = 5; node *n = find(list,i); // 查找第i个元素 if(n) printf("链表的第%d个元素是%d\n",i,n->data); else printf("链表访问越界！\n"); dataType x = 6; printf("在第%d个位置后面插入元素%d\n",i,x); insert(&list,i,x); display(list); printf("删除一个值为%d的元素\n",x); del(&list,x); display(list); return 0; }
