數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)匯總(共28頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第二章2.1線性表的概念及其抽象數(shù)據(jù)類型的定義2.1.1 線性表的邏輯結(jié)構(gòu)線性表的定義線性表是n個(gè)類型相同的數(shù)據(jù)元素的有限序列，對(duì)n>0,除第一個(gè)元素?zé)o直接前驅(qū)，最后一個(gè)元素?zé)o直接后繼外，其余的每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性表的特點(diǎn)：1） 同一性：線性表有同類元素?cái)?shù)據(jù)組成，每一個(gè)必須屬于同一數(shù)據(jù)類型。2） 有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成，表長就是表中數(shù)據(jù)元素的個(gè)數(shù)。3）有序性：線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。2.1.2線性表的抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義：見課本。2.2線性表的順序存儲(chǔ)2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)的

2、定義線性表的順序存儲(chǔ)結(jié)構(gòu)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素，使得線性表中在邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中，即通過數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系。采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。將線性表歸納為：關(guān)系線性化，節(jié)點(diǎn)順序存。假定順序表中有個(gè)元素，每個(gè)元素占個(gè)單元，第一個(gè)元素的地址為，則可通過如下公式計(jì)算出第個(gè)元素的地址：其中，稱為基地址。線性存儲(chǔ)結(jié)構(gòu)的C語言定義#define MAXSIZE 100typedef structElemType elemMAXSIZE; /*ElemType 可為int，char等*/int la

3、st;/*記錄線性表中最后一個(gè)元素在數(shù)組elem 中的位置(下標(biāo)值)*/Seqlist;上述為定義一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)名為Seqlist。知識(shí)延伸（typedef）（C課本用typedef聲明新類型名）2.2.2 線性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算線性表的基本運(yùn)算1、 查找操作2、 插入操作3、 刪除操作4、 順序表合并算法線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)分析2.3 線性表的鏈?zhǔn)酱鎯?chǔ)鏈表定義：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱為鏈表。鏈表的分類：1） 按實(shí)現(xiàn)角度看：鏈表可分為動(dòng)態(tài)鏈表和靜態(tài)鏈表。2） 按鏈接方式的角度看：鏈表可分為單鏈表、循環(huán)鏈表和雙鏈表。2.3.1 單鏈表2.3.2 單鏈表上的基本操作線性表的基本

