數(shù)據(jù)結構 c語言版 第2版 教學課件 ppt 李云清 楊慶紅 揭安全 第03章_線性表（ii）

1、數(shù)據(jù)結構,李云清 楊慶紅 揭安全,高等學校精品課程,人民郵電出版社,（第2版）,數(shù)據(jù)結構,揭安全,江西省高等學校精品課程,E_mail: jieanquan@163.com,江西師范大學計算機信息工程學院,第3章 線性表的鏈式存儲,鏈式存儲,單鏈表,帶頭結點的單鏈表,循環(huán)單鏈表,,,,雙鏈表,鏈式棧,鏈式隊列,線性表的存儲方式除了常用的順序存儲外，采用鏈式方式存儲也是一種常見的方式。本章將介紹一般線性表的幾種鏈式存儲實現(xiàn)方式，如單

2、鏈表、帶頭結點單鏈表、循環(huán)單鏈表、雙鏈表以及特殊的線性表------棧和隊列的鏈式存儲實現(xiàn)。,3.1鏈式存儲,數(shù)據(jù)結構的存儲方式必須體現(xiàn)它的邏輯關系 。在鏈式存儲方式下，實現(xiàn)中除存放一個結點的信息外，還需附設指針，用指針體現(xiàn)結點之間的邏輯關系。如果一個結點有多個后繼或多個前驅(qū)，那么可以附設相應個數(shù)的指針，一個結點附設的指針指向的是這個結點的某個前驅(qū)或后繼。,線性結構中，每個結點最多只有一個前驅(qū)和一個后繼，這里暫且設定更關心它的后繼，這樣

3、在存儲時除了存放該結點的信息外，只要附設一個指針即可，該指針指向它的后繼結點的存放位置。每個結點的存儲形式是：,例，數(shù)據(jù)的邏輯結構B=（K，R）其中 K={k1,k2,k3,k4,k5} R={r} R={,,,}是一個線性結構，它的鏈式存儲如圖所示,為了清晰，上圖可以更簡潔地用下圖表示。,3.2 單鏈表,單鏈表是線性表鏈式存儲的一種形式，其中的結點一般含有兩個域，一個是存放數(shù)據(jù)信息的info域，另一個是指

4、向該結點的后繼結點的存放地址的指針域next。一個單鏈表必須有一個首指針指向單鏈表中的第一個結點。,,◎,,◎,,◎,數(shù)據(jù)域,指針域,…,節(jié)點,直觀化的描述方法：,單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例如：若頭指針名是head，則把鏈表稱為表head。,,head,,(a) 非空表,head=NULL,(b) 非空表,3.2.2單鏈表的實現(xiàn),單鏈表結構的C語言描述如下：/????????????????????

5、?????????????????????//? 鏈表實現(xiàn)的頭文件,文件名slnklist.h   ?//?????????????????????????????????????????/ typedef int datatype; typedef struct link_node{ datatype info; struct link_node ?next; }node;,單鏈表

6、幾個基本操作的具體實現(xiàn)：,建立一個空的單鏈表 /???????????????????????????????????????????????????//? 函數(shù)功能:建立一個空的單鏈表 ?//? 函數(shù)參數(shù):無 ?//? 函數(shù)返回值:指向node類型變量的指針 ?//? 文件名:slnklist.c,函數(shù)名:init() ?//?

