linea-list-queue.c

用C语言实现了一个带头节点的线性链表和链队列

		C语言_带头节点的线性链表和链队列实现
/***********************************
带头节点的线性链表
定义见数据结构2.19
vincent
2007-01-23
这个带头节点的单链表，稍加修改就可以成为链队列
链队列与这个单链表的细微的区别在于，队列的插入
元素始终在表头，队列删除元素始终在表尾，因此
增加2个函数，InsertHead,DelTail
************************************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define TRUE            1
#define FALSE           0
#define OK              1
#define ERROR           0
#define INFEASIBLE      -1
#define OVERFLOW        -2

typedef int ElemType;
typedef int Status;

typedef struct LNode{//节点类型
    ElemType    data;
    struct LNode  *next;
}LNode,*Link;

typedef struct List{
    Link   head;
    Link   tail;
    int       len;
}List,*LinkList;

//typedef Link Position;
typedef int (*cmp)(ElemType i,  ElemType x);
typedef void (*vis)(Link N);


/*创建节点*/
Link MakeNode (ElemType e);
/*删除节点*/
Status FreeNode (Link p);
/*创建链表*/
/*Status InitList (LinkList L);*/
LinkList InitList ();
/*生成指定数量节点的链表*/
LinkList CreateList (int i);
/*销毁链表*/
Status DestroyList (LinkList L);
/*清空链表*/
Status ClearList (LinkList L);
/*删除指定位置节点*/
Status DelNode (LinkList L, int i);
/*在链表末尾增加节点*/
Status Append (LinkList L, Link p);
/*设置指定位置节点*/
Status SetNode (LinkList L, int i, ElemType e);
/*得到指定位置的节点*/
Link GetNode (LinkList L, int i);
/*得到头节点*/
Link GetHead (LinkList L);
/*得到尾节点*/
Link GetTail (LinkList L);
/*链表是否为空*/
Status ListEmpty (LinkList L);
/*链表长度*/
int    ListLength (LinkList L);
/*比较元素并返回第一个与被比较内容一致的节点*/
Link LocateElem (LinkList L, Link n, cmp f);
/*遍历链表*/
Status ListTraverse (LinkList L, vis v);
/*将2个链表合并*/
LinkList MergeList (LinkList La, LinkList Lb, cmp f);
/*比较2个节点*/
int Compare (ElemType i,ElemType x);
/*遍历节点*/
void Vist(Link N);
/*插入元素成为头节点指向的元素，即链表第一个元素*/
Status InsertHead (LinkList L, ElemType e);
/*删除表尾元素*/
Status DelTail (LinkList L);


void main(){
    Link p = NULL;
    LinkList L = NULL;
    //注意函数指针的使用方法
    vis v = Vist ;
    
    int i = 0,j = 0;
    p = MakeNode(1);
    if(!FreeNode(p)) exit(ERROR);    
    printf("success1\n");
    //if(!InitList(L)) exit(ERROR);
    L = InitList();
    if(!L) exit(ERROR);
    printf("success2\n");
    if(!DestroyList(L)) exit(ERROR);
    printf("success3\n");
    L = CreateList(5);
    DelNode(L,1);
    ListTraverse(L,v);
    if(!DestroyList(L)) exit(ERROR);
    printf("success4\n");    
}

/*创建节点*/
Link MakeNode (ElemType e){    
    Link p = (Link) malloc(sizeof(LNode));   
    p->data = e;   
    p->next = NULL;
    return p;
}

/*删除节点*/
Status FreeNode (Link p){
    if(!p) exit(ERROR);
    free(p);
    return TRUE;
}

/*创建链表*/
/*
Status InitList (LinkList L){
    Link p = NULL;
    p = MakeNode(0);
    if(!p) exit(ERROR);
    L = (LinkList) malloc(sizeof(List));
    L->head = p;
    L->tail = NULL;
    L->len = 0;
    return TRUE;
}
*/
/*C 中必须把结构内指针在函数的头部申明，放在函数中间会报错*/
LinkList InitList (){
    Link p = NULL;
    LinkList L = NULL;
    p = MakeNode(0);
    if(!p) exit(ERROR);
    L = (LinkList) malloc(sizeof(List));
    if(!L) exit(ERROR);
    L->head = p;
    L->tail = NULL;
    L->len = 0;
    return L;
}

/*生成指定数量节点的链表*/
LinkList CreateList (int i){
    Link p = NULL;
    LinkList L = NULL;
    int j,k;
    L = InitList();
    if(!L) exit(ERROR);
    for(j = 0 ; j < i ; j++){
        scanf("%d",&k);
        p = MakeNode(k);
        if(!p) exit(ERROR);
        if(!Append(L,p)) exit(ERROR);
    }
    return L;
}

/*销毁链表*/
Status DestroyList (LinkList L){
    Link p = NULL;
    Link t = NULL;
    p = L->head;
    while(p->next){
        t = p->next;
        free(p);
        p = t;
    }
    free(L);
    L = NULL;    
    return TRUE;
}

