| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1266 人关注过本帖
标题:插入排序法的困惑!
只看楼主 加入收藏
论坛
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1372
专家分:0
注 册:2006-3-27
收藏
 问题点数:0 回复次数:12 
插入排序法的困惑!

下面是对链表进行插入排序,怎么可能不行呢?估计是排序函数有问题,其他函数应该没事,都看看那不行

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char data;
struct node *priorPtr;
struct node *nextPtr;
}*LinkList, Lnode; /* 单链表结构 */

static void CreateList(LinkList *headPtr, LinkList *tailPtr, char ch);
static void InsertSort(LinkList *headPtr);
static void Traverse(LinkList headPtr);
static void DestroyList(LinkList *headPtr, LinkList *tailPtr);

int main(void)
{
LinkList headPtr = NULL, tailPtr = NULL;
char ch;

printf("Enter ch('@' quit): ");
scanf(" %c", &ch);
while (ch != '@')
{
CreateList(&headPtr, &tailPtr, ch); /* 创建链表 */
printf("continue enter: ");
scanf(" %c", &ch);
}

Traverse(headPtr); /* 打印排序前顺序 */

if (headPtr != NULL) /* 链表不空的情况下对链表进行插入排序 */
{
InsertSort(&headPtr);
}
else
{
printf("The list is empty.\n");
}

Traverse(headPtr); /* 打印排序后的顺序 */

if (headPtr != NULL) /* 释放所分配的内存空间 */
{
DestroyList(&headPtr, &tailPtr);
}
else
{
printf("The list is empty.\n");
}

return 0;
}

static void CreateList(LinkList *headPtr, LinkList *tailPtr, char ch)
{
LinkList newPtr;

if ((newPtr = (LinkList)malloc(sizeof(Lnode))) == NULL)
{
exit(1);
}

newPtr -> data = ch;
newPtr -> priorPtr = NULL;
newPtr -> nextPtr = NULL;

if (*headPtr == NULL) /* 空表情况下 */
{
newPtr -> priorPtr = *headPtr;
newPtr -> nextPtr = *headPtr;
*headPtr = newPtr;
}
else /* 非空情况下 */
{
(*tailPtr) -> nextPtr = newPtr;
newPtr -> priorPtr = *tailPtr;
newPtr -> nextPtr = NULL;
}
*tailPtr = newPtr;
}

static void InsertSort(LinkList *headPtr) /* 插入排序 */
{
LinkList pA,pB;
char temp;

/* 按数组的形式进行插入排序,下面有问题,看不出来啊 */
for (pA = *headPtr; pA -> nextPtr != NULL; pA = pA -> nextPtr)
{
if (pA -> data > pA -> nextPtr -> data) /* 当前结点数据大于下一结点数据 */
{
temp = pA -> nextPtr -> data;
for (pB = pA; pB != NULL; pB = pB -> priorPtr)
{
if (pB -> data > temp)
{
pB -> nextPtr -> data = pB -> data;
}
else
{
break;
}
}
pB -> nextPtr -> data = temp;
}
}
}

static void Traverse(LinkList headPtr) /* 打印函数 */
{
while (headPtr != NULL)
{
printf("%c -> ", headPtr -> data);
headPtr = headPtr -> nextPtr;
}
printf("NULL\n");
}

static void DestroyList(LinkList *headPtr, LinkList *tailPtr)
{
LinkList tempPtr;

while (*headPtr != NULL) /*释放内存空间 */
{
tempPtr = *headPtr;
*headPtr = (*headPtr) -> nextPtr;
free(tempPtr);
}
*headPtr = NULL;
*tailPtr = NULL;
}




搜索更多相关主题的帖子: 困惑 
2006-05-14 22:34
论坛
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1372
专家分:0
注 册:2006-3-27
收藏
得分:0 
原以为挺简单的问题,按照数组转换一下就可以了,不做不知道,一做下一跳,判断指空这么难,哎,我倒啊

日出东方,唯我不败! 做任何东西都是耐得住寂寞,任何一个行业要有十年以上的积累才能成为专家
2006-05-14 23:31
论坛
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1372
专家分:0
注 册:2006-3-27
收藏
得分:0 
啊,苍天啊,大地啊,终于搞定了,未来不是梦,哈哈哈哈

