南邮数据结构实验1.4:带表头结点单链表的非递减排序

题目:以实验 1.2 的带表头结点单链表为存储结构,编写程序实现单链表的非递减排序。

部分代码:

带表头结点单链表的非递减排序函数:

本来想用冒泡排序的,但是没成功,此部分程序参考了这里:https://bbs.csdn.net/topics/390668062

//简单选择排序:每次选择min的排到前面
Status Order(HeaderList *h){
    Node *s1,*s2,*s3,*s4,*p,*q;
    for (p=h->head;p!=NULL && p->link!=NULL;p=p->link) {     // p从指向头结点开始
        for (q=p->link;q!=NULL && q->link!=NULL;q=q->link) {
            if (p->link->element > q->link->element) {       // 如果当前结点元素值大于后面元素值,则交换
                s1=p->link;                                  // s1指向p后面的结点
                s2=p->link->link;                            // s2指向p后面的后面的结点
                s3=q->link;                                  // s2指向q后面的结点
                s4=q->link->link;                            // s4指向q后面的后面结点
 
                if (s2!=s3) {                                //如果s2不等于s3,说明交换两个结点的中间有一些其他结点数据
                    p->link=s3;
                    s3->link=s2;
                    q->link=s1;
                    s1->link=s4;
                }
                else {                                       // s2和s3指向同一个结点
                    p->link=s3;
                    s3->link=s1;
                    q=s3;
                    s1->link=s4;
                }
            }
        }
    }
    return OK;
}

完整程序:

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef int Status;
#define ERROR 0
#define OK 1

typedef struct Node {
	ElemType element;      //结点的数据域
	struct Node * link;    //结点的指针域
}Node;

typedef struct {
	struct Node* head;     //表头结点
	int n;
}HeaderList;


//带表头结点单链表的初始化
Status Init(HeaderList *h) {
    h->head=(Node*)malloc(sizeof(Node));   //生成表头结点
    if(!h->head){
        return ERROR;
    }
	h->head->link = NULL;                  //设置单链表为空表
	h->n = 0;
	return OK;
}


//带表头结点单链表的查找
Status Find(HeaderList *h,int i,ElemType *x){
    Node *p;
    int j;
    if(i<0||i>h->n-1){
        return ERROR;
    }
    p=h->head->link;
    for(j=0;j<i;j++){
        p=p->link;
    }
    *x=p->element;
    return OK;
}


//带表头结点单链表的插入
Status Insert(HeaderList *h, int i, ElemType x) {
	Node *p, *q;
	int j;
	if (i<-1 || i>h->n - 1)
		return ERROR;
	p = h->head;                          //从头结点开始找ai元素所在的结点p
	for (j = 0; j <= i; j++) {
		p = p->link;
	}
	q = (Node*)malloc(sizeof(Node));      //生成新结点q
	q->element = x;
	q->link = p->link;                    //新结点q插在p之后
	p->link = q;
	h->n++;
	return OK;
}


//带表头结点单链表的删除
Status Delete(HeaderList *h,int i){
    int j;
    Node *p,*q;
    if(!h->n){
        return ERROR;
        if(i<0||i>h->n-1){
            return ERROR;
        }
    }
    q=h->head;
    for(j=0;j<i;j++){
        q=q->link;
    }
    p=q->link;
    q->link=p->link;                //从单链表中删除p所指结点
    free(p);                        //释放p所指结点的存储空间
    h->n--;
    return OK;
}


//带表头结点单链表的输出
Status Output(HeaderList *h) {
	Node *p;
	if (!h->n)
		return ERROR;
	p = h->head->link;
	while (p) {
		printf("%d ",p->element);
		p = p->link;
	}
	return OK;
}


//带表头结点单链表的撤销
void Destroy(HeaderList *h){
    Node *p,*q;
    while(h->head->link){
        q=h->head->link;
        p=h->head->link->link;
        free(h->head->link);
        h->head=q;
    }
}


//简单选择排序:每次选择min的排到前面
Status Order(HeaderList *h){
    Node *s1,*s2,*s3,*s4,*p,*q;
    for (p=h->head;p!=NULL && p->link!=NULL;p=p->link) {     // p从指向头结点开始
        for (q=p->link;q!=NULL && q->link!=NULL;q=q->link) {
            if (p->link->element > q->link->element) {       // 如果当前结点元素值大于后面元素值,则交换
                s1=p->link;                                  // s1指向p后面的结点
                s2=p->link->link;                            // s2指向p后面的后面的结点
                s3=q->link;                                  // s2指向q后面的结点
                s4=q->link->link;                            // s4指向q后面的后面结点
 
                if (s2!=s3) {                                //如果s2不等于s3,说明交换两个结点的中间有一些其他结点数据
                    p->link=s3;
                    s3->link=s2;
                    q->link=s1;
                    s1->link=s4;
                }
                else {                                       // s2和s3指向同一个结点
                    p->link=s3;
                    s3->link=s1;
                    q=s3;
                    s1->link=s4;
                }
            }
        }
    }
    return OK;
}



void main()
{
	int i,j, x;
	HeaderList list;
	Init(&list);
	for (i = 8,j = 0; i >= 0; i--,j ++) {
		Insert(&list, j - 1, i);    //插入8~0
	}
    printf("the linklist is:");
	Output(&list);
    Order(&list);                   //非递减排序
    printf("\nthe linklist is:");
    Output(&list);
    Destroy(&list);
}

实验结果:

版权声明:本文为博主原创文章,未经博主允许不得转载。

全部评论

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务