計(jì)算機(jī)軟件基礎(chǔ)課件：線性數(shù)據(jù)結(jié)構(gòu)

線性數(shù)據(jù)結(jié)構(gòu)《計(jì)算機(jī)軟件基礎(chǔ)》本章重點(diǎn)難點(diǎn)本章重點(diǎn)：線性表的特點(diǎn)；順序表和鏈表上的基本操作；棧、隊(duì)列的概念及基本操作；棧的應(yīng)用；特殊矩陣壓縮存儲(chǔ)時(shí)元素的位置。本章難點(diǎn)：?jiǎn)捂湵砩系牟僮鳎粭５膽?yīng)用。01.線性表02.棧03.隊(duì)列04.特殊矩陣的壓縮存儲(chǔ)主要內(nèi)容01線性表1.線性表的概念線性表是一種簡(jiǎn)單且常用的數(shù)據(jù)結(jié)構(gòu)。線性表是由n（n≥0）個(gè)相同類型的數(shù)據(jù)元素a1、a2、a3、…、an組成的有限序列。n=0，為空表。對(duì)于非空的線性表，每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，有且僅有一個(gè)開始數(shù)據(jù)元素和一個(gè)終端數(shù)據(jù)元素，其余數(shù)據(jù)元素有且僅有唯一的一個(gè)直接前驅(qū)和唯一的一個(gè)直接后繼。例如： inta[5];

定義a為一個(gè)整型數(shù)組，可以用來存儲(chǔ)線性表，其長(zhǎng)度為5，每個(gè)數(shù)據(jù)元素都是整型。2.線性表的順序存儲(chǔ)結(jié)構(gòu)1）順序表用一組地址連續(xù)的存儲(chǔ)空間依次（邏輯順序）存放線性表中的各個(gè)數(shù)據(jù)元素

線性表中邏輯上相鄰的數(shù)據(jù)結(jié)點(diǎn)在物理位置上也相鄰。2）順序表上的基本操作可以用一維數(shù)組來實(shí)現(xiàn)線性表的順序存儲(chǔ)。方式：靜態(tài)方式：存儲(chǔ)數(shù)組的大小和空間事先已經(jīng)固定分配動(dòng)態(tài)方式：是存儲(chǔ)數(shù)組的空間在程序執(zhí)行過程中通過動(dòng)態(tài)存儲(chǔ)分配語句來分配順序表的靜態(tài)存儲(chǔ)表示如下：#defineM100/*順序表最大長(zhǎng)度為M*/typedefintElemType; /*此處以整型元素為例*/typedefstruct{ElemTypedata[M];intlength; /*length代表線性表的當(dāng)前長(zhǎng)度*/}SqList; /*定義SqList線性表類型*/①查找操作線性表的查找是在表中查找與給定值x相等的數(shù)據(jù)元素的位置。例8-1在長(zhǎng)度為n的線性表L中順序查找內(nèi)容為x的數(shù)據(jù)元素，找到則返回下標(biāo)值，沒找到則返回-1。然后，計(jì)算成功的平均查找次數(shù)及時(shí)間復(fù)雜度T(n)。/*在線性表L中順序查找內(nèi)容為x的數(shù)據(jù)元素*/intsearch_Sq(SqListL,intx){ inti;for(i=0;i<L.length;i++)if(L.data[i]==x)returni;/*返回找到第一個(gè)值相等元素的下標(biāo)，從0開始*/return-1;/*沒有找到返回-1*/}

②插入操作線性表的插入操作是指在線性表的第i-1個(gè)數(shù)據(jù)元素和第i個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素，使長(zhǎng)度為n的線性表變成長(zhǎng)度為n+1的線性表。

intinsert_Sq(SqList*L,inti,intx){intj;if(i<0||i>L->length||L->length==M)return0;/*插入位置非法或線性表已滿，插入失敗*/for(j=L->length-1;j>=i;j--)L->data[j+1]=L->data[j];/*將第i個(gè)位置及之后的元素都向后移動(dòng)一位*/L->data[i]=x;/*將x插入到第i個(gè)位置*/L->length++;/*線性表長(zhǎng)度加1*/return1;/*插入成功*/}

③刪除操作

