//四题,3小题,单链表选择排序
#include <stdio.h>
#include <malloc.h> /*包含动态内存分配函数的头文件*/
#define N 10
struct Node
{
Node()
{
_val = -1;
_next = NULL;
}
int _val;
struct Node* _next;
};
typedef Node* LinkNode;
LinkNode CreateLink(int n) /*建立单链表的函数，形参n为数量*/
{
LinkNode p,h,s; /* *h保存表头结点的指针，*p指向当前结点的前一个结点，*s指向当前结点*/
int i; /*计数器*/
if((h=(LinkNode)malloc(sizeof(Node)))==NULL) /*分配空间并检测*/
{
printf("不能分配内存空间!");
return NULL;
}
h->_val= -1; /*把表头结点的数据域置空*/
h->_next=NULL; /*把表头结点的链域置空*/
p=h; /*p指向表头结点*/
for(i=0;i<n;i++)
{
if((s= (LinkNode) malloc(sizeof(Node)))==NULL) /*分配新存储空间并检测*/
{
printf("不能分配内存空间!");
return NULL;
}
p->_next=s; /*把s的地址赋给p所指向的结点的链域，这样就把p和s所指向的结点连接起来了*/
printf("请输入第%d个数据:",i+1);
scanf("%d",s->_val); /*在当前结点s的数据域中存储输入数据*/
s->_next=NULL;
p=s;
}
return(h);
}
void ExchLinkNode(const LinkNode head,const LinkNode node1,const LinkNode node2)
{
//head不准被交换
LinkNode prenode1 = NULL; //保存待交换节点node1的前一个节点
LinkNode postnode1 = NULL; //保存待交换节点node1的后一个节点
LinkNode prenode2 = NULL; //保存待交换节点node2的前一个节点
LinkNode postnode2 = NULL; //保存待交换节点node2的后一个节点
LinkNode tmp = head;
//不得和头节点交换
if (node1 == head)
return;
else if (node2 == head)
return ;
//自己和自己就不必交换了
if (node1 == node2)
return ;
if (node1->_next == node2)
{
tmp = head;
while (tmp->_next != node1)
tmp = tmp->_next;
prenode1 = tmp;
postnode2 = node2->_next;
prenode1->_next = node2;
node2->_next = node1;
node1->_next = postnode2;
return ;
}
if (node2->_next == node1)
{
tmp = head;
while (tmp->_next != node1)
tmp = tmp->_next;
prenode2 = tmp;
postnode1 = node1->_next;
prenode2->_next = node1;
node1->_next = node2;
node2->_next = postnode1;
return ;
}
tmp = head;
while (tmp->_next != node1)
tmp = tmp->_next;
prenode1 = tmp;
tmp = head;
while (tmp->_next != node2)
tmp = tmp->_next;
prenode2 = tmp;
postnode1 = node1->_next;
postnode2 = node2->_next;
//交换节点
prenode1->_next = node2;
node2->_next = postnode1;
prenode2->_next = node1;
node1->_next = postnode2;
}
void SelectLinkListSort(const LinkNode head)
{
//头节点不参与排序
LinkNode tmp = head->_next;
for (;tmp->_next != NULL; tmp = tmp->_next)
{
LinkNode min = tmp;
for (LinkNode node = tmp->_next; node != NULL; node = node->_next)
{
if (node->_val < min->_val)
min = node;
}
ExchLinkNode(head,tmp,min);
tmp = min; //遍历的是链表中的相对位置，但是绝对位置的信息已经在ExchLinkNode被修改了
}
}
int main(int argc,char* argv[])
{
LinkNode head = CreateLink(10);
SelectLinkListSort(head);
return 0;
}
- 1
- 2
前往页