日出东方,唯我不败! 做任何东西都是耐得住寂寞,任何一个行业要有十年以上的积累才能成为专家
2006-05-14 23:51
论坛
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1372
专家分:0
注 册:2006-3-27
收藏
得分:0 

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char data;
struct node *priorPtr;
struct node *nextPtr;
}*LinkList, Lnode; /* 单链表结构 */

static void CreateList(LinkList *headPtr, LinkList *tailPtr, char ch);
static void InsertSort(LinkList *headPtr);
static void Traverse(LinkList headPtr);
static void DestroyList(LinkList *headPtr, LinkList *tailPtr);

int main(void)
{
LinkList headPtr = NULL, tailPtr = NULL;
char ch;

printf("Enter ch('@' quit): ");
scanf(" %c", &ch);
while (ch != '@')
{
CreateList(&headPtr, &tailPtr, ch); /* 创建链表 */
printf("continue enter: ");
scanf(" %c", &ch);
}

Traverse(headPtr); /* 打印排序前顺序 */

if (headPtr != NULL) /* 链表不空的情况下对链表进行插入排序 */
{
InsertSort(&headPtr);
}
else
{
printf("The list is empty.\n");
}

Traverse(headPtr); /* 打印排序后的顺序 */

if (headPtr != NULL) /* 释放所分配的内存空间 */
{
DestroyList(&headPtr, &tailPtr);
}
else
{
printf("The list is empty.\n");
}

return 0;
}

static void CreateList(LinkList *headPtr, LinkList *tailPtr, char ch)
{
LinkList newPtr;

if ((newPtr = (LinkList)malloc(sizeof(Lnode))) == NULL)
{
exit(1);
}

newPtr -> data = ch;
newPtr -> priorPtr = NULL;
newPtr -> nextPtr = NULL;

if (*headPtr == NULL) /* 空表情况下 */
{
newPtr -> priorPtr = *headPtr;
newPtr -> nextPtr = *headPtr;
*headPtr = newPtr;
}
else /* 非空情况下 */
{
(*tailPtr) -> nextPtr = newPtr;
newPtr -> priorPtr = *tailPtr;
newPtr -> nextPtr = NULL;
}
*tailPtr = newPtr;
}

static void InsertSort(LinkList *headPtr) /* 插入排序 */
{
LinkList pA, pB;
char temp;

/* 按数组的形式进行插入排序 */
for (pA = *headPtr; pA -> nextPtr != NULL; pA = pA -> nextPtr)
{
if (pA -> data > pA -> nextPtr -> data) /* 当前结点数据大于下一结点数据 */
{
temp = pA -> nextPtr -> data;
for (pB = pA; pB != *headPtr; pB = pB -> priorPtr)
{
if (pB -> data > temp)
{
pB -> nextPtr -> data = pB -> data;
}
else
{
break;
}
}
if (pB == *headPtr && pB -> data > temp) /* 当第一结点大于第二结点情况*/
{
pB -> nextPtr -> data = pB -> data;
pB -> data = temp;
}
else
{
pB -> nextPtr -> data = temp;
}
}
}
}

static void Traverse(LinkList headPtr) /* 打印函数 */
{
while (headPtr != NULL)
{
printf("%c -> ", headPtr -> data);
headPtr = headPtr -> nextPtr;
}
printf("NULL\n");
}

static void DestroyList(LinkList *headPtr, LinkList *tailPtr)
{
LinkList tempPtr;

while (*headPtr != NULL) /*释放内存空间 */
{
tempPtr = *headPtr;
*headPtr = (*headPtr) -> nextPtr;
free(tempPtr);
}
*headPtr = NULL;
*tailPtr = NULL;
}





日出东方,唯我不败! 做任何东西都是耐得住寂寞,任何一个行业要有十年以上的积累才能成为专家
2006-05-14 23:54
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

我改了下。。。
[CODE]
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char data;
struct node *priorPtr;
struct node *nextPtr;
}*LinkList, Lnode; /* 单链表结构 */

