主要是考完期中之后发现自己一些基础的东西（特指链表）太差了，所以去学了一下，现在把它挂上来，方便以后回忆

链表补救计划

1.malloc

malloc函数引用前需要#include
malloc函数的返回类型是void*，如果没有空间即返回失败，则返回0，或者是NULL
free()把申请的空间还给系统，申请过的空间，最终都要还，且只能还申请的空间的首地址，即申请的是什么就只能free()什么，容易出现的问题：

free后又free了一次
free的地址变了，即可能内存申请的时候用的是p，然后在程序执行时出现了p++，再去free时就会出现问题，建议先将p改为原来的值再去free

一个程序的例子： （输入一个数number，然后再连续输入number个数）

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int number, i;
    scanf("%d", &number);
    // for C99 and after
    // int a[number];
    // for malloc
    int *a;
    // 注意这里的sizeof后面是int
    a = (int*)malloc(number*sizeof(int));
    for (i=0; i<number; i++)
        scanf("%d", &a[i]);
    for (i=0; i<number; i++)
        printf("%d", a[i]);
    free(a);
    return 0;
}

2.linked list

一个程序的例子：（输入n个数，n未知，以-1结尾，再输出）

#include<stdio.h>
#include<stdlib.h>
typedef struct _node{
    int value;
    struct _node* next;
}node;
int main()
{
    node *head = NULL;
    int number;
    do{
        scanf("%d", &number);
        if (number == -1)
            break;
        node *p = (node*)malloc(sizeof(node)); //注意这里是sizeof（node）而不是sizeof(node*)
        p->value = number;
        p->next = NULL;
        if (head) //加这一步是为了确定head非空
        {
            node *tail = head;
            while (tail->next)
                tail = tail->next;
            tail->next = p;
        } 
        else 
            head = p;   
    }while(1);
    node *q = head;
    for(; q; q=q->next)
    {
        printf("%d", q->value);
    }
    return 0;
}

3.linked list 函数

这里同样也是上一个的例子

#include<stdio.h>
#include<stdlib.h>
typedef struct _node{
    int value;
    struct _node* next;
}node;
typedef struct _list{
    node* head;
}List;
void build_linkedlist(List *plist); 
int main()
{
    List list;
    list.head = NULL;
    int number;
    build_linkedlist(&list); //传进去的是list的地址
    node *q = list.head;
    for(; q; q=q->next)
    {
        printf("%d", q->value);
    }
    return 0;
}
void build_linkedlist(List *plist)
{
    int number;
    do{
        scanf("%d", &number);
        if (number == -1)
            break;
        node *p = (node*)malloc(sizeof(node)); //注意这里是sizeof（node）而不是sizeof(node*)
        p->value = number;
        p->next = NULL;
        if ((*plist).head) //加这一步是为了确定head非空
        {
            node *tail = (*plist).head; //(*plist).head相当于plist->head
            while (tail->next)
                tail = tail->next;
            tail->next = p;
        } 
        else 
            (*plist).head = p;  
    }while(1);
    return ;
}

这里是通过建立了一个函数来对链表进行操作，建立结构体List的原因是方便对链表进行管理，成体系。
我们在向函数中传参数的时候传入的是list的地址，因为我们想对head这个指针做修改，即对一个东西的地址做修改，所以我们需要传入的是地址的地址，这样才能完成对其的修改。

4.其他一些要注意的地方

如果一个指针出现在了箭头的左边例p->value中的p，我们一定在程序中要直接或间接地判断p会不会是NULL
这点非常非常重要。
一般我们很有可能会没有考虑空链表的情况

例如，在上述代码中，p和q都出现在了箭头地左边，但p是被判断过地，因为在for循环地进入条件就是p即p!=NULL，而q是没有判断过的，所以为避免错误，这里应该补充对q的判断看其是不是NULL 这一点非常非常重要

删掉链表的结点时首先让其上一个结点的结点指向其下一个结点，再free掉该结点即可

删除链表

for (p=head; p; p=q)
{
    q = p->next;
    free(p);
}

因为结束时p和q都是NULL所以就free完毕了

做题时遇到的问题

段错误

Polynomial Add( Polynomial a, Polynomial b )
{
    if (a == NULL)
        return b;
    else if (b == NULL)
        return a;
    else
    {
        Polynomial head, tail;
        tail = (Polynomial)malloc(sizeof(struct Node));
        //这里如果让不对tail做初始化也会段错误，好像是因为一定要对指针做初始化，tail地初始化是malloc来的，而head的初始化是tail来的
        head = tail;
        //这里如果写head = tail = NULL;会段错误，好像是因为如果让其为NULL，它就没有Next了，所以会段错误
        a = a->Next;
        b = b->Next;
        while (a&&b)
        {
            Polynomial this = (Polynomial)malloc(sizeof(struct Node));
            if (a->Exponent > b->Exponent)
            {
                this->Exponent = a->Exponent;
                this->Coefficient = a->Coefficient;
                a = a->Next;
            }
            else if(a->Exponent < b->Exponent)
            {
                this->Exponent = b->Exponent;
                this->Coefficient = b->Coefficient;
                b = b->Next;
            }
            else
            {
                this->Exponent = b->Exponent;
                this->Coefficient = b->Coefficient + a->Coefficient;
                a = a->Next;
                b = b->Next;
                if (this->Coefficient == 0)
                    continue;
            }
            tail->Next = this;
            tail = this;
        }
        if (a)
            tail->Next = a;
        if (b)
            tail->Next = b;
        return head;
    }
}

