精华内容
下载资源
问答
  • 对每个节点进行排序
    千次阅读
    2019-05-07 19:54:45

    初次用到链表的排序还是在C语言课程设计上,当时想着要把代码发到CSDN上,结果一拖再拖到现在。

    我的课程设计项目为“学生成绩管理系统”,所用链表为双向链表链表。
    涉及到成绩管理则避免不了成绩的排序。
    结构体中的项目包括:

    1. 学生成绩;
    2. 学生姓名;
    3. 学生学号;
    4. 结构体的头指针与尾指针;
      先创建结构体:
    #include"stdio.h"
    #include"stdlib.h"
    #include"string.h"
    struct student
    {
    	struct student *ahead;
    	float grade[10];
    	char name[10];
    	char x[10];
    	struct student *next;
    }*head, *end, *New, *get, *stu;
    

    设置head指针和end指针。head指向头结点,end始终指向尾节点。
    输入数据:

    int input(int N, char **G)//数据输入
    //变量说明:“N”为考试的科目数量,此处**G为字符串指针数组,其中存储着考试科目。
    {
    	int i, c = 1, icount = 0, s[10], j, k, d;
    	char r[10];
    	for (j = 0; j < 10; j++)
    		s[j] = 0;
    	while (c)
    	{
    		New = (struct student *)malloc(sizeof(struct student));
    		printf("\t\t输入该名学生姓名(结束请按‘0’):");
    		scanf("%s", New->name);
    		if (New->name[0] != 48)
    		{
    			printf("\t\t输入该名学生学号:");
    			scanf("%s", r);
    			icount++;
    			strcpy(New->x, r);
    			New->grade[N] = 0;
    			for (i = 0; i < N; i++)
    			{
    				printf("\t\t%s成绩:", G[i]);
    				scanf("%f", &New->grade[i]);
    				if (New->grade[i] < 60)
    					s[i]++;
    				New->grade[N] = New->grade[N] + New->grade[i];
    			}
    			strcpy(New->mima, "1234");
    			end->next = New;
    			New->ahead = end;
    			end = New;
    			end->next = NULL;
    		}
    	}
    	else
    	{
    		c = 0;
    	}
    }
    

    链表已经创建完成,现在只需要向其中添加数据,下一步祭出我屌炸天 的链表节点排序代码?
    此代码运用简单选择排序的排序方法。即,先比较两个节点中数据的大小,并两个选中较大或较小的一个。并让选中的节点与下一个节点中的数据比较直到最后一个节点。比较完毕后将最小的节点接到链表的最后。
    当然,开始排序之前,我创建了一个空节点让其存储成绩的数组的每一个元素都等于“-1”将其接到了链表的最后作为新的有序链表与旧的无序链表的边界。在排序完毕后程序自动将此空节点删除。得到的就是新的有序数组。

    1.排序前的准备阶段(假设此处为升序排序)

    主要步骤为:

    1. 创建三个结构体指针“ *min”、“*xunow”、“ *uend”;
    2. uend就是我添加的边界空指针;
    int paixu(int N)//成绩排序
    {
    	int i;//在程序的后便会让用户选择升序还是降序排序,变量i的作用是根据i的值选择排序方式。若i为1则降序排列,0则升序排列
    	struct student *min, *xunow, *uend;
    	uend = (struct student *)malloc(sizeof(struct student));
    	uend->grade[0] = -1;
    	uend->next = NULL;
    	uend->ahead = end;
    	end->next = uend;
    

    2.排序执行阶段

    上一步中创建的三个结构体指针已经用掉了一个,在这一步中“min”代表比较值最小的节点。"xunow"表示当前与min节点比较的节点。

    1. 通过简单选择排序找出旧链表中的最小值节点;
    2. 将此最小值节点接到链表的最后;
    printf("\n\t\t升序排序(0)     降序排序(1)\n\t\t");
    	scanf("%d", &i);
    	for (min = head->next; min->next->grade[0] != -1; min = head->next)
    	{
    		xunow = min->next;
    		if (i == 0)
    		{
    			do
    			{
    				if (xunow->grade[0] < min->grade[0])
    				{
    					min = xunow;
    				}
    				xunow = xunow->next;
    			} while (xunow->next->grade[0] != -1 && xunow->grade[0] != -1 && min->next->grade[0] != -1);
    			min->ahead->next = min->next;
    			min->next->ahead = min->ahead;
    			min->ahead = uend;
    			uend->next = min;
    			uend = min;
    		}
    		else
    		{
    			do
    			{
    				if (xunow->grade[0] > min->grade[0])
    				{
    					min = xunow;
    				}
    				xunow = xunow->next;
    			} while ( xunow->grade[0] != -1 && min->next->grade[0] != -1);
    			min->ahead->next = min->next;
    			min->next->ahead = min->ahead;
    			min->ahead = uend;
    			uend->next = min;
    			uend = min;
    		}
    		
    	}
    

    3.排序完成收尾阶段

    在执行完上步代码后,表明排序基本完成。按照步骤,此时边界空节点的旧链表一侧还有最后一个具有有效数据的节点,即存储最大数据的节点。现在只需要将此节点与边界节点一起转移到整个链表的最后再删除边界节点,就能最终完成链表的排序。

        min = head->next;
    	xunow = min->next;
    	head->next = xunow->next;
    	xunow->next->ahead = head;
    	xunow->next = NULL;
    	min->ahead = uend;
    	uend->next = min;
    	uend = xunow;
    	end = uend->ahead;
    	uend->ahead->next = NULL;
    	free(uend);
    	return 0;
    }
    

    这就是自己在本学期的课程设计中,灵光一现敲出的链表节点排序代码。虽然不够简洁但不管怎么样这段代码还是实现了功能,即节点排序。

    更多相关内容
  • 如何根据链表节点数据大小链表节点进行排序

    千次阅读 多人点赞 2020-09-14 15:57:52
    (1)比较了两个节点的大小后,指针进行改变,从而交换节点的顺序; (2)比较了两个节点的大小后,只交换数据域,而不改变指针,从而交换节点的顺序。 第二种办法比较简单,本文主要第二种方法进行讲解。 链表...

    对链表排序有两种方法:
    (1)比较了两个节点的大小后,对指针进行改变,从而交换节点的顺序;
    (2)比较了两个节点的大小后,只交换数据域,而不改变指针,从而交换节点的顺序。
    第二种办法比较简单,本文主要对第二种方法进行讲解。
    链表节点排序算法,采用(冒泡排序)。
    定义一个指针end,end最开始时赋值为空,再经过一次比较后,找到一个最大值,将该最大值的指针赋给end;每次循环找到该次循环中的最大值,都将其指针赋值给end,等于说end每次循环结束,都会向前移动一个节点,这样就可以根据end和头节点是否相等作为排序结束条件,因为end指向的节点及其后面的节点中的数据肯定是大于end之前的,所以没有必要比较,因此每次循环根据是否到达end作为该次循环结束条件。
    最开始: 定义一个指针end,end最开始时赋值为空。在这里插入图片描述
    第一次比较:找到一个最大值,将该最大值的指针赋给end;end就指向了第一次找到的最大值。
    在这里插入图片描述

    第n次比较:每次循环找到该次循环比较中的最大值,都将其指针赋值给end。
    在这里插入图片描述

    最后一次循环:每次循环结束,end都会向前移动一个节点,这样就可以根据end和头节点是否相等作为整个排序结束的条件。
    在这里插入图片描述
    程序源码:
    //排序源码

    link_node_t* bubblesort(link_node_t* head)     //head是有头链表
    {  
        head = head->next;                  
        if (head == NULL) return NULL;            
        //定义一个尾,初值为空,以后为每次的最大值  
        link_node_t* end = NULL;  
        while (end != head)  
        {  
            //p和pnext一前一后
            link_node_t* p = head;               //p在前
            link_node_t* pnext = head->next;     //pnext在后  
            while (pnext != end)  
            {  
                //比较相邻的节点数据
                if (p->size < pnext->size)          
                {  
                    //数据交换
                    swapS(p->data, pnext->data);      //交换函数名(字符串)
                    swapI(&p->size, &pnext->size);   //交换数据(整型)
                }  
                //p和pnext同时向后移动一个节点
                p = p->next;  
                pnext = pnext->next;  
            }  
            //该次循环结束,找到的该次循环中的最大值。
            end = p;  
        }  
        return head;  
    } 
    

    数据交换程序

    这里封装两个交换函数,一个是对字浮串进行交换,一个是对整型进行交换。
    void swapI(int* a, int* b)  
    {  
        int temp = 0;  
        temp = *a;  
        *a = *b;  
        *b = temp;  
    }  
    void swapS(char* arr, char* brr)  
    {  
        char temp[N] = {0};  
        strcpy(temp,arr);  
        strcpy(arr,brr);  
        strcpy(brr,temp);  
    } 
    
    展开全文
  • 详解XML节点属性排序

    千次阅读 2022-03-25 22:36:38
    用python实现“xml节点中的属性进行排序

    1. 引入

    为了对xml文件计算hash值,需要固定xml中item的属性顺序。否则相同xml但属性顺序不同,就会造成hash值不同(MITRE的Defense Evasion逃脱检测)。

    就是想让如下两种写法: <a x="11" b="12" a="13"></a><a x="11" b="12" a="13"></a>,经过属性排序后,都变为 <a a="13" b="12" x="11"></a>。注意这里要解决的问题是对xml节点内部的属性排序,不是节点之间的排序。

    如何用python实现“对xml节点中的属性进行排序”呢?

    2. 问题分析

    为了解决这个问题,查了xml解析的各种库,Google搜了关键词:

    • sort xml attributes alphabetically
    • canonical XML python
    • xml attribute sort python
    • python sort xml elements alphabetically
    • python xml attribute order
    • sort android manifest by python
    • python write xml with attribute order
    • python enforcing specific order for xml attributes
    • python enforcing order for xml attributes
    • python enforcing xml attributes order
    • xml c14n

    看了各种资料,写代码做了一些测试,得出如下结论:

    1. 在XML中,本身是对属性没有顺序(order)要求的,也就是XML标准中认为XML的顺序无意义

    2. 只有把XML写到.XML文件中,属性的顺序是对最终XML的表现形式(hash值)有影响

    3. 往大一点说,这个问题属于XML规范化(XML Canonicalization,c14n)问题,W3C对这个c14n有专门的定义(见参考2)

    4. 然而,并没有什么成熟的python的库来实现c14n。有一些个人实现的c14n就是对tag做了规范化(简单的replace)。有一些库的老版本做过c14n但后来又deprecated了。其他一些搜到的方法也跑不通

    5. 根据如下链接,发现了一点蛛丝马迹:貌似 xml.etree.ElementTree 写xml到文件中时,会改变xml的attributes的顺序,而且根据回复看这个是将结果变为有序的。详见参考3.

    3. 测试

    1. 属性无序的xml文件

    创建一个名为easy1.xml的文件,内容如下,

    <a x="11" b="12" a="13">
        <b y="21" c="22" d="23">
            <c t="31" f="32" e="33">
            </c>
        </b>
    </a>
    
    1. python程序
    import xml.etree.ElementTree as ET
    tree = ET.parse('easy1.xml')# read xml from file
    tree.write('tmp1.xml', encoding="UTF-8")# write xml content to file
    

    程序只做了很简单的事情,读入xml文件,然后直接写到另一个文件中。

    1. 结果

    程序运行后,得到的tmp1.xml文件中的内容如下

    <a a="13" b="12" x="11">
        <b c="22" d="23" y="21">
            <c e="33" f="32" t="31">
            </c>
        </b>
    </a>
    

    可见最终结果是和原始easy1.xml文件内容不一样的,这里的各个节点内部的属性都变的有序了。

    所以验证了第2部分第5个结论。

    4. 为什么能做到有序

    1. 动态调试源码

    单纯通过这样简单的验证,是不敢保证每一次这样操作都是有序的。有可能是ElementTree将xml解析为dict,这样因为dict的无序性,上一步的测试结果可能就是意外。

    所以还需要查看下2中的源码实现原理,看看源码中是否做了属性有序的保证。通过(见参考1)中方法,找到如下源码:

    • /home/xxx/anaconda3/envs/xxxxx/lib/python3.7/xml/etree/ElementTree.py

    打开这个文件,在其函数_serialize_xml中,如下位置,加入断点(或者print)进行动态调试:

                if items or namespaces:
                    if namespaces:
                        for v, k in sorted(namespaces.items(),
                                           key=lambda x: x[1]):  # sort on prefix
                            if k:
                                k = ":" + k
                            write(" xmlns%s=\"%s\"" % (
                                k,
                                _escape_attrib(v)
                                ))
                    print(items)#这里加print调试
                    for k, v in sorted(items):  # lexical order
                        if isinstance(k, QName):
                            k = k.text
                        if isinstance(v, QName):
                            v = qnames[v.text]
                        else:
                            v = _escape_attrib(v)
                        write(" %s=\"%s\"" % (qnames[k], v))
    
    

    运行3中的python程序,可得输出结果(去掉非list的内容,因为这里只有sorted只对list有效)为:

    [('x', '11'), ('b', '12'), ('a', '13')]
    [('y', '21'), ('c', '22'), ('d', '23')]
    [('t', '31'), ('f', '32'), ('e', '33')]
    
    

    这里的输出结果,就是源码items的内容,从结果上也能看到这都是xml节点的属性。通过sorted排序后,这些属性就被写到外部文件中了。

    所以,从源码调试中,验证了ElementTree的write操作,是会对xml的节点属性进行排序的,排序规则是(sorted函数自带的lexical order,也就是按字符串排序)。

    5. 结论

    1. 用xml.etree.ElementTree来解析manifest文件,这个库在将xml写到外部文件时,会对属性排序后再写出去
    2. 很多其他库解析manifest会保持原始的attribute顺序,比如lxml

    6. 参考

    1. 如何动态调试Python的第三方库,https://blog.csdn.net/ybdesire/article/details/54649211
    2. XML Canonicalization, https://www.w3.org/TR/xml-exc-c14n/
    3. https://stackoverflow.com/questions/14257978/elementtree-setting-attribute-order
    展开全文
  • 解决方案:为每个form-item绑定 data-id属性,值为后台传入的序号,再用sortable.js的sort()方法进行排序。 1.HTML代码 &lt;el-form :model="form" :rules="rules" ref="formAdd&...

    需求描述: 前端代码写的顺序是:用户账号、用户姓名、手机号码,需求想对此进行灵活排序。

    解决方案:为每个form-item绑定 data-id属性,值为后台传入的序号,再用sortable.js的sort()方法进行排序。

     

    1.HTML代码 

    <el-form :model="form" :rules="rules" ref="formAdd" id="formAdd">
                  <el-form-item label="用户账号" :label-width="formLabelWidth" prop="userName" :data-id="3">
                    <el-input v-model="form.userName" autocomplete="off"></el-input>
                  </el-form-item>
                  <el-form-item label="用户姓名" :label-width="formLabelWidth" prop="personalName" :data-id="2">
                    <el-input v-model="form.personalName" autocomplete="off"></el-input>
                  </el-form-item>
                  <el-form-item label="手机号码" :label-width="formLabelWidth" prop="phone" :data-id="1">
                    <el-input v-model="form.phone" autocomplete="off"></el-input>
                  </el-form-item>
    </el-form>

    注意:data-id属性,即为sortable 对象 toArrary()方法得到的顺序,这里为[3,2,1]

    2. JS代码 

       先引入sortable.js,在节点渲染完毕后,JS代码如下:

             let body =  document.getElementById('formAdd');
            var sortable = Sortable.create(body)
            var order = sortable.toArray();
            console.log(order)//[3,2,1]
            sortable.sort(order.sort()); // apply

    用sortable对象的sort()方法即可对节点进行排序。

    3.排序前后对比图

    排序前:

     排序后

    展开全文
  • 题目:设计一算法,求出指定节点在给定二叉排序树中的层次 分析: 我们可以根据二叉排序树的性质,从根节点一直向下查找,查找一次,层次便加一 typedef struct node { int data; node *left, *right; }...
  • ANSYS使用APDL数组实现节点坐标大小排序,并返回其对应的节点编号 注:节点组件node_cm中的所有节点都在一条直线上,即所有节点坐标的三个分量有两个是相同的...选择一个节点组件 *get,firstnodenum,node,0,num,...
  • 链表进行插入排序(C语言实现)

    千次阅读 2021-01-09 10:26:11
    链表进行插入排序。 插入排序的动画演示如下。从第一元素开始,该链表可以被认为已经部分排序(用黑色表示)。 每次迭代时,从输入数据中移除一元素(用红色表示),并原地将其插入到已排好序的链表中。 插入...
  • 通过索引找到每一行所对应列的数据,之后该列的所有数据进行排序(本实例只进行降序排列),排序结果的每个数据的索引就是该数据所对应行的位置。 【问题解决】 1、如何知道那一列需要排...
  • 做LeetCode时遇到的一个小问题,总结一下。 链表定义为如下 public class ListNode {  int val;...要求用插入排序对进行排序,并返回第一个节点。 解决方案的代码如下: public class Solution {
  • 在二叉排序树中查找节点查找一次,层次就+1,因此判断指定节点在二叉树中的层次,只需要看进行了几次非递归查找操作。 有了这思路之后代码就非常简单啦~ int search_1(btree T, int a) { while (T!=...
  • 链表排序总结(全)(C++)

    千次阅读 多人点赞 2020-07-18 15:17:48
    链表排序一般指单链表排序,链表是不支持随机访问的,需要访问后面的节点只能从表头顺序遍历,所以链表的排序是一相对比较复杂的问题。 那么怎样进行链表排序呢? 借助外部空间 既然数组排序简单,那可以借助数组...
  • 二叉排序树——寻找父节点

    千次阅读 2020-03-24 11:10:59
    【问题描述】二叉排序树,也称为二叉查找树。可以是一颗空树,也可以是一颗具有如下特性的... 现在给你N关键字值各不相同的节点,要求你按顺序插入一初始为空树的二叉排序树中,每次插入后成功后,求相应的父亲...
  • 链表的排序

    千次阅读 多人点赞 2021-09-11 12:29:42
    你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,链表进行排序吗? 示例 1: 输入:head = [4,2,1,3] 输出:[1,2,3,4] 示例 2: 输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5] 示例 3: 输入:...
  • 二叉排序树求根节点

    千次阅读 2018-05-14 15:17:10
    题目描述二叉排序树,也称为二叉查找树。可以是一颗空树,也可以是一颗具有如下特性的... 现在给你N关键字值各不相同的节点,要求你按顺序插入一初始为空树的二叉排序树中,每次插入后成功后,求相应的父亲节点...
  • 排序中非叶子节点的位置怎么算

    千次阅读 2020-09-15 15:36:30
    首先一个n个节点二叉树的度n-1,从下往上看,因为除了根节点以为每个节点都有一个入度 设n个节点中 有x个非叶子节点和y个叶子节点,x+y =n ,从上往下看,所有的非叶子节点都有两个出度,叶子节点没有-》2x = n-1 = ...
  • 算法学习总结(2)——温故十大经典排序算法

    万次阅读 多人点赞 2019-08-29 14:57:51
    一序列对象根据某个关键字进行排序。 1.2、排序术语 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;内排序:所有排序操作都在...
  • 十大经典排序算法-堆排序,计数排序,桶排序,基数排序 1-堆排序 算法思想: 算法图解: 示例代码: 在这里插入代码片 复杂度分析: 2-计数排序 算法思想: 算法图解: 示例代码: 在这里插入代码片 复杂度分析: 3-桶排序 ...
  • 用xgboost模型特征重要性进行排序

    万次阅读 多人点赞 2018-08-12 21:08:21
    用xgboost模型特征重要性进行排序 在这篇文章中,你将会学习到: xgboost预测模型特征重要性排序的原理(即为什么xgboost可以预测模型特征重要性进行排序)。 如何绘制xgboost模型得到的特征重要性条形图。...
  • 文章目录一、总览二、常用排序算法1、冒泡排序——交换类排序1.1 简介1.2 源码1.3 效果2、快速排序——交换类排序2.1 简介2.2 源码2.3 效果3、选择排序——选择类排序3.1 简介3.2 源码3.3 效果4、堆排序——选择类...
  • 链表中的每个节点的成员由两部分组成: 1. 数据域:专门用来保存各个成员的信息数据。 2. 指针域:专门用来与其他节点链接。 2. 结构体中的两个重要指针 直接后继 & 直接前驱: 直接后继:我个人习惯称之为后向指针...
  • 给定一二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如: 给定二叉树:[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] ...
  • 十大排序算法

    万次阅读 多人点赞 2021-08-20 13:37:46
    对每一对相邻元素作同样的工作,从开始第一到尾部的最后一对,这样在最后的元素应该会是最大(小)的数 重复步骤1~2,重复次数等于数组的长度,直到排序完成 代码实现 下面数组实现排序:{24, 7, 43, 78, 62, 98...
  • 根据上述规则可以看出,根节点值不同,形成的二叉搜索树就不同,那么[1:n]范围内的n数就有n不同的选择。 [1:i−1]这i-1数在其左子树上,[i+1:n]这n-i数在其右子树上。 通过[1:i−1]这i-1数可以构成多...
  • 双向链表的排序

    千次阅读 2020-03-03 20:35:49
    用单个指针单一方向进行排序,利用选择法排序的方法进行排序,对于链表排序的关键在于要和数组的排序方法一一对应,由于链表并不知道有多少个节点,也即不知道要进行多少次循环,所以对于数组中的惯用for循环就不...
  • java求二叉树叶子节点个数的函数

    千次阅读 2019-06-01 09:28:13
    树的每个节点最多只能有两个子节点,称为左子树与右子树 2.左子树上所有结点的值均小于或等于它的根结点的值。 3.右子树上所有结点的值均大于或等于它的根结点的值。 4.左、右子树也分别为二叉排序树。 叶子...
  • 二叉排序树详解

    千次阅读 2022-04-01 16:49:31
    摘要:本篇笔记专门介绍二叉排序树,重点讲解了二叉排序树的特性,以及二叉排序树各方面的基本实现。
  • 也就是说,在堆中,一个待排序序列的元素都可以看做是一个堆的节点,而堆的个节点,又有两个子节点。 我们称图中任何一个节点下方的左右两个分支节点为其左右孩子节点,这个节点本身称之为其左右孩子节点...
  • 题目求包含n个节点的二叉树的种类数;方法1设dp[i]表示共有i个节点时,能产生的BST树的个数 n == 0 时,空树的个数必然为1,因此dp[0] = 1 n == 1 时,只有1这个根节点,数量也为1,因此dp[1] = 1 当根节点...
  • 数据结构与算法—二叉排序(查找)树

    千次阅读 多人点赞 2019-08-19 13:23:31
    再数据结构中`树`、`图`才是数据结构标志性产物,(线性表大多都现成api可以使用),因为树的`难度相比线性表大一些`并且树的`拓展性很强`,你所知道的树、二叉树、**二叉排序树**,**AVL树**,线索二叉树、**红黑树**...
  • 二叉排序

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 382,809
精华内容 153,123
热门标签
关键字:

对每个节点进行排序