数据结构C语言实现系列――线性表[组图]

#include <stdio.h>
　　#include <stdlib.h>
　　typedef int elemType;
　　/************************************************************************/
　　/*                以下是关于线性表顺序存储操作的16种算法                        */
　　/************************************************************************/
　　strUCt List{
　　    elemType *list;
　　    int size;
　　    int maxSize;
　　};
　　
　　void againMalloc(struct List *L)
　　{    
　　    /* 空间扩展为原来的2倍，并由p指针所指向，原内容被自动拷贝到p所指向的存储空间 */
　　    elemType *p = realloc(L->list, 2 * L->maxSize * sizeof(elemType));
　　    if(!p){    /* 分配失败则退出运行 */
　　        printf("存储空间分配失败！ ");
　　        exit(1);
　　    }
　　    L->list = p;    /* 使list指向新线性表空间 */
　　    L->maxSize = 2 * L->maxSize;    /* 把线性表空间大小修改为新的长度 */
　　}
　　
　　/* 1.初始化线性表L，即进行动态存储空间分配并置L为一个空表 */
　　void initList(struct List *L, int ms)
　　{
　　    /* 检查ms是否有效，若无效的则退出运行 */
　　    if(ms <= 0){
　　        printf("MaxSize非法！ ");
　　        exit(1);    /* 执行此函数中止程序运行，此函数在stdlib.h中有定义 */
　　    }
　　    L->maxSize = ms;    /* 设置线性表空间大小为ms */
　　    L->size = 0;
　　    L->list = malloc(ms * sizeof(elemType));
　　    if(!L->list){
　　        printf("空间分配失败！ ");
　　        exit(1);
　　    }
　　    return;
　　}
　　
　　/* 2.清除线性表L中的所有元素，释放存储空间，使之成为一个空表 */
　　void clearList(struct List *L)
　　{
　　    if(L->list != NULL){
　　        free(L->list);
　　        L->list = 0;
　　        L->size = L->maxSize = 0;
　　    }
　　    return;
　　}
　　
　　/* 3.返回线性表L当前的长度，若L为空则返回０ */
　　int sizeList(struct List *L)
　　{
　　    return L->size;
　　}
　　
　　/* 4.判定线性表L是否为空，若为空则返回1, 否则返回0 */
　　int emptyList(struct List *L)
　　{
　　    if(L->size ==0){
　　        return 1;
　　    }
　　    else{
　　        return 0;
　　    }
　　}
　　
　　/* 5.返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行 */
　　elemType getElem(struct List *L, int pos)
　　{
　　    if(pos < 1  pos > L->size){    /* 若pos越界则退出运行 */
　　        printf("元素序号越界！ ");
　　        exit(1);
　　    }
　　    return L->list[pos - 1];    /* 返回线性表中序号为pos值的元素值 */
　　}
　　
　　/* 6.顺序扫描（即遍历）输出线性表L中的每个元素 */
　　void traverseList(struct List *L)
　　{
　　    int i;
　　    for(i = 0; i < L->size; i++){
　　        printf("%d ", L ->list[i]);
　　    }
　　    printf(" "); 
　　    return;
　　}
　　
　　/* 7.从线性表L中查找值与x相等的元素，若查找成功则返回其位置，否则返回-1 */
　　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;
　　}
　　
　　/* 8.把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0 */
　　int updatePosList(struct List *L, int pos, elemType x)
　　{
　　    if(pos < 1  pos > L->size){    /* 若pos越界则修改失败 */
　　        return 0;
　　    }
　　    L->list[pos - 1] = x;
　　    return 1;
　　}
　　
　　/* 9.向线性表L的表头插入元素x */
　　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;
　　}
　　
　　/* 10.向线性表L的表尾插入元素x */
　　void insertLastList(struct List *L, elemType x)
　　{
　　    if(L->size == L ->maxSize){    /* 重新分配更大的存储空间 */
　　        againMalloc(L);
　　    }
　　    L->list[L->size] = x;    /* 把x插入到表尾 */
　　    L->size++;    /* 线性表的长度增加１ */
　　    return;
　　}
　　
　　/* 11.向线性表L中第pos个元素位置插入元素x，若插入成功返回１，否则返回０ */
　　int insertPosList(struct List *L, int pos, elemType x)
　　{
　　    int i;
　　    if(pos < 1  pos > L->size + 1){    /* 若pos越界则插入失败 */
　　        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;
　　}
　　/* 12.向有序线性表L中插入元素x,　使得插入后仍然有序*/
　　void insertOrderList(struct List *L, elemType x)
　　{
　　    int i, j;
　　    /* 若数组空间用完则重新分配更大的存储空间 */
　　    if(L->size == L->maxSize){
　　        againMalloc(L);
　　    }
　　    /* 顺序查找出x的插入位置 */
　　    for(i = 0; i < L->size; i++){
　　        if(x < L->list[i]){ 
　　            break;
　　        }
　　    }
　　    /* 从表尾到下标i元素依次后移一个位置， 把i的位置空出来 */
　　    for(j = L->size - 1; j >= i; j--)
　　        L->list[j+1] = L->list[j];
　　    /* 把x值赋给下标为i的元素 */    
　　    L->list[i] = x;
　　    /* 线性表长度增加1 */
　　    L->size++;
　　    return;
　　}
　　
　　/* 13.从线性表L中删除表头元素并返回它，若删除失败则停止程序运行 */
　　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;
　　}
　　
　　/* 14.从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行 */
　　elemType deleteLastList(struct List *L)
　　{
　　    if(L ->size == 0){
　　        printf("线性表为空，不能进行删除操作！ ");
　　        exit(1);
　　    }
　　    L->size--;
　　    return L ->list[L->size];        /* 返回原来表尾元素的值 */
　　}
　　/* 15.从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行 */
　　elemType deletePosList(struct List *L, int pos)
　　{
　　    elemType temp;
　　    int i;
　　    if(pos < 1  pos > L->size){        /* pos越界则删除失败 */
　　        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;
　　}
　　/* 16.从线性表L中删除值为x的第一个元素，若成功返回1，失败返回0 */
　　int deleteValueList(struct List *L, elemType x)
　　{
　　    int i, j;
　　    /* 从线性表中顺序查找出值为x的第一个元素 */
　　    for(i = 0; i < L->size; i++){
　　        if(L->list[i] == x){    
　　            break;
　　        }
　　    }
　　    /* 若查找失败，表明不存在值为x的元素，返回0 */
　　    if(i == L->size){
　　        return 0;
　　    }
　　    /* 删除值为x的元素L->list[i] */
　　    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 ;
　　/************************************************************************/
　　/*             以下是关于线性表链接存储（单链表）操作的16种算法        */
　　/************************************************************************/
　　struct sNode{    /* 定义单链表结点类型 */
　　    elemType data;
　　    struct sNode *next;
　　};
　　
　　/* 1.初始化线性表，即置单链表的表头指针为空 */
　　void initList(struct sNode* *hl)
　　{
　　    *hl = NULL;
　　    return;
　　}
　　
　　/* 2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
　　void clearList(struct sNode* *hl)
　　{
　　    /* cp和np分别作为指向两个相邻结点的指针 */
　　    struct sNode *cp, *np;
　　    cp = *hl;
　　    /* 遍历单链表，依次释放每个结点 */
　　    while(cp != NULL){
　　        np = cp->next;    /* 保存下一个结点的指针 */
　　        free(cp);
　　        cp = np;
　　    }
　　    *hl = NULL;        /* 置单链表的表头指针为空 */
　　    return;
　　}
　　
　　/* 3.返回单链表的长度 */
　　int sizeList(struct sNode *hl)
　　{
　　    int count = 0;        /* 用于统计结点的个数 */
　　    while(hl != NULL){
　　        count++;
　　        hl = hl->next;
　　    }
　　    return count;
　　}
　　
　　/* 4.检查单链表是否为空，若为空则返回１，否则返回０ */
　　int emptyList(struct sNode *hl)
　　{
　　    if(hl == NULL){
　　        return 1;
　　    }else{
　　        return 0;
　　    }
　　}
　　
　　/* 5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
　　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);
　　    }
　　}
　　
　　/* 6.遍历一个单链表 */
　　void traverseList(struct sNode *hl)
　　{
　　    while(hl != NULL){
　　        printf("%5d", hl->data);
　　        hl = hl->next;
　　    }
　　    printf(" ");
　　    return;
　　}
　　
　　/* 7.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
　　elemType* findList(struct sNode *hl, elemType x)
　　{
　　    while(hl != NULL){
　　        if(hl->data == x){
　　            return &hl->data;
　　        }else{
　　            hl = hl->next;    
　　        }
　　    }
　　    return NULL;
　　}
　　
　　/* 8.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
　　int updatePosList(struct sNode *hl, int pos, elemType x)
　　{
　　    int i = 0;
　　    struct sNode *p = hl;
　　    while(p != NULL){        /* 查找第pos个结点 */
　　        i++;
　　        if(pos == i){
　　            break;
　　        }else{
　　            p = p->next;
　　        }
　　    }
　　    if(pos == i){
　　        p->data = x;
　　        return 1;
　　    }else{
　　        return 0;
　　    }
　　}
　　
　　/* 9.向单链表的表头插入一个元素 */
　　void insertFirstList(struct sNode* *hl, elemType x)
　　{
　　    struct sNode *newP;
　　    newP = malloc(sizeof(struct sNode));
　　    if(newP == NULL){
　　        printf("内存分配失败，退出运行！
　　 ");
　　        exit(1);
　　    }
　　    newP->data = x;        /* 把x的值赋给新结点的data域 */
　　    /* 把新结点作为新的表头结点插入 */
　　    newP->next = *hl;        
　　    *hl = newP;
　　    return;
　　}
　　
　　/* 10.向单链表的末尾添加一个元素 */
　　void insertLastList(struct sNode* *hl, elemType x)
　　{
　　    struct sNode *newP;
　　    newP = malloc(sizeof(struct sNode));
　　    if(newP == NULL){
　　        printf("内在分配失败，退出运行！ ");
　　        exit(1);
　　    }
　　    /* 把x的值赋给新结点的data域，把空值赋给新结点的next域 */
　　    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;
　　}
　　
　　/* 11.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
　　int insetPosList(struct sNode* *hl, int pos, elemType x){
　　    int i = 0;
　　    struct sNode *newP;
　　    struct sNode *cp = *hl, *ap = NULL;
　　    /* 对pos值小于等于０的情况进行处理 */
　　    if(pos <= 0){
　　        printf("pos值非法，返回０表示插入失败！ ");
　　        return 0;
　　    }
　　    /* 查找第pos个结点 */
　　    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;
　　    }
　　    /* 把x的值赋给新结点的data域 */
　　    newP->data = x;
　　    /* 把新结点插入到表头 */
　　    if(ap == NULL){
　　        newP->next = cp;        /* 或改为newP->next = *hl; */
　　        *hl = newP;
　　    }
　　    /* 把新结点插入到ap和cp之间 */
　　    else{
　　        newP->next = cp;
　　        ap->next = newP;
　　    }
　　    return 1;        /* 插入成功返回1 */
　　}
　　
　　/* 12.向有序单链表中插入元素x结点，使得插入后仍然有序 */
　　void insertOrderList(struct sNode* *hl, elemType x)
　　{
　　    /* 把单链表的表头指针赋给cp，把ap置空 */
　　    struct sNode *cp = *hl, *ap = NULL;
　　    /* 建立新结点 */
　　    struct sNode *newP;
　　    newP = malloc(sizeof(struct sNode));
　　    if(newP == NULL){
　　        printf("内在分配失败，退出运行！ ");
　　        exit(1);
　　    }
　　    newP->data = x;        /* 把x的值赋给新结点的data域 */
　　    /* 把新结点插入到表头 */
　　    if((cp == NULL)  (x < cp->data)){
　　        newP->next = cp;
　　        *hl = newP;
　　        return;
　　    }
　　    /* 顺序查找出x结点的插入位置 */
　　    while(cp != NULL){
　　        if(x < cp->data){
　　            break;
　　        }else{
　　            ap = cp;
　　            cp = cp->next;
　　        }
　　    }
　　    /* 把x结点插入到ap和cp之间 */
　　    newP->next = cp;
　　    ap->next = newP;
　　    return;
　　}
　　
　　/* 13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
　　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;            /* 返回第一个结点的值 */
　　}
　　
　　/* 14.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
　　elemType deleteLastList(struct sNode* *hl)
　　{
　　    elemType temp;
　　    /* 初始化cp和ap指针，使cp指向表头结点，使ap为空 */
　　    struct sNode *cp = *hl;
　　    struct sNode *ap = NULL;
　　    /* 单链表为空则停止运行 */
　　    if(cp == NULL){
　　        printf("单链表为空，无表头进行删除，退出运行！ ");
　　        exit(1);
　　    }
　　    /* 从单链表中查找表尾结点，循环结束时cp指向表尾结点，ap指向其前驱结点 */
　　    while(cp->next != NULL){
　　        ap = cp;
　　        cp = cp->next;
　　    }
　　    /* 若单链表中只有一个结点，则需要修改表头指针 */
　　    if(ap == NULL){
　　        *hl = (*hl)->next;        /* 或改为*hl = NULL; */
　　    }
　　    /* 删除表尾结点 */
　　    else{
　　        ap->next = NULL;
　　    }
　　    /* 暂存表尾元素，以便返回 */
　　    temp = cp->data;
　　    free(cp);        /* 回收被删除的表尾结点 */
　　    return temp;        /* 返回表尾结点的值 */
　　}
　　
　　/* 15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
　　elemType deletePosList(struct sNode* *hl, int pos)
　　{
　　    int i = 0;
　　    elemType temp;
　　    /* 初始化cp和ap指针，使cp指向表头结点，使ap为空 */
　　    struct sNode *cp = *hl;
　　    struct sNode *ap = NULL;
　　    /* 单链表为空或pos值非法则停止运行 */
　　    if((cp == NULL)  (pos <= 0)){
　　        printf("单链表为空或pos值不正确，退出运行！
　　 ");
　　        exit(1);
　　    }
　　    /* 从单链表中查找第pos个结点，找到后由cp指向该结点，由ap指向其前驱结点 */
　　    while(cp != NULL){
　　        i++;
　　        if(i == pos){
　　            break;
　　        }
　　        ap = cp;
　　        cp = cp->next;
　　    }
　　    /* 单链表中没有第pos个结点 */
　　    if(cp == NULL){
　　        printf("pos值不正确，退出运行！ ");
　　        exit(1);
　　    }
　　    /* 若pos等于1，则需要删除表头结点 */
　　    if(pos == 1){
　　        *hl = (*hl)->next;        /* 或改为*hl = cp->next; */
　　    }
　　    /* 否则删除非表头结点，此时cp指向该结点，ap指向前驱结点 */
　　    else{
　　        ap->next = cp->next;
　　    }
　　    /* 暂存第pos个结点的值，以便返回 */
　　    temp = cp->data;
　　    free(cp);        /* 回收被删除的第pos个结点 */
　　    return temp;    /* 返回在temp中暂存的第pos个结点的值 */
　　}
　　
　　/* 16.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
　　int deleteValueList(struct sNode* *hl, elemType x)
　　{
　　    /* 初始化cp和ap指针，使cp指向表头结点，使ap为空 */
　　    struct sNode *cp = *hl;
　　    struct sNode *ap = NULL;
　　    /* 从单链表中查找值为x的结点，找到后由cp指向该结点，由ap指向其前驱结点 */
　　    while(cp != NULL){
　　        if(cp->data == x){
　　            break;
　　        }
　　        ap = cp;
　　        cp = cp->next;
　　    }
　　    /* 若查找失败，即该单链表中不存在值为x的结点，则返回0 */
　　    if(cp == NULL){
　　        return 0;
　　    }
　　    /* 假如删除的是表头或非表头结点则分别进行处理 */
　　    if(ap == NULL){
　　        *hl = (*hl)->next;        /* 或改为*hl= cp->next */
　　    }else{
　　        ap->next = cp->next;
　　    }
　　    free(cp);        /* 回收被删除的结点 */
　　    return 1;        /* 返回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;
　　}