第2章線性表第2章線性表1第2章線性表學習目的要求:線性表的定義和線性表的特征。線性表的順序存儲結構及其算法的實現。線性鏈表的描述及其算法的實現。循環鏈表和雙向循環鏈表的描述。數組的順序存儲和矩陣的壓縮存儲的描述。第2章線性表學習目的要求:線性表的定義和線性表的特征。22.1線性表的基本概念2.2線性表的順序存儲結構及其算法2.3線性表的鏈式存儲結構及其運算2.4算法應用舉例2.5數組第2章線性表2.1線性表的基本概念2.2線性表的順序存儲結構及其算法32.1.1線性表的定義2.1線性表的基本概念線性表（linearlist）是由n個數據元素組成的有限序列。線性表可以用一個標識符來命名，如果用A來表示線性表，則: A=（a1，a2，…，ai，…，an）線性表是一種非常典型的線性結構，用二元組可以表示成:S=（D，R）D=｛a1，a2，…，ai，…，an｝R=｛<a1，a2>，<a2，a3>，…，<ai，ai+1>，…，<an-1，an>｝2.1.1線性表的定義2.1線性表的基本概念線性表（li42.1.2線性表的基本操作（1）InitList（List）:初始化操作，建立一個空的線性表List;（2）ListLength（List）:求線性表的長度;（3）GetElement（List，i）:取線性表中的第i個元素（1≤i≤n，n為線性表長度）;（4）PriorElement（List，x）:若x不是第一個數據元素，則取x的直接前驅;（5）NextElement（List，x）:若x不是最后一個元素，則取x的直接后繼;（6）LocateElement（List，x）:若x存在于表中，則取得x的位置（位序）;（7）ListInsert（List，i，x）:在線性表第i個元素之前插入一個數據元素x;（8）ListDelete（List，i）:刪除線性表中第i個元素（1≤i≤n，n為線性表長度）。2.1線性表的基本概念2.1.2線性表的基本操作（1）InitList（List52.2線性表的順序存儲結構及其算法2.2.1線性表的順序存儲結構線性表的順序存儲結構簡稱為順序表（SequentialList）。順序存儲結構的特點是:在線性表中邏輯關系相鄰的數據元素，在計算機的內存中物理位置也是相鄰的。線性表中第i個元素ai的存儲位置為:

