拉丁方阵

发表于 2017-02-02

function Latinsquare(num){
	var list=[];
	for(var i = 0;i<num;i++){
	  var pre = 0;
	  if(i==0){
	    pre=num;
	  }else{
	    pre = i;
	  }
	  var nextt = 0;
	  if(i ==num-1){
	    nextt = 1;
	  }else{
	    nextt = i+2;
	  }
	  list.push({
	    prior:pre,
	    data:i+1,
	    next:nextt
	  })
	}
	for(var i = 0;i<num;i++){
	  var string=[];
	  var p = 1;
	  for(var j = 0;j<i;j++){
	    p = list[p-1].next;
	  }
	  for(var k = 0;k<num;k++){
	    string.push(list[p-1].data);
	    p = list[p-1].next;
	  }
	  console.log(string);
	}
}
Latinsquare(5);

判断单链表是否有环

发表于 2017-02-02

有环定义:链表的尾节点指向了链表中的某个结点

方法一：p、q指针同时向前走，但q每次都从头开始走，对于每个结点，若p、q走的步数不等则说明有环
方法二：快慢指针:使用p,q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p==q,则存在环
代码

单链表

发表于 2017-02-02

头插法建立单链表

代码链接

尾插法建立单链表

头插法建立的链表输入顺序与结点次序相反，尾插法可以使二者顺序相同

R做索引，S做中介节点
代码链接
重点r=p;将尾节点更新为r

整表删除

参照删除单链表制定位置结点代码代码链接

快慢指针—>标尺思想

快速找到未知长度单链表的中间结点代码链接

单链表与顺序存储结构优缺点

1.存储分配方式：
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素;
单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
2.时间性能：
—查找
顺序存储结构O(1);
单链表O(n)
—插入和删除
顺序存储结构需要平均移动表长一半的元素，时间为O(n);
单链表在计算出某位置的指针后，插入和删除时间仅为O(1)
3.空间性能
顺序存储结构需要预分配存储空间，分大了容易造成空间浪费，分小了容易发生溢出
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

小结

1.频繁查找，较少插入删除操作，宜用顺序存储结构，如，游戏开发时用户注册的个人信息的存储
2.频繁插入删除操作，较少查找，宜用单链表结构，如游戏中的玩家的装备列表
3.当线性表大致长度已知，宜用顺序存储结构，反之，长度变化大或未知，则用单链表

静态链表

发表于 2017-02-02

用数组描述的链表叫做静态链表
这种描述方法叫做游标实现法

Staticlinklist是一个容量为maxsize大的数组，数组每一项是一个结构struct，
这个结构包含两项，数据data和游标cur
整个数组的第一项(下标为0)和最后一项（下标为maxsize-1）的数据部分不存放数据
把未使用的数组元素（数据部分为空称为备用链表
约定：
——第一项的游标指向数组中除收尾两项外的项中，第一个数据部分为空的项，即首项游标为该项的下标/备用链表第一个结点的下标;
——尾项游标指向第一个有数据的元素相当于头结点作用
——其他元素游标等于其指向的元素位于数组中的下标
——数据元素的最后一项的游标等于首项下标0,即指向备用链表开始结点

初始化静态链表相当于初始化数组

Status InitList(StatixLinkList space)
{
	int i;
	for(i =0;i<MAXSIZE-1;i++){
		space[MAXSIZE-1].cur = 0;
		return OK;
	}
}

链表插入，删除，求长度代码链接

单循环链表

发表于 2017-02-02

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表成为单循环链表，简称循环链表

循环链表并不一定要有头结点
与单链表的主要差异为判断链表是否为空
单链表为空条件为head->next = null
循环链表为空条件为head->next = head
终端节点用尾指针rear指示，查找终端结点是O(1);开始结点是rear->next->next,也是O(1);
[插入、删除、返回位置代码思路参考单链表]
Rear == rear->next 空循环链表

小结
循环链表的特点是无须增加存储量，仅对链接方式稍作改变，即可使得表处理更加方便灵活

线性表顺序存储结构

发表于 2017-02-02

顺序存储结构

结构struct{
数据类型数组名data[数组最大长度MAXSIZE]；
Int length;(线性表当前长度/数组当前数据个数)
}

封装3个属性
1.存储空间起始位置，数组data,它的存储位置就是线性表存储空间的存储位置
2.线性表最大存储容量：maxsize ,初始化后一般不变
3.线性表当前长度：length，时刻改变

地址计算方法

假设每个元素占C个存储单元（字节），LOC表示获得存储位置的函数
LOC( )= loc( )+C
LOC( )= loc( )+(i-1)*C
假设,线性表最大长度设置为10；当前长度为4；如下
var maxsize = 10;
var list ={
data:[1,2,3,4],
length:4
}

