本节目标
1.链表表示和实现（单链表+双向链表）
2.链表的常见OJ题
3.顺序表和链表的区别和联系
链表表示和实现（单链表+双向链表）
顺序表的问题及思考问题：
中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？下面给出了链表的结构来看看。
链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
逻辑结构
想必大家看的都是链表的逻辑结构，其实真实并不存在连接两个链表的箭头，为了更好理解罢了。箭头代表前面的节点存了，后面节点的指针。
物理结构
物理结构就是真正的结构，便于初学者学习!
是不是突然对链表有了更深刻的理解！
单链表的实现
// 1、无头+单向+非循环链表增删查改实现 // 动态申请一个节点 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 SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x); // 单链表删除pos位置的值 void SListErase(SListNode** pplist, SListNode* pos);
链表节点创建
链表的创建也是用结构体创建。
//类型创建 typedef int SLDataType; typedef struct SListNode { SLDataType date; //存值 struct SListNode* next; //存下一节点的指针 }SLNode;
// 动态申请一个节点 SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->date = x; newnode->next = NULL; return newnode; }
// 打印 void SListPrint(SLTNode* phead) { while (phead != NULL) { printf("%d ", phead->date); phead = phead->next; } printf("NULL\n"); }
//尾插 void SListPushBack(SLTNode** pphead, SLTDataType x) { if (*pphead == NULL) { *pphead = BuySListNode(x); } else { SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = BuySListNode(x); } }
//头插接口测试 void TestSList2() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPushFront(&plist, 6); SListPrint(plist); }
//头插 void SListPushFront(SLTNode** pphead, SLTDataType x) { if (!*pphead) { *pphead= BuySListNode(x); } else { SLTNode* first = BuySListNode(x); first->next = *pphead; *pphead = first; } }
//头插接口测试 void TestSList2() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPushFront(&plist, 6); SListPrint(plist); }
//头删 void SListPopFront(SLTNode** pphead) { if (!*pphead) { return; } else { *pphead = (*pphead)->next; } }
//头删接口测试 void TestSList3() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPushFront(&plist, 6); SListPrint(plist); SListPopFront(&plist); SListPopFront(&plist); SListPopFront(&plist); SListPopFront(&plist); SListPrint(plist); }
//尾删 void SListPopBack(SLTNode** pphead) { //1头结点为空 //2只有一个节点 //3多个节点 if (*pphead == NULL) { return; } else if ((*pphead)->next ==NULL) { *pphead = NULL; free(*pphead); } else { SLTNode* tail = *pphead; SLTNode* ret = *pphead; while (tail->next) { ret = tail; tail = tail->next; } tail = NULL; ret->next = NULL; free(tail); } }
//尾删接口测试 void TestSList4() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPushFront(&plist, 6); SListPrint(plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListPrint(plist); }
//查找节点x位置并返回节点位置 SLTNode* SListFind(SLTNode* phead, SLTDataType x) { if (phead == NULL) //节点为空 { return NULL; } else { SLTNode *ret= phead; while (ret) { if (ret->date == x) //找到了 { return ret; } ret = ret->next; } return NULL; //找不到 } }
// 在pos的前面插入x void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { return; } else if(*pphead==pos) { *pphead = newnode; newnode->next = pos; } else { SLTNode* ret = *pphead; while (ret->next != pos) { ret = ret->next; } ret->next = newnode; newnode->next = pos; } }
//任意位置查找插入测试 void TestSList5() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPushFront(&plist, 6); SListPrint(plist); SLTNode* pos = SListFind(plist,3); if (pos) { SListInsert(&plist,pos,0); } SListPrint(plist); }
//删除pos位置的值 void SListErase(SLTNode** pphead, SLTNode* pos) { if (*pphead==NULL) { return; } else if (*pphead == pos) { *pphead = NULL; } else { SLTNode* ret = *pphead; while (ret->next != pos) { ret = ret->next; } ret->next = pos->next; pos = NULL; free(pos); } }
//任意位置修改接口测试 void TestList6() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPushBack(&plist, 6); SListPrint(plist); SLTNode* pos = SListFind(plist, 3); if (pos) { SListErase(&plist, pos); } SListPrint(plist); }
