數(shù)據(jù)結(jié)構(gòu)第02章

第2章線性表主要知識點線性表抽象數(shù)據(jù)類型順序表單鏈表循環(huán)單鏈表循環(huán)雙向鏈表靜態(tài)鏈表設(shè)計舉例2.1

線性表抽象數(shù)據(jù)類型1.線性表的定義線性表是一種可以在任意位置插入和刪除數(shù)據(jù)元素操作、由n(n≥0)個相同類型數(shù)據(jù)元素a0,a1,…,an-1組成的線性結(jié)構(gòu)。線性結(jié)構(gòu):2.線性表抽象數(shù)據(jù)類型數(shù)據(jù):｛a0,a1,…,an-1｝,ai的數(shù)據(jù)類型為DataType操作:(1)ListInitiate(L)初始化線性表(2)ListLength(L)求當前數(shù)據(jù)元素個數(shù)(3)

ListInsert(L,i,x)插入數(shù)據(jù)元素(4)ListDelete(L,i,x)刪除數(shù)據(jù)元素(5)ListGet(L,i,x)取數(shù)據(jù)元素｛a0,a1,…,an-1｝表示數(shù)據(jù)元素有次序關(guān)系,簡稱序列。2.2線性表的順序表示和實現(xiàn)1.順序表的存儲結(jié)構(gòu)

實現(xiàn)順序存儲結(jié)構(gòu)的方法是使用數(shù)組。數(shù)組把線性表的數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存單元中，這樣線性表中邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上也相鄰。數(shù)據(jù)元素間的邏輯上的前驅(qū)、后繼邏輯關(guān)系就表現(xiàn)在數(shù)據(jù)元素的存儲單元的物理前后位置上。順序表的存儲結(jié)構(gòu)如圖所示順序存儲結(jié)構(gòu)的線性表稱作順序表a0a1a2a3a4a5…listsize=6MaxSize-10123456其中a0,a1,

a2等表示順序表中存儲的數(shù)據(jù)元素，list表示順序表存儲數(shù)據(jù)元素的數(shù)組，MaxSize表示存儲順序表的數(shù)組的最大存儲單元個數(shù)，size表示順序表當前存儲的數(shù)據(jù)元素個數(shù)。

typedef

struct{DataType

list[MaxSize];

intsize;}SeqList;2.順序表操作的實現(xiàn)

（1）初始化ListInitiate(L)void

ListInitiate(SeqList*L) {L->size=0; /*定義初始數(shù)據(jù)元素個數(shù)*/}

（2）求當前數(shù)據(jù)元素個數(shù)ListLength(L)int

ListLength(SeqListL) {returnL.size;}

（3）插入數(shù)據(jù)元素ListInsert(L,i,x)

int

ListInsert(SeqList*L,inti,DataTypex){intj;

for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];

/*依次后移*/

L->list[i]=x; /*插入x*/ L->size++; /*元素個數(shù)加1*/

return1;}（4）刪除數(shù)據(jù)元素ListDelete(L,i,x)int

ListDelete(SeqList*L,inti,DataType*x) {intj;

*x=L->list[i]; /*保存刪除的元素到x中*/

for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];

/*依次前移*/

L->size--; /*數(shù)據(jù)元素個數(shù)減1*/

return1;}（5）取數(shù)據(jù)元素ListGet(L,i,x)int

ListGet(SeqListL,inti,DataType*x){if(i<0||i>L.size-1){printf("參數(shù)i不合法!\n"); return0;}else{ *x=L.list[i];return1;}}3.順序表操作的效率分析時間效率分析:算法時間主要耗費在移動元素的操作上，因此計算時間復(fù)雜度的基本操作(最深層語句頻度)T(n)=O(移動元素次數(shù))而移動元素的個數(shù)取決于插入或刪除元素的位置i.若i=size，則根本無需移動（特別快）；若i=0，則表中元素全部要后移（特別慢）；應(yīng)當考慮在各種位置插入（共n+1種可能）的平均移動次數(shù)才合理。設(shè)Pi是在第i個存儲位置插入一個數(shù)據(jù)元素的概率，順序表中的數(shù)據(jù)元素個數(shù)為n,當在順序表的任何位置上插入數(shù)據(jù)元素的概率相等時，有Pi=1/(n+1),則

插入時的平均移動次數(shù)為:n(n+1)/2÷（n+1）＝n/2≈O(n)同理可證:順序表刪除一元素的時間效率為:T（n)=(n-1)/2≈O(n)

