创建window

在创建window的时候，需要指定window的⼤⼩。通常window的⼤⼩（frame）与屏幕（UIScreen）⼤⼩⼀致。这里还是使用MRC模式来练习。

重写dealloc方法：

- (void)dealloc
{
    [_window release];
    [super dealloc];
}


创建window时使用autorelease:

self.window = [[[UIWindow alloc] initWithFrame:[[UIScreen mainScreen] bounds]] autorelease];
self.window.backgroundColor = [UIColor whiteColor];
[self.window makeKeyAndVisible];




UIView

代表屏幕上的⼀个矩形区域，iOS中所有能看到的内容都是view或其⼦类。



创建步骤

开辟空间并初始化视图

UIView *view = [[UIView alloc]initWithFrame:CGRectMake(120, 100, 200, 50)];

对视图做一些设置 （比如：背景颜色）

view.backgroundColor = [UIColor yellowColor];

将视图添加到window上进行显示

[self.window addSubview:view];

释放视图对象

[view release];

frame

frame是⼀个结构体，包含2部分内容：origin和size。origin也是⼀个结构体，包含2部分内容：x和y。size同样是⼀个结构体，包含2部分内容：width和height。frame的origin和size是相对于⽗视图来说的。



center

center是个结构体，包含2个部分：x和y。 

center.x = frame.origin.x + frame.size.width/2; 

center.y = frame.origin.y + frame.size.height/2;



bounds

bounds 边界 可以控制子视图的坐标系， 默认的bounds 就是从(0,0)点开始， 改变父视图的bounds 相当于改变子视图的坐标系（也就是原点坐标）， 父视图是不会发生变化，只是更改子视图的位置。

view1.bounds = CGRectMake(10, 10, 100, 30);


（子视图的原点坐标，相对来说向左移10，向上移10。word版自制图片：） 




frame、bounds、center之间的联系









常用方法

insertSubview:atIndex:  

     在指定的index处插⼊⼦视图 

    示例：[superview insertSubview:View atIndex:1];
insertSubview:aboveSubview:  

 在指定的视图上⾯添加⼦视图 

示例：[superview insertSubview:grayView aboveSubview:redView];
insertSubview:belowSubview:  

在指定的视图下⾯添加⼦视图 

示例：[superview insertSubview:grayView belowSubview:redView];
bringSubviewToFront:  

把指定的⼦视图移动到最前⾯ 

示例：[superview bringSubviewToFront:redView];
sendSubviewToBack:  

 把指定的⼦视图移动到最后⾯ 

示例：[superview sendSubviewToBack:redView];
exchangeSubviewAtIndex: withSubviewAtIndex:  

交换两个指定索引位置的⼦视图 

示例：[superview exchangeSubviewAtIndex:0 withSubviewAtIndex:2];
removeFromSuperview  

从⽗视图上移除 

示例：[View removeFromSuperview];
重要属性





UILabel

显⽰⽂本的控件。UILabel是UIView⼦类，是能显⽰⽂字的视图。UILabel是具有特定外观特定功能的视图，侧重于⽂本的呈现。创建过程与UIview相同。

编程：随意输入10个正整数并存入数组a;编程找出数组a中所有的素数，及其下标，并按（下标，素数）格式输出。

#include<stdio.h>
int main()
{
	int isPrime(int data);   //函数声明
	int t,i;
	int a[10] = {0};
    for(i=0;i<10;i++)
	{
		scanf("%d",&a[i]);
	}
	    for(i=0;i<10;i++)
		{
			t=isPrime(a[i]);
			if(t!=-1) //判断是否为素数
			printf("(%d,%d)  ",i,isPrime(a[i]));
		}
   printf("\n");
	return 0;
}

int isPrime(int data)   //函数
{
	int j;
	for(j=2;j<data;j++)
	{
			if(data%j==0)
			break;
	}
		    if(j==data)
				return data;
              else return -1;
		
}

图的邻接表表示及其遍历



1.图的结构定义



#define MAXVEX 100
#define true 1
typedef char VertexType;        //定义图节点值得类型，可随意更换
typedef int EdgeType;           
typedef struct EdgeNode         //定义边表节点
{
    int adjvex;                 //存储顶点下标
    EdgeType weight;            //权重值
    struct EdgeNode* next;      //边指针
}EdgeNode;
typedef struct VertexNode   /*顶点表节点*/
{
    VertexType data;
    EdgeNode* firstedge;
}VertexNode,AdjList[MAXVEX];
typedef struct
{
    AdjList adjList;
    int numVertexes,numEdges;
}GraphAdjList;




2.图的建立