7、??????????????????????????????????????????????????/ node ?init() /?建立一個空的單鏈表?/ { return NULL; }算法3.1 建立一個空的單鏈表,輸出單鏈表中各個結點的值 void display(node ?head){ node ?p; p=head; if(!p) printf(&

8、quot;\n單鏈表是空的！"); else { printf("\n單鏈表各個結點的值為:\n"); while(p) { printf("%5d",p->info);p=p->next;} } } 算法3.2輸出單鏈表中各個結點的值,在單鏈表中查找一個值為x的結點 node ?fin

9、d(node ?head,int i) { int j=1; node ?p=head; if(inext;j++; } return p; }算法3.3 在單鏈表中查找一個值為x的結點,單鏈表的插入過程見下圖所示 ：,,(2) head=p;,(1),(1) p->next=head;,(a) 在單鏈表的最前面插入一個值為x的新結點,單鏈表的插入過程見下圖所示 ：,,∧,,,,,,head,

10、(2),,(2) head=p;,(a) 在單鏈表的最前面插入一個值為x的新結點,(1),(1) p->next=head;,單鏈表的插入過程見下圖所示 ：,,(b) 在q所指的結點后插入一個p所指的值為x的新結點,(1) p->next=q->next;,(1),單鏈表的插入過程見下圖所示 ：,head,,,,,,(b) 在q所指的結點后插入一個p所指的值為x的新結點,(1) p->next=q->nex

11、t;,p,q,(2) q->next=p;,(1),(2),/?????????????????????????????????????????????????????//? 函數(shù)功能:單鏈表第i個結點后插入值為x的新結點    ?//? 函數(shù)參數(shù):指向node類型變量的指針head   ?//? datatype

12、類型變量x,int型變量I ?//? 函數(shù)返回值:指向node類型變量的指針   ?//? 文件名:slnklist.c,函數(shù)名:insert()    ?//?????????????????????????????????????????????????????/ node ?insert(node ?head,d

13、atatype x,int i) { node ?p,?q; q=find(head,i);/?查找第i個結點?/ if(!q&&i!=0) printf("\n找不到第%d個結點,不能插入%d！",i,x); else{ p=(node?)malloc(sizeof(node));/?分配空間?/ p->info=

14、x;/?設置新結點?/,if(i==0){/* 插入的結點作為單鏈表的第一個結點*/ p->next=head;/?插入(1)?/ head=p;/?插入(2)?/ } else { p->next=q->next;/?插入(1)?/

15、 q->next=p;/?插入(2)?/ } } return head; }算法3.4 在單鏈表中第i個結點后插入一個值為x的新結點,刪除操作見下圖所示：,∧,,,,,,,head,(1) head=head->next;,(a) 刪除單鏈表的最前面的（第一個）結點,(2) free(p),,刪除操作見下圖所示：,∧,,,,,head,(1) head=h

16、ead->next;,(a) 刪除單鏈表的最前面的（第一個）結點,(2) free(p),(b) 刪除p指向的結點，pre為p的前驅(qū)結點,(1) pre->next=p->next;,head,,,,(b) 刪除p指向的結點，pre為p的前驅(qū)結點,(1) pre->next=p->next;,head,,,(1),(b) 刪除p指向的結點，pre為p的前驅(qū)結點,(1) pre->next=p->

17、;next;,head,,pre,,(1),(2) free(p),/???????????????????????????????????????????????????//? 函數(shù)功能:在單鏈表中刪除一個值為x的結點 ?//? 函數(shù)參數(shù):指向node類型變量的指針head ?//? datatype 類型變量x ?//? 函數(shù)返回值:指向node類型變量的指針

18、 ?//? 文件名:slnklist.c,函數(shù)名:dele() ?//???????????????????????????????????????????????????/ node ?dele(node ?head,datatype x) { node ?pre=NULL,?p; if(!head) {printf("單鏈表是空的！");return head;} p

19、=head; while(p&&p->info!=x)/?沒有找到并且沒有找完?/ {pre=p;p=p->next;}/?pre指向p的前驅(qū)結點?/ if(!pre&&p->info==x)/?要刪除的是第一個結點?/ head=head->next;/?刪除(1)?/,else pre->next=p->next

20、; free(p); return head; }算法3.5 在單鏈表中刪除一個值為x的結點,鏈式存儲的插入和刪除操作比順序存儲方便，但不能隨機訪問某個結點！,3.3 帶頭結點單鏈表,3.3.1帶頭結點單鏈表,帶頭結點單鏈表見下圖所示：,3.3.2帶頭結點單鏈表的實現(xiàn),一般的單鏈表中，第一個結點由head指示，而在帶頭結點單鏈表中，head指示的是所謂的頭結點，它不是存儲數(shù)據(jù)結構中的實際結點，第一個實際的結點是

21、head->next指示的。在帶頭結點單鏈表的操作實現(xiàn)時要注意這一點。,node ?init() { node ?head; head=(node?)malloc(sizeof(node)); head->next=NULL; return head; }算法3.6 建立一個空的帶頭結點的單鏈表,void display(node ?head) { node ?p; p=head

22、->next;/?從第一個（實際）結點開始?/ if(!p) printf("\n帶頭結點的單鏈表是空的!"); else { printf("\n帶頭結點的單鏈表各個結點的值為:\n"); while(p) { printf("%5d",p->info);p=p->next;} } }算法3

