鏈結(jié)構(gòu)線性表

1、鏈結(jié)構(gòu)線性表鏈結(jié)構(gòu)線性表 2011/03/82 Gmail最近有問(wèn)題，暫時(shí)停用。 提交問(wèn)題和作業(yè)： 標(biāo)題：bio-*3順序表插入刪除操作順序表插入刪除操作 刪除固定位置的元素 插入一個(gè)元素4567順序結(jié)構(gòu)的線性表順序結(jié)構(gòu)的線性表89鏈表插入操作鏈表插入操作1011指針、間接訪問(wèn)、指針的指針指針、間接訪問(wèn)、指針的指針12上機(jī)題：關(guān)于指針的指針上機(jī)題：關(guān)于指針的指針1314鏈結(jié)構(gòu)的線性表鏈結(jié)構(gòu)的線性表 對(duì)外操作 空間擴(kuò)展 時(shí)間效率1515兩種不同類型的鏈表兩種不同類型的鏈表第一種類型：struct Node *head = NULL；第二種類型：struct Node head.link = NU

2、LL; 16171819202121多種形式的鏈表多種形式的鏈表 帶尾指針的單鏈表帶尾指針的單鏈表2222多種形式的鏈表多種形式的鏈表 帶尾指針的單鏈表帶尾指針的單鏈表(續(xù)續(xù))尾部插入： ptr = clist-next; clist-next = newNode; newNode-next = ptr; clist = newNode;頭部刪除： if (ptr = clist-next) != clist) clist-next = clist-next -next; free(ptr); newNodepclista0a2an-12323兩個(gè)循環(huán)鏈表的合并兩個(gè)循環(huán)鏈表的合并palista

3、0an-1pblistb0bn-1palista0an-1pblistb0bn-12424單鏈表缺點(diǎn)：找后繼容易，找前驅(qū)必須從頭開始查找。單鏈表缺點(diǎn)：找后繼容易，找前驅(qū)必須從頭開始查找。雙向鏈表：雙向鏈表： 既可以找前驅(qū)，也可以找后繼。既可以找前驅(qū)，也可以找后繼。infollinkrlink結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)：pdlistk0k1kn-1headrear多種形式的鏈表多種形式的鏈表 雙向鏈表雙向鏈表2525多種形式的鏈表多種形式的鏈表 雙向鏈表的結(jié)構(gòu)定義雙向鏈表的結(jié)構(gòu)定義struct DoubleNode; /* 雙鏈表結(jié)點(diǎn) */typedef struct DoubleNode * PDou

4、bleNode; /*結(jié)點(diǎn)指針類型 */struct DoubleNode /* 雙鏈表結(jié)點(diǎn)結(jié)構(gòu) */DataType info;PDoubleNode llink, rlink;struct DoubleList /* 雙鏈表類型 */ PDoubleNode head; /* 指向第一個(gè)結(jié)點(diǎn) */ PDoubleNode rear; /* 指向最后一個(gè)結(jié)點(diǎn) */; 2626infollinkrlink結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)：pdlistk1k2knheadrear空表判斷空表判斷 ： pdlist-head = NULL最后一個(gè)節(jié)點(diǎn)：最后一個(gè)節(jié)點(diǎn)： p-rlink = NULL第一個(gè)節(jié)點(diǎn)：第一

5、個(gè)節(jié)點(diǎn)： p-llink = NULL 訪問(wèn)第一個(gè)節(jié)點(diǎn)：訪問(wèn)第一個(gè)節(jié)點(diǎn)： pdlist-head訪問(wèn)最后結(jié)點(diǎn)：訪問(wèn)最后結(jié)點(diǎn)： pdlist-rearP-rlink-llink = p-llink-rlink = p272727刪除雙向鏈表的結(jié)點(diǎn)刪除雙向鏈表的結(jié)點(diǎn)ABCpp-llink-rlink = p-rlinkp-rlink-llink = p-llink雙向鏈表結(jié)點(diǎn)刪除雙向鏈表結(jié)點(diǎn)刪除free(p)2828往雙向鏈表中往雙向鏈表中p前插入結(jié)點(diǎn)：前插入結(jié)點(diǎn)：(1) q-llink = p-llink;(2) p-llink-rlink = q;(3) q-rlink = p;(4) p-l

6、link = q;雙向鏈表結(jié)點(diǎn)的插入雙向鏈表結(jié)點(diǎn)的插入p指向結(jié)點(diǎn)后插入新結(jié)點(diǎn)指向結(jié)點(diǎn)后插入新結(jié)點(diǎn):(1) q-llink = p; (3) p-rlink-llink = q; (2) q-rlink = p-rlink; (4) p-rlink = q; ABCqp(1)(2)(4)(3)ABCpq(1)(4)(3)(2)Q = (PDoubleNode)malloc(sizeof(struct DoubleNode)2929struct CDoubleList /* 循環(huán)雙鏈表類型循環(huán)雙鏈表類型 */ PDoubleNode head; /*指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn)CDoubleList cdlist;pdlistk0k1kn-1head3030帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表操作帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表操作 帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表空表判斷空表判斷 ：pdlist-head-rlink = NULL最后結(jié)點(diǎn)判斷：最后結(jié)點(diǎn)判斷：p-rlink=pdlist-head 或或 p =pdlist-head-llink第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn) ：pdlist-head-rlink最后結(jié)點(diǎn)最后結(jié)點(diǎn) ：pdlist-head-llinkpdlistk0k1kn-1head31關(guān)于鏈表的擴(kuò)展話題關(guān)于鏈表的擴(kuò)展話題32用數(shù)組來(lái)實(shí)現(xiàn)鏈表結(jié)構(gòu)用數(shù)組來(lái)實(shí)現(xiàn)鏈表結(jié)構(gòu) struct Node