4、運(yùn)算1、 初始化單鏈表 InitList(LinkList *L) *L=(LinkList)malloc(sizeof(Node); /*建立頭結(jié)點(diǎn)*/ (*L)->next=NULL;/*建立空的單鏈表L*/ 注意：L是指向單鏈表的頭結(jié)點(diǎn)的指針，用來接收主程序中帶初始化單鏈表的頭指針變量的地址，*L相當(dāng)于主程序中帶初始化單鏈表的頭指針變量。2、 建立單鏈表1）頭插法建表算法描述：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新節(jié)點(diǎn)的數(shù)據(jù)域中，然后將新節(jié)點(diǎn)插入到當(dāng)前鏈表的表頭節(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止。單鏈表的存儲(chǔ)結(jié)構(gòu)：typedef struct Node /*結(jié)點(diǎn)類

5、型定義，結(jié)構(gòu)體名為Node*/ElemType data;struct Node * next;Node,*Linklist; /*LinkList為結(jié)構(gòu)指針類型*/LinkList與Node *同為結(jié)構(gòu)指針類型，這兩種類型是等價(jià)的。通常習(xí)慣上用LinkList說明指針變量，強(qiáng)調(diào)他是某個(gè)單鏈表的頭指針變量。例如，使用定義LinkList L，則L為單鏈表的頭指針，從而提高程序的可讀性。用Node *來定義指向單鏈表中節(jié)點(diǎn)的指針，例如，Node *p，則p為指向單鏈表中節(jié)點(diǎn)的指針變量。算法：typedef struct NodeElemType data;struct Node * next;N

6、ode,*Linklist;void CreatFromHead(LinkList L)Node *s;char c;int flag=1;while(flag)c=getchar();if(c!='$')s=(Node *)malloc(sizeof(Node);s->data=c;s->next=L->next;L->next=s;else flag=0;2） 尾插法建表算法描述：頭插法建立鏈表雖然簡單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者相同，可采用尾插法建表。該方法是將新節(jié)點(diǎn)插到當(dāng)前單鏈表的尾上。為此需增加一個(gè)尾指針r，使之指向當(dāng)

7、前單鏈表的結(jié)尾。算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;void CreatFromHead(LinkList L)Node *s,*r;r=L;char c;int flag=1;while(flag)c=getchar();if(c!='$')s=(Node *)malloc(sizeof(Node);s->data=c;r->next=s;r=s;else flag=0;r->next=NULL;3、 單鏈表查找1） 按序號(hào)查找算法描述：設(shè)帶頭結(jié)點(diǎn)的單鏈表

8、的長度為n，要查找表中第i個(gè)結(jié)點(diǎn)，則需要從單鏈表的頭指針L出發(fā)，從頭結(jié)點(diǎn)(L->next)開始順著鏈域掃描，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，初值指向頭結(jié)點(diǎn),用j做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)(初值為0)，當(dāng)j=i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;Node * Get(LinkList L,int i)int j=0;Node *p;p=L:if(i<=0) return NULL; /*找的序號(hào)太小*/while(p->next!

9、=NULL)&&(j<i)p=p->next;j+;if(p->next=NULL) return NULL; /*找不到i*/else return i; /*找到了i*/2） 按值查找算法描述：按值查找是指在單鏈表中查找是否有節(jié)點(diǎn)值等于e的結(jié)點(diǎn)，若有的話，則返回首次找到的其值等于e的結(jié)點(diǎn)的存儲(chǔ)位置，否則返回NULL。查找過程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值e作比較。 算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;Node *Locat

10、e(LinkList L,ElemType key)Node *p;p=L->next;while(p!=NULL)if(p->data=key)return p; /*找到了key*/p=p->next;return NULL; /*沒有找到了key*/ 4、 單鏈表插入操作問題要求：在線性表的第個(gè)位置之前插入一個(gè)新元素e。算法思想：查找：在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)并有指針pre指示。申請(qǐng)：申請(qǐng)新節(jié)點(diǎn)s，將其數(shù)據(jù)域的值置為e；插入掛鏈：通過修改指針域?qū)⑿鹿?jié)點(diǎn)s掛入單鏈表L。 算法：typedef struct NodeElemType data;struct Node *

