【数据结构】02 单链表

#include 
#include 

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Elemtype;
typedef int Status;


typedef struct LNode{
    Elemtype data;//数据域
    struct LNode *next;//指针域
}LNode, *LinkList; /
Status InitList(LinkList *L){
    *L = (LinkList) malloc(sizeof(LNode));
    if(!L){
        exit(OVERFLOW);
    }
    (*L)->next = NULL;// (*L)
}


 void DestroyList(LinkList *L){
     LinkList temp;
     while(*L){
         temp = (*L)->next;
         free(*L);
         *L = temp;
     }
 }



void ClearList(LinkList L){
    LinkList p = L->next;
    L->next = NULL;
    DestroyList(&p);
}


Status isEmpty(LinkList L){
    if(L->next){
        return FALSE;
    }
    else{
        return TRUE;
    }
}


int GetLength(LinkList L){
    int i = 0;
    LinkList p = L->next;
    while(p){
        i++;
        p = p->next;
    }
    return i;
}

                
Status InsertElem(LinkList L, int i,Elemtype e){ 
    int j = 0;
    LinkList s, p = L;
    while(p && j < i - 1){
        j++;
        p = p->next;
    }
    if(!p || j > i-1){// j>i-1说明位置不对
        return ERROR;
    }
    s = (LinkList) malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}      



Status DeleteElem(LinkList L, int i, Elemtype *e){
    int j = 0;
    LinkList q, p = L;
    while(p && j < i-1){
        j++;
        p = p->next;
    }
    if(!p || j > i-1){
        return ERROR;
    }
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK;
 }
 
 
Status GetElem(LinkList L, int i,Elemtype *e){
    int j =1;
    LinkList p=L->next;
    while(p && j < i){//直到j==i
        j++;
        p = p->next;
    }
    if(!p || j > i){
        return ERROR;
    }
    *e = p->data;
    return OK;
}


Status  compare(Elemtype e1,Elemtype e2){
    if(e1 == e2){return 0;}
    else if(e1 > e2) {return 1;}
    else {return -1;}
}



int FindElem(LinkList L,Elemtype e, Status (*cpmpare)(Elemtype,Elemtype)){
    int i = 0;
    LinkList p = L->next;
    while(p){
        i++;
        if(!compare(p->data,e)){//相等时返回0,a>b返回1，小于返回-1
            return i;
        }
        p = p->next;
    }
    return 0;
}


Status PreElem(LinkList L,Elemtype cur_e,Elemtype *pre_e){
    LinkList q, p = L->next;
    while(p->next){
        q = p->next;
        if(q->data == cur_e){
            *pre_e = p->data;
            return OK;
        }
        p = q;
    }
    return ERROR;
}


Status NextElem(LinkList L, Elemtype cur_e,Elemtype *next_e){
    LinkList p = L->next;
    while(p->next){
        if(p->data == cur_e){
            *next_e = p->next->data;
            return OK;
        }
        p = p->next;
    }
    return ERROR;
}




void visit(Elemtype e){
    printf("%d",e);
}

 
 Status TraverseList(LinkList L, void (*visit)(Elemtype)){
     LinkList p = L->next;
     while(p){
         visit(p->data);
         p = p->next;
     }
 }

int main(){
    LinkList L;
    InitList(&L);
    Elemtype e;
    int i;
    if (L){
        printf("init successn");
    }

    if (isEmpty(L)){ // 判断链表是否为空
        printf("list is emptyn");
    }

    for (i = 0; i < 10; i++){ // 插入元素
        InsertElem(L, i + 1, i);
    }

    if (GetElem(L, 1, &e)) { // 获取元素的值
        printf("The first element is %dn", e);
    }

    printf("length is %dn", GetLength(L)); // 获取表长

    printf("The 5 at %dn", FindElem(L, 5, *compare)); // 查找元素

    PreElem(L, 6, &e); // 获取元素 6 的前驱元素
    printf("The 6's previous element is %dn", e);

    NextElem(L, 6, &e); // 获取元素 6 的后继元素
    printf("The 6's next element is %dn", e);

    DeleteElem(L, 1, &e); // 删除元素
    printf("delete first element is %dn", e);

    printf("list:");
    TraverseList(L,visit); // 遍历链表

    DestroyList(&L); // 销毁线性表
    if (!L) {
        printf("ndestroy successn");
    }
}

shiyanlou:project/ $ gcc -o 3.1 3.1.c                                                      [18:29:19]
shiyanlou:project/ $ ./3.1                                                                 [18:29:22]
init success
list is empty
The first element is 0
length is 10
The 5 at 6
The 6's previous element is 5
The 6's next element is 7
delete first element is 0
list:123456789
destroy success