不懂!!
思想可能有问题!!
/*单链表插入排序*/
#include <stdio.h>
#include <malloc.h>
typedef struct node
{
int data;
struct node *next;
}*LinkList, ListNode;
void CreateList(LinkList *headPtr, LinkList *tailPtr);
void Insert_sort(LinkList *headPtr);/*插入排序*/
void VisitList(LinkList headPtr);
int main(void)
{
LinkList newhead = NULL, newtail = NULL;
CreateList(&newhead, &newtail);
VisitList(newhead);
Insert_sort(&newhead);
VisitList(newhead);
return 0;
}
void CreateList(LinkList *headPtr, LinkList *tailPtr)
{
int newdata;
LinkList newPtr = NULL;
printf("Enter one number:\n");
scanf("%d", &newdata);
while (newdata != 0)
{
newPtr = (LinkList)malloc(sizeof(ListNode));
if (newPtr == NULL)
{
exit(1);
}
newPtr -> data = newdata;
newPtr -> next = NULL;
if (*headPtr == NULL)
{
newPtr -> next = *headPtr;
*headPtr = newPtr;
}
else
{
(*tailPtr) -> next = newPtr;
}
newPtr -> next = NULL;
*tailPtr = newPtr;
printf("Enter one number:\n");
scanf("%d", &newdata);
}
}
void Insert_sort(LinkList *headPtr)
{
LinkList prev = NULL, cur = NULL, q = NULL, prev2 = NULL, cur2 = NULL;/*插入q*/
prev = *headPtr;
cur = prev -> next;
while (prev)
{
q = cur;/*将插入接点赋予q*/
cur = cur -> next;
prev -> next = q -> next;/*去除q*/
prev2 = *headPtr;/*对prev前的元素遍力一遍,找到q的位置并插入*/
while (prev2)
{
cur2 = prev2 -> next;
if (q -> data < (*headPtr) -> data)/* 小于头接点的情况*/
{
q -> next = *headPtr;
*headPtr = q;
}
else if (q -> data > prev2 -> data && q -> data < cur2 -> data)
{
q -> next = prev2 -> next;
prev2 -> next = q;
}
else if (q -> data > prev -> data)/*大于prev指向接点的情况*/
{
q -> next = prev -> next;
prev = q;
}
prev2 = prev2 -> next;
}
}
}
void VisitList(LinkList headPtr)
{
while (headPtr != NULL)
{
printf("%d ", headPtr -> data);
headPtr = headPtr -> next;
}
printf("\n");
}
[此贴子已经被作者于2006-5-30 20:51:59编辑过]