關(guān)于線性表順序存儲(chǔ)操作的16種算法

1、#include <stdio.h>#include <stdlib.h>typedef int elemType;/*/*                以下是關(guān)于線性表順序存儲(chǔ)操作的16種算法               

2、         */*/struct List    elemType *list;    int size;    int maxSize;void againMalloc(struct List *L)        /* 空間擴(kuò)展為

3、原來的2倍，并由p指針?biāo)赶?，原?nèi)容被自動(dòng)拷貝到p所指向的存儲(chǔ)空間 */    elemType *p = realloc(L->list, 2 * L->maxSize * sizeof(elemType);    if(!p)    /* 分配失敗則退出運(yùn)行 */       

4、60;printf("存儲(chǔ)空間分配失??！ ");        exit(1);        L->list = p;    /* 使list指向新線性表空間 */    L->maxSize = 2 * L->maxSize; 

5、   /* 把線性表空間大小修改為新的長(zhǎng)度 */* 1.初始化線性表L，即進(jìn)行動(dòng)態(tài)存儲(chǔ)空間分配并置L為一個(gè)空表 */void initList(struct List *L, int ms)    /* 檢查ms是否有效，若無效的則退出運(yùn)行 */    if(ms <= 0)      

6、60; printf("MaxSize非法！ ");        exit(1);    /*  */        L->maxSize = ms;    /* 設(shè)置線性表空間大小為ms */    L->size

7、 = 0;    L->list = malloc(ms * sizeof(elemType);    if(!L->list)        printf("空間分配失??！ ");        exit(1);    

8、60;   return;/* 2.清除線性表L中的所有元素，釋放存儲(chǔ)空間，使之成為一個(gè)空表 */void clearList(struct List *L)    if(L->list != NULL)        free(L->list);        L->list&#

9、160;= 0;        L->size = L->maxSize = 0;        return;/* 3.返回線性表L當(dāng)前的長(zhǎng)度，若L為空則返回 */int sizeList(struct List *L)    return L->size;/*

10、0;4.判斷線性表L是否為空，若為空則返回1, 否則返回0 */int emptyList(struct List *L)    if(L->size =0)        return 1;        else        return

11、 0;    /* 5.返回線性表L中第pos個(gè)元素的值，若pos超出范圍，則停止程序運(yùn)行 */elemType getElem(struct List *L, int pos)    if(pos < 1 | pos > L->size)    /* 若pos越界則退出運(yùn)行 */ 

12、0;      printf("元素序號(hào)越界！ ");        exit(1);        return L->listpos - 1;    /* 返回線性表中序號(hào)為pos值的元素值 */* 6.順序掃描（即遍歷）輸出線性表L中的每個(gè)元素&#

13、160;*/void traverseList(struct List *L)    int i;    for(i = 0; i < L->size; i+)        printf("%d ", L ->listi);    

14、;    printf(" ");     return;/* 7.從線性表L中查找值與x相等的元素，若查找成功則返回其位置，否則返回-1 */int findList(struct List *L, elemType x)    int i;    for(i = 0; i <&#

15、160;L->size; i+)        if(L->listi = x)            return i;                return -1;/*

16、 8.把線性表L中第pos個(gè)元素的值修改為x的值，若修改成功返回1，否則返回0 */int updatePosList(struct List *L, int pos, elemType x)    if(pos < 1 | pos > L->size)    /* 若pos越界則修改失敗 */   

17、     return 0;        L->listpos - 1 = x;    return 1;/*  */void inserFirstList(struct List *L, elemType x)    int i; 

18、;   if(L->size = L->maxSize)        againMalloc(L);        for(i = L->size - 1; i >= 0; i-)        L-&g

19、t;listi + 1 = L ->listi;        L->list0 = x;    L->size +;    return;/*  */void insertLastList(struct List *L, elemType x)  &

20、#160; if(L->size = L ->maxSize)    /* 重新分配更大的存儲(chǔ)空間 */        againMalloc(L);        L->listL->size = x;    /* 把x插入到表尾 *

21、/    L->size+;    /* 線性表的長(zhǎng)度增加 */    return;/* 11.向線性表L中第pos個(gè)元素位置插入元素x，若插入成功返回，否則返回 */int insertPosList(struct List *L, int pos, elemType x)    int i; &#

22、160;  if(pos < 1 | pos > L->size + 1)    /* 若pos越界則插入失敗 */        return 0;        if(L->size = L->maxSize)

23、60;   /* 重新分配更大的存儲(chǔ)空間 */        againMalloc(L);        for(i = L->size - 1; i >= pos - 1; i-)        

24、;L->listi + 1 = L->listi;        L->listpos - 1 = x;    L->size+;    return 1;/* 12.向有序線性表L中插入元素x,使得插入后仍然有序*/void insertOrderList(struct List *

25、L, elemType x)    int i, j;    /* 若數(shù)組空間用完則重新分配更大的存儲(chǔ)空間 */    if(L->size = L->maxSize)        againMalloc(L);        

26、;/* 順序查找出x的插入位置 */    for(i = 0; i < L->size; i+)        if(x < L->listi)             break;   

27、60;            /* 從表尾到下標(biāo)i元素依次后移一個(gè)位置， 把i的位置空出來 */    for(j = L->size - 1; j >= i; j-)        L->listj+1 = L

28、->listj;    /* 把x值賦給下標(biāo)為i的元素 */        L->listi = x;    /* 線性表長(zhǎng)度增加1 */    L->size+;    return;/* 13.從線性表L中刪除表頭元素并返回它，若刪除失敗則停止程序運(yùn)行 */

29、elemType deleteFirstList(struct List *L)    elemType temp;    int i;    if(L ->size = 0)        printf("線性表為空，不能進(jìn)行刪除操作！ ");    

30、    exit(1);        temp = L->list0;    for(i = 1; i < L->size; i+)        L->listi-1 = L->listi;   

31、 L->size-;    return temp;/* 14.從線性表L中刪除表尾元素并返回它，若刪除失敗則停止程序運(yùn)行 */elemType deleteLastList(struct List *L)    if(L ->size = 0)        printf("線性表為空，不能進(jìn)行刪除操作！ &quo

32、t;);        exit(1);        L->size-;    return L ->listL->size;        /* 返回原來表尾元素的值 */* 15.從線性表L中刪除第pos個(gè)元素并返回它，若刪除失敗則停止程序運(yùn)行&

33、#160;*/elemType deletePosList(struct List *L, int pos)    elemType temp;    int i;    if(pos < 1 | pos > L->size)        /*

34、60;pos越界則刪除失敗 */        printf("pos值越界，不能進(jìn)行刪除操作！ ");        exit(1);        temp = L->listpos-1;    for(i = pos; i

35、60;< L->size; i+)        L->listi-1 = L->listi;    L->size-;    return temp;/* 16.從線性表L中刪除值為x的第一個(gè)元素，若成功返回1，失敗返回0 */int deleteValueList(struct List *L, 

36、;elemType x)    int i, j;    /* 從線性表中順序查找出值為x的第一個(gè)元素 */    for(i = 0; i < L->size; i+)        if(L->listi = x)   

37、;             break;                /* 若查找失敗，表明不存在值為x的元素，返回0 */    if(i = L->size)     

38、   return 0;        /* 刪除值為x的元素L->listi */    for(j = i + 1; j < L->size; j+)        L->listj-1 = L->list

39、j;        L->size-;    return 1;/*/void main()    int a10 = 2, 4, 6, 8, 10, 12, 14, 16, 18, 20;    int i;   

40、; struct List L;    initList(&L, 5);    for(i = 0; i < 10; i+)        insertLastList(&L, ai);        insertPosList

41、(&L, 11, 48);        insertPosList(&L, 1, 64);    printf("%d ", getElem(&L, 1);    traverseList(&L);    printf("%d ", findList(&a

42、mp;L, 10);    updatePosList(&L, 3, 20);    printf("%d ", getElem(&L, 3);    traverseList(&L);    deleteFirstList(&L);        

43、0;   deleteFirstList(&L);    deleteLastList(&L);                deleteLastList(&L);    deletePosList(&L, 5);      

44、      deletePosList(&L, 7);    printf("%d ", sizeList(&L);    printf("%d ", emptyList(&L);    traverseList(&L);    clearList(&L); 

45、   return 0; #include <stdio.h>#include <stdlib.h>#define NN 12#define MM 20typedef int elemType /*/*             以下是關(guān)于線性表鏈接存儲(chǔ)（單鏈表）操作的16種算法  &#

46、160;     */*/struct sNode    /* 定義單鏈表結(jié)點(diǎn)類型 */    elemType data;    struct sNode *next;/* 1.初始化線性表，即置單鏈表的表頭指針為空 */void initList(struct sNode* *hl)  

47、0; *hl = NULL;    return;/* 2.清除線性表L中的所有元素，即釋放單鏈表L中所有的結(jié)點(diǎn)，使之成為一個(gè)空表 */void clearList(struct sNode* *hl)    /* cp和np分別作為指向兩個(gè)相鄰結(jié)點(diǎn)的指針 */    struct sNode *cp, *np;   

48、 cp = *hl;    /* 遍歷單鏈表，依次釋放每個(gè)結(jié)點(diǎn) */    while(cp != NULL)        np = cp->next;    /* 保存下一個(gè)結(jié)點(diǎn)的指針 */       

49、60;free(cp);        cp = np;        *hl = NULL;        /* 置單鏈表的表頭指針為空 */    return;/*  */int sizeList(struct s

50、Node *hl)    int count = 0;        /* 用于統(tǒng)計(jì)結(jié)點(diǎn)的個(gè)數(shù) */    while(hl != NULL)        count+;        hl

51、0;= hl->next;        return count;/* 4.檢查單鏈表是否為空，若為空則返回，否則返回 */int emptyList(struct sNode *hl)    if(hl = NULL)        return 1;   &

52、#160;else        return 0;    /* 5.返回單鏈表中第pos個(gè)結(jié)點(diǎn)中的元素，若pos超出范圍，則停止程序運(yùn)行 */elemType getElem(struct sNode *hl, int pos)    int i = 0;      

53、  /* 統(tǒng)計(jì)已遍歷的結(jié)點(diǎn)個(gè)數(shù) */    if(pos < 1)        printf("pos值非法，退出運(yùn)行！ ");        exit(1);        while(hl != NULL)&

54、#160;       i+;        if(i = pos)            break;                hl 

55、;= hl->next;        if(hl != NULL)        return hl->data;    else        printf("pos值非法，退出運(yùn)行！ ");    &#

56、160;   exit(1);    /*  */void traverseList(struct sNode *hl)    while(hl != NULL)        printf("%5d", hl->data);      

57、60; hl = hl->next;        printf(" ");    return;/* 7.從單鏈表中查找具有給定值x的第一個(gè)元素，若查找成功則返回該結(jié)點(diǎn)data域的存儲(chǔ)地址，否則返回NULL */elemType* findList(struct sNode *hl, elemType x)   

58、0;while(hl != NULL)        if(hl->data = x)            return &hl->data;        else       

59、;     hl = hl->next;                    return NULL;/* 8.把單鏈表中第pos個(gè)結(jié)點(diǎn)的值修改為x的值，若修改成功返回，否則返回 */int updatePosList(struct sNode *hl,

60、0;int pos, elemType x)    int i = 0;    struct sNode *p = hl;    while(p != NULL)        /* 查找第pos個(gè)結(jié)點(diǎn) */    &#

61、160;   i+;        if(pos = i)            break;        else            p

62、60;= p->next;                if(pos = i)        p->data = x;        return 1;    els

63、e        return 0;    /*  */void insertFirstList(struct sNode* *hl, elemType x)    struct sNode *newP;    newP = malloc(sizeof(struct s

64、Node);    if(newP = NULL)        printf("內(nèi)存分配失敗，退出運(yùn)行！ ");        exit(1);        newP->data = x;     &

65、#160;  /* 把x的值賦給新結(jié)點(diǎn)的data域 */    /* 把新結(jié)點(diǎn)作為新的表頭結(jié)點(diǎn)插入 */    newP->next = *hl;            *hl = newP;    return;/*  */void

66、 insertLastList(struct sNode* *hl, elemType x)    struct sNode *newP;    newP = malloc(sizeof(struct sNode);    if(newP = NULL)        print

67、f("內(nèi)在分配失敗，退出運(yùn)行！ ");        exit(1);        /* 把x的值賦給新結(jié)點(diǎn)的data域，把空值賦給新結(jié)點(diǎn)的next域 */    newP->data = x;    newP->next = NULL;  &#

68、160; /* 若原表為空，則作為表頭結(jié)點(diǎn)插入 */    if(*hl = NULL)        *hl = newP;                /* 查找到表尾結(jié)點(diǎn)并完成插入 */   

69、 else        struct sNode *p = NULL;        while(p->next != NULL)            p = p->next;   &

70、#160;            p->next = newP;        return;/* 11.向單鏈表中第pos個(gè)結(jié)點(diǎn)位置插入元素為x的結(jié)點(diǎn)，若插入成功返回，否則返回 */int insetPosList(struct sNode* *hl, int pos, elemType&#

71、160;x)    int i = 0;    struct sNode *newP;    struct sNode *cp = *hl, *ap = NULL;    /* 對(duì)pos值小于等于的情況進(jìn)行處理 */    if(pos <=&

72、#160;0)        printf("pos值非法，返回表示插入失??！ ");        return 0;        /* 查找第pos個(gè)結(jié)點(diǎn) */    while(cp != NULL)   

73、60;    i+;        if(pos = i)            break;        else            

74、;ap = cp;            cp = cp->next;                /* 產(chǎn)生新結(jié)點(diǎn)，若分配失敗，則停止插入 */    newP = malloc(sizeo

75、f(struct sNode);    if(newP = NULL)        printf("內(nèi)存分配失敗，無法進(jìn)行插入操作！ ");        return 0;        /* 把x的值賦給新結(jié)點(diǎn)的data域 */

76、60;   newP->data = x;    /* 把新結(jié)點(diǎn)插入到表頭 */    if(ap = NULL)        newP->next = cp;        /* 或改為newP->next 

77、= *hl; */        *hl = newP;        /* 把新結(jié)點(diǎn)插入到ap和cp之間 */    else        newP->next = cp;     

78、;   ap->next = newP;        return 1;        /* 插入成功返回1 */* 12.向有序單鏈表中插入元素x結(jié)點(diǎn)，使得插入后仍然有序 */void insertOrderList(struct sNode* *hl, elemType x)&

79、#160;   /* 把單鏈表的表頭指針賦給cp，把a(bǔ)p置空 */    struct sNode *cp = *hl, *ap = NULL;    /* 建立新結(jié)點(diǎn) */    struct sNode *newP;    newP = malloc(si

80、zeof(struct sNode);    if(newP = NULL)        printf("內(nèi)在分配失敗，退出運(yùn)行！ ");        exit(1);        newP->data = x;  &

81、#160;     /* 把x的值賦給新結(jié)點(diǎn)的data域 */    /* 把新結(jié)點(diǎn)插入到表頭 */    if(cp = NULL) | (x < cp->data)        newP->next = cp;   

82、     *hl = newP;        return;        /* 順序查找出x結(jié)點(diǎn)的插入位置 */    while(cp != NULL)        if(x <

83、0;cp->data)            break;        else            ap = cp;           

84、 cp = cp->next;                /* 把x結(jié)點(diǎn)插入到ap和cp之間 */    newP->next = cp;    ap->next = newP;    return;/*&#

85、160;13.從單鏈表中刪除表頭結(jié)點(diǎn)，并把該結(jié)點(diǎn)的值返回，若刪除失敗則停止程序運(yùn)行 */elemType deleteFirstList(struct sNode* *hl)    elemType temp;    struct sNode *p = *hl;        /* 暫存表頭結(jié)點(diǎn)指針，以便回收 */ &

86、#160;  if(*hl = NULL)        printf("單鏈表為空，無表頭可進(jìn)行刪除，退出運(yùn)行！ ");        exit(1);        *hl = (*hl)->next;     

87、0;  /* 使表頭指針指向第二個(gè)結(jié)點(diǎn) */    temp = p->data;            /* 暫存原表頭元素，以便返回 */    free(p);            &#

88、160;   /* 回收被刪除的表頭結(jié)點(diǎn) */    return temp;            /* 返回第一個(gè)結(jié)點(diǎn)的值 */* 14.從單鏈表中刪除表尾結(jié)點(diǎn)并返回它的值，若刪除失敗則停止程序運(yùn)行 */elemType deleteLastList(struct sNode* *hl) 

89、60;  elemType temp;    /* 初始化cp和ap指針，使cp指向表頭結(jié)點(diǎn)，使ap為空 */    struct sNode *cp = *hl;    struct sNode *ap = NULL;    /* 單鏈表為空則停止運(yùn)行 */  

90、60; if(cp = NULL)        printf("單鏈表為空，無表頭進(jìn)行刪除，退出運(yùn)行！ ");        exit(1);        /* 從單鏈表中查找表尾結(jié)點(diǎn)，循環(huán)結(jié)束時(shí)cp指向表尾結(jié)點(diǎn)，ap指向其前驅(qū)結(jié)點(diǎn) */    

91、while(cp->next != NULL)        ap = cp;        cp = cp->next;        /* 若單鏈表中只有一個(gè)結(jié)點(diǎn)，則需要修改表頭指針 */    if(ap =&#

92、160;NULL)        *hl = (*hl)->next;        /* 或改為*hl = NULL; */        /* 刪除表尾結(jié)點(diǎn) */    else    &#

93、160;   ap->next = NULL;        /* 暫存表尾元素，以便返回 */    temp = cp->data;    free(cp);        /* 回收被刪除的表尾結(jié)點(diǎn) */  &#

94、160; return temp;        /* 返回表尾結(jié)點(diǎn)的值 */* 15.從單鏈表中刪除第pos個(gè)結(jié)點(diǎn)并返回它的值，若刪除失敗則停止程序運(yùn)行 */elemType deletePosList(struct sNode* *hl, int pos)    int i = 0;    el

95、emType temp;    /* 初始化cp和ap指針，使cp指向表頭結(jié)點(diǎn)，使ap為空 */    struct sNode *cp = *hl;    struct sNode *ap = NULL;    /* 單鏈表為空或pos值非法則停止運(yùn)行 */    i

96、f(cp = NULL) | (pos <= 0)        printf("單鏈表為空或pos值不正確，退出運(yùn)行！ ");        exit(1);        /* 從單鏈表中查找第pos個(gè)結(jié)點(diǎn)，找到后由cp指向該結(jié)點(diǎn)，由ap指向其前驅(qū)結(jié)點(diǎn)

97、0;*/    while(cp != NULL)        i+;        if(i = pos)            break;        

98、;        ap = cp;        cp = cp->next;        /* 單鏈表中沒有第pos個(gè)結(jié)點(diǎn) */    if(cp = NULL)     

99、0;  printf("pos值不正確，退出運(yùn)行！ ");        exit(1);        /* 若pos等于1，則需要?jiǎng)h除表頭結(jié)點(diǎn) */    if(pos = 1)        *hl = (*hl)

100、->next;        /* 或改為*hl = cp->next; */        /* 否則刪除非表頭結(jié)點(diǎn)，此時(shí)cp指向該結(jié)點(diǎn)，ap指向前驅(qū)結(jié)點(diǎn) */    else        ap->next = cp-

101、>next;        /* 暫存第pos個(gè)結(jié)點(diǎn)的值，以便返回 */    temp = cp->data;    free(cp);        /* 回收被刪除的第pos個(gè)結(jié)點(diǎn) */    return temp; &

102、#160;  /* 返回在temp中暫存的第pos個(gè)結(jié)點(diǎn)的值 */* 16.從單鏈表中刪除值為x的第一個(gè)結(jié)點(diǎn)，若刪除成功則返回1,否則返回0 */int deleteValueList(struct sNode* *hl, elemType x)    /* 初始化cp和ap指針，使cp指向表頭結(jié)點(diǎn)，使ap為空 */    struct sNode *cp = *hl;    struct sNode *ap = NUL