資料結構C語言實作系列[1]——線性表

#include  < stdio.h >

#include  < stdlib.h >

typedef  int  elemType;

struct  List ... {

    elemType *list;

    int size;

    int maxSize;

} ;

void  againMalloc( struct  List  * L)

... {    

    elemType *p = realloc(L->list, 2 * L->maxSize * sizeof(elemType));

    if(!p)...{    

        printf("存儲空間配置設定失敗！ ");

        exit(1);

    }

    L->list = p;    

    L->maxSize = 2 * L->maxSize;    

}

void  initList( struct  List  * L,  int  ms)

... {

    if(ms <= 0)...{

        printf("MaxSize非法！ ");

        exit(1);    

    }

    L->maxSize = ms;    

    L->size = 0;

    L->list = malloc(ms * sizeof(elemType));

    if(!L->list)...{

        printf("空間配置設定失敗！ ");

        exit(1);

    }

    return;

}

void  clearList( struct  List  * L)

... {

    if(L->list != NULL)...{

        free(L->list);

        L->list = 0;

        L->size = L->maxSize = 0;

    }

    return;

}

int  sizeList( struct  List  * L)

... {

    return L->size;

}

int  emptyList( struct  List  * L)

... {

    if(L->size ==0)...{

        return 1;

    }

    else...{

        return 0;

    }

}

elemType getElem( struct  List  * L,  int  pos)

... {

    if(pos < 1 || pos > L->size)...{    

        printf("元素序号越界！ ");

        exit(1);

    }

    return L->list[pos - 1];    

}

void  traverseList( struct  List  * L)

... {

    int i;

    for(i = 0; i < L->size; i++)...{

        printf("%d ", L ->list[i]);

    }

    printf(" "); 

    return;

}

int  findList( struct  List  * L, elemType x)

... {

    int i;

    for(i = 0; i < L->size; i++)...{

        if(L->list[i] == x)...{

            return i;

        }

    }

    return -1;

}

int  updatePosList( struct  List  * L,  int  pos, elemType x)

... {

    if(pos < 1 || pos > L->size)...{    

        return 0;

    }

    L->list[pos - 1] = x;

    return 1;

}

void  inserFirstList( struct  List  * L, elemType x)

... {

    int i;

    if(L->size == L->maxSize)...{

        againMalloc(L);

    }

    for(i = L->size - 1; i >= 0; i--)...{

        L->list[i + 1] = L ->list[i];

    }

    L->list[0] = x;

    L->size ++;

    return;

}

void  insertLastList( struct  List  * L, elemType x)

... {

    if(L->size == L ->maxSize)...{    

        againMalloc(L);

    }

    L->list[L->size] = x;    

    L->size++;    

    return;

}

int  insertPosList( struct  List  * L,  int  pos, elemType x)

... {

    int i;

    if(pos < 1 || pos > L->size + 1)...{    

        return 0;

    }

    if(L->size == L->maxSize)...{    

        againMalloc(L);

    }

    for(i = L->size - 1; i >= pos - 1; i--)...{

        L->list[i + 1] = L->list[i];

    }

    L->list[pos - 1] = x;

    L->size++;

    return 1;

}

void  insertOrderList( struct  List  * L, elemType x)

... {

    int i, j;

    if(L->size == L->maxSize)...{

        againMalloc(L);

    }

    for(i = 0; i < L->size; i++)...{

        if(x < L->list[i])...{ 

            break;

        }

    }

    for(j = L->size - 1; j >= i; j--)

        L->list[j+1] = L->list[j];

    L->list[i] = x;

    L->size++;

    return;

}

elemType deleteFirstList( struct  List  * L)

... {

    elemType temp;

    int i;

    if(L ->size == 0)...{

        printf("線性表為空，不能進行删除操作！ ");

        exit(1);

    }

    temp = L->list[0];

    for(i = 1; i < L->size; i++)

        L->list[i-1] = L->list[i];

    L->size--;

    return temp;

}

elemType deleteLastList( struct  List  * L)

... {

    if(L ->size == 0)...{

        printf("線性表為空，不能進行删除操作！ ");

        exit(1);

    }

    L->size--;

    return L ->list[L->size];        

}

elemType deletePosList( struct  List  * L,  int  pos)

... {

    elemType temp;

    int i;

    if(pos < 1 || pos > L->size)...{        

        printf("pos值越界，不能進行删除操作！ ");

        exit(1);

    }

    temp = L->list[pos-1];

    for(i = pos; i < L->size; i++)

        L->list[i-1] = L->list[i];

    L->size--;

    return temp;

}

