ReadMe

本文用来记录2022年秋季学期笔者从王瑀屏老师《程序设计基础》课堂上以及作业中获得的感悟。

平时作业见：to be continued（等我结课了我再把仓库放出来）

https://github.com/liuydd/programming-fundamentals

一、位运算符

1.将a左移b位：左移一位相当于乘2，故可由此计算2的n次方。

2.位与&和位或|：将数字转化为二进制后在每一位上与or或，其他的位运算符同理。

3.进行复杂运算时记得把括号加全。

二、一点点指针的知识

是谁，直到现在都不太会用指针

1
2
3
4
int *p=NULL;
int n=1;
int *p=&n;
*p=2;

即p会输出n的地址，而*p会输出n的值

int *a为指针，而int &a就是单纯地引用

三、写作业时的感悟

  • string类的每一位为字符类型，比较大小可采用m[i]>’9’;
  • 若字符串里储存的是数字，则应该减去’0’而不是’a’。如m[i]=m[i]+n[i]-‘0’;
  • 判断时可以把情况少的放在前面，这样&&符号会自动把后面的砍掉
  • 冒泡排序：遍历所有的数，每一轮遍历中都判断相邻两个数的顺序。故有两个循环，同时要注意第二个循环条件为j<n-1。

四、筛法

筛法求1~100内的所有素数并输出

原来的思路：利用素数的定义，循环用每一个数去除以当前的数，即

1
2
3
for(int i=2;i<=100;i++){
	for(int j=i+1;j<100;j++)
}

稍微简化一点：

1
2
3
for(int i=2;i<=100;i++){
    for(int j =i+1;j<=sqrt(100);j++)
}

本质还是列出每一个数，然后用数挨个来作除法

