兰州新区小程序建站,南通 网站优化,做好史志网站建设,最新军事新闻头条前言: 上一文中我们介绍了顺序表的特点及实现,但是顺序表由于每次扩容都是呈二倍增长(扩容大小是自己定义的),可能会造成空间的大量浪费,但是链表却可以解决这个问题.
概念及结构: 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接…前言: 上一文中我们介绍了顺序表的特点及实现,但是顺序表由于每次扩容都是呈二倍增长(扩容大小是自己定义的),可能会造成空间的大量浪费,但是链表却可以解决这个问题.
概念及结构: 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 注意:
链式结构在逻辑上是连续的,但是在物理上不一定连续结点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的,两次申请的空间可能连续也可能不连续 分类:
单向或双向带头或不带头循环或不循环 虽然链表有这么多种结构,但是在实际中最常用的还是两种结构:
无头单向非循环链表: 结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈 希桶、图的邻接表等等。 带头双向循环链表: 结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单 无头单向非循环链表
接口:
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode** pphead,SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode** pphead,SListNode* pos);
// 在pos的前面插入
SListNode* SListInsertFront(SListNode** pphead, SListNode* pos, SLTDateType x);
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
//单链表摧毁
void SLTDestroy(SLNode** pphead);1.动态申请结点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc);return;}newnode-data x;newnode-next NULL;
}
2.单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}
3.单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newnode BuySListNode(x);if (*pplist NULL){*pplist newnode;}else{SListNode* tail *pplist;while (tail-next){tail tail-next;}tail-next newnode;}
}
4.单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode BuySListNode(x);newnode-next *pplist;*pplist newnode;
}
5.单链表尾删
void SListPopBack(SListNode** pplist)
{assert(*pplist);SListNode* pre NULL;SListNode* tail *pplist;if ((*pplist)-next NULL){*pplist NULL;}else{/* while (tail-next){pre tail; tail tail-next;}free(tail);tail NULL;pre-next NULL;*/SListNode* tail *pplist;while (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;}
}6.单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);if ((*pplist)-next NULL){*pplist NULL;}else{SListNode* ret ((*pplist)-next);free(*pplist);*pplist ret;}
}
7.单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{assert(plist);SListNode* ret plist;while (ret-data ! xret-next){retret-next;}if (ret-next NULL ret-data ! x)return NULL;elsereturn ret;
}
8.摧毁单链表
void SLTDestroy(SListNode** pphead)
{SListNode* cur *pphead;SListNode* ret NULL;while (cur){ret cur-next;free(cur);cur ret;}*pphead NULL;
}9.在pos位置之后插入x
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode** pphead,SListNode* pos, SLTDateType x)
{assert(pphead);//检测插入位置是否存在assert(pos); assert(*pphead);SListNode* newnodeBuySListNode(x);newnode-next pos-next;pos-next newnode;
}
10.删除pos位置之后的值
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode** pphead,SListNode* pos)
{assert(pphead);assert(pos);assert(pos-next);assert(*pphead);SListNode* tmp pos-next;pos-next pos-next-next;free(tmp);tmp NULL;
}
11.在pos位置之前插入x
SListNode* SListInsertFront(SListNode** pphead, SListNode* pos, SLTDateType x)
{assert(pphead);assert(pos);assert(*pphead);SListNode* newnode BuySListNode(x);SListNode* pre *pphead;if (*pphead pos){SListPushFront(pphead,x);}else{while (pre-next ! pos){pre pre-next;}newnode-next pos;pre-next newnode;}}
12.删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead pos){SListPopFront(pphead);}else{SListNode* pre *pphead;while (pre-next ! pos){pre pre-next;}pre-next pos-next;free(pos);pos NULL;}} 带头双向循环链表
接口:
// 带头双向循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
1.创建返回链表的头节点
ListNode* ListCreate(LTDataType x)
{ListNode* node (ListNode*)malloc(sizeof(ListNode));if (node NULL){perror(malloc);exit(-1);}node-_data x;node-_next NULL;node-_prev NULL;return node;
}
2.双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-_next;while (cur ! pHead){ListNode* next cur-_next;free(cur);cur next;}free(pHead);
}
3.双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-_next;while (cur ! pHead){printf(%d - , cur-_data);cur cur-_next;}
}
4.双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{ListNode* newnode ListCreate(x);ListNode* tail pHead-_prev; //尾指针tail-_next newnode;newnode-_next pHead;newnode-_prev tail;pHead-_prev newnode;
}
5.双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead-_next!pHead);ListNode* tail pHead-_prev;pHead-_prev tail-_prev;tail-_prev-_next pHead;free(tail);tail NULL;
}
6.双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode ListCreate(x);newnode-_next pHead-_next;pHead-_next-_prev newnode;pHead-_next newnode;newnode-_prev pHead;
}
7.双向链表头删
void ListPopFront(ListNode* pHead)
{ListNode* pHeadNext pHead-_next;pHeadNext-_next-_prev pHead;pHead-_next pHeadNext-_next;free(pHeadNext);pHeadNext NULL;
}
8.双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-_next;while (cur ! pHead){if (cur-_data x)return cur;cur cur-_next;}return NULL;
}
9.双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* posprev pos-_prev;ListNode* newnode ListCreate(x);newnode-_next pos;pos-_prev newnode;posprev-_next newnode;newnode-_prev pos-_prev;
}
10.双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posprev pos-_prev;ListNode* posnext pos-_next;posprev-_next posnext;posnext-_prev posprev;free(pos);
}
