數(shù)據(jù)結(jié)構(gòu)C語言實現(xiàn)系列——線性表

1、數(shù)據(jù)結(jié)構(gòu)C語言實現(xiàn)系列線性表2007-02-03 08:00來源：csdn作者：88250責(zé)任編輯：龍犢·yesky評論(3)#include <stdio.h>#include <stdlib.h>typedef int elemType;/*/*                以下是關(guān)于線性表順序存儲操作的16種算法   

2、0;                    */*/struct List    elemType *list;    int size;    int maxSize;void againMalloc(struct List&#

3、160;*L)        /* 空間擴展為原來的2倍，并由p指針?biāo)赶颍瓋?nèi)容被自動拷貝到p所指向的存儲空間 */    elemType *p = realloc(L->list, 2 * L->maxSize * sizeof(elemType);    if(!p)    /*

4、 分配失敗則退出運行 */        printf("存儲空間分配失敗！ ");        exit(1);        L->list = p;    /* 使list指向新線性表空間 */  

5、;  L->maxSize = 2 * L->maxSize;    /* 把線性表空間大小修改為新的長度 */* 1.初始化線性表L，即進行動態(tài)存儲空間分配并置L為一個空表 */void initList(struct List *L, int ms)    /* 檢查ms是否有效，若無效的則退出運行 */  &#

6、160; if(ms <= 0)        printf("MaxSize非法！ ");        exit(1);    /* 執(zhí)行此函數(shù)中止程序運行，此函數(shù)在stdlib.h中有定義 */        L->max

7、Size = ms;    /* 設(shè)置線性表空間大小為ms */    L->size = 0;    L->list = malloc(ms * sizeof(elemType);    if(!L->list)        printf

8、("空間分配失??！ ");        exit(1);        return;/* 2.清除線性表L中的所有元素，釋放存儲空間，使之成為一個空表 */void clearList(struct List *L)    if(L->list != NULL)  &#

9、160;     free(L->list);        L->list = 0;        L->size = L->maxSize = 0;        return;/* 3.返回線性表L當(dāng)前的長度，

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

11、60;1;        else        return 0;    /* 5.返回線性表L中第pos個元素的值，若pos超出范圍，則停止程序運行 */elemType getElem(struct List *L, int pos)    if(pos <

12、 1 | pos > L->size)    /* 若pos越界則退出運行 */        printf("元素序號越界！ ");        exit(1);        return L

13、->listpos - 1;    /* 返回線性表中序號為pos值的元素值 */* 6.順序掃描（即遍歷）輸出線性表L中的每個元素 */void traverseList(struct List *L)    int i;    for(i = 0; i < L->size; i+) &#

14、160;      printf("%d ", L ->listi);        printf(" ");     return;/* 7.從線性表L中查找值與x相等的元素，若查找成功則返回其位置，否則返回-1 */int findList(struct List *L

15、, elemType x)    int i;    for(i = 0; i < L->size; i+)        if(L->listi = x)            return

16、 i;                return -1;/* 8.把線性表L中第pos個元素的值修改為x的值，若修改成功返回1，否則返回0 */int updatePosList(struct List *L, int pos, elemType x)    if(pos &l

17、t; 1 | pos > L->size)    /* 若pos越界則修改失敗 */        return 0;        L->listpos - 1 = x;    return 1;/* 

18、;9.向線性表L的表頭插入元素x */void inserFirstList(struct List *L, elemType x)    int i;    if(L->size = L->maxSize)        againMalloc(L);       

19、 for(i = L->size - 1; i >= 0; i-)        L->listi + 1 = L ->listi;        L->list0 = x;    L->size

20、0;+;    return;/* 10.向線性表L的表尾插入元素x */void insertLastList(struct List *L, elemType x)    if(L->size = L ->maxSize)    /* 重新分配更大的存儲空間 */      

21、0; againMalloc(L);        L->listL->size = x;    /* 把x插入到表尾 */    L->size+;    /* 線性表的長度增加 */    return;/* 11.向線性表L中第pos個元素位置插入元素x，

22、若插入成功返回，否則返回 */int insertPosList(struct List *L, int pos, elemType x)    int i;    if(pos < 1 | pos > L->size + 1)    /* 若pos越界則插入失敗 */&

23、#160;       return 0;        if(L->size = L->maxSize)    /* 重新分配更大的存儲空間 */        againMalloc(L);      &

24、#160; for(i = L->size - 1; i >= pos - 1; i-)        L->listi + 1 = L->listi;        L->listpos - 1 = x; &

25、#160;  L->size+;    return 1;/* 12.向有序線性表L中插入元素x,使得插入后仍然有序*/void insertOrderList(struct List *L, elemType x)    int i, j;    /* 若數(shù)組空間用完則重新分配更大的存儲空間 */   

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

27、60;  if(x < L->listi)             break;                /* 從表尾到下標(biāo)i元素依次后移一個位置， 把i的位置空出來 */    f

28、or(j = L->size - 1; j >= i; j-)        L->listj+1 = L->listj;    /* 把x值賦給下標(biāo)為i的元素 */        L->listi = x;  

29、;  /* 線性表長度增加1 */    L->size+;    return;/* 13.從線性表L中刪除表頭元素并返回它，若刪除失敗則停止程序運行 */elemType deleteFirstList(struct List *L)    elemType temp;    int i;  

30、60; if(L ->size = 0)        printf("線性表為空，不能進行刪除操作！ ");        exit(1);        temp = L->list0;    for(i 

31、;= 1; i < L->size; i+)        L->listi-1 = L->listi;    L->size-;    return temp;/* 14.從線性表L中刪除表尾元素并返回它，若刪除失敗則停止程序運行 */elemType deleteLastList(struct&

32、#160;List *L)    if(L ->size = 0)        printf("線性表為空，不能進行刪除操作！ ");        exit(1);        L->size-;   

33、 return L ->listL->size;        /* 返回原來表尾元素的值 */* 15.從線性表L中刪除第pos個元素并返回它，若刪除失敗則停止程序運行 */elemType deletePosList(struct List *L, int pos)    elemType temp;  

34、0; int i;    if(pos < 1 | pos > L->size)        /* pos越界則刪除失敗 */        printf("pos值越界，不能進行刪除操作！ ");    &#

35、160;   exit(1);        temp = L->listpos-1;    for(i = pos; i < L->size; i+)        L->listi-1 = L->listi;  &#

36、160; L->size-;    return temp;/* 16.從線性表L中刪除值為x的第一個元素，若成功返回1，失敗返回0 */int deleteValueList(struct List *L, elemType x)    int i, j;    /* 從線性表中順序查找出值為x的第一個元素 */  &#

37、160; for(i = 0; i < L->size; i+)        if(L->listi = x)                break;        

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

39、 for(j = i + 1; j < L->size; j+)        L->listj-1 = L->listj;        L->size-;    return 1;/*/void main()  &#

40、160; int a10 = 2, 4, 6, 8, 10, 12, 14, 16, 18, 20;    int i;    struct List L;    initList(&L, 5);    for(i = 0; i&#

41、160;< 10; i+)        insertLastList(&L, ai);        insertPosList(&L, 11, 48);        insertPosList(&L, 1, 64);   &

42、#160;printf("%d ", getElem(&L, 1);    traverseList(&L);    printf("%d ", findList(&L, 10);    updatePosList(&L, 3, 20);    printf("%d 

43、", getElem(&L, 3);    traverseList(&L);    deleteFirstList(&L);            deleteFirstList(&L);    deleteLastList(&L);    

44、60;           deleteLastList(&L);    deletePosList(&L, 5);            deletePosList(&L, 7);    printf("%d ",

45、 sizeList(&L);    printf("%d ", emptyList(&L);    traverseList(&L);    clearList(&L);    return 0;#include <stdio.h>#include <stdlib.h>#define NN&#

46、160;12#define MM 20typedef int elemType /*/*             以下是關(guān)于線性表鏈接存儲（單鏈表）操作的16種算法        */*/struct sNode    /* 定義單鏈表結(jié)點類型 */ 

47、0;  elemType data;    struct sNode *next;/* 1.初始化線性表，即置單鏈表的表頭指針為空 */void initList(struct sNode* *hl)    *hl = NULL;    return;/* 2.清除線性表L中的所有元素，即釋放單鏈表L中所有的結(jié)點，使之成為一個空表 */v

48、oid clearList(struct sNode* *hl)    /* cp和np分別作為指向兩個相鄰結(jié)點的指針 */    struct sNode *cp, *np;    cp = *hl;    /* 遍歷單鏈表，依次釋放每個結(jié)點 */    while(cp

49、60;!= NULL)        np = cp->next;    /* 保存下一個結(jié)點的指針 */        free(cp);        cp = np;      

50、  *hl = NULL;        /* 置單鏈表的表頭指針為空 */    return;/* 3.返回單鏈表的長度 */int sizeList(struct sNode *hl)    int count = 0;      &

51、#160; /* 用于統(tǒng)計結(jié)點的個數(shù) */    while(hl != NULL)        count+;        hl = hl->next;        return count;/* 4.檢查單鏈表是否

52、為空，若為空則返回，否則返回 */int emptyList(struct sNode *hl)    if(hl = NULL)        return 1;    else        return 0;    /* 5

53、.返回單鏈表中第pos個結(jié)點中的元素，若pos超出范圍，則停止程序運行 */elemType getElem(struct sNode *hl, int pos)    int i = 0;        /* 統(tǒng)計已遍歷的結(jié)點個數(shù) */    if(pos < 1)   

54、     printf("pos值非法，退出運行！ ");        exit(1);        while(hl != NULL)        i+;        i

55、f(i = pos)            break;                hl = hl->next;        if(hl != NULL) &

56、#160;      return hl->data;    else        printf("pos值非法，退出運行！ ");        exit(1);    /* 6.遍歷一個單鏈表 */void trave

57、rseList(struct sNode *hl)    while(hl != NULL)        printf("%5d", hl->data);        hl = hl->next;        p

58、rintf(" ");    return;/* 7.從單鏈表中查找具有給定值x的第一個元素，若查找成功則返回該結(jié)點data域的存儲地址，否則返回NULL */elemType* findList(struct sNode *hl, elemType x)    while(hl != NULL)        if(

59、hl->data = x)            return &hl->data;        else            hl = hl->next;   

60、0;                return NULL;/* 8.把單鏈表中第pos個結(jié)點的值修改為x的值，若修改成功返回，否則返回 */int updatePosList(struct sNode *hl, int pos, elemType x)    int i =&#

61、160;0;    struct sNode *p = hl;    while(p != NULL)        /* 查找第pos個結(jié)點 */        i+;        if(pos&

62、#160;= i)            break;        else            p = p->next;          

63、;      if(pos = i)        p->data = x;        return 1;    else        return 0;   

64、; /* 9.向單鏈表的表頭插入一個元素 */void insertFirstList(struct sNode* *hl, elemType x)    struct sNode *newP;    newP = malloc(sizeof(struct sNode);    if(newP = NULL) 

65、0;      printf("內(nèi)存分配失敗，退出運行！ ");        exit(1);        newP->data = x;        /* 把x的值賦給新結(jié)點的data域 */  

66、  /* 把新結(jié)點作為新的表頭結(jié)點插入 */    newP->next = *hl;            *hl = newP;    return;/* 10.向單鏈表的末尾添加一個元素 */void insertLastList(struct sNode* 

67、;*hl, elemType x)    struct sNode *newP;    newP = malloc(sizeof(struct sNode);    if(newP = NULL)        printf("內(nèi)在分配失敗，退出運行！ "); 

68、0;      exit(1);        /* 把x的值賦給新結(jié)點的data域，把空值賦給新結(jié)點的next域 */    newP->data = x;    newP->next = NULL;    /* 若原表為空，則作為表頭結(jié)點插入 

69、*/    if(*hl = NULL)        *hl = newP;                /* 查找到表尾結(jié)點并完成插入 */    else     

70、;   struct sNode *p = NULL;        while(p->next != NULL)            p = p->next;         

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

72、i = 0;    struct sNode *newP;    struct sNode *cp = *hl, *ap = NULL;    /* 對pos值小于等于的情況進行處理 */    if(pos <= 0)     &#

73、160;  printf("pos值非法，返回表示插入失?。?#160;");        return 0;        /* 查找第pos個結(jié)點 */    while(cp != NULL)        i+;

74、0;       if(pos = i)            break;        else            ap = cp;  

75、60;         cp = cp->next;                /* 產(chǎn)生新結(jié)點，若分配失敗，則停止插入 */    newP = malloc(sizeof(struct sNode);  &

76、#160; if(newP = NULL)        printf("內(nèi)存分配失敗，無法進行插入操作！ ");        return 0;        /* 把x的值賦給新結(jié)點的data域 */    newP->

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

78、0;      *hl = newP;        /* 把新結(jié)點插入到ap和cp之間 */    else        newP->next = cp;        ap->nex

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

80、0;把單鏈表的表頭指針賦給cp，把ap置空 */    struct sNode *cp = *hl, *ap = NULL;    /* 建立新結(jié)點 */    struct sNode *newP;    newP = malloc(sizeof(struct sNode); 

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

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

83、 *hl = newP;        return;        /* 順序查找出x結(jié)點的插入位置 */    while(cp != NULL)        if(x < cp->data) 

84、0;          break;        else            ap = cp;            cp = cp-

85、>next;                /* 把x結(jié)點插入到ap和cp之間 */    newP->next = cp;    ap->next = newP;    return;/* 13.從單鏈表中刪除表頭結(jié)點，并把該結(jié)點

86、的值返回，若刪除失敗則停止程序運行 */elemType deleteFirstList(struct sNode* *hl)    elemType temp;    struct sNode *p = *hl;        /* 暫存表頭結(jié)點指針，以便回收 */    if(*hl&

87、#160;= NULL)        printf("單鏈表為空，無表頭可進行刪除，退出運行！ ");        exit(1);        *hl = (*hl)->next;        /*

88、60;使表頭指針指向第二個結(jié)點 */    temp = p->data;            /* 暫存原表頭元素，以便返回 */    free(p);               

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

90、Type temp;    /* 初始化cp和ap指針，使cp指向表頭結(jié)點，使ap為空 */    struct sNode *cp = *hl;    struct sNode *ap = NULL;    /* 單鏈表為空則停止運行 */    if(cp 

91、;= NULL)        printf("單鏈表為空，無表頭進行刪除，退出運行！ ");        exit(1);        /* 從單鏈表中查找表尾結(jié)點，循環(huán)結(jié)束時cp指向表尾結(jié)點，ap指向其前驅(qū)結(jié)點 */    while(cp->n

92、ext != NULL)        ap = cp;        cp = cp->next;        /* 若單鏈表中只有一個結(jié)點，則需要修改表頭指針 */    if(ap = NULL) 

93、;       *hl = (*hl)->next;        /* 或改為*hl = NULL; */        /* 刪除表尾結(jié)點 */    else      

94、0; ap->next = NULL;        /* 暫存表尾元素，以便返回 */    temp = cp->data;    free(cp);        /* 回收被刪除的表尾結(jié)點 */    retu

95、rn temp;        /* 返回表尾結(jié)點的值 */* 15.從單鏈表中刪除第pos個結(jié)點并返回它的值，若刪除失敗則停止程序運行 */elemType deletePosList(struct sNode* *hl, int pos)    int i = 0;    elemType te

96、mp;    /* 初始化cp和ap指針，使cp指向表頭結(jié)點，使ap為空 */    struct sNode *cp = *hl;    struct sNode *ap = NULL;    /* 單鏈表為空或pos值非法則停止運行 */    if(cp =

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

98、;   while(cp != NULL)        i+;        if(i = pos)            break;         &#

99、160;      ap = cp;        cp = cp->next;        /* 單鏈表中沒有第pos個結(jié)點 */    if(cp = NULL)       &

100、#160;printf("pos值不正確，退出運行！ ");        exit(1);        /* 若pos等于1，則需要刪除表頭結(jié)點 */    if(pos = 1)        *hl = (*hl)->

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

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

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