🪴 Quartz 4.0

链表

3 min read

有一个节点, 它含有两个值, 一个是当前他代表的值, 一个是指向的下一个值

the interface

过程解析

1️⃣ add node内部直接剪切出来

int main() {
    Node* head = NULL;
    int number;
    do {
        scanf("%d", &number);
        if (number != -1) {
            node_add(head, number);
        }
    } while (number != -1);
 
    return 0;
}
 
void node_add(Node *head, int number){
    // add a new node
    Node *p=(Node*)malloc(sizeof(Node));
    /*  既然要一个node存放新值, 为什么不直接Node p呢?
        因为我到时候是需要原最后node去指向新node的地址, 这样简洁, 真是这样吗?
        这是个本地变量, 不用malloc, node存不下来  */
    p->value=number;
    p->next=NULL;
    // find the last node
    if(!head){
        /*  如果是NULL, 那第一个就得是head */
        head=p;
    }else{
        Node *last=head;
        while(last->next){
            last=last->next;
        }
		/* 会不会觉得这里每次add找last都挺烦的? 不要担心, 是个伏笔 */
        // attach
        last->next=p;
    }
}

❓ 为什么head进去里头改变值了外面没改变?

  • 我传进去的是地址没错, 但是我没有溯源去改这个地址上的变量, 而是直接改了这个地址, 这种情况地址就是个变量(事实上也确实只是个变量而已), 那么自然不会变

2️⃣ 在链表中找到数字并删除

int main() {
    List list;
    list.head = NULL;
    int number;
    do {
        scanf("%d", &number);
        if (number != -1) {
            node_add(&list, number);
        }
    } while (number != -1);
 
    scanf("%d", &number);
    Node *p, *q = NULL;
    /* q用来记录前一个node的地址 */
    int isfound = 0;
    for (p = list.head; p; q = p, p = p->next) {
        if (p->value == number) {
            if (!p->next) {		// 特殊情况是number就是第一个数
                list.head = p->next;	// 注意第一个head要改咯
            } else {
                q->next = p->next;
            }
            free(p);
            isfound = 1;
            break;
        }
    }
    if (!isfound) {
        printf("没找到");
    }
 
    return 0;
}

❓ How do we find the boundary?

  • Any pointer at the left of -> must be checked

3️⃣ 清除链表

Node *p = list.head, *q;
while (p) {
	q = p->next;  // 收起那质朴的想法, 这样可以免去q的初值, 而且还能化简
	free(p);
	p = q;
	// q=q->next;
}
Node *p, *q;
for (p = list.head; p; p = q) {
	q = p->next;
	free(p);
}

for 循环的条件还是有玩头的

Graph View

Backlinks