表（ADT）

顺序表这种数据结构比较简单，这里不在详细讲解。

链表的类型声明：

第二行应该有:

#define _LIST_H

具有表头的链表模型

 表头中的element一般用于存储表的大小（代码实现中如此）

表的操作

 空表判断：如果表头的next指针->NULL;则表中没有数据。

末尾判断：如果所给节点位置的next指针为空，则为末尾；

表的插入：

三个参数：插入值，要插入的表的表头，以及插入位置（一般用头插和尾插）；

插入过程分析：

注意顺序不可变；

T->next = p->next;

p->next = T;

 表的数据查找：

参数：数据和表；

临时 p指向头节点的next，遍历一直找到x为止，未找到，则到了表的末尾，则返回NULL；

查找前一个结点：

原理相同，只不过要多查一个，这个函数用于删除节点。

不同点在于它查找p的下一个节点的数据；

 表的数据删除：

过程分析：

令前节点指向要删除节点的下一个节点->删除要删除的节点，这里我们用TmpCell保存要删除的节点。

非尾节点

 尾节点

直接让前结点指向空，然后删除尾节点。

表的删除：

p = L->next,把p指向存储数据的表，

L->next = NULL;把表头指向空；

接下来就是循环释放每一个节点。

 双链表

模型

 循环链表模型

 清楚了单链表，双链表只是改指针域的问题，其他差别不算太大。

多重表

链表的嵌套。实现过程比较复杂，这里看图也能看个大概。

下面是源码。（注释已删除，不过函数名具体，自行写一遍，基本就掌握了单链表）

单链表的数组实现

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define SIZE 100

struct List* createList();

void insertFirst(struct List* p, int x);
void insertLast(struct List* p, int x);

int find(struct List* p, int x);

int findKth(struct List* p, int position);

void delete(struct List* p, int x);

bool isEmpty(struct List* p);

void printList(struct List* p);

int size(struct List* p);

struct List
{
	int element[SIZE];

	int length;
};

int main(int argc, char const *argv[])
{
	int index = 0;
	int element = 0;

	struct List* list = createList();
	printf("List isEmpty?:%s",isEmpty(list)?"YES":"NO");
	puts("AFTER INSERT_F 1,2 BY TURN");
	insertFirst(list,1);
	insertFirst(list,2);
	printList(list);
	puts("AFTER INSERT_L 3,4 BY TURN");
	insertLast(list,3);
	insertLast(list,4);
	printList(list);
	printf("List isEmpty?:%s",isEmpty(list)?"YES":"NO");
	index = find(list,3);
	if (index == -1)
	{
		puts("NOT FIND");
	}
	else
	{
		printf("FIND ELEMENT INDEX: %d\n",index);
	}

	element = findKth(list,2);
	printf("FIND_KTH_2: %d\n",element);
	puts("AFTER DEL 3");
	delete(list, 3);
	printList(list);

	printf("THE SIZE: %d\n",size(list));
	return 0;
}
struct List* createList()
{
	struct List* p;
	p = malloc(sizeof(struct List));

	p->length = 0;

	return p;
}
bool isEmpty(struct List* p)
{
	return p->length == 0;
}
void insertFirst(struct List* p, int x)
{
	if (p->length >= SIZE)
	{
		puts("OUT OF SPACE");
		return;
	}

	for (int i = p->length; i > 0; --i)
	{
		p->element[i] = p->element[i - 1];
	}
	p->element[0] = x;
	p->length++;

	return;
}
void insertLast(struct List* p, int x)
{
	int length = p->length;
	if (length >= SIZE)
	{
		puts("OUT OF SPACE");
		return;
	}

	p->element[length] = x;
	p->length++;
}
void printList(struct List* p)
{
	for (int i = 0; i < p->length; ++i)
	{
		printf("List element: %d\n",p->element[i] );
	}
}
int find(struct List* p, int x)
{
	for (int i = 0; i < p->length; ++i)
	{
		if (p->element[i] == x)
		{
			return i;
		}
	}

	return -1;
}
int findKth(struct List* p, int position)
{
	if (position <= 0)
	{
		puts("PLEASE POSITIVE");
		exit(1);
	}
	if (position > p->length)
	{
		puts("OUT OF LENGTH");
		exit(1);
	}

	return p->element[position - 1];
}
void delete(struct List* p, int x)
{
	int length = p->length;
	for (int i = 0; i < p->length; ++i)
	{
		if (p->element[i] == x)
		{
			for (; i < p->length -1; ++i)
			{
				p->element[i] = p->element[i + 1];
			}
			p->length--;
			break;
		}
	}
	if (length == p->length)
	{
		printf("NOT FIND %d\n",x);
	}
}
int size(struct List* p)
{
	return p->length;
}

