通信原理大綜合課件軟件

1Character

00000線性表2

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

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線性表的存儲結構及其運算線性表的順序存儲結構

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

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

intV[M]；//V是數(shù)組的名字，假設數(shù)組中的數(shù)據(jù)元素是整型類型intlength；//當前長度V[1]V[n]V[M-1]6…..a2a1alength…..ai+1ai01i-1ilength-11順序表的插入運算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個元素之前插入x，M是存儲空間大小，p是指針變量，指向存儲表長的變量*/intn,j;n=*p;/*獲取表長*/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;//表長加1,有p返回到函數(shù)調用處

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個元素*/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;//表長減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");}順序表的刪除運算9特點：便于隨機存取表中的任一個數(shù)據(jù)元素，做插入、刪除時需移動大量元素。靜態(tài)分配空間，無法動態(tài)分配。表中元素個數(shù)是動態(tài)變化時，按最大空間分配。適用于需要頻繁查找操作的線性表10線性表的鏈式存儲結構

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

structLNode{intdata;structLNode*next;}listnode;線性表的鏈式存儲結構——可用C語言中的“結構指針”來描述帶頭結點的線性鏈表datanext1415①生成結點變量的標準函數(shù)

p=(ListNode*)malloc(sizeof(ListNode))；//函數(shù)malloc分配一個類型為ListNode的結點變量的空間,并將其首地址放入指針變量p中②釋放結點變量空間的標準函數(shù)free(p)；//釋放p所指的結點變量空間③結點分量的訪問

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

方法二：p-﹥data和p-﹥next④指針變量p和結點變量*p的關系指針變量p的值——結點地址結點變量*p的值——結點內容

(*p).data的值——p指針所指結點的data域的值

(*p).next的值——*p后繼結點的地址

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單鏈表的插入運算S18ai-1a1aiai+1headprvoiddeletelist(listnode*p){listnode*r;if(p->next!=NULL){r=p->next;p->next=r->next;free(r);}}單鏈表的刪除運算19線性鏈表的查找操作listnode*reseach(listnode*h,intx){listnode*p;p=h;while(p!=NULL&&p->data!=x)p=p->next;return(p);}20.循環(huán)鏈表：首尾相接的鏈表。將最后一個結點的空指針改為指向頭結點，從任一結點出發(fā)均可找到其它結點。.雙向鏈表