天天看點
傳回

【資料結構】線性表順序存儲結構線性表的順序存儲順序存儲下線性表的操作實作

線性表的順序存儲

線性表的存儲結構有順序、連結、索引、散列等多種方式，順序存儲結構是其中最簡單、最常見的一種。

線性表的順序存儲結構可叙述為：把線性表中所有元素按照其邏輯順序依次存儲到計算機存儲器中從指定存儲位置開始的一塊連續的存儲空間中，使得線性表中的第一個元素的位置就是被指定存儲空間中的開始位置，第i個元素（2≤i≤n）被緊接着存儲在第i-1個元素的存儲位置的後面。

元素類型為ElemType的線性表的順序存儲類型描述：

stuuct List{
    ElemType list[MaxSize]; //定義一個數組來存儲線性表中的所有元素
    int size; //定義一個整型變量來存儲線性表的長度

}

元素類型為ElemType的線性表數組空間動态配置設定的順序存儲類型描述：

struct List{
    ElemType list; //存儲線性表元素的動态存儲空間的指針
    int size; //存儲線性表長度
    int MaxSize; //存儲list數組長度，即所能存儲線性表最大長度
}

順序存儲下線性表的操作實作

1.初始化線性表L，即進行動态存儲空間配置設定并置L為一個空表

void InitList(struct List *L,int ms){
    //檢查ms是否有效，若無效則退出運作
    if(ms < 0){
        printf("ms值無效！\n")；
        exit(1);
    }
    //置線性表空間大小為ms
    L->MaxSize = ms;
    //動态存儲空間配置設定，若配置設定失敗則退出運作
    L->list = (ElemType *)malloc(ms * sizeof(ElemType));
    if(!L->list){
        printf("動态存儲配置設定失敗！\n");
        exit(1);    
    }
    //初始化置線性表為空
    L->size = 0;    
}

2.清除線性表L中的所有元素，釋放動态存儲空間，使之成為一個空表

void ClearList(struct List *L){
    if(L->list != NULL){
        free(L->list); //釋放存儲空間
        L->list = 0;
        L->size = L->MaxSize = 0;
    }
}

3.傳回線性表L的長度，若L為空則傳回0

//該函數就是傳回線性表L的size域的值，它可以用表達式L->size直接代替
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);
    }
    //傳回線性表中序号為pos值的元素的值
    return L->list[pos-1];
    
}

6.周遊輸出線性表L中的每個元素

void TraverseList(struct List *L){
    int i;
    for(i=0;i<L->size;i++){
        printf("%d",L-size[i]);
    }
    printf("\n");
    
}

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
}
/*
 *  若用于比較的元素類型為字元串或某個域類型為字元串，則需要用字元串比較函數strcmp
 *  修改if條件表達式為(strcmp(L->list[i],x) == 0)
 */

8.把線性表L中第pos個元素的值修改為x的值，若修改成功傳回1，否則傳回0

int UpdatePosList(struct List *L,int pos,ElemType x){
    //若pos越界則修改失敗
    if(pos<1 || pos>L->size)
        return 0;
    L->list[pos-1] = x;
    return 1;
    
}

9.向線性表L的表頭插入元素x

/*
    操作過程
    1.檢查線性表存儲空間是否已滿，若已滿則重新配置設定更大的存儲空間
    2.移動元素位置，将下标為0的位置空出
    3.将x寫入表頭
    4.修改線性表長度，使其增1
*/


void InsertFirstList(struct List *L,ElemTypr 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++;
}


void againMalloc(struct List *L){
    //空間擴充為原來的2倍，并有p指針所指向，原内容被自動拷貝到新的存儲空間中
    ElemTpye *p=(ElemType *)realloc(L->list,2*L->MaxSize*sizeof(ElemType));  
    //若配置設定失敗
    if(!p){
        printf("存儲空間用盡！\n");
        exit(1);
    }  
    L->list = p;
    L-MaxSize = 2*L->MaxSize;
}

10.向線性表L的表尾插入元素x

void InsertLastList(struct List *L){
    if(L->size == L->MaxSize)
        //重新配置設定空間大小
        againMalloc(L);
    L->list[L->size] = x;
    l->size++;    

}

11.向線性表L中第pos個元素位置摻入元素x，若插入成功傳回1，否則傳回0

/*
    1.檢查pos是否越界
    2.檢查線性表是否已滿
    3.從表尾向前至pos-1位置，每個元素向後移動一個位置
    4.将x寫入pos個元素位置，即下表為pos-1的位置
    5.修改線性表長度，使其增1
    6.傳回1表示插入成功
*/


int InsertPosList(struct List *L, int pos, ElemType x){
    int i;
    //若pos越界則插入失敗
    if(pos<1 || pos>L->size+1)
        return 0;

    //若已滿，重新配置設定存儲空間
    if(L->size == L->MaxSize)
        againMalloc(L)

    //從表尾向前至pos-1位置，每個元素向後移動一個位置
    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，使得插入後任然有序

/*
    1.檢查表空間是否用完
    2.采用順序産找法找出x得插入位置
    3.從表尾到插入位置，元素後移
    4.把新元素插入到查找到得位置上
    5.修改線性表長度，使其增1
*/


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;
    }
    //後移元素
    for(j=L->size-1;j>=i;j--)
        L->list[j+1] = L->list[j];

    L->list[i] = x;
    l->size++;
}

13.從線性表L中删除表頭元素并傳回它，若删除失敗則停止程式運作

/*
    1.檢查線性表是否為空，若是則給出錯誤資訊并停止執行
    2.把表頭元素指派給一個臨時變量暫時存放
    3.從第二個元素到最後一個元素，依次向前移動一個位置
    4.修改線性表長度，使其減1
    5.傳回表頭元素
*/

ElemType DeleteFirstList(struct List *L){
    ElemType temp;
    int i;
    if(L->size == 0){
        printf("線性表為空，不能删除！\n");
        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中删除表尾元素x并傳回它，若删除失敗則停止程式運作

ElemType DeleteLastList(struct List *L){
    if(L->size==0){
        prinf("線性表為空，不能删除！\n");
        exit(1);
    }        
    L->size--;
    return L->list[L->size];
}

15.從線性表L中删除第pos個元素并傳回它，若删除失敗則停止程式運作

/*
    1.檢查pos的值是否有效
    2.把pos的值暫時儲存，以便删除後傳回
    3.從第pos+1個元素位置開始至表尾元素，依次前移一個位置
    4.修改線性表長度，使其減1
    5.傳回暫時儲存的第pos個元素的值

*/
ElemType DeletePosList(struct List *L,int pos){
    ElemType temp;
    int i;
    if(pos<1 || pos>L->size){
        printf("pos值越界！");
        exit(1);
    }

    //把pos的值暫時儲存，以便删除後傳回
    temp = L->list[pos-1];

    //從第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的元素
    for(j=i+1;j<L->size;j++)
        L->list[j-1] = L->list[j];
    
    L->size--;
    return 1;
}
資料結構 順序存儲結構
上一篇: 浏覽器指紋--純js拿到浏覽器指紋
下一篇: 前端裝置指紋

繼續閱讀