Loading... # 链表 ## 单链表 ### 基本概念 每个链表结点包括两个域：用来存储数据的数据域和用来链接下个结点的指针域。链表由若干个结点链接而成，头指针head指向链表中的第一个结点，称为表头。由前一个结点的指针可以访问到后面的结点，前结点指针为空说明到达表尾。与顺序存储相比不涉及任何结点的移动。 不含结点的链表为空链表，此时head为空(NULL)。当链表中插入结点时要先判断是否是空链表。是则修改head，否则从表头开始寻找插入位置。实际应用中可以附加一个空的头结点，这样空链表的head不是空指针，无需判断头指针是否为空。 ### 单链表**结点**结构 单链表结点的定义中包含了数据和指针这两个要素。 Node.h ```c # 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 ```c #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 ```c struct linkedStack { LinkedList *stack; }; typedef struct linkedStack LinkedStack; void InitLinkedStack(LinkedStack *);/*初始化函数*/ void Push(LinkedStack *, ElementType item);/*操作栈的方法*/ ElementType Pop(LinkedStack *);/*弹栈*/ ElementType Top(LinkedStack *);/*取栈顶的表目*/ ``` ### 队列的单链表实现 linkedqueue.h ```c 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 ```c 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 ```c 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 所示。  代码见书 Last modification：January 20, 2023 © Allow specification reprint Like 如果觉得我的文章对你有用，请留下评论。