數(shù)據(jù)結(jié)構(gòu)教程第六課線性表的順序表示和實(shí)現(xiàn)

本課主題： 線性表的順序表示和實(shí)現(xiàn)
    教學(xué)目的： 掌握線性表的順序表示和實(shí)現(xiàn)方法
    教學(xué)重點(diǎn)： 線性表的順序表示和實(shí)現(xiàn)方法
    教學(xué)難點(diǎn)： 線性表的順序存儲(chǔ)的實(shí)現(xiàn)方法
    授課內(nèi)容：
    復(fù)習(xí)
    1、存儲(chǔ)結(jié)構(gòu)
    邏輯結(jié)構(gòu) “數(shù)據(jù)結(jié)構(gòu)”定義中的“關(guān)系”指數(shù)據(jù)間的邏輯關(guān)系，故也稱數(shù)據(jù)結(jié)構(gòu)為邏輯結(jié)構(gòu)。
    存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為物理結(jié)構(gòu)。又稱存儲(chǔ)結(jié)構(gòu)。
    順序存儲(chǔ)結(jié)構(gòu)
    鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
    2、線性表的類型定義
    一、線性表的順序表示
    用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。C語言中的數(shù)組即采用順序存儲(chǔ)方式。
    2000:0001
    2000:0003
    2000:0005
    2000:0007
    2000:0009
    2000:0011
    2000:0013
    2000:0015
    2000:0017
    ...
    2000:1001
    2000:1003
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
     a[9] 1
    2
    3
    4
    5
    6
    7
    8
    9
    假設(shè)線性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則存在如下關(guān)系：
    LOC(ai+1)=LOC(ai)+l
    LOC(ai)=LOC(a1)+(i-1)*l
    式中LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置，通常稱做線性表的起始位置或基地址。常用b表示。
    線性表的這種機(jī)內(nèi)表示稱做線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映象。
    稱順序存儲(chǔ)結(jié)構(gòu)的線性表為順序表。順序表的特點(diǎn)是以元素在計(jì)算機(jī)內(nèi)物理位置相鄰來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。
    二、順序存儲(chǔ)結(jié)構(gòu)的線性表類C語言表示：
    線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    typedef struct{
    ElemType *elem; //存儲(chǔ)空間基址
    int length; //當(dāng)前長度
    int listsize; //當(dāng)前分配的存儲(chǔ)容量以一數(shù)據(jù)元素存儲(chǔ)長度為單位
    }SqList;
    三、順序存儲(chǔ)結(jié)構(gòu)的線性表操作及C語言實(shí)現(xiàn)：
    順序表的插入與刪除操作：
    序號(hào) 數(shù)據(jù)元素 序號(hào) 數(shù)據(jù)元素 序號(hào) 數(shù)據(jù)元素 序號(hào) 數(shù)據(jù)元素
    1
    2
    3
    4
    5
    6
    7
    8
    9
     12
    13
    21
    24
    28
    30
    42
    77
    <-25
     1
    2
    3
    4
    5
    6
    7
    8
    9
     12
    13
    21
    24
    25
    28
    30
    42
    77
     1
    2
    3
    4
    5
    6
    7
    8
    9
     12
    13
    21
    24
    28
    30
    42
    77
    ->24
     1
    2
    3
    4
    5
    6
    7
    8
    9
     12
    13
    21
    28
    30
    42
    77
    插入前n=8;插入后n=9; 刪除前n=8;刪除后n=7;
    順序表的插入算法
    status ListInsert(List *L,int i,ElemType e) {
    struct STU *p,*q;
    if (i<1||i>L->length+1) return ERROR;
    q=&(L->elem[i-1]);
    for(p=&L->elem[L->length-1];p>=q;--p)
    *(p+1)=*p;
    *q=e;
    ++L->length;
    return OK;
    }/*ListInsert Before i */
    順序表的合并算法
    void MergeList(List *La,List *Lb,List *Lc) {
    ElemType *pa,*pb,*pc,*pa_last,*pb_last;
    pa=La->elem;pb=Lb->elem;
    Lc->listsize = Lc->length = La->length + Lb->length;
    pc = Lc->elem =
    (ElemType *)malloc(Lc->listsize * sizeof(ElemType));
    if(!Lc->elem) exit(OVERFLOW);
    pa_last = La->elem + La->length - 1;
    pb_last = Lb->elem + Lb->length - 1;
    while(pa<=pa_last && pb<=pb_last) {
    if(Less_EqualList(pa,pb)) *pc++=*pa++;
    else *pc++=*pb++;
    }
    while(pa<=pa_last) *pc++=*pa++;
    while(pb<=pb_last) *pc++=*pb++;
    }
    順序表的查找算法
    int LocateElem(List *La,ElemType e,int type) {
    int i;
    switch (type) {
    case EQUAL:
    for(i=0;i    if(EqualList(&La->elem[i],&e))
    return 1;
    break;
    default:
    break;
    }
    return 0;
    }
    順序表的聯(lián)合算法
    void UnionList(List *La, List *Lb) {
    int La_len,Lb_len; int i; ElemType e;
    La_len=ListLength(La); Lb_len=ListLength(Lb);
    for(i=0;i    GetElem(*Lb,i,&e);
    if(!LocateElem(La,e,EQUAL))
    ListInsert(La,++La_len,e);
    }
    }
    三、C語言源程序范例
    四、總結(jié)
    線性表的順序表示
    順序表的插入算法
    順序表的合并算法