如何提高编程能力？(下)
- 2019 年 10 月 5 日
- 筆記
22.栈及栈应用
22.1 入栈出栈及判空实现
/* 栈 */ #include<stdio.h> #define N 10 typedef struct Stack { int top; int data[N]; }stack; stack s = { -1,{0} }; int isempty() { if (s.top == -1) return 1; else return 0; } void setEmpty() { s.top = -1; } int push(int data) { if (s.top + 1 <= N - 1) { s.data[++s.top] = data; return 1; } else { return 0; } } int pop() { if (isempty()) return -1; else return s.data[s.top--]; } void tenTobinary(int n) { if (n == 0) return; else { int m = n % 2; push(m); tenTobinary(n/2); } } int main() { int a[10]; int i; for (i = 0; i < 10; i++) { a[i] = i + 1; } for (i = 0; i < 10; i++) push(a[i]); while (!isempty()) { printf("%dn",pop()); } tenTobinary(100); while (!isempty()) { printf("%d", pop()); } printf("n"); return 0; }
22.2 栈实现括号匹配
#include<stdio.h> #include<string.h> #define MAX 999 int judge(char p[]) { int len = strlen(p); int top = -1; char s[MAX]; int i; for (i = 0; i < len; i++) { switch(p[i]) { case '(': case '[': case '{': s[++top] = p[i]; break; case ')': if (s[top] == '(') top--; else return 0; break; case ']': if (s[top] == '[') top--; else return 0; break; case '}': if (s[top] == '{') top--; else return 0; break; } } if (top == -1) return 1; else return 0; }
23. 二叉树
23.1 二叉树所有操作
- 前序遍历
- 中序遍历
- 后序遍历
- 节点总数
- 各层节点
- 节点访问
- 二叉树深度
#include<stdio.h> #include<malloc.h> #define MAXSIZE 100 typedef char dataType; typedef struct bnode { dataType data; struct bnode *lChild, *rChild; }Bnode,*BTree; typedef struct { BTree data[MAXSIZE]; int front, rear; }SeQuence,*PSeqQueue; BTree createTree() { BTree tree; dataType str; str = getchar(); if (str == '#') tree = NULL; else { tree = (BTree)malloc(sizeof(Bnode)); tree->data = str; tree->lChild = createTree(); tree->rChild = createTree(); } return tree; } void visit(char ch) { printf("%c t",ch); } void preOrder(BTree tree) { BTree p = tree; if (tree == NULL) return; visit(p->data); preOrder(p->lChild); preOrder(p->rChild); } void inOrder(BTree tree) { BTree p = tree; if (tree == NULL) return; inOrder(p->lChild); visit(p->data); inOrder(p->rChild); } void postOrder(BTree tree) { BTree p = tree; if (tree == NULL) return; postOrder(p->lChild); postOrder(p->rChild); visit(p->data); } PSeqQueue initSeqQueue() { PSeqQueue queue; queue = (PSeqQueue)malloc(sizeof(SeQuence)); if (queue) { queue->front = queue->rear = 0; } return queue; } int emptyQueue(PSeqQueue queue) { if (queue&&queue->front == queue->rear) return 1; else return 0; } int pushQueue(PSeqQueue queue, Bnode *node) { if ((queue->rear + 1) % MAXSIZE == queue->front) return -1; else { queue->rear = (queue->rear + 1) % MAXSIZE; queue->data[queue->rear] = node; return 1; } } int popQueue(PSeqQueue queue, BTree *node) { if (emptyQueue(queue)) { return -1; } else { queue->front = (queue->front + 1) % MAXSIZE; *node = queue->data[queue->front]; return 1; } } void destryQueue(PSeqQueue *queue) { if (*queue) { free(*queue); *queue = NULL; } } void levelOrder(BTree tree) { BTree p = tree; PSeqQueue queue = initSeqQueue(); if (p) { pushQueue(queue,p); while (!emptyQueue(queue)) { popQueue(queue,&p); visit(p->data); if(p->lChild) pushQueue(queue, p->lChild); if (p->rChild) pushQueue(queue, p->rChild); } } } int height(BTree tree) { int h1, h2; if (tree == NULL) return 0; else { h1 = height(tree->lChild); h2 = height(tree->rChild); if (h1 > h2) return h1 + 1; else return h2 + 1; } } void levelCount(BTree tree,int num[],int l) { if (tree) { num[l]++; levelCount(tree->lChild, num, l + 1); levelCount(tree->rChild, num, l + 1); } } int countTree(BTree tree) { int lCount, rCount; if (tree == NULL) return 0; lCount = countTree(tree->lChild); rCount = countTree(tree->rChild); return lCount + rCount + 1; } int main() { BTree tree = createTree(); int i = 0; int countNum[10] = { 0,0,0,0,0,0,0,0,0,0 }, l = 1, treeHeight, treeCount;//记录每层的节点数,l从1开始,树的深度 treeHeight = height(tree); printf("n此二叉树的深度为: %dn", treeHeight); treeCount = countTree(tree); printf("此二叉树的节点总数为: %dn", treeCount); levelCount(tree, countNum, l); printf("此二叉树各层的节点数为: "); for (i = 1; i <= treeHeight; i++) { printf("第%d层数目: %d, ", i, countNum[i]); } printf("nn"); printf("先序遍历此二叉树: "); preOrder(tree); printf("n"); printf("中序遍历此二叉树: "); inOrder(tree); printf("n"); printf("后序遍历此二叉树: "); postOrder(tree); printf("n"); printf("层次遍历此二叉树: "); levelOrder(tree); printf("n"); return 0; }
24.必会小点
24.1 四舍五入
- 通过float类型转变为int类型即可实现
- float a; 假设a=5.6;则四舍五入操作为:
int b=(int)(a+0.5);
24.2 逗号表达式
逗号表达式的要领：
- 1.从左到右逐个计算；
- 2.逗号表达式作为一个整体，它的值为最后一个表达式的值；
- 3.逗号表达式的优先级别在所有运算符中最低。
例如：
x=y=1; z=x++,y++,++y; printf("x=%d,y=%d,z=%d",x,y,z); 由于赋值运算符优先级大于逗号表达式优先级，所以z=1; x=2;y=3 若z=(x++,y++,++y) 则z=3; x=2;y=3; 若z=(x++,++y,y++) 则z=2; x=2;y=3;
同时也说明了一个问题对于z=(x++,y++,++y);中，y++执行完后，再去执行++y，即y++后，y变为2，++y变为3.而不是先y++，只按照赋值，后面+1未操作，这样是不对的。 带括号记住逗号表达式中取最后一个为逗号表达式的值，不带括号，要注意赋值运算或者其他运算，自左向右进行。
24.3 void 类型指针
可以指向任何类型的数据，也可以用任意数据类型的指针对void指针赋值。 int *pint; void *pvoid; pvoid = pint; //right; pint = pvoid; //error; pint = (int *)pvoid;//right，强制转化可以
24.4 内存分配
1.静态分配
int a[50]; int *p; p=a;
2.动态分配
int *p=(int *)malloc(sizeof(int));
24.5 质数分解
#include<stdio.h> int main() { int i, j, val; printf("请输入一个正整数:"); scanf("%d",&val); printf("将该正整数分解质因数输出为："); printf("%d=",val); for (i = 2; i <val; i++) { if (val%i == 0) { printf("%d*", i); val /= i; } } printf("%d",val); printf("n"); return 0; }
24.6 大小写转化
if (p[i] >= 'a'&&p[i] <= 'z') //小写转大写 //s[i] = p[i] - 32; //s[i]=p[i]-'a'+'A'; if (p[i] >= 'A'&&p[i] <= 'Z') //大写转小写 s[i] = p[i] + 32; //s[i] = p[i] - 'A' + 'a';
24.7 字符数字转化为整型数字
'1'–> 1
#include<stdio.h> int main() { char ch; ch=getchar(); int a = ch - '0'; //int a = ch - 48; printf("%dn",a); //数字转字符 int b = 98; char ch1 = (char)b; putchar(ch1); return 0; }
25.常考小点
25.1 完数
例如：6=1+2+3，即所有因子之和
int fun(int n, int a[], int *k) { int t = n; int i, j=0; for (i = 1; i < n; i++) { if (n%i == 0) { a[j++] = i; t -= i; } } *k = j; if (t == 0) return 1; else return 0; }
25.2 闰年
leap = (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
25.3 统计输入的数是几位数
int fun(int n) { int bits = 1; while (n / 10) { bits++; n /= 10; } return bits; }
25.4 注意事项
1.gets/gets_s函数只能传数组名，而不能传指针 2.求int类型数组长度 a[]={1,6,8,3,6,0,10}; int len=sizeof(a)/sizeof(int);
25.5 字符串比较
int compare(char *s1, char *s2) { while (*s1&&*s2&&*s1 == *s2) { s1++; s2++; } if (*s1 == ' '&&*s2 == ' ') return 0; else return *s1 - *s2; }
25.6 转二进制
void stobinary(int *p) { int i,j; int k,result; int m; for (i=0,j=0;j<N;j++) { k = 1; result = 0; while (p[j]) { m = p[j] % 2; result += k*m; k = k * 10; p[j] /= 2; } a[i++] = result; } int t = i; for (i = 0; i < t; i++) { printf("%3dn",a[i]); } }
25.7 文件指针
文件指针是指针类型的变量
文件指针是指针变量，存储的是文件缓存首地址，而不是文本在计算机磁盘中的路径信息
b=a>>2后，a还是a，只是b变
注意数组陷阱:a[5]={9,1,3,4};还有一个元素0
25.8 sizeof与strlen
//指针是固定的4字节 CHAR *A = "SA"; SIZEOF(A)=4; //如果数组[]没数字，SIZOEF根据后面的字符串长度来算，如果有数字，直接是数字值 CHAR A[] = "ADSASD"; SIZEOF(A) = 7;
25.9 转义符
char *str1 = "asd sa"; char *str1 = "ad 阿斯达"; puts(str1); //ad //分析: 后面是字符/汉字，而不是数字，不能表示八进制数，直接推出，输出ad /*char *str2 = "ad 125456"; puts(str2);*/ //ad换一行(n)5456 //分析: 后面两位与 表示八进制数,则八进制12对应十进制10即n; char *str2 = "ad 85456"; puts(str2); //ad //分析: 后面第一位直接是8，超过8进制范围，直接结束，此时只输出ad //char *str3 = "adxgsdd";//编译器报错，无法运行，x后面的g超出十六进制范围 //char *str3 = "adx1112"; //有x则对后面所有数字组合成十六进制进行转化，而1112转化为十进制4370，会报"对字符来说太大"错误 char *str3 = "adx9 5"; //x9对应制表符 printf("%d", strlen(str3));//strlen,不算末尾的 ,4个字符长 a d 十六进制x9--对应十进制9即制表符t 八进制 5对应5对应梅花 puts(str3); //x与 一点不同之处在于，当x后面跟的数字不符合十六进制，则会报错，因为x不会像 那样， 是字符串结束标记， //后面跟的数字即使不符合结束标记，它也不会报错，此时会直接作为字符串结束标记，结束字符串，而x后面必须跟合法的十六 //进制数，否则直接报错。 char *str4 = "t 17 qw"; printf("%s", str4); printf("n%dn", strlen(str4)); //2个分别是制表符t与八进制 17对应的十进制15即太阳，共两个字符 char *str5 = "ta 17bc"; printf("n%d,%dn", strlen(str5), sizeof(str5)); //5 4 5个字符分别是t a 17 b c
25.10 数字正反序
//正序输出 8765 int n,t,s=1,x=0; while(n) { t=n%10; x+=t*s; s*=10; n/=10; } //逆序输出5678 int n,t,x=0; while(n) { t=n%10; x=x*10+t; n/=10; }
25.11 求最后三位
x=x/1000;
25.12 一维与二维数组对比
char *s[] = {"c language","pascal","masm"}; printf("%sn",s[1]+2); //输出---scal printf("%cn",s[1][2]);//或printf("%c",*(s[1]+2)); //输出s
25.13 优先级
int a = 1,b = 2, c = 0; printf("%d", a || b&&c); //1,&&优先级高于||优先级
括号成员第一,全体单目第二
&乘除余三 //这个"余"是指取余运算即%
加减四,移位五
关系六,等于不等排第七
位与异或和位或三分天下八九十,逻辑与十一
逻辑或十二,条件(十三、？：)高于赋值(十四=)
逗号运算级最低!
例：
int i = 1 << 1 + 1; printf("%d",i); //4---+-优先级排四，位移五
