//
/// <summary>
/// 插入节点,按大小排序
/// </summary>
/// <param name="head">[out] struct LStuInfo *head:链表的头指针。</param>
/// <param name="node">[in] struct LStuInfo *node:将要插入的节点。</param>
/// <returns>返回的是插入后的链表头指针</returns>
struct LStuInfo *Insert(struct LStuInfo *head,struct LStuInfo *node)//head是指向第一个节点的指针
{
struct LStuInfo *p1;
struct LStuInfo *p2;
if(head == NULL)
{
//在还没有创建节点的情况下
head = node;
node ->next = NULL;
node ->prior = NULL;
position += 1;
return head;
}
p1 = head;
while(p1->nId < node ->nId && p1 ->next !=NULL)
{
p2 = p1;
p1 = p1 ->next;
}
if(node ->nId < head->nId)//比第一个节点小
{
node ->prior = NULL;
//head ->prior->next = node;
node ->next = head;
head->prior = node;
position += 1;
return head;
}
else if(p1 ->next == NULL && node ->nId > p1 ->nId)//插入节点在最后
{
p1 ->next = node;
node ->prior = p1;
node ->next =NULL;
position += 1;
return head;
}
//插入节点在中段
node ->prior = p1 ->prior;
p1 ->prior->next = node;
node ->next = p1;
p1->prior = node;
position += 1;
return head;
}
/// <summary>
/// 移除nId为Id的节点
/// </summary>
/// <param name="head">[out] struct LStuInfo *head:链表的头指针。</param>
/// <param name="Id">[in] long Id:要移除节点的nId</param>
/// <returns>返回的移除某个节点后的链表头指针</returns>
struct LStuInfo *Remove(struct LStuInfo *head,long Id)
{
struct LStuInfo *p1;//p1寻找Id相同的节点
struct LStuInfo *p2;//在p1后一位的节点,方便操作
if(head == NULL)
{
printf("there are no node to delete!");
return head;
}
p1 = head;
while(p1->nId != Id && p1 ->next !=NULL)
{
p2 = p1;
p1 = p1 ->next;
}
if(Id == p1 ->nId)
{
if(p1 == head)//p1是第一个节点
{
head = p1 ->next;
p1 ->next ->prior = NULL;
}
else
{
if(p1 ->next == NULL)//p1是最后一个节点
{
p2 ->next ->prior =NULL;
p2 ->next = NULL;
}
p1 ->prior ->next = p1 ->next;//p1是中间某个节点
p1 ->next ->prior = p1 ->prior;
}
free(p1);
p1 = NULL;
position -= 1;
}
else
{
printf("not found!");
}
return head;
}
/// <summary>
/// 查找并更改相应节点里的值
/// </summary>
/// <param name="head">[out] struct LStuInfo *head:链表的头指针。</param>
/// <param name="Id">[in] long Id:要查找节点对应的nId号。</param>
/// <param name="Grade">[in] int Grade:查找节点对应的Grade。</param>
/// <returns>返回的节点值更改后的链表表头</returns>
void Search_Update(struct LStuInfo *head,long Id,int Grade)
{
struct LStuInfo *p1;
for(p1 = head ;p1 ->nId != Id;p1 = p1->next);
p1 ->nGrade = Grade;
}
//
/// <summary>
/// 打印链表
/// </summary>
/// <param name="head">[out] struct LStuInfo *head:链表的头指针。</param>
/// <returns>依次答应出链表中的节点</returns>
void Print(struct LStuInfo *head)
{
struct LStuInfo *p;
printf("There are %d records are:/n",position);
p = head;
if(head != NULL)
{
printf("head is %o/n",head);
printf("PriorAddress Address ID Name Grade NextAddress/n");
do
{
printf("%6X %X %ld %s %d %X/n",p->prior,p,p->nId,p->sName,p->nGrade,p->next);
p = p ->next;
}
while(p != NULL);
}
}
/// <summary>
/// 选择排序
/// </summary>
/// <param name="out">[out] struct LStuInfo *head:链表的头指针。</param>
/// <returns>返回的是按Id号从大到小的排序</returns>
struct LStuInfo *SelectSort(struct LStuInfo *head)
{
struct LStuInfo *first;//排序后有序链表的表头指针
struct LStuInfo *tail;//排列后有序链表的表尾指针
struct LStuInfo *p_min;//保留键值更小的节点的前驱节点的指针
struct LStuInfo *min;//存储最小节点
struct LStuInfo *p;//当前比较的节点
first = NULL;
while(head != NULL)//在链表中找键值最小的节点
{
for(p = head,min = head; p ->next != NULL;p = p->next)//循环遍历链表中的节点,找出此时最小的节点
{
if(p ->next ->nId > min ->nId)
{
p_min = p;//保存找到节点的前驱节点
min = p->next;//保存键值最小的节点
}
}
if(first == NULL)//目前还是空链
{
first = min;//第一次找到最小的节点
tail = min;//尾指针让它指向最后一个节点
}
else
{
tail ->next = min;//把刚找到的最小节点放到最后,即让尾指针指向它
tail = min;//尾指针也要指向它
}
if(min == head) //如果找到的最小节点就是第一个节点
{
head = head ->next;//让head指向原head->next,即第二个节点
}
else
{
p_min ->next = min ->next;//前次最小节点的next指向当前min的next,就让min离开原链表
}
}
if(first!= NULL) //循环结束得到有序链表first
{
tail ->next = NULL;//单链表的最后一个节点的next应该指向NULL
}
head = first;
return head;
}