void CreatGraph(GraphAdjList *g)
{
    int i,j,k;
    EdgeNode *e;
    scanf("%d%d",&g->numVertexes,&g->numEdges);//获取顶点数和边数
    char c;
    //gettchar();
    for(i=0;i<g->numVertexes;i++)
    {
        while((c=getchar())=='\n'||c==' ');//排除空格和换行符
        g->adjList[i].data = c;            //获取顶点值，
        g->adjList[i].firstedge = NULL;    //将边表置为空
    }
    for(k=0;k<g->numEdges;k++)
    {
        scanf("%d%d",&i,&j);               //输入i,j 在图中有i-->j
        e=(EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->next = g->adjList[i].firstedge;   //头插法建立边表
        g->adjList[i].firstedge= e;
        /*如果为无向图，则加入以下代码
                e=(EdgeNode*)malloc(sizeof(EdgeNode));
                e->adjvex = i;
                e->next = g->adjList[j].firstedge;
                g->adjList[j].firstedge= e;*/
    }
}



3.图的DFS遍历



void DFS(GraphAdjList *g,int i)
{
        EdgeNode *p;
        visited[i]=true;
        printf("%c ",g->adjList[i].data);
        p = g->adjList[i].firstedge;
        while(p)
        {
                if(visited[p->adjvex]==0)
                        DFS(g,p->adjvex);
                p=p->next;
        }
}

假设有下面这张图，这个图包含两个连通图。



输入如下：



7 6                  <==输入顶点数和边数
a b c d e f g        <==输入顶点值
0 2 0 3 0 1 4 5 1 6 1 2        依次输入边


根据输入，可以得到邻接表如下： 


根据邻接表可知，该图的深度优先遍历如下:



a->b->c->g->d->e->f

程序运行结果： 


证明程序是正确的。 

完整程序代码参见： 
https://github.com/zkangHUST/DataStructure

一些概念（待补充）

·二叉树与度为2的树的区别：二叉树的左右子树严格区分，不能随意交换 

·满二叉树与完全二叉树：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树



二叉树的存储结构与基本操作



1.二叉树的存储结构

二叉链表



struct node{
    typename data;
    node* lchild;
    node* rchild;
};

由于二叉树建树前根结点不存在，因此其地址一般设为NULL：



node* root=NULL;

新建结点（往二叉树中插入结点）



node* newNode(int v){
    node* Node=new node; 
    Node->data=v;
    Node->lchild=Node->rchild=NULL;
    return Node;
}

关于申请node型地址空间，也可用(node* )malloc(sizeof(node)); 【关于malloc和new的区别这个问题对我来说暂且有点高深……



2.二叉树结点的查找、修改

查找操作是指在给定数据域的条件下，在二叉树中找到所有数据域为给定数据域的结点，并将它们的数据域修改为给定的数据域



void search(node* root,int x,int newdata){
    if(root==NULL)     //递归边界
        return;
    if(root->data==x)
        root->data=newdata;
    search(root->lchild,x,newdata);
    search(root->rchild,x,newdata);
}



3.二叉树结点的插入

二叉树结点的插入位置就是数据域在二叉树中查找失败的位置 

此处根结点指针root要使用引用



void insert(node* &root,int x){
    if(root==NULL){
        root=newNode(x);   //新建数据域为x的结点
        return;
    }
    if(??由题意要求的二叉树性质应该插在左子树){
        insert(root->lchild,x);
    }else insert(root->rchild,x);
}



4.二叉树的创建

实质为二叉树结点的插入过程



node* Create(int data[],int n){
    node* root=NULL;
    for(int i=0;i<n;i++){
        insert(root,data[i]);
    }
    return root;
}



5.完全二叉树的存储结构

基于完全二叉树的性质，有更方便的存储方法，可通过建立一个2^n的数组来存放所有结点的信息 

·在1号位存根结点的前提下，对于完全二叉树中的任何一个结点（编号x），其lchild一定为2x，rchild一定为2x+1 

·该数组中元素存放的顺序恰好为该完全二叉树的层序遍历序列 

·判断某个结点是否为叶子结点的标志为：该结点（x)的左子结点编号2x大于结点总个数n 

·判断某个结点是否为空结点的标志为：该结点下标大于结点总个数n



二叉树的遍历



1.先序遍历

对一棵二叉树的先序遍历，序列的第一个一定是根结点



void preorder(node* root){
    if(root==NULL){
        return;
    }
    printf("%d",root->data);    //访问根结点，例如输出数据域
    preorder(root->lchild);
    preorder(root->rchild);
}



2.中序遍历

只要知道根结点，就可以通过根结点在中序遍历序列中的位置区分出左右子树



void inorder(node* root){
    if(root==NULL){
        return；
    }
    inorder(root->lchild);
    printf("%d",root->data);
    inorder(root->rchild);
}



3.后序遍历

对于后序遍历，序列的最后一个一定是根结点



void postorder(node* root){
    if(root==NULL){
        return;
    }
    postorder(root->lchild);
    postorder(root->rchild);
    printf("%d",root->data);
}

无论是先序还是后序，都必须知道中序遍历序列才能唯一地确定一棵树



4.层序遍历

与树的层序遍历同样套路 

若要记录结点层次，则在node结构体中加设layer



struct node{
    int data;
    int layer;
    node* lchild;
    node* rchild;
};



void bfs(node* root){
    queue<node*> q;
    root->layer=1;
    q.push(root);
    while(!q.empty()){
        node* now=q.front();
        q.pop;
        printf("%d",now->data);  //取出队首结点并访问
        if(now->lchild!=NULL){
            now->lchild->layer=now->layer+1;
            q.push(now->lchild);
        }
        if(now->rchild!=NULL){
            now->rchild->layer=now->layer;
            q.push(now->rchild);
        }
    }
}



给定先、中序重建二叉树

（给定先后序同理）



node* create(int preL,int preR,int inL,int inR){
    if(preL>preR) 
        return NULL;
    node* root=new node;
    root->data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++){
        if(in[k]==pre[preL])
            break;
    }
    int numL=k-inL;
    root->lchild=create(preL+1,preL+numL,inL,k-1);
    root->rchild=create(preL+numL+1,preR,k+1,inR);
    return root;
}



二叉树的静态实现



struct node{
    int data,lchild,rchild;    //通常用-1表示子树为空
}Node[maxn];

其他操作相应更改即可~