Scentea 发布的文章

先看以下C语言代码执行,猜一下运算结果

#include <stdio.h>

void inplace_swap(int *x, int *y) {
    *y = *x ^ *y; /* Step 1 */
    *x = *x ^ *y; /* Step 2 */
    *y = *x ^ *y; /* Step 3 */
}
// 注: ^符号为异或运算,异或运算符合数学运算的可交换定律,符合加法逆运算a^a=0

void reverse_array(int a[], int cnt){
    int first, last;
    for (first = 0, last = cnt-1; first <= last; first++,last--) {
        inplace_swap(&a[first], &a[last]);
    }
}

int main(int argc, const char * argv[]) {
    int nums1[4] = {1,2,3,4};
    int cnt1 = sizeof(nums1) / sizeof(nums1[0]);
    reverse_array(nums1,cnt1);
    for(int i=0; i<cnt1; i++){
        printf("%d ", nums1[i]);
    }
    printf("\n");
    
    int nums2[5] = {1,2,3,4,5};
    int cnt2 = sizeof(nums2) / sizeof(nums2[0]);
    reverse_array(nums2,cnt2);
    for(int i=0; i<cnt2; i++){
        printf("%d ", nums2[i]);
    }
    printf("\n");
    
    return 0;
}

结果:

  • 遍历nums1数组,结果为4 3 2 1
  • 遍历nums2数组,结果为5 4 0 2 1
  • 多测试几遍,发现当数字元素为偶数时,结果是数组倒序的结果;当数字元素为奇数时,它就会把中间元素置成0

问题:

  1. 对于一个长度为奇数的数组,长度cnt=2k+1,函数reverse_array最后一次循环中,变量first和last的值分别是什么?
  2. 为什么这时调用函数inplace_swap会将数组元素设置为0?
  3. 对reverse_array的代码做哪些简单改动就能消除这个问题?

思路:

先来分析inplace_swap里每一步的结果,假使指针x和y指向的位置存储值分别是a和b作为开始,则有下表1:

步骤*x*y
初始ab
第1步aa^b
第2步a^(a^b)=(a^a)^b=ba^b
第3步bb^(a^b)=(b^b)^a=a

再来看nums2的reverse_array里循环:
第一次循环:a[0]值为1,a[4]值为5,套入上面公式,inplace_swap(&a[0], &a[4]),a[0]值为5,a[4]值为1;
第二次循环:a[1]值为2,a[3]值为4,套入上面公式,inplace_swap(&a[1], &a[3]),a[1]值为4,a[2]值为2;
第三次循环:a[2]值为3,a[2]值为3,套入上面公式,inplace_swap(&a[2], &a[2]),a[2]值为0,a[3]值为0;
注意第三次循环:inplace_swap里,第1步,这时x和y都指向的是同一个位置,所以当我们计算x^y时,我们得到的是0!

答案:

  1. 长度cnt=2k+1,所以first和last的值都为k,也就是2。
  2. 因为x和y都指向的是同一个位置,所以当我们计算x^y时,我们得到的是0。
  3. 使x和y指向不同位置,也就是说,reverse_array里first <= last 改为:first < last

总结:

异或运算符合交换律:a^(a^b)=(a^a)^b
异或运算符合加法逆运算:a^a=0

  • 删除上一个字符使用抄ctrl-h
  • 删除光标到行首使用ctrl-u
  • 删除光标到行尾使用ctrl-k
  • 删除一个单词ctrl-w
  • 跳转到上一个单词使知用alt-b
  • 跳转到下一个单词使用alt-f
  • 跳转到行首使用ctrl-a
  • 跳转到行尾使用ctrl-e
  • 搜索历史命令使用ctrl-r

阻塞与非阻塞

  • 线程访问资源,该资源是否准备就绪的一种处理方式

同步与异步

  • 同步和异步是指访问数据的一种机制

BIO

  • 同步阻塞IO,Block IO
  • 举例子,去上厕所,坑全满,此时我一直光等着,主动观察哪个坑位好了,只要坑位释放了,我就立马去占坑

NIO

  • 同步非阻塞IO,New IO (Non-Block IO)
  • 厕所坑全满,此时我去厕所外面玩手机干其他事情,然后时不时得再主动去厕所看看有没有坑被释放,如果有坑了去占坑

AIO

  • 异步非阻塞IO(AIO),A上厕所排队,做别的事情的同时等待别人告诉自己哪个坑没人
  • 异步阻塞IO,上厕所排队,在厕所里等待别人告诉自己哪个坑没人