LOC（ai）=LOC（a1）+（i-1）L2.2線性表的順序存儲結構及其算法2.2.1線性表的順序62.2.2順序表的運算1.插入運算插入運算是指在具有n個元素的線性表的第i（1≤i≤n）個元素之前插入一個新元素x。2.2線性表的順序存儲結構及其算法2.2.2順序表的運算1.插入運算插入運算是指在具有n個7intinsertsqlist(inti,elementtypex,SqList*sql){ /*在順序表(*sql)的第i個元素之前插入一個新元素x*/intj;if((i<1)||(i>sql->len)) /*i值非法，返回值為0*/return(0);else{ for(j=sql->len;j>=i;j--) sql->s[j+1]=sql->s[j]; /*向后移動數據，騰出要插入的空位*/ sql->s[j+1]=x; /*修正插入位置為j+1*/ (sql->len)++; /*表長加1*/ return(1); /*插入成功，返回值為1*/}}2.2線性表的順序存儲結構及其算法intinsertsqlist(inti,element82.刪除運算刪除運算是指從具有n個元素的線性表中，刪除其中的第i（1≤i≤n）個元素，使表的長度減1。2.2線性表的順序存儲結構及其算法2.刪除運算刪除運算是指從具有n個元素的線性表中，刪除其中9intdelsqlist(inti,SqList*sql) /*刪除順序表(*sql)的第i個元素*/{intj;if((i<1)||(i>sql->len)) /*i值非法，返回值為0*/return(0);else{for(j=i+1;j<=sql->len;j++)sql->s[j-1]=sql->s[j]; /*向前移動數據，覆蓋前一數據*/(sql->len)--; /*表長度減1*/return(1); /*刪除成功，返回值為1*/}}2.2線性表的順序存儲結構及其算法intdelsqlist(inti,SqList*sq102.3.1線性表的鏈式存儲結構為了表示出每個元素與其直接后繼元素之間的關系，除了存儲元素本身的信息外，還需存儲一個指示其直接后繼的存儲位置信息。typedefstructnode{intdata;structnode*next;}NODE;2.3線性表的鏈式存儲結構及其運算2.3.1線性表的鏈式存儲結構為了表示出每個元素與其直接11線性鏈表是通過結點指針域中的指針表示各結點之間的線性關系的。線性表的每個結點都有一個鏈接指針，所以不要求鏈表中的結點必須按照結點先后次序存儲在一個地址連續的存儲區中。在鏈表中插入或刪除數據元素比在順序表中要容易得多，但是鏈表結構需要的存儲空間較大。2.3線性表的鏈式存儲結構及其運算線性鏈表是通過結點指針域中的指針表示各結點之間的線性關系的。122.3.2單鏈表的運算若線性鏈表的每個結點只含有一個指針域，則稱這樣的線性鏈表為單鏈表。1.建立帶表頭結點的單鏈表建立鏈表時，首先要建立表頭結點，此時為空鏈表。然后將新的結點逐一插入到鏈表中，其過程如下:（1）申請存儲單元，用C語言的動態分配庫函數malloc得到。（2）讀入新結點的數據，新結點的指針域為空。（3）把新結點鏈接到鏈表上去（有前插和后插兩種方式）。重復以上步驟，直到將所有結點都鏈接到鏈表上為止。2.3線性表的鏈式存儲結構及其運算2.3.2單鏈表的運算若線性鏈表的每個結點只含有一個指針域13NODE*create() /*此函數采用后插入方式建立單鏈表*/{NODE*head,*q,*p; /*定義指針變量*/charch;inta;head=(NODE*)malloc(sizeof(NODE)); /*申請新的存儲空間，建立表頭結點*/q=head;ch='*';printf("\nInputthelist:");

2.3線性表的鏈式存儲結構及其運算(Continue…)NODE*create() /*此函數采用后插入方式建14while(ch!='?') /*"ch"為是否建立新結點的標志，若"ch"為"?"則輸入結束*/{scanf("%d",&a); /*輸入新元素*/p=(NODE*)malloc(sizeof(NODE));p->data=a;q->next=p;q=p;ch=getchar(); /*讀入輸入與否的標志*/}q->next=NULL;return(head); /*返回表頭指針head*/}2.3線性表的鏈式存儲結構及其運算while(ch!='?') 2.3線性表的鏈式存儲結152.單鏈表中結點的查找單鏈表有兩種查找方法，即按序號查找和按給定值查找。在單鏈表中，即使知道了要查找的結點的序號，也只能從頭指針開始查找。與順序表不一樣，單鏈表不能實現隨機查找。2.3線性表的鏈式存儲結構及其運算2.單鏈表中結點的查找單鏈表有兩種查找方法，即按序號查找和16NODE*locate(NODE*head,intx)/*在已知鏈表中查找給定的值x*/{NODE*p;p=head->next;while((p!=NULL)&&(p->data!=x))/*未到表尾且未找到給定數據*/p=p->next; /*指向下一個元素*/return(p);}（1）按值查找

2.3線性表的鏈式存儲結構及其運算按值查找，就是在單鏈表中查找是否存在數據域值為給定的值（如整數x）的結點。NODE*locate(NODE*head,intx)17NODE*find(NODE*head,inti)/*在已知鏈表中查找給定的值x*/{intj=1;NODE*p;p=head->next;while((p!=NULL)&&(j<i))/*未到表尾且未找到給定數據*/{p=p->next;/*指向下一個元素*/j++;}return(p);}（2）按序號查找2.3線性表的鏈式存儲結構及其運算在單鏈表中查找第i個位置上的結點，若找到，則返回它的地址，否則返回NULL。NODE*find(NODE*head,inti)183.單鏈表上的插入運算在順序表中，插入運算時，將會有大量元素向后移動。而在單鏈表中，插入一個結點不需要移動元素，只需要修改指針即可。若將x插入到a1和a2之間，其過程如下:（1）建立一個新結點q，將x值賦給q->data。（2）修改有關結點的指針域。2.3線性表的鏈式存儲結構及其運算3.單鏈表上的插入運算在順序表中，插入運算時，將會有大量元19voidinsert(NODE*p,intx) /*在鏈表的p結點后插入給定元素x*/{NODE*q;q=(NODE*)malloc(sizeof(NODE));/*申請新的存儲空間*/q->data=x;q->next=p->next;/*實現圖的①*/p->next=q; /*實現圖的②，將新結點q鏈接到p結點之后*/}2.3線性表的鏈式存儲結構及其運算voidinsert(NODE*p,intx) /*在204.單鏈表上的刪除運算刪除單向鏈表中的結點x，并由系統收回其占用的存儲空間，其過程如下:（1）設定兩個指針p和q，p指針指向被刪除結點，q為跟蹤指針，指向被刪除結點的直接前驅結點。（2）p從表頭指針head指向的第一個結點開始依次向后搜索。當p→data等于x時，被刪除結點找到。（3）修改p的前驅結點q的指針域。使p結點被刪除，然后釋放存儲空間。2.3線性表的鏈式存儲結構及其運算4.單鏈表上的刪除運算刪除單向鏈表中的結點x，并由系統收回21voiddelete(NODE*head,intx) /*刪除鏈表中的給定元素x*/{NODE*p,*q;q=head;p=q->next;while((p!=NULL)&&(p->data!=x)) /*查找要刪除的元素*/{q=p;p=p->next;}if(p==NULL)printf("%dnotfound.\n",x); /*x結點未找到*/else{q->next=p->next; /*鏈接x直接后繼結點*/free(p); /*刪除x結點，釋放x結點空間*/}}2.3線性表的鏈式存儲結構及其運算voiddelete(NODE*head,intx)225.輸出單鏈表若要將單鏈表按其邏輯順序輸出，就必須從頭到尾訪問單鏈表中的每一個結點。voidprint(NODE*head)/*輸出單向鏈表各元素*/{NODE*p;p=head->next;printf("Outputthelist:");while(p!=NULL){printf("%3d",p->data);p=p->next;}}2.3線性表的鏈式存儲結構及其運算5.輸出單鏈表若要將單鏈表按其邏輯順序輸出，就必須從頭到尾232.3.3循環鏈表結構如果將單鏈表最后一個結點的指針指向頭結點，使鏈表形成一個環形，此鏈表就稱為循環鏈表（CircularLinkList）。2.3線性表的鏈式存儲結構及其運算2.3.3循環鏈表結構如果將單鏈表最后一個結點的指針指向頭242.3.4雙向鏈表結構1.雙向鏈表的基本概念在循環鏈表的結點中再增加一個指針域，這個指針直接指向該結點的直接前驅。這樣，鏈表中一個結點就有了兩個指針域，我們把這樣的鏈表稱為雙向鏈表。2.3線性表的鏈式存儲結構及其運算如果每條鏈都構成一個循環鏈表，則稱這樣的鏈表為雙向循環鏈表。2.3.4雙向鏈表結構1.雙向鏈表的基本概念在循環鏈表的252.插入運算在雙向鏈表的p結點之后插入新結點q。2.3線性表的鏈式存儲結構及其運算2.插入運算在雙向鏈表的p結點之后插入新結點q。2.3線26voidinsert（DUPNODE*p，DUPNODE*q）｛ /*把q結點插在雙向鏈表的p結點之后*/q->prior=p;q->next=p->next;（p->next）->prior=q;p->next=q;｝2.3線性表的鏈式存儲結構及其運算voidinsert（DUPNODE*p，DUPNOD273.刪除運算將雙向鏈表中的p結點刪除。2.3線性表的鏈式存儲結構及其運算3.刪除運算將雙向鏈表中的p結點刪除。2.3線性表的28voiddelete（DUPNODE*p） /*在雙向鏈表中刪除結點p*/

｛

（p->prior）->next=p->next;（p->next）->prior=p->prior;free（p）;｝2.3線性表的鏈式存儲結構及其運算voiddelete（DUPNODE*p） /*在29例2.1 有兩個線性表A和B，都是循環鏈表存儲結構，兩個鏈表頭指針分別為head1和head2，將B鏈表鏈接到A鏈表的后面，合并成一個鏈表。2.4算法應用舉例例2.1 有兩個線性表A和B，都是循環鏈表存儲結構，兩個鏈表30例2.2一元多項式的加法運算。設有兩個一元多項式分別為:An（x）=a0+a1x+a2x2+…+anxnBm（x）=b0+b1x+b2x2+…+bmxm多項式中每個非零項的系數用一個結點來表示，結點中含有兩個數據域和一個指針域，兩個數據域分別存放非零項的系數和指數。typedefstructpnode｛intcoef;/*系數以整型為例*/intexp;/*指數*/structpnode*next;｝PNODE;2.4算法應用舉例例2.2一元多項式的加法運算。設有兩個一元多項式分別為:31設有多項式A（x）=1+2x+4x3（1）B（x）=2-2x+3x2（2）2.4算法應用舉例多項式（1）加多項式（2）的和為多項式（3）:R（x）=3+3x2+4x3（3）設有多項式2.4算法應用舉例多項式（1）加多項式（2）的和32數組是線性表的推廣，也是一種常用的數據結構。2.5.1數組的定義數組是由一組具有相同特性的數據元素組成的。數據元素在數組中的相對位置是由其下標來確定的。一旦定義了數組，它的維數和元素數目也就確定了，而且數據元素的下標具有上下界約束關系，并且是有序的。2.5數組數組是線性表的推廣，也是一種常用的數據結構。2.5.1數332.5.2數組的順序存儲結構通常數組采用的是順序存儲結構，即把數組元素順序地存放在一片地址連續的存儲單元中。二維數組存儲地址的計算與一維數組存儲地址的計算類似。假設給定二維數組按行為主順序存儲，則數組中任一元素aij的存儲地址計算公式為2.5數組LOC（a［i］［j］）=LOC（a11）+（（i-1）×n+j-1）×L2.5.2數組的順序存儲結構通常數組采用的是順序存儲結構，342.5.3矩陣的壓縮存儲一般將要壓縮存儲的矩陣分成特殊矩陣和稀疏矩陣。具有相同值的元素和非零元素有一定分布規律的矩陣，稱為特殊矩陣，如三角矩陣帶狀矩陣等。零元素遠遠多于非零元素，并且非零元素的分布沒有規律的矩陣稱為稀疏矩陣。2.5數組2.5.3矩陣的壓縮存儲一般將要壓縮存儲的矩陣分成特殊矩陣351.三角矩陣以對角線劃分，三角矩陣有上三角和下三角兩種。下三角矩陣中的任一非零元素aij（i≥j）的下標和一維數組A的下標K有一個惟一的對應關系，即

K=i*（i-1）/2+j對于n階上三角矩陣，也可以用類似下三角矩陣的方法存儲，其非零元素和一維數組A的下標K的對應關系為:

K=（i-1）*n-（i-1）（i-2）/2+（j-i+1）2.5數組1.三角矩陣以對角線劃分，三角矩陣有上三角和下三角兩種。下362.稀疏矩陣稀疏矩陣一般都采用壓縮存儲的方法來存儲矩陣中的元素。有兩種常用的存儲稀疏矩陣的方法:三元組表法和十字鏈表法。在壓縮存放稀疏矩陣的非零元素時，還要存放此非零元素所在的行號和列號，這種存儲方法稱為三元組表法。2.5數組2.稀疏矩陣稀疏矩陣一般都采用壓縮存儲的方法來存儲矩陣中的37在鏈表中，每個非零元素可用一個含5個域的結點表示，其中row、col和val分別表示該非零元素所在行、列和值，向右域right用以鏈接稀疏矩陣同一行中的非零元素，向下域down用以鏈接稀疏矩陣同一列中下一個非零元素。同一行的非零元素通過right域鏈接成一個線性鏈表，同一列的非零元素通過down域鏈成一個線性鏈表，每個非零元素既是某個行鏈表中的一個結點，又是某個列鏈表中的一個結點。整個稀疏矩陣構成一個十字交叉鏈表，故稱這樣的存儲結構為十字鏈表。2.5數組在鏈表中，每個非零元素可用一個含5個域的結點表示，其中row38用十字鏈表作稀疏矩陣存儲結構時，每個結點除了存儲元素值外，還要存儲該非零元素的行、列的下標和兩個指針。另外還要增設行、列鏈表表頭指針數組。只有在矩陣中非零元素少于一定數量時采用十字鏈表才可能節約存儲空間。2.5數組用十字鏈表作稀疏矩陣存儲結構時，每個結點除了存儲元素值外，還39線性表是一種具有一對一的線性關系的特殊數據結構。線性表有兩種存儲方法:用順序存儲方法來表示這種線性關系，得到順序存儲結構（即順序表）;用鏈式存儲方式來表示這種線性關系，得到線性表的鏈式存儲結構（即鏈表）。線性表的鏈式存儲結構，是通過結點之間的鏈接而得到的，鏈式存儲結構有單鏈表、雙向鏈表和循環鏈表等。單鏈表結點至少有兩個域:一個數據域和一個指針域。雙向鏈表結點至少含有三個域:一個數據域和兩個指針域。本章小結線性表是一種具有一對一的線性關系的特殊數據結構。線性表有兩404.循環鏈表不存在空指針，最后一個結點的指針指向表頭，形成一個首尾相接的環。5.為了處理問題方便，在鏈表中增加一個頭結點。6.順序存儲可以提高存儲單元的利用率，不便于插入和刪除運算。鏈式存儲會占用較多的存儲空間，可以使用不連續的存儲單元，插入、刪除運算較方便。本章小結4.循環鏈表不存在空指針，最后一個結點的指針指向表頭，形成41第2章線性表第2章線性表42第2章線性表學習目的要求:線性表的定義和線性表的特征。線性表的順序存儲結構及其算法的實現。線性鏈表的描述及其算法的實現。循環鏈表和雙向循環鏈表的描述。數組的順序存儲和矩陣的壓縮存儲的描述。第2章線性表學習目的要求:線性表的定義和線性表的特征。432.1線性表的基本概念2.2線性表的順序存儲結構及其算法2.3線性表的鏈式存儲結構及其運算2.4算法應用舉例2.5數組第2章線性表2.1線性表的基本概念2.2線性表的順序存儲結構及其算法442.1.1線性表的定義2.1線性表的基本概念線性表（linearlist）是由n個數據元素組成的有限序列。線性表可以用一個標識符來命名，如果用A來表示線性表，則: A=（a1，a2，…，ai，…，an）線性表是一種非常典型的線性結構，用二元組可以表示成:S=（D，R）D=｛a1，a2，…，ai，…，an｝R=｛<a1，a2>，<a2，a3>，…，<ai，ai+1>，…，<an-1，an>｝2.1.1線性表的定義2.1線性表的基本概念線性表（li452.1.2線性表的基本操作（1）InitList（List）:初始化操作，建立一個空的線性表List;（2）ListLength（List）:求線性表的長度;（3）GetElement（List，i）:取線性表中的第i個元素（1≤i≤n，n為線性表長度）;（4）PriorElement（List，x）:若x不是第一個數據元素，則取x的直接前驅;（5）NextElement（List，x）:若x不是最后一個元素，則取x的直接后繼;（6）LocateElement（List，x）:若x存在于表中，則取得x的位置（位序）;（7）ListInsert（List，i，x）:在線性表第i個元素之前插入一個數據元素x;（8）ListDelete（List，i）:刪除線性表中第i個元素（1≤i≤n，n為線性表長度）。2.1線性表的基本概念2.1.2線性表的基本操作（1）InitList（List462.2線性表的順序存儲結構及其算法2.2.1線性表的順序存儲結構線性表的順序存儲結構簡稱為順序表（SequentialList）。順序存儲結構的特點是:在線性表中邏輯關系相鄰的數據元素，在計算機的內存中物理位置也是相鄰的。線性表中第i個元素ai的存儲位置為:

LOC（ai）=LOC（a1）+（i-1）L2.2線性表的順序存儲結構及其算法2.2.1線性表的順序472.2.2順序表的運算1.插入運算插入運算是指在具有n個元素的線性表的第i（1≤i≤n）個元素之前插入一個新元素x。2.2線性表的順序存儲結構及其算法2.2.2順序表的運算1.插入運算插入運算是指在具有n個48intinsertsqlist(inti,elementtypex,SqList*sql){ /*在順序表(*sql)的第i個元素之前插入一個新元素x*/intj;if((i<1)||(i>sql->len)) /*i值非法，返回值為0*/return(0);else{ for(j=sql->len;j>=i;j--) sql->s[j+1]=sql->s[j]; /*向后移動數據，騰出要插入的空位*/ sql->s[j+1]=x; /*修正插入位置為j+1*/ (sql->len)++; /*表長加1*/ return(1); /*插入成功，返回值為1*/}}2.2線性表的順序存儲結構及其算法intinsertsqlist(inti,element492.刪除運算刪除運算是指從具有n個元素的線性表中，刪除其中的第i（1≤i≤n）個元素，使表的長度減1。2.2線性表的順序存儲結構及其算法2.刪除運算刪除運算是指從具有n個元素的線性表中，刪除其中50intdelsqlist(inti,SqList*sql) /*刪除順序表(*sql)的第i個元素*/{intj;if((i<1)||(i>sql->len)) /*i值非法，返回值為0*/return(0);else{for(j=i+1;j<=sql->len;j++)sql->s[j-1]=sql->s[j]; /*向前移動數據，覆蓋前一數據*/(sql->len)--; /*表長度減1*/return(1); /*刪除成功，返回值為1*/}}2.2線性表的順序存儲結構及其算法intdelsqlist(inti,SqList*sq512.3.1線性表的鏈式存儲結構為了表示出每個元素與其直接后繼元素之間的關系，除了存儲元素本身的信息外，還需存儲一個指示其直接后繼的存儲位置信息。typedefstructnode{intdata;structnode*next;}NODE;2.3線性表的鏈式存儲結構及其運算2.3.1線性表的鏈式存儲結構為了表示出每個元素與其直接52線性鏈表是通過結點指針域中的指針表示各結點之間的線性關系的。線性表的每個結點都有一個鏈接指針，所以不要求鏈表中的結點必須按照結點先后次序存儲在一個地址連續的存儲區中。在鏈表中插入或刪除數據元素比在順序表中要容易得多，但是鏈表結構需要的存儲空間較大。2.3線性表的鏈式存儲結構及其運算線性鏈表是通過結點指針域中的指針表示各結點之間的線性關系的。532.3.2單鏈表的運算若線性鏈表的每個結點只含有一個指針域，則稱這樣的線性鏈表為單鏈表。1.建立帶表頭結點的單鏈表建立鏈表時，首先要建立表頭結點，此時為空鏈表。然后將新的結點逐一插入到鏈表中，其過程如下:（1）申請存儲單元，用C語言的動態分配庫函數malloc得到。（2）讀入新結點的數據，新結點的指針域為空。（3）把新結點鏈接到鏈表上去（有前插和后插兩種方式）。重復以上步驟，直到將所有結點都鏈接到鏈表上為止。2.3線性表的鏈式存儲結構及其運算2.3.2單鏈表的運算若線性鏈表的每個結點只含有一個指針域54NODE*create() /*此函數采用后插入方式建立單鏈表*/{NODE*head,*q,*p; /*定義指針變量*/charch;inta;head=(NODE*)malloc(sizeof(NODE)); /*申請新的存儲空間，建立表頭結點*/q=head;ch='*';printf("\nInputthelist:");

2.3線性表的鏈式存儲結構及其運算(Continue…)NODE*create() /*此函數采用后插入方式建55while(ch!='?') /*"ch"為是否建立新結點的標志，若"ch"為"?"則輸入結束*/{scanf("%d",&a); /*輸入新元素*/p=(NODE*)malloc(sizeof(NODE));p->data=a;q->next=p;q=p;ch=getchar(); /*讀入輸入與否的標志*/}q->next=NULL;return(head); /*返回表頭指針head*/}2.3線性表的鏈式存儲結構及其運算while(ch!='?') 2.3線性表的鏈式存儲結562.單鏈表中結點的查找單鏈表有兩種查找方法，即按序號查找和按給定值查找。在單鏈表中，即使知道了要查找的結點的序號，也只能從頭指針開始查找。與順序表不一樣，單鏈表不能實現隨機查找。2.3線性表的鏈式存儲結構及其運算2.單鏈表中結點的查找單鏈表有兩種查找方法，即按序號查找和57NODE*locate(NODE*head,intx)/*在已知鏈表中查找給定的值x*/{NODE*p;p=head->next;while((p!=NULL)&&(p->data!=x))/*未到表尾且未找到給定數據*/p=p->next; /*指向下一個元素*/return(p);}（1）按值查找

2.3線性表的鏈式存儲結構及其運算按值查找，就是在單鏈表中查找是否存在數據域值為給定的值（如整數x）的結點。NODE*locate(NODE*head,intx)58NODE*find(NODE*head,inti)/*在已知鏈表中查找給定的值x*/{intj=1;NODE*p;p=head->next;while((p!=NULL)&&(j<i))/*未到表尾且未找到給定數據*/{p=p->next;/*指向下一個元素*/j++;}return(p);}（2）按序號查找2.3線性表的鏈式存儲結構及其運算在單鏈表中查找第i個位置上的結點，若找到，則返回它的地址，否則返回NULL。NODE*find(NODE*head,inti)593.單鏈表上的插入運算在順序表中，插入運算時，將會有大量元素向后移動。而在單鏈表中，插入一個結點不需要移動元素，只需要修改指針即可。若將x插入到a1和a2之間，其過程如下:（1）建立一個新結點q，將x值賦給q->data。（2）修改有關結點的指針域。2.3線性表的鏈式存儲結構及其運算3.單鏈表上的插入運算在順序表中，插入運算時，將會有大量元60voidinsert(NODE*p,intx) /*在鏈表的p結點后插入給定元素x*/{NODE*q;q=(NODE*)malloc(sizeof(NODE));/*申請新的存儲空間*/q->data=x;q->next=p->next;/*實現圖的①*/p->next=q; /*實現圖的②，將新結點q鏈接到p結點之后*/}2.3線性表的鏈式存儲結構及其運算voidinsert(NODE*p,intx) /*在614.單鏈表上的刪除運算刪除單向鏈表中的結點x，并由系統收回其占用的存儲空間，其過程如下:（1）設定兩個指針p和q，p指針指向被刪除結點，q為跟蹤指針，指向被刪除結點的直接前驅結點。（2）p從表頭指針head指向的第一個結點開始依次向后搜索。當p→data等于x時，被刪除結點找到。（3）修改p的前驅結點q的指針域。使p結點被刪除，然后釋放存儲空間。2.3線性表的鏈式存儲結構及其運算4.單鏈表上的刪除運算刪除單向鏈表中的結點x，并由系統收回62voiddelete(NODE*head,intx) /*刪除鏈表中的給定元素x*/{NODE*p,*q;q=head;p=q->next;while((p!=NULL)&&(p->data!=x)) /*查找要刪除的元素*/{q=p;p=p->next;}if(p==NULL)printf("%dnotfound.\n",x); /*x結點未找到*/else{q->next=p->next; /*鏈接x直接后繼結點*/free(p); /*刪除x結點，釋放x結點空間*/}}2.3線性表的鏈式存儲結構及其運算voiddelete(NODE*head,intx)635.輸出單鏈表若要將單鏈表按其邏輯順序輸出，就必須從頭到尾訪問單鏈表中的每一個結點。voidprint(NODE*head)/*輸出單向鏈表各元素*/{NODE*p;p=head->next;printf("Outputthelist:");while(p!=NULL){printf("%3d",p->data);p=p->next;}}2.3線性表的鏈式存儲結構及其運算5.輸出單鏈表若要將單鏈表按其邏輯順序輸出，就必須從頭到尾642.3.3循環鏈表結構如果將單鏈表最后一個結點的指針指向頭結點，使鏈表形成一個環形，此鏈表就稱為循環鏈表（CircularLinkList）。2.3線性表的鏈式存儲結構及其運算2.3.3循環鏈表結構如果將單鏈表最后一個結點的指針指向頭652.3.4雙向鏈表結構1.雙向鏈表的基本概念在循環鏈表的結點中再增加一個指針域，這個指針直接指向該結點的直接前驅。這樣，鏈表中一個結點就有了兩個指針域，我們把這樣的鏈表稱為雙向鏈表。2.3線性表的鏈式存儲結構及其運算如果每條鏈都構成一個循環鏈表，則稱這樣的鏈表為雙向循環鏈表。2.3.4雙向鏈表結構1.雙向鏈表的基本概念在循環鏈表的662.插入運算在雙向鏈表的p結點之后插入新結點q。2.3線性表的鏈式存儲結構及其運算2.插入運算在雙向鏈表的p結點之后插入新結點q。2.3線67voidinsert（DUPNODE*p，DUPNODE*q）｛ /*把q結點插在雙向鏈表的p結點之后*/q->prior=p;q->next=p->next;（p->next）->prior=q;p->next=q;｝2.3線性表的鏈式存儲結構及其運算voidinsert（DUPNODE*p，DUPNOD683.刪除運算將雙向鏈表中的p結點刪除。2.3線性表的鏈式存儲結構及其運算3.刪除運算將雙向鏈表中的p結點刪除。2.3線性表的69voiddelete（DUPNODE*p） /*在雙向鏈表中刪除結點p*/

｛

（p->prior）->next=p->next;（p->next）->prior=p->prior;free（p）;｝2.3線性表的鏈式存儲結構及其運算voiddelete（DUPNODE*p） /*在70例2.1 有兩個線性表A和B，都是循環鏈表存儲結構，兩個鏈表頭指針分別為head1和head2，將B鏈表鏈接到A鏈表的后面，合并成一個鏈表。2.4算法應用舉例例2.1 有兩個線性表A和B，都是循環鏈表存儲結構，兩個鏈表71例2.2一元多項式的加法運算。設有兩個一元多項式分別為:An（x）=a0+a1x+a2x2+…+anxnBm（x）=b0+b1x+b2x2+…+bmxm多項式中每個非零項的系數用一個結點來表示，結點中含有兩個數據域和一個指針域，兩個數據域分別存放非零項的系數和指數。typedefstructpnode｛intcoef;/*系數以整型為例*/intexp;/*指數*/structpnode*next;｝PNODE;2.4算法應用舉例例2.2一元多項式的加法運算。設有兩個一元多項式分別為:72設有多項式A（x）=1+2x+4x3（1）B（x）=2-2x+3x2（2）2.4算法應用舉例多項式（1）加多項式（2）的和為多項式（3）:R（x）=3+3x2+4x3（3）設有多項式2.4算法應用舉例多項式（1）加多項式（2）的和