单链表的插入过程
【说明】：
1、要在带头结点的单链表第i（0≤i≤size）个结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后动态申请一个结点存储空间并由指针q指示，并把数据元素x的值赋予新结点的数据元素域（即q->data=x），最后修改新结点的指针域指向ai结点（即q->next=p->next），并修改ai-1结点的指针域使之指向新结点q（即p->next= q）。插入过程如上图所示。
2、循环条件由两个子条件逻辑与组成，其中子条件p->next != NULL保证指针所指结点存在，子条件j<i-1保证最终让指针p指向ai-1结点。
代码实现：
int ListInsert(SLNode *head,int i,DataType x) { //在带头结点的单链表head的第i(0<=i<=size)个结点前 //插入一个存放数据元素x的结点。插入成功则返回1，失败则返回0 SLNode *p,*q; int j; p=head; j=-1; while(p->next!=NULL&&j<i-1) //最终让指针p指向第i-1个结点 { p=p->next; j++; } if(j!=i-1) { printf("插入元素位置参数错！"); return 0; } //生成新结点，并赋值 q=(SLNode *)malloc(sizeof(SLNode)); q->data=x; //插入步骤 q->next=p->next; p->next=q; return 1; }
单链表的删除ListDelete
【说明】：
1、要在带头结点的单链表中删除第i（0≤i≤size-1）个结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向ai结点（即s=p->next），并把数据元素a i的值赋予x（即*x=s->data），最后把ai结点脱链（即p->next=p->next->next），并动态释放ai结点的存储空间，即free(s)。删除过程如上图所示。
2、循环条件由三个子条件逻辑与组成，其中子条件p->next!=NULL保证ai-1结点存在，子条件p->next->next!=NULL保证ai结点存在，子条件j<i-1保证最终让指针p指向ai-1结点。与插入函数相比，删除函数的循环条件多了子条件p->next->next!=NULL。这是因为删除函数要删除ai结点，若没有子条件p->next->next!=NULL保证ai结点存在，则当ai结点不存在时，动态释放语句free(s)将因指针s为空而出错。
注意：在循环条件中，前两个子条件的次序不能颠倒，否则在ai-1结点不存在时，会因指针p->next->next不存在而出错
代码实现：
int ListDelete(SLNode *head,int i,DataType *x) { SLNode *p,*s; int j; p=head; j=-1; while(p->next!=NULL&&p->next->next!=NULL&&j<i-1) //循环结束时指针p指向第i-1个结点 { p=p->next; j++; } if(j!=i-1) { printf("删除元素位置参数错！"); return 0; } s=p->next; *x=s->data; p->next=p->next->next;//删除 free(s); //释放指针s所指向结点的内存空间 return 1; }
单链表取数据元素
取数据元素函数和删除函数基本类同，主要差别是，取数据元素函数的循环条件改为j<i，并且不删除ai结点。
代码实现：
int ListGet(SLNode *head,int i,DataType *x) { SLNode *p; int j; p=head; j=-1; while(p->next!=NULL && j<i) { p=p->next; j++; } if(j!=i) { printf("取元素位置出错！"); return 0; } *x=p->data; return 1; }
撤销单链表
单链表的结点空间是在程序运行时动态申请的，而系统只负责自动回收程序中静态分配的内存空间，所以，和顺序表相比，单链表要增加一个撤销单链表操作，释放动态申请的内存空间。
代码实现：
void Destroy(SLNode **head) { SLNode *p,*p1; p=*head; while(p!=NULL) { p1=p; p=p->next; free(p1); } *head=NULL; }
单链表实例
1、编程实现建立一个线性表，首先依次输入数据元素1, 2, 3,…,10，然后删除数据元素5，最后依次显示当前表中的数据元素。要求使用单链表。
代码如下：
include <stdio.h> //包含printf()函数 #include <stdlib.h> //包含exit()函数 #include <malloc.h> //包含malloc()等函数 //2020.05。04 微信公众号：C语言与CPP编程 typedef int DataType; //定义DataType为int #include "LinList.h" //包含单链表文件 int main(int argc, char* argv[]) { SLNode *head; //定义头指针变量 int i,x; ListInitiate(&head); //初始化 for(i = 0;i < 10; i++) //插入10个数据元素 { if(ListInsert(head,i,i+1) == 0) { printf("错误！\n"); return ; } } for(i = 0;i < ListLength(head); i++) //显示当前的数据元素中的值 { if(ListGet(head,i,&x) == 0) //取元素值到x变量中 { printf("错误！\n"); return ; } else { printf("%d ",x); //显示 } } printf("\n"); if(ListDelete(head,4,&x) == 0) //删除下标为四(值为5)的数据元素 { printf("错误！\n"); return ; } for(i = 0;i < ListLength(head); i++) //显示当前的数据元素中的值 { if(ListGet(head,i,&x) == 0) //取元素值到x变量中 { printf("错误！\n"); return ; } else { printf("%d ",x); //显示 } } printf("\n"); Destroy(&head); //撤消单链表 return 0; }
2、设头指针为head,并设带头结点单链表中的数据元素递增有序，编写算法将数据 元素x插入到带头结点单链表的适当位置上，要求插入后保持单链表数据元素的递增有序。
算法思路：从链表的第1个数据元素结点开始，逐个比较每个结点的data域值和x的值，当data小于等于x时，进行下一个结点的比较；否则，就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾。
代码如下：
void LinListInsert(SLNode*head,DataType x) { SLNode*curr,*pre,*q; //循环初始化 curr = head->next; //curr指向第一个数据元素结点 pre = head; //pre指向头结点 //循环定位插入位置 while(curr != NULL && curr->data <= x) { pre = curr; curr = curr->next; } //申请一个结点并把x存入data域 if((q = (SLNode*)malloc(sizeof(SLNode))) == NULL) exit(1); q->data = x; //把新结点插入pre所指结点后 q->next = pre->next; pre->next = q; }
3、设head为单链表的头指针，并设单链表带有头结点，编写算法将单链表中的数据元素按照其值递增有序的顺序进行就地排序。
代码如下：