数据结构（C语言）-线性表之单链表-学习笔记02

文章目录

1. 基本介绍
2. 基本用法
3. 单链表实现
- 3.1 创建结点
- 3.2 在链表尾插入新的结点
- 3.3 遍历打印
- 3.4 链表查找
- 3.5 插入
- 3.6 删除链表中的某个结点
- 3.7 删除链表中的所有结点
- 3.8 链表的反转
- 3.9 求相邻两个结点的和最大得到的前一个结点的指针
- 3.10 合并链表
- 3.11 释放空间
4. 所有代码

1. 基本介绍

将线性表 L = ( a 0 , a 1 , ⋯ , a n − 1 ) L=(a_0, a_1,cdots, a_{n-1}) L=(a0,a1,⋯,an−1)中各元素分布在存储器的不同存储块，称为结点，通过地址或指针建立元素之间的联系。
每个结点有一个data和一个next指针，data存储数据元素 a i a_i ai，next指向下一个结点，最后一个元素的指针指向NULL

2. 基本用法

定义：

typedef struct node{
	data_t data; //结点的数据域
	struct node *next; //结点的后继指针域
}listnode, *linklist;

用法：

//在堆空间中声明
linklist p = (linklist)malloc(sizeof(listnode));
p->data = value; //赋值

//在栈空间中声明
linknode a;
a.data = value; //赋值

假设p指向链表中结点 a i a_i ai，也就是 p → a i ∣ n e x t → a i + 1 ∣ n e x t → ⋯ prightarrow a_i|nextrightarrow a_{i+1}|nextrightarrow cdots p→ai∣next→ai+1∣next→⋯，如果要获取 a i a_i ai，写作p->data；取 a i + 1 a_{i+1} ai+1，写作p->next->data；若指针p的值为NULL，则它不指向任何结点，此时取地址会爆段错误

3. 单链表实现 3.1 创建结点

linklist create(){
	linklist header;
	header = (linklist)malloc(sizeof(listnode));
	if (header == NULL){
		printf("malloc failedn");
	}
	header->data = 0;
	header->next = NULL;
	return header;
}

3.2 在链表尾插入新的结点

int append(linklist header, int value){ 
	if (header == NULL){
		printf("Header is NULL");
		return -1;
	}
	// new node
	linklist p, cur_node;
	if ((p = (linklist)malloc(sizeof(listnode))) == NULL){
		printf("malloc failedn");
		return -1;
	}
	p->data = value;
	p->next = NULL;
	
	//locate the tail of the list
	cur_node = header;
	while (cur_node->next != NULL)
		cur_node = cur_node->next;

	//insert
	cur_node->next = p;
	return 0;
}

3.3 遍历打印

int show(linklist header){
	linklist p;
	if (header == NULL) {
		printf("Header is NULLn");
		return -1;
	}
	p = header;

	while (p->next != NULL){
		printf("%d ", p->next->data);
		p = p->next;
	}
	puts("");
	return 0;
}

简单实现一下，依次读入表 L = ( a 0 , ⋯ , a n − 1 ) L=(a_0, cdots, a_{n-1}) L=(a0,⋯,an−1)中每一元素 a i a_i ai（假设为整型，且所有元素必须为正整数），若<0则结束插入操作，则为 a i a_i ai创建一结点，然后插入到表尾，最后遍历一下

#include 
#include "linklist.h"

int main(int argc, char *argv[]){
	linklist header;
	int value;
	header = create();
	if (header == NULL)
		return -1;
	while (1){
		printf("input: ");
		scanf("%d", &value);
		if (value < 0)
			break;
		append(header, value);
	}
	show(header);
	return 0;
}

3.4 链表查找

按照位置查找相对应的结点，-1对应着头结点，第一个有元素的结点为0，依次类推

linklist get_node(linklist header, int pos){
	linklist cur_node;
	if (header == NULL){
		printf("Header is NULLn");
		return NULL;
	}
	cur_node = header;
	for (int i=-1; i<=pos; i++){
		if (pos == -1)
			return cur_node;
		if (cur_node->next == NULL){
			printf("Invalid positionn");
			return NULL;
		}
		else{
			if (pos == i)
				return cur_node;
			cur_node = cur_node->next;
		}
	}
	return NULL;
}

3.5 插入

要在第i个位置插入，需要先找到i-1位置的node然后指向新的node，原来指向的结点赋值给新的node的next

