数据结构_知识点_单链表

1. 单链表定义

头指针：头指针是指向单链表第一个结点的指针，是链表必须有的。
头结点：头结点可有可无，若有，则头指针指向头结点。头结点不存储元素，可存储一些关于链表之信息（通常不储存）。但必须存储指向第一个存储元素的指针。
</br>
头结点带来的优点：
1.由于开始节点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置的操作一致，无需进行特殊处理。
2.无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。

//定义结点
typedef struct Node
{
    ElemType elem;
    Node *next;
} Node;

//定义链表
typedef Node *List;

2. 链表的创建与清空

创建：
1.头插法：新结点的指针域等于头结点的指针域（指向原来的第一结点），头结点的指针域指向新结点。

bool createList(List &l)
{
    //头插法,创建表 
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    int i;
    Node *p,*s;
    l = (Node *)malloc(sizeof(Node));
    l->next = NULL;
    
    s = (Node *)malloc(sizeof(Node));
    p = l;
    
    for(i = 0;i<10;i++)
    {
        //创建新结点
        s = (Node *)malloc(sizeof(Node));
        s->elem = a[i];
  
        //新结点的指针域等于头结点的指针域
        s->next = l->next;

        //头结点的指针域指向新结点
        l->next = s;        
    }
    
    return true;
}

2.尾插法：最后结点指针域指向新结点，新结点指针域赋值为NULL。

bool createList2(List &l)
{
    int a[10] = {1,2,3,4,5,6,7,8,9,100};
    int i;
    Node *p,*s;
    
    l = (Node *)malloc(sizeof(Node));
    p = l;
    
    for(i = 0;i < 10; i++)
    {
        //创建新结点
        s = (Node *)malloc(sizeof(Node));
        s->elem = a[i];

        //最后结点指针域指向新结点
        p->next = s;

        p = s;
    }
    //最后结点指针域为NULL
    p->next = NULL;
    return true;
}

清空：从第一个存有数据元素的结点开始，保存结点的指针域，清除该结点。通过指针域，找到下一个结点，如此重复，直到表尾。

bool clearList(List &l)
{
    Node *p,*q;
    p = l->next;
    l->next = NULL;
    while(p)
    {
        //保存结点的指针域
        q = p->next;
        //清除该结点
        free(p);
        p = q;
    }
    
    return true;
}

3. 插入与删除

插入：找到要插入位置的前一个结点，使新结点指针域等于其指针域，使其指针域指向新结点。

bool insert(List &l, int i,ElemType e)
{
    Node *p,*q;
    int j = 1;
    
    p = l->next;
    q = (Node *)malloc(sizeof(Node));

    while(p && j<i)
    {
        p = p->next;
        j++;    
    }
    
    q->next = p->next;
    p->next = q;
    q->elem = e;
    return true;
}

删除：找到要删除的结点的前一个结点，使其指针域等于待删除结点的指针域，释放带删除结点内存空间。

bool deleteNode(List l, int i)
{
    Node *p,*q;
    int k;
    p = l->next;
    
    for(k = 1;(k < i-1) && p;k++)
    {
        p = p->next;
    }
    
    q = p->next;
    p->next = q->next;
    free(q);
    return true;
}

4. 查找：

还是遍历，不断地通过结点的指针找到下一个结点