intdelete_Sq(SqList*L,inti){intj; if(i<0||i>=L->length)return0;/*刪除位置非法，刪除失敗*/for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];/*將第i+1個(gè)位置及之后的元素都向前移動(dòng)一位*/L->length--;/*線性表長(zhǎng)度減1*/return1;/*刪除成功*/}

3.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這些存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。數(shù)據(jù)元素的存儲(chǔ)映像（結(jié)點(diǎn)）：數(shù)據(jù)域+指針域1）單鏈表（線性鏈表）利用指針將鏈表各結(jié)點(diǎn)按其邏輯順序依次鏈接起來。①求表長(zhǎng)表長(zhǎng)是單鏈表中數(shù)據(jù)元素結(jié)點(diǎn)的個(gè)數(shù)。例8-4求帶頭結(jié)點(diǎn)單鏈表的表長(zhǎng)。intgetlen_SL(SLinkedList*head)/*head是指向單鏈表的頭指針*/{SLinkedList*p;intn=0;/*結(jié)點(diǎn)個(gè)數(shù)用n記錄，置初值為0*/p=head; /*p指向頭結(jié)點(diǎn)*/while(p->next!=NULL)/*p不是最后一個(gè)結(jié)點(diǎn)則進(jìn)行循環(huán)*/{p=p->next;/*p指針前進(jìn)一個(gè)結(jié)點(diǎn)*/n++;/*結(jié)點(diǎn)個(gè)數(shù)加1*/}returnn; /*返回鏈表表長(zhǎng)n*/}

②查找操作例8-5在單鏈表中查找元素值為x的結(jié)點(diǎn)，若找到，返回該點(diǎn)地址；否則返回NULL。SLinkedList*search_SL(SLinkedList*head,ElemTypex){SLinkedList*p;p=head->next;/*置初態(tài)，p指向單鏈表的第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)*/while(p!=NULL&&p->data!=x)/*當(dāng)p尚未指向空，且p的data值不是x時(shí)*/ p=p->next;/*p指針后移*/if(p->data==x) returnp;/*找到x則返回指向該結(jié)點(diǎn)的指針p*/else returnNULL;/*沒找到返回NULL*/}

③插入操作例8-6在指針p所指的單鏈表結(jié)點(diǎn)后面插入元素值為x的結(jié)點(diǎn)。

創(chuàng)建被插入結(jié)點(diǎn)ss=(SLinkedList*)malloc(sizeof(SLinkedList));s->data=x;①讓s的next指向p的下一個(gè)結(jié)點(diǎn)，即s->next=p->next；②讓p的next指向s結(jié)點(diǎn)，即p->next=s。④刪除操作

首先，將p的下一個(gè)結(jié)點(diǎn)地址保存到q中，即令q=p->next；其次，從鏈表中刪除結(jié)點(diǎn)q，p的next指向q的下一個(gè)結(jié)點(diǎn)，即令p->next=q->next；最后，回收被刪除的q所指結(jié)點(diǎn)的空間，即free(q)。⑤單鏈表的建立頭插法。頭插法的特點(diǎn)是每次總是將新結(jié)點(diǎn)插在表頭結(jié)點(diǎn)head的后面。尾插法。尾插法的特點(diǎn)是每次總是將新結(jié)點(diǎn)插在當(dāng)前鏈表的尾部。例8-7依次輸入一串字符"abc"，以"*"為結(jié)束標(biāo)記。例8-8依次輸入一串字符“abc”，以“*”作為結(jié)束標(biāo)記。2）循環(huán)單鏈表循環(huán)鏈表：將鏈表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。循環(huán)單鏈表的操作和單鏈表的操作基本一致，差別僅在于算法中的循環(huán)條件不是p或p->next是否為空，而是它們是否等于頭指針。

