《數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：線性表順序表.ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：線性表順序表.ppt（36頁珍藏版）》請在匯文網(wǎng)上搜索。

1、線 性 表程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容：邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的客觀聯(lián)系 存儲結(jié)構(gòu)：數(shù)據(jù)在計算機(jī)內(nèi)部的存儲方法 算法研究數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)：線性表，棧，隊列非線性結(jié)構(gòu)：樹，圖 在各種程序設(shè)計與軟件開發(fā)中都要涉及到對數(shù)據(jù)的組織、存儲、管理和處理在環(huán)境領(lǐng)域：不同環(huán)境監(jiān)測點的監(jiān)測指標(biāo)統(tǒng)計在土地領(lǐng)域：不同宗地的屬性在測繪領(lǐng)域：外業(yè)測繪信息的存儲，各測點三維坐 標(biāo)的存儲 最常見的數(shù)據(jù)組織方式：表格形式的數(shù)據(jù)編號名稱SO2含量 水質(zhì)指標(biāo)懸浮物指標(biāo)宗地號周長面積使用者土地等級點號等級XYH學(xué)號姓名性別籍貫?zāi)挲g成績2.1 線性表的基本概念和運(yùn)算線性表的基本概念和運(yùn)算2.1.1 邏輯結(jié)

2、構(gòu)定義邏輯結(jié)構(gòu)定義定義定義：線性：線性表是由n（n0）個數(shù)據(jù)元素數(shù)據(jù)元素a1,a2,，an構(gòu)成的有限序列有限序列。n為表的長度，n=0時稱為空表。非空的線性表（n0）記作（a1,a2,，an）。數(shù)據(jù)元素可以有不同的含義，但同一線性表中的元素必須具有相同的特性。9119遼寧男李鐵0220年齡87北京男楊晨01成績籍貫性別姓名學(xué)號9520上海男祁宏30在非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2(或沒有后繼)；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨a n-1(或沒有前趨)；其余的內(nèi)部結(jié)點ai(2in-1)都有且僅有一個直接前趨a i-1和一

3、個直接后繼a i+1。2.1.2 線性表的線性表的ADT表示表示ADT List數(shù)據(jù)對象：L=ai|ai元素集合，i=1，2，n，n0數(shù)據(jù)關(guān)系：R=ai-1，ai|ai-1，ai元素集合，i=1，2，n基本操作：構(gòu)造空表initList(&L)銷毀線性表destroyList(&L)清空表 clearList(&L)求長度 listLength(L)取結(jié)點 getElem(L,index,&e)定位 locateElem(L,x)插入 insertElem(&L,index,e)刪除deleteElem(&L,index,&e)取直接前趨 priorElem(L,cur_e,&prior_e)

4、取直接后繼 nextElem(L,cur_e,&next_e)2.1.3 線性表的運(yùn)算線性表的運(yùn)算清空表 clearList(&L)學(xué)號成績clearList(list);取結(jié)點 getElem(L,index,&e)getElem(list,2,&e)序號成績017802900384定位 locateElem(L,x)locateElem(list,84)=3學(xué)號成績017802900384 插入 insertElem(&L,index,e)：在index位置插入值為e的元素 insertElem(list,3,87)學(xué)號成績017802900384308390027801成績學(xué)號83318

5、4048703 刪除deleteElem(&L,index)deleteElem(list,3)學(xué)號 成績017802900384298390027801成績學(xué)號83308404870390027801成績學(xué)號83308404 取直接前趨 priorElem(L,cur_e,&prior_e)取直接后繼 nextElem(L,cur_e,&next_e)90027801成績學(xué)號833084048703PRIOR(L,87)NEXT(L,87)對線性表的所有復(fù)雜操作都可以由以上操作完成對線性表的所有復(fù)雜操作都可以由以上操作完成e.g 清除線性表L中多余的重復(fù)結(jié)點 從i=1開始，每次取第i個元素g

6、etElem(L,i,&e)對第i個元素后的所有元素進(jìn)行比較，若值相同則刪除 判斷完后將i+，繼續(xù)執(zhí)行，直到i=listLengh(L)Purge(Linear_List list)int i=1,j,x,y;while(ilistLength(list)getElem(list,i,&x);j=i+1;while(j”，不用“.”說明：用結(jié)構(gòu)體類型定義指針 struct student stu-1;struct student*p;p=&stu-1;以下三種形式等價：(*p).成員名 p-成員名 結(jié)構(gòu)體變量.成員名如(*p).age,p-age,stu-1.age等價 void clearL

7、ist(sequencelist*pList)pList-length=0;void initList(sequencelist*pList)pList-length=0;2 插入運(yùn)算序號成績017802900384308390027801成績序號833184048703a1a2ai-1aian-1an移動后a1a2ai-1aiai+1an插入前插入x下標(biāo)0 1i-2i-1in-1lasta1a2ai-1xaian-1an插入后lastinsertElem(L,i,x)1 if(ilength+1)return wrong;2 for j=n to index step(-1)3 Lj+1=L

8、j4end5Li=x6 length=length+17 returna1a2ai-1aian-1an移動后a1a2ai-1aiai+1an插入前插入x下標(biāo)0 1i-2i-1in-1lastint insertElem(sequencelist*pList,int index,datatype x)if(pList-length=maxsize)return 0;/溢出 if(index pList-length+1)/位置不合法 return 0;for(int i=pList-length ;i=index;i-)pList-datai=pList-datai-1;/元素后移 pList-

9、dataindex-1=x;/把值寫入index位置 +pList-length;/修改length return 1;3 刪除運(yùn)算序號 成績017802900384298390027801成績序號83308404870390027801成績序號83308404a1a2ai-1ai+1an刪除a1a2ai-1aiai+1an刪除前刪除x下標(biāo)0 1i-2i-1in-1lasta1a2ai-1ai+1ai+2an刪除后last算法描述：deleteElem(L,i)1 if(i length)return wrong;2 for j=i to n-13 Lj=Lj+14 end(j)5 lengt

10、h=length-1int deleteElem(sequencelist*pList,int index)if(index pList-length)return 0;for(int i=index;i length;i+)pList-datai-1=pList-datai;/元素前移 -pList-length;/修改length return 1;3 算法分析時間主要用于移動元素，與表長和操作位置有關(guān)。算法的時間復(fù)雜度為O(n)本節(jié)重點：1 線性表的定義及特點；2 順序表的存儲方式及算法實現(xiàn)，尤其是插入和刪除的實現(xiàn)。作業(yè)：作業(yè)：1.對順序表就地逆置；2.試寫出一個高效算法，把順序表中的所有重復(fù)元素移到表尾，返回表尾中第一個重復(fù)元素的位置（如沒有重復(fù)元素，則返回 最后一個元素位置+1）。