静态链表快排序问题~~求助!!急!!!
以下是我做的静态链表创建和快排序.
但排序之后显示不出来!应该是排序的地方有问题~
请帮忙挑挑错误!!!!多谢了!!
#include<stdio.h>
#include<stdlib.h>
#define SIZEMAX 10
#define OK 0
#define ERR 1
typedef struct node
{
int nData;
}NODE;
typedef struct List
{
NODE p[SIZEMAX+1];
int Length;
}SqList;
SqList *Creat(SqList *pHead)
{
int i;
SqList *pTmp;
pHead = (SqList *)malloc(sizeof(SqList));
pTmp = pHead;
printf("Data:\n");
for(i = 1; i< SIZEMAX+1; i++)
{
scanf("%d", pTmp->p+i);
}
return (pHead);
}//creat
void print(SqList *pHead)
{
int i;
for(i = 1; i< SIZEMAX+1; i++)
{
printf("%-3d", pHead->p[i].nData);
}
printf("\n");
}//print
int Partition(SqList *pHead, int low, int high)
{
int nKeyWord;
pHead->p[0] = pHead->p[low];
nKeyWord = pHead->p[low].nData;
while(low < high)
{
while(low < high && pHead->p[high].nData >= nKeyWord)
{
--high;
}
pHead->p[low] = pHead->p[high];
while(low < high && pHead->p[low].nData <= nKeyWord)
{
++low;
}
pHead->p[high] = pHead->p[low];
}
pHead->p[low] = pHead->p[0];
return (low);
}//Partition
void QSort(SqList *pHead, int low, int high)
{
int nMidLoc;
if(low < high)
{
nMidLoc = Partition(pHead, low, high);
QSort(pHead, low, nMidLoc-1);
QSort(pHead, nMidLoc+1, high);
}
}//QSort
SqList *QuickSort(SqList *pHead)
{
QSort(pHead, 1, pHead->Length);
return (pHead);
}//QuickSort
int main()
{
SqList *Creat(SqList *pHead);
void print(SqList *pHead);
int Partition(SqList *pHead, int low, int high);
void QSort(SqList *pHead, int low, int high);
SqList *QuickSort(SqList *pHead);
SqList L1;
SqList *Q;
SqList *pHead;
Q = &L1;
L1.Length = 10;
pHead = Creat(Q);
print(pHead);
printf("Sort.\n");
pHead = QuickSort(Q);
print(pHead);
return OK;
}
[解决办法]
#include <stdio.h > #include <stdlib.h > #define SIZEMAX 10 #define OK 0 #define ERR 1 typedef struct node { int nData; }NODE; typedef struct List { NODE p[SIZEMAX+1]; int Length; }SqList; SqList *Creat(SqList **pHead) // 这里改成了2个星号，否则不能返回申请的空间{ int i; SqList *pTmp; *pHead = (SqList *)malloc(sizeof(SqList)); pTmp = *pHead; printf("Data:\n"); for(i = 1; i < SIZEMAX+1; i++) { scanf("%d", pTmp->p+i); } return (*pHead); }//creat void print(SqList *pHead) { int i; for(i = 1; i < SIZEMAX+1; i++) { printf("%-3d", pHead->p[i].nData); } printf("\n"); }//print int Partition(SqList *pHead, int low, int high) { int nKeyWord; pHead->p[0] = pHead->p[low]; nKeyWord = pHead->p[low].nData; while(low < high) { while(low < high && pHead->p[high].nData >= nKeyWord) { --high; } pHead->p[low] = pHead->p[high]; while(low < high && pHead->p[low].nData <= nKeyWord) { ++low; } pHead->p[high] = pHead->p[low]; } pHead->p[low] = pHead->p[0]; return (low); }//Partition void QSort(SqList *pHead, int low, int high) { int nMidLoc; if(low < high) { nMidLoc = Partition(pHead, low, high); QSort(pHead, low, nMidLoc-1); QSort(pHead, nMidLoc+1, high); } }//QSort SqList *QuickSort(SqList *pHead) { QSort(pHead, 1, pHead->Length); return (pHead); }//QuickSort int main() { SqList *Creat(SqList **pHead); // 这里改成了2个星号，否则不能返回申请的空间 void print(SqList *pHead); int Partition(SqList *pHead, int low, int high); void QSort(SqList *pHead, int low, int high); SqList *QuickSort(SqList *pHead); SqList L1; SqList *Q; SqList *pHead; Q = &L1; L1.Length = 10; pHead = Creat(&Q); // 这里改成了2个星号，否则不能返回申请的空间 print(pHead); printf("Sort.\n"); pHead = QuickSort(Q); print(pHead); return OK; }
[解决办法]
我是说这样才能返回创建的空间，你排序算法有问题
另: 链表快排序不要采用取枢轴的方式，要考虑链表随机访问速度那个慢啊
参考一下以下代码，说不定有点启发
//1 楼goodluckyxl（被人遗忘的狗）回复于 2003-06-28 15:10:49 得分 100免费赠送： // 快速排序，变量有为定义： void select(list L) { *q=&L; //q指向l的地址 while (q->next!=null) //头接点不为零 让pl，最小接点指针minp指向头接点 { i++； pl=q->next; minp=pl; while(pl->next!=null) // pl下个指针指向不为空 { if(pl->next->data<minp->data) //比较接点内容大小 { front=pl; //front设置为最小接点的前指针为方便拿出 minp=pl->next; //最小接点 } pl=pl->next; //依次按地址增加 } if(i==1) // 如果第一次比较，i为比较次数。让最小接点放到头接点之前 { r1=front->next; front->next=r1->next; r1->next=q; q=r1; //头接点为最小的 } else if(minp!=q->next) // 不是第一次比较，如果最小接点不为头接点 { //将他放到头接点和头接点前个接点之间 //因为每做一次q=q->next； r1=front->next; pl->next=r1->next; r1->next=q->next; q->next=r1; } q=q->next; //循环 } }
[解决办法]
还有这个
struct LIST; { int i; LIST* next; }NODE; LIST qsortL (LIST h, LIST lnext) { NODE n1, n2; LIST p, t1 = &n1, t2 = &n2; if (h == NULL) return lnext; for (p = h->next; p != NULL; p = p->next) if (p->i < h->i) { t1->next = p; t1 = p; } else { t2->next = p; t2 = p; } t1->next = t2->next = NULL; h->next = qsortL(n2.next, lnext); return qsortL(n1.next, h); }