搜索到
13
篇与
的结果
-
带头结点的单链表 #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; } // 4.查找第i个结点 node *find(linkList head, int i) { node *p = head->next; // p为工作指针，初值为头结点的下一结点 if(i < 0) { printf("索引非法!"); exit(1); } if(i == 0) return head; int j = 1; while (p && i!=j) { p = p->next; j++; } return p; } // 5.在单链表的第i个位置后插入元素x void insert(linkList *head, int i, dataType x) { node *p = find(*head,i),*q; q = (node*) malloc(sizeof(node)); q->data = x; q->next = p->next; p->next = q; } // 6.删除单链表中值为x的元素 void del(linkList *head, dataType x) { node *p = (*head)->next,*pre = *head; while (p && p->data != x) { pre = p; p = p->next; } if(p) { pre->next = p->next; free(p); } else printf("没有找到该结点，无法删除！\n"); } int main() { linkList list; // 声明头指针 init(&list); // 初始化单链表 display(list); // 输出单链表 for (int i = 1; i <= 10; i++) rearInsert(&list,i); // 插入结点 display(list); int i = 2; node *n = find(list,i); if(n) printf("第%d个结点的值是%d\n",i,n->data); else printf("第%d个结点不存在！\n",i); dataType x = 0; 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 *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.查找单链表中的第i个元素 node *find(linkList list, int i) { if(i < 1) return NULL; int j = 1; node *p = list; while (p && j!=i) { p = p->next; j++; } return p; } // 4.在单链表尾部插入元素 void rearInsert(linkList *list, dataType x) { node *p = *list,*q; // p初值为当前链表指针指向的位置 q = (node*)malloc(sizeof(node)); // 创建新节点 q->data = x; q->next = NULL; // 新节点的指针域置空 if(!p) *list = q; // 如果当前链表为空 else { while (p->next) // 找到最后一个结点 p = p->next; p->next = q; } } // 5.在单链表第i个位置后插入元素 void insert(linkList *list,int i,dataType x) { node *p = *list,*q; // p初值为当前链表指针指向的位置 q = (node*)malloc(sizeof(node)); // 创建新节点 q->data = x; p = find(p,i); // 找到第i个结点 if(!p) { if(i == 0) // 如果是在第1个元素前插入 { q->next = *list; // 若在链表前插入，则把链表挂在新结点后 *list = q; // 更新链表指针的的地址，让它指向q } else { printf("位置不存在，无法插入元素！\n"); exit(1); } } else { q->next = p->next; // 把p结点后的结点挂在q结点后 p->next = q; // 把新结点插入p结点后 } } // 6.删除一个值为x的结点 void del(linkList *head, dataType x) { node *p = *head,*pre = NULL; // p为工作指针，q为前驱指针 if(!*head) // 1.链表为空时 { printf("链表为空，无法删除！\n"); exit(1); // 遇到错误终止程序 } while (p && p->data != x) // 寻找x结点 { pre = p; p = p->next; } if(p) // 找到x结点 { if(!pre) // 如果要删除的是第一个结点 *head = p->next; else pre->next = p->next; free(p); } else printf("未找到结点%d\n",x); } // 7.删除倒数第m个元素 void delM(linkList *list, int m) { // p为链表的工作指针，pre为p的前驱指针，q指向待删结点 node *p = *list, *pre = NULL, *q; if(!p) { printf("单链表为空，无法删除！\n"); return; } int n = 0, i, j = 1; // n为链表个数，i、j为链表位序 while (p) // 统计链表结点个数 { n++; p = p->next; } i = n-m+1; // 删除的是第i个结点 if(i < 1 || i > n) { printf("不存在该结点，无法删除！\n"); return; } p = *list; // 重置p指针指回首结点 while (p->next && j < i) // 寻找要删除的结点 { j++; pre = p; p = p->next; } q = p; // q指向待删结点 if(!pre) // 删除的是首结点 *list = p->next; else pre->next = p->next; free(q); } int main() { linkList list; // 声明一个指向链表的指针 init(&list); // 初始化链表 display(list); for (int i = 1; i <= 10; i++) // 循环插入值 rearInsert(&list,i); display(list); // 输出链表 int i = 1; node *n = find(list,i); // 查找第i个元素 if(n) printf("链表的第%d个元素是%d\n",i,n->data); else printf("链表访问越界！\n"); dataType x = 5; printf("在第%d个位置后面插入元素%d\n",i,x); insert(&list,i,x); display(list); // 输出链表 printf("删除一个值为%d的元素\n",x); del(&list,x); display(list); // 输出链表 printf("删除倒数第%d个元素\n",5); delM(&list,5); display(list); // 输出链表 return 0; }
-
顺序循环队列及其实现 #include <stdio.h> #include <stdlib.h> // 定义队列的容量，可以修改为更小的值测试循环队列 #define MAX_SIZE 100 typedef int dataType; // 2.4.3 顺序存储的循环队列 typedef struct { dataType a[MAX_SIZE]; int front,rear; // 队头指针和队尾指针 }seqQueue; // 1.初始化队列 void init(seqQueue *queue) { queue->front = queue->rear = 0; } // 2.判断队列是否为空 int empty(seqQueue queue) { return queue.rear == queue.front; } // 3.打印队列 void display(seqQueue queue) { if(empty(queue)) { printf("队列为空！\n"); return; } while (!empty(queue)) { printf("%d ",queue.a[queue.front]); queue.front = (queue.front + 1)%MAX_SIZE; } printf("\n"); } // 4.获取队首结点的值 dataType get(seqQueue queue) { if(empty(queue)) { printf("队列为空！\n"); exit(1); } return queue.a[queue.front]; } // 5.入队操作 void insert(seqQueue *queue, dataType x) { if((queue->rear + 1)%MAX_SIZE == queue->front) { printf("队列已满，无法入队！\n"); exit(1); } queue->a[queue->rear] = x; queue->rear = (queue->rear + 1)%MAX_SIZE; } // 6.出队操作 void del(seqQueue *queue) { if(queue->rear == queue->front) { printf("队列为空，无法出队！\n"); exit(1); } queue->front = (queue->front + 1)%MAX_SIZE; } // 7.获取队列中元素的个数 int getSize(seqQueue queue) { return (queue.rear-queue.front+MAX_SIZE)%MAX_SIZE; } int main() { seqQueue queue; // 声明队列 init(&queue); // 初始化队列 dataType a = 1, b = 2; insert(&queue,a); // 元素入队 insert(&queue,b); // 元素入队 printf("此时队列中元素有%d个\n", getSize(queue)); display(queue); // 打印队列元素 del(&queue); // 队首元素出队 printf("队首元素是%d\n", get(queue)); display(queue); // 打印队列元素 return 0; }
-
栈的应用三——后缀表达式求值 // 将字符转换成数字 double readNumber(char c[],int *i) { double x = 0.0; int k = 0; while (c[*i] >= '0' && c[*i] <= '9') x = x*10 + (c[(*i)++] - '0'); if(c[*i] == '.') { (*i)++; while (c[*i] >= '0' && c[*i] <= '9') { x = x*10 + (c[(*i)++] - '0'); k++; } } while (k != 0) { x = x/10.0; k--; } return x; } // 后缀表达式求值 double cal(char c[]) { double op[MAX_SIZE] = {}; // 操作数栈 int top = 0; // 栈顶指针 double left,right; // 左、右操作数 int i = 0; while (c[i]) { if(c[i] >= '0' && c[i] <= '9') op[top++] = readNumber(c,&i); else if(c[i] == ' ') i++; else { right = op[--top]; left = op[--top]; if(c[i] == '+') op[top++] = left + right; else if(c[i] == '-') op[top++] = left - right; else if(c[i] == '*') op[top++] = left * right; else op[top++] = left / right; i++; } } return op[--top]; } int main() { char c[] = "6/3+(5*6-2*7)/4"; char r[MAX_SIZE]={}; convert(c,r); int i=0; while (r[i]) printf("%c",r[i++]); printf("\n"); printf("%f",cal(r)); return 0; }
-
栈的应用二——中缀转后缀表达式 使用以上栈的声明和基本操作，只需把typedef int dataType;中的int改为char即可。// 将字符分类 int classify(char c) { switch (c) { case '(': case ')': return 2; // 表示界限符 case '+': case '-': case '*': case '/': return 3; // 表示运算符 default: return 1; // 表示操作数0-9 } } // 将运算符划分优先级 int priority(char c) { switch (c) { case '+': case '-': return 1; case '*': case '/': return 2; } } // 中缀表达式转后缀表达式的机器计算 /** 初始化一个栈，用于保存暂时无法确定运算顺序的运算符，依次扫描元素直到结束， * 1.遇到操作数直接加入后缀表达式； * 2.遇到左界限符则入栈，遇到右界限符则依次弹出栈中的运算符加入表达式， * 直到弹出左界限符，但左界限符不加入表达式； * 3.遇到运算符，依次弹出栈中优先级高于或等于当前运算符的所有运算符并加入后缀表达式， * 直到弹出左界限符或栈空。然后再把当前运算符入栈。 * 4.当扫描的中缀表达式结束时，栈中的运算符依次出栈加入后缀表达式。 **/ void convert(char m[], char r[]) { int i=0,j=0,type; seqStack stack; init(&stack); while (m[i]) { type = classify(m[i]); if(type == 1) // 扫描到数字时 { r[j++] = m[i]; } else if(type == 2) // 扫描到界限符 { if(m[i] == '(') push(&stack,m[i]); else { while (!empty(stack)) { if(read(stack) != '(') { r[j++] = read(stack); pop(&stack); } else { pop(&stack); break; } } } } else // 扫描到运算符 { while(!empty(stack)&&read(stack)!='('&&classify(read(stack))==3) { if(priority(read(stack)) >= priority(m[i])) { r[j++] = read(stack); pop(&stack); } else break; // 如果栈中运算符优先级较低则退出循环 } push(&stack,m[i]); r[j++] = ' '; // 每两个数之间加一个分隔符 } i++; } while (!empty(stack)) { r[j++] = read(stack); pop(&stack); } } int main() { char c[] = "6/3+(5*6-2*7)/4"; char r[MAX_SIZE]={}; convert(c,r); int i=0; while (r[i]) { printf("%c",r[i++]); } return 0; }
