网站建设实训总结范文,phpnow 搭建网站,个人网页模板王,海外网络是什么意思目录 单向链表的概念及结构 尾插
头插
尾删
编辑 头删 查找 在pos位置前插 在pos位置后插 删除pos位置 删除pos的后一个位置
总结
代码 单向链表的概念及结构 概念#xff1a;链表是一种 物理存储结构上非连续 、非顺序的存储结构#xff0c;数据元素的 逻辑顺序 是…目录 单向链表的概念及结构 尾插
头插
尾删
编辑 头删 查找 在pos位置前插 在pos位置后插 删除pos位置 删除pos的后一个位置
总结
代码 单向链表的概念及结构 概念链表是一种 物理存储结构上非连续 、非顺序的存储结构数据元素的 逻辑顺序 是通过链表中的指针链接 次序实现的。 单向链表的结构
注意:
从上图可看出链式结构在逻辑上是连续的但是在物理上不一定连续。现实中的结点一般都是从堆上申请出来的。从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续。 无头单向非循环链表:结构简单, 一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 尾插
尾插分为两种情况
一开始没有链表当开始没有链表直接将newnode赋给*pphead通过二级指针改变plist。一开始有链表当开始有链表创建一个结构体指针tail来找到最后一个节点再将newnode赋给最后一个节点的next。 头插
头插分为两种情况开始有链表和开始没有链表但是两种情况不需要分类考虑先将*pphead即plist赋给newnode-next再将newnode连上*pphead。 尾删 尾删分两种情况考虑
只有一个节点给*pphead赋空值一个以上节点确定尾节点tail后通过tail的前一个节点tailprev进行tailprev-nextNULL赋空值或者直接通过tail-next-next找倒数第二个节点再给tail-next赋空值。 头删 头删不需要分情况直接将第一个节点的next即第二个节点的地址通过newnode的中转赋给*pphead。 查找
创建一个结构体指针cur链表中遍历查找cur-datax的节点找到后返回cur方便后面的修改功能。 不需要修改所以传入函数的是一级指针 在pos位置前插 分两种情况考虑
当pos为第一个节点相当于头插调用头插函数即可。当pos不为第一个节点通过pos的前一个节点prev将newnode插入pos前面。 在pos位置后插
在pos位置后插先将pos-next赋给newnode-next把newnode和d3连上再将newnode赋给pos-next,连上d2。
注意在两个语句不能换位置不然成环循环打印 删除pos位置 分两种情况
pos在第一个节点位置直接调用头删函数即可。pos不在第一个节点位置通过pos的前一个节点prev将pos-next赋给prev-next达到将pos节点删除的效果。 删除pos的后一个位置
删除pos的后一个位置需要先检测pos-next是否为空值为空值就直接返回若pos-next不为空赋给posNext再将posNext-next赋给pos-next达到删除posNext节点后面可以free(posNext)释放posNext节点再posNextNULL给它赋空值。 无头删除pos位置 不给头节点的情况下可以先通过pos-dataposNext-data的方式交换内容再删除pos的下一节点posNext将pos替换为posNext达到和删除pos一样的效果。
但是这种方法的缺点是当pos本身为尾节点时不能通过下一节点posNext来使用替换法。 代码 总结 在上面众多单向链表的实现中很多并不实用当需要大量的头插头删时使用单向链表会更高效。 代码 SList.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestring.htypedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//typedef struct SListNode SLTNode;//打印
void SLTPrint(SLTNode* phead);SLTNode* BuySListNode(SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头插
void SLTPushBack(SLTNode** pphead, SLTDataType);//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在pos位置前插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos位置后插
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h//打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;//while (cur ! NULL)while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;}尾插 phead是plist的形参 //开始就有链表
//void SLTPushBack(SLTNode* phead, SLTDataType x)
//{
// SLTNode* newnode BuySListNode(x);
// SLTNode* tail phead;
// while (tail-next ! NULL)
// {
// tail tail-next;
// }
// tail-next newnode;
//}//尾插 //包括一开始没有链表
void SLTPushBack(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;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{//1.空assert(*pphead);//2、一个节点//3、一个以上节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//方法1.SLTNode* tailPrev NULL;SLTNode* tail *pphead;while (tail-next){tailPrev tail;tail tail-next;}free(tail);tailPrev-next NULL;方法2.//SLTNode* tail *pphead;//while (tail-next-next)//{// tail tail-next;//}//free(tail-next);//tail-next NULL;}}//头删
void SLTPopFront(SLTNode** pphead)
{//空assert(*pphead);//非空SLTNode* newhead (*pphead)-next;free(*pphead);*pphead newhead;
}//查找是否有x这个数,找到返回指向该数的指针
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}//在pos位置前插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySListNode(x);prev-next newnode;newnode-next pos;}
}//在pos位置后插
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySListNode(x);//下面两句不能交换位置否则会成环newnode-next pos-next;pos-next newnode;
}//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (*pphead pos){SLTPopFront(pphead);}//else if (pos-next NULL)//{// SLTPopBack(pphead);//}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;} //free(prev-next);//不要free不然这个节点后面全没了prev-next pos-next; }
}//删除pos后一个位置
void SLTEraseAfter(SLTNode* pos)
{//assert(pos);//检测pos是否是尾节点//assert(pos-next);//暴力检测if (pos-next NULL)//温和检测{return NULL;}SLTNode* posNext pos-next;pos-next posNext-next;free(posNext);posNext NULL;} Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.hvoid TestSList1()
{int n;printf(请输入链表的长度);scanf(%d, n);printf(\n请依次输入每个节点的值);SLTNode* plist NULL;for (size_t i 0; i n; i){int val;scanf(%d, val);SLTNode* newnode BuySListNode(val);//头插newnode-next plist;plist newnode;}SLTPrint(plist);SLTPushBack(plist, 1000);SLTPrint(plist);}void TestSList2()
{SLTNode* plist NULL;//尾插SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);//头插SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);
}void TestSList3()
{SLTNode* plist NULL;//尾插SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);头插//SLTPushFront(plist, 10);//SLTPushFront(plist, 20);//SLTPushFront(plist, 30);//SLTPushFront(plist, 40);//SLTPrint(plist);//尾删SLTPopBack(plist);//SLTPopBack(plist);//SLTPopBack(plist);//SLTPopBack(plist);//SLTPopBack(plist);SLTPrint(plist);}void TestSList4()
{SLTNode* plist NULL;//尾插SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);//头插SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);//头删SLTPopFront(plist);SLTPrint(plist);
}void TestSList5()
{SLTNode* plist NULL;//尾插SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);//头插SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);//查找SLTNode* pos SLTFind(plist, 40);if (pos){pos-data * 10;}SLTPrint(plist);
}void TestSList6()
{SLTNode* plist NULL;//尾插SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);//头插SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);//在pos位置前插int x;scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTInsert(plist, pos, x * 10);}SLTPrint(plist);
}void TestSList7()
{SLTNode* plist NULL;//尾插SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);//头插SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);//在pos位置后插int x;scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTInsertAfter(pos, x * 10);}SLTPrint(plist);
}void TestSList8()
{SLTNode* plist NULL;//尾插SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);//头插SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);//删除pos位置int x;scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTErase(plist, pos);pos NULL;}SLTPrint(plist);
}void TestSList9()
{SLTNode* plist NULL;//尾插SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);//头插SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);//删除pos后一个位置int x;scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTEraseAfter(pos);pos NULL;}SLTPrint(plist);
}void PrintSList(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}int main()
{//TestSList1();// 头插 尾插//TestSList2();// 尾删//TestSList3();// 头删//TestSList4();// 查找//TestSList5();// pos位置前插//TestSList7();// pos位置后插//TestSList8();// 删除pos位置TestSList9();//删除pos的后一个位置//TestSList10();return 0;
}
