单链表数据结构

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct Node
{
    int data;
    struct Node * pNext;
}NODE, *PNODE;

PNODE create_Node();
void traversal(PNODE p);
bool is_empty(PNODE);
int length(PNODE);
void sort(PNODE);
bool insert(PNODE pHead, int pos, int val);
bool delete_list(PNODE pHead, int pos, int *pVal);

int main(int argc, char * argv)
{
    PNODE p = create_Node();

    traversal(p);

    if (is_empty(p))
        printf("empty\n");
    else
        printf("not empty\n");

    printf("链表的长度为：%d\n", length(p));

    sort(p);

    traversal(p);

    insert(p, 2, 9);
    printf("插入后：\n");

    traversal(p);

    int d_val;
    delete_list(p, 2, &d_val);
    printf("删除后：\n");
    traversal(p);
    free(p);
    return 0;
}

PNODE create_Node()
{
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead)
    {
        printf("分配失败，程序终止！");
        exit(-1);
    }
    PNODE pTail = pHead;
    pTail->pNext = NULL;
    int i;
    int len;
    int val;
    printf("input arg number: len=");
    scanf("%d", &len);
    for (i = 0; i < len; ++i)
    {
        printf("第%d个值:", i+1);
        scanf("%d", &val);
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pNew)
        {
            printf("分配失败，程序终止！");
            exit(-1);
        }
        //set pNew
        pNew->data = val;
        pNew->pNext = NULL;
        //将pNew挂到pTail下
        pTail->pNext = pNew;
        //更新中间变量
        pTail = pNew;
    }
    return pHead;
}

void traversal(PNODE pHead)
{
    PNODE p = pHead->pNext;
    while (NULL != p)
    {
        printf("%d\n",p->data);
        p = p->pNext;
    }
}

bool is_empty(PNODE pHead)
{
    if (NULL == pHead->pNext)
        return true;
    else
        return false;
}

int length(PNODE pHead)
{
    PNODE p = pHead->pNext;
    int len = 0;
    while (NULL != p)
    {
        ++len;
        p = p->pNext;
    }
    return len;
}

void sort(PNODE pHead)
{
    int i, j, t;
    int len = length(pHead);
    PNODE p, q;
    for (i = 0,p = pHead->pNext; i < len - 1; ++i, p = p->pNext)
    {
        for (j = i + 1, q = p->pNext; j < len; ++j, q = q->pNext)
        {
            if (p->data > q->data)
            {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
}

bool insert(PNODE pHead, int pos, int val)
{
    int i = 0;
    PNODE p = pHead;

    //通过i的递增来定位到p节点（在p节点的后面插入新节点）
    while (NULL != p && i < pos - 1)
    {
        p = p->pNext;
        ++i;
    }

    if (i > pos - 1 || NULL == p)
    {
        return false;
    }

    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("分配失败，程序终止！");
        exit(-1);
    }
    pNew->data = val;
    pNew->pNext = p->pNext;
    p->pNext = pNew;

    return true;
}

bool delete_list(PNODE pHead, int pos, int *pVal)
{
    int i = 0;
    PNODE p = pHead;

    while (NULL != p->pNext && i < pos - 1)
    {
        p = p->pNext;
        ++i;
    }

    if (i > pos - 1 || NULL == p->pNext)
    {
        return false;
    }

    PNODE q = p->pNext;
    *pVal = q->data;

    p->pNext = p->pNext->pNext;
    free(q);
    q = NULL;
    return true;
}