23、.7 輸出帶頭結點的單鏈表中各個結點的值,/?????????????????????????????????????????????????????//? 函數(shù)功能:在帶頭結點的單鏈表中查找第i個結點地址?//? 函數(shù)參數(shù):指向node類型變量的指針head?//? int類型變量i?//? 函數(shù)返回值:指向node類型變量的指針head?//? 文件名hlnklis

24、t.c,函數(shù)名find()?//?????????????????????????????????????????????????????/ node ?find(node ?head,int i) { int j=0; node ?p=head; if(i<0){printf("\n帶頭結點的單鏈表中不存在第%d個結點！",i);return NULL;} else if

25、(i==0) return p;/*此時p指向的是頭結點*/,while(p&&i!=j)/?沒有查找完并且還沒有找到?/ { p=p->next;j++;/?繼續(xù)向后（左）查找,計數(shù)器加1?/ } return p;/?返回結果,i=0時,p指示的是頭結點?/ }算法3.8 在帶頭結點的單鏈表中查找第i個結點,帶頭結點單鏈表的插入過程見圖3.7 ：,帶頭

26、結點的單鏈表的插入操作的具體實現(xiàn)見算法3.9。 /????????????????????????????????????????????????????/ /? 函數(shù)功能:在帶頭結點的單鏈表中第i個結點后插入一個值為x的新結點          ?//? 函數(shù)參數(shù):指向node類型變量的指針head ?/

27、/? datatype 類型變量x,int型變量i ?//? 函數(shù)返回值:指向node類型變量的指針head ?//? 文件名:hlnklist.c,函數(shù)名:insert() ?//????????????????????????????????????????????????????/ node ?insert(node

28、 ?head,datatype x,int i) { node ?p,?q; q=find(head,i);/?查找?guī)ь^結點的單鏈表中的第i個結點?/ /?i=0,表示新結點插入在頭結點之后,此時q指向的是頭結點?/,if(!q)/?沒有找到?/ { printf("\n帶頭結點的單鏈表中不存在第%d個結點！不能插入%d！",i,x);return head;}

29、 p=(node?)malloc(sizeof(node));/?為準備插入的新結點分配空間?/ p->info=x;/?為新結點設置值x?/ p->next=q->next;/?插入(1)?/ q->next=p;/?插入(2),當i=0時,由于q指向的是頭結點,本語句等價于head>next=p ?/ return head; }算

30、法3.9 在帶頭結點的單鏈表中第i個結點后插入一個值為x的新結點,帶頭結點單鏈表的刪除過程見圖3.8。,,,,∧,,,,,,,head ×,q,,(1) head->next=q->next;,(a) 刪除帶頭結點單鏈表的最前面的（第一個）實際結點,(1) (1),,node ?dele(node ?head,datatype x) { node ?pre=

31、head,?q;/?首先pre指向頭結點?/ q=head->next;/?q從帶頭結點的第一個實際結點開始找值為x的結點?/ while(q&&q->info!=x)/?沒有查找完并且還沒有找到?/ {pre=q;q=q->next;}/?繼續(xù)查找,pre指向q的前驅(qū)?/ if (q) {pre->next=q->next;/?刪除?/

32、 free(q);}/?釋放空間?/ return head; }算法3.10 在帶頭結點的單鏈表中刪除一個值為x的結點,算法設計題：1、用單鏈表作為存儲結構，實現(xiàn)線性表（a0,a1,…, an-1）就地逆置的操作，所謂就地指輔助空間應為O(1)。2、設單鏈表L是一個遞減有序表，試寫一算法將X插入其中后仍保持L的有序性。3、寫一算法將單鏈表中值重復的結點刪除，使所得的結果表中各結點值均不相同。4

33、、設計一個算法，對單鏈表按結點值從小到大對結點進行排序。,算法設計題：5、設計一個算法，將兩個有序單鏈表合并成一個有序的單鏈表。6、設計一個算法，求兩個單鏈表表示的集合的交集，并將結果用一個新的單鏈表保存并返回。,10,,^,,p,鏈表插入排序演示,50,,,10,,^,,,,head,^,,s,^,50,,10,,^,,,,head,^,,s,^,q=head->next,while ( q && q->

34、;datadata ) { },pre=q; q=q->next;,循環(huán)結束時，將s結點加在pre與q所指示的結點之間！,50,,10,,^,,,,head,^,,s,^,q=head->next,while ( q && q->datadata ) {

35、 },pre=q; q=q->next;,s->next=q;pre->next=s;,50,,10,,^,,,,head,^,q=head->next,while ( q && q->datadata ) { },pre=q; q=q->next;,s->next=q;pre->next