#include <iostream>
typedef struct line{
    struct line * prior;
    int data;
    struct line * next;
}line;
//双链表的创建
line* initLine(line * head);
//双链表插入元素,add表示插入位置
line * insertLine(line * head,int data,int add);
//双链表删除指定元素
line * delLine(line * head,int data);
//双链表中查找指定元素
int selectElem(line * head,int elem);
//双链表中更改指定位置节点中存储的数据,add表示更改位置
line *amendElem(line * p,int add,int newElem);
//输出双链表的实现函数
void display(line * head);
int main() {
    line * head=NULL;
    //创建双链表
    head=initLine(head);
    display(head);
    //在表中第 3 的位置插入元素 7
    head=insertLine(head, 7, 3);
    display(head);
    //表中删除元素 2
    head=delLine(head, 2);
    display(head);
    printf("元素 3 的位置是:%d\n",selectElem(head,3));
    //表中第 3 个节点中的数据改为存储 6
    head = amendElem(head,3,6);
    display(head);
    return 0;
}
line* initLine(line * head){
    head=(line*)malloc(sizeof(line));
    head->prior=NULL;
    head->next=NULL;
    head->data=1;
    line * list=head;
    for (int i=2; i<=5; i++) {
        line * body=(line*)malloc(sizeof(line));
        body->prior=NULL;
        body->next=NULL;
        body->data=i;
        list->next=body;
        body->prior=list;
        list=list->next;
    }
    return head;
}
line * insertLine(line * head,int data,int add){
    //新建数据域为data的结点
    line * temp=(line*)malloc(sizeof(line));
    temp->data=data;
    temp->prior=NULL;
    temp->next=NULL;
    //插入到链表头,要特殊考虑
    if (add==1) {
        temp->next=head;
        head->prior=temp;
        head=temp;
    }else{
        line * body=head;
        //找到要插入位置的前一个结点
        for (int i=1; i<add-1; i++) {
            body=body->next;
        }
        //判断条件为真,说明插入位置为链表尾
        if (body->next==NULL) {
            body->next=temp;
            temp->prior=body;
        }else{
            body->next->prior=temp;
            temp->next=body->next;
            body->next=temp;
            temp->prior=body;
        }
    }
    return head;
}
line * delLine(line * head,int data){
    line * temp=head;
    //遍历链表
    while (temp) {
        //判断当前结点中数据域和data是否相等,若相等,摘除该结点
        if (temp->data==data) {
            temp->prior->next=temp->next;
            temp->next->prior=temp->prior;
            free(temp);
            return head;
        }
        temp=temp->next;
    }
    printf("链表中无该数据元素");
    return head;
}
//head为原双链表,elem表示被查找元素
int selectElem(line * head,int elem){
//新建一个指针t,初始化为头指针 head
    line * t=head;
    int i=1;
    while (t) {
        if (t->data==elem) {
            return i;
        }
        i++;
        t=t->next;
    }
    //程序执行至此处,表示查找失败
    return -1;
}
//更新函数,其中,add 表示更改结点在双链表中的位置,newElem 为新数据的值
line *amendElem(line * p,int add,int newElem){
    line * temp=p;
    //遍历到被删除结点
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    temp->data=newElem;
    return p;
}
//输出链表的功能函数
void display(line * head){
    line * temp=head;
    while (temp) {
        if (temp->next==NULL) {
            printf("%d\n",temp->data);
        }else{
            printf("%d->",temp->data);
        }
        temp=temp->next;
    }
}

#include <iostream>
//节点
typedef struct Link {
    int  elem;
    struct Link *next;
}link;
//初始化链表
link * initLink();
//链表插入的函数,p是链表,elem是插入的结点的数据域,add是插入的位置
link * insertElem(link * p, int elem, int add);
//删除结点的函数,p代表操作链表,add代表删除节点的位置
link * delElem(link * p, int add);
//查找结点的函数,elem为目标结点的数据域的值
int selectElem(link * p, int elem);
//更新结点的函数,newElem为新的数据域的值
link *amendElem(link * p, int add, int newElem);
void display(link *p);
int main() {
    //初始化链表(1,2,3,4)
    printf("初始化链表为:\n");
    link *p = initLink();
    display(p);
    printf("在第4的位置插入元素5:\n");
    p = insertElem(p, 5, 4);
    display(p);
    printf("删除元素3:\n");
    p = delElem(p, 3);
    display(p);
    printf("查找元素2的位置为:\n");
    int address = selectElem(p, 2);
    if (address == -1) {
        printf("没有该元素");
    }
    else {
        printf("元素2的位置为:%d\n", address);
    }
    printf("更改第3的位置上的数据为7:\n");
    p = amendElem(p, 3, 7);
    display(p);
    return 0;
}
link * initLink() {
    link * p = (link*)malloc(sizeof(link));//创建一个头结点
    link * temp = p;//声明一个指针指向头结点,用于遍历链表
    //生成链表
    for (int i = 1; i < 5; i++) {
        link *a = (link*)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}
link * insertElem(link * p, int elem, int add) {
    link * temp = p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (int i = 1; i < add; i++) {
        temp = temp->next;
        if (temp == NULL) {
            printf("插入位置无效\n");
            return p;
        }
    }
    //创建插入结点c
    link * c = (link*)malloc(sizeof(link));
    c->elem = elem;
    //向链表中插入结点
    c->next = temp->next;
    temp->next = c;
    return  p;
}
link * delElem(link * p, int add) {
    link * temp = p;
    //遍历到被删除结点的上一个结点
    for (int i = 1; i < add; i++) {
        temp = temp->next;
        if (temp->next == NULL) {
            printf("没有该结点\n");
            return p;
        }
    }
    link * del = temp->next;//单独设置一个指针指向被删除结点,以防丢失
    temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    free(del);//手动释放该结点,防止内存泄漏
    return p;
}
int selectElem(link * p, int elem) {
    link * t = p;
    int i = 1;
    while (t->next) {
        t = t->next;
        if (t->elem == elem) {
            return i;
        }
        i++;
    }
    return -1;
}
link *amendElem(link * p, int add, int newElem) {
    link * temp = p;
    temp = temp->next;//tamp指向首元结点
    //temp指向被删除结点
    for (int i = 1; i < add; i++) {
        temp = temp->next;
    }
    temp->elem = newElem;
    return p;
}
void display(link *p) {
    link* temp = p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null,就执行输出语句。
    while (temp->next) {
        temp = temp->next;
        printf("%d ", temp->elem);
    }
    printf("\n");
}