11、 next;Node,*Linklist;void Inslist(ElemType e,int i,LinkList L)Node *pre,*s;int k;if(i<=0) return ERROR;pre=L;k=0;while(pre!=NULL&&k<i-1)pre=pre->next;k+;if(k=i)s=(Node *)malloc(sizeof(Node);s->data=e;s->next=pre->next;pre->next=s;return OK;elseprintf("插入位置不合理")

12、;return ERROR;5、 單鏈表刪除問題要求：將線性表的第個(gè)元素e刪除算法思想：查找：通過計(jì)數(shù)方式找到第i-1個(gè)結(jié)點(diǎn)并由指針pre指示；刪除第i個(gè)結(jié)點(diǎn)并釋放結(jié)點(diǎn)空間。結(jié)果：將長度為n的線性表變成長度為n-1 的線性表算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;void DelList(LinkList L,int i,ElemType *e)Node *pre,*s;int k;if(i<=0) return ERROR;pre=L;k=0;/*按序號(hào)查找第i個(gè)位置*/while(pr

13、e->next!=NULL&&k<i)pre=pre->next;k+;if(pre->next=NULL)printf("刪除位置錯(cuò)誤");return ERROR;s=pre->next; /*使得刪除得第i個(gè)位置的指針為s*/pre->next=s->next;*e=s->data;free(s); /*釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間*/return OK;算法應(yīng)用舉例1、 求單鏈表的長度算法描述：可以采用“數(shù)”結(jié)點(diǎn)的方法來求出單鏈表的長度，用指針p依次指向各個(gè)結(jié)點(diǎn)，從第一個(gè)元素開始“數(shù)”，一直“數(shù)”到最

14、后一個(gè)結(jié)點(diǎn)(p->next=NULL).算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;int ListLength(LinkList L)Node *p;int k=0;p=L:while(p->next!=NULL)p=p->next;k+;return k;2、 求兩個(gè)集合的差已知：以單鏈表表示集合，假設(shè)集合A用單鏈表LA表示，集合B用單鏈表LB表示，設(shè)計(jì)算法求兩個(gè)集合的差，即A-B。算法思想：由集合運(yùn)算的規(guī)則可知，集合的差A(yù)-B中包含所有屬于集合A而不屬于集合B的元素。具體做法

15、是，對(duì)于集合A中的每個(gè)元素e，在集合B的鏈表LB中進(jìn)行查找，若存在與e相同的元素，則從LA中將其刪除。算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;void Difference(LinkList LA,LinkList LB)Node *p,*q,*pre,*r;pre=LA;p=LA->next;while(p!=NULL)q=LB->next;while(p->data!=q->data&&q!=NULL) /*查找有無相同元素*/q=q->next

16、;if(p->data=q->data) /*有相同元素*/r=p; pre->next=p->next;/*本來pre->next=p,現(xiàn)改為pre->next=p->next*/p=p->next; /*下一次判斷p->next*/free(r); /*釋放被刪除的元素的空間*/else pre=p; /*也可寫為pre=pre->next*/p=p->next;3、有兩個(gè)單鏈表LA和LB，其元素均為非遞減有序排列，編寫一個(gè)算法，將他們合并成一個(gè)單鏈表LC，要求LC也是非遞減有序排列。要求：新表LC利用現(xiàn)有的表LA和LB中的

17、元素結(jié)點(diǎn)空間，而不要額外申請(qǐng)結(jié)點(diǎn)空間。例如，則。算法思想：要求利用現(xiàn)有的表LA和LB中的結(jié)點(diǎn)空間來建立新表LC，可通過更改結(jié)點(diǎn)的next域來重建新的元素之間的線性關(guān)系。為包證新表仍然遞增有序，可以利用尾插法建立單鏈表的方法，只是新表中的結(jié)點(diǎn)不用malloc，而只要從表LA和LB中選擇合適的點(diǎn)插入新表LC即可。算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;LinkList MergeLinkList(LinkList LA,LinkList LB)Node *pa,*pb,*pc;LinkList LC

18、;/*pa和pb分別指向兩個(gè)單鏈表LA和LB中的將要判斷的結(jié)點(diǎn)，pc初值為LC且pc始終指向LC的表尾*/pa=LA->next;pb=LB->next;LC=LA;LC->next=NULL;/*將LC初始置為空表*/pc=LC; /*pc始終指向LC的表尾*/*當(dāng)兩表均未處理完時(shí)，選擇較小者*/while(pa!=NULL&&pb!=NULL)if(pa->data<=pb->data)pc->next=pa;pc=pc->next;pa=pa->next;elsepc->next=pb;pc=pc->nex

19、t;pb=pb->next;if(pa=NULL)/*表B未處理完*/pc->next=pb;else /*表A未處理完*/pc->next=pa;free(LB); /*表C是以表A為基礎(chǔ)，所以釋放表B*/return LC;2.3.3 循環(huán)鏈表循環(huán)鏈表：循環(huán)鏈表是一個(gè)首尾相接的鏈表。特點(diǎn)：將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈表形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點(diǎn)被鏈在一個(gè)環(huán)上。 帶頭結(jié)點(diǎn)的循環(huán)鏈表的算法和帶頭結(jié)點(diǎn)的單鏈表的算法的區(qū)別僅在與算法中判別當(dāng)前結(jié)點(diǎn)p是否為尾結(jié)點(diǎn)。單鏈表判別條件為，而循環(huán)

20、單鏈表的判別條件為。例題：有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA、LB，編寫算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為LA。算法思想：先找到兩個(gè)鏈表LA、LB的表尾，并分別由指針p，q指向它們，然后將第一個(gè)鏈表的尾與第二個(gè)鏈表的第一個(gè)結(jié)點(diǎn)鏈接起來，并修改第二表的表尾q，使它指向第一個(gè)表的頭結(jié)點(diǎn)。算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;LinkList merge_1(LinkList LA,LinkList LB)Node *p,*q;p=LA;q=LB;/*尋找A的尾結(jié)點(diǎn)，并置為p*/wh

21、ile(p->next!=LA)p=p->next;/*尋找B的尾結(jié)點(diǎn)，并置為q*/while(q->next!=LB)q=q->next;/*修改A的尾指針，并使之為B的第一節(jié)點(diǎn)*/p->next=LB->next;/*修改B的尾指針，并使之為A的頭結(jié)點(diǎn)*/q->next=LA;free(LB);return LA;采用上面的方法，需要遍歷鏈表，找到表尾，其執(zhí)行時(shí)間為。若循環(huán)單鏈表設(shè)置為尾指針表示，在實(shí)現(xiàn)上述合并時(shí)，無需循環(huán)遍歷找尾結(jié)點(diǎn)，只需直接修改尾結(jié)點(diǎn)的指針域，其執(zhí)行時(shí)間是。算法：typedef struct NodeElemType data;

22、struct Node * next;Node,*LinkList;LinkList merge_2(LinkList RA,LinkList LB)Node *p;p=RA->next; /*記錄A的頭結(jié)點(diǎn)*/RA->next=RB->next->next;free(RB->next);RB->next=p;return RB; /*返回新循環(huán)鏈表的尾指針*/2.3.4 雙向鏈表雙向鏈表：給單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其前驅(qū)的指針域prior。雙鏈表的結(jié)點(diǎn)的結(jié)構(gòu)如下圖： prior 前驅(qū)指針域數(shù)據(jù)域后繼指針域 data next雙鏈表的結(jié)構(gòu)定義如下：t

23、ypedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;設(shè)指針p指向雙鏈表中某一點(diǎn)，則有下式成立：1、 雙向鏈表的前插操作算法思想：欲在雙向鏈表第i個(gè)結(jié)點(diǎn)之前插入一個(gè)新的結(jié)點(diǎn)，則指針的變化情況如下圖：算法： typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;int DlinkIns(DoubleList L,int i,ElemType e)DNode *p,*s;int k;if(i<

24、=0)return ERROR;p=L;k=0;while(p!=NULL&&k<i)p=p->next;k+;if(p=NULL)printf("插入位置不合理");return ERROR;s=(DNode *)malloc(sizeof(DNode);s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;return OK; 2、 雙向鏈表的刪除操作算法思想：欲刪除雙向鏈表中的第i個(gè)結(jié)點(diǎn)，則指針的變化情況如下圖所示：算法：

25、typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;int DlinkDel(DoubleList L,int i,ElemType *e)/*將刪除的元素保存到*e中*/DNode *p;int k;if(i<=0)return ERROR;p=L;k=0;while(p!=NULL&&k<i)p=p->next;k+;if(p=NULL)printf("插入位置錯(cuò)誤");return ERROR;*e=p->data;p->

26、;prior->next=p->next;p->next=p->prior;free(p);return OK;3、 應(yīng)用舉例例題：已知：設(shè)一個(gè)循環(huán)雙鏈表編寫一個(gè)算法將鏈表轉(zhuǎn)換為。算法思想：實(shí)際上是交換表中前兩個(gè)元素的次序。算法：typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;void swep(DLinkList L)DNode *p,*q,*r;p=L->next;q=p->next;r=p->prior;p->next=q->n

27、ext;q->next->prior=p;p->prior=q;q->next=p;q->prior=r;L->next=q;return L;2.4 一元多項(xiàng)式的表示及相加2.4.1 一元多項(xiàng)式的表示一元多項(xiàng)式可按升冪的形式寫成：其中，為第項(xiàng)的指數(shù)，是指數(shù)的項(xiàng)的系數(shù)，且。假設(shè)是一個(gè)一元多項(xiàng)式，則它可以用一個(gè)線性表來表示。即：若假設(shè)，則兩個(gè)多項(xiàng)式相加的結(jié)果，也可以用線性表來表示：2.4.2 一元多項(xiàng)式的存儲(chǔ)1、一元多項(xiàng)式的順序存儲(chǔ)表示2、一元多項(xiàng)式的鏈?zhǔn)酱鎯?chǔ)表示在鏈?zhǔn)酱鎯?chǔ)中，對(duì)一元多項(xiàng)式只存非零項(xiàng)，則該多項(xiàng)式中每一項(xiàng)由兩部分組成(指數(shù)項(xiàng)和系數(shù)項(xiàng))，用單鏈表存

