网站突然不被百度收录,wordpress软件最低要求,深圳代理记账多少钱一月,网站谁做的一.实现一个单链表#xff08;无头单向不循环#xff09;
我们首先实现一个无头单向不循环单链表。
写出基本的增删查改功能#xff0c;以及其它的一些功能#xff08;可忽略#xff09;。
#includestdio.h
#includeassert.h
#includestdlib.h…一.实现一个单链表无头单向不循环
我们首先实现一个无头单向不循环单链表。
写出基本的增删查改功能以及其它的一些功能可忽略。
#includestdio.h
#includeassert.h
#includestdlib.h
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;SLTNode* BuyListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){printf(malloc failed.\n);exit(-1);}newnode-data x;newnode-next NULL;
}void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}void SListPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuyListNode(x);if (*pphead NULL){*pphead newnode;}else{//找到尾结点SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuyListNode(x);newnode-next *pphead;*pphead newnode;
}void SListPopBack(SLTNode** pphead)
{assert(*pphead ! NULL);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* tail *pphead;SLTNode* prev NULL;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);tail NULL;prev-next NULL;}
}void SListPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}else{cur cur-next;}}return NULL;
}void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{SLTNode* newnode BuyListNode(x);if (*pphead pos){newnode-next *pphead;*pphead newnode;}else{SLTNode* posPrev *pphead;while (posPrev-next ! pos){posPrev posPrev-next;}posPrev-next newnode;newnode-next pos;}
}void SListErase(SLTNode** pphead, SLTNode* pos)
{if (*pphead pos){*pphead pos-next;free(pos);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
}void SListDestroy(SLTNode** pphead)
{assert(*pphead);SLTNode* cur *pphead;SLTNode* next (*pphead)-next;while (next){free(cur);cur next;next next-next;}free(cur);*pphead NULL;
}//通过一趟遍历确定长度为n的单链表中值最大的结点
SLTNode* SListFindMax(SLTNode* pphead)
{assert(pphead);SLTNode* cur pphead;SLTNode* maxnode pphead;SLTDataType max pphead-data;while (cur){if (cur-data max){max cur-data;maxnode cur;}cur cur-next;}return maxnode;
}二.原地逆转
接下来我们要写一个接口实现将链表中所有结点的链接方向“原地”逆转即要求仅利用原表的存储空间换句话说要求空间复杂度为O1 那么我们需要将链表遍历进行逆转改变链接方向 时要尤其注意避免行差踏错。
//将链表中所有结点的链接方向“原地”逆转即要求仅利用原表的存储空间换句话说要求空间复杂度为O1
void SListReverse(SLTNode** pphead)
{SLTNode* head *pphead; //此指针在每次循环中始终指向当前链表的头SLTNode* tmp head-next; //此指针在每次循环中始终指向要被后删头插的节点SLTNode* oldhead *pphead; //此指针在每次循环中始终指向原本的头结点不会改变指向while (tmp) //如果tmp为空则代表逆序结束旧头的next已经是空的了成为新链表的末尾{oldhead-next tmp-next; //将tmp架空实际是后删操作的一部分tmp-next head; //让tmp变成新的头实际是头插操作的一部分 head tmp; //换头tmp oldhead-next; //让tmp变成下次循环中待删除的节点}*pphead head;
}
或许仅仅一段代码不足以让你理解我们可以来看下面的图。
对照着代码每一次循环就是下面的一行。
最后一行即为逆转后的链表。 三.测试运行
最后我们来看一下上面代码的运行效果。
我们可以写一个测试函数。
void TestSList()
{SLTNode* plist NULL;SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushBack(plist, 3);SListPushBack(plist, 4);SListPushBack(plist, 5);SListPrint(plist);SListReverse(plist);SListPrint(plist);SListDestroy(plist);}int main()
{TestSList();return 0;
}
运行结果 这样我们就实现了链表的原地逆转。
