C语言学习笔记

学习内容

计算概论（基于C语言，北大主干基础课）
从问题到程序————程序设计与C语言引论
数据结构（基于C语言，北大主干基础课）
C语言程序设计——课程材料、参考材料和讨论
最常用标准库函数
裘宗燕（Qiu Zongyan） 北京大学数学学院信息科学系教授
理论计算机

习题

1) 写出运行结果

#include <stdio.h>

int main() {
    unsigned int i = -2;
    int j = ~i;
    printf("%d\n", j);
}

2) 写出运行结果

#include <stdio.h>

void swap(int &a, int &b) {
    a ^= b ^= a ^= b;
}

int main() {
    int m = 5, n = 3;
    swap(m, n);
    printf("m = %d, n = %d\n", m, n);
}

表的顺序表示 答案

/* 定义顺序表的大小。应根据需要修改 */
#define MAXNUM 20

/* 定义顺序表的元素类型。应根据需要修改 */
typedef int DataType;

struct SeqList {      
    int      n;                /* 存放线性表中元素的个数 n < MAXNUM  */
    DataType element[MAXNUM];    /* 存放线性表中的元素 */
};

typedef struct SeqList *PSeqList;

/* 创建新的顺序表 */
PSeqList createNullList_seq(void);

/* 释放顺序表 */
void freeList_seq(PSeqList palist);

/* 判断顺序表是否为空 */
int isNullList_seq(PSeqList palist);

/* 在palist所指顺序表中下标为p的元素之前插入元素x */
int insert_seq(PSeqList palist, int p, DataType x);

/* 在palist所指顺序表中删除下标为ｐ的元素 */
int delete_seq(PSeqList palist, int p);

/* 求x在palist所指顺序表中的下标 */
int locate_seq(PSeqList palist, DataType x);

/* 求palist所指顺序表中下标为p的元素值 */
DataType retrieve_seq(PSeqList palist, int p);

表的链接表示 答案

/* 定义链接表元素类型。应根据需要定义 */
typedef int DataType;

struct Node;                      /* 单链表结点类型 */
typedef struct Node *PNode;      /* 结点指针类型 */
typedef struct Node *LinkList;  /* 单链表类型 */

struct Node {                       /* 单链表结点结构 */
    DataType info;
    PNode    link;
};

/* 创建一个带头结点的空链表 */
LinkList createNullList_link(void);

/* 释放一个带头节点的链表 */
void freeList_link(LinkList llist);

/* 判断llist带有头结点的单链表是否是空链表 */
int isNullList_link(LinkList llist);

/* 在llist带头结点的单链表中下标为i的(第i+1个)结点前插入元素x */
int insert_link(LinkList llist, int i, DataType x);

/* 在llist带有头结点的单链表中删除第一个值为x的结点 */
int delete_link(LinkList llist, DataType x);

/* 在llist带有头结点的单链表中找第一个值为x的结点存储位置 */
PNode locate_link(LinkList llist, DataType x);

/* 在带有头结点的单链表llist中求下标为i的(第i+1个)结点的存储位置 */
/* 当表中无下标为i的(第i+1个)元素时，返回值为NULL */
PNode find_link(LinkList llist, int i);

枚举

#include <stdio.h>

void chai(int a[], int i) {
    a[2] = i%10; i /= 10;
    a[1] = i%10; i /= 10;
    a[0] = i;
}

int zhong(int w[]) {
    int f[] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    for(int i=0; i<9; i++) {
        if(f[w[i]]) return 0;
        f[w[i]] = 1;
    }
    return 1;
}

int main() {
    for(int i=123; i<=329; i++) {
        int w[9];
        chai(w, i);
        chai(w+3, 2*i);
        chai(w+6, 3*i);
        if(zhong(w)) printf("%d %d %d\n", i, 2*i, 3*i);
    }
}

#include <stdio.h>
#define N 6

static int s[N][N];

void output_solution() {
    if(s[0][10] == N*N || s[2][11] == N*N || s[3][12] == N*N) {
        for(int y=0; y<N; y++) {
            for(int x=0; x<N; x++) printf("%02d ", s[x][y]);
            printf("\n");
        }
        printf("\n");
    }
}

void dfs(int x, int y, int count) {
    struct {
        int x;
        int y;
    } hn[] = {
        { 1, 2}, { 2, 1}, { 2,-1}, { 1,-2},
        {-1,-2}, {-2,-1}, {-2, 1}, {-1, 2}
    };
    if(count > N*N) {
        output_solution();
        return;
    }
    for(int i=0; i<8; i++) {
        int tx = x + hn[i].x;
        int ty = y + hn[i].y;
        if(0<=tx && tx<N && 0<=ty && ty<N && !s[tx][ty]) {
            s[tx][ty] = count;
            dfs(tx, ty, count+1);
            s[tx][ty] = 0;
        }
    }
}

int main() {
    s[1][0] = 1;
    dfs(1, 0, 2);
}

递推

#include <stdio.h>

unsigned long Fibonacci(int n) {
    static unsigned long F[100] = {1, 1};
    static int N = 2;
    while(N<n) {
        F[N] = F[N-1]+F[N-2];
        N++;
    }
    return F[n-1];
}

int main() {
    printf("Fibonacci(2)=%lu\n", Fibonacci(2));
    printf("Fibonacci(3)=%lu\n", Fibonacci(3));
    printf("Fibonacci(5)=%lu\n", Fibonacci(5));
    printf("Fibonacci(19)=%lu\n", Fibonacci(19));
    printf("Fibonacci(80)=%lu\n", Fibonacci(80));
    printf("Fibonacci(90)=%lu\n", Fibonacci(90));
    printf("Fibonacci(91)=%lu\n", Fibonacci(91));
    printf("Fibonacci(92)=%lu\n", Fibonacci(92));
    printf("Fibonacci(93)=%lu\n", Fibonacci(93));
    printf("Fibonacci(95)=%lu\n", Fibonacci(95));
    printf("Fibonacci(100)=%lu\n", Fibonacci(100));
}

贪心、递归、递推和动态规划

文章一
文章二
文章三
文章四

基本算法之分治

大数乘法
文章一
文章二
文章三

基本算法之搜索

文章一
文章二
文章三