《數據結構》鏈表《數據結構》鏈表a1,a2,a3,…,anSa1,a2,a3,…,anS線性表—順序存儲與鏈式存儲《數據結構》鏈表單鏈表結構a1nexta2nexta1=(structnode*)malloc(sizeof(node));a1->next=NULL;

head->next=a2;

a2->next=NULL;

a2=(structnode*)malloc(sizeof(node));head=a1;

Structnode*head; //指示鏈表頭節點的指針head^鏈表尾節點標志;

^《數據結構》鏈表循環單鏈表結構a1nexta2nexta1=(structnode*)malloc(sizeof(node));head->next=head;

head->next=a2;

a2->next=head;

a2=(structnode*)malloc(sizeof(node));head=a1;

Structnode*head; //指示鏈表頭節點的指針head如何判別鏈表結束？《數據結構》鏈表鏈表操作—搜索指定節點a1nexta2nextif(p->key!=key){q=p;p=p->next;}p=head;

Structnode*head,*q,*p;heada3nextan^while(p){繼續搜索}

q指向anp=NULL;while(p){if(p->key!=key){q=p;p=p->next;}}

p=NULL;搜索失敗;if(p->key!=key){q=p;p=p->next;}elsereturn(p);//返回位置指針《數據結構》鏈表循環鏈表操作—搜索指定節點a1nexta2nextp=head;if(p->key!=key){q=p;p=p->next;}p=head;

Structnode*head,*q,*p;heada3nextannextwhile(p!=head){繼續搜索}

q指向anif(p->key!=key){q=p;p=p->next;}elsereturn(p);//返回位置指針搜索失敗;《數據結構》鏈表鏈表操作—指定節點前插入新節點，遞增有序a1nexta2next若走出while(p){}循環,則p=NULL;p=head;

Structnode*head,*q,*p;heada3nextan^if(p->key>s->key){在a3前插入}if(p->key<s->key){q=p;p=p->next;}q指向anSnextS->next=p;q->next=S;Snext^q->next=S

插入尾部if(p->key<S->key){q=p;p=p->next;}《數據結構》鏈表struct BILLdls_store(structBILL*S,structBILL*head){struct BILL*p,*q;if(!head){ head=S; S->next=NULL; return(S); }p=head;q=p;while(p){ if(p->key<S->key){ q=p; p=p->next; } else{ if(p==head){ S->next=head; head=S; return(S); } q->next=S; S->next=p; return(head); } } }

q->next=S; S->next=NULL;return(head);}待插入節點鏈表頭指針插入表頭插入表尾循環搜索S插入表內《數據結構》鏈表a1nexta2nextS在a1前插入：if(head->key>S->key)heada3nextan^SnextS->next=head;headhead=S;return(S);鏈表操作—新節點在頭部插入《數據結構》鏈表鏈表操作—刪除指定節點a1nexta2nextif(p->key!=key){q=p;p=p->next;}p=head;

Structnode*head,*q,*p;heada3nexta4^頭節點不變if(p->key!=key){q=p;p=p->next;}if(p->key==key){q->next=p->next;free(p);return(head);}free(p);《數據結構》鏈表《數據結構》鏈表heada1nextproa2nextproa3nextproif(p->key<S->key){q=p;p=p->next;}雙鏈表操作—插入節點S，遞增有序SnextproS->next=p;p->pro->next=S;p=head;if(p->key>s->key){S插在p前}p->pro=S;S->pro=p->pro;《數據結構》鏈表StructBILL*dls_store(structBILL*S,structBILL*head){struct BILL*p,*q;if(!head){ S->next=NULL; S->pro=NULL; return(S); }p=head; q=p; while(p){ if(p->key<S->key){ q=p; p=p->next; } else{ if(p==head){ S->next=head; S->pro=NULL; p->pro=S; return(S); } S->next=p; S->pro=p->pro; p->pro->next=S; p->pro=S; return(head); } }q->next=S;S->next=NULL;S->pro=q;return(head);}插入表頭循環搜索S插入表內注意指針修改順序插入表尾雙鏈表節點插入程序《數據結構》鏈表例1.5單鏈表復制（一）a1nexta2nextp=head;