/*清空链表*/
Status ClearList (LinkList L){
    Link p = NULL;
    Link t = NULL;
    if(!L) exit(ERROR);
    p = L->head->next;
    while(p){
        t = p->next;
        free(p);
        p = t;
    }
    L->tail = NULL;
    L->len = 0;
    return TRUE;
}

/*删除指定位置节点*/
Status DelNode (LinkList L,int i){
    Link p = NULL;
    Link t = NULL;
    int j = 0;
    if(!L || i > L->len || i <= 0) exit(ERROR);
    p = L->head;
    for(j = 0; j < i - 1 ; j++){
        p = p->next;
    }
    t = p->next;
    p->next = p->next->next;
    t->next = NULL;
    free(t);
    --L->len;     
    return TRUE;
}

/*在链表末尾增加节点*/
Status Append (LinkList L, Link p){
    Link t = NULL;
    Link h = NULL;
    if(!L || !p) exit(ERROR);
    t = L->tail;
    if(!t) t = L->head;
    t->next = p;
    while(t->next){
        t = t->next;
        ++L->len;
    }
    L->tail = t;
    return TRUE;    
}

/*设置指定位置节点*/
Status SetNode (LinkList L, int i, ElemType e){
    Link p = NULL;
    int j = 0;
    if(!L || i > L->len || i <= 0) exit(ERROR);
    p = L->head;
    for(j = 0; j < i; j++){
        p = p->next;
    }
    p->data = e;
    return TRUE;
}
/*得到指定位置节点*/
Link GetNode(LinkList L, int i){
    Link p = NULL;
    int j = 0;
    if(!L || i > L->len || i <= 0) exit(ERROR);
    for(j = 0; j < i; j++){
        p = p->next;
    }    
    return p;    
}

/*得到头节点*/
Link GetHead (LinkList L){
    if(!L) exit(ERROR);
    return L->head;    
}

/*得到尾节点*/
Link GetTail (LinkList L){
    if(!L) exit(ERROR);
    return L->tail;
}

/*链表是否为空*/
Status ListEmpty (LinkList L){
    if(!L) exit(ERROR);
    if(L->len) return(FALSE);
    return TRUE;
}
/*链表长度*/
int    ListLength (LinkList L){
    if(!L) exit(ERROR);
    return L->len;
}
/*比较元素并返回第一个与被比较内容一致的节点*/
Link LocateElem (LinkList L, Link n, cmp f){
    Link p = NULL;
    int i = 0;
    p = L->head;
    while(p->next){
        p = p->next;
        if(f(n->data, p->data) == 0) return p;
    }
    return p;
}

/*遍历链表*/
Status ListTraverse (LinkList L, vis v){
    Link p = NULL;
    if(!L) exit(ERROR);
    p = L->head;
    while(p){
        v(p);
        p = p->next;
    }
    return TRUE;
}

/*将2个链表合并*/
LinkList MergeList (LinkList La, LinkList Lb, cmp f){
    
    Link pa = NULL;
    Link pb = NULL;
    Link pc = NULL;
    Link t = NULL;
    Link p = NULL;
    Link m = NULL;
    LinkList Lc = NULL;
    Lc = InitList();
    if(!La || !Lb || !Lc) exit(ERROR);
    pa = La->head->next;
    pb = Lb->head->next;
    if(!Append(Lc,pa)) exit(ERROR);
    if(!Append(Lc,pb)) exit(ERROR);    
    pc = Lc->head;
    t = pc->next;
    while(t->next){        
        p = t->next;
        while(p){
            if(f(t->data,p->data) > 0){
                pc->next = p;
                m = p->next;
                p->next = t;
                t = m;                
            }
            p = p->next;
        }
        t = t->next;
    }
    return Lc;
}

/*比较2个节点*/
int Compare (ElemType i,ElemType x){
    if(i == x) return 0;
    if(i < x) return -1;
    if(i > x) return 1;
}

/*遍历节点*/
void Vist(Link N){
    if(!N) exit(ERROR);
    printf("%d\n",N->data);
}

/*插入元素成为头节点指向的元素，即链表第一个元素*/
Status InsertHead (LinkList L, ElemType e){
    Link p = NULL;
    if(!L) exit(ERROR);
    p = MakeNode(e);
    if(!p) exit(ERROR);
    p->next = L->head->next;
    L->head->next = p;
    ++L->len;
    return TRUE;
}

/*删除表尾元素*/
Status DelTail (LinkList L){
    Link p = NULL;
    Link t = NULL;
    if(!L || !L->tail) exit(ERROR);
    p = L->head;
    while(p->next->next){
        p = p->next;
    }
    t = p->next;
    p->next = NULL;
    free(t);
    L->tail = p;
    --L->len;
    return TRUE;
}