數(shù)據(jù)結構02-線性表.ppt

第2章線性表數(shù)據(jù)結構主講教師：祝建華華中科技大學計算機學院22.1線性表的定義2.1.1線性表的邏輯結構1.線性表：由n(n0)個數(shù)據(jù)元素(a1,a2,.,an)構成的有限序列。記作:L=(a1,a2,.,an)a1首元素an尾元素2.表的長度(表長)線性表中數(shù)據(jù)元素的數(shù)目。3.空表不含數(shù)據(jù)元素的線性表。華中科技大學計算機學院3線性表舉例:例1.字母表L1=(A,B,C,.,Z)表長26例2.姓名表L2=(李明,陳小平,王林,周愛玲)表長4例3.圖書登記表序號書名作者單價(元)數(shù)量(冊)1C語言程序設計譚浩強301002數(shù)據(jù)結構嚴蔚敏22120n數(shù)據(jù)庫系統(tǒng)原理王珊3560表長：n華中科技大學計算機學院4對于L=(a1,a2,.,ai-1,ai,ai+1,.,an)1.ai-1在ai之前,稱ai-1是ai的直接前驅(1in)2.ai+1在ai之后,稱ai+1是ai的直接后繼(1in)3.a1沒有前驅4.an沒有后繼5.ai(1in)有且僅有一個直接前驅和一個直接后繼線性表的特征:華中科技大學計算機學院52.1.2抽象數(shù)據(jù)類型線性表的定義ADJList數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,.n,n=0數(shù)據(jù)關系：R1=|ai-1,aiD,i=2,.n基本操作：1.IniList(&L)/構造空表L。2.LengthList(L)/求表L的長度3.GetElem(L,i,&e)/取元素ai,由e返回ai4.PriorElem(L,ce,&pre_e)/求ce的前驅,由pre_e返回5.InsertElem(&L,i,e)/在元素ai之前插入新元素e6.DeleteElem(&L,i)/刪除第i個元素7.EmptyList(L)/判斷L是否為空表8.ClearList(&L)/置L為空表.ADJList華中科技大學計算機學院6說明1.刪除表L中第i個數(shù)據(jù)元素(1=i=n),記作:DeleteElem(&L,i)L=(a1,a2,.,ai-1,ai,ai+1,.,an)指定序號i,刪除aiL=(a1,a2,.,ai-1,ai+1,.,an)2.指定元素值x,刪除表L中的值為x的元素,記作:DeleteElem(&L,x)；3.在元素ai之前插入新元素e(1=i=n+1)L=(a1,a2,.,ai-1,ai,.,an)插入eL=(a1,a2,.,ai-1,e,ai,.,an)4.查找-確定元素值(或數(shù)據(jù)項的值)為e的元素。給定:L=(a1,a2,.,ai,.,an)和元素e若有一個ai=e，則稱“查找成功”,i=1,2,.,n否則，稱“查找失敗”。華中科技大學計算機學院75.排序-按元素值或某個數(shù)據(jù)項值的遞增（或遞減）次序重新排列表中各元素的位置。例.排序前:L=(90,60,80,10,20,30)排序后:L=(10,20,30,60,80,90)L變?yōu)橛行虮?.將表La和表Lb合并為表Lc例.設有序表：La=(2,14,20,45,80)Lb=(8,10,19,20,22,85,90)合并為表Lc=(2,8,10,14,19,20,20,22,45,80,85,90)7.將表La復制為表LbLa=(2,14,20,45,80)Lb=(2,14,20,45,80)華中科技大學計算機學院8可利用現(xiàn)有操作組成更復雜的操作：例：將線性表Lb中的，且不在線性表La數(shù)據(jù)元素合并到線性La中。voidunion(List&La,List&Lb)La_len=List_length(La)；/求線性表La的長度Lb_len=List_length(Lb)；/求線性表Lb的長度for(i=1；i=Lb_len；i+)GetElem(Lb,i,e)；/取Lb的的第i個數(shù)據(jù)元素賦給e/即依次取出Lb中的所有元素if(!LocateElem(La,e,equal)/判斷e在La中是否存在ListInsert(La,+La_len,e)；/不存在則插入華中科技大學計算機學院92.2線性表的順序表示（順序存儲結構）2.2.1.順序分配將線性表中的數(shù)據(jù)元素依次存放到計算機存儲器中一組地址連續(xù)的存儲單元中,這種分配方式稱為順序分配或順序映像。由此得到的存儲結構稱為順序存儲結構或向量(一維數(shù)組）。例.線性表：a=(30,40,10,55,24,80,66)內(nèi)存狀態(tài)C語言中靜態(tài)一維數(shù)組