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

計(jì)算機(jī)軟件基礎(chǔ)第二篇數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第八章

線性表（linearlist）一、線性表的概念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)具有相同的屬性。③線性表長(zhǎng)度：線性表中數(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）用一維數(shù)組描述順序表#defineM100/*假定順序表最大長(zhǎng)度為M*/struct{int

data[M];

/*假定各數(shù)據(jù)節(jié)點(diǎn)均為整型*/

int

n;

/*n代表線性表表長(zhǎng)*/}L;/*用L代表線性表*/二、順序表2.順序表的基本運(yùn)算——查找intloca(L[],n){i=0;

while(L[i]!=x&&i<=n-1)i++;

if(i>n-1)return(-1);/*找不到x*/

elsereturn(i);/*找到了x，返回下標(biāo)位置i*/}例8-1在長(zhǎng)度為n的線性表L中順序查找內(nèi)容為X的節(jié)點(diǎn)。要求：寫出類C語言算法，求成功的平均查找長(zhǎng)度及時(shí)間復(fù)雜度T(n)。二、順序表一個(gè)完整的查找程序：#include<stdio.h>#definelistsize50struct

sequenlist

/*構(gòu)建sequenlist型*/

{

int

data[listsize];

intlength;};struct

sequenlistL;/*定義sequenlist變量L*/int