36、=s;,,50,,40,,,10,,^,,,,head,^,q=head->next,while ( q && q->datadata ) { },pre=q; q=q->next;,s->next=q;pre->next=s;,,,,,算法設計題：多相式相加問題:A(x)=7+3x+9x8+5x17B(x

37、)=8x+22x7-9x8,3.4 循環(huán)單鏈表,3.4.1 循環(huán)單鏈表,循環(huán)單鏈表類型的描述 （略）,3.4.2循環(huán)單鏈表的實現(xiàn),單鏈表中某個結點p是表中最后一個結點的特征是p->next==NULL。對于一個循環(huán)單鏈表，若首指針為head，表中的某個結點p是最后一個結點的特征應該是p->next==head。 循環(huán)單鏈表的頭文件和單鏈表的相同。,建立一個空的循環(huán)單鏈表 /????????

38、??????????????????????????????????????????//? 函數(shù)功能:建立一個空的循環(huán)單鏈表 ?//? 函數(shù)參數(shù):無 ?//? 函數(shù)返回值:指向node類型變量的指針 ?//? 文件名:clnklist.c,函數(shù)名init() ?//??????????????????????????????????????????????

39、????/ node ?init()/?建立一個空的循環(huán)單鏈表?/ { return NULL; }算法3.11 建立一個空的循環(huán)單鏈表,/??????????????????????????????????????????????????????//? 函數(shù)功能:獲得循環(huán)單鏈表的最后一個結點的存儲地址 ?//? 函數(shù)參數(shù):指向node類型變量的指針變量head ?//? 函數(shù)返回值:

40、指向node類型變量的指針 ?//? 文件名:clnklist.c,函數(shù)名:rear() ?//??????????????????????????????????????????????????????/ node ?rear(node ?head) { node ?p; if(!head)/?循環(huán)單鏈表為空?/ p=NULL; else {

41、 p=head;/?從第一個結點開始?/ while(p->next!=head)/?沒有到達最后一個結點?/ p=p->next;/?繼續(xù)向后?/,} return p; }算法3.12 獲得循環(huán)單鏈表的最后一個結點的存儲地址,/??????????????????????????????????????????????????

42、???//? 函數(shù)功能:輸出循環(huán)單鏈表中各個結點的值 ?//? 函數(shù)參數(shù):指向node類型變量的指針變量head ?//? 函數(shù)返回值:空 ?//? 文件名:clnklist.c,函數(shù)名:display() ?//????