順序表中的其余操作都和數(shù)據(jù)元素個數(shù)n無關(guān)，因此，在順序表中插入和刪除一個數(shù)據(jù)元素的時間復(fù)雜度為O(n),其余操作的時間復(fù)雜度都為O(1)主要優(yōu)點是算法簡單，空間單元利用率高；主要缺點是需要預(yù)先確定數(shù)據(jù)元素的最大個數(shù)，插入和刪除時需要移動較多的數(shù)據(jù)元素。主要優(yōu)缺點4.順序表應(yīng)用舉例例：編程實現(xiàn)如下任務(wù):建立一個線性表，首先依次輸入數(shù)據(jù)元素1，2，3，…，10，然后刪除數(shù)據(jù)元素5，最后依次顯示當前線性表中的數(shù)據(jù)元素。要求采用順序表實現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過100個。

實現(xiàn)方法：

1、采用直接編寫一個主函數(shù)實現(xiàn)。

2、利用已設(shè)計實現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名為SeqList.h中，通過#include“SeqList.h”）程序設(shè)計如下：#include<stdio.h> #defineMaxSize100 typedef

int

DataType;#include"SeqList.h"

voidmain(void){SeqList

myList;

inti,x;

ListInitiate(&myList);

for(i=0;i<10;i++)

ListInsert(&myList,i,i+1);

ListDelete(&myList,4,&x);

for(i=0;i<ListLength(myList);i++)

ListGet(myList,i,&x);}程序運行結(jié)果：12346789102.3線性表的鏈式表示和實現(xiàn)1.單鏈表的結(jié)構(gòu)(1)單鏈表中構(gòu)成鏈表的結(jié)點只有一個指向直接后繼結(jié)點的指針域。其結(jié)構(gòu)特點：邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。結(jié)點結(jié)構(gòu)如圖示：指針域數(shù)據(jù)域nextdata或數(shù)據(jù)域：存儲元素數(shù)值數(shù)據(jù)指針域：存儲直接后繼的存儲位置(2)頭指針、頭結(jié)點和首元結(jié)點的區(qū)別頭指針頭結(jié)點首元結(jié)點a0heada1…an^示意圖如下：頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為首元結(jié)點）的指針；頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息，它不計入表長度。首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a０的結(jié)點。(3)帶頭結(jié)點單鏈表和不帶頭結(jié)點單鏈表的比較pa0a1an-1∧…h(huán)eaddatanextx∧s(a)插入前pa0a1an-1∧…h(huán)eaddatanextx∧s(b)插入后1).在帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素前插入結(jié)點2).刪除帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素結(jié)點pa0a1an-1∧…h(huán)eaddatanext3).在不帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素前插入結(jié)點a0a1an-1∧…h(huán)eadx∧s(a)插入前a0a1an-1∧…h(huán)eadxs(b)插入后4).在不帶頭結(jié)點單鏈表其他數(shù)據(jù)元素前插入結(jié)點pai-1a0aian-1∧…h(huán)eaddatanextxs…×5).刪除不帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素結(jié)點a0a1an-1∧…h(huán)eaddatanext×6).刪除不帶頭結(jié)點單鏈表其他數(shù)據(jù)元素結(jié)點pai-1a0aian-1∧…h(huán)eaddatanext…×ai+1結(jié)論：（1）帶頭結(jié)點單鏈表無論在第一個數(shù)據(jù)元素結(jié)點前插入，還是在其他結(jié)點前插入，操作方法一樣；而不帶頭結(jié)點單鏈表在第一個數(shù)據(jù)元素結(jié)點前插入，和在其他結(jié)點前插入，操作方法不一樣（2）刪除操作和插入操作類似（3）設(shè)計帶頭結(jié)點單鏈表的算法時，頭指針參數(shù)可設(shè)計成輸入型參數(shù)；設(shè)計不帶頭結(jié)點單鏈表的算法時，頭指針參數(shù)必須設(shè)計成輸出型參數(shù)（4）因此，帶頭結(jié)點單鏈表的算法設(shè)計簡單結(jié)點定義：typedef

structNode{

DataTypedata;

structNode*next;}SLNode2.單鏈表的操作實現(xiàn)（1）初始化ListInitiate(head)voidListInitiate(SLNode**head){

*head=(SLNode*)malloc(sizeof(SLNode));(*head)->next=NULL; }（2）求當前數(shù)據(jù)元素個數(shù)ListLength(head)int

ListLength(SLNode*head){

SLNode*p=head;

intsize=0;

while(p->next!=NULL) {p=p->next; size++; }returnsize;}（3）插入ListInsert(head,i,x)int

ListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;

p=head;j=-1;

while(p->next!=NULL&&j<i-1){p=p->next;j++; }

