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

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

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

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

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

5、用頭插法和尾插法建立一個無頭結(jié)點單鏈表#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;/計數(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賦給第一個結(jié)點else tailpointer->next = p; 將新結(jié)點插入尾部； p->next = null;tailpointer = p; 插入的結(jié)點變?yōu)?/p>

7、尾結(jié)點/*頭插法*/void creatlistheadinsert(linklist &l, int n)linklist p;int i;/計數(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é)點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é)點next指向賦給新結(jié)點/*依次顯示表中所有元素*/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、元素個數(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)利用頭插法和尾插法建立一個有頭結(jié)點單鏈表#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;/計數(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é)點變?yōu)槲步Y(jié)點/*頭插法*/void creatlistheadinsert(linklist &l, int n)linklist p;int i;計數(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é)點p = (linklist)malloc(sizeof(lnode);if(!p) exit(o);scanf("%d",&(p->data);p->next = l->next; 將頭結(jié)點next指向賦給新結(jié)點 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;插入元素個數(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ù)測試】輸入：8插入8個元索輸入八個數(shù)字頭插法和尾插法區(qū)別在于，頭插法輸入數(shù)據(jù)是逆序存入，尾插法是順序存入；帶頭結(jié)點和不帶頭結(jié)點在數(shù)據(jù)顯示上基本沒區(qū)別，區(qū)別在丁初始化鏈表和插入