网站建设属于哪个税目,软件开发工具03173课后题,事件营销方案模板,wordpress移动端底部广告目录 前言
头文件
动态申请一个结点
单链表打印
单链表尾插
单链表的头插
单链表的尾删
单链表头删
单链表查找
单链表在pos位置之后插入x
单链表删除pos位置之后的值
在pos的前面插入
删除pos位置
销毁顺序表 前言
本文将介绍链表常见的功能的实现
头文件
#…目录 前言
头文件
动态申请一个结点
单链表打印
单链表尾插
单链表的头插
单链表的尾删
单链表头删
单链表查找
单链表在pos位置之后插入x
单链表删除pos位置之后的值
在pos的前面插入
删除pos位置
销毁顺序表 前言
本文将介绍链表常见的功能的实现
头文件
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDateType;
typedef struct SListNode
{SLTDateType val;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
// 分析思考为什么不在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置
void SListEraseAfter(SListNode* pos);
// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
//销毁顺序表
void SLTDestroy(SListNode** pphead);
动态申请一个结点
原理链表的结点所代表的是一个内存块里面包含着该节点的值以及指向下一个结点地址的指针用动态申请的方式更加方便插入时只需要将前一个结点里的指针指向自己即可但新结点刚创建时里面的指针指向空不要变为野指针。
SListNode* BuySListNode(SLTDateType x)
{SListNode* ans (SListNode*)malloc(sizeof(SListNode));if (ans NULL){perror(malloc fail);return NULL;}ans-val x;ans-next NULL;return ans;
} 单链表打印
原理遍历输出即可但链表的遍历不同于顺序表的遍历在于需要将遍历指针指向下一个结点顺序表是下标遍历遇到空为止。
void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur){printf(%d-, cur-val);cur cur-next;}printf(NULL);
} 单链表尾插
原理链表的唯一缺点是不能通过下标去寻找对应结点只能通过从头结点遍历到指定结点因为一个结点只能通过上一个结点的指针找到它们在内存里的存储位置不是连续的所以定义一个指针从头结点开始这里要考虑到两种情况
1.当头结点为空时意味着这是链表刚创建直接将头结点指向空即可
2.当头结点不为空时意味着这是一个好的链表需要遍历到该链表的末结点将末结点的指针指向新结点完成尾插。遍历终止的条件时当前指针的下一个指针指向空如果该指针指向空的话遍历到末尾时会进一次循环走到空此时会丢失之前结点的地址。
void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newnode BuySListNode(x);//用x创建新结点if ((*pplist) NULL){(*pplist) newnode;}else{SListNode* cur *pplist;while (cur-next){cur cur-next;}cur-next newnode;}
} 单链表的头插 原理当头结点为空时和尾插一样要讲的是不为空的情况
创建好新结点后将新结点的下一个指针指向头结点指向的结点然后头结点指向新结点。顺序不能对调会丢失头结点原本指向的结点地址。
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode BuySListNode(x);if (*pplist NULL){*pplist newnode;}else{newnode-next (*pplist);*pplist newnode;}
} 单链表的尾删
原理动态申请的内存如果需要删除的话是需要通过free函数进行释放的。
这里也要考虑两种情况因为单一的方法不适用于所有情况。
1.当链表有两个以上的结点时遍历到末尾结点的前驱结点然后释放掉下一个指针指向的结点再置为空即可如果遍历到删除结点的话你释放时就会丢失掉前一个结点的地址那个结点的指针就会变成野指针。
2.当链表为空或是只有一个结点时直接释放即可当然为什么头结点为空时也能进行释放不会构成对空指针的引用吗我们来看看Cplusplus上面的描述 最后一句如果指针为空该功能不做任何改变因为释放完后还是为空人为操作。
根据free的特性可以将空和单个结点的情况考虑进去。
void SListPopBack(SListNode** pplist)
{if ((*pplist) NULL || (*pplist)-next NULL){free(*pplist);*pplist NULL;}else{SListNode* cur *pplist;while (cur-next-next){cur cur-next;}free(cur-next);cur-next NULL;}
} 单链表头删
头删和尾删一样同样也要考虑一个结点和多个结点的情况
1.只有一个结点或为空时和尾删一样直接free掉即可。
2.当有多个结点时我们需要保留头结点的下一个指针在删除头结点后将头结点指向刚刚保留的指针即可。
void SListPopFront(SListNode** pplist)
{if ((*pplist NULL) || (*pplist)-next NULL){free(*pplist);*pplist NULL;}else{SListNode* next (*pplist)-next;free(*pplist);*pplist next;}
} 单链表查找
直接遍历定位即可返回该值的结点而不是该值。
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur plist;while (cur){if (cur-val x){return cur;}cur cur-next;}return NULL;} 单链表在pos位置之后插入x
定位到pos位置后将pos进行头插即可。
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);SListNode* next pos-next;pos-next newnode;newnode-next next;
} 单链表删除pos位置之后的值
和插入相反只是进行头删即可pos在头结点上情况也一样。
void SListEraseAfter(SListNode* pos)
{assert(pos);SListNode* next pos-next;if (next ! NULL){SListNode* nextnext next-next;free(next);pos-next nextnext;}
} 在pos的前面插入
首先这里得考虑pos的位置因为如果在头结点上的话就得单独考虑。
1.如果pos在头结点上的话直接头插
2.否则用一个前驱指针保留pos位置的前驱指针再做插入操作。
这里断言一下以防传来的pos和头结点为空
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{//不允许*pphead和pos一者为空要么都为空要么都不空assert(*pphead);assert(pos);assert(pphead);SListNode* newnode BuySListNode(x);if (pos *pphead){SListPushFront(pphead, x);}else{SListNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;} 删除pos位置
和上面一样如果pos位置是头结点的话就头删否则保留pos位置的前驱和后继指针free掉pos后两个指针链接。
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(pos);if (pos *pphead){SListPopFront(pphead);}else{SListNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SListNode* next pos-next;free(pos);prev-next next;pos NULL;}
} 销毁顺序表
从头结点开始一个个结点往下遍历释放最后头结点置空即可。
void SLTDestroy(SListNode** pphead)
{assert(pphead);SListNode* cur *pphead;while (cur){SListNode* next cur-next;free(cur);cur next;}*pphead NULL;}