43、?????????????????????????????????????????????????/ void display(node ?head) { node ?p; if(!head) printf("\n循環(huán)單鏈表是空的！\n"); else { printf("\n循環(huán)單鏈表各個結點的值分別為:\n"); printf(&qu

44、ot;%5d",head->info);/?輸出非空表中第一個結點的值?/,p=head->next;/?p指向第一個結點的下一個結點?/ while(p!=head)/?沒有回到第一個結點?/ { printf("%5d",p->info); p=p->next; } } }算法3.

45、13 輸出循環(huán)單鏈表中各個結點的值,/?????????????????????????????????????????????????????//? 函數(shù)功能:循環(huán)單鏈表中查找值為x的結點的存儲地址 ?//? 函數(shù)參數(shù):指向node類型變量的指針變量head   ?//? datatype類型的變量x  

46、 ?//? 函數(shù)返回值:指向node類型變量的指針   ?//? 文件名:clnklist.c,函數(shù)名:find()   ?//?????????????????????????????????????????????????????/ node ?find(node ?head,datatype x) { /?查找一個值

47、為x的結點?/ node ?q; if(!head)/?循環(huán)單鏈表是空的?/ { printf("\n循環(huán)單鏈表是空的！無法找指定結點！"); return NULL;,} q=head;/? q指向循環(huán)單鏈表的第一個結點,準備查找?/ while(q->next!=head&&q->info!=x)/?沒有查找到并且沒有

48、查找完整個表?/ q=q->next;/?繼續(xù)查找?/ if(q->info==x) return q; else return NULL; }算法3.14 在循環(huán)單鏈表中查找一個值為x的結點,循環(huán)單鏈表的插入過程如圖 ：,,,,,,,,,head ×,p,,(2) (1),(2),,re

49、ar,(a) 在循環(huán)單鏈表的最前面插入一個值為x的新結點,,,,,(3) (3)×,,(1) p->next=head;,(2) head=p;,(3) rear->next=p;,循環(huán)單鏈表的插入過程如圖 ：,,,,head,,,(2) (1),(2)×,q p,,,(b) 循環(huán)單鏈表，在q所指的結點后插入一個p所指的值為x的新結點,(1) p->next=q->

50、;next;,,,,,,,(2) q->next=p;,/???????????????????????????????????????????????????????//? 函數(shù)功能:循環(huán)單鏈表第i個結點后插入值為x的新結點 ?//? 函數(shù)參數(shù):指向node類型變量的指針變量head  ?//? datatype類型的變量x,int類型的變量I  

51、  ?//? 函數(shù)返回值:指向node類型變量的指針?//? 文件名:clnklist.c,函數(shù)名:insert()  ?//???????????????????????????????????????????????????????/ node ?insert(node ?head,datatype x,int i) {/*i為0時表示將值為x的結點插入作為循環(huán)單鏈表的

52、第一個結點*/ node ?p,?q,*myrear; int j; p=(node?)malloc(sizeof(node)); /?分配空間?/ p->info=x;/?設置新結點的值?/ if(i<0)/?如果i小于0,則輸出出錯信息?/ {printf("\n無法找到指定的插入位置！"); free(p);return head;},if(

53、i==0&&!head)/?插入前循環(huán)單鏈表如果是空的,則新結點的指針域應指向它自己?/ { p->next=p;head=p;return head;} if(i==0&&head)/*在非空的循環(huán)單鏈表最前面插入*/ { myrear=rear(head);/?找到循環(huán)單鏈表的最后一個結點?/ p->next=head;/?插

54、入(1)?/ head=p; /?插入(2)?/ myrear->next=p;/?插入(3)最后一個結點的指針域指向新插入的表中第一個結點?/ return head;} if(i>0&&!head) {printf("\n無法找到指定的插入位置！"); free(p);return head;} if(i>

55、0&&head){/*在非空的循環(huán)單鏈表中插入值為x的結點,并且插入的結點不是第一個結點*/,q=head;/?準備從表中第一個結點開始查找?/ j=1;/?計數(shù)開始?/ while(i!=j&&q->next!=head)/?沒有找到并且沒有找遍整個表?/ {

56、 q=q->next;j++;/?繼續(xù)查找,計數(shù)器加1?/ } if(i!=j) /? 找不到指定插入位置,即i的值超過表中結點的個數(shù),則不進行插入?/ { printf("\n表中不存在第%d個結點,無法進行插入!\n",i); free(p);

57、 return head; } else,else {/?找到了第i個結點,插入x?/ p->next=q->next;/?插入,修改指針(1)?/ q->next=p;/?插入,修改指針(2)?/

58、 return head; } } }算法3.15 在循環(huán)單鏈表中第i個結點后插入一個值為x的新結點,循環(huán)單鏈表的刪除過程如圖 ：,,,,,,,,head ×,q,,(1) head=head->next; (2) pre->next=head;,(a) 刪除循環(huán)單鏈表的最前面的（第一個）結點,(1) (1),,,,,,pre,

59、,(2) × (2),循環(huán)單鏈表的刪除過程如圖 ：,/?????????????????????????????????????????????????????//? 函數(shù)功能:在循環(huán)單鏈表中刪除一個值為x的結點 ?/ /? 函數(shù)參數(shù):指向node類型變量的指針變量head ?//? datatype類型的

60、變量x ?//? 函數(shù)返回值:指向node類型變量的指針 ?//? 文件名:clnklist.c,函數(shù)名:dele() ?//?????????????????????????????????????????????????????/ node ?dele(node ?head,datatype x) {

61、 node ?pre=NULL,?q;/?q用于查找值為x的結點,pre指向q的前驅(qū)結點?/ if(!head)/?表為空,則無法做刪除操作?/ { printf("\n循環(huán)單鏈表為空,無法做刪除操作！"); return head; },q=head;/?從第1個結點開始準備查找?/ while(q->next!=head&&a

62、mp;q->info!=x)/?沒有找遍整個表并且沒有找到?/ { pre=q; q=q->next;/?pre為q的前驅(qū),繼續(xù)查找?/ }/?循環(huán)結束后,pre為q的前驅(qū)?/ if(q->info!=x)/?沒找到?/ { printf("沒有找到值為%d的結點！",x); } e

63、lse/?找到了,下面要刪除q?/ { if(q!=head){pre->next=q->next;free(q);} else,if(head->next==head){free(q);head=NULL;} else { pre=head->next; while(pre->next!

64、=q) pre=pre->next;/*找q的前驅(qū)結點位置*/ head=head->next; pre->next=head; free(q); } } return head; }算法3.16 在循環(huán)單鏈表中刪除一個值為x的結點,3．循環(huán)單鏈表的整體插入與刪除操作,圖3.12 一個循環(huán)單鏈表

