目录
1.前言
2.了解单链表
3.单链表代码实现
3.1 单链表结构体实现
3.2 创建节点
3.3 打印单链表
3.4 尾插
3.5 头插
3. 6 头删
3.7 尾删
3.8 查找
3.9 插入
3.9.1 在pos位置之前插入
3.9.2 在pos位置之后插入(主要使用这种功能)---不需要找pos前一个
3.10 删除
3.10.1 删除pos位置的值
3.10.2 删除pos后一个(主要使用这种功能)---不需要找pos前一个
3.11 单链表总结
1.前言
学习了顺序表发现有以下缺点:
1.1 空间不够,需要扩容(扩容有一定的空间浪费)。
1.2 头插、头删(需要移动数据)时间复杂度是O(N),效率低。
所以我们学习单链表来按需申请释放空间,不需要移动数据,提高效率。
2.了解单链表
概念:单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。
特点:每个结点除了存放数据元素外,还要存储指向下一个节点的指针
优点:不要求大片连续空间,改变容量方便。。
缺点:不可随机存取,要耗费一定空间存放指针。
单链表逻辑及重要性:
3.单链表代码实现
3.1 单链表结构体实现
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;//存放数据struct SListNode* next;//指向下一个结构体的指针
}SLTNode;
3.2 创建节点
void TestSList1()
{//struct SListNode* SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));assert(n1);SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));assert(n2);SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));assert(n3);SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));assert(n4);n1->data = 1;n2->data = 2;n3->data = 3;n4->data = 4;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;
}
3.3 打印单链表
cur = cur->next理解:
第一次进来cur指向的是链表的头,cur=cur—>next说明把下一个节点的地址赋给cur,现在的cur指向的是第二个结构体,是第二个结构体的地址.......
循环下去就可以打印出节点里的data数据,直到cur=NULL。
void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
3.4 尾插
注意点:
当链表为空的时候,newnode给phead时,由于phead是一个形参,函数中形参的改变不会改变实参。
这时要改变指针变量(plist)就要传指针变量的地址——就要传二级指针。
void SListPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{// 找尾节点SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
3.5 头插
单链表头插不需要和尾插一样要特殊处理
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}
3. 6 头删
void SListPopFront(SLTNode** pphead)
{assert(*pphead != NULL);//暴力检查//if (*pphead == NULL) //温柔检查// return;SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
3.7 尾删
void SListPopBack(SLTNode** pphead)
{assert(*pphead);// 1、只有一个节点// 2、多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{ //两种方法 /*SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;*/
//SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}
3.8 查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}
3.9 插入
3.9.1 在pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){ assert(pos);assert(ppheart);//头插if (pos= *pphead){SListPushFront(pphead.x);}else{SLTNNode* prev= *ppheart;while(prev->next !=pos){prev=prev->next;}SLTNode* newnode=BuySListNode(x);prev->next=newnode;newnode->next=pos; }
3.9.2 在pos位置之后插入(主要使用这种功能)---不需要找pos前一个
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);/*SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;*/// 不在乎链接顺序SLTNode* newnode = BuySListNode(x);SLTNode* next = pos->next;// pos newnode nextpos->next = newnode;newnode->next = next;
}
3.10 删除
3.10.1 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);assert(ppheart);//头删 if (pos= *pphead){SListPopFront(pphead);}else{ SLTNode* prev= *pphesd;while(prev->next !=pos){prev=prev->next;}prev->next= pos->next;free(pos);}
3.10.2 删除pos后一个(主要使用这种功能)---不需要找pos前一个
void SListEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL)return;SLTNode* del = pos->next;//pos->next = pos->next->next;//这样就释放不了节点pos->next = del->next;free(del);del = NULL;
}
3.11 单链表总结
由单链表的在pos位置之后插入和删除pos位置之后的值可知,单链表没有完全解决顺序表的缺陷,所以我们后面学习双向的链表来提高效率。