单链表相关操作

#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
typedef ElemType int;

typedef struct LNode{
  ElemType data; //数据域

  struct LNode *next; //指针域

}LNode;
typedef LNode *LinkList; //单链表类型名


void WarnMessage(char *s)
{
    printf(s);
}

LNode* CreateNode(ElemType e)//创建结点

{
    LNode *temp = (LNode*)malloc(sizeof(LNode));
    temp->data = e;
    temp->next = NULL;
    return temp;
}

void DestoryList_Link(LinkList *LHead)//销毁单链表；

/*从头结点开始，释放每个结点的空间*/
{
    if(NULL == *LHead)
    {
        WarnMessage("\nThere are no Nodes to be freed!\n");
        return;
    }
    else{
        LinkList p;
        /*从头结点开始，一一释放结点的空间*/
        while(*LHead){
            p = (*LHead)->next;
            free(*LHead);
            *LHead = p;
        }
    }
}

int ListLength_Link(LinkList *LHead)//求链表长度；

/*通过遍历各结点，将长度length加一*/
{
    int length = 0;//定义表长变量length并初始化为0；

    if(NULL == *LHead)
    {
        return 0;
    }
    LNode *p = *LHead;
    while(p){
        length++;
        p=p->next;
    }
    return length;
}

void ListInsert_Link(LinkList *LHead,int i,LNode *node)//在单链表中插入元素；

/*在单链表L中第i个位置之前插入值e的结点，1<=i<=表长+1；*/
{
    if(NULL == *LHead){
        *LHead = node;/*如果头结点指针域为空，则当前结点作为第一个结点*/
        return ;
    }
    /*头结点指针域不为空,指针指向第一个结点
    **移动指针，找到相应的插入位置；
    */
    LNode *p = *LHead;
    int k=0;
    while(p && k<(i-1)){
        k ++;
        p = p->next;
    }
    if(!p ||(k > i-1)){
        WarnMessage("Input Error,Insert Failed!\n");
    }
    else{

        node->next = p->next;
        p->next = node;
    }
}

ElemType GetElem_Link(LinkList *LHead,int i)//某位置i取元素值；

{
    ElemType re_data = 0;
    if(NULL == *LHead){
        return ERROR;
    }
    if(i>ListLength_Link(LHead)){
        printf("input error!\n");
        return ERROR;
    }
    LinkList Temp = *LHead;
    int k = 0;
    while(Temp && k<(i-1)){
        Temp = Temp->next;
        k++;
    }
    re_data = Temp->data;
    return re_data;
}

State ListDelete_Link(LinkList *LHead,int i)//删除特定的元素。

/*在带头结点的单链表中，删除第i个元素*/
{
    LinkList p,temp;
    if(NULL == *LHead){
        WarnMessage("NO Node to be deleted!");
        return ERROR;
    }
    if(i>ListLength_Link(LHead)){
        return ERROR;
    }
    p = *LHead;
    int k = 0;
    while(p->next && (k<i-1)){
        p = p->next;
        ++k;
    }
    temp = p->next;
    p->next = temp->next;
    free(temp);
    return OK;
}

int LocateElem_Link(LinkList *LHead,ElemType e)//定位元素的位置。

/*根据结点数据值，找到到其所在位置*/
{
    LinkList p = *LHead;
    int k=0;
    while(p&&(p->data != e))
    {
        p=p->next;
        ++k;
    }
    return k;
}

void LNode_Traver(LinkList *LHead)
/*从头结点开始遍历整个链表*/
{
    LinkList p = *LHead;
    while(NULL != p)
    {
        printf("%d-->",p->data);
        p = p->next;
    }
    WarnMessage("\n\n");
}

/*
**根据结点数据域的大小进行由大到小的排序
*/
/*这个排序方法不怎么实用
void Sort_LinkList(LinkList *LHead){
    LinkList p,q,big;
    Elemtype temp;
    for(p = (*LHead)->next;p->next;p = p->next){
        big = p;
        for(q = p->next;q->next;q = q->next){
            if(q->data > big->data){
                big = q;
            }
        }
        if(p != big){
            temp = p->data;
            p->data = big->data;
            big->data = temp;
        }
    }
}
*/
//另一种单链表排序方法

void selectsort(LinkList *g)
{
    LNode *p,*q,*t,*s,*h;
    h=(LNode *)malloc(sizeof(LNode));
    h->next=*g;        /*h-->g的第一个结点*/
    p=h;             //p,h->同一地址

    while(p->next->next!=NULL)
    {
          for(s=p,q=p->next;q->next!=NULL;q=q->next)
           if(q->next->data<s->next->data)
           s=q;
          if(s!=q)
          {
              t=s->next;
               s->next=t->next;
              t->next=p->next;
              p->next=t;
          }
     p=p->next;
    }
    *g=h->next;
        free(h);
}

/*将两个单链表A,B归并成新的单链表C
**设置两个指针分别指向A，B的第一个结点，第三个指针指向空表
**当其中一个表为空时，表示其已并完，只需将另一表中元素归并到C中；
*/
void MergeList_L(LinkList *HeadA,LinkList *HeadB,LinkList *HeadC){
    LinkList pa,pb,pc;
    /*pa,pb分别指向第一个结点，pc作为新链表的头指针*/
    pa = (*HeadA)->next;
    pb = (*HeadB)->next;
    *HeadC = pc = *HeadA; //将HeadA的头结点作为HeadC头结点

    while(pa && pb){
        if(pa->data <= pb->data){
            pc->next = pa;
            pc = pa;//移动结点指针至新插入的当前结点

            pa = pa->next;
        }
        else{
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
        pc->next = pa ? pa : pb;
        free(*HeadB);
}
以上代码还是有点小问题，比如最后一个归并函数，我运行的时候，居然把链表B的首结点删除了，还是需要改进，还有就是单链表排序问题，第一个排序没有起到作用；