而筛法： $O(nlog(n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(){
	bool isPrime[110];
    for(int i=0;i<110;i++)
        isPrime[i]=true;
    for(int i=2;i*i<=100;i++){
        if(isPrime[i]){
            for(int j=i*i;j<=100;j+=i){
                isPrime[j]=false;
            }
        }
    }
    for(int i=2;i<=100;i++){
        if(isPrime[i])
            cout<<i<<endl;
    }
    return 0;
}

思路是在这100个数中逐一筛掉2的倍数、3的倍数……

精髓在于利用数组（筛子），仅对需要处理的数进行枚举遍历，而非遍历每个数后再进行判断。

例：对1~100的每一个数求欧拉函数$\phi(n)=n\prod_{n|p}(a-\frac{1}{p})$

1
//to be continued...

五、查找

1.线性查找

即循环遍历

2.折半查找 $O(log_2 n)$

需要先对数组中的元素进行排序

1
2
3
4
5
6
7
8
9
10
int id=-1,low=0,high=9;
    while(low<=high){
        int middle=(low+high)/2;
        if(target==cards[middle])
            id=middle;
        else if(target>cards[middle])
            low=middle+1;//通过改这里的和下面的可以将每次的范围控制为前闭后开或前开后闭等等
        else
            high=middle-1;
    }

3.索引查找

关键词作为数组下标，直接找到目标。

但是需要关键字是比较小的数

so…

1
2
3
Package pkgs[5];
Package * shelf[10][30];
shelf[1][13]=&pkgs[0]; //这里还是要用*和&，否则只是传值不传参

4.散列查找（哈希查找）

通过散列函数，将关键字映射为较小的整数，再将这一整数作为数组下标，完成查找。

最简单的散列函数：key%p，p为质数

六、排序

1.选择排序 $O(n^2)$

每次选择剩余元素中最大的放在后面

思路：从后往前枚举每个位置i，找到位置i之前的最大的数，将最大的数交换到位置i处

1
2
3
4
5
6
7
8
9
10
11
for(int i=9;i>=0;i--){
    int max=cards[0],maxid=0;
    for(int j=0;j<=i;j++){
        if(cards[j]>max){
            max=cards[j];
            maxid=j;
        }
    }
    cards[maxid]=cards[i];
    cards[i]=max;
}

2.冒泡排序 $O(n^2)$

比较相邻的元素，如果顺序不正确就进行交换

1
2
3
4
5
6
7
8
9
for(int i=9;i>=0;i--){ //一个向前，一个向后
    for(int j=0;j<i;j++){
        if(cards[j]>cards[j+1]){
            int tmp=cards[j];
            cards[j]=cards[j+1];
            cards[j+1]=tmp;
        }
    }
}

七、数组、指针、结构体

1.数组的动态分配：

1
2
int *a=new int[n];
delete[] a;
1
2
3
4
5
6
//动态分配二维数组，需要分成两步进行，如
char **a=new char *[10];
a[i]=new char[20];
delete[] a;
//或者在理解了内存形式的基础上写成：
char *a=new char[200];

运用于函数的声明中：

void BubbleSort(int a[],int n);

void BubbleSort(int *a,int n);

2.结构体与指针

当一个指针指向结构体时，称其为结构体指针。

1
2
3
4
5
6
7
8
9
10
Package *linear_search(Package p[],int n,char *tgt){
    //...
    return &p[i];
}
int main(){
    Package *p=linear_search(pkgs,5,"Wang");
    cout<<(*p).payment<<endl;
    //或者
    cout<<p->payment<<endl;
}

3.结构变量的赋值

结构变量的赋值相当于内存拷贝，当结构中包含指针，给结构变量赋值可能不会达到预期的效果（此时拷贝过来的结构体中的指针和原结构体中的指针指向同一块地址）

结构变量作为函数参数：传值不传参，如：

1
2
3
4
5
6
7
8
9
10
struct adate{
  int year;
  int month;
  int day;
};
void get_today(adate today){
}
int main(){
    get_today(today);
}

即进入从main函数进入新函数后，新函数会再在内存中创造一个和传进来的结构体一模一样的结构体（地址不同），新函数会在新产生的结构体基础之上对其进行操作，而不会改变原结构体。

故应运用结构体指针，改为：

1
2
3
4
5
void get_today(adate *today){
}
int main(){
    get_today(&today);
}

同理，写个结构体交换的函数的声明也应该“带星”，运用此函数时也一定要有“&”

不过我觉得，如果是在main函数中，直接拷贝交换应该也可以。

八、常见数据结构（扩展）

队列：先进先出

栈：先进后出

链表：一种基于结构的数据结构

1
2
3
4
struct linked_node{
  int n;
  linked_node *next;
};

使用链表实现栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct linked_node{
    int n;
    linked_node * next;
};
linked_node *head=NULL;
void stack_in(int x){
    linked_node *p=new linked_node;
    p->n=x;
    p->next=head;
    head=p;
}
bool stack_out(int *px){
    if(head==NULL)
        return false;
    *px=head->n;
    linked_node *p=head;
    head=head->next; //这里是迭代
    delete p;
    return true;
}

九、递归改进（存储增强）

本质是使用一个数组把已经算了的值储存起来，避免需要调用时重新计算。

如改进递归算斐波那契数列算法：

1
2
3
4
5
6
7
8
9
10
11
int fib_result[100];
for(int i=0;i<100;i++)
    fib_result[i]=-1; //初始值设为-1，表示还没有计算
int fib_improved(int n){
    if(n==0||n==1)
        return 1;
    if(fib_result[n]>0)
        return fib_result[n];
    fib_result[n]=fib_improved(n-1)+fib_improved(n-2);
    return fib_result[n];
}

Final

课是好课，王老师也是好老师。一学期的练习让我的coding水平又提高了不少，可能还是很菜（废话，就是很菜），但至少我写出来了很多曾经是绝对写不出来的题，让我觉得还是有很大的收获。

呜呜，大作业还没有写完，希望收尾工作顺利

其实如果不横向比较的话，人会幸福的多。