单链表的操作

#include <stdio.h>
#include <stdlib.h>
#ifndef _SINGLY_LINKED_LIST_H_H
#define _SINGLY_LINED_LIST_H_H

//设计节点结构
typedef struct Node
{
    int data;
    struct Node *pNext;
} NODE, *pNODE;

//创建单向链表
pNODE CreateSgLinkList(void);

//打印单向链表
void TraverseSgLinkList(pNODE pHead);

//判断单向链表是否为空
int IsEmptySgLinkList(pNODE pHead);

//计算单向链表的长度
int GetLengthSgLinkList(pNODE pHead);

//向单向链表插入节点
int InsertEleSgLinkList(pNODE pHead, int pos, int data);

//从单向链表删除节点
int DeleteEleSgLinkList(pNODE pHead, int pos);

//删除整个链表，释放内存
void FreeMemory(pNODE *ppHead);

#endif


//创建单向链表
pNODE CreateSgLinkList(void)
{
    int i, length, data;
    pNODE p_new = NULL, pTail = NULL;
    //创建头节点，头结点是第0个节点，后面的节点从1开始计数
    pNODE pHead = (pNODE)malloc(sizeof(NODE));

    if (NULL == pHead)
    {
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
     
    pHead->data = 0;
    pHead->pNext = NULL;
    pTail = pHead;
     
    printf("请输入要创建链表的长度：");
    scanf("%d", &length);
     
    for (i=1; i<length+1; i++)
    {
        p_new = (pNODE)malloc(sizeof(NODE));
        if (NULL == p_new)
        {
            printf("内存分配失败！\n");
            exit(EXIT_FAILURE);
        }
     
        printf("请输入第%d个节点的值：", i);
        scanf("%d", &data);
     
        p_new->data = data;
        p_new->pNext = NULL;
        pTail->pNext = p_new;
        pTail = p_new;
    }
    return pHead;

}

//打印单向链表，不打印头结点的值。
void TraverseSgLinkList(pNODE pHead)
{
    pNODE pt = pHead->pNext;

    printf("打印链表：");
    while (pt != NULL)
    {
        printf("%d ", pt->data);
        pt = pt->pNext;
    }
    putchar('\n');

}

int IsEmptySgLinkList(pNODE pHead)
{
    if (pHead->pNext == NULL)
        return 1;
    else
        return 0;
}

//计算单向链表长度
int GetLengthSgLinkList(pNODE pHead)
{
    int length = 0;
    pNODE pt = pHead->pNext;

    while (pt != NULL)
    {
        length++;
        pt = pt->pNext;
    }
    return length;

}

//向单向链表插入一个节点,位置从1开始，到链表长度加1结束。
int InsertEleSgLinkList(pNODE pHead, int pos, int data)
{
    pNODE pt = NULL, p_new = NULL;

    if (pos > 0 && pos < GetLengthSgLinkList(pHead) + 2)
    {
        p_new = (pNODE)malloc(sizeof(NODE));
        if (NULL == p_new)
        {
            printf("内存分配失败！\n");
            exit(EXIT_FAILURE);
        }
        p_new->data = data;
     
        while (1)
        {
            pos--;        
            if (0 == pos)
                break;
            pHead  = pHead->pNext;
        }
     
        pt = pHead->pNext;
        pHead->pNext = p_new;
        p_new->pNext = pt;
     
        return 1;
    }
    else
        return 0;

}


//从单向链表中删除一个节点，位置从1开始，到链表长度结束。
int DeleteEleSgLinkList(pNODE pHead, int pos)
{
    pNODE pt = NULL;

    if (pos > 0 && pos < GetLengthSgLinkList(pHead) + 1)
    {
        while (1)
        {
            pos--;
            if (0 == pos)
                break;
            pHead = pHead->pNext;
        }
     
        pt = pHead->pNext->pNext;
        free(pHead->pNext);
        pHead->pNext = pt;
     
        return 1;
    }
    else
        return 0;

}


//删除整个单向链表，释放内存。
void FreeMemory(pNODE *ppHead)
{
    pNODE pt = NULL;
    while (*ppHead != NULL)
    {
        pt = (*ppHead)->pNext;
        free(*ppHead);
        *ppHead = pt;
    }
}

int main(void)
{
    int flag = 0, length = 0;
    int position = 0, value = 0;
    pNODE head = NULL;

    head = CreateSgLinkList();
    
    flag = IsEmptySgLinkList(head);
    if (flag)
        printf("单向链表为空！\n");
    else
    {
        length = GetLengthSgLinkList(head);
        printf("单向链表的长度为：%d\n", length);
        TraverseSgLinkList(head);
    }
    
    printf("请输入要插入节点的位置和元素值(两个数用空格隔开)：");
    scanf("%d %d", &position, &value);
    flag = InsertEleSgLinkList(head, position, value);
    if (flag)
    {
        printf("插入节点成功！\n");
        TraverseSgLinkList(head);
    }    
    else
        printf("插入节点失败！\n");
    
    flag = IsEmptySgLinkList(head);
    if (flag)
        printf("单向链表为空，不能进行删除操作！\n");
    else
    {
        printf("请输入要删除节点的位置：");
        scanf("%d", &position);
        flag = DeleteEleSgLinkList(head, position);
        if (flag)
        {
            printf("删除节点成功！\n");
            TraverseSgLinkList(head);
        }    
        else
            printf("删除节点失败！\n");
    }
        
    FreeMemory(&head);
    if (NULL == head)
        printf("已成功删除单向链表，释放内存完成！\n");
    else
        printf("删除单向链表失败，释放内存未完成！\n");
     
    return 0;

}