static void CreateList(LinkList *headPtr, LinkList *tailPtr, char ch);
static void InsertSort(LinkList *headPtr);
static void Traverse(LinkList headPtr);
static void DestroyList(LinkList *headPtr);

int main(void)
{
LinkList headPtr = NULL, tailPtr = NULL;
char ch;

printf("Enter ch('@' quit): ");
scanf(" %c", &ch);
while (ch != '@')
{
CreateList(&headPtr, &tailPtr, ch); /* 创建链表 */
printf("continue enter: ");
scanf(" %c", &ch);
}

Traverse(headPtr); /* 打印排序前顺序 */

if (headPtr != NULL) /* 链表不空的情况下对链表进行插入排序 */
{
InsertSort(&headPtr);
}
else
{
printf("The list is empty.\n");
}

Traverse(headPtr); /* 打印排序后的顺序 */

if (headPtr != NULL) /* 释放所分配的内存空间 */
{
DestroyList(&headPtr);
}
else
{
printf("The list is empty.\n");
}

return 0;
}

static void CreateList(LinkList *headPtr, LinkList *tailPtr, char ch)
{
LinkList newPtr;

if ((newPtr = (LinkList)malloc(sizeof(Lnode))) == NULL)
{
exit(-1);
}

newPtr -> data = ch;
newPtr -> priorPtr = NULL;
newPtr -> nextPtr = NULL;

if (*headPtr == NULL) /* 空表情况下 */
{
newPtr -> priorPtr = *headPtr;
newPtr -> nextPtr = *headPtr;
*headPtr = newPtr;
}
else /* 非空情况下 */
{
(*tailPtr) -> nextPtr = newPtr;
newPtr -> priorPtr = *tailPtr;
newPtr -> nextPtr = NULL;
}
*tailPtr = newPtr;
}

static void InsertSort(LinkList *headPtr) /* 插入排序 */
{
LinkList pA,pB;
char temp;


for (pA = (*headPtr)->nextPtr ; pA != NULL; pA = pA -> nextPtr)
{
if (pA->data < pA->priorPtr->data)
{
temp = pA->data;
for (pB = pA; pB->priorPtr != NULL; pB = pB->priorPtr)
if (pB->priorPtr->data > temp)
pB->data = pB->priorPtr->data;
else
break;

pB -> data = temp;
}
}
}

static void Traverse(LinkList headPtr) /* 打印函数 */
{
while (headPtr != NULL)
{
printf("%c -> ", headPtr -> data);
headPtr = headPtr -> nextPtr;
}
printf("NULL\n");
}

static void DestroyList(LinkList *headPtr) /*你那样没必要*/
{
LinkList tempPtr;

while (*headPtr != NULL) /*释放内存空间 */
{
tempPtr = *headPtr;
*headPtr = (*headPtr) -> nextPtr;
free(tempPtr);
}

}


[/CODE]


叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-14 23:54
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

显然你是思维混乱,前后两种混在一起
当然第二个for里可以把那个条件直接写在for条件里很清楚


叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-14 23:56
论坛
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1372
专家分:0
注 册:2006-3-27
收藏
得分:0 
for (pB = pA; pB->priorPtr != NULL; pB = pB->priorPtr)
if (pB->priorPtr->data > temp)
pB->data = pB->priorPtr->data;



仁兄,你这里是错误的,pB -> priorPtr不可能成为NULL

日出东方,唯我不败! 做任何东西都是耐得住寂寞,任何一个行业要有十年以上的积累才能成为专家
2006-05-14 23:59
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

错不错运行再说,你的程序开始你按数组写完也认为是对的吧


叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-15 00:01
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

双向表头指针的前驱指针为NULL(当然有人不这么设置),这还有问题啊?


叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-15 00:02
论坛
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1372
专家分:0
注 册:2006-3-27
收藏
得分:0 

哎,你是从第2个结点开始向后走,我是从第1个结点直接比较,我说怎么不一样呢


日出东方,唯我不败! 做任何东西都是耐得住寂寞,任何一个行业要有十年以上的积累才能成为专家
2006-05-15 00:11
快速回复:插入排序法的困惑!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017202 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved