单链表-学习

1,单链表类型描述：

typedef char DateType;

typedef struct node{
    DateType data;
    struct node *next;
}ListNode, *LinkList;

LinkList p,head;

2,建立单链表,并以换行符'\n'为输入条件结束标志符：

  （1）头插法建表：将新的节点插入当前链表的表头上

LinkList CreatListF(void)
{
    char ch;
    LinkList p = NULL,head = NULL;
    ch = getchar();

    while(ch != ‘\n’)
    {
        p = (LinkList)malloc(sizeof(ListNode));
        p->data = ch;
        p->next = head;
        head = p;

        ch = getchar();
    }

    return head;
}

   (2)尾插法建表：将新节点插入到当前链表的表尾上

LinkList CreatListT(void)
{
    char ch;
    LinkList head = NULL;
    Linklist p = NULL,T = NULL;//T始终指向链表尾节点指针

    ch = getchar();
    while(ch != "\n")
    {
        p = (LinkList)malloc(sizeof(ListNode));
        p->data = ch;
        if(head == NULL)
        {
            head = p;//空表插入第一个新节点
        }
        else
        {
            T->next = p; //将第二个之后的新节点放入*T之后
        }
        T = P;
        ch = getchar();
    }
    if(T != NULL)
    {
        T->next = NULL; ////尾节点指针域应被置空
    }

    return head;
}

3,单链表的查找运算：

（1）按序号查找

//在带头结点的单链表head中查找第i个结点，若找到（0≤i≤n），则返回该结点的存储位置，否则返回NULL，头结点可看做是第0个结点。

ListNode* GetNode(LinkList head,int i)
{
    int j;
    LinkList p = NULL;

    p = head;
    j = 0; //从头结点开始查找

    while((p->next != NULL) && (j < i))
    {
        p = p->next;
        j++;
    }

    if(i == j)
    {
        return p; //找到
    }
    else
        return NULL; // 没有找到

}

（2）按值查找：

从开始结点出发，顺着链逐个将结点的值和给定值key作比较，若有结点的值与key相等，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。

ListNode* LocateNode(LinkList head,DataType key)
{
    ListNode *p = head->next;
    while((p != NULL) && (p->data != key))
    {
        p = p->next;
    }
    return p;

}

4,单链表的插入运算：

插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间，

实现：将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上

void InsertList(LinkList head,DataType x,int i)
{
    ListNode *P;
    ListNode *NewNode;

    P = GetNode(head,i-1);//第i-1节点
    if(p == NULL)
       Error("position error\n");错误退出

    NewNode = (ListNode*)malloc(sizeof(ListNode));
    p->next = NewNode;
    NewNode->next = p->next;
    NewNode->data = x;

}

5,单链表的删除运算：

删除运算是将表的第i个结点删去，实例：/删除带头结点的单链表head上的第i个结点

void DeleteList(LinkList head,int i)
{
    ListNode *p,*DeleteNode;

    p = GetNode(head,i-1);//获取i-1节点
    if((p == NULL) && (p->next == NULL)) //考虑尾节点
    Error("position error\n"); //错误退出

    DeleteNode = p->next;
    p->next = DeleteNode->next;
    free(p);//释放内存空间

}