LinkList

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

typedef struct Node
{
    int data;               //数据域，可以很复杂
    struct Node * pNext;    //指针域
}*PNODE,NODE;

PNODE create_list();        //创建链表
void traverse_list(PNODE);  //遍历链表
bool empty_list(PNODE);       //判断链表是否为空
int length_list(PNODE);     //得到链表长度
bool insert_list(PNODE,int,int);        //在pos位置前插入值为val的新节点，pos>=1
bool delete_list(PNODE,int,int *);      //删除
void sort_list(PNODE);                  //排序

int main()
{
    int val;        //临时存储函数返回的节点值
    PNODE pHead = NULL;
    pHead = create_list();
    traverse_list(pHead);
    insert_list(pHead,3,99);
    traverse_list(pHead);

    if(delete_list(pHead,3,&val))
        printf("删除的第三个节点是%d\n",val);
    else
        printf("删除失败！\n");

    traverse_list(pHead);
    return 0;
}

PNODE create_list()
{
    int len;    //存放有效节点个数
    int i;
    int val;    //临时存放用户输入节点的值

    PNODE pHead = (PNODE)malloc(sizeof(NODE));      //创建头节点
    if(NULL == pHead)
    {
        printf("内存分配失败，程序终止！\n");
        exit(-1);
    }
    PNODE pTail = pHead;        //临时充当尾节点
    pTail->pNext = NULL;

    printf("请输入你需要生成链表节点数：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("内存分配失败，程序终止！\n");
            exit(-1);
        }
        pNew->data = val;
        pTail->pNext = pNew;
        pNew->pNext = NULL;
        pTail = pNew;
    }
    return pHead;
}

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

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

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

void sort_list(PNODE pHead)
{
    int i,j,t;
    int len = length_list(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)
        {
            t = p->data;
            p->data = q->data;
            q->data = t;
        }
    }
    return;
}

bool insert_list(PNODE pHead,int pos,int val)       //在pos位置前插入值为val的新节点，pos>=1
{
    int i = 0;
    PNODE p = pHead;

    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("动态内存分配失败！\n");
        exit(-1);
    }
    pNew->data = val;
    PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;

    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;
}