链表实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct Node* createHeaderNode();

void insertFirst(struct Node* header, int x);
void insertLast(struct Node* header, int x);

struct Node* find(struct Node* header, int x);
struct Node* findKth(struct Node* header, int x);

void delete(struct Node* header, int x);
bool isEmpty(struct Node* header);

int size(struct Node* header);

void printList(struct Node* header);

struct Node
{
	int element;
	struct Node* next;
};
int main(int argc, char const *argv[])
{
	struct Node* node;
	struct Node* header;

	header = createHeaderNode(header);
	printf("List is empty?: %s\n",isEmpty(header)?"YES":"NO");
	puts("INSERT_FIRST 1,2 BY TURN");
	insertFirst(header,1);
	insertFirst(header,2);

	printList(header);

	puts("INSERT_LAST 3,4 BY TURN");
	insertLast(header,3);
	insertLast(header,4);

	printList(header);

	printf("List is empty?: %s\n",isEmpty(header)?"YES":"NO");

	node = find(header,3);
	if (node == NULL)
	{
		printf("NOT FIND\n");
	}
	else
	{
		printf("FIND %d\n",node->element);
	}

	node = findKth(header,2);
	if (node == NULL)
	{
		printf("NOT FIND\n");
	}
	else
	{
		printf("FIND_KTH_2 %d\n",node->element);
	}

	delete(header,3);
	puts("DELETE 3");
	printList(header);

	printf("LIST SIZE %d\n",size(header));
	return 0;
}

struct Node* createHeaderNode()
{
	struct Node* p;

	p = (struct Node*)malloc(sizeof(struct Node));

	if (p == NULL)
	{
		printf("OUT OF SPACE\n");
		exit(1);
	}

	p->next = NULL;
	p->element = 0;
	return p;
}
bool isEmpty(struct Node* header)
{
	return header->next == NULL;
}
void insertFirst(struct Node* header, int x)
{
	struct Node* tmp;

	tmp = (struct Node*)malloc(sizeof(struct Node));

	if (tmp == NULL)
	{
		printf("OUT OF SPACE\n");
		return;
	}

	tmp->element = x;
	tmp->next = header->next;
	header->next = tmp;
	header->element++;
	return;
}
void printList(struct Node* header)
{
	struct Node* p;
	p = header->next;
	while(p != NULL)
	{
		printf("NODE ELEMENT %d\n",p->element);
		p = p->next;
	}

	return;
}
void insertLast(struct Node* header, int x)
{
	struct Node* p;
	struct Node* tmp;

	tmp = (struct Node*)malloc(sizeof(struct Node));

	if (tmp == NULL)
	{
		printf("OUT OF SPACE\n");
		return;
	}

	tmp->element = x;
	tmp->next = NULL;
	p = header;

	while(p->next != NULL)
	{
		p = p->next;
	}

	p->next = tmp;
	header->element++;

	return;
}
struct Node* find(struct Node* header, int x)
{
	struct Node* p;
	p = header->next;

	while(p != NULL && p->element != x)
	{
		p = p->next;
	}
	return p;
}
struct Node* findKth(struct Node* header, int position)
{
	int count = 1;
	struct Node* p;

	if (position <= 0)
	{
		printf("POSITION IS POSITIVE\n");
		return NULL;
	}

	p = header->next;
	while(p != NULL)
	{
		if (count == position)
		{
			return p;
		}

		p = p->next;
		count++;
	}

	return NULL;
}
void delete(struct Node* header, int x)
{
	struct Node* privious;
	struct Node* p;

	privious = header;
	p = header->next;

	while(p != NULL)
	{
		if (p->element == x)
		{
			privious->next = p->next;
			free(p);

			break;
		}
		else
		{
			privious = p;
			p = p->next;
		}
	}

	header->element--;
	return;
}
int size(struct Node* header)
{
	return header->element;
}