例8-9一個(gè)帶頭結(jié)點(diǎn)循環(huán)單鏈表，假設(shè)它只有尾指針r，且最少具有兩個(gè)數(shù)據(jù)域有值的結(jié)點(diǎn)，試寫出刪除r的前一個(gè)結(jié)點(diǎn)操作的算法。首先，找出r的前前一個(gè)結(jié)點(diǎn)p；然后，把p的下一個(gè)結(jié)點(diǎn)（即r的前一個(gè)結(jié)點(diǎn)，被刪除結(jié)點(diǎn)）地址保存到q中；最后，從鏈表中刪除q結(jié)點(diǎn)，并回收q結(jié)點(diǎn)空間。時(shí)間復(fù)雜度：T(n)=O(n)3）雙向鏈表prior稱為左鏈域，存放直接前驅(qū)（左邊）結(jié)點(diǎn)的地址。next稱為右鏈域，存放直接后繼（右邊）結(jié)點(diǎn)的地址。data稱為數(shù)據(jù)域，存放該結(jié)點(diǎn)的信息內(nèi)容。插入操作刪除操作時(shí)間性能順序存儲(chǔ)結(jié)構(gòu)：對(duì)于隨機(jī)訪問操作（根據(jù)數(shù)組下標(biāo)查找元素），時(shí)間復(fù)雜度為O(1)。對(duì)于插入和刪除操作，需要移動(dòng)后續(xù)元素來保持順序，平均情況下的時(shí)間復(fù)雜度為O(n)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：對(duì)于插入和刪除操作，時(shí)間復(fù)雜度為O(1)，僅需調(diào)整指針即可。對(duì)于隨機(jī)訪問操作，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)需要遍歷結(jié)點(diǎn)來查找特定位置的元素，時(shí)間復(fù)雜度為O(n)?？臻g性能順序存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)的空間利用率高。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：需要額外的空間來存儲(chǔ)指針，因此，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的空間利用率相對(duì)較低。

需要根據(jù)具體的應(yīng)用場(chǎng)景和需求來選擇合適的存儲(chǔ)結(jié)構(gòu)，權(quán)衡時(shí)間和空間性能的優(yōu)劣。4）順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的比較02棧棧:特殊線性表，一端固定，只允許在另一端插入和刪除的線性表。又稱堆棧。pushpoptopbottom棧底、棧頂、入棧、出棧、棧空、棧滿……與一般線性表的相同和不同？特性：“先進(jìn)后出(FILO:FirstInLastOut)”或“后進(jìn)先出(LIFO-LastInFirstOut)”

元素關(guān)系操作特殊在操作：操作受限制！1.棧的概念2.棧的順序存儲(chǔ)結(jié)構(gòu)順序棧類型定義如下：#defineM100/*棧的容量*/typedefcharElemType;typedefstructSnode{ElemTypedata[M];inttop;/*棧頂指針*/}SeqStack;1）順序棧的類型定義2）順序棧的基本操作①進(jìn)棧：在向s棧中加入值為x的新元素時(shí)，首先判斷棧是否已滿；若滿，則進(jìn)行上溢處理，返回；不滿則top加1，并將x放入data數(shù)組的top位置。voidpush(SeqStack*s,ElemTypex){if(s->top==M-1){printf("棧滿\n");return;}s->top++;s->data[s->top]=x;}特點(diǎn)：簡(jiǎn)單、方便，但易產(chǎn)生溢出?！錾弦?Overflow):棧已經(jīng)滿，又要壓入元素；■下溢(Underflow)：棧已經(jīng)空，還要彈出元素；②出棧：首先判斷棧是否為空；若棧為空，則進(jìn)行下溢處理（返回一個(gè)特殊錯(cuò)誤標(biāo)志'\0'）；若不空，返回棧頂元素，同時(shí)將棧頂指針top減1。出棧操作算法描述如下：ElemTypepop(SeqStack*s){ElemTypeitem;if(s->top==-1){printf("?？誠n");return'\0';}item=s->data[s->top];s->top--;returnitem;}3.棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1）鏈棧的類型定義鏈棧類型定義如下：typedefcharElemType;typedefstructLsnode{ElemTypedata;structLsnode*next;}LinkStack;2）鏈棧的基本操作①進(jìn)棧：向鏈棧的棧頂插入數(shù)據(jù)元素x。LinkStack*push(LinkStack*Ls,ElemTypex){LinkStack*s=(LinkStack*)malloc(sizeof(LinkStack));if(s==NULL){printf("內(nèi)存分配失敗.\n");returnLs;}s->data=x;s->next=Ls;Ls=s;returnLs;}②出棧：鏈棧的出棧操作即刪除棧頂元素。算法實(shí)現(xiàn)如下：LinkStack*pop(LinkStack*Ls,ElemType*x){if(Ls==NULL){printf("?？?\n");returnLs;}*x=top->data;LinkStack*temp=Ls;Ls=Ls->next;free(temp);returnLs;}4.棧的應(yīng)用1）出棧順序判斷例8-10

