链表

声明节点类型

想要建立链表,就需要有一个可以表示单个结点的结构.先声明一个结构体类型.

struct node {
    int data; // 存储数据
    struct node *next; // 结构体指针,指向下一结点
}

可以使用 typedef 来给结构命名.

typedef struct _node *nextNode;
struct node {
    int data; // 存储数据
    nextNode next; // 结构体指针,指向下一结点
}
typedef nextNode List;

创建结点

构建链表时,需要逐个创建结点,并将结点添加在链表中.创建结点可以大致分为三个步骤:

把结点分配到内存单元中.
把数据存在结点中.
把结点插入到链表中.

下面是创建结点的一种方法:

List listadd(List list,int number) /* 添加新节点到链表 */
{
    List new_node = (List)malloc(sizeof(struct _node)); // 把结点分配到内存单元中
    new_node->data = number; // 把数据存在结点中
    /* 把结点插入到链表中 */
    new_node->next = list; 
    list = new_node;
    return list; // 返回链表
}

这是创建结点的一种方法,是我们的教材中讲到的一种方法.这个函数并不会对原来的链表做修改,而是返回一个链表.然后用原来的链表等于函数的返回值.类似这样:

List list = NULL;
list = listadd(list,1);
list = listadd(list,2);

还有一点,如果使用上面这种方法创建新结点,这个链表会是倒序的.如果要创建正序的链表,需要用一个遍历先找到链表的最后一个结点,然后插入新节点.

搜索链表

创建链表后,可能需要去在链表中搜索某一个特定的值.一般情况使用for循环语句去遍历一个链表:

for(p = list; p! = NULL; p = p->next){
    ...CODE...
}

如果在函数内有一个链表的副本,在函数内修改它不会对原链表产生影响时,可以这样写:

for(;list != NULL; list = list->next){
    ...CODE...
}

当然也可以使用while循环去做这件事情:

// p = list;
while(p!=NULL){
    p = p->next;
    ...CODE...
}

因此搜索链表可以写成下面这个函数:

List listsearch(List list,int number) /* 在链表中搜索 */
{
    for(; list!=NULL && list->data != number; list = list->next);
    return list; // 将搜索到的结点返回
}

删除结点

删除结点大概分为三个步骤:

搜索到要删除的结点.
让前一个结点与后一个结点链接.
free掉要删除的结点.

List listdel(List list,int number) /* 删除结点 */
{
    List cur = NULL; // 存储当前结点
    List prev = NULL; // 存储上一结点
    for(cur = list,prev = NULL;\
        cur->data!=number && list!=NULL;\
        prev = cur, cur = cur->next);
    if(cur == NULL) // 未找到
    {
        return list;
    }
    else if(prev == NULL) // 在首结点处
    {
        list = list->next;
    }
    else // 搜索到,且不在首结点
    {
        prev = cur->next;
    }
    free(cur);
    return list;
}