C语言遍历单链表，插入、删除...完整实现代码
1. 遍历单链表（打印，修改）
便利的概念想必大家都不会陌生，即就是从链表的头开始，逐步向后进行每一个元素的访问，这就是遍历，对于遍历操作，我们可以衍生出很多常用的数据操作，比如说查询元素，修改元素，获取元素个数，打印整个链表数据等等。
进行遍历的思路极其简单，只需要建立一个指向链表L的结点，然后沿着链表L逐个向后搜索即可。
对于遍历操作，以下是代码实现：
//便利输出单链表void printList(LinkedList L){ Node *p=L->next; int i=0; while(p){ printf("第%d个元素的值为:%d\n",++i,p->data); p=p->next; }} |
对于元素修改操作，以下是代码实现：
//链表内容的修改，再链表中修改值为x的元素变为为k。LinkedList LinkedListReplace(LinkedList L,int x,int k) { Node *p=L->next; int i=0; while(p){ if(p->data==x){ p->data=k; } p=p->next; } return L;} |
简单的遍历设计的函数只需要void无参即可，而当我们需要进行元素修等涉及到元素操作时，我们可以设计一个LinkedList类型的函数，使其返回一个修改后的新链表。
以上的操作均用到了遍历的思维，针对于遍历还有非常多的用法供自主设计，请参考后文配套的习题进行练习。
2. 插入操作
链表的增加结点操作主要分为查找到第i个位置，将该位置的next指针修改为指向我们新插入的结点，而新插入的结点next指针指向我们i+1个位置的结点。其操作方式可以设置一个前驱结点，利用循环找到第i个位置，再进行插入。
如图，在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点：
从原来的链表状态
到新的链表状态：
以下是代码实现：
//单链表的插入，在链表的第i个位置插入x的元素 LinkedList LinkedListInsert(LinkedList L,int i,int x) { Node *pre; //pre为前驱结点 pre = L; int tempi = 0; for (tempi = 1; tempi < i; tempi++) { pre = pre->next; //查找第i个位置的前驱结点 } Node *p; //插入的结点为p p = (Node *)malloc(sizeof(Node)); p->data = x; p->next = pre->next; pre->next = p; return L;} |
3. 删除操作
删除元素要建立一个前驱结点和一个当前结点，当找到了我们需要删除的数据时，直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数释放掉。
参考如图
以下是代码实现：
//单链表的删除，在链表中删除值为x的元素 LinkedList LinkedListDelete(LinkedList L,int x) { Node *p,*pre; //pre为前驱结点，p为查找的结点。 p = L->next; while(p->data != x) { //查找值为x的元素 pre = p; p = p->next; } pre->next = p->next; //删除操作，将其前驱next指向其后继。 free(p); return L;} |
4. 附：完整实现代码
#include <stdio.h>#include <stdlib.h>//定义结点类型typedef struct Node { int data; //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型 struct Node *next; //单链表的指针域} Node,*LinkedList;//单链表的初始化LinkedList LinkedListInit() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请结点空间 if(L==NULL){ //判断申请空间是否失败 exit(0); //如果失败则退出程序 } L->next = NULL; //将next设置为NULL,初始长度为0的单链表 return L;}//单链表的建立1，头插法建立单链表LinkedList LinkedListCreatH() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 int x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL L->next = p; } return L;}//单链表的建立2，尾插法建立单链表LinkedList LinkedListCreatT() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 Node *r; r = L; //r始终指向终端结点，开始时指向头结点 int x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL r = p; } r->next = NULL; return L;}//单链表的插入，在链表的第i个位置插入x的元素LinkedList LinkedListInsert(LinkedList L,int i,int x) { Node *pre; //pre为前驱结点 pre = L; int tempi = 0; for (tempi = 1; tempi < i; tempi++) { pre = pre->next; //查找第i个位置的前驱结点 } Node *p; //插入的结点为p p = (Node *)malloc(sizeof(Node)); p->data = x; p->next = pre->next; pre->next = p; return L;}//单链表的删除，在链表中删除值为x的元素LinkedList LinkedListDelete(LinkedList L,int x) { Node *p,*pre; //pre为前驱结点，p为查找的结点。 p = L->next; while(p->data != x) { //查找值为x的元素 pre = p; p = p->next; } pre->next = p->next; //删除操作，将其前驱next指向其后继。 free(p); return L;}//链表内容的修改，再链表中修改值为x的元素变为为k。LinkedList LinkedListReplace(LinkedList L,int x,int k) { Node *p=L->next; int i=0; while(p){ if(p->data==x){ p->data=k; } p=p->next; } return L;}//便利输出单链表void printList(LinkedList L){ Node *p=L->next; int i=0; while(p){ printf("第%d个元素的值为:%d\n",++i,p->data); p=p->next; }} int main() { //创建 LinkedList list; printf("请输入单链表的数据：以EOF结尾\n"); list = LinkedListCreatT(); //list=LinkedListCreatT(); printList(list); //插入 int i; int x; printf("请输入插入数据的位置："); scanf("%d",&i); printf("请输入插入数据的值："); scanf("%d",&x); LinkedListInsert(list,i,x); printList(list); //修改 printf("请输入修改的数据："); scanf("%d",&i); printf("请输入修改后的值："); scanf("%d",&x); LinkedListReplace(list,i,x); printList(list); //删除 printf("请输入要删除的元素的值："); scanf("%d",&x); LinkedListDelete(list,x); printList(list); return 0;} |
THE END
