链表基础知识

链式结构：通过结构成员的指向同类型结构的指针成员，指针成员把一个结构和另一个结构链接起来，利用指针成员可以实现多种形式的数据组织，如线性链表、二叉链表、邻接表等。一个结构中包括数据域和指针域，数据域是存放数据的，指针域是链接单元。

定义示例：

struct node
{
	int data;
	struct node *next;//用结构体名称定义一个指针 
};
typedef struct node Node;

链表的实现：

1、创建链表：若要使用链表，需要在声明节点之后先创建链表，并对链表初始化。链表的创建实质上是头节点的创建。若创建一个空链表，则链表节点的指针应指向NULL，数据域存储的链表长度应为0.

pHead *createList()
{
    pHead *ph=(ListNode*)malloc(sizeof(ListNode));//创建头指针
    ph->data = 0;  //初始化链表长度
    ph->next = NULL; //初始化头指针指向
    return ph;
}

2、插入节点：单链表通过节点的指针域来记录下一个节点的位置，从而实现所有节点的连接。因此，当插入一个新元素时，修改节点指针域的指向关系，再修改链表头节点中链表的长度，使其值加1即可。

（1）头插法：是向链表头部插入新元素，即将新元素插入链表节点之后。代码演示：

int insertHead(pHead *ph,int data)
{
    //创建新节点
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    if(NULL = newNode)
        return -1;
    newNode->data = data;
    //插入新节点
    newNode->next = ph->next;
    ph->next = newNode;
    //链表长度加1
    ph->data++;
    return 0;
}

（2）尾插法：将待插入的节点插入到最后一个节点之后，使得插入节点成为尾节点。代码演示：

int insertTail(pHead *ph,int data)
{
    pHead *p = ph;
    //找到尾节点
    while(p->next!=NULL)
    {
        p = p->next;
    }
    //创建新节点
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    if(NULL = newNode)
        return -1;
    newNode->data = data;
    //插入新节点
    newNode->next = NULL;
    p->next = newNode;
    ph->data++;
    return 0;
}

3、删除节点：要删除链表中的元素，只需要使该元素前驱节点（当前节点的上一个节点）中的指针指向该元素的后继节点（当前节点之后的节点），释放该节点占用的内存空间，再使链表长度减1即可。单链表只能根据当前节点的next指针找到后继节点，不能由当前节点找到其前驱节点；前驱节点指向后继节点，亦无法利用前驱节点访问已删除的节点。在执行删除操作之前，应先找到并记录待删除结点和其前驱节点，释放删除节点后，前驱节点指针域保存删除节点的后继节点地址。

代码演示：

int delNode(pHead *ph,int pos)
{
    pHead *p = ph;
//判断链表是否为空
    if(NULL = p->next)
    {
        printf("链表为空\n");
        return -1;
    }
//判断位置是否合理
    int len = ph->data;
    if(pos<1||pos>len)
    {
        printf("位置错误\n");
        return -2;
    }
//找到并记录要删除的节点及其前驱节点
    ListNode *pre = ph;
    for(int i;i<pos;i++)
    {
        pre = p;
        p = p->next;
    }
    pre->next = p->next;
    ph ->data--;
    free(p);
    return 0;
}
    

4、遍历链表：遍历链表就是逐个访问链表节点，读取节点中储存的数据。代码演示：

void printList(pHead *ph)
{
    pHead *p = ph;
    while(p->next!=NULL)
    {
        p = p->next;
        printf("%3d",p->next);
    }
}