通信原理大綜合課件軟件

1Character

00000線性表2

2．2線性表2.2.1線性表的基本概念線性表是n個(gè)元素的有限序列，它們之間的關(guān)系可以排成一個(gè)線性序列：a1，a2，...，ai，...，an線性結(jié)構(gòu)中各數(shù)據(jù)成員之間的線性關(guān)系:有直接前驅(qū)和直接后繼(除最前、最后一個(gè)元素)3在線性表上常用的運(yùn)算有：初始化求長(zhǎng)度取元素修改前插刪除檢索排序4設(shè)線性表的基地址為：LOC(a1),ai的存儲(chǔ)地址為：

LOC(ai)=LOC(a1)＋(i-1)*k1<=i<=na1a2aian……Loc(a1)Loc(a1)+kLoc(a1)+(i-1)*kLoc(a1)+(n-1)*k

2.2.2線性表的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算線性表的順序存儲(chǔ)結(jié)構(gòu)

把數(shù)據(jù)元素按照邏輯順序依次存放到一組連續(xù)的存儲(chǔ)單元中。5元素1元素2……..元素n……..01n-1V[0]

線性表的順序存儲(chǔ)結(jié)構(gòu)——可用C語(yǔ)言中的一維數(shù)組來描述.#defineM100//定義M為常數(shù)100，M的值作為數(shù)組的最大容量

intV[M]；//V是數(shù)組的名字，假設(shè)數(shù)組中的數(shù)據(jù)元素是整型類型intlength；//當(dāng)前長(zhǎng)度V[1]V[n]V[M-1]6…..a2a1alength…..ai+1ai01i-1ilength-11順序表的插入運(yùn)算ai-1…..a2a1alength

…ai+1ai

xP（P+1）q

ai-1…..

a2

a1

ai

ai+1

…alength

alength

…

…ai+1

ai

x7intinsq(inti,intx,intV[],intM,int*p）{/*在線性表中V中第i個(gè)元素之前插入x，M是存儲(chǔ)空間大小，p是指針變量，指向存儲(chǔ)表長(zhǎng)的變量*/intn,j;n=*p;/*獲取表長(zhǎng)*/if(n==M){printf(“overflow\n”);return(0);}if（i<1‖i>n+1）

{printf(“Itiserror\n”);return(0);}//i值不合法else{for(j=n;j>=i;j--)V[j]=V[j-1];V[j]=X;*p=++n;//表長(zhǎng)加1,有p返回到函數(shù)調(diào)用處

return(1);}}

voidmain(){ intM=10,n=4; intresult,k; staticintV[10]={3,5,7,10};

result=insq(2,4,V,M,&n); if(result==1){printf("success\n"); for(k=0;k<n;k++)printf("%d",V[k]);} elseprintf("failure");}8intdelsq（inti,intV[],int*p){/*在線性表中V中刪除第i個(gè)元素*/intn,j;if（i<1‖i>n）

{printf(“Thiselementisnotinthelist\n”);return(0);}//i值不合法else

{for(j=i;j<n;j++)V[j-1]=V[j];*p=--n;//表長(zhǎng)減1return(1);}}voidmain(){ intM=10,n=4; intresult,k; staticintV[10]={3,5,7,10};

result=delsq(2,V,&n); if(result==1){printf("success\n"); for(k=0;k<n;k++)printf("%d",V[k]);} elseprintf("failure");}順序表的刪除運(yùn)算9特點(diǎn)：便于隨機(jī)存取表中的任一個(gè)數(shù)據(jù)元素，做插入、刪除時(shí)需移動(dòng)大量元素。靜態(tài)分配空間，無法動(dòng)態(tài)分配。表中元素個(gè)數(shù)是動(dòng)態(tài)變化時(shí)，按最大空間分配。適用于需要頻繁查找操作的線性表10線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。它是動(dòng)態(tài)地進(jìn)行存鏈表儲(chǔ)分配的一種結(jié)構(gòu)。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的含義是指邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存中的物理存儲(chǔ)空間不一定相鄰。每個(gè)數(shù)據(jù)元素對(duì)應(yīng)內(nèi)存一個(gè)存儲(chǔ)空間，叫存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。1112將線性表的元素放到一個(gè)具有頭指針的鏈表中，鏈表中每個(gè)結(jié)點(diǎn)包含數(shù)據(jù)域和指針域。特點(diǎn)：插入、刪除靈活方便，不需要移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可。datanextdata域--存放結(jié)點(diǎn)值的數(shù)據(jù)域next域--存放結(jié)點(diǎn)的直接后繼的地址（位置）的指針域（鏈域）13a1a2an∧a3L…..typedef

structLNode{intdata;structLNode*next;}listnode;線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——可用C語(yǔ)言中的“結(jié)構(gòu)指針”來描述帶頭結(jié)點(diǎn)的線性鏈表datanext1415①生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)

p=(ListNode*)malloc(sizeof(ListNode))；//函數(shù)malloc分配一個(gè)類型為L(zhǎng)istNode的結(jié)點(diǎn)變量的空間,并將其首地址放入指針變量p中②釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)free(p)；//釋放p所指的結(jié)點(diǎn)變量空間③結(jié)點(diǎn)分量的訪問

利用結(jié)點(diǎn)變量的名字*p訪問結(jié)點(diǎn)分量方法一：(*p).data和(*p).next

方法二：p-﹥data和p-﹥next④指針變量p和結(jié)點(diǎn)變量*p的關(guān)系指針變量p的值——結(jié)點(diǎn)地址結(jié)點(diǎn)變量*p的值——結(jié)點(diǎn)內(nèi)容

(*p).data的值——p指針?biāo)附Y(jié)點(diǎn)的data域的值

(*p).next的值——*p后繼結(jié)點(diǎn)的地址

1617voidinsertlist(listnode*L,charx){listnode*p,*s;p=L;if(p==NULL)printf("positionerror");s=(listnode*)malloc(sizeof(listnode));s->data=x;s->next=p->next;p->next=s;}babaxPP5單鏈表的插入運(yùn)算S18ai-1a1aiai+1headprvoiddeletelist(listnode*p){listnode*r;if(p->next!=NULL){r=p->next;p->next=r->next;free(r);}}單鏈表的刪除運(yùn)算19線性鏈表的查找操作listnode*reseach(listnode*h,intx){listnode*p;p=h;while(p!=NULL&&p->data!=x)p=p->next;return(p);}20.循環(huán)鏈表：首尾相接的鏈表。將最后一個(gè)結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn)，從任一結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn)。.雙向鏈表