計算機軟件基礎(自考本科)(1.8)

計算機軟件基礎(自考本科)(1.8)一、線性表的概念1.線性表的邏輯結(jié)構(gòu)（1）線性表：是由n（n≥0）個數(shù)據(jù)節(jié)點a0，a1,…，an-1組成的有限序列。（2）線性表的邏輯結(jié)構(gòu)特征：①對于非空線性表：有且僅有一個開始節(jié)點，該節(jié)點有且僅有一個直接的后繼；有且只有一個終結(jié)節(jié)點，該節(jié)點有且僅有一個直接的前驅(qū)；其余內(nèi)部節(jié)點有且僅有一個直接前驅(qū)和一個直接后繼。一、線性表的概念（2）線性表的邏輯結(jié)構(gòu)特征：②同一個線性表中的數(shù)據(jù)節(jié)點具有相同的屬性。③線性表長度：線性表中數(shù)據(jù)節(jié)點的個數(shù)。2.線性表的存儲結(jié)構(gòu)（1）順序存儲結(jié)構(gòu)：順序表結(jié)構(gòu)；（2）鏈式存儲結(jié)構(gòu)：鏈表結(jié)構(gòu)；二、順序表1.順序表（1）順序表：把線性表中的數(shù)據(jù)節(jié)點按其邏輯順序依次存放到計算機內(nèi)存中的一連續(xù)空間中，將這一連續(xù)空間稱為順序表。（2）順序表中數(shù)據(jù)節(jié)點地址的計算Loc(ai)=loc(a0)+i*d(0≤i≤n-1)二、順序表1.順序表（3）順序表C語言描述：structsequenlist{datatypea[listsize];//表示線性表有（a0，a1，...，an-1）intlength;//length表示線性表的實際長度};二、順序表2.順序表的基本運算——查找structsequenlist/*構(gòu)建sequenlist型*/{datatypedata[listsize];intlength;};structsequenlistL;/*定義sequenlist變量L*/intfind(structsequenlistL,datatypex)/*定義find函數(shù)*/{inti=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length)return(i);/*如果找到了，則返回數(shù)值i*/elsereturn(0);/*如果找不到，則返回數(shù)值0*/}二、順序表一個完整的查找程序：#include<stdio.h>#definelistsize50structsequenlist/*構(gòu)建sequenlist型*/{ intdata[listsize]; intlength;};structsequenlistL;/*定義sequenlist變量L*/intfind(structsequenlistL,intx)/*定義find函數(shù)*/{ inti=0; while(i<L.length&&L.data[i]!=x) i++; if(i<L.length)return(i); elsereturn(0);}二、順序表一個完整的查找程序（續(xù)）：main(){ inti,j,y; structsequenlista; scanf("%d",&a.length);/*輸入實際表長*/ scanf("%d",&j);/*輸入要查找的數(shù)據(jù)*/ for(i=0;i<a.length;i++) scanf("%d",&a.data[i]); y=find(a,j); if(y)printf("%d\n",y); elseprintf("nofind");}二、順序表順序表查找運算的結(jié)論：（1）查找成功的平均查找次數(shù)為：(表長+1)/2。（2）時間復雜度：表長越長，查找所消耗時間越多，所以，時間復雜度與n有關，即：T(n)=O(n)。二、順序表3.順序表的基本運算——插入step1:判斷表是否滿？如果已滿，則輸出“表滿”；否則進行第二步；step2:判斷要插入的位置是否在表內(nèi)？如果不在，則輸出“位置不對”；否則進行第三步；step3:從第n-1個節(jié)點到第i個節(jié)點全部后移1位；step5:將順序表的表長加1；step4:在順序表的第i個位置插入x；二、順序表插入運算的類C語言算法：voidinsert(structsequenlistL,datatypex,inti)/*定義insert函數(shù)*/{ intj; if(L.length>=listsze)printf("overflow\n"); elseif((i<0)||(i>L.length))printf("positionisnocorrect\n"); else { for(j=L.length-1;j>=i;j--) { L.data[j+1]=L.data[j]; } L.data[i]=x; L.length++; }}二、順序表一個完整的插入運算程序#include<stdio.h>#definelistsze10structsequenlist/*構(gòu)建sequenlist型*/{ intdata[listsze]; intlength;};structsequenlistL;二、順序表一個完整的插入運算程序（續(xù)）voidinsert(structsequenlistL,intx,inti)/*定義insert函數(shù)*/{ intj; if(L.length>=listsze)printf("overflow\n"); elseif((i<0)||(i>L.length))printf("positionisnocorrect\n"); else { for(j=L.length-1;j>=i;j--) { L.data[j+1]=L.data[j]; } L.data[i]=x; L.length++; for(j=0;j<L.length;j++) printf("%d,",L.data[j]); }}二、順序表一個完整的插入運算程序（續(xù)）main(){ inti,j,y; structsequenlista; scanf("%d",&a.length);/*輸入實際表長*/ scanf("%d",&y);/*輸入要插入的數(shù)據(jù)*/ scanf("%d",&j);/*輸入要插入數(shù)據(jù)的位置*/ for(i=0;i<a.length;i++) scanf("%d",&a.data[i]); insert(a,y,j);}二、順序表順序表插入運算的結(jié)論：（1）在線性表中插入一個數(shù)據(jù)節(jié)點需要移動順序表的一半節(jié)點，即：n/2。（2）時間復雜度：插入運算的時間復雜度與n有關，即：T(n)=O(n)。二、順序表3.順序表的基本運算——刪除step1:判斷表是否為空？如果為空，則輸出“無法刪除”；否則進行第二步；step2:判斷要刪除的位置是否在表內(nèi)？如果不在，則輸出“位置不對”；否則進行第三步；step3:從第i+1個節(jié)點到第n-1個節(jié)點全部前移1位（采用覆蓋的形式刪除）；step4:將順序表的表長減去1；二、順序表刪除運算的類C語言算法：voiddelete(structsequenlistL,inti)/*定義delete函數(shù)*/{intj;if(L.length==0)printf("Emptylist,cannotdelete!\n");elseif((i<0)||(i>=L.length))printf("positionisnocorrect\n");else { for(j=i+1;j<L.length;j++) { L.data[j-1]=L.data[j]; } L.length--;}二、順序表一個完整的刪除運算程序#include<stdio.h>/*調(diào)用頭文件“stidio.h”*/#definelistsze10structsequenlist/*構(gòu)建sequenlist型*/{intdata[listsze];intlength;};structsequenlistL;/*定義sequenlist變量L*/二、順序表一個完整的刪除運算程序（續(xù)）voiddelete(structsequenlistL,inti)/*定義delete函數(shù)*/{intj;if(L.length==0)printf("Emptylist,cannotdelete!\n");elseif((i<0)||(i>=L.length))printf("positionisnocorrect\n");else{for(j=i+1;j<L.length;j++){ L.data[j-1]=L.data[j];}L.length--;for(j=0;j<L.length;j++)printf("%d,",L.data[j]);}}二、順序表一個完整的刪除運算程序（續(xù)）main()/*定義主函數(shù)*/{inti,j;structsequenlista;/*定義順序表a*/scanf("%d",&a.length);/*輸入實際表長*/scanf("%d",&j);/*輸入要刪除數(shù)據(jù)的位置*/for(i=0;i<a.length;i++)/*依次輸入順序表a的各節(jié)點*/scanf("%d",&a.data[i]);delete(a,j);/*調(diào)用delete()函數(shù)*/}二、順序表順序表刪除運算的結(jié)論：（1）在線性表中刪除一個數(shù)據(jù)節(jié)點需要移動順序表的一半節(jié)點，即：n/2。（2）時間復雜度：刪除運算的時間復雜度與n有關，即：T(n)=O(n)。三、線性表的鏈式存儲結(jié)構(gòu)1.線性表順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)的異同點順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)存儲空間連續(xù)的存儲空間可以連續(xù)，可以不連續(xù)（分散）的存儲空間節(jié)點間的相鄰關系邏輯上的相鄰關系與存儲結(jié)構(gòu)上的相鄰關系一致。邏輯上是相鄰的，在存儲結(jié)構(gòu)上是不相鄰的?？臻g使用在使用前，事先分配存儲空間。只在使用時才申請存儲空間，使用過后其存儲空間可以刪除。三、線性表的鏈式存儲結(jié)構(gòu)2.單鏈表的形態(tài)非空表：…abm頭節(jié)點第一個數(shù)據(jù)節(jié)點最后一個數(shù)據(jù)節(jié)點head空表：頭節(jié)點headData域next域三、線性表的鏈式存儲結(jié)構(gòu)3.單鏈表類型定義structnode{ datatypedata;//節(jié)點的數(shù)據(jù)域

structnode*next;//節(jié)點的指針區(qū)}；5.求單鏈表的表長(1)單鏈表的表長：單鏈表中數(shù)據(jù)節(jié)點的個數(shù)（不包括頭節(jié)點）。(2)算法：intlength(head)//head是指向單鏈表的頭指針{intn=0;//節(jié)點個數(shù)計數(shù)器賦初值0structnode*p;//定義一個node型指針pp=head;//p指針指向表頭節(jié)點while(p->next!=null)//p指針所指節(jié)點不是鏈表的最后一個節(jié)點{p=p->next;//p指針前進一個節(jié)點n++;//節(jié)點個數(shù)加1}return(n)//返回表長n}6.查找運算（find）structnode*find(head,x){structnode*p;p=head->next;//p指針指向第一個數(shù)據(jù)節(jié)點while((p->next!=null)&&(p-data!=x))//p指針所節(jié)點不是最后節(jié)點，而且其data域的值不為x{p=p->next;//p前進一個節(jié)點}if(p->data==x)return(p);//找到了該節(jié)點，則返回對應p指針的值elsereturn(null);//沒找到該節(jié)點，則返回null（空）}7.插入運算（insert）----插入已知地址的節(jié)點如：在p指針所指節(jié)點后面插入已知地址為s的節(jié)點pP->nexts(1)s->next=p->next;(2)p->next=s;7.插入運算（insert）----插入已知內(nèi)容的節(jié)點如：在p指針所指節(jié)點后面插入已知內(nèi)容為x的節(jié)點pP->nexts(1)s->next=p->next;(2)P->next=s;s=(structnode)malloc(sizeof(structnode));s->data=x;x8.刪除運算（delete）如：刪除p指針所指節(jié)點的下一個節(jié)點pp->next->nextp->nextq=p->next;qq->nextp->next=p->next->next;（或p->next=q->next）free(q);四、單循環(huán)鏈表1.單循環(huán)鏈表的形態(tài)非空表：…abmhead空表：headr注意：單鏈表只能沿著鏈表從前向后訪問表中的各節(jié)點，無法找到某節(jié)點前面的其他節(jié)點；單循環(huán)鏈表可以通過任一節(jié)點訪問表中的其他節(jié)點。四、單循環(huán)鏈表2.單循環(huán)鏈表的刪除運算例如：一個單循環(huán)鏈表，沒有頭指針只有尾指針r，試寫出刪除尾指針r的前一個節(jié)點。a1an-2anra0…an-1四、單循環(huán)鏈表2.單循環(huán)鏈表的刪除運算a1an-2anra0…an-1Step1：找出r節(jié)點前前的那個節(jié)點p；Step2：讓q指向p的下一個節(jié)點；Step3：從鏈表中刪除q所指向的節(jié)點；Step3：回收q。pp->nextqp->next->next四、單循環(huán)鏈表2.單循環(huán)鏈表的刪除運算voiddelete(r){structnode*p,*q;//定義兩個node型指針p和qp=r->next;//讓p指向r的后繼節(jié)點（給p賦初值）while(p->next->next!=r)//找r節(jié)點的前前節(jié)點{p=p->next;}q=p->next;//將要刪除節(jié)點的地址保存到q中p->next=r;//從鏈表中刪除qfree(q);//回收被刪除節(jié)點q的空間}五、雙循環(huán)鏈表1.雙循環(huán)鏈表的形態(tài)habc非空表：h空表：五、雙循環(huán)鏈表2.雙循環(huán)鏈表的類型定義每個節(jié)點有3個成員：priordatanextprior：左鏈域，存放直接前驅(qū)節(jié)點的地址；next：右鏈域，存放直接后繼節(jié)點的地址；data：數(shù)據(jù)域，存放本節(jié)點的信息內(nèi)容。五、雙循環(huán)鏈表2.雙循環(huán)鏈表的類型定義structnode{datatypedata;//節(jié)點的數(shù)據(jù)域structnode*prior,*next;//直接前驅(qū)、后繼的指針}3.雙循環(huán)鏈表的特點:p->prior->next=p->next->prior=p五、雙循環(huán)鏈表4.雙循環(huán)鏈表的基本運算----插入例如：在p所指節(jié)點的前面插入地址為s的節(jié)點。mnxpp->priors(2)(1)(3)(4)五、雙循環(huán)鏈表4.雙循環(huán)鏈表的基本運算----插入例如：在p所指節(jié)點的前面插入地址為s的節(jié)點。(1)s->prior=p-prior;(2)s->next=p;(3)p-prior-next=s;(4)p-prior=s;五、雙循環(huán)鏈表4.雙循環(huán)鏈表的基本運算----刪除例如：刪除p指針所指的節(jié)點pp->priorp->next(1)(2)(1)p->prior->next=p->ne