搜索到
40
篇与
的结果
-
在单链表中插入结点 在带头结点单链表值为y的结点前插入一个值为x的结点#include <stdio.h> #include <stdlib.h> typedef int dataType; // 带头结点的单链表 typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化带头结点的单链表 void init(linkList *head) { node *p = (node*)malloc(sizeof(node)); p->next = NULL; *head = p; } // 2.输出链表 void display(linkList head) { node *p = head->next; if(!p) { printf("单链表为空！\n"); return; } while (p) { printf("%d ",p->data); p = p->next; } printf("\n"); } // 3.在链表尾部插入元素 void rearInsert(linkList *head, dataType x) { node *p = *head,*q; // head初值为头结点 q = (node*) malloc(sizeof(node)); q->data = x; q->next = NULL; while (p->next) // 找到尾结点 p = p->next; p->next = q; } // 寻找结点值为x的前驱结点 node *findXPre(linkList head, dataType x) { node *p = head->next,*pre = head; while (p && p->data != x) { pre = p; p = p->next; } if(!p) return NULL; return pre; } // 3.8.4.在带头结点单链表值为y的结点前插入一个值为x的结点 void insert(linkList *head, dataType y, dataType x) { node *p = findXPre(*head,y),*q; if(!p) { printf("没有找到这样的结点，无法插入！\n"); return; } q = (node*) malloc(sizeof(node)); q->data = x; q->next = p->next; p->next = q; } int main() { linkList list; // 声明头指针 init(&list); // 初始化单链表 for (int i = 1; i <= 10; i++) rearInsert(&list,i); // 插入结点 display(list); dataType y = 1,x = 0; printf("在带头结点单链表值为%d的结点前插入一个值为%d的结点\n",y,x); insert(&list,y,x); display(list); return 0; } -
求单链表的结点个数 求单链表的结点个数1.求单链表的结点个数#include <stdio.h> #include <stdlib.h> typedef int dataType; // 单链表 typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化不带头结点的单链表 void init(linkList *list) { *list = NULL; // 表示链表指针指向空处 } // 2.输出单链表元素 void display(linkList list) { node *p = list; // p为工作指针，初值为头指针 if(!p) { printf("链表为空！\n"); return; } while (p) { printf("%d ",p->data); p = p->next; } printf("\n"); } // 3.根据用户输入构造单链表 void scanInsert(linkList *head) { node *p,*q; dataType x; printf("请输入(以9999作为结束标识)...\n"); scanf("%d",&x); while (x!=9999) { q = (node*) malloc(sizeof(node)); q->data = x; q->next = NULL; if(!*head) // 创建第一个结点时 { *head = q; p = *head; } else { p->next = q; p = p->next; } scanf("%d",&x); } } // 3.8.2 统计单链表结点个数 int count(linkList head) { node *p = head; int i = 0; while (p) { p = p->next; i++; } return i; } int main() { linkList list; // 声明一个指向链表的指针，即头指针 init(&list); // 初始化链表 scanInsert(&list); display(list); // 输出链表 printf("链表的结点个数是%d个", count(list)); return 0; }2.求带头结点的单链表的结点个数#include <stdio.h> #include <stdlib.h> typedef int dataType; // 带头结点的单链表 typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化带头结点的单链表 void init(linkList *head) { node *p = (node*)malloc(sizeof(node)); p->next = NULL; *head = p; } // 2.输出链表 void display(linkList head) { node *p = head->next; if(!p) { printf("单链表为空！\n"); return; } while (p) { printf("%d ",p->data); p = p->next; } printf("\n"); } // 3.根据用户输入构造带头结点的单链表 void scanInsert(linkList *head) { node *p = *head,*q; dataType x; printf("请输入(以9999作为结束标识)...\n"); scanf("%d",&x); while (x!=9999) { q = (node*) malloc(sizeof(node)); q->data = x; q->next = NULL; p->next = q; p = q; scanf("%d",&x); } } // 3.8.3 统计带头结点单链表结点个数 int count(linkList head) { node *p = head->next; int i = 0; while (p) { p = p->next; i++; } return i; } int main() { linkList list; // 声明头指针 init(&list); // 初始化单链表 scanInsert(&list); display(list); printf("链表的结点个数是%d个", count(list)); return 0; }
-
二叉树的非递归遍历和相关运算 #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; }
