久久草xxxxx欧美,日韩福利一区,亚洲综合9

引言

線性表是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)，一個線性表是n個數(shù)據(jù)元素的有限序列。它的數(shù)據(jù)元素ElemType可以有不同的含義，可以是一個數(shù)，也可以是一本書，具體取決于ElemType實(shí)際定義。線性表中元素的個數(shù)n(>=0)定義為線性表的長度，n=0時稱為空表。線性表一個相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，對線性表不僅可以進(jìn)行訪問，還可以進(jìn)行插入和刪除等操作。

順序表示

定義：線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，這種表示稱為線性表的順序存儲結(jié)構(gòu)。通常稱這種線性表為順序表。它的特點(diǎn)是：表中相鄰的元素a_i和a_i+1在計(jì)算機(jī)內(nèi)的物理存儲位置也相鄰。
優(yōu)點(diǎn)：只要確定了存儲順序表的起始位置，表中任一元素均可隨機(jī)存取。
缺點(diǎn)：在作插入或刪除操作時，需移動大量元素。

具體實(shí)現(xiàn)

元素定義

線性表中元素類型ElemType需根據(jù)實(shí)際需要來定義，本文定義為int類型。

typedef int ElemType;

ElemType也可以定義為結(jié)構(gòu)體，例如在后續(xù)講多項(xiàng)式的時候，ElemType定義為：

typedef  struct {
         float coef;
         int exp;
} ElemType;

順序表定義

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
        ElemType *base;
        int length;
        int listsize;
}SqList;

在上述定義中，數(shù)組elem指示順序表的基地址，length指示順序表的當(dāng)前長度。listsize指示順序表當(dāng)前分配的存儲空間大小，一旦因插入導(dǎo)致空間不足，可進(jìn)行再分配，為順序表增加一個LISTINCREMENT個數(shù)據(jù)元素的空間。

基本操作

#include <stdio.h> 
#include <stdlib.h>
#define LIST_INIT_SIZE 100      //列表存儲空間的初始分配量
#define LIST_INCREMENT 10       //列表存儲空間分配增量
#define TRUE 1  //真值
#define FALSE 0 //假值
#define SUCCESS 1        //成功標(biāo)識
#define FAILURE -1      //失敗標(biāo)識

typedef int ElemType;    // 基本數(shù)據(jù)元素

//ElemType相關(guān)函數(shù)
//比較, 需根據(jù)elem類型實(shí)時更改, 這里ElemType定義為為int類型
int compare(ElemType e1, ElemType e2){
        if(e1 == e2) return 0;
        else if(e1 > e2) return 1;
        else if(e1 < e2) return -1;    
}

//visit ElemType元素
int visit(ElemType e){ 
        printf("%d ", e); 
        return SUCCESS;
}

typedef struct{
        ElemType *elem;
        int length;     //當(dāng)前長度
        int listsize;   //當(dāng)前分配的存儲容量
}SqList;

int InitList_Sq(SqList *L){
        // 構(gòu)造一個空的線性表L
        L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
        if (!L->elem) exit(-1);         //容量分配失敗
        L->length = 0;
        L->listsize = LIST_INIT_SIZE;
        return SUCCESS; 
} 

int ListInsert_Sq(SqList *L, int i, ElemType e){ 
        // 在第i個位置之前插入e
        // i的有效位置為1<=i<=L->length
        if(i<1 || i>L->length+1) return FAILURE; 
        if(L->length >= L->listsize){   //空間已滿
                ElemType *elem = (ElemType *)realloc(L->elem, 
                                LIST_INCREMENT*sizeof(ElemType));
                if(!elem){
                        printf("內(nèi)存分配失敗，即將退出\n");
                        exit(-1);       //重新分配失敗
                }   
                L->elem = elem;
                L->listsize += LIST_INCREMENT;
        }   
        ElemType *p = L->elem + i - 1;
        ElemType *q = L->elem + L->length - 1;
        for(; q>=p; --q) *(q+1) = *q; 
        *p = e;
        L->length++;
        return SUCCESS;    
}

int ListDelete_Sq(SqList *L, int i, ElemType *e){
        // 刪除順序表中第i位置元素
        if (i < 1 || i > L->length) return FAILURE; 
        ElemType *p = L->elem + i-1;    //被刪除元素的位置      
        *e = *p;        //返回被刪除元素        
        ElemType *q = L->elem + L->length - 1;
        for(p;p<q; ++p) *p = *(p+1);
        L->length--;
        return SUCCESS;
}

