#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//输入的一个字符为一个链表节点
typedef struct node
{
char data;
struct node *prior, *next;
} ch_node;
//找到链表的里val最大的节点，并返回val
char findmax(ch_node *head)
{
ch_node *p = head;
char data_Max; /*记录最大值*/
if(NULL == p)
{
printf("链表为空!\n");
return '\0';
}
data_Max = p->data; /*初值为第一个结点值*/
while(p->next != NULL)
{
if(data_Max < p->next->data) /*data_Max保存最大值*/
{
data_Max = p->next->data;
}
p = p->next;
}
return data_Max;
}
//用直接插入算法对此链表排序, 传如链表头指针，返回排后新的头节点地址
ch_node *insert_sort(ch_node *head)
{
int flag = 0;
ch_node *p = NULL;
ch_node *tmpH = NULL;
ch_node *tmpT = NULL;
ch_node *ptr = NULL;
if(NULL == head)
{
printf("链表为空!\n");
return NULL;
}
/*直接插入排序算法思路:
从第一个结点开始拆除原始链表，与新链表的后项比较，如果大于，续在其后，如果小于，前项后移循环比较*/
p = malloc(sizeof(ch_node));
p->data = head->data;
tmpH = p;
tmpT = p;
p->prior = NULL;
p->next = NULL;
ptr = head;
while(NULL != head)
{
ptr = head->next;
head = head->next;
head->prior = NULL;
if(ptr->data > tmpT->data) /*从小到大顺序排列*/
{
tmpT->next = ptr;
ptr->prior = tmpT;
tmpT = ptr;
tmpT->next = NULL;
}
else
{
p = tmpT;
while(!flag)
{
if(NULL != p->prior) /*中间结点*/
{
if(ptr->data > p->prior->data)
{
ptr->next = p;
ptr->prior = p->prior;
p->prior->next = ptr;
p->prior = ptr;
flag = 1;
}
else
{
p = p->prior;
}
}
else /* 头结点*/
{
ptr->next = p;
ptr->prior = NULL;
p->prior = ptr;
tmpH = ptr;
flag = 1;
}
}
}
}
head = tmpH;
return head;
}
int main(int argc, char *argv[])
{
ch_node *head;
ch_node *ptmp;
/*1.从键盘输入一行字符串，调用函数建立反序的链表，然后输出整个链表
链表节点的定义为 ch_node, 代码写这里*/
char str[81];
int i = 0;
head = NULL;
printf("请输入一行字符串:\n");
scanf("%s", str);
while(str[i] != '\0') /*反序链表可以考虑前插法*/
{
ptmp = malloc(sizeof(ch_node));
if(NULL == ptmp)
{
printf("空间分配失败!结束!\n");
return -1;
}
else /*前插建立链表*/
{
ptmp->data = str[i];
ptmp->next = head;
if(head != NULL)
{
head->prior = ptmp;
}
head = ptmp;
}
i++;
}
head->prior = NULL;
//2.找到链表的里val最大的节点，并返回val
char max = findmax(head);
printf("max = %c\n", max);
//打印排序前
ptmp = head;
while(ptmp)
{
printf("%2c", ptmp->data);
ptmp = ptmp->next;
}
printf("\n");
//3.用直接插入算法对此链表排序
head = insert_sort(head);
//打印排序后
ptmp = head;
while(ptmp->next)
{
ptmp = ptmp->next;
}
printf("<%d>\n", __LINE__);
while(ptmp)
{
printf("%2c", ptmp->data);
ptmp = ptmp->prior;
}
printf("\n");
return 0;
}
排序部分的错误，怎么调试都不明白，请大家指导一下 谢谢！！ |
楼主
标题置顶
标题高亮
