[数据结构与算法]C语言——链表的使用

C语言——链表的使用

链表是一些包含数据的独立数据结构（通常称为节点）的集合。链表中的每个节点通过链或指针连接在一起。程序通过指针访问链表中的节点。通常节点是动态分配的。

创建链表

对于一个处理链表的程序而言，各节点在物理上是否相邻并没有什么区别，因为程序始终用链从一个节点移动到另一个节点。

#include <stdio.h>
#include <stdlib.h>  
#include <string.h>  
#define TSIZE 45   
struct film {
	char title[TSIZE];
	int rating;
	struct film * next;     
};
int main(void)
{
	struct film * head = NULL;  
	struct film * prev, *current;
	char input[TSIZE];

	puts("Enter first movet title : ");
	while (gets(input) != NULL && input[0] != '\0')
	{
		
		current = (struct film *) malloc(sizeof(struct film));
		if (head == NULL)  
			head = current; 
		else               
			prev->next = current; 
		current->next = NULL;  
		strcpy_s(current->title, TSIZE,input);  
		puts("Enter your rating <0-10> : ");
		scanf_s("%d", &current->rating);
		while (getchar() != '\n')        
			continue;
		puts("Enter next movie title (empty line to stop) :  ");
		prev = current; 
	}
	
	if (head == NULL)  
		printf("No data entered ");
	else
		printf("Here is the movie list : \n");
	current = head;   
	while (current != NULL) 
	{
		printf("movie: %s Rating: %d \n", current->title, current->rating);
		current = current->next;   
	}
	
	current = head;
	while (current != NULL)
	{
		free(current);
		current = current->next;
	}
	printf("Bye \n");
	return 0;
}

有序单向链表的插入操作

这段简化代码的关键之处在于，创建一个耳机指针，就拥有了一个指向该节点的指针（一级指针）和一个指向该节点link字段的指针（二级指针）。对于第一个节点，使用这个二级指针就是节点的根指针，初始化的时候引用二级指针current = *linkp，那么current->link就指向了下一节点。链表的使用不要求物理内存的连续，那么找到插入位置之后，只需要将插入的节点的link指向下一节点，将上一节点的指针 *linkp指向当前节点的地址即可。

#include <stdio.h>
#include <stdlib.h>

#define FALSE	0
#define TRUE	1
typedef struct NODE
{
	struct NODE* link;
	int value;
}ListNode;

int sll_insert(register ListNode **linkp, int new_value)
{
	register ListNode *current;
	register ListNode *new;
	//current = *linkp 指向第一个节点的地址
	//linkp二级指针，是一级指针（current->link)的地址
	while ((current = *linkp) != NULL 
			&& current->value < new_value)
	{
		linkp = &current->link;
	}

	new = (ListNode*)malloc(sizeof(ListNode));
	if (new == NULL)
	{
		return FALSE;
	}
	new->value = new_value;

	new->link = current;	//插入节点的指针指向下一节点
	*linkp = new;			//上一节点的指针指向插入的节点
	return TRUE;
}