if(j!=i-1){printf(“插入位置參數(shù)錯！”); return0;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=p->next;p->next=q; return1;}說明：①要在帶頭結(jié)點的單鏈表第i（0≤i≤size）個結(jié)點前插入一個存放數(shù)據(jù)元素x的結(jié)點，首先要在單鏈表中尋找到第i-1個結(jié)點并由指針p指示，然后動態(tài)申請一個結(jié)點存儲空間并由指針q指示，并把數(shù)據(jù)元素x的值賦予新結(jié)點的數(shù)據(jù)元素域（即q->data=x），最后修改新結(jié)點的指針域指向ai結(jié)點（即q->next=p->next），并修改ai-1結(jié)點的指針域指向新結(jié)點q（即p->next=q）。②循環(huán)條件由兩個子條件邏輯與組成，其中子條件p->next!=NULL保證指針所指結(jié)點存在，子條件j<i-1保證最終讓指針p指向ai-1結(jié)點。

（4）刪除ListDelete(head,i,x)int

ListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;

p=head;j=-1;

while(p->next!=NULL&&p->next->next!=NULL&&j<i-1){p=p->next; j++;}

if(j!=i-1){printf(“插入位置參數(shù)錯！”); return0;}

s=p->next;*x=s->data;p->next=p->next->next;

free(s);return1;}

說明：要在帶頭結(jié)點的單鏈表中刪除第i（0≤i≤size-1）個結(jié)點，首先要在單鏈表中尋找到第i-1個結(jié)點并由指針p指示，然后讓指針s指向ai結(jié)點（即s=p->next），并把數(shù)據(jù)元素ai的值賦予x（即*x=s->data），最后把ai結(jié)點脫鏈（即p->next=p->next->next），并動態(tài)釋放ai結(jié)點的存儲空間（即free(s)）。刪除過程如圖2-14所示。圖中的①對應(yīng)算法中的刪除語句。（5）取數(shù)據(jù)元素ListGet(head,i,x)int

ListGet(SLNode*head,inti,DataType*x){SLNode*p;

intj;

p=head;j=-1;

while(p->next!=NULL&&j<i){p=p->next; j++; }

if(j!=i){printf(“取元素位置參數(shù)錯！”); return0;}

*x=p->data;return1;}

（6）撤消單鏈表Destroy(head)voidDestroy(SLNode**head){SLNode*p,*p1;

p=*head;

while(p!=NULL){p1=p;p=p->next;free(p1); }*head=NULL;}4.單鏈表操作的效率分析單鏈表的插入和刪除操作不需移動數(shù)據(jù)元素，只需比較數(shù)據(jù)元素。因此，當在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：刪除一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：另外，單鏈表求數(shù)據(jù)元素個數(shù)操作的時間復(fù)雜度為O(n)。和順序表相比主要優(yōu)點是不需要預(yù)先確定數(shù)據(jù)元素的最大個數(shù)，插入和刪除操作不需要移動數(shù)據(jù)元素；主要缺點是查找數(shù)據(jù)元素時需要順序進行，不能像順序表那樣隨機查找任意一個數(shù)據(jù)元素。另外，每個結(jié)點中要有一個指針域，因此空間單元利用率不高。而且單鏈表操作的算法也較復(fù)雜。單鏈表和順序表相比，單鏈表的優(yōu)點和缺點正好相反。5.單鏈表應(yīng)用舉例例：編程實現(xiàn)如下任務(wù):建立一個線性表，首先依次輸入數(shù)據(jù)元素1，2，3，…，10，然后刪除數(shù)據(jù)元素5，最后依次顯示當前線性表中的數(shù)據(jù)元素。要求采用單鏈表實現(xiàn)。#include<stdio.h> #include<stdlib.h> #include<malloc.h>typedef

int

DataType;#include"LinList.h"

voidmain(void){SLNode*head;

inti,x;

ListInitiate(&head);

for(i=0;i<10;i++)

ListInsert(head,i,i+1);

ListDelete(head,4,&x);

for(i=0;i<ListLength(head);i++){ListGet(head,i,&x)==0);

printf(“%d”,x);

}

