前言:

        上一文中我们介绍了顺序表的特点及实现,但是顺序表由于每次扩容都是呈二倍增长(扩容大小是自己定义的),可能会造成空间的大量浪费,但是链表却可以解决这个问题.

概念及结构:

         链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

注意:

1. 链式结构在逻辑上是连续的,但是在物理上不一定连续
2. 结点一般都是从堆上申请出来的
3. 从堆上申请的空间是按照一定的策略来分配的,两次申请的空间可能连续也可能不连续

    分类:

1. 单向或双向
2. 带头或不带头
3. 循环或不循环

    虽然链表有这么多种结构,但是在实际中最常用的还是两种结构:

• 无头单向非循环链表:

          结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈       希桶、图的邻接表等等。       

•  带头双向循环链表:

       结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单

无头单向非循环链表

接口:

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 != x&&ret->next){ret=ret->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* newnode=BuySListNode(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);
}