对于以上的代码，下面的写法也是可以通过的

Polynomial Add( Polynomial a, Polynomial b )
{
    if (a->Next == NULL)
        return b;
    else if (b->Next == NULL)
        return a;
    else
    {
        Polynomial head, tail;
        head = tail = NULL;//这里让head和tail直接为NULL
        a = a->Next;
        b = b->Next;
        while (a&&b)
        {
            Polynomial this = (Polynomial)malloc(sizeof(struct Node));
            if (a->Exponent > b->Exponent)
            {
                this->Exponent = a->Exponent;
                this->Coefficient = a->Coefficient;
                a = a->Next;
            }
            else if(a->Exponent < b->Exponent)
            {
                this->Exponent = b->Exponent;
                this->Coefficient = b->Coefficient;
                b = b->Next;
            }
            else
            {
                this->Exponent = b->Exponent;
                this->Coefficient = b->Coefficient + a->Coefficient;
                a = a->Next;
                b = b->Next;
                if (this->Coefficient == 0)
                    continue;
            }
            if (head == NULL)
                head = this;//在第一次经过时，这里和下面分布重新对tail和head做了初始化
            else
                tail->Next = this;
            tail = this;//
        }
        if (a)
            tail->Next = a;
        if (b)
            tail->Next = b;
        Polynomial head1 = (Polynomial)malloc(sizeof(struct Node));
        head1->Next = head;
        return head1;//head1的作用是为了加一个dummy head
    }
}

而对没有dummy head的情况我们用下面的代码

head = tail = NULL;
...
...
if (head == NULL)
    head = cur;
else
    tail->next = cur;
tail=cur;

但一般都是会有dummy head的，所以，嗯

给定一个有dummy head的链表，要求返回一个逆序的链表，且给定的链表也要是逆序的 (Data Structures and Algorithms (English) 6-4)

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node {
    ElementType Element;
    Position Next;
};
List Read(); /* details omitted */
void Print( List L ); /* details omitted */
List Reverse( List L );
int main()
{
    List L1, L2;
    L1 = Read();
    L2 = Reverse(L1);
    Print(L1);
    Print(L2);
    return 0;
}
/* Your function will be put here */
List Reverse( List L )
{
    if (L->Next==NULL || L->Next->Next==NULL)
        return L;
    List l1, pre, l2;
    l1 = L->Next->Next;
    l2 = L->Next;
    l2->Next = NULL;
    /*
    这里的上面三行我本来写成了
    {
        l1 = L->Next;
        l2 = L->Next;
        l2->Next = NULL;
        l1 = l1->Next;
    }
    但这样写是错的，因为我们不难看到在
    l1 = L->Next;
    l2 = L->Next;
    的赋值之后，l1和l2指向了同一块地方，而下一行的l2->Next = NULL;又对这一块地方做了修改，这就会使l1->Next也为NULL。
    */
    while (l1)
    {
        pre = l1->Next;
        l1->Next = l2;
        l2 = l1;
        l1 = pre;
    }
    L->Next = l2;
    return L;
}

如果要使给定的链表也是逆序的就要让return 参数，即L

如上图所示，一个有dummy head的linked list，即L是一块地址，它指向一块地址，而这块地址的Next也是一块地址，指向链表的第一个结点，那么，我们往一个函数里传入L相当于传入了地址的地址，即在一个函数里，虽然主函数里的L和被调函数的L是位于不同的两个地址的两个相同的值，但正因为他们相同，都指向上图中中间这个结点，如果如果我们把这个结点的next修改一下，就可以改变原主函数中L所指向的值

Tree

做到的一些题

判断两个树是否同构

int Isomorphic( Tree T1, Tree T2 )
{
    if (T1->Element == T2->Element)
    {
        if (!T1->Left && !T1->Right && !T2->Left && !T2->Right)
            return 1;
        else if (!T1->Left && !T2->Left && T1->Right && T2->Right)
            ...
    }
    else
        return 0;
}

不要像上面这么写，这么写的话会写很多，而且容易漏掉一些情况，要写成下面这种

int Isomorphic( Tree T1, Tree T2 )
{
    if (T1 == NULL && T2 == NULL)
        return 1;
    else if (T1 != NULL && T2 == NULL)
        return 0;
    else if (T1 == NULL && T2 != NULL)
        return 0;
    else if (T1 != NULL && T2 != NULL) 
    {
        if (T1 -> Element != T2 -> Element)
            return 0;
        else
            return ((Isomorphic(T1 -> Left, T2 -> Right) && Isomorphic(T1 -> Right, T2 -> Left)) || (Isomorphic(T1 -> Right, T2 -> Right) && Isomorphic(T1 -> Left, T2 -> Left)));
    }
}

即传入的T1和T2可以是NULL然后让这个函数对是不是NULL来判断，这样写的话可以省好多位置

求二叉树的高度

用一个简单的递归即可

int countheight(BinTree T)
{
    if (T==NULL)
        return 0;
    else if (countheight(T->Left) > countheight(T->Right))
        return countheight(T->Left) + 1;
    else
        return countheight(T->Right) + 1;
}

浙大课程笔记

数据结构补天记录