单链表的基本操作及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;
}