數(shù)據(jù)結(jié)構(gòu)教程第五課線性表的類型定義

教學(xué)目的： 掌握線性表的概念和類型定義
    教學(xué)重點(diǎn)： 線性表的類型定義
    教學(xué)難點(diǎn)： 線性表的類型定義
    授課內(nèi)容：
    復(fù)習(xí)：數(shù)據(jù)結(jié)構(gòu)的種類
    線性結(jié)構(gòu)的特點(diǎn)：
    在數(shù)據(jù)元素的非空有限集中，
    （1）存在的一個被稱做“第一個”的數(shù)據(jù)元素；
    （2）存在的一個被稱做“后一個”的數(shù)據(jù)元素；
    （3）除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)；
    （4）除后一個之外，集合中每個數(shù)據(jù)元素均只有一個后繼。
    二、線性表的類型定義
    1、抽象數(shù)據(jù)類型線性表的定義如下：
    ADT List{
    數(shù)據(jù)對象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
    數(shù)據(jù)關(guān)系: R1={| ai-1,ai(- D,i=2,...,n}
    基本操作：
    InitList(&L)
    DestroyList(&L)
    ClearList(&L)
    ListEmpty(L)
    ListLength(L)
    GetElem(L,i,&e)
    LocateElem(L,e,compare())
    PriorElem(L,cur_e,&pre_e)
    NextElem(L,cur_e,&next_e)
    ListInsert(&L,i,e)
    ListDelete(&L,i,&e)
    ListTraverse(L,visit())
    union(List &La,List &Lb)
    }ADT List
    2、部分操作的類C實(shí)現(xiàn)：
    InitList(&L)
    {L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem)exit(OVERFLOW);
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
    }//InitList
    GetElem(L,i,&e)
    {*e=L.lem[i]
    }//GetElem
    ListInsert(List &L,int i,ElemType e)
    {if(i<1||i>L.length+) 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
    void union(List &La,List &Lb)
    {La_len=ListLength(La);Lb_len=ListLength(Lb);
    for(i=1;i<=Lb_len;i++){
    GetElem(Lb,i,e);
    if(!LocateElem(La,e,equal))
    ListInsert(La,++La_len,e);
    }//union
    void MergeList(List La,List Lb,List &Lc)
    {InitList(Lc);
    i=j=1;k=0;
    La_len=ListLength(La);Lb_len=ListLength(Lb);
    while((i<=La_len)&&(j    GetElem(La,i,ai);GetElem(Lb,j,bj);
    if(ai<=bj){ListInsert(Lc,++k,ai);++i;}
    else{ListInsert(Lc,++k,bj);++j;}
    }
    while(k<=La_len){
    GetElem(La,i++,ai);ListInsert(Lc,++k,ai);
    }
    while(j<=Lb_len){
    GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);
    }
    }//MergeList