单链表二

点击打开在线编译器,边学边练

(续接前文)

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数据结点:

从原来的链表状态

31.png


到新的链表状态:

32.png


以下是代码实现:

//单链表的插入,在链表的第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函数释放掉。

参考如图

33.png


以下是代码实现:

//单链表的删除,在链表中删除值为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;
}


5.  题目练习推荐

1676题1052题

请独自完成提交并通过


本文固定URL:https://www.dotcpp.com/course/97

上一课:单链表一 下一课:双向链表一
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记
Dotcpp在线编译      (登录可减少运行等待时间)