如何提高編程能力？(下)
- 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---+-優先順序排四，位移五