find(struct

sequenlistL,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(){

int

i,j,y;

struct

sequenlista;

scanf("%d",&a.length);/*輸入實(shí)際表長(zhǎng)*/

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ù)為：(表長(zhǎng)+1)/2。（2）時(shí)間復(fù)雜度：表長(zhǎng)越長(zhǎng)，查找所消耗時(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:將順序表的表長(zhǎng)加1；step4:在順序表的第i個(gè)位置插入x；二、順序表例8-2在長(zhǎng)度為n的線性表L中第i(0≤i≤n)個(gè)位置上插入內(nèi)容為x的數(shù)據(jù)節(jié)點(diǎn)。要求：寫出類c語言算法，求節(jié)點(diǎn)平均移動(dòng)次數(shù)及時(shí)間復(fù)雜度T(n)。voidinse(L[]，i，x){if(n==m)滿，無法插入；

else{for(k=n-1；k>=i；k--)L[k+1]=L[k]；/*后移*/

L[i]=x；/*插入x*/

n++；/*表長(zhǎng)加1*/

}}二、順序表一個(gè)完整的插入運(yùn)算程序#include<stdio.h>#definelistsze10struct

sequenlist

/*構(gòu)建sequenlist型*/

{

int

data[listsze];

intlength;};struct

sequenlistL;二、順序表一個(gè)完整的插入運(yùn)算程序（續(xù)）voidinsert(struct

sequenlistL,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(){

int

i,j,y;

struct

sequenlista;

scanf("%d",&a.length);/*輸入實(shí)際表長(zhǎng)*/

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:將順序表的表長(zhǎng)減去1；二、順序表

例8-3在表長(zhǎng)為n的線性表L中刪除第i(0≤i≤n一1)個(gè)節(jié)點(diǎn)。要求：寫出類c語言算法，求節(jié)點(diǎn)平均移動(dòng)次數(shù)及時(shí)間復(fù)雜度T(n)。

voiddele(L[],i){if(n==0)表空，無法刪；

else{for(k=i+1；k<=n-1；k++)L[k-1]=L[k]；/*前移*/

n--;/*表長(zhǎng)減1*/

}}二、順序表一個(gè)完整的刪除運(yùn)算程序#include<stdio.h>/*調(diào)用頭文件"stidio.h"

*/#definelistsze10struct

sequenlist

/*構(gòu)建sequenlist型*/

{

int

data[listsze];

intlength;};struct

sequenlistL;/*定義sequenlist變量L*/二、順序表一個(gè)完整的刪除運(yùn)算程序（續(xù)）voiddelete(struct

sequenlistL,inti)/*定義delete函數(shù)*/{

intj;

if(L.length==0)printf("Empty

list,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ù)*/{

int

i,j;

struct

sequenlista;/*定義順序表a*/

scanf("%d",&a.length);/*輸入實(shí)際表長(zhǎng)*/

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.單鏈表的形態(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)2.線性表順序存儲(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)上是不相鄰的。空間使用在使用前，事先分配存儲(chǔ)空間。只在使用時(shí)才申請(qǐng)存儲(chǔ)空間，使用過后其存儲(chǔ)空間可以刪除。三、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3.單鏈表運(yùn)算符號(hào)的說明1）p->data，p指針?biāo)腹?jié)點(diǎn)的data值2）p->next，p指針?biāo)腹?jié)點(diǎn)的next值，即下一個(gè)節(jié)點(diǎn)的地址3）p->next->data

，p的下一個(gè)節(jié)點(diǎn)的data值4）p->next->next

，p的下下個(gè)節(jié)點(diǎn)的地址5）p=p->next，讓p指針指向下一個(gè)節(jié)點(diǎn)（p指針前進(jìn)一個(gè)節(jié)點(diǎn))6）p->next==null，p所指節(jié)點(diǎn)為單鏈表的最后一個(gè)節(jié)點(diǎn)7）p=(類型名*)malloc(sizeof(類型名));申請(qǐng)節(jié)點(diǎn)空間，p指向其首地址8）free(p)回收p所指節(jié)點(diǎn)的空間4.單鏈表上的簡(jiǎn)單運(yùn)算例8-4求單鏈表的表長(zhǎng)（不包括表頭節(jié)點(diǎn)）。intlength(head)//head是指向單鏈表的頭指針{

intn=0;//節(jié)點(diǎn)個(gè)數(shù)計(jì)數(shù)器賦初值0

structnode*p;//定義一個(gè)node型指針pp=head;//p指針指向表頭節(jié)點(diǎn)

while(p->next!=null)//p不為最后一個(gè)節(jié)點(diǎn)就循環(huán)

{p=p->next;//p指針前進(jìn)一個(gè)節(jié)點(diǎn)n++;//節(jié)點(diǎn)個(gè)數(shù)加1}return(n)//返回表長(zhǎng)n}例8-5在單鏈表中查找內(nèi)容為x的節(jié)點(diǎ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ǎn)捂湵碇荒苎刂湵韽那跋蚝笤L問表中的各節(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：讓p指向q的下一個(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;//從鏈表中刪除q

free(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->next;(2)p->next->prior=p->prior;(3)free(p);六、鏈表的建立1.尾插法依次輸入abc時(shí)，以尾插法建立的單鏈表為：headab2.頭插法依次輸入abc時(shí)，以頭插法建立的單鏈表為：cheadcba例8-10依次輸入一串字符"abc"，以"*"作為結(jié)束標(biāo)志，建立并輸出如下單鏈表：#defineLENsizeof(structstu10)#include<stdi0.h>structstu10/*定義一個(gè)具有data域和next域的單鏈表節(jié)點(diǎn)結(jié)構(gòu)*/{chardata；

structstul0*next；}*head，*P；/*為指向單鏈表頭節(jié)點(diǎn)的指針，P為指向各節(jié)點(diǎn)的指針*/Structstu10*f810()/*定義一個(gè)返回單鏈表頭地址的指針函數(shù)*/{stmctstul0*r；/*r為指向單鏈表各節(jié)點(diǎn)的指針*/Charch;head=(structstu10*)malloc(LEN)；/*申請(qǐng)一個(gè)表頭節(jié)點(diǎn)head*/r=head；/*開始r指向head所指節(jié)點(diǎn)，即表頭節(jié)點(diǎn)*/六、鏈表的建立while((ch=getchar())!=‘*')/*輸入字符*/{P=(structstu10*)malloc(LEN)；/*申請(qǐng)一個(gè)節(jié)點(diǎn)P*/

p->data=ch；/*把ch存入data域*/

p->next=NULL；/*P的鏈域置空*/

r->next=P：/*把P鏈入r的鏈中*/

r=P;/*r下移一個(gè)節(jié)點(diǎn)*/retum(head)；/*返回單鏈表表頭節(jié)點(diǎn)地址*/}voidprint()/*輸出單鏈表各節(jié)點(diǎn)的data值*/{P=head->next；

while(P!=NULL){printf("%c"，p->data)；

p=p->next；

}}

六、鏈表的建立

例8-11依次輸人一串字符"abc"，以"*"為結(jié)束標(biāo)記，建立并輸出如下單鏈表：

structstu10*f811(){charch；head=(structstu10*)malloc(LEN)；/*申請(qǐng)頭節(jié)點(diǎn)*/head->next=NULL；/*頭節(jié)點(diǎn)鏈域置空*/while((ch=getchar())!='*'){p=(structstu10*)malloc(LEN)；

p->data=ch；

p->next=head->next；/*把head的下一個(gè)節(jié)點(diǎn)地址存入P的鏈*/

head->next=P；/*把P節(jié)點(diǎn)的地址存入head的鏈*/