获取线性表第i个位置的元素

function getitem(list,i){
  if(i<1 || i >list.length || list.length == 0){   //线性表位置从1 开始
    console.log("input is error")
    return
  }
  var item;
  item = list[i-1]; //数组下标从0 开始，与线性表差1
  return item;
}
var ff = getitem(list.data,0);
console.log(ff);

在线性表第i个位置插入元素item

function insertitem(list,i,item){
  if(list.data.length == maxsize){
    console.log("the list is full");
    return
  }
  if(i<1 || i >list.data.length){
    console.log("the position is not in the range")
    return
  }
  if(i<list.data.length){
    for(var j = list.data.length -1;j>=i-1;j--){
      list.data[j+1] = list.data[j];
    }
  }
  list.data[i-1] = item; 
  list.length = list.length+1;
}
insertitem(list,2,5);
console.log(list);

删除线性表第i个位置的元素

function deleteitem(list,i){
  if(list.data.length == 0){
    console.log("the list is empty")
    return
  }
  if(i<1 || i >list.data.length){
    console.log("the position is not in the range")
    return
  }
  var temp = list.data[i-1];//被删除的元素
  if(i<list.data.length){
    for(var j = i ;j<list.data.length;j++){
      list.data[j-1] = list.data[j];
    }
    
  }
  list.data.splice(list.data.length-1,1);//删除最后一个
  list.length = list.length-1;
}
deleteitem(list,3);
console.log(list);

小结

在存、读数据时，不管是那个位置,时间复杂度都是O(1).
而在插入或删除时，时间复杂度都是O(n);
比较适合元素个数稳定，不经常插入和删除元素，而更多操作是存取数据的应用。
优点：
1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间
2.可以快速存取表中任意位置元素
缺点
1.插入和删除操作需要移动大量元素
2.当线性表长度变化较大时，难以确定存储空间的容量
3.容易造成存储空间的碎片

线性表链式存储结构

发表于 2017-02-02

链式存储结构

用一组任意的存储单元存储线性表数据元素，这组存储单元可以存在内存中未被占用的任意位置；每个元素需要两个位置，一个存储元素本身，一个存储它后继元素的存储地址（指针）
数据域：存储数据元素信息的域；
指针域：存储直接后继位置的域；
指针/链：指针域中存储的信息
存储映像/结点（node）：数据域和指针域这两部分信息组成的数据元素
链式存储结构：n个结点连接成一个链表
单链表：链表中每个结点中只包含一个指针域

头指针：链表中第一个结点的存储位置
最后一个结点指针为空

头结点的数据域一般不存储任何信息
头指针
—— 指指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针
在头结点之前
—— 头指针具有标志作用，所以常用头指针冠以链表的名字（指针变量的名字）
—— 无论链表是否为空，头指针均不为空
—— 头指针是链表的必要元素
头结点
—— 为了操作统一和方便而设立，放在第一个元素的结点之前，其数据域一般无
意义（但也可以用来存放链表的长度）
—— 有了头结点，对第一个元素节点前插入结点和删除第一个结点操作与其他结
点的操作就统一了
——头结点不一定是链表的必须要素

用结构指针来描述单链表

typedef struct Node
{
	ElemType data;//数据域
	struct Node* Next;//指针域
}Node;
Typedef struct Node* LinkList

Typedef struct Node LinkList 将Node取别名为LinkList
结点由存放数据元素的数据域和存放后继结点的地址指针组成

假设P是指向线性表第i个元素的指针，则该结点ai的数据域为p->data
指针域为p->next,因为p->next是一个指针，它指向第i+1个元素ai+1
因此，如果p->data=ai,那么p->next->data=ai+1

单链表元素读取

链表元素不像顺序存储线性表通过位置计算可以得到，需要一个一个找

时间复杂度为O（n）;核心思想：“工作指针后移”

单链表元素插入O(n)

单链表元素删除O(n)

以上操作代码链接

小结

如果我们想从第i个位置开始，插入连续10个元素，
对顺序存储结构意味着，每次插入都需要移动n-i个位置,所以每次都是O(n);
而单链表，只需要在第一次找到第i个位置的指针，此时时间复杂度为O(n),
接下来只是简单的赋值移动指针而已，时间复杂度都是O(1)
因此对于频繁插入或删除数据来说，单链表效率更高。

线性表基本概念

发表于 2017-02-02

线性表

由0个或多个数据元素组成的有限序列

1.序列，有顺序
2.若元素存在多个，则第一个无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继
3.有限的，无论计算机发展到多强大，线性表处理的元素都是有限的

(ai-1,ai,ai+1) ai-1是ai 的直接前驱元素;ai+1是ai的直接后继元素
线性表长度即线性表元素个数,个数为0，即为空表

数据类型

