数据结构头插法和尾插法建立链表(各分有无头结点).doc

实验一 链表的建立及基本操作方法实现一、【实验目的】1、理解和掌握单链表的类型定义方法和结点生成方法。2、掌握利用头插法和尾插法建立单链表和显示单链表元素的算法。3、掌握单链表的查找（按序号）算法。4、掌握单链表的插入、删除算法。二、【实验内容】1、利用头插法和尾插法建立一个无头结点单链表，并从屏幕显示单链表元素列表。2、利用头插法和尾插法建立一个有头结点单链表，并从屏幕显示单链表元素列表。3、将测试数据结果用截图的方式粘贴在程序代码后面。重点和难点：尾插法和头插法建立单链表的区别。建立带头结点和无头结点单链表的区别。带头结点和无头结点单链表元素显示方法的区别三、【算法思想】1) 利用头插法和尾插法建立一个无头结点单链表链表无头结点，则在创建链表时，初始化链表指针L=NULL。当用头插法插入元素时，首先要判断头指针是否为空，若为空，则直接将新结点赋给L,新结点next指向空，即L=p,p-next=NULL，若表中已经有元素了，则将新结点的next指向首结点，然后将新结点赋给L即（p-next=L,L=p）。当用尾插法插入元素时，首先设置一个尾指针tailPointer以便随时指向最后一个结点，初始化tailPointer和头指针一样即tailPointer=L。插入元素时，首先判断链表是否为空，若为空，则直接将新结点赋给L即L=p，若不为空，else将最后一个元素的next指向新结点即tailPointer-next=p，然后跳出这个if,else语句，将新结点next指向空，并且将tailPointer指向新结点即p-next=NULL,tailPointer=p。2) 利用头插法和尾插法建立一个有头结点单链表链表有头结点，则在创建链表时，初始化链表指针L-next = NULL。与无头结点区别在于，判断链表为空是根据L-next是否为空。用头插法插入元素时，要判断链表是否为空，若为空则将新结点next指向空，作为表尾，若不为空，则直接插入，将新结点next指向头结点next的指向，再将头结点next指向新结点即p-next=L-next,L-next=p。用尾插法插入元素时，首先也要设置一个尾指针tailPointer以便随时指向最后一个结点，初始化tailPointer=L，与无头结点区别就只是插入第一个元素时有区别。插入元素时，不需要判断链表是否为空，直接进行插入，代码tailPointer-next=p,p-next=NULL,tailPointer=p。3）带头结点和无头结点单链表元素显示方法的区别：区别在于，显示时带头结点是从头结点next开始即p=L-next，而无头结点链表是直接从L开始即p=L。四、【源程序代码】1) 利用头插法和尾插法建立一个无头结点单链表#include#include#include typedef struct LNode int data; struct LNode *next;LNode, *LinkList;/* 尾插法 */void creatListTailInsert(LinkList &L, int n) LinkList p, tailPointer; int i;/计数 L = (LinkList)malloc(sizeof(LNode); if(!L) exit(0); /分配空间失败则退出程序 L = NULL; /no headcrunode tailPointer = L; /把尾赋给尾指针 printf(taillist(%d):,n); for(i = 0;i data); if(L = NULL) L = p; /当链表为空,L赋给第一个结点 else tailPointer-next = p; /将新结点插入尾部； p-next = NULL; tailPointer = p; /插入的结点变为尾结点 /* 头插法 */void creatListHeadInsert(LinkList &L, int n) LinkList p; int i;/计数 L = (LinkList)malloc(sizeof(LNode); if(!L) exit(0); /分配空间失败则退出程序 L = NULL; /no headcrunode printf(headlist(%d):,n); for(i = 0;i data); if(L != NULL) p-next = L; else p-next = NULL; L = p; /将头结点 next指向赋给新结点 /* 依次显示表中所有元素 */void getAllElem(LinkList &L, int n) LinkList p; int i = 0; p = L; while(p & i data); p = p-next; i+; printf(n);void main() LinkList headList; LinkList tailList; int count; /插入元素个数 printf(count=); scanf(%d,&count); creatListHeadInsert(headList, count); creatListTailInsert(tailList, count); printf(headList:); getAllElem(headList, count); printf(tailList:); getAllElem(tailList, count);2) 利用头插法和尾插法建立一个有头结点单链表#include#include#include typedef struct LNode int data; struct LNode *next;LNode, *LinkList;/* 尾插法 */void creatListTailInsert(LinkList &L, int n) LinkList p, tailPointer; int i;/计数 L = (LinkList)malloc(sizeof(LNode); if(!L) exit(0); /分配空间失败则退出程序 L-next = NULL; /headcrunode tailPointer = L; /把尾赋给尾指针 printf(taillist(%d):,n); for(i = 0;i data); p-next = tailPointer-next; tailPointer-next = p; tailPointer = p; /插入的结点变为尾结点 /* 头插法 */void creatListHeadInsert(LinkList &L, int n) LinkList p; int i;/计数 L = (LinkList)malloc(sizeof(LNode); if(!L) exit(0); /分配空间失败则退出程序 L-next = NULL; /headcrunode printf(headlist(%d):,n); for(i = 0;i data); p-next = L-next; /将头结点 next指向赋给新结点 L-next = p; /* 依次显示表中所有元素 */void getAllElem(LinkList &L, int n) LinkList p; int i = 0; p = L-next; while(p & i data); p = p-next; i+; printf(n);void main() LinkList headList; LinkList tailList; int count; /插入元素个数 printf(count=); scanf(%d,&count); creatListHeadInsert(headList, count); creatListTailInsert(tailList, count); printf(headList:); getAllElem(headList, count); printf(tailList:); ge