C和指针 第十二章 使用结构和指针

链表是一种常用的数据结构，每个节点通过链或者指针链接在一起，程序通过间接指针访问链表中的节点。

typedef struct Node  {
    //指向下一个节点的指针
     struct Node *next;
     int value;    
}

单链表只可以单向遍历

单链表中插入：第一版

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

typedef struct Node {
	struct Node *next;
	int value;
} LinkList;

//假设链表从小到大排序
int linkInsert(LinkList * current, int value)
{
	//保存前一个节点
	LinkList *previous;
	LinkList *new;

	//循环到合适的位置
	while (current-> value < value) {
		previous = current;
		current = current->next;
	}

	new = malloc(sizeof(LinkList));
	if (new == NULL) {
		return FALSE;
	}

	new->value = value;
	new->next = current;
	previous->next = new;

	return TRUE;
}

当插入值到表头和表尾时，会出错，需要加上对特殊情况的判断，将传入的第一个参数由，指向链表头部节点的指针改为，指向 指向链表头部的指针的指针，这样就可以添加节点到链表的头部。

添加特殊情况处理的版本二：

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

typedef struct Node {
    struct Node *next;
    int value;
} LinkList;

//
int linkInsert(LinkList **rootPtr, int value)
{
    //保存前一个节点
    LinkList *previous;
    LinkList *current;
    LinkList *new;

    current = *rootPtr;
    previous = NULL;

    //循环到达末尾和找到符合要求的节点
    while (current != NULL && current-> value < value) {
        previous = current;
        current = current->next;
    }

    new = malloc(sizeof(LinkList));
    if (new == NULL) {
        return FALSE;
    }

    new->value = value;
    new->next = current;

    //指向列表首页
    if(previous == NULL){
        *rootPtr = new;
    }else{
        previous -> next = new;
    }

    return TRUE;
}

int main()
{
    LinkList third = {NULL, 4};
    LinkList second = {&third, 2};
    LinkList first = {&second, 1};
    LinkList *head = &first;
    LinkList **rootPtr = &head;

    linkInsert(rootPtr, 0);

    LinkList *pre = NULL;
    LinkList *current = *rootPtr;
    while(current != NULL){
        printf("%d	", current -> value);
        pre = current;
        current = current -> next;
    }

    return 0;
}

优化：

版本二把一个节点插入到链表的起始位置当做一种特殊情况处理，对于新节点需要修改的是根节点，对于其他任何点，修改的是前一个节点的next字段，其实这个两个修改是相同的，即修改指向当前节点的指针，所以当我们移动到下一个节点时，需要保存的是指向下一个节点的next字段的指针，而不是保持指向下一个节点的指针

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

typedef struct Node {
    struct Node *next;
    int value;
} LinkList;

//
int linkInsert(LinkList **nextPtr, int value)
{
    LinkList *current;
    LinkList *new;

    //nextPtr为指向当前节点的next字段的指针
    while ((current = *nextPtr) != NULL && value > current -> value) {
        nextPtr = &current -> next;
    }

    new = malloc(sizeof(LinkList));
    if (new == NULL) {
        return FALSE;
    }

    new-> value = value;
    new-> next = current;
    //前一个节点指向最新的节点，即使是表头也可以正常处理
    *nextPtr = new;

    return TRUE;
}

int main()
{
    LinkList third = {NULL, 4};
    LinkList second = {&third, 2};
    LinkList first = {&second, 1};
　　//把head当做next字段，指向第一个节点
    LinkList *head = &first;
    LinkList **nextPtr = &head;

    linkInsert(nextPtr, 3);

    LinkList *current = *nextPtr;
    while(current != NULL){
        printf("%d	", current -> value);
        current = current -> next;
    }

    return 0;
}