对链表的相关操作及数据结构的再理解 (一)

#include   
#include   
#include   
typedef struct Node  
{  
    int data;//数据域   
    struct Node *pNext;//指针域   
}NODE,*PNODE;  
PNODE CreateList();//创建链表   
void TraverseList(PNODE);//遍历链表   
bool IsEmpty(PNODE);//判断链表是否为空   
int Length(PNODE);//求链表长度   
bool InsertNode(PNODE,int,int);//插入结点   
bool DeleteNode(PNODE,int,int *);//删除结点   
bool QueryNode(PNODE,int);//查找结点    
bool ModifyNode(PNODE,int,int);//修改结点   
void SortList(PNODE);//排序   
  
int main()  
{  
    PNODE pHead=NULL;  
    pHead=CreateList();//将创建链表的头指针的地址赋给pHead   
    if(0==Length(pHead))  
    {  
        printf("链表无有效节点，退出程序！\n");  
        exit(-1);  
    }  
    TraverseList(pHead);  
    if(InsertNode(pHead,2,100))  
    {  
        printf("插入后");  
        TraverseList(pHead);   
    }  
    else  
    {  
        printf("插入操作失败！\n");  
    }  
    SortList(pHead);  
    printf("排序后");  
    TraverseList(pHead);  
  
    return 0;  
}  
PNODE CreateList()  
{  
    int len;//用来保存需要创建链表的结点个数   
    int i;  
    int val;//用来临时存放新节点的值   
    PNODE pHead=(PNODE)malloc(sizeof(NODE));//动态分配一块内存，该内存保存头结点的地址，并将其赋给pHead   
    PNODE pTail=pHead;  
    PNODE pNew;  
    pTail->





pNext=NULL;//将尾结点的指针域赋为NULL   
    if(NULL==pHead)  
    {  
        printf("分配失败，程序终止运行！\n");  
        exit(-1);  
    }  
    printf("请输入你要创建链表的结点个数：len=");  
    scanf("%d",&len);  
    for(i=0;idata=val;  
        pTail->pNext=pNew;//将新结点挂到原尾结点的后面   
        pNew->pNext=NULL;//将新结点的指针域赋为NULL   
        pTail=pNew;//将新结点置为尾结点   
    }  
    return pHead;  
}  
void TraverseList(PNODE pHead)  
{  
    PNODE p=pHead->pNext;//将头结点的指针域指向首结点(链表的第一个有效结点)，并赋给指针变量p，此时p指向首节点的地址   
    printf("遍历整个链表：");  
    while(NULL!=p)//当p指向首节点的地址不为NULL(即链表不为空)，循环输入个结点的值   
    {  
        //当p指向尾结点的地址时，可输出尾结点的值   
        //但此时尾结点指针域为NULL，将跳出while循环   
        printf("%d  ",p->data);  
        p=p->pNext;//将p指向下一个结点的地址赋给p指针   
    }  
    printf("\n");   
}  
bool IsEmpty(PNODE pHead)  
{  
    if(NULL==pHead->pNext)  
        return true;  
    else  
        return false;  
}  
int Length(PNODE pHead)  
{  
    PNODE p=pHead->pNext;//此时p指向链表的首结点(第一个有效结点)的地址   
    int len=0;  
    while(NULL!=p)  
    {  
        ++len;  
        p=p->pNext;  
    }  
    return len;  
}  
bool InsertNode(PNODE pHead,int pos,int val)  
{  
    int i=0;  
    PNODE p=pHead,q;  
    PNODE pNew;  
    while(NULL!=p&&ipNext;  
        ++i;//如链表只有两个有效结点，要插入的位置结点pos=3，i=2时,2<3-1不成立，循环结束，   
    }  
    if(i>pos-1||NULL==p)//p为NULL说明要插入位置结点的前一个结点不存在，i>pos-1是为了防止用户输入pos为像0、-1等非法数据   
        return false;  
    pNew=(PNODE)malloc(sizeof(NODE));//为新节点分配内存   
    if(NULL==pNew)  
    {  
        printf("动态内存分配失败，程序终止！\n");  
        exit(-1);  
    }  
    pNew->data=val;  
    q=p->pNext;  
    p->pNext=pNew;  
    pNew->pNext=q;  
    return true;   
}  
bool DeleteNode(PNODE pHead,int pos,int *pVal)  
{  
    int i=0;  
    PNODE p=pHead,q;  
    while(NULL!=p->pNext&&ipN