链表
单链表
基本概念
每个链表结点包括两个域：用来存储数据的数据域和用来链接下个结点的指针域。链表由若干个结点链接而成，头指针head指向链表中的第一个结点，称为表头。由前一个结点的指针可以访问到后面的结点，前结点指针为空说明到达表尾。与顺序存储相比不涉及任何结点的移动。
不含结点的链表为空链表，此时head为空(NULL)。当链表中插入结点时要先判断是否是空链表。是则修改head，否则从表头开始寻找插入位置。实际应用中可以附加一个空的头结点，这样空链表的head不是空指针，无需判断头指针是否为空。
单链表结点结构
单链表结点的定义中包含了数据和指针这两个要素。
Node.h
# ifndef _NODE_H
# define _NODE_H
#include <stdio.h>
#include <stdlib.h>
struct node
{
struct node *next;
ElementType data;
};
typedef struct node Node;
void InitNode(Node *, ElementType item, Node *prt);/*初始化*/
void InsertAfter(Node *, Node *);/*插入一个单链表结构*/
Node *DeleteAfter(Node *);/*删除一个单链表结点*/
Node *GetNode(ElementType item, Node *ptr);/*创建一个单链表的结点*/
void FreeNode(Node *);/*释放一个单链表的结点*/单链表结构
利用单链表结点结构构建单链表结构。包含表头指针front和表尾指针rear。此外，为了处理方便，包含结点个数size，当前结点位置position，当前结点指针currPtr，指向当前结点前驱指针prevPtr
linkedlist.h
#include "Node.h"/*书上没写*/
#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H
enum blooean {FALSE, TRUE};
typedef enum boolean Bool;
struct linkedList
{
Node *front, *rear;
Node *PrevPtr, *currPtr;
int size;
int positoin;
};
typedef struct likedList LinkedList;
Node *GetNode(ElementTYpe itme, Node *prt);/*申请结点空间的函数*/
void FreeNode(Node *p);/*释放结点空间的函数*/
void InitLinkedList(linkedList *);/*初始化函数*/
Bool IsEmpty(LinkedList *);/*判断列表是否为空*/
int NextLNode(LinkedList *);/*求当前结点后继的函数*/
int SetPosition(LinkedList *, int pos);/*重定位当前结点*/
void InsertAt(LinkedList *,ElementType item);/*在当前结点处插入结点的函数*/
void InsertAfter(LinkedList *, ElementType item);/*在当前结点后面插入结点的函数*/
void DeleteAt(LinkedList *);/*删除当前结点的函数*/
void DeleteAfter(LinkedList *);/*删除当前结点后继的函数*/
ElementType GetData(LinkdedList *);/*修改和访问数据的函数*/
void SetData(LinkedList *, ElementType item);
void Clear(LinkedList *);/*清空链表的函数*/
#endif注意，在这个头文件中，当前结点这个值是存储在LinkedList结构中的，而不能通过传入，所以要修改结点要先定位
栈的单链表实现
用单链表结构存储的栈又称为链栈，
linkedStack.h
struct linkedStack
{
LinkedList *stack;
};
typedef struct linkedStack LinkedStack;
void InitLinkedStack(LinkedStack *);/*初始化函数*/
void Push(LinkedStack *, ElementType item);/*操作栈的方法*/
ElementType Pop(LinkedStack *);/*弹栈*/
ElementType Top(LinkedStack *);/*取栈顶的表目*/队列的单链表实现
linkedqueue.h
struct linkedQueue
{
LinkedList *queue;
};
typedef struct linkedQueue LinkedQueue;
void InitLinkedQueue(LinkedQueue *);/*初始化一个链队列*/
void In(LinkedQueue *, ElementType item);/*插入一个新数据*/
ElementType Out(LinkedQueue *);/*队列中删除一个新数据元素*/
ElementType Front(LinkedQueue *);/*取队列的头部元素*/
void ClearLQ(LinkedQueue *);/*清除队列的数据元素*/
Bool IsEmptyLQ(LinkedQueue *);/*判断队列是否为空*/因为反复调用SetPosition函数，插入，删除运算不能保证O(1)。下面用循环队列优化，只有尾结点指针，能保证插入删除运算时间开销为O(1)
clnkqueue.h
typedef int T;
struct LNode{
T data;
LNode * next;
};
typedef LNode CLnkQueue;
void CLQ_Free(CLnkQueue *q);
void CLQ_MakeEmpty(CLnkQUeue **q);
BOOL CLQ_IsEmpty(CLnkQueue *q);
int CLQ_Length(CLnkQueue *q);
void CLQ_In(CLnkQueue *q, T x);
T CLQ_Out(CLnkQueue** q);
T CLQ_Head(CLnkQueue* q);
void CLQ_Print(CLnkQueue *q);单链表的应用举例
p75自己看书
循环链表
附加头结点的链表，表尾的指针域指向表的附加头结点。判断表头是否为空只要判断header(附加头结点)的指针是否指向自身
循环链表结点结构
cNode.h
struct cNode
{
struct cNode *next;
ElementType data;
};
typedef struct cNode CNode;
void InitCNode(CNode *, ElementType);
void InsertCNAfter(CNode *, CNode *ptr);
CNode *DeleteCNAfter(CNode *);
CNode *NewCNode(ElementType item);/*申请循环链表结点空间的函数*/双链表
每个结点有两个指针，一个prev指向前戏，一个next指向后继。通过两个指针域，多个双链结点可构成两个循环链，建立了一种灵活，有效的动态结构，称为双向循环链表，简称双链表。
在双链表中插入一个结点时，涉及插入点前一结点的 next指针、插入点后一结点的prev 指针以及被插入结点的两个指针的修改。在结点后插入的处理过程如图上图所示。需要注意的是，如果不引用临时指针变量，则必须按合理的顺序进行操作，例如按(1)、(2)、(3)、(4)的顺序或者按(1)、(3)、(2)、(4)的顺序，如图3.9所示。从双链表中删除一个结点的过程，只需修改前一结点的next指针和后一结点的prev指针即可，如图3.10 所示。
代码见书