线性表之链表

为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。

• 数据域：我们把存储数据元素信息的域称为数据域。
• 指针域：存储直接后继位置的域称为指针域。
• 指针/链：指针域中存储的信息称做指针或链。
• 结点(Node)：数据域与指针域这两部分信息组成数据元素ai的存储映像，称为结点(Node)

明白了单链表名字的由来。n个结点（ai的存储映像）链结成一个链表，即为线性表（ai, a2…，an）的链式存储结构，因为此链表的每个结点中只包含一个指针域。因为指针域中存储的信息称做链，而且这个链每个结点都只有一个，所以叫做单链表。

和顺序表一样先看它的定义，再写它的操作。

//List.h
#pragma once

typedef int DataType;

typedef struct ListNode {
	DataType data;
	struct ListNode* next;
}ListNode;

void ListInit(ListNode** ppFirst);  // 初始化链表
void ListDestroy(ListNode** ppFirst);  //销毁链表
void ListPushFront(ListNode** ppFirst, DataType data);   // 头插
void ListPushBack(ListNode** ppFirst, DataType data);    // 尾插
void ListInsert(ListNode** ppFirst, DataType data, int pos);  //在中间插入
void ListPopFront(ListNode** ppFirst);   //头删
void ListPopBack(ListNode** ppFirst);    // 尾删
void ListEarse(ListNode** ppFirst, ListNode* pos);    //删除中间元素
void ListEarse2(ListNode** ppFirst, DataType data);  // 另一种写法，上面的传参我感觉不太方便
ListNode* ListFind(ListNode** ppFirst, DataType data);   //查找
void ListPrint(ListNode** ppFirst);   //打印链表
static ListNode* CreateNode(DataType data);   //创建一个结点
 

 

//List.c
#include "List.h"
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>

void ListInit(ListNode** ppFirst) {
	assert(ppFirst != NULL);
	*ppFirst = NULL;
}

static ListNode* CreateNode(DataType data) {
	ListNode* newNode = (ListNode *)malloc(sizeof(ListNode));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

void ListDestroy(ListNode** ppFirst) {
	assert(ppFirst != NULL);
	ListNode* next;
	ListNode* cur;
	cur = *ppFirst;
	while (cur != NULL) {
		next = cur->next;
		free(cur);
		cur = next;
	}
	*ppFirst = NULL;
}

void ListPushFront(ListNode** ppFirst, DataType data) {
	assert(ppFirst != NULL);
	ListNode* newNode = CreateNode(data);
	//特殊情况  链表为空 
	if (*ppFirst == NULL)
	{
		*ppFirst = newNode;
		return;
	}
	newNode->next = *ppFirst;
	*ppFirst = newNode;
}
void ListPushBack(ListNode** ppFirst, DataType data) {
	assert(ppFirst != NULL);
	ListNode* newNode = CreateNode(data);
	ListNode* cur = *ppFirst;
	if (*ppFirst == NULL)
	{
		*ppFirst = newNode;
		return;
	}
	while (cur->next != NULL)
	{
		cur = cur->next;
	}
	cur->next = newNode;

}

void ListInsert(ListNode** ppFirst, DataType data, int pos) {
	assert(ppFirst != NULL);
	ListNode* newNode = CreateNode(data);
	//if (pos == *ppFirst) {
	//	ListPushFront(ppFirst, data);
	//	return;
	//}
	ListNode * cur = *ppFirst;
	//while (cur->next != pos) {
	//	cur = cur->next;
	//}
	//newNode->next = pos;
	//cur->next = newNode;
	ListNode* pre =NULL; 
	for (int i = 1; i < pos; i++) {
		pre = cur;
		cur = cur->next;
	}
	newNode->next = cur;
	pre->next = newNode;
}

void ListPopFront(ListNode** ppFirst) {
	assert(ppFirst);
	assert(*ppFirst);
	ListNode* del = *ppFirst;
	*ppFirst = del->next;
	free(del);
}
void ListPopBack(ListNode** ppFirst) {
	assert(ppFirst);
	assert(*ppFirst);   
	// 谨记要考虑特殊情况  
	if ((*ppFirst)->next == NULL) {
		free(*ppFirst);
		*ppFirst = NULL;
		return;
	}
	ListNode* del;
	ListNode* cur = *ppFirst;
	while (cur->next->next != NULL) {
		
		cur = cur->next;
	}
	del = cur->next;
	cur->next = NULL;
	free(del);
}
void ListEarse(ListNode** ppFirst,ListNode* pos) {
	assert(ppFirst != NULL);
	ListNode* cur = (*ppFirst);
	if (pos == *ppFirst) {
		ListPopFront(ppFirst);
	}
	while (cur->next != pos) {
		cur = cur->next;
	}
	cur->next = pos->next;
	free(pos);
	

}
ListNode*  ListFind(ListNode** ppFirst, DataType data) {
	assert(ppFirst != NULL);
	ListNode* cur = *ppFirst;
	while (cur != NULL) {
		if (cur->data == data) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void ListEarse2(ListNode** ppFirst, DataType data) {
	assert(ppFirst);
	ListNode* del = ListFind(ppFirst, data);
	if (del == NULL) {
		printf("没有值为%d 的数", data);
		return;
	}
	ListNode* cur = *ppFirst;
	while (cur->next != del) {
		cur = cur->next;
	}
	cur->next = del->next;
	free(del);
}

void ListPrint(ListNode** ppFirst) {
	assert(ppFirst != NULL);
	ListNode* cur = *ppFirst;
	while (cur != NULL) {
		printf("%d ->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//main.c
#include "SeqList.h"

void test()
{
	SeqList s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 5);
	SeqListPushBack(&s1, 6);
	SeqListPushBack(&s1, 7);
	SeqListInsert(&s1, 4, 3);
	SeqListPushFront(&s1, 0);
	SeqListPrint(&s1);
	SeqListPopFront(&s1);
	SeqListPrint(&s1);
	SeqListPopBack(&s1);
	SeqListPrint(&s1);
	SeqListEarse(&s1, 3);
	SeqListPrint(&s1);
}
int main()
{
	test();
	getchar();
	return 0;
}