交通建设监理协会网站,大学生网站建设方案,马鞍山网站建设公,嘉兴百度快照优化排名CSDN主页#xff1a;醋溜马桶圈_C语言进阶,初始C语言,数据结构-CSDN博客 Gitee主页#xff1a;mnxcc (mnxcc) - Gitee.com 专栏#xff1a;数据结构_醋溜马桶圈的博客-CSDN博客 目录 1.认识单链表 2.创建单链表 3.单链表的操作 3.1打印单链表 3.2开辟新空间 3.3尾插 3.4头插… CSDN主页醋溜马桶圈_C语言进阶,初始C语言,数据结构-CSDN博客 Gitee主页mnxcc (mnxcc) - Gitee.com 专栏数据结构_醋溜马桶圈的博客-CSDN博客 目录 1.认识单链表 2.创建单链表 3.单链表的操作 3.1打印单链表 3.2开辟新空间 3.3尾插 3.4头插 3.5尾删 3.6头删 3.7查找 3.8在pos前面插入 3.9删除pos位置 3.10销毁 3.11在pos位置之后插入 3.12删除pos位置之后的值 4.总代码 SList.h SList.c test.c 我们之前学习了顺序表的有关知识顺序表存在下面的问题 尾插效率还不错头插或中间插入删除需要挪动数据效率低满了以后只能扩容扩容是有一定的消耗的扩容一般存在一定的空间浪费 1.认识单链表
这篇文章我们来认识一下单链表 如果想要插入一个结点就不需要挪动数据了改指针的指向就可以了 同样我们删除结点直接将前一个结点的指针指向后一个结点就可以了 首先我们还是从工程的角度去考虑创建SList.h SList.c test.c三个文件 SList.h放置函数的声明
SList.c放置函数的定义
test.c进行测试
2.创建单链表 3.单链表的操作
3.1打印单链表
//打印单链表
//尽量不要动phead
void SLTPrint(SLNode* phead)
{SLNode* cur phead;while (cur ! NULL){printf(%d-, cur-val);cur cur-next;}printf(NULL\n);
}
3.2开辟新空间
//开辟新空间
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;return newnode;
}
3.3尾插
//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);if (*pphead NULL){*pphead newnode;}else{SLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
3.4头插
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);newnode-next *pphead;*pphead newnode;
}
3.5尾删
//尾删
void SLTPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLNode* prev NULL;SLNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}
3.6头删
//头删
void SLTPopFront(SLNode** pphead)
{assert(*pphead);SLNode* tmp *pphead;*pphead (*pphead)-next;free(tmp);
}
3.7查找
//查找
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{SLNode* cur phead;while (cur){if (cur-val x){return cur;}else{cur cur-next;}}return NULL;
}
3.8在pos前面插入
//在pos前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert(pos);assert(*pphead);//assert((!pos !(*pphead)) || (pos (*pphead)));if (*pphead pos){SLTPushFront(pphead, x);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLNode* newnode CreateNode(x);prev-next newnode;newnode-next pos;}
}
3.9删除pos位置
//删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead pos){SLTPopFront(pphead);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
3.10销毁
//销毁
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur-next ! NULL){SLNode* next cur-next;free(cur);cur next;}*pphead NULL;
}
3.11在pos位置之后插入
// 单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{SLNode* newnode CreateNode(x);newnode-next pos-next;pos-next newnode;
} 3.12删除pos位置之后的值
// 单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos)
{assert(pos-next ! NULL);pos-next pos-next-next;free(pos-next);pos-next NULL;
}
4.总代码
SList.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
//创建单链表
typedef int SLNDataType;
typedef struct SLNode
{SLNDataType val;struct SLNode* next;
}SLNode;//打印单链表
//尽量不要动phead
void SLTPrint(SLNode* phead);
//开辟新空间
SLNode* CreateNode(SLNDataType x);//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x);
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x);
//尾删
void SLTPopBack(SLNode** pphead);
//头删
void SLTPopFront(SLNode** pphead);//查找
SLNode* SLTFind(SLNode* phead, SLNDataType x);
//在pos前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
//删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos); // 单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLNDataType x);
// 单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos);//销毁
void SLTDestroy(SLNode** pphead);SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h
//打印单链表
//尽量不要动phead
void SLTPrint(SLNode* phead)
{SLNode* cur phead;while (cur ! NULL){printf(%d-, cur-val);cur cur-next;}printf(NULL\n);
}
//开辟新空间
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;return newnode;
}
//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);if (*pphead NULL){*pphead newnode;}else{SLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);newnode-next *pphead;*pphead newnode;
}
//尾删
void SLTPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLNode* prev NULL;SLNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}
//头删
void SLTPopFront(SLNode** pphead)
{assert(*pphead);SLNode* tmp *pphead;*pphead (*pphead)-next;free(tmp);
}
//查找
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{SLNode* cur phead;while (cur){if (cur-val x){return cur;}else{cur cur-next;}}return NULL;
}
//在pos前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert(pos);assert(*pphead);//assert((!pos !(*pphead)) || (pos (*pphead)));if (*pphead pos){SLTPushFront(pphead, x);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLNode* newnode CreateNode(x);prev-next newnode;newnode-next pos;}
}
//删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead pos){SLTPopFront(pphead);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
// 单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{SLNode* newnode CreateNode(x);newnode-next pos-next;pos-next newnode;
}
// 单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos)
{assert(pos-next ! NULL);pos-next pos-next-next;free(pos-next);pos-next NULL;
}
//销毁
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur-next ! NULL){SLNode* next cur-next;free(cur);cur next;}*pphead NULL;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include SList.h
int main()
{SLNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushFront(plist, 5);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLNode* pos SLTFind(plist, 2);SLTInsert(plist, pos, 0);SLTPrint(plist);/*SLTErase(plist, pos);SLTPrint(plist);*/SLTInsertAfter(pos, 0);SLTPrint(plist);SLTEraseAfter(pos);SLTPrint(plist);SLTDestroy(plist);return 0;
}