65、整體插入到一個單鏈表前部的圖示,3.5 雙鏈表,3.5.1 雙鏈表,前面的各種鏈式表中，一個結點的指針域是指向它的后繼結點的，如果需要找一個結點p的前驅(qū)結點，則必須從表首指針開始查找，當某個結點pre的指針域指向的是結點p時，即pre->next==p時，則說明pre是p的前驅(qū)結點。如果常常需要知道一個結點的前驅(qū)和后繼結點，上述的鏈式表是不適合的。既然單鏈表中每個結點有一個指針域指向它的后繼結點，那自然地想到再增設一個指針域指

66、向它的前驅(qū)結點，這就構成了雙鏈表。,雙鏈表的結點包括三個域，一個是存放數(shù)據(jù)信息的info域，另外兩個是指針域，這里用llink和rlink表示，llink指向它的前驅(qū)結點，rlink指向它的后繼結點。,雙鏈表的一般情形如圖所示：,雙鏈表類型的描述（略?。?3.5.2 雙鏈表的實現(xiàn),雙鏈表結構的C語言描述如下：/???????????????????????????????????????//? 雙鏈表的頭文件,文件名dlnklist

67、.h  ?//???????????????????????????????????????/ typedef int datatype; typedef struct dlink_node{ datatype info; struct dlink_node ?llink,?rlink; }dnode;,/??????????????????????????????????????????????

68、????//? 函數(shù)功能:輸出雙鏈表中各個結點的值 ?//? 函數(shù)參數(shù):指向dnode類型變量的指針head ?//? 函數(shù)返回值:空 ?//? 文件名:dlnklist.c,函數(shù)名:display() ?//??????????????????????????????????????????????????/ void display(dnode ?head) { dno

69、de ?p; printf("\n"); p=head; if(!p) printf("\n雙鏈表是空的!\n"); else { printf("\n雙鏈表中各個結點的值為:\n"); while(p) { printf("%5d",p->info);p=p->rlink;} } }

70、 算法3.18 輸出雙鏈表中各個結點的值,dnode ?find(dnode ?head,int i) { int j=1; dnode ?p=head; if(irlink;j++;/?繼續(xù)沿著右指針向后查找,計數(shù)器加1?/ } if(!p){printf("\n第%d個結點不存在!\n",i);return NULL;} return p; }算法3.1

71、9 查找雙鏈表中第i個結點,雙鏈表插入過程如下圖所示：,雙鏈表插入過程如下圖所示：,,∧,,,,,,,,,head,(1) p->rlink=q->rlink; (2) p->llink=q; (3) q->rlink->llink=p; (4) q->rlink=p;,,,,,,,,,(2) (4) (3) (1),q,,x,,,p,,,(4)××(3),,

72、(b) 在雙鏈表中q所指結點的后面插入一個值為x的新結點,,雙鏈表插入過程如下圖所示：,,∧,,,,,,,,,(1) p->rlink=q->rlink (=NULL); (2) p->llink=q; (4) q->rlink=p;,,,(2) (4) (1),q,x,∧

73、,,p,,,(c) 在雙鏈表中q所指結點（是最后一個結點）的后面插入一個值為x的新結點,head,,,/?????????????????????????????????????????????????????//? 函數(shù)功能:雙鏈表第i個結點后插入值為x的新結點 ?//? 函數(shù)參數(shù):指向dnode類型變量的指針head ?//? datatype類型的變量x, int

74、類型的變量 ?//? 函數(shù)返回值:指向dnode類型變量的指針 ?//? 文件名:dlnklist.c,函數(shù)名:insert() ?//?????????????????????????????????????????????????????/dnode *insert(dnode *head,datatype x,int i) { dnode