void SelectSort(pLinkList list) //选择排序
{
assert(list);
if (NULL == list->pHead || NULL ==list->pHead->next) //如果是空链表或者只有一个结点则直接结束
{
return;
}
pLinkNode cur = list->pHead;
pLinkNode p = NULL;
pLinkNode min = NULL;
while (cur!=NULL)
{
p = cur->next ; //p指向无序区第二个元素
min = cur; //min指向无序区第一个元素
while (p != NULL)
{
if (min->data > p->data)
{
min = p; //min记录最小的data的地址
}
p = p->next;
}
if (min != cur) //将min所指向的data与无序区第一个元素进行交换
{
DataType tmp = cur->data;
cur->data = min->data;
min->data = tmp;
}
cur = cur->next; //有序区加一，无序区减一
}
}
二、寻找中间结点 快慢指针是解决大多数链表问题的一个重要方法，在本题中就应用到了快慢指针，快指针fast每次走两步，慢指针slow每次走一步，等到fast走到链表尾部时，slow刚好指向中间结点。
pLinkNode FindMindNode(pLinkList list) //查找中间节点
{
assert(list);
pLinkNode fast= list->pHead; //快指针，每次走两步
pLinkNode slow = list->pHead; //慢指针，每次走一步
while (NULL!=fast)
{
if (NULL != fast->next) //如果fast不是尾结点
{
fast = fast->next->next;
slow = slow->next;
}
else
{
break;
}
}
return slow;
}三、删除一个非尾的结点
void EraseNotTail(pLinkNode pos) //删除非尾结点
{
assert(pos->next);
pLinkNode cur = pos->next;
pos->data = cur->data;
pos->next = cur->next;
free(cur);
cur = NULL;
}四、删除倒数第k个结点，k大于1，小于链表长度（O（n）） 这个题跟快慢指针很像，我们可以先让一个指针走k步，然后再让一个指针从起点出发,等到先走的指针到达链表尾部时，第二个指针刚好指向倒数第k个结点。
void DelKnode(pLinkList list,int k) //删除倒数第k个结点，k要大于1，小于链表长度
{
assert(list);
if (NULL == list->pHead || NULL == list->pHead->next||k<=1)
{
return;
}
pLinkNode cur = list->pHead;
pLinkNode del= list->pHead; //del指向要删除的结点
while (cur->next!=NULL)
{
k--; //cur先走k步，del再开始走
if (k <=0)
{
del = del->next;
}
cur = cur->next;
}
if (k <=0)
{
del->data = del->next->data; //del的下一个结点的data保存到del里面
cur = del->next; //记住del下一个结点的地址
del->next = cur->next; //del指向del的下下一个结点
free(cur);
cur = NULL;
}
}
五、反转链表
void Reverselist(pLinkList list) //反转链表
{
assert(list);
if (NULL == list->pHead || NULL == list->pHead->next)
{
return;
}
pLinkNode newHead = NULL; //指向新链表的头
pLinkNode tmp = NULL;
pLinkNode cur = list->pHead;
while (cur != NULL)
{
tmp = cur->next; //tmp保存cur的下一个结点
cur->next = newHead; //指向新链表的头
newHead = cur; //链表的头指针移动
cur = tmp; //cur指向下一个结点
}
list->pHead = newHead;
}
六、在指定位置结点的前面插入一个结点 这个问题与删除一个非尾结点是一模一样的解决方法！！！
void InsertFrontNode(pLinkNode pos, DataType x) //在当前结点前插入一个结点
{
assert(pos);
pLinkNode newNode=NULL;
newNode = (pLinkNode)malloc(sizeof(LinkNode)); //创建一个新结点
if (NULL ==newNode)
{
printf("out of memory\n");
exit(EXIT_FAILURE);
}
newNode->next = pos->next; //将这个新节点插入到pos后面
pos->next = newNode;
newNode->data = pos->data; //将pos指向的data保存到newHead里面
pos->data = x; //将x保存在pos里面
} - 顶
- 1
- 踩
- 0