Destroy(&head);}程序運行結(jié)果：12346789102.4循環(huán)單鏈表循環(huán)單鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點是鏈表中最后一個結(jié)點的指針域指向整個鏈表的第一個結(jié)點，從而使鏈表形成一個環(huán)。它的優(yōu)點是從鏈尾到鏈頭比較方便。循環(huán)單鏈表也有帶頭結(jié)點和不帶頭結(jié)點兩種結(jié)構(gòu)。一個帶頭結(jié)點的循環(huán)單鏈表如下圖示：a0a1an-1…h(huán)eadhead(a)空鏈表(b)非空鏈表程序設(shè)計：p!=NULL 改為 p!=headP->next!=NULL 改為 p->next!=head2.5雙向鏈表雙向鏈表是每個結(jié)點除后繼指針域外還有一個前驅(qū)指針域，它有帶頭結(jié)點和不帶頭結(jié)點，循環(huán)和非循環(huán)結(jié)構(gòu)，雙向鏈表是解決查找前驅(qū)結(jié)點問題的有效途徑。結(jié)點結(jié)構(gòu)如圖示：priordatanext下圖是帶頭結(jié)點的循環(huán)雙向鏈表的結(jié)構(gòu)，可見，其前驅(qū)指針和后繼指針各自構(gòu)成自己的循環(huán)單鏈表。head(a)空鏈表a0a1an-1head(b)非空鏈表…在雙向鏈表中:設(shè)指針p指向第i個數(shù)據(jù)元素結(jié)點，則p->next指向第i+1個數(shù)據(jù)元素結(jié)點，p->next->prior仍指向第i個數(shù)據(jù)元素結(jié)點，即p->next->prior=p;同樣p->prior->next=p。循環(huán)雙向鏈表的插入過程如圖示：a0aian-1head…xs…ai-1××…④①②③p刪除過程如圖示：ai+1aian-1head……ai-1××①②p2.6靜態(tài)鏈表在數(shù)組中增加一個(或兩個)指針域用來存放下一個(或上一個)數(shù)據(jù)元素在數(shù)組中的下標，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。因為數(shù)組內(nèi)存空間的申請方式是靜態(tài)的，所以稱為靜態(tài)鏈表，增加的指針稱做仿真指針。結(jié)構(gòu)如下：ABCE∧headD(a)常規(guī)鏈表A1B2C3D4E-1┇(b)靜態(tài)鏈表1datanext01234┇maxSize-1A2E-1B4D1C3┇(b)靜態(tài)鏈表2datanext01234┇maxSize-12.7設(shè)計舉例例2-4設(shè)計一個順序表的刪除函數(shù)，把順序表L中的數(shù)據(jù)元素x刪除。算法思想：首先，找到要刪除元素的位置，然后，從這個位置到最后一個元素，逐個前移，最后，把元素個數(shù)減1。int

ListDataDelete(SeqList*L,DataTypex){

inti,j;

for(i=0;i<L->size;i++)

if(x==L->list[i])break;

if(i==L->size)return0; else {for(j=i;j<L->size;j++)

L->list[j]=L->list[j+1];

L->size--; return1;}}

例2-5構(gòu)造一個順序表的刪除算法，把順序表L中所有值相同的數(shù)據(jù)元素x全部刪除。算法思想：在例2-4所設(shè)計的刪除算法的基礎(chǔ)上，增加外重循環(huán)進行查找，查找到元素x則刪除，然后繼續(xù)進行這樣的過程和刪除過程，直到元素末尾結(jié)束。int

ListMoreDataDelete(SeqList*L,DataTypex){inti,j;

inttag=0;

for(i=0;i<L->size;i++){if(x==L->list[i]) {for(j=i;j<L->size-1;j++)

L->list[j]=L->list[j+1]; L->size--;

i--;

tag=1; }}

returntag;}例2-6設(shè)頭指針為head，并設(shè)帶頭結(jié)點單鏈表中的數(shù)據(jù)元素遞增有序，編寫算法將數(shù)據(jù)元素x插入到帶頭結(jié)點單鏈表的適當位置上，要求插入后保持單鏈表數(shù)據(jù)元素的遞增有序。算法思想：從鏈表的第一個數(shù)據(jù)元素結(jié)點開始，逐個比較每個結(jié)點的data域值和x的值，當data小于等于x時，進行下一個結(jié)點的比較；否則就找到了插入結(jié)點的合適位置，此時申請新結(jié)點把x存入，然后把新結(jié)點插入；當比較到最后一個結(jié)點仍有data小于等于x時，則把新結(jié)點插入單鏈表尾。voidLinListInsert(SLNode*head,DataTypex){SLNode*curr,*pre,*q;

curr=head->next;pre=head;

while(curr!=NULL&&curr->data<=x){pre=curr;

curr=curr->next;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=pre->next;pre->next=q;}算法設(shè)計說明：（1）在循環(huán)定位插入位置時，循環(huán)條件必須首先是curr!=NULL，然后是curr->data<=x。如果次序顛倒，則當curr為空（即等于鏈表結(jié)束標記NULL