計(jì)算機(jī)軟件基礎(chǔ)(自考本科)(1.8)

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

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