Structnode*head,*head2,*q,*p;heada3nextan^snexthead2虛空q=head2;

申請節點s；

s->data=p->data;

q->next=s;

a1使用空指針while(p){s=(structnode*)malloc(sizeof(node))；s->data=p->data;q->next=s;q=s;p=p->next;}《數據結構》鏈表例1.5單鏈表復制（二）p=head;

Structnode*head,*head2,*q,*p;headan^h2nexthead2q->next=s;

snexta1申請節點san

q=s;

q=head2;

a3nexta2next申請節點h2a1nexthead返回頭指針q=head2->nextfree(head2);return(q);s->data=p->data;

若走出while(p){}則復制過程結束while(p){s=(structnode*)malloc(sizeof(node))；s->data=p->data;q->next=s;q=s;p=p->next;}q->next=NULL;q=head2->next;free(head2);return(q);^《數據結構》鏈表（X?Y）?X=Y（101?111）?101=111（101?111）?111=101節點i指針域=前驅節點i-1的地址?后繼節點i+1的地址異或關系二進制串X二進制串Y用X置換出Y用Y置換出X對稱表結構原理（ξi-1?ξi+1）?ξi-1=ξi+1前驅節點i-1地址后繼節點i+1地址（X?Y）?Y=X（ξi-1?ξi+1）?ξi+1=ξi-1當前節點i指針域指向前趨節點指向后繼節點對稱單鏈表原理《數據結構》鏈表（NULL?ξi）=ξi（000?111）=111（101?000）=101與0異或，結果不變二進制串0二進制串Y還是Y仍是Xan-2=(an-2?an)?an指向前趨節點根據異或原理可以同時指向前趨和后繼對稱單鏈表頭尾處理前趨為空a1nexta2nexta1節點指針域=(0?ξ2)=ξ2heada2a1?a3annextan-1an節點指針域=（ξn-1?0）=ξn-1an=(an-2?an)?an-2an-1nextan-2?an《數據結構》鏈表對稱單鏈表結構a1nexta2nexta2a1?a3annextan-1

an-1nextan-2?anp=head;

Structnode*head,*ps,*p,*q=NULL,*qq,*pp;While(p){if(p->key!=key){ps=q?p->next;q=p;p=ps;}}head當p=an時，q=an-1搜索失敗;當p指向an時，q異或p->next的結果為空《數據結構》鏈表程序1.10對稱表檢索

struct BILL*search(intkey,structBILL*head){ longia; struct BILL*ps,*p,*q,*qq,*pp; p=head; q=NULL; while(p){ if(p->key!=key){ ia=(long)q^(long)(p->next); ps=(structBILL*)ia; q=p; p=ps; } else return(p); } return(NULL);}《數據結構》鏈表矩陣的鏈式存儲—十字鏈表矩陣的每一行用一個循環鏈表描述：行鏈表矩陣的每一列用一個循環鏈表描述：列鏈表節點結構1,1right1,2rightHhead11,3right第一行2,1right3,1rightn,1right1,mright第一列Vhead1《數據結構》鏈表各行列頭指針之間的關系1,1right1,2right1,3right行頭指針鏈2,1right3,1rightn,1right1,mrightn,2rightn,3rightn,mright2,mright3,mrighthead矩陣頭指針HheadnHhead3Hhead2Hhead1Vhead1Vhead2Vhead3Vheadm列頭指針鏈從head開始通過頭指針鏈可以最快的搜索到指定的行列《數據結構》鏈表頭指針數組定義一個矩陣節點類型的輔助數組，存儲行列頭指針輔助數組元素Hhead3HheadnheadHhead2Hhead1輔助數組VheadmVhead1Vhead2Vhead3a1a2a3ana1a2a3am元素之間的地址相鄰表達了頭指針之間的鏈表連接關系數組同時存儲了行列頭指針數組元素個數=MAX(n,m)《數據結構》鏈表程序1.11輔助向量方式的十字鏈表節點插入函數

struct BILL*dls_store(structBILL*s,structBILL*cp){struct BILL*q,*p;q=(*(cp+s->row)).right;if(q==(cp+s->row)){s->right=(cp+s