int LocateElem_Sq(SqList L, ElemType e, int (*compare)(ElemType, ElemType)){
        // 返回L中第一個與e滿足compare關(guān)系為0的元素的位序，如無則返回-1
        int i = 1;
        ElemType *p = L.elem;
        while(i <= L.length && compare(*p++, e) != 0) i++;
        if (i<= L.length) return i;
        return FAILURE;
}

void MergeList_Sq(SqList La, SqList Lb, SqList *Lc){
        //已知La和Lb為非遞減的順序表序列
        //歸并La和Lb為新的順序表Lc，Lc中元素非遞減排列
        ElemType *pa = La.elem, *pb = Lb.elem;

        Lc->listsize = Lc->length = La.length + Lb.length;
        ElemType *pc = Lc->elem = (ElemType *)malloc(Lc->listsize *
                        sizeof(ElemType));
        if(!Lc->elem) exit(-1); //存儲分配失敗
        ElemType *pa_last = La.elem + La.length -1, *pb_last = Lb.elem +
                Lb.length -1;
        while(pa <= pa_last && pb <= pb_last){  //歸并
                if (*pa <= *pb) *pc++ = *pa++;
                else *pc++ = *pb++;
        }
        //插入剩余元素
        while(pa <= pa_last) *pc++ = *pa++;
        while(pb <= pb_last) *pc++ = *pb++;
}

int ListEmpty_Sq(SqList L){
        //判斷L是否為空
        if(L.length == 0){
                return TRUE;
        } else {
                return FALSE;
        }
}

int ListLength_Sq(SqList L){
        //如果L為順序表，返回L長度
        if(L.elem != NULL){
                return L.length;
        } else {
                return -1;
        }
}

int PriorElem_Sq(SqList L, ElemType cur_e, ElemType *pre_e){
        //若cur_e為L中元素，且不是第一個，則用pre_e返回它的前驅(qū)
        ElemType *p = L.elem, *q = L.elem + L.length - 1;
        while(p < q){
                if(*(p+1) == cur_e){
                        *pre_e = *p;
                        return SUCCESS;
                }
                p++;
        }
        return FAILURE;
}

int NextElem_Sq(SqList L, ElemType cur_e, ElemType *next_e){
        //若cur_e是L中數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼元素
        int pos = LocateElem_Sq(L, cur_e, compare);
        if(pos >= L.length || pos < 1) return FAILURE;  //查找失敗
        int i = 1;
        ElemType *p = L.elem;
        while(i <= pos) {
                p++;
                i++;
        }
        *next_e = *p;
        return SUCCESS;
}

int ListTraverse_Sq(SqList L, int(*visit)(ElemType)){
        ElemType *p = L.elem;   // 起始位置
        ElemType *p_last = L.elem + L.length - 1;       // 結(jié)束位置
        while(p <= p_last){
                if(!(visit(*p++))) return FAILURE;
        }
        return SUCCESS;
}

void DestroyList_Sq(SqList *L){
        //銷毀線性表L
        if(L->elem != NULL){
                free(L->elem); //釋放內(nèi)存空間
                L->elem = NULL;
                L->length = 0;
                L->listsize = 0;
        }
}

void ClearList_Sq(SqList *L){
        if(L->elem != NULL){
                L->length = 0;  //是否為空判斷依據(jù)
        }
}

