/* 结构体不能含有同类型的结构，但是可以含有指向同类型结构的指针。这样的定义是定义一个链表的基础。 */
1 typedef int Element;

2

3 typedef struct node{

4     Element e;

5     struct node* next;//这里只是声明了一个名为next的指针，指针本身也占内存空间，里面存放的始终是地址。 struct node* 表示指针的类型是 struct node，即指向的地址里存放的是一个结构体

6 }LNode, *Linklist;　　//LNode等价于struct node; *LinkList 等价于 struct node* 

 1 /**

 2 * 插入元素

 3 */

 4 Linklist insert(Linklist head, int k, Element e){

 5     int getLength(Linklist head);

 6

 7     Linklist p = (Linklist)malloc(sizeof(LNode));//申请一个新节点

 8     Linklist pre = (Linklist)malloc(sizeof(LNode));//申请一个新节点

 9     int length = getLength(head);

10     pre = head;

11

12     if(k == length+1){    //在链表末尾添加新节点

13         while(pre->next) {

14             pre = pre->next; //单链表中申请的节点 p 不能使用"p++"操作。p++本身不会出现语法问题，但是并不会"从指向p变成指向p的下一个节点" ， 而是"从指向p的数据域地址变成指向p的指针域地址" 

15         }//循环结束时，pre已经到达链表末尾

16         p->e = e;

17         pre->next = p;

18         p->next = NULL;

19     }else if(k > 0 && k <= length){//在链表中间添加节点 ，插入位置从1开始算

20         int j = 1;

21         while(j < k) {

22             pre = pre->next;//单链表中申请的节点 p 不能使用"p++"操作。p++本身不会出现语法问题，但是并不会"从指向p变成指向p的下一个节点" ， 而是"从指向p的数据域地址变成指向p的指针域地址" 

23             j++;

24         }//循环结束时，pre是要插入位置的前驱节点

25         p->e = e;

26         p->next = pre->next; // p 的指针域指向原先 pre 节点的下一个节点的地址 

27         pre->next = p;  // pre的指针域指向节点 p 的地址

28     }else{

29         printf("插入的位置有误！\n");

30     }

31     return head;

32 }