C语言链表操作(冒泡排序提取最大值)

默认分类 | 2020-03-21 18:36:02 | 阅读 254 次 | 评论(0)
#include<stdio.h>
#include<stdlib.h>

/*冒泡排序提取最大值,并使最大值添加到最后(注释两种方法)
注意:输入-1退出添加链表数据*/
typedef int DataType; //定义单链表的数据类型为整型
struct Node
{
    DataType      data;  //数据域
    struct Node*  next;  //指针域
};
typedef struct Node  *PNode;      //定义指向结构体的PNode类型
typedef struct Node  *LinkList;   //定义链表类型

LinkList SetNullList_Link() //创建带有头结点的空链表
{
    LinkList head = (LinkList)malloc(sizeof(struct Node));
    if (head != NULL) head->next = NULL;
    else printf("alloc failure");
    return head; //返回头指针
}

void CreateList_Tail(struct Node* head)// 尾插法建立单链表
{
    PNode p = NULL;
    PNode q = head;
    DataType data;
    scanf("%d", &data);
    while (data != -1)
    {   //分配空间,赋值
        p = (struct Node*)malloc(sizeof(struct Node));
        p->data = data;
        p->next = NULL;
        q->next = p;
        q = p;
        scanf("%d", &data);
    }
}

void print(LinkList head)    //输出单链表
{
    PNode  p = head->next;
    while (p)
    {
        printf("%d\n", p->data);
        p = p->next;
    }
    printf("\n");
}
void DestoryList_Link(LinkList head)  //释放单链表
{
    PNode  pre = head; 
    PNode p = pre->next;
    while (p)
    {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);
}

void MoveMaxToTail(LinkList H) //冒泡算法
{
	LinkList q = H, p = H->next, r = H, s;
    while( p != NULL ){     //寻查找最大值点及其前驱结点
        if((p->data) - (q->data) > 0){    
			
            s = r;//s记录最大值域节点的直接前驱结点
            q = p;
			
        }
		
		else if((p->data) - (q->data) < 0){//否则交换指针数据
			
			s = r;//s记录最大值域节点的直接前驱结点
			DataType tmp = q->data;
			q->data = p->data;
			p->data = tmp;
			
            q = p;
		}
		r = p; //法1否则没找到指针后移
		//r=p;r->next=p->next;//法2取出最大值,释放连接,建立新连接	
        p = p->next;
		
    }
    //判断最大值点位置
    if( q != r ){      
        if( q == H ){     
            H = H->next;
        }
        else{                
            s->next = q->next;
        }
    //否则将最大值点与末尾点交换
        r->next = q;   
        q->next = NULL;
    }
    //你的代码将嵌入在这里
}

int main()
{
    LinkList head = NULL;
    head = SetNullList_Link();
    CreateList_Tail(head);
    MoveMaxToTail(head);
    print(head);
    DestoryList_Link(head);
    return 0;
} 
捕获.PNG (上传于2020-03-21 18:36:02)
捕获.PNG
文章评论,共0条
游客请输入验证码
文章分类
最新评论