int  deleteValueList( struct  List  * L, elemType x)

... {

    int i, j;

    for(i = 0; i < L->size; i++)...{

        if(L->list[i] == x)...{    

            break;

        }

    }

    if(i == L->size)...{

        return 0;

    }

    for(j = i + 1; j < L->size; j++)...{

        L->list[j-1] = L->list[j];

    }

    L->size--;

    return 1;

}

void  main()

... {

    int a[10] = ...{2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

    int i;

    struct List L;

    initList(&L, 5);

    for(i = 0; i < 10; i++)...{

        insertLastList(&L, a[i]);

    }

    insertPosList(&L, 11, 48);        insertPosList(&L, 1, 64);

    printf("%d ", getElem(&L, 1));

    traverseList(&L);

    printf("%d ", findList(&L, 10));

    updatePosList(&L, 3, 20);

    printf("%d ", getElem(&L, 3));

    traverseList(&L);

    deleteFirstList(&L);            deleteFirstList(&L);

    deleteLastList(&L);                deleteLastList(&L);

    deletePosList(&L, 5);            ;deletePosList(&L, 7);

    printf("%d ", sizeList(&L));

    printf("%d ", emptyList(&L));

    traverseList(&L);

    clearList(&L);

    return 0;

}  

#include  < stdio.h >

#include  < stdlib.h >

#define  NN 12

#define  MM 20

typedef  int  elemType ;

struct  sNode ... {    

    elemType data;

    struct sNode *next;

} ;

void  initList( struct  sNode *   * hl)

... {

    *hl = NULL;

    return;

}

void  clearList( struct  sNode *   * hl)

... {

    struct sNode *cp, *np;

    cp = *hl;

    while(cp != NULL)...{

        np = cp->next;    

        free(cp);

        cp = np;

    }

    *hl = NULL;        

    return;

}

int  sizeList( struct  sNode  * hl)

... {

    int count = 0;        

    while(hl != NULL)...{

        count++;

        hl = hl->next;

    }

    return count;

}

int  emptyList( struct  sNode  * hl)

... {

    if(hl == NULL)...{

        return 1;

    }else...{

        return 0;

    }

}

elemType getElem( struct  sNode  * hl,  int  pos)

... {

    int i = 0;        

    if(pos < 1)...{

        printf("pos值非法，退出運作！ ");

        exit(1);

    }

    while(hl != NULL)...{

        i++;

        if(i == pos)...{

            break;

        }

        hl = hl->next;

    }

    if(hl != NULL)...{

        return hl->data;

    }else...{

        printf("pos值非法，退出運作！ ");

        exit(1);

    }

}

void  traverseList( struct  sNode  * hl)

... {

    while(hl != NULL)...{

        printf("%5d", hl->data);

        hl = hl->next;

    }

    printf(" ");

    return;

}

elemType *  findList( struct  sNode  * hl, elemType x)

... {

    while(hl != NULL)...{

        if(hl->data == x)...{

            return &hl->data;

        }else...{

            hl = hl->next;    

        }

    }

    return NULL;

}

int  updatePosList( struct  sNode  * hl,  int  pos, elemType x)

... {

    int i = 0;

    struct sNode *p = hl;

    while(p != NULL)...{        

        i++;

        if(pos == i)...{

            break;

        }else...{

            p = p->next;

        }

    }

    if(pos == i)...{

        p->data = x;

        return 1;

    }else...{

        return 0;

    }

}

void  insertFirstList( struct  sNode *   * hl, elemType x)

... {

    struct sNode *newP;

    newP = malloc(sizeof(struct sNode));

    if(newP == NULL)...{

        printf("記憶體配置設定失敗，退出運作！ ");

        exit(1);

    }

    newP->data = x;        

    newP->next = *hl;        

    *hl = newP;

    return;

}

void  insertLastList( struct  sNode *   * hl, elemType x)

... {

    struct sNode *newP;

    newP = malloc(sizeof(struct sNode));

    if(newP == NULL)...{

        printf("内在配置設定失敗，退出運作！ ");

        exit(1);

    }

    newP->data = x;

    newP->next = NULL;

    if(*hl == NULL)...{

        *hl = newP;        

    }

    else...{

        struct sNode *p = NULL;

        while(p->next != NULL)...{

            p = p->next;

        }

        p->next = newP;

    }

    return;

}

int  insetPosList( struct  sNode *   * hl,  int  pos, elemType x) ... {

    int i = 0;

    struct sNode *newP;

    struct sNode *cp = *hl, *ap = NULL;

    if(pos <= 0)...{

        printf("pos值非法，傳回０表示插入失敗！ ");

        return 0;

    }

    while(cp != NULL)...{

        i++;

        if(pos == i)...{

            break;

        }else...{

            ap = cp;

            cp = cp->next;

        }

    }

    newP = malloc(sizeof(struct sNode));

    if(newP == NULL)...{

        printf("記憶體配置設定失敗，無法進行插入操作！ ");

        return 0;

    }

    newP->data = x;

    if(ap == NULL)...{

        newP->next = cp;        

        *hl = newP;

    }

    else...{

        newP->next = cp;

        ap->next = newP;

    }

    return 1;        

}

void  insertOrderList( struct  sNode *   * hl, elemType x)

... {

    struct sNode *cp = *hl, *ap = NULL;

    struct sNode *newP;

    newP = malloc(sizeof(struct sNode));

    if(newP == NULL)...{

        printf("内在配置設定失敗，退出運作！ ");

        exit(1);

    }

    newP->data = x;        

    if((cp == NULL) || (x < cp->data))...{

        newP->next = cp;

        *hl = newP;

        return;

    }

    while(cp != NULL)...{

        if(x < cp->data)...{

            break;

        }else...{

            ap = cp;

            cp = cp->next;

        }

    }

    newP->next = cp;

    ap->next = newP;

    return;

}

elemType deleteFirstList( struct  sNode *   * hl)

... {

    elemType temp;

    struct sNode *p = *hl;        

    if(*hl == NULL)...{

        printf("單連結清單為空，無表頭可進行删除，退出運作！ ");

        exit(1);

    }

    *hl = (*hl)->next;        

    temp = p->data;            

    free(p);                

    return temp;            

}

elemType deleteLastList( struct  sNode *   * hl)

... {

    elemType temp;

    struct sNode *cp = *hl;

    struct sNode *ap = NULL;

    if(cp == NULL)...{

        printf("單連結清單為空，無表頭進行删除，退出運作！ ");

        exit(1);

    }

    while(cp->next != NULL)...{

        ap = cp;

        cp = cp->next;

    }

    if(ap == NULL)...{

        *hl = (*hl)->next;        

    }

    else...{

        ap->next = NULL;

    }

    temp = cp->data;

    free(cp);        

    return temp;        

}

elemType deletePosList( struct  sNode *   * hl,  int  pos)

... {

    int i = 0;

    elemType temp;

    struct sNode *cp = *hl;

    struct sNode *ap = NULL;

    if((cp == NULL) || (pos <= 0))...{

        printf("單連結清單為空或pos值不正确，退出運作！ ");

        exit(1);

    }

    while(cp != NULL)...{

        i++;

        if(i == pos)...{

            break;

        }

        ap = cp;

        cp = cp->next;

    }

    if(cp == NULL)...{

        printf("pos值不正确，退出運作！ ");

        exit(1);

    }

    if(pos == 1)...{

        *hl = (*hl)->next;        

    }

    else...{

        ap->next = cp->next;

    }

    temp = cp->data;

    free(cp);        

    return temp;    

}

int  deleteValueList( struct  sNode *   * hl, elemType x)

... {

    struct sNode *cp = *hl;

    struct sNode *ap = NULL;

    while(cp != NULL)...{

        if(cp->data == x)...{

            break;

        }

        ap = cp;

        cp = cp->next;

    }

    if(cp == NULL)...{

        return 0;

    }

    if(ap == NULL)...{

        *hl = (*hl)->next;        

    }else...{

        ap->next = cp->next;

    }

    free(cp);        

    return 1;        

}

int  main( int  argc,  char *  argv[])

... {

    int a[NN];

    int i;

    struct sNode *p, *h, *s;

    srand(time(NULL));

    initList(&p);

    for(i = 0; i < NN; i++)...{

        a[i] = rand() & MM;

    }

    printf("随機數序列：");

    for(i = 0; i < NN; i++)...{

        printf("%5d", a[i]);

    }

    printf(" ");

    printf("随機數逆序：");

    for(i = 0; i < NN; i++)...{

        insertFirstList(&p, a[i]);

    }

    traverseList(p);

    printf("單連結清單長度：%5d ", sizeList(p));

    for(h = p; h != NULL; h = h->next)...{

        while(deleteValueList(&(h->next), h->data))...{

            ;

        }

    }

    printf("去除重複數：");

    traverseList(p);

    printf("單連結清單長度：%5d ", sizeList(p));

    h = NULL;

    for(s = p; s != NULL; s = s->next)...{

        insertOrderList(&h, s->data);

    }

    printf("有序表序列：");

    traverseList(h);

    clearList(&p);

    system("pause");

    return 0;

}