28、儲(chǔ)表示的結(jié)點(diǎn)結(jié)構(gòu)如下圖：系數(shù)coef 指數(shù)exp指針next結(jié)點(diǎn)結(jié)構(gòu)定義如下： typedef struct Polynode int coef; int exp; struct Polynode *next; Polynode,* Polylist;建立多項(xiàng)式鏈表：算法描述：通過鍵盤輸入一組多項(xiàng)式的系數(shù)和指數(shù)，用尾插法建立一元多項(xiàng)式鏈表。以輸入系數(shù)0為結(jié)束標(biāo)志，并約定建立多項(xiàng)式鏈表時(shí)，總是按指數(shù)由小到大的順序排列。算法：typedef struct Polynodeint coef;int exp;Polynode *next;Polynode,*Polylist;Polylist Poly

29、Create()Polynode *head,*rear,*s;int c,e;/*申請(qǐng)頭結(jié)點(diǎn)*/head=(Polynode *)malloc(sizeof(Polynode);rear=head; /*rear始終指向最后一個(gè)結(jié)點(diǎn)*/scanf("%d%d",&c,&e);while(c!=0)/*申請(qǐng)一個(gè)新的結(jié)點(diǎn)*/s=(Polynode *)malloc(sizeof(Polynode);s->coef=c;s->exp=e;rear->next=s; /*將鏈表連接起來*/rear=s; /*鏈表的結(jié)尾后移一位*/scanf(&q

30、uot;%d%d",&c,&e);rear->next=NULL;/*結(jié)束鏈表*/return head;/*返回鏈表的頭結(jié)點(diǎn)*/3、 兩個(gè)多項(xiàng)式相加運(yùn)算規(guī)則：指數(shù)相同項(xiàng)的對(duì)應(yīng)系數(shù)相加，若不為0，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)； 指數(shù)不相同的項(xiàng)均按升冪順序復(fù)制到“和多項(xiàng)式” 中。算法思想：設(shè)p、q分別指向單鏈表polya和polyb的當(dāng)前項(xiàng)，比較p、q結(jié)點(diǎn)的指數(shù)項(xiàng)，由此得到以下運(yùn)算規(guī)則：1 若，則結(jié)點(diǎn)p所指的一項(xiàng)應(yīng)該是“和多項(xiàng)式”中的一項(xiàng)，令指針p后移。2 若，則將兩個(gè)結(jié)點(diǎn)的指數(shù)相加，當(dāng)和不為0時(shí)，修改結(jié)點(diǎn)p的系數(shù)域，釋放q結(jié)點(diǎn)；當(dāng)和為0時(shí)，應(yīng)該從polya中刪去p

31、結(jié)點(diǎn)，同時(shí)釋放p和q結(jié)點(diǎn)。3 當(dāng)，則結(jié)點(diǎn)q所指的一項(xiàng)應(yīng)該是“和多項(xiàng)式”中的一項(xiàng)，將結(jié)點(diǎn)q插入在p之前，同時(shí)令指針q后移。算法：typedef struct Polynodeint coef;int exp;Polynode *next;Polynode,*Polylist;void PolyAdd(Polylist polya,Polylist polyb)/*p指向polya的當(dāng)前比較點(diǎn)，q指向polyb的當(dāng)前比較點(diǎn)tail指向和多項(xiàng)式的末尾點(diǎn)*/Polynode *p,*q,*tail,*temp;int sum;p=polya->next;q=polyb->next;tail

32、=polya;while(p!=NULL&&q!=NULL)if(p->exp<q->exp)tail->next=p;tail=p;p=p->next;else if(p->exp=q->exp)sum=p->coef+q->coef;if(sum=0)temp=p;p=p->next;free(p);temp=q;q=q->next;free(q);elsep->coef=sum;tail->next=p;tail=p;p=p->next;temp=q;q=q->next;free(t

33、emp);elsetail->next=q;tail=q;q=q->next;if(p!=NULL)tail->next=p;elsetail->next=q;return polya;假設(shè)A多項(xiàng)式有M項(xiàng)，B多項(xiàng)式有N項(xiàng)，則上述算法的時(shí)間復(fù)雜度為。2.5 順序表和鏈表的綜合比較2.5.1 順序表和鏈表的比較(課本)2.5.2 線性表鏈?zhǔn)酱鎯?chǔ)方式的比較2.6 總結(jié)與提高2.6.1主要知識(shí)點(diǎn)線性表的特征線性表中每個(gè)數(shù)據(jù)元素有且僅有一個(gè)直接前驅(qū)和直接后繼，第一個(gè)結(jié)點(diǎn)無前驅(qū)，最后一個(gè)結(jié)點(diǎn)無后繼。線性表的存儲(chǔ)方式線性表在計(jì)算機(jī)中的存儲(chǔ)方式有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。線性表的順序存儲(chǔ)(順

34、序表)：采用靜態(tài)分配方式，借助于C語言的數(shù)組類型，申請(qǐng)一組連續(xù)的地址空間，依次存放表中元素，其邏輯次序隱含在存儲(chǔ)順序中。線性表的鏈?zhǔn)酱鎯?chǔ)(鏈表)：采用動(dòng)態(tài)分配方式，借助于C語言的指針類型，動(dòng)態(tài)申請(qǐng)與動(dòng)態(tài)釋放地址空間，故鏈表中的各結(jié)點(diǎn)的物理存儲(chǔ)可以是不連續(xù)的。單鏈表的操作特點(diǎn)（1） 順鏈操作技術(shù)：從“頭”開始，訪問單鏈表L中結(jié)點(diǎn)i(p指向該結(jié)點(diǎn))時(shí)，由于第i個(gè)結(jié)點(diǎn)的地址在第i-1個(gè)結(jié)點(diǎn)(pre指向該結(jié)點(diǎn)，為p的前驅(qū))的指針域中存放，查找必須從單鏈表的“首結(jié)點(diǎn)”開始(p=L);通過p=p->next并輔助計(jì)數(shù)器來實(shí)現(xiàn)。（2） 指針保留技術(shù)：通過對(duì)第i個(gè)結(jié)點(diǎn)進(jìn)行插入、刪除等操作時(shí)，需要對(duì)第i-

