數(shù)據(jù)結(jié)構(gòu)___頭插法和尾插法建立鏈表(各分有無頭結(jié)點(diǎn))

1、實(shí)驗(yàn)一鏈表的建立及基木操作方法實(shí)現(xiàn)一、【實(shí)驗(yàn)?zāi)康摹?、理解和掌握單鏈表的類型定義方法和結(jié)點(diǎn)生成方法。2、掌握利用頭插法和尾插法建立單鏈表和顯示單鏈表元素的算法。3、掌握單鏈表的查找（按序號(hào)）算法。4、掌握單鏈表的插入、刪除算法。二、【實(shí)驗(yàn)內(nèi)容】1、利用頭插法和尾插法建立一個(gè)無頭結(jié)點(diǎn)單鏈表，并從屏幕顯示單鏈表元素列表。2、利用頭插法和尾插法建立一個(gè)冇頭結(jié)點(diǎn)單鏈表，并從屏幕顯示單鏈表元素列表。3、將測(cè)試數(shù)據(jù)結(jié)果用截圖的方式粘貼在程序代碼后面。重點(diǎn)和難點(diǎn)：尾插法和頭插法建立單鏈表的區(qū)別。建立帶頭結(jié)點(diǎn)和無頭結(jié)點(diǎn)單鏈表的區(qū)別。帶頭結(jié)點(diǎn)和無頭結(jié)點(diǎn)單鏈表元素顯示方法的區(qū)別三、【算法思想】1）利用頭插法和尾插

2、法建立一個(gè)無頭結(jié)點(diǎn)單鏈表鏈表無頭結(jié)點(diǎn)，則在創(chuàng)建鏈表時(shí)，初始化鏈表指針l=null。當(dāng)用頭插法插入元素時(shí)，首先要判斷頭指針是否為空，若為空，則直接將新結(jié)點(diǎn)賦給l,新 結(jié)點(diǎn)next指向空，即l=p,p->next=null,若表中已經(jīng)有元素了，則將新結(jié)點(diǎn)的next指向首 結(jié)點(diǎn)，然后將新結(jié)點(diǎn)賦給l即（p->next=l,l=p）o當(dāng)用尾插法插入元素時(shí)，首先設(shè)置一個(gè)尾指針tailpointer以便隨時(shí)指向最后一個(gè)結(jié)點(diǎn)，初始 化tailpointer和頭指針一樣即tailpointer=lc插入元素時(shí)，首先判斷鏈表是否為空，若為空, 則直接將新結(jié)點(diǎn)賦給l即l=p,若不為空，else將最后一個(gè)

3、元素的next指向新結(jié)點(diǎn)即 tailpointer->next=p,然后跳出這個(gè)if,else語句，將新結(jié)點(diǎn)next指向空，并且將tailpointer指 向新結(jié)點(diǎn)即 p->next=null,tailpointer=po2）利用頭插法和尾插法建立一個(gè)有頭結(jié)點(diǎn)單鏈表鏈表冇頭結(jié)點(diǎn)，則在創(chuàng)建鏈表時(shí)，初始化鏈表指針l->next = nullo與無頭結(jié)點(diǎn)區(qū)別 在于，判斷鏈表為空是根據(jù)l->next是否為空。用頭插法插入元素吋，要判斷鏈表是否為空，若為空則將新結(jié)點(diǎn)next指向空，作為表 尾,若不為空,則直接插入，將新結(jié)點(diǎn)next指向頭結(jié)點(diǎn)next的指向,再將頭結(jié)點(diǎn)next指向

4、新結(jié)點(diǎn)即 p->next=l->next,l->next=p。用尾插法插入元素時(shí)，首先也要設(shè)置一個(gè)尾指針tailpointer以便隨時(shí)指向最后一個(gè)結(jié)點(diǎn), 初始化tailpointer=l,與無頭結(jié)點(diǎn)區(qū)別就只是插入第一個(gè)元索時(shí)有區(qū)別。插入元索時(shí)，不需 要判斷鏈表是否為空，肓接進(jìn)行插入，代碼tailpointer->next=p,p->next=null,tailpointer=p03）帶頭結(jié)點(diǎn)和無頭結(jié)點(diǎn)單鏈表元素顯示方法的區(qū)別：區(qū)別在于，顯示時(shí)帶頭結(jié)點(diǎn)是從頭結(jié)點(diǎn)nextff始即p=l->next,而無頭結(jié)點(diǎn)鏈表是直接 從l開始即p=lo四、【源程序代碼】i）利