一组性质相同的值的集合及定义在此集合上的一些操作的总称（编程语言中的各种类型）

抽象数据类型把数据类型和操作结合捆绑在一起

标准格式

ADT（抽象数据名）list
Data（数据元素之间逻辑关系的定义）
	  数据间关系一对一
Operation（操作）
	Initlist()初始化操作 新建一个空表
	ListEmpty(list) 判断线性表list是否为空，空返回true
	Clearlist(list) 清空线性表
	Getitem(list,i,e) 获取线性表第i个位置元素并返回给e
	Search(item,list) 在list里面查找item是否在里面，存在返回序号；否则返回0
	  				 线性表从1 开始
	Listinsert(item,i,list) 在list的第i个位置插入item
	Listdelete(item,i,list) 删除list中第i个位置元素，并返回该元素给item
	Listlength(list) 返回线性表list元素个数
endADT

基础概念

发表于 2017-02-01

数据结构

逻辑结构：数据元素之间的关系
物理结构：逻辑结构在计算机中的存储形式

四大逻辑结构：
1.集合结构：同属一个集合，相互之间无关系
2.线性:一对一
3.树形：一对多
4.图形：多对多

物理机构：
顺序存储：地址连续
链式存储：可连续可不连续

算法

1.特性
输入：0或多个
输出：至少1个或多个
有穷性：不会无限循环，有限时间内结束
确定性：无歧义，一条路径得到结果相同
可行性：有限次数完成

2.设计要求
正确性：
算法程序没有语法错误；
对于合法输入能够产生满足要求的输出；
对于非法输入能够产生满足规格的说明；
对于故意刁难得测试输入都有满足要求的输出结果；
可读性：
便于阅读和修改
健壮性：
当输入数据不合法时，算法也能做出相关处理，而不是产生异常、崩溃或明明奇妙结果
时间效率高和存储量低

函数渐进增长

函数F(n)在n>N时,始终大于函数G(n),就说G(n)渐进增长F(n)

X为输入规模，Y 为算法执行次数（复杂度） aX^b+cX+d 执行次数计算方法
Y= aX^b+cX+d a,c,d对Y值的影响均可忽略，此时只看b值，b越大Y 增长越快
Y= cX+d c,d忽略,Y随X增长
Y = d d无论为多大常熟，均视作1

时间复杂度

T(n)=O(f(n)); f(n)是n的某个函数
执行次数 = 时间
O() 大O记法
T(n)增长最慢的算法为最优算法

推导大O阶

用常熟1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项存在且不是1，则去除与这个项相乘的常数

时间复杂度耗时从小到大O(以下项)

打印文件

发表于 2017-02-01

打印文件

关键语句：Window.print();

$scope.print= function(){
      $("#noprint").css('display','none');
      $("#print").css('display','block');
      window.print();
      $("#print").css('display','none');
      $("#noprint").css('display','block');
     }

一个具有打印功能的HTML代码地址

浏览器分页打印

在需要分页的地方插入语句

<div class="PageNext" ng-if='$index<printdata.length-1'></div>
  .PageNext
  {
      page-break-after: always;
  }

例如打印多个表格，每一张表格内容的分页由浏览器决定，但是A表格结束到B表格开始,B表格另起一页开始打印由添加的语句决定
另外，打印一张表格当内容产生多页时，将表名放在thead中可以使表名打印在该表的每一页上

<div ng-repeat="line in printdata" class="row"><!--打印多张表-->
     <table width="98%" border="1" align="center" cellpadding="2" cellspacing="0" bordercolor="#000000" class="tabp">
      <thead>
        <tr><!-- 表名,合并单元格,去边框-->
            <td colspan="3" style="border: 1px solid #fff;border-bottom-color: black;">
              <span style="float: left">日期：{{date}}</span><span>{{line.line_title}}</span>
            </td>
        </tr>
        <tr>
          <th width="5%"> 序号 </th>
          <th width="13"> 分类 </th>
          <th width="82%"> 明细</th>
        </tr>
      </thead>
      <tbody>
        <tr ng-if="line.columns.length>0" ng-repeat="item in line.columns">
          <td>{{$index+1}}</td>
          <td>{{item.column_name}}</td>
          <td style="text-align: left"><span ng-repeat="bar in item.products">{{bar.name}}x{{bar.count}}<i class="fa fa-square-o"></i>, </span></td>
        </tr>
      </tbody>
    </table>
    <hr align="center" width="98%" size="1" noshade class="NOPRINT" ng-if='$index<printdata.length-1'><!--下划线做装饰 -->
    <div class="PageNext" ng-if='$index<printdata.length-1'></div><!--每一个表结束,另起一页打印下一个表-->
  </div>
  <style type="text/css">
  	 .PageNext
  {
      page-break-after: always;
  }
  </style>