创建一个新的单链表链表 用表头或表尾插入法（C语言）急

#include <stdio.h>

typedef struct student

{

int id

char name[20]

float score

}elemtype

elemtype stu[ ]={{1,"wang",78.0},{2,"zhang",80.0},{3,"li",86.0}}

typedef struct list_type

{

elemtype data[3]

int num

}listtype

int insert1 (listtype *l,int i,elemtype x)

int main()

{

int i

listtype lt

lt.num = 0

for (i=0i<3i++)

{

printf("%d,%s,%f",stu[i].id,stu[i].name,stu[i].score)

}

insert1(&lt, 0, stu[2])

insert1(&lt, 1, stu[1])

insert1(&lt, 2, stu[0])

printf("\nresult:\n")

for (i = 0i <lt.numi++)

{

printf("%d, %s, %f\n", lt.data[i].id, lt.data[i].name, lt.data[i].score)

}

return 0

}

# define true 0

# define false 1

int insert1 (listtype *l,int i,elemtype x)

{

int j

if (l->num>=3)

{

printf("the list is full,can not insert.")

return(false)

}

if ((i<0)||(i>l->num))

{

printf("i is invalid value")

return(false)

}

for (j=l->num-1j>=ij--)

l->data[j+1]=l->data[j]

l->data[i]=x

l->num++

return(true)

}

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

以C语言为例，

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 上述插入过程的函数完整实现:

4）主函数 main() 流程

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

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

何在指针q指向的结点后面插入结点。该过程的步骤如下：

（1）先创建一个新结点，并用指针p指向该结点。

（2）将q指向的结点的next域的值（即q的后继结点的指针）赋值给p指向结点的next域。

（3）将p的值赋值给q的next域。

通过以上3步就可以实现在链表中由指针q指向的结点后面插入p所指向的结点。可以通过图1-5形象地展示出这一过程。

图1-5 向链表插入结点过程

下面给出代码描述：

1.void insertList(LinkList *list,LinkList q,ElemType e) /*当链表为空时*/ 10.else 16.} 上面的这段代码描述了如何在指针q指向的结点后面插入结点的过程。其过程包括以下几步。

（1）首先生成一个新的结点，大小为sizeof(LNode)，用LinkList类型的变量p指向该结点。将该结点的数据域赋值为e。

（2）接下来判断链表是否为空。如果链表为空，则将p赋值给list，p的next域的值置为空。否则，将q指向的结点的next域的值赋值给p指向结点的next域，这样p指向的结点就与q指向结点的下一个结点连接到了一起。

（3）然后再将p的值赋值给q所指结点的next域，这样就将p指向的结点插入到了指针q指向结点的后面。

其实通过上面这段算法描述可以看出，应用这个算法同样可以创建一个链表。这是因为当最开始时链表为空，即list==NULL，该算法可自动为链表创建一个结点。在下面的创建其他结点的过程中，只要始终将指针q指向链表的最后一个结点，就可以创建出一个 链表。

注意：函数insertList()的参数中有一个LinkList *list，它是指向LinkList类型的指针变量，相当于指向LNode类型的指针的指针。这是因为在函数中要对list，也就是表头指针进行修改，而调用该函数时，实参是&list，而不是list。因此必须采取指针参数传递的办法，否则无法在被调函数中修改主函数中定义的变量的内容。以下的代码也有类似的情况。

---