5、用頭插法和尾插法建立一個(gè)無頭結(jié)點(diǎn)單鏈表#include<stdio.h># include<malloc.h>#include <stdlib.h>typcdcf struct lnodcint data; struct lnode *next;lnodc, *linklist;/*尾插法*/void creatlisttailinsert(linklist &l，int n)linklist p, tailpointcr;int i;/計(jì)數(shù)l = (linklist)malloc(sizeof(lnode);if(!l) cxit(o);分配空間失

6、敗則退出程序l = null; /no headcrunodetailpointer = l; /把尾賦給尾指針printf(,taillist(%d):m,n);for(i = 0;i < n; i+)p = (linklist)malloc(sizeof(lnode);if(!p) exit(o);scanf(n%dn,&(p->data);if(l = null) l = p;當(dāng)鏈表為空,l賦給第一個(gè)結(jié)點(diǎn)else tailpointer->next = p; 將新結(jié)點(diǎn)插入尾部； p->next = null;tailpointer = p; 插入的結(jié)點(diǎn)變?yōu)?/p>

7、尾結(jié)點(diǎn)/*頭插法*/void creatlistheadinsert(linklist &l, int n)linklist p;int i;/計(jì)數(shù)l = (linklist)malloc(sizeof(lnode);if( !l) exit(o);分配空間失敗則退出程序l = null; /no headcrunodeprintf(hheadlist(%d):,n);for(i = ();i v n; i+)創(chuàng)建新結(jié)點(diǎn)p = (linklist)malloc(sizeof(lnode);if(!p) exit(o);scanf(n%dh,&(p->data);if(l

8、!= null) p->next = l;else p->next = null;l = p; 將頭結(jié)點(diǎn)next指向賦給新結(jié)點(diǎn)/*依次顯示表中所有元素*/void getahelem(linklist &l, int n)linklist p;int i = 0;p = l; whilc(p && i v n) printf("%d ",p->data); p = p->next;i+；)printf(,nh);void main()linklisthcadlist;linklisttaillist;int count; 插入

9、元素個(gè)數(shù)printf(,fcount=n); scanf(n%dn,&count);creatlistheadinsert(headlist, count); creatlisttailinsert(taillist, count); printfc'headlist:");getahelem(headlist, count);printf("taillist:m);getahelem(taillist, count);2)利用頭插法和尾插法建立一個(gè)有頭結(jié)點(diǎn)單鏈表#include<stdio.h># include<malloc.h>

10、#include <stdlib.h>typcdcf struct lnodcint data;struct lnode *next;lnodc, *linklist;/*尾插法*/void creatlisttailinsert(linklist &l，int n)linklist p, tailpointer; int i;/計(jì)數(shù)l = (linklist)malloc(sizeof(lnode);if(!l) exit(o);分配空間失敗則退出程序l->ncxt = null; /hcadcrunodctailpointer = l; 把尾賦給尾指針printf

11、(ntaillist(%d):rn);for(i = 0;i < n; i+)p = (linklist)malloc(sizeof(lnode); if(!p) exit(o);scanf(,f%dm,&(p->data);p->next = tailpointer->next; tailpointer->next = p;tailpointer二p; /插入的結(jié)點(diǎn)變?yōu)槲步Y(jié)點(diǎn)/*頭插法*/void creatlistheadinsert(linklist &l, int n)linklist p;int i;計(jì)數(shù)l = (linklist)mal

12、loc(sizeof(lnode);if(!l) exit(o);分配空間失敗則退出程序l->next = null; /headcrunodeprintf(hheadlist(%d):,n);for(i = ();i < n; i+)創(chuàng)建新結(jié)點(diǎn)p = (linklist)malloc(sizeof(lnode);if(!p) exit(o);scanf("%d",&(p->data);p->next = l->next; 將頭結(jié)點(diǎn)next指向賦給新結(jié)點(diǎn) l->next = p;/*依次顯示表中所有元素*/void getalle

13、lem(linklist &l, int n)linklist int i = 0;p；p = l->next; while(p && i v n) printf("%d m,p->data); p = p->ncxt;i+；printf("nm);linklistlinklist int count;headlist; taillist;插入元素個(gè)數(shù)printf(ncount=h);scanf(” ct，&count);creatlistheadinsert(headlist, count); creatlisttailinsert(taillist, count);printf(uheadlist:"); gctahelcm(hcadlist, count); printf("taillist:"); getahelem(taillist, count);五、【數(shù)據(jù)測(cè)試】輸入：8插入8個(gè)元索輸入八個(gè)數(shù)字頭插法和尾插法區(qū)別在于，頭插法輸入數(shù)據(jù)是逆序存入，尾插法是順序存入；帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)在數(shù)據(jù)顯示上基本沒區(qū)別，區(qū)別在丁初始化鏈表和插入