35、1個(gè)結(jié)點(diǎn)的指針域進(jìn)行鏈址操作(pre->next)，因此在處理過程中始終需要維持當(dāng)前指針p與其前驅(qū)指針pre的關(guān)系，將這種技術(shù)簡稱為“指針保留技術(shù)”。鏈表處理中的相關(guān)技術(shù)（1） 單鏈表與多重鏈表的差別在于指針域的個(gè)數(shù)。（2） 一般鏈表與循環(huán)鏈表的差別在于是否首尾相接，將非空表、空表等多種情況統(tǒng)一處理，以方便運(yùn)算。（3） 判斷當(dāng)前結(jié)點(diǎn)p是否是表尾。一般鏈表中，p結(jié)點(diǎn)是表尾結(jié)點(diǎn)的條件是：該結(jié)點(diǎn)的后繼指針值為空指針，即p->next=NULL;循環(huán)鏈表中，p結(jié)點(diǎn)是表尾結(jié)點(diǎn)的條件是：該結(jié)點(diǎn)的后繼指針值為頭指針值，即p->next=head.（4） 鏈表的表長度并未顯示保存。由于鏈表是

36、動(dòng)態(tài)生成的結(jié)構(gòu)，其長度要通過順鏈查找到表尾得到。因此在處理鏈表時(shí)，往往是以當(dāng)前處理位置是否是表尾作為控制條件，而不是以表長度n作為控制條件。2.6.2 典型例題例1：分解順序表為奇偶兩部分已知順序表L中的數(shù)據(jù)元素類型為int。設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊的元素(即排在前面的)均為奇數(shù)，右邊的所有元素(即排在后面的)均為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1).問題分析：將位于表尾左半部分的偶數(shù)與位于表右半部分的奇數(shù)通過一個(gè)輔助變量進(jìn)行交換。設(shè)置兩個(gè)位置指示器i和j，i的初值為0，j的初值為L->last.當(dāng)L->elemi為偶數(shù)，L->elemj為奇數(shù)是，則將L->elemi與L->elemj交換否則，L->elemi為奇數(shù)，i+，L->elemj為偶數(shù)，j-。這樣既可以保證算法時(shí)間復(fù)雜度為0（n），亦可以保證空間復(fù)雜度為0（1）。算法：#define MaxSize 100typedef structint elemMaxSize;int last;/*記錄線性表中最后一個(gè)元素在數(shù)組elem中的位置(下標(biāo)值)*/SeqList;vo