int main(){
        ElemType a[10] = {2,4,5,6,7,8,9,3,5,7};
        // declare L
        SqList *L;
        // init
        InitList_Sq(L);
        printf("\nInit list *************\n");
        printf("Init List, L.length: %d, L.size: %d\n", L->length, L->listsize);
        // insert element 
        printf("\nInsert element ***********\n");
        int i;
        for(i=1;i<=10;i++){
                if(!ListInsert_Sq(L, i, a[i-1])){
                        printf("insert failure!");
                }
        }
        printf("Insert List, now L.length: %d, L.size: %d\n", L->length,
                        L->listsize);
        // traverse
        printf("\ntraverse ********************\n");
        printf("now elems: ");
        ListTraverse_Sq(*L, visit);
        printf("\n");
        // delete
        printf("\ndelete element **********************\n");
        ElemType e;
        if(ListDelete_Sq(L, 5, &e) > 0){
                printf("Success delete value at 5 index: %d\n", e);
        } else {
                printf("delete value at 5 index failure\n");
        }
        // another delete
        ElemType f;
        if(ListDelete_Sq(L, 11, &f) > 0){
                printf("Success delete value at 11 index: %d", f);
        } else {
                printf("delete value at 11 index failure");
        }
        printf("\nnow elem: ");
        ListTraverse_Sq(*L, visit);
        printf("\nAfter delete: length: %d, size: %d\n", L->length,
                        L->listsize);
        // search elem
        printf("\nSearch elem **********************\n");
        int pos1 = LocateElem_Sq(*L, 3, compare);
        int pos2 = LocateElem_Sq(*L, 11, compare);
        if(pos1 >= 0){
                printf("success find 3 at index: %d\n", pos1);
        } else {
                printf("failure find 3 at list L!");
        }
        if(pos2 >= 0){
                printf("success find 11 at index: %d\n", pos2);
        } else {
                printf("failure find 11 in list L!\n");
        }
        // merge list
        printf("\nMerge Sort List*******************\n");
        int b[] = {1, 4, 5};
        int c[] = {5, 6, 9, 12};
        SqList L1, L2, L3;
        InitList_Sq(&L1);
        InitList_Sq(&L2);
        InitList_Sq(&L3);
        for(i=0;i<3;i++){
                ListInsert_Sq(&L1,i+1,b[i]);
        }
        for(i=0;i<4;i++){
                ListInsert_Sq(&L2, i+1, c[i]);
        }
        printf("Start Merge*********\n");
        MergeList_Sq(L1, L2, &L3);
        printf("L1 elem: ");
        ListTraverse_Sq(L1, visit);
        printf("\nL2 elem: ");
        ListTraverse_Sq(L2, visit);
        printf("\nL3 elem: ");
        ListTraverse_Sq(L3, visit);
        // get length
        printf("\nL3 length is: %d\n", ListLength_Sq(L3));
        // is empty
        if(ListEmpty_Sq(L3)) printf("L3 is empty!\n");
        else printf("L3 is not empty!\n");
        // get prior elem
        ElemType pre_e, next_e;
        int p1, p2, p3, p4;
        p1 = PriorElem_Sq(L3, 1 , &pre_e);
        if(p1 < 0) printf("pre find 1 failure in L3!\n");
        p2 = PriorElem_Sq(L3, 12, &pre_e);
        if(p2 >= 0) printf("prior 12 in L3 is %d\n", pre_e);
        p3 = NextElem_Sq(L3, 1, &next_e);
        if(p3 >= 0) printf("next 1 in L3 is %d\n", next_e);
        p4 = NextElem_Sq(L3, 12, &next_e);
        if(p4 < 0) printf("next find 12 in L3 failure!\n");
        // clear list
        printf("\n\nClear List **********************\n");
        ClearList_Sq(L);
        printf("L length: %d, L size: %d, L elem: %p\n", L->length, L->listsize,
                        L->elem);
        // destroy list
        printf("\nDestroy List **********************\n");
        DestroyList_Sq(L);
        printf("L length: %d, L size: %d, L elem: %p\n", L->length, L->listsize,
                        L->elem);
        if(L->elem){
                printf("L elem: %p\n", L->elem);
        } else {
                printf("L elem is NULL\n");
        }
}

運(yùn)行結(jié)果

*************** Init list *************
Init List, L.length: 0, L.size: 100

*************** Insert element ***********
Insert List, now L.length: 10, L.size: 100

************** traverse ********************
now elems: 2 4 5 6 7 8 9 3 5 7 

************* delete element **********************
Success delete value at 5 index: 7
delete value at 11 index failure
now elem: 2 4 5 6 8 9 3 5 7 
After delete: length: 9, size: 100

************ Search elem **********************
success find 3 at index: 7
failure find 11 in list L!

*********** Merge Sort List*******************
Start Merge*********
L1 elem: 1 4 5 
L2 elem: 5 6 9 12 
L3 elem: 1 4 5 5 6 9 12 
L3 length is: 7
L3 is not empty!
pre find 1 failure in L3!
prior 12 in L3 is 9
next 1 in L3 is 4
next find 12 in L3 failure!


*********** Clear List **********************
L length: 0, L size: 100, L elem: 0x232d010

*********** Destroy List **********************
L length: 0, L size: 0, L elem: (nil)
L elem is NULL

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

線性表（一）順序表示與實(shí)現(xiàn)

線性表（一）順序表示與實(shí)現(xiàn)

引言

順序表示

具體實(shí)現(xiàn)

元素定義

順序表定義

基本操作

運(yùn)行結(jié)果

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

線性表（一）順序表示與實(shí)現(xiàn)

引言

順序表示

具體實(shí)現(xiàn)

元素定義

順序表定義

基本操作

運(yùn)行結(jié)果

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av