单向链表

数据元素的逻辑顺序是通过链表中的指针连接次序来实现的

★基础：定义、创建、插入、删除

★进阶：查找、清空、倒置（最难）

1.头指针、头结点、数据首结点

头指针：是指向链表中的第一个结点（头结点或数据首结点）的指针，单链表可由一个头指针唯一确定
头结点：在链表的数据首结点之前附设的一个结点，不存数据
数据首结点：链表中存储第一个数据元素的结点

2.定义

struct Node
{
    Type data;//int data/double.....
    struct Node *next;
}；

(1)指针后移操作： p=p->next

(2)指向指针的指针: Node **h;

3.单向链表的基本运算的实现

（1）初始化

void ininode(Node *head)
{
    *head=(Node*)malloc(sizeof(Node));
    (*head)->next=NULL;
}

（2）创建动态结点

Node* getnode(Type item)
{
    Node* newnode=(Node*)malloc(sizeof(Node));
    if(newnode==NULL)
    {
        printf("overflow!");
        exit(1);
    }
    newnode->data=item;
    newnode->next=NULL;
    return (newnode);
}

（3）后插运算

步骤：
①找插入位置，指针p指向插入结点，即ai-1
②nextptr指向要插入的结点
③插入：
1. nextptr->next=p->next;

2. p->next=nextptr;

12不可以交换

void insertafter(Node *p,Node *nextptr)
{
    nextptr->next=p->next;
    p->next=nextptr;
}

（4）顺序插入（按增序把数据插入链表）

步骤：
①用一个指针指向链表头结点。
②用另一个指针指向新创建的数据结点
③寻找插入位置
④插入新的数据结点

void listinsert(Node *head,Type item)
{
    Node *p,*newp;
    p=head;
    newp=getnode(item);//创建新结点
    //搜索链表，寻找插入位置
    while(p->next!=NULL)
    {
        if(p->next->data<item) p=p->next;
        else break;
    }
    insertafter(p,newp);
}

（5）后删（删除P结点的后继结点）

①t=p->next;
②p->next=t->next;
③free(t);

Node *deleteafter(Node *p)
{
    Node *t=p->next;
    if(t!=NULL) p->next=t->next;
    return (t);
}

（6）查找（查找数据）

Node *findnode(const Node *h,Type item)
{
    Node *p=h->next;
    while(p!=NULL)
    {
        if(p->data==item) break;
        p=p->next;
    }
    return (p);
}

（7）清表（执行清表操作后结果为空表）

void listclear(Node *h)
{
    Node *p=deleteafter(h);//删除数据首结点
    while(p!=NULL)
    {
        free(p);//释放结点空间
        p=deleteafter(h);//继续删除下一个结点
    }
}

（8）逆置：将单向链表中的数据逆置

步骤：
① 令指针rear指向链表头结点。
② 如果链表非空，令指针rear指向数据首结点。
③ 如果*rear有后继结点，就删除其后继结点， 并把删除的结点插到链表头结点之后，否则算法结束。

void revert(Node *head)
{
    Node *rear=head,*del;
    if(head->next!=NULL) rear=head->next;
    while(rear->next!=NULL)
    {
        del=deleteafter(rear);
        insertafter(head,del);
    }
}