int insert(linklist header, data_t value, int pos){
	linklist node, new_node;
	node = get_node(header, pos-1);
	new_node = create();
	new_node->next = node->next;
	new_node->data = value;
	node->next = new_node;
	return 0;
}

3.6 删除链表中的某个结点

如果我们要删除第i个元素，我们需要先找到第i-1个元素，其地址给到node，让node->next = node->next->next随后free掉node->next就好了

int del(linklist header, int pos){
	if (header == NULL){
		printf("Header is NULL");
		return -1;
	}
	linklist node = get_node(header, pos-1);
	if (node == NULL){
		printf("Invalid position");
		return -1;
	}
	if (node->next == NULL){
		printf("Invalid position");
		return -1;
	}
	linklist next_node = node->next;
	node->next = node->next->next;
	free(next_node);
	next_node = NULL;
	return 0;
}

3.7 删除链表中的所有结点

linklist del_every_node(linklist header){
	linklist node;
	if (header == NULL)
		return NULL;
	node = header;
	while (header != NULL){
		node = header;
		header = header->next;
		free(node);
	}
	return NULL;
}

3.8 链表的反转

我们不需要释放旧结点，malloc新结点，我们要做的是反转链表指向的方向。
- 首先判断我们头结点是否为空。链表是否为空或者只有一个结点
- 然后我们需要一个指针p先指向第二个结点，也就是待操作的结点
- 将第一个结点的next赋值为NULL
- 将指针p指向的结点通过指针q的辅助下插入到头结点之后，让p指向下三个结点
- 循环至链表结束

3.9 求相邻两个结点的和最大得到的前一个结点的指针

linklist adjmax(linklist header){
	linklist p, q, r;
	data_t sum;
	if (header == NULL){
		return NULL;
	}
	if (header->next == NULL || header->next->next == NULL || header->next->next->next == NULL)
		return header;

	q = header->next;
	p = header->next->next;
	r = q;
	sum = q->data + p->data;
	
	while (p->next != NULL){
		p = p->next;
		q = q->next;
		if (sum < q->data + p->data){
			sum = q->data + p->data;
			r = q;
		}
	}
	return 0;
}

3.10 合并链表

当链表A和链表B都是单调递增的，要求将链表A和链表B合并到链表A中，且递增有序

int merge(linklist header1, linklist header2){
	linklist p, q, r;
	if (header1 == NULL || header2 == NULL)
		return -1;
	p = header1->next;
	q = header2->next;
	r = header1;
	header1->next = NULL;
	header2->next = NULL;

	while( p && q){
		if (p->data <= q->data){
			r->next = p;
			p = p->next;
			r = r->next;
			r->next = NULL;
		}
		else{
			r->next = q;
			q = q->next;
			r = r->next;
			r->next = NULL;
		}
	}
	if (p == NULL){
		r->next = q;
	}
	else{
		r->next = p;
	}
	return 0;
}

3.11 释放空间

linklist list_free(linklist H) {
	linklist p;

	if (H == NULL)
		return NULL;

	p = H;

	printf("free:");
	while (H != NULL) {
		p = H;
		printf("%d ", p->data);
		H = H->next;
		free(p);
	}
	puts("");

	return NULL;
}

4. 所有代码

test.c

#include 
#include "linklist.h"

int main(int argc, char *argv[]){
	linklist header, node;
	int value;
	header = create();
	if (header == NULL)
		return -1;
	while (1){
		printf("input: ");
		scanf("%d", &value);
		if (value < 0)
			break;
		append(header, value);
	}
	show(header);
	node = get_node(header, 2);
	if (node != NULL)
		printf("%d n", node->data);
	insert(header, 10, 0);
	printf("ninsert 10 before pos 0n");
	show(header);
	printf("ndel entry at pos 2n");
	del(header, 2);
	show(header);
	header = del_every_node(header);
	printf("ndel all entriesn");
	show(header);
	return 0;
}

linklist.h

typedef int data_t;

typedef struct node{
	data_t data;
	struct node *next;
}listnode, *linklist;

linklist create();
int append(linklist header, int value); //the head of the list
linklist get_node(linklist header, int pos);
int insert(linklist header, data_t value, int pos);
int show(linklist header);
int del(linklist header, int pos);
linklist del_every_node(linklist header);
int reverse(linklist header);
linklist list_free(linklist header);
int merge(linklist header1, linklist header2);