若將a、b和c三個(gè)字符元素依次進(jìn)棧，試問可能有多少種出棧順序，它們分別是什么?三個(gè)字符元素的全排列有六種：分別是abc、acb、bac、bca、cab、cba。下面逐一進(jìn)行分析：要得到abc出棧順序、其進(jìn)、出棧過程為：a進(jìn)→a出→b進(jìn)→b出→c進(jìn)→c出。acb的進(jìn)、出棧過程為：a進(jìn)→a出→b進(jìn)→c進(jìn)→c出→b出。bac的進(jìn)、出棧過程為：a進(jìn)→b進(jìn)→b出→a出→c進(jìn)→c出。bca的進(jìn)、出棧過程為：a進(jìn)→b進(jìn)→b出→c進(jìn)→c出→a出。要想得到出棧順序cba，也就是要想c先出來，abc依次都得進(jìn)棧。其過程為：a進(jìn)→b進(jìn)→c進(jìn)；最后的出棧順序只能為cba，而不可能得到cab，因?yàn)閍要出來，b必須先出來。本題結(jié)果是有五種出棧順序，分別為abc、acb、bac、bca、cba。[問題]如果將A、B、C、D四個(gè)字符按順序壓入堆棧，出棧順序任意，那么是不是A、B、C、D的所有排列都可能是出棧的序列？可以產(chǎn)生CABD這樣的序列嗎？2）數(shù)值轉(zhuǎn)換十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換。

NN/8N%8134816841682102125202while(N){ push(&stack,N%8); N=N/8;}while(!isEmpty(&stack)){ e=pop(&stack); printf("%d",e);}3）表達(dá)式求值(中綴)例8-12試寫出表達(dá)式9+4*6/8-5求值時(shí)棧的變化過程。4）逆置操作例8-13

利用棧逆置單鏈表?；舅悸肥菍捂湵碓貜念^依次進(jìn)棧，然后棧內(nèi)元素再依次出棧從頭放入單鏈表中。voidtransLink(SLinkedList*head){SeqStackstack;SLinkedList*p;initStack(&stack);/*創(chuàng)建一個(gè)空棧stack*/p=head->next;/*p指向單鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/while(p!=NULL)/*鏈表中元素尚未全部進(jìn)棧時(shí)*/{push(&stack,p->data);/*將p指向結(jié)點(diǎn)的數(shù)據(jù)進(jìn)棧*/p=p->next; /*p指針下移*/}p=head->next;/*再將p指向單鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/while(!isEmpty(&stack))/*若棧非空*/{p->data=pop(&stack);/*棧頂元素出棧放入p所指結(jié)點(diǎn)數(shù)據(jù)域*/p=p->next;/*p指針下移*/}}03隊(duì)列1.隊(duì)列的概念只允許在一端插入，在另一端刪除的線性表。隊(duì)首、隊(duì)尾、入隊(duì)、出隊(duì)、隊(duì)空、隊(duì)滿……與一般線性表的相同和不同？特性：“先進(jìn)先出(FIFO)”或“后進(jìn)后出(LILO)”元素關(guān)系操作rearfront特殊在操作：操作受限制！2.隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)1）順序隊(duì)列的類型定義#defineM100/*假設(shè)隊(duì)列空間最多容納100個(gè)元素，即隊(duì)列的容量*/typedefcharElemType;typedefstructqnode{ElemTypedata[M];intfront;intrear;}seqQueue;2）順序隊(duì)列的基本操作①入隊(duì)voidenqueue(seqQueue*queue,ElemTypex){if(queue->rear==M-1){printf("隊(duì)列已滿，無法插入元素\n");return;}queue->rear++;queue->data[queue->rear]=x;}②出隊(duì)ElemTypedequeue(seqQueue*q