单链表创建之--头插法创建带头结点的单链表,超详细

一、单链表创建之--头插法创建带头结点的单链表,超详细

单链表常见的创建方法有头插法和尾插法，这里记录头插法创建带头结点的单链表具体过程：

1）首先使用 typedef关键字定义结点数据类型

4行的 LNode和* LinkList可有可无，有的话后面定义结点变量和指针变量时更方便，不必须在LNode前面加 struct关键字，可直接这样定义变量,

与上面 typedef关键字定义的单链表数据类型一样的定义方法：

若用这种方法定义链表结点类型，定义结点变量和指针变量时必须在LNode前带上 struct关键字，即：

这两种定义方法效果是一样的，都是定义了包含 1个整型变量的数据域和 1个后继指针域的单链表结点类型

2）通过函数头插构建链表，并返回 LinkList类型表头指针变量 L，

算法基本思想：带有头结点的单链表有两类结点，头结点和元素结点，头结点通常不存储数据，用 L表示，元素结点存储数据，用 s表示

2.1定义头结点指针变量 L和元素结点 s

2.2定义了头结点之后，内存中尚未分配空间，此时头结点并不真实存在，需使用 malloc关键字分配存储空间后，并使 L指针指之，才真正创建了 L头结点。由于此时仅有头结点，无后继结点，需将其指针域置空

这时设置一个整型变量 x，通过不断输入其值，来初始化各结点数据域 val，判断 x=9999时为输入结束条件，先任意输入一个 x，然后通过 while循环来判断 x值决定是否进入添加结点过程

1，初始化一个 s元素结点，先初始化数据域 var，然后初始化指针域 next

先初始化数据域 var，然后初始化指针域 next头插法是这样插入新结点的，新的结点 s始终在当前的表中第一个元素结点之前

，也就是 L->next之前插入，数据输入顺序与最终链表结点顺序是相反的，

所以在创建了一个新的元素结点 s后，需要将其指针域置为 L->next,如图

4，若输入的值非9999，则再次进入 while循环，反复执行上述流程，不断插入元素结点扩大单链表长，这里赘述再添加一个元素结点的过程

又初始化了一个元素结点 s，状态如图：

按照上述算法，头插法新的元素结点 s插入时始终插入在当前表中首个元素结点 F之前，故需要将其后继指针域置为当前表中首个元素结点 F，即 s->next= L->next,记住 L->next始终指向首个元素结点，结果如图：

元素结点 s被“半插入”到表中后， F已经不是绝对意义上的首个元素结点了，此时需要更改头结点 L的后继指针域，将其后继指针域置为被“半插入”表中的新元素结点 s，这样，新的元素结点 s正式被插入表中，表长+1，如图

2.3上述插入过程的函数完整实现:

需要初始化一个 head指针变量，来接收 head_Insert()函数所返回的已创建的链表头结点指针值,然后将 head传入 printList()函数直接调用打印输入单链表数据，由于printList()是从首个结点开始打印，而头结点不存储数据，故传入第一个元素结点

程序最终运行结果如图，可以看到，头插法建立的单链表数据顺序与输入顺序相反：

二、下列代码用C语言求单链表的长度为什么不对

1、很高兴为楼主解答，首先楼主是想头插入法创建单链表，然后按输入的逆顺序输出，然后尾插入法创建单链表，然后按输入的顺序输出，接着输出第一个链表的长度和第二个链表的长度。但楼主犯了一个简单的错误用getchar来判断是否输入来创建链表，因为空字符也会作为字符来判断，但不是'a'字符（包括回车）也会创建一个结点，这就是为什么楼主的链表的长度是2倍的原因，楼主可以通过输入的数据来判断是否创建结点，比如说把int ch;输入的ch不为0创建一个结点，一直下去，直到输入的数据为0，替楼主的代码稍作了修改，如果可以，希望楼主采纳！！！！

2、 head=(linklist*)malloc(sizeof(linklist));

3、 p=(linklist*)malloc(sizeof(linklist));

4、 linklist*head,*p,*r;intch;//修改

5、 head=(linklist*)malloc(sizeof(linklist));

6、 p=(linklist*)malloc(sizeof(linklist));

7、 printf("%-3d",p->data);//修改

三、c语言 链表操作:建立,显示及节点的插入,删除

先写个头文件，包含链表的各种操作。具体代码如下：

typedef LNode*LinkList;//另一种定义LinkList的方法

//单链表线性表的基本操作(12个)

//操作结果：构造一个空的线性表L

L=(LinkList)malloc(sizeof(LNode));//产生头结点,并使L指向此头结点

void CreateList_L(LinkList&L, int n)//算法2.11

//逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L

L=(LinkList)malloc(sizeof(LNode));

L->next= NULL;//先建立一个带头结点的单链表

p=(LinkList)malloc(sizeof(LNode));//生成新结点

p->data= rand()%200;//改为一个随机生成的数字(200以内)

//初始条件：线性表L已存在。操作结果：销毁线性表L

int ClearList(LinkList L)//不改变L

//初始条件：线性表L已存在。操作结果：将L重置为空表

p=L->next;// p指向第一个结点

L->next=NULL;//头结点指针域为空

//初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE

//初始条件：线性表L已存在。操作结果：返回L中数据元素个数

LinkList p=L->next;// p指向第一个结点

int GetElem(LinkList L,int i,ElemType&e)//算法2.8

// L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回1,否则返回-1

LinkList p=L->next;// p指向第一个结点

while(p&&j<i)//顺指针向后查找,直到p指向第i个元素或p为空

if(!p||j>i)//第i个元素不存在

int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType))

//初始条件:线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0)

//操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。

//若这样的数据元素不存在,则返回值为0

if(compare(p->data,e))//找到这样的数据元素

int PriorElem(LinkList L,ElemType cur_e,ElemType&pre_e)

//操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,

//返回1;否则操作失败,pre_e无定义,返回-1

LinkList q,p=L->next;// p指向第一个结点

while(p->next)// p所指结点有后继

int NextElem(LinkList L,ElemType cur_e,ElemType&next_e)

//操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，

//返回1;否则操作失败，next_e无定义，返回-1

LinkList p=L->next;// p指向第一个结点

while(p->next)// p所指结点有后继

int ListInsert(LinkList L,int i,ElemType e)//算法2.9。不改变L

//在带头结点的单链线性表L中第i个位置之前插入元素e

while(p&&j<i-1)//寻找第i-1个结点

if(!p||j>i-1)// i小于1或者大于表长

s=(LinkList)malloc(sizeof(LNode));//生成新结点

int ListDelete(LinkList L,int i,ElemType&e)//算法2.10。不改变L

//在带头结点的单链线性表L中，删除第i个元素,并由e返回其值

while(p->next&&j<i-1)//寻找第i个结点,并令p指向其前趋

if(!p->next||j>i-1)//删除位置不合理

q=p->next;//删除并释放结点

int ListTraverse(LinkList L,void(*vi)(ElemType))

// vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同

//操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败

LinkList ReverseList(LinkList phead)//实现链表的逆置

#endif// LINKEDLIST_H_INCLUDED

int compare(ElemType c1,ElemType c2)

void MergeList_L(LinkList&La, LinkList&Lb, LinkList&Lc)

//已知单链线性表La和Lb的元素按值非递减排列。

//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。

Lc= pc= La;//用La的头结点作为Lc的头结点

if(pa->data<= pb->data)

pc->next= pa? pa: pb;//插入剩余段

printf("在L的表尾依次插入10个数据后：L=");

printf("第4个元素的值为：%d\n",e);

ListDelete(L,4,e);//删除第4个数据

printf("删除第4个数据后：L=");