linklist.c

#include 
#include 
#include "linklist.h"

linklist create(){
	linklist header;
	header = (linklist)malloc(sizeof(listnode));
	if (header == NULL){
		printf("malloc failedn");
	}
	header->data = 0;
	header->next = NULL;
	return header;
}

int append(linklist header, int value){ 
	if (header == NULL){
		printf("Header is NULL");
		return -1;
	}
	// new node
	linklist p, cur_node;
	if ((p = (linklist)malloc(sizeof(listnode))) == NULL){
		printf("malloc failedn");
		return -1;
	}
	p->data = value;
	p->next = NULL;
	
	//locate the tail of the list
	cur_node = header;
	while (cur_node->next != NULL)
		cur_node = cur_node->next;

	//insert
	cur_node->next = p;
	return 0;
}

linklist get_node(linklist header, int pos){
	linklist cur_node;
	if (header == NULL){
		printf("Header is NULLn");
		return NULL;
	}
	cur_node = header;
	for (int i=-1; i<=pos; i++){
		if (pos == -1)
			return cur_node;
		if (cur_node->next == NULL){
			printf("Invalid positionn");
			return NULL;
		}
		else{
			if (pos == i)
				return cur_node;
			cur_node = cur_node->next;
		}
	}
	return NULL;
}

int insert(linklist header, data_t value, int pos){
	linklist node, new_node;
	node = get_node(header, pos-1);
	new_node = create();
	new_node->next = node->next;
	new_node->data = value;
	node->next = new_node;
	return 0;
}

int del(linklist header, int pos){
	if (header == NULL){
		printf("Header is NULL");
		return -1;
	}
	linklist node = get_node(header, pos-1);
	if (node == NULL){
		printf("Invalid position");
		return -1;
	}
	if (node->next == NULL){
		printf("Invalid position");
		return -1;
	}
	linklist next_node = node->next;
	node->next = node->next->next;
	free(next_node);
	next_node = NULL;
	return 0;
}

linklist del_every_node(linklist header){
	linklist node;
	if (header == NULL)
		return NULL;
	node = header;
	while (header != NULL){
		node = header;
		header = header->next;
		free(node);
	}
	return NULL;
}

int show(linklist header){
	linklist p;
	if (header == NULL) {
		printf("Header is NULLn");
		return -1;
		}
	p = header;

	while (p->next != NULL){
		printf("%d ", p->next->data);
		p = p->next;
	}
	puts("");
	return 0;
}

int reverse(linklist header){
	if (header == NULL || header->next == NULL || header->next->next == NULL)
		return -1;
	linklist q, p = header->next->next;
	header->next->next = NULL;
	while (p != NULL){
		q = p;
		p = p->next;

		q->next = header->next;
		header->next = q;
	}
	return 0;
}

linklist list_free(linklist H) {
	linklist p;

	if (H == NULL)
		return NULL;

	p = H;

	printf("free:");
	while (H != NULL) {
		p = H;
		printf("%d ", p->data);
		H = H->next;
		free(p);
	}
	puts("");

	return NULL;
}

linklist adjmax(linklist header){
	linklist p, q, r;
	data_t sum;
	if (header == NULL){
		return NULL;
	}
	if (header->next == NULL || header->next->next == NULL || header->next->next->next == NULL)
		return header;

	q = header->next;
	p = header->next->next;
	r = q;
	sum = q->data + p->data;
	
	while (p->next != NULL){
		p = p->next;
		q = q->next;
		if (sum < q->data + p->data){
			sum = q->data + p->data;
			r = q;
		}
	}
	return r;
}

int merge(linklist header1, linklist header2){
	linklist p, q, r;
	if (header1 == NULL || header2 == NULL)
		return -1;
	p = header1->next;
	q = header2->next;
	r = header1;
	header1->next = NULL;
	header2->next = NULL;

	while( p && q){
		if (p->data <= q->data){
			r->next = p;
			p = p->next;
			r = r->next;
			r->next = NULL;
		}
		else{
			r->next = q;
			q = q->next;
			r = r->next;
			r->next = NULL;
		}
	}
	if (p == NULL){
		r->next = q;
	}
	else{
		r->next = p;
	}
	return 0;
}

数据结构（C语言）-线性表之单链表-学习笔记02

C/C++/C#相关栏目本月热门文章