2017年1月

c数据结构学习

数据的逻辑结构

根据数据元素间的基本特性,有四种基本数据结构

类型特性
集合数据元素间除“同属于同一集合”外,无其他关系
线性结构一个对一个,如线性表,栈,队列
树形结构一个对多个
图状结构多个对多个

线性结构的特点

  • 一对一的关系
  • 除了第一个和最后一个元素外,数据中的每一个元素都有且只有一个直接前驱和一个直接后继

树形结构的特点

  • 一对多的关系
  • 有且只有一个特定的称为根(root)的数据元素(节点)
  • 在树形结构中,树根节点没有前驱元素,其余的每个节点有且只有一个前驱元素。末端元素没有后续的元素,其余的每个元素的后续元素个数可以是一个也可以是多个

图状结构的特点

  • 多对多的关系
  • 任意的两个元素都可能相关,即图中的任一元素可以有若干个直接前驱和直接后继,属于网状结构类型

逻辑结构

表示数据元素之间的抽象关系(如邻接关系,从属关系等),按每个元素可能具有的直接前驱数和直接后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。它是从具体问题中抽象出来的数学模型,是独立于计算机存储器(与机器无关)。


数据的存储结构思想

无论数据的逻辑结构是怎样的,它都需要参与各种运算,那就需要将这些数据元素他原本的逻辑关系进行保存,存储于计算机的存储器中(内存)。存储结构是通过计算机语言所编制的程序来实现的故而是依赖于具体的计算机语言的。

顺序存储

将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中(如c语言的数据)
如表L = (a1,a2,a3...)顺序结构

链式存储

将数据结构中各元素分布到存储器的不同点,用地址(或链指针)方式建立他们之间的联系,由此得到的存储结构为链式存储结构
如表L = (a1,a2,a3...)顺序结构
链式存储结构是数据结构的一个重点,因为数据结构元素的关系在计算机内部很大程序上是通过地址或指针建立的

索引存储

在存储数据的同时,建立一个附加的索引表,即索引存储结构=数据文件+索引表
电话号码查询问题:为便于提高查询速度,在存储用户数据文件的同时,建立一张姓氏索引表

散列存储

散列技术是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。
散列法存储的基本思想是:由节点的关键码决定节点的存储位置。散列技术除了可以用于查找外,还可以用于存储
散列是数组存储方式的一种发展,相比数组,散列的数据访问速度要高于数组,因为可以依据存储数据的部分内容找到数据在数组中的存储位置,进而能够快速实现数据的访问,理想的散列访问速度是非常迅速的。


算法

算法是一个有穷规则(或语句,指令)的有序集合
它确定了解决某一问题的一个运算序列。对于问题的初始输入,通过算法有限步的运行,产生一个或多个输出

算法的特点

  • 有穷性:算法的执行步骤是有限的
  • 确定性:每个计算步骤无二义性
  • 可行性:每个计算步骤能够在有限的时间内完成
  • 输入:算法有一个或多个外部输出
    要说明的是,算法与程序既有联系又有区别。二者都是为了完成某个任务,或解决某个问题而编制的规则(或语句)的有序集合,这是他们的共同点。区别在于:其一,算法与计算机无关,但程序依赖于具体的计算机语言。其二,算法必须是有穷尽的,但程序可能是无穷尽的。其三,算法可能忽略一些语法细节问题,重点放在解决问题的思路上,但程序必须严格遵循相应语言工具的语法。算法转换成程序后才能在计算机上运行。

数据结构是研究从具体问题中抽象出来的数学模型如何在计算机存储器中表示出来;而算法研究的是对数据处理的步骤。如果对问题的数据表示和数据处理都作出了具体的设计,就相当于完成了相应的程序。

算法分析

词句的频度

词句频度定义为可执行语句在算法(或程序)中重复执行的次数,若某语句执行一次时间为t,执行次数为f则该语句所耗时间估计为t*f
示例

float A[n][n],B[n][n],C[n][n];
int j,j,k;
for(i = 0;i < n;i++) // n + 1
{
        for(j = 0;j < n;j++) // n * (n + 1)
        {
                C[n][n] = 0; // n * n
                for(k = 0;k < n;k++) // n * n * (n + 1)
                {
                        C[i][j] = C[i][j] + A[i][j] * C[i][j]; // n * n * n
                }
        }
}

时间复杂度

算法的时间复杂度定义为可执行语句的频度之和,记为T(n)T(n)是算法所需时间的一种估计,其中n为问题的规模(或大小,体积)。

空间复杂度

设算法对应问题的体积(或规模)为n,执行算法所占存储空间的量为D(n),则D(n)为算法的空间复杂度

算法效能度量

  • 算法效率:用依据该算法编制的程序在计算机上执行所消耗的时间来度量。用字母“O”表示其数量级的概念
  • 算法中基本操作重复执行的次数是问题规模n的某个函数f(n)

线性表

  • 定义:线性表是信息表的一种形式,表中数据元素之间满足线性逻辑关系(或线性结构),是一种最基本,最简单的数据结构类型
  • 线性表(Linear List)是包含若干数据元素的一个线性序列,记为:L=(a0,...ai-1,ai,ai+1,...an-1)

    • 其中:L为表面,ai(0 <= i <= n-1)为数据元素,n为表长,n大于0时,线性表L为非空表,否则为空表。线性表L可用二元组形式描述:L=(D,R)
    • 即线性表L包含数据元素集合D和关系集合R。
  • 线性表的特征:对非空表,a0是表头,无前驱;an-1是表尾,无后继;其他元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)
  • 运算:设线性表L=(a0,a1,...an-1)

    • 建立一个空表:CreateList(L);
    • 置空表:ClearList(L);
    • 判断表是否为空:EmptyList(L);,如表为空,返回true,否则返回false
    • 求表长:LengthList(L);
    • 取表中某个元素:GetList(L,i);,即ai。要求0 <= i <= length(L) - 1
    • 定位运算:LocateList(L,x);,确定元素x在表L中的位置(或序号)
    • 插入:InsertList(L,x,i);,将元素x插入表L中的第i个元素ai之前,切表长加1
    • 删除:DeleteList(L,i);删除表L中第i个元素ai,且表长减1,要求0 <= i <= n-1
    • 其他:合并,拆分,复制,排序,遍历等

线性表的存储

线性表作为一种基本数据类型结构,在计算机存储器中的映像(或表示)一般有两种形式,一种是顺序映像,一个是链式映像
线性表的存储结构

  • 若将线性表中的各元素依次存储于计算机一片连续的空间。这种为线性表的顺序存储结构。

    • 逻辑上相邻的元素,存储位置上也是相邻的
    • 对数据元素ai的存取为随机存取或按地址存取
    • 存储密度高。存储密度D=(数据结构中元素所占的存储空间)/(整个数据结构所占空间)
  • 顺序存储结构的不足

    • 对表的插入和删除等运算的时间复杂度较差
      子c语言中,一维数组的元素也是存放在一片连续的存储空间中,故可借助c语言中一维数组类型来描述线性表的顺序存储结构,即
#define MAX               // 线性表的最大长度
typedef struct{           // 表的类型
    datatype data[MAX];   // 表的存储空间
    int last;             // 当前表尾指针
}sqlist;*sqlink;          // 表说明符

如说明sqlink L;L = (sqlink)malloc(sizeof(sqlist))
关于线性表的运算,有些实现起来是相当简单的

  • 置空表

    • ClearList(L),令L->last=-1
  • 取表元素

    • GetList(L,i),取L->data[i]的值
  • 求表长

    • Length(L),取L->last之值加1即可
      示例
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "01_lib.h"
#define MAX 20
typedef struct{
        int data[MAX];
        int last;
}sqlist;
typedef sqlist* sqlink;
sqlink CreateList(void)
{       
        sqlink l = (sqlink)realloc(NULL,sizeof(sqlist));
        l->last = -1;
        memset(l->data,0,MAX);
        return l;
}
int Length(sqlink L)
{       
        return L->last + 1;
}
void ClearList(sqlink L)
{       
        free(L);
}
int EmptyList(sqlink L)
{       
        return L->last == -1;
}
int FullList(sqlink L)
{       
        return L->last == (MAX - 1);
}
int GetList(sqlink L,int index)
{       
        if(index >= 1 || index <= (L->last + 1))
        {       
                return L->data[index - 1];
        }
        return -1;
}
int LocateList(sqlink L,int value)
{       
        if(EmptyList(L))
        {       
                return -1;
        }
        for(int i = 0;i <= L->last;i++)
        {       
                if(L->data[i] == value)
                {       
                        return i + 1;
                }
        }
        return -1;
}
void InsertList(sqlink L,int value,int index)
{       
        if(EmptyList(L) || FullList(L) || index - 1 > L->last)
        {       
                return;
        }
        for(int i = index - 1;i <= L->last;i++)
        {       
                L->data[i + 1] = L->data[i];
        }
        L->data[index - 1] = value;
        L->last++;
}
void DeleteList(sqlink L,int index)
{
        if(EmptyList(L) || FullList(L) || index - 1 > L->last)
        {   
                return;
        }   
        for(int i = index - 1;i < L->last;i++)
        {   
                L->data[i] = L->data[i + 1]; 
        }   
        L->last--;
}
void PushList(sqlink L,int value)
{
        if(FullList(L))
        {   
                return;
        }   
        L->data[++L->last] = value;

}
void PrintList(sqlink L)
{
        for(int i = 0;i <= L->last;i++)
        {   
                printf("data[%d] = %d\n",i,L->data[i]);
        }   
}

单向链表

将线性链表L=(a<sub>0</sub>,a<sub>1</sub>,...,a<sub>n-1</sub>)中各元素分布在存储器的不同存储块,称为节点,通过地址或指针建立他们之间的联系,所得到的存储结构为链表结构

  • 其中元素ai的节点有由datanext两部分组成
  • 其中,节点的data域存放元素ai,而next域是一个指针,指向ai的直接后继ai + 1所在的节点。于是,线性表L=(a0,a1,...,an-1)的结构
  • 示例
#include "03_lib.h"
#include <malloc.h>
int empty(sqlink* L)
{       
        if(*L == NULL)
        {       
                return 0;
        }
        return 1;
}
sqlink* CreateList(void)
{       
        sqlink* L = (sqlink*)malloc(sizeof(sqlink));
        *L = NULL;
        return L;
}
int Length(sqlink* L)
{       
        if(empty(L) == 0)
        {       
                return 0;
        }
        int length = 0;
        sqlink l = *L;
        while(l->next != NULL)
        {       
                length++;
        }
        return length;
}
void freeList(sqlink L)
{
        if(L->next != NULL)
        {
                freeList(L->next);
        }
        free(L);
}
void ClearList(sqlink* L)
{
        if(empty(L) == 0)
        {
                return;
        }
        freeList(*L);
}
int GetList(sqlink* L,int index)
{
        if(empty(L) == 0)
        {
                return -1;
        }
        index--;
        int i = 0;
        sqlink l = *L;
        while(l->next != NULL)
        {
                if(i == index)
                {
                        return l->data;
                }
                l = l->next;
                i++;
        }
        return -1;
}
int LocateList(sqlink* L,int value)
{
        if(empty(L) == 0)
        {
                return -1;
        }
        int i = 1;
        sqlink l = *L;
        while(l->next != NULL);
        {
                if(l->data == value)
                {
                        return i;
                }
                i++;
        }
        return -1;
}
void PushList(sqlink* L,int value)
{
        if(empty(L) == 0)
        {
                *L = (sqlink)malloc(sizeof(sqlist));
                (*L)->data = value;
                (*L)->next = NULL;
                return;
        }
        sqlink l = *L;
        while(1)
        {
                if(l->next == NULL)
                {
                        l->next = (sqlink)malloc(sizeof(sqlist));
                        l->next->data = value;
                        l->next->next = NULL;
                        return;
                }
                l = l->next;
        }
}
void InsertList(sqlink* L,int value,int index)
{
        sqlink l = NULL;
        if(index == 1)
        {
                l = (sqlink)malloc(sizeof(sqlist));
                l->data = value;
                l->next = *L;
                *L = l;
                return;
        }
        int i = 1;
        sqlink l1 = *L;
        do{
                if(index == (i + 1))
                {
                        l = (sqlink)malloc(sizeof(sqlist));
                        l->data = value;
                        l->next = l1->next;
                        l1->next = l;
                        return;
                }
                i++;
                l1 = l1->next;
        }
        while(l1->next != NULL);
}
void DeleteList(sqlink* L,int index)
{
        if(empty(L) == 0)
        {
                return;
        }
        sqlink l = NULL;
        if(index == 1)
        {
                l = (*L)->next;
                free(*L);
                *L = l;
                return;
        }
        l = *L;
        int i = 1;
        while(l->next != NULL)
        {
                if(i == (index - 1))
                {
                        sqlink temp = l->next->next;
                        free(l->next);
                        l->next = temp;
                }
                i++;
        }
}
void PrintList(sqlink* L)
{
        if(empty(L) == 0)
        {
                return;
        }
        sqlink l = *L;
        int i = 1;
        do
        {
                printf("data[%d] = %d\n",i,l->data);
                l = l->next;
                i++;
        }
        while(l != NULL);
}
void reverse(sqlink* L)
{
        if(empty(L) == 0)
        {
                return;
        }
        sqlink l = *L,reverse = NULL,last = *L,temp;
        do{
                temp = l;
                l = l->next;
                if(reverse == NULL)
                {
                        reverse = temp;
                }
                else
                {
                        temp->next = reverse;
                        reverse = temp;
                }
        }
        while(l != NULL);
        *L = reverse;
        last->next = NULL;
}
void merge(sqlink * L_left,sqlink * L_right)
{
        if(empty(L_left) == 0 || empty(L_right) == 0)
        {
                return;
        }
        sqlink l = *L_left;
        while(l != NULL)
        {
                if(l->next == NULL)
                {
                        l->next = *L_right;
                }
                l = l->next;
        }
        *L_right = *L_left;
}
  • 约瑟夫环
#include <stdio.h>
#include <malloc.h>
struct node
{       
        int data;
        struct node* pre;
        struct node* next;
};
void Joseph_problem(int i,int j,int k);
int main(void)
{       
        Joseph_problem(7,2,3);
        return 0;
}
void Joseph_problem(int i,int j,int k)
{
        struct node* L = NULL,* l = NULL;
        int a = 1;
        for(;a <= i;a++)
        {
                if(L == NULL)
                {
                        L = (struct node*)malloc(sizeof(struct node));
                        L->data = a;
                        l = L;
                }
                else
                {
                        l->next = (struct node*)malloc(sizeof(struct node));
                        l->next->data = a;
                        l->next->pre = l;
                        l = l->next;
                }
        }
        L->pre = l;
        l->next = L;
        l = L;
        for(a = 1;a <= j;a++)
        {
                l = l->next;
        }
        a = 1;
        struct node* temp;
        while(L->next != L)
        {
                if(k == a)
                {
                        temp = L->next;
                        L->next = L->next->next;
                        L->next->pre = L;
                        printf("%d\n",temp->data);
                        free(temp);
                        a = 1;
                }
                else
                {
                        a++;
                }
                L = L->next;
        }
        printf("%d\n",L->data);
        free(L);
}

  • 定义:栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈),允许操作的一端称为栈顶,另一端固定称为栈底,当栈中没有元素时称为空栈。
  • 特点:后进先出
  • 由于栈也是线性逻辑结构,因此线性表的存储结构对栈也适用,通常栈有顺序链和链栈两种存储结构,这两种存储结构的不同,则实现栈的基本运算的算法也不同。
  • 运算:设S=(a0,a1,...,an-1)

    • 构造空栈:InitStack(S);
    • 设置空栈:SetEmpty(S);
    • 判断是否是空栈:IsEmpty(S);
    • 元素进栈:StackPush(S,x);,可形象的理解为压入,这时栈中会多一个元素
    • 元素出栈:StackPop(S);,可形象的理解为弹出,弹出后栈中就无此元素了
    • 读取栈顶元素:ShowTop(S);,不同与弹出,只是使用栈顶元素的值,该元素仍在栈顶不会改变
  • 顺序存储
typedef struct node{
        int* data;
        int top;
} node,* nodep;
nodep InitStack(void)
{
        nodep p = malloc(sizeof(node));
        p->top = -1;
        p->data = NULL;
        return p;
}
void SetEmpty(nodep p)
{
        free(p->data);
        p->top = -1;
        p->data = NULL;
}
int IsEmpty(nodep p)
{
        if(p->top == -1)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}
void StackPush(nodep p,int data)
{
        p->data = realloc(p->data,sizeof(int) * (++p->top + 1));
        p->data[p->top] = data;
}
int StackPop(nodep p)
{
        if(1 == IsEmpty(p))
        {
                return 0;
        }
        int data = ShowTop(p);
        p->data = realloc(p->data,sizeof(int) * p->top--);
        if(p->top == -1)
        {
                p->data = NULL;
        }
        return data;
}
int ShowTop(nodep p)
{
        if(1 == IsEmpty(p))
        {
                return 0;
        }
        return p->data[p->top];
}
  • 链表存储
typedef struct node{
        int data;
        struct node* next;
} node,* nodep;
nodep* InitStack(void)
{
        nodep* p = (nodep*)malloc(sizeof(nodep));
        *p = NULL;
        return p;
}
void freeNode(nodep p)
{
        if(p->next != NULL)
        {
                freeNode(p->next);
        }
        free(p);
}
void SetEmpty(nodep* p)
{
        if(IsEmpty(p) == 1)
        {
                return;
        }
        freeNode(*p);
}
int IsEmpty(nodep* p)
{
        if(*p == NULL)
        {
                return 1;
        }
        return 0;
}
void StackPush(nodep* p,int data)
{
        nodep temp = (nodep)malloc(sizeof(node));
        temp->data = data;
        temp->next = *p;
        *p = temp;
}
int StackPop(nodep* p)
{
        if(IsEmpty(p) == 1)
        {
                return 0;
        }
        int data = (*p)->data;
        nodep temp = *p;
        *p = (*p)->next;
        free(temp);
        return data;
}
int ShowTop(nodep* p)
{
        if(IsEmpty(p) == 1)
        {
                return 0;
        }
        return (*p)->data;

队列

  • 定义:队列也是一种运算受限的线性表,它的运算限制与栈不同,是两头都有限制,插入只能在表的一端进行(只进不出),而删除只能在表的另一端进行(只出不进),允许删除的一端成为队头(Front),允许插入的一端称为队尾(rear),当线性表中没有队尾时,称为空队。
  • 特点:先进先出
  • 常用基本运算

    • 置空队:SetEmpty(Q);
    • 判断空队:IsEmpty(Q);
    • 判断满队:IsFull(Q);
    • 入队:PushQueue(Q,x)
    • 出队:OutQueue(Q);
    • 取队头:ShowFront(Q);

队列顺序存储结构

顺序队列是线性逻辑结构顺序存储的一种,具有和顺序表一样的存储结构,由数组定义,配合用数组下标表示的对头指针和队尾指针(相对指针)完成各种操作

  • 规定:头指针front总是指向队头元素的第一个位置,尾指针rear总是指向队尾元素所在位置的下一个位置
  • 在队列操作过程中,为了提高效率,以调整指针代替队列元素的移动,并将数组作为循环队列的操作空间
  • 为区别空队和满队,尾指针rear指向的位置必须为空,满队元素个数比数组元素个数少一个。
  • 实例
typedef struct queue
{
        int data[MAX_SIZE];
        int front;
        int rear;
}queue,* queuep;
queuep InitQueue(void)
{
        queuep q = (queuep)malloc(sizeof(queue));
        SetEmpty(q);
        return q;
}
int IsEmpty(queuep q)
{
        return (q->front == q->rear) ? 1 : 0;
}
void SetEmpty(queuep q)
{
        q->front = 0;
        q->rear = 0;
}
int IsFull(queuep q)
{
        return (((q->rear + 1) % MAX_SIZE) == q->front) ? 1 : 0;
}
void PushQueue(queuep q,int v)
{
        if(IsFull(q) == 1)
        {
                return;
        }
        q->data[q->rear] = v;
        q->rear = (q->rear + 1) % MAX_SIZE;
}
int OutQueue(queuep q)
{
        if(IsEmpty(q) == 1)
        {
                return -1;
        }
        int temp = q->data[q->front];
        q->front = (q->front + 1) % MAX_SIZE;
        return temp;
}
int ShowFront(queuep q)
{
        if(IsEmpty(q) == 1)
        {
                return -1;
        }
        return q->data[q->front];
}

链式存储

  • 在c语言中,不能用静态分配的一维数组来实现循环队列,若使用循环队列,必须设置最大队列长度,若无法估计最大长度,就使用链式队列。
  • 插入操作在队尾进行,删除操作在队头进行,由队头指针和队尾指针控制队列的操作
typedef struct node
{
        int data;
        struct node* next;
}node,* nodep;
typedef struct queue
{
        nodep front;
        nodep rear;
}queue,* queuep;
queuep InitQueue(void)
{
        queuep q = (queuep)malloc(sizeof(queue));
        q->front = NULL;
        q->rear = NULL;
        return q;
}
int IsEmpty(queuep q)
{
        return (q->front == NULL) ? 1 : 0;
}
void SetEmpty(queuep q)
{
        nodep n = q->front,temp = NULL;
        while(n != NULL)
        {
                temp = n;
                n = n->next;
                free(temp);
        }
        q->front = NULL;
        q->rear = NULL;
}
int IsFull(queuep q)
{
        return 0;
}
void PushQueue(queuep q,int v)
{
        if(q->rear == NULL)
        {
                q->rear = (nodep)malloc(sizeof(node));
                q->front = q->rear;
                q->rear->next = NULL;
        }
        else
        {
                q->rear->next = (nodep)malloc(sizeof(node));
                q->rear->next->next = NULL;
                q->rear = q->rear->next;
        }
        q->rear->data = v;
}
int OutQueue(queuep q)
{
        if(IsEmpty(q) == 1)
        {
                return -1;
        }
        int n = q->front->data;
        nodep temp = q->front;
        q->front = q->front->next;
        if(q->front == NULL)
        {
                q->rear = NULL;
        }
        free(temp);
        return n;
}
int ShowFront(queuep q)
{
        if(IsEmpty(q) == 1)
        {
                return -1;
        }
        return q->front->data;
}

  • 树(Tree)是n(n>=0)个节点的有限集合,可记为T,满足两个条件

    • 有且只有一个特定的称为根(Root)的节点
    • 其余的节点可以分为m(m>=0)个互不相交的有限集合T1,T2...Tm,其中每一个集合又是一个树并称为其根的子树
  • 表示方法:树形表示法,目录表示法
  • 特点:仅有一个根节点,节点间有明显的层次关系

树的基本术语

  • 一个节点的子树的个数称为该节点的度数,一棵树的度数是指该树中节点的最大度数
  • 度数为0的节点称为树叶或终端节点,度数不为0的节点称为分支节点,除根节点之外的节点称为内部节点
  • 一个节点的子树的节点称为该节点的子节点,该节点称为他们的父节点,同一节点的各个子节点之间称为兄弟节点。一个数的根节点没有父节点,叶节点没有子节点
  • 节点的层数等于父节点的层数加1,根节点的层数定义为1。树中节点层数的最大值称为该树的高度或深度
  • 一个节点k1,k2,...ki,ki+1,...,kj并满足ki是ki+1的父节点,就称为一条从k1到kj的路径,路径的长度为j-1,即路径的边数。路径总前面的节点是后面的节点的祖先,后面节点是前面节点的子孙
  • 若树中每个节点的各个子树的排列为从左到右,不能交换,即兄弟之间是有序的,则称该树为有序树,一般的树是有序树
  • m(m>=0)颗互不相交的树的集合,称为森林。树去掉根节点就成为森林,森林加上一个新的根节点就称为树

树的逻辑结构

树中任何节点都可以有零个或多个直接后继节点(子节点),但至多只有一个直接前驱节点(父节点),根节点没有前驱结点,叶节点没有后继节点。

树的存储结构

树的存储结构可以采用具有多个指针域的多重链表,节点中指针域的个数应由树的度来决定。在实际应用中,这种存储结构很不方便,一般将树转化为二叉树表示法进行处理

二叉树

  • 二叉树是一种重要的树形结构。是由n(n>=0)个节点组成的有限集合,他或者是空集(n=0),或者是由一个根节点以及两颗互不相交的,分别称为左子树和右子树的二叉树组成
  • 二叉树与普通有序树不同,二叉树严格区分左孩子和右孩子,即使只有一个子节点也要区分左右,左右次序不能颠倒。
  • 基本形态:

    • 要点:二叉树结点的子树要区分左子树和右子树,即使在节点只有一棵子树的情况下也要明确的指出该子树是左子树还是右子树
  • 二叉树的性质

    • 二叉树第i(i>=1)层上的节点最多2i-1
    • 深度为k(k>=1)的二叉树最多有2k-1个节点
    • 在任意一颗二叉树中,叶子数(度数为0)=度数为2的节点数 + 1
  • 二叉树的形式

    • 满二叉树:深度为k(k>=1)且有2k-1个节点的二叉树
    • 完全二叉树:只有最下面两层有度数小于2的节点,且最下面一层的叶节点集中在最左边的若干位置上。

      • 具有n个节点的完全二叉树的深度为(log2n)+1或log2(n+1)

二叉树存储结构

  • 顺序存储结构

    • 完全二叉树节点的编号方法是从上到下,从左到右,根节点为一号节点
    • 有n个节点的完全二叉树可以用有n+1个元素的数组进行顺序存储,节点号和数组下标一一对应,下表为0的元素不用
    • 利用以上特性,可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚结点构成完全二叉树,然后用数组存储,还要浪费一些存储空间
    • 一般二叉树必须转换成完全二叉树的形式存储,将造成存储的浪费
    • 若父节点在数组中i下标处,其左孩子在2i处,右孩子在2i-1处
  • 链式存储结构

    • 每个节点由数据域,左指针域和右指针域组成
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchilde,*rchild;
}BiTNode,* BiTree;

二叉树遍历

  • 沿着某条搜索路径周游二叉树,对树中的每一个节点访问一次且仅访问一次
  • 是任何类型均有的操作,对线性结构而言,只有一条搜索路径(因为每个节点均只有一个后继),故不需要另加讨论。而二叉树是非线性结构,每个节点有两个后继,则存在如何遍历即按什么样的搜索路径进行遍历的问题。
  • 查找某个节点,或对二叉树中全部节点进行某种处理,就需要遍历
  • 由于二叉树的递归性质,遍历算法将采用递归方式
  • 三种基本的遍历方法如下

    • 先上(根)后下(子树)的按层次遍历
    • 先左(子树)后(子树)的遍历
    • 先右(子树)后左(子树)的遍历
  • 遍历的算法

    • 前序遍历(D L R)

      • 访问跟节点,按先序遍历左子树,按先序访问右子树
    • 中序遍历(L D R)

      • 按中序遍历左子树,访问根节点,按中序遍历右子树
    • 后序遍历(L R D)

      • 按后序遍历左子树,按后序遍历右子树,访问根节点
      • 二叉树为空时,执行空操作,即空二叉树已遍历完
  • 实例
typedef struct BiTNode{
        int data;
        struct BiTNode *l,*r;
}BiTNode,* BiTree;
BiTree create(void)
{
        BiTree tree = NULL;
        char c;
        if((c = fgetc(stdin)) != '#' && c != '\n')
        {
                tree = (BiTree)malloc(sizeof(BiTNode));
                tree->data = c;
                tree->l = create();
                tree->r = create();
        }
        return tree;
}
// 前序
void PerOrder(BiTree tree)
{
        printf("%c",tree->data);
        if(tree->l != NULL)
        {
                PerOrder(tree->l);
        }
        if(tree->r != NULL)
        {
                PerOrder(tree->r);
        }
}
// 中序
void InOrder(BiTree tree)
{
        if(tree->l != NULL)
        {
                InOrder(tree->l);
        }
        printf("%c",tree->data);
        if(tree->r != NULL)
        {
                InOrder(tree->r);
        }
}
// 后序
void PostOrder(BiTree tree)
{
        if(tree->l != NULL)
        {
                PostOrder(tree->l);
        }
        if(tree->r != NULL)
        {
                PostOrder(tree->r);
        }
        printf("%c",tree->data);
}

排序

  • 将无序的记录序列调整成有序的序列
  • 对记录进行排序有着重要的意义。如果记录按key有序,可对其折半查找,使查找效率提高;在数据库(Data Base)和文件库(File Base)等系统中,一般要建立若干索引文件(记录),就涉及到排序问题;在一些计算机的应用系统中,要按不同的数据做出若干统计,也涉及到排序。排序效率的高低,直接影响到计算机的工作效率。
  • 设有n个记录文件f=(R1,R2,...,Rn),相应记录关键字(key)集合k={k1,k2,...,kn},若对1,2,3,...,n的一种排列
    P(1) P2 P3 (1 <= P(i) <= n,i!=j时,Pi!=Pj)

有:KP(1) <= KP(2) <= ... <= KP(n) 递增
有:KP(1) >= KP(2) >= ... >= KP(n) 递减
则使f按key线性有序:(Rp(1) Rp(2) ... Rp(n)),称这种运算为排序(或分类),关系符"<="和">="并不一定是数学意义上的"小于等于"或者"大于等于",而是一种次序关系。但为了讨论问题方便,取整型数作为key,故"<="和">="可以看作通常意义上的符号

  • 稳定排序和非稳定排序
    设文件f=(R1,R2,...,Ri,...,Rj,...,Rn)中记录Ri Rj(i!=j,i=1...n)的key相等,即Ri=Rj,若在排序前Ri领先于Rj,排序后Ri仍领先于Rj,则称这种排序是稳定的,其含义是没有破坏原本已有序的次序。反之,若排序后Ri和Rj的次序有可能颠倒,则这种排序是非稳定的,即他有可能破坏了原本以有序记录的次序
  • 内排序和外排序
    若待排文件f在计算机的内部存储器中,且排序过程也在内存中进行,称这种排序为内排序,内排序速度快,但由于内存容量一般很小,文件的长度(记录个数)n受到一定限制。若排序中的文件存入外存储器,排序过程借助于内外数据交换(或归并)来完成,则称这种排序为外排序
  • 内排序的分类

    • 交换法排序

      • 冒泡排序
      • 快速排序
    • 插入法排序

      • 直插排序
    • 选择法排序
    • 归并法排序
  • 排序的对象

    • 顺序结构:类似线性表的顺序存储,将文件f=(R1,R2,...,Rn)存于一片连续的存储空间,逻辑上相连的存储记录在存储器中的物理位置也是相邻的,在这种结构上对文件进行排序,一般要作记录的移动。当发生成片记录移动时,是一个非常耗时的工作
    • 链表结构:类似于线性表的链式存储,文件中记录用节点来表示,其物理位置随意,节点之间用指针相连,链表的优点在于排序时无需移动记录,只需修改相应记录的指针即可
  • 交换法-冒泡排序
    外层循环决
void sort1(sqlink* L)
{
        int length = Length(L);
        sqlink i_temp = NULL;
        for(int i = 0;i < length - 1;i++)
        {
                i_temp = *L;
                // while(l->next != NULL)
                for(int j = 0;j < length - i - 1;j++)
                {       
                        //printf("%d\n",j);
                        if(i_temp->data < i_temp->next->data)
                        {       
                                if(i_temp->pre != NULL)
                                {
                                        i_temp->pre->next = i_temp->next;
                                }
                                if(i_temp->next->next != NULL)
                                {
                                        i_temp->next->next->pre = i_temp;
                                }
                                i_temp->pre = i_temp->next;
                                i_temp->next = i_temp->next->next;
                                if(i_temp->pre != NULL)
                                {
                                        i_temp->pre->next = i_temp;
                                }
                                if(j == 0)
                                {
                                        *L = i_temp->pre;
                                }       
                        }       
                        else    
                        {
                                i_temp = i_temp->next;
                        }       
                }       
        }       
}
  • 交换法-快速排序
    对冒泡排序的一种改进,目的是提高排序的效率

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

  • 示例
void sort2(sqlink* L,sqlink left,sqlink right)
{
        sqlink key,left_copy = left,right_copy = right;
        int flag_left = 1,flag_right = 1;
        while(left != right)
        {
                while(left != right)
                {
                        if(left->data > right->data)
                        {
                                swapSqlink(L,left,right);
                                key = left;
                                left = right;
                                right = key;
                                if(flag_left == 1)
                                {
                                        left_copy = left;
                                        if(flag_right == 1)
                                        {
                                                right_copy = right;
                                        }
                                }
                                break;
                        }
                        else
                        {
                                flag_right++;
                                right = right->pre;
                        }
                }
                while(left != right)
                {
                        if(left->data > right->data)
                        {
                                swapSqlink(L,left,right);
                                key = left;
                                left = right;
                                right = key;
                                if(flag_right == 1)
                                {
                                        right_copy = right;
                                }
                                break;
                        }
                        else
                        {
                                flag_left++;
                                left = left->next;
                        }
                }
        }
        // printf("\nleft_copy %d; address = %p\n",left_copy->data,left_copy);
        // printf("right_copy %d; address = %p\n",right_copy->data,right_copy);
        // printf("right %d; address = %p\n",right->data,right);
        // printf("left %d; address = %p\n",left->data,left);
        //printf("left->pre %d; address = %p\n",left->pre->data,left->pre);
        if(left_copy != left->pre && left->pre != NULL && left != left_copy)
        {
                sort2(L,left_copy,left->pre);
        }
// printf("start %d; address = %p\n",left->data,left);
        if(right_copy != right->next && right->next != NULL && right != right_copy)
        {
                sort2(L,right->next,right_copy);
        }
        // printf("end\n");
        // return left;
}
void swapSqlink(sqlink* L,sqlink left,sqlink right)
{
        // PrintList(L);
        // printf("\tstart %d %d\n",left->data,right->data);
        if(left->pre == NULL)
        {
                *L = right;
        }
        if(left->next == right)
        {
                if(left->pre != NULL)
                {
                        left->pre->next = right;
                }
                if(right->next != NULL)
                {
                        right->next->pre = left;
                }
                left->next = right->next;
                right->pre = left->pre;
                left->pre = right;
                right->next = left;
        }
        else
        {
                sqlink ll = left->pre,lr = left->next,rl = right->pre,rr = right->next;
                if(ll != NULL)
                {
                        ll->next = right;
                }
                // printf("\tyyy %d %d\n",left->data,right->data);
                lr->pre = right;
                right->pre = ll;
                right->next = lr;
                if(rr != NULL)
                {
                        rr->pre = left;
                }
                rl->next = left;
                left->pre = rl;
                left->next = rr;
        }
        // printf("\tend %d %d\n",left->data,right->data);
}
  • 插入法-直插排序
Last login: Sat Feb  4 08:55:01 2017 from 192.168.1.62
-bash-4.1$ pwd
/home/jin
-bash-4.1$ cd c_test/
-bash-4.1$ cd 19_algorithm/
-bash-4.1$ 



























-bash-4.1$ ls
bin  include  obj  src
-bash-4.1$ vim src/
01.c      02.c      03_lib.c  05.c      06.c      07.c      08_lib.c  09_lib.c  10_lib.c  11_lib.c  12_lib.c  
01_lib.c  03.c      04.c      05_lib.c  06_lib.c  08.c      09.c      10.c      11.c      12.c      
-bash-4.1$ vim src/.
./  ../ 
-bash-4.1$ vim src/12
12.c      12_lib.c  
-bash-4.1$ vim src/12.c 
-bash-4.1$ vim src/12.c 






















                                {
                                        new_l_copy->pre->next = old_l;
                                }       
                                else    
                                {
                                        new_l = old_l;
                                        old_l->pre = NULL;
                                }       
                                new_l_copy->pre = old_l;
                                old_l->next = new_l_copy;
                                new_l_copy = new_l;
                                break;
                        }       
                        else if(new_l_copy->next == NULL)
                        {
                                new_l_copy->next = old_l;
                                old_l->next = NULL;
                                old_l->pre = new_l_copy;
                                new_l_copy = new_l;
                                break;
                        }       
                        new_l_copy = new_l_copy->next;
                }       
                old_l = *l;
        }       
        *l = new_l;
}
  • 以上案例是基于如下链表的
typedef struct node{
        int data;
        struct node* next;
        struct node* pre;
}sqlist,*sqlink;
int empty(sqlink* L)
{       
        if(*L == NULL)
        {       
                return 0;
        }
        return 1;
}
sqlink* CreateList(void)
{
        sqlink* L = (sqlink*)malloc(sizeof(sqlink));
        *L = NULL;
        return L;
}
int Length(sqlink* L)
{
        if(empty(L) == 0)
        {
                return 0;
        }
        int length = 0;
        sqlink l = *L;
        while(l != NULL)
        {
                l = l->next;
                length++;
        }
        return length;
}
void freeList(sqlink L)
{
        if(L->next != NULL)
        {
                freeList(L->next);
        }
        free(L);
}
void ClearList(sqlink* L)
{
        if(empty(L) == 0)
        {
                return;
        }
        freeList(*L);
}
sqlink GetList(sqlink* L,int index)
{
        if(empty(L) == 0)
        {
                return NULL;
        }
        index--;
        int i = 0;
        sqlink l = *L;
        while(l->next != NULL)
        {
                if(i == index)
                {
                        return l;
                }
                l = l->next;
                i++;
        }
        return NULL;
}
int LocateList(sqlink* L,int value)
{
        if(empty(L) == 0)
        {
                return -1;
        }
        int i = 1;
        sqlink l = *L;
        while(l->next != NULL);
        {
                if(l->data == value)
                {
                        return i;
                }
                i++;
        }
        return -1;
}
void PushList(sqlink* L,int value)
{
        if(empty(L) == 0)
        {
                *L = (sqlink)malloc(sizeof(sqlist));
                (*L)->data = value;
                (*L)->next = NULL;
                (*L)->pre = NULL;
                return;
        }
        sqlink l = *L;
        while(1)
        {
                if(l->next == NULL)
                {
                        l->next = (sqlink)malloc(sizeof(sqlist));
                        l->next->data = value;
                        l->next->next = NULL;
                        l->next->pre = l;
                        return;
                }
                l = l->next;
        }
}
void InsertList(sqlink* L,int value,int index)
{
        if(empty(L) == 0 || index > Length(L))
        {
                return;
        }
        sqlink l = NULL;
        if(index == 1)
        {
                l = (sqlink)malloc(sizeof(sqlist));
                l->data = value;
                l->next = *L;
                (*L)->pre = l;
                *L = l;
                return;
        }
        int i = 1;
        sqlink l1 = *L;
        do{
                if(index == i)
                {
                        l = (sqlink)malloc(sizeof(sqlist));
                        l->data = value;
                        l->pre = l1->pre;
                        l->next = l1;
                        l->next->pre = l;
                        l->pre->next = l;
                        return;
                }
                i++;
                l1 = l1->next;
}
        while(l1 != NULL);
}
void DeleteList(sqlink* L,int index)
{
        if(empty(L) == 0)
        {
                return;
        }
        sqlink l = NULL;
        if(index == 1)
        {
                l = (*L)->next;
                free(*L);
                *L = l;
                return;
        }
        l = *L;
        int i = 1;
        while(l->next != NULL)
        {
                if(i == (index - 1))
                {
                        sqlink temp = l->next->next;
                        free(l->next);
                        l->next = temp;
                }
                i++;
        }
}
void PrintList(sqlink* L)
{
        if(empty(L) == 0)
        {
                return;
        }
        sqlink l = *L;
        int i = 1;
        do
        {
                printf("data[%d] = %d\n",i,l->data);
                l = l->next;
                i++;
        }
        while(l != NULL);
}

查找

  • 顺序查找,就是遍历链表,就不写了
  • 二分查找
int BinSearch(sqlink l,int value,int length)
{
        int left = 0,right = length,mid = (left + right) / 2,i;
        sqlink l_copy = l;
        while(left <= right)
        {
                mid = (left + right) / 2;
                l_copy = l;
                for(i = 0;i < mid;i++)
                {
                        l_copy = l_copy->next;
                }
                // printf("%d\n",l_copy->data);
                if(l_copy->data > value)
                {
                        left = mid + 1;
                }
                else if(l_copy->data < value)
                {
                        right = mid - 1;
                }
                else
                {
                        return 1;
                }
        }
        return -1;
}
  • 哈希表

    • 又称散列表,杂凑表。在前面讨论的顺序,拆半,分块查找和树表的查找中,其ASL的量级都在O(n)~O(log2n)之间。不论ASL是哪个量级,都与记录长度n有关,随着n的扩大,算法的效率会越来越低。ASL与n有关是因为存储在存储器中的存放是随机的,或者说记录的key与记录的存放地址无关,因而查找只能建立在key的比较基础上。
    • 理想的查找是:对给定的k,不经任何比较便能获取所需记录,其查找时间复杂度为常数级O(C)。这叫要求在建立记录表的时候,确定记录的key与其存储地址之间的关系f,即使key与记录的存放地址H相对应
    • 或者说记录按key存放
    • 之后,当要查找key=k的记录时,通过关系f就可得到响应记录的地址儿获取记录了,从而免去了key的比较过程。这个关系f就是所谓的哈希函数(或称散列函数,杂凑函数),记为H(key)。它实际上是一个地址映像函数,其自变量为记录的key,函数值为记录的存储地址(或称Hash地址)
    • 另外,不同的key可能得到同一个Hash地址,即当key1 != key2时,可能会有H(key1)=H(key2),此时称key1和key2为同义词。这种现象称为冲突或碰撞,因为一个数据单位只可存放一条记录。
    • 一般,选取Hash函数只能做到使冲突尽可能少,却不能完全避免。这就要求在出现冲突后,寻求适当的方法来解决冲突记录的存放问题
    • 例 设记录的key的集合为c语言的一些保留字,则k={case,char,float,for,int,while,struct,typedef,union,goto,void,return,switch,if,break,continue,else},构造关于k的Hash表时,可按不同的方法选取H(key)

      • 令H1(key)=key[0]-'a',其中key[0]为key的第一个字符。显然这样选取的Hash函数冲突现象频繁。如:H1(float)=H1(for)='f'-'a'=5。解决冲突的方法之一时为for寻求另一个有效位置。
      • 令H2(key)=(key[0]+key[i-1]-2'a')/2。其中key[i-1]为key的最后一个字符。如:H2(float)=('f'+'t'-2'a')/2=12,H2(for)=('f'+'r'-2*'a')/2=11,从而消除了一些冲突的发生,但仍无法完全避免,如:H2(case)=H2(continue)
  • 综上所述,对Hash表的含义描述如下

    • 根据选取的hash函数H(key)和处理冲突的方法,将一组记录(R1 R2 R3 ...)映射到记录的存储空间,所得到的记录表称为Hash表
    • 关于Hash表的讨论关键时两个问题,一是选取Hash函数的方法;二是确定解决冲突的方法
  • 选取(或构造)Hash函数的方法很多,原则是尽可能将记录均匀分布,以减少冲突现象发生。以下是几种常用的构造方法

    • 直接地址法

      • 直接取key的某个线性函数为hash函数,即令:H(key)=a*key+b,其中a,b为常数,此时称H(key)为直接hash函数或自身函数
    • 数字分析法

      • 分析数据的规律,取数据中的部分进行hash
    • 平方取中法
    • 保留除数法
  • 根据实际情况,数据的规律,选取(或构造)Hash函数的方法

scanf/fscanf 的%[]和%n使用方法

标准输入输出函数%[]和%n说明符的使用方法

scanffscanf,均从第一个非空格的可显示字符开始读起!
标准输入输出函数scanf具有相对较多的转换说明符,它常常作为入门级函数出现在各种教材中。但奇怪的是,[]n这两种都为c89/c99所规定的标准说明符却鲜少在大多数教材中出现。虽然[]n说明符的使用频率不及其它说明符,但两者在程序设计中的作用仍然不可小视,尤其是[]说明符。

众所周之,scanf以空白字符为定界符,但如果输入的字符串是以其它字符为定界符的,那怎么办?[]就是专门处理这个问题的转换说明符。[]转换说明符可以通过两种方式产生结果字符集,如果第一个[字符右边没有抑扬符^,那么处于[]之间的字符就是结果字符集,不在其中的可输入字符都作为定界符;如果左边[符号紧靠一个抑扬符^,那么意义相反,^]之间的字符是定界符,其余可输入字符是结果字符集。

在使用[]说明符之前,得先明白两个概念:一是扫描列表。扫描列表(scanlist)指的是包含在[和]两个字符之间除紧靠左边[字符的抑扬符之外的字符,例如:

scanf("%[abcd]", ptr);

abcd组成扫描列表。二是扫描字符集(scanset)。扫描字符集指的是结果字符集,例如上面的例子,结果字符集就是abcd。如果输入一个字符串“cbadkjf”,那么ptr得到的字符串是cbad,kjf三个字符都属于定界符,输入到k字符时输入字符串被截断,kjf三个字符被留在stdin里面。如果带有抑扬符,例如:

scanf("%[^abcd]", ptr);

扫描列表仍然是abcd,但扫描字符集是除abcd外的可输入字符。如果输入字符串“jksferakjjdf”,ptr得到的字符串是“jksfer”。如果想限制输入字符串的字符数量,可以象s说明符那样,在[]前面使用位域,例如:

scanf("%10[^abcd]", ptr);

这样结果字符串最多只能包含10个字符(除'0'字符外)。

[符号可以作为扫描列表中的一个成员,但]字符除紧贴最左边的[字符或抑扬符两种情况外,其余情况下都不会被看作扫描列表的成员。例如%[]abcd]或者%[^]abcd],上述两种情况下]字符属于扫描列表的成员,但如果是“%[ab]cd]”,中间的]字符不会被看作扫描列表的成员,而且输入输出的结果会是乱七八糟的。

对于减号-,只有在紧贴[字符或抑扬字符以及作为扫描列表最后一个成员时,-字符才会被视为扫描列表的成员。c标准把其余情况规定为编译器相关的。大多数编译器把这种情况的减号定义为连字符,例如:

scanf("%[a-zA-Z]", ptr);

那么扫描列表由大小写各26个字母组成。少数编译器仍旧把这种情况下的减号视为扫描列表成员。

fscanf(fd,"%*[^\n]\n");//%*是虚读,没有存,只是让指针跳过了这个变量!

%n说明符输出有效字符数量,%nscanfprintf中都可使用。与%n相对应的形参是一个int类型的指针,%n不影响scanfprintf的返回值。例如:

scanf("%d %d%n", &i, &j, &k);

如果输入434 6434,则k等于8,而scanf的返回值仍然为2。又如:

scanf("%c%n", &ch, &k);

输入sbcdefdg后,k等于1,而不是8,因为%c只取一个字符,%n输出的是有效字符数量。

%n用在printf函数里,表示输出的字符数量,例如:

printf("i=%d, j=%d/n%n", i, j, &k);

在i=343、j=123的情况下,k=12,同时%n不影响printf的返回值,其返回值仍然为12,而不是14。


这个用法是在参H264 jm82考代码上看到的,用来从解码器参数配置文件中读取配置参数,代码如下:

// read the decoder configuration file
if((fd=fopen(config_filename,"r")) == NULL)
{
snprintf(errortext, ET_SIZE, "Error: Control file %s not found/n",config_filename);
error(errortext, 300);
}

fscanf(fd,"%s",inp->infile);                // H.26L compressed input bitsream
fscanf(fd,"%*[^/n]");

fscanf(fd,"%s",inp->outfile);               // YUV 4:2:2 input format
fscanf(fd,"%*[^/n]");

fscanf(fd,"%s",inp->reffile);               // reference file
fscanf(fd,"%*[^/n]");

对应的配置文件内容如下:

test.264                 ........H.26L coded bitstream
test_dec.yuv             ........Output file, YUV 4:2:0 format
test_rec.yuv             ........Ref sequence (for SNR)

通过这种方式

inp->infile = "test.264"

inp->outfile = "test_dec.yuv"

inp->reffile = "test_rec.yuv"

而相应的配置文件中的一些注释则不会被读入,这是相当简便的用法,比起通过严格约定注释符并进行一个字符一个字符来解析,这种方式简单了许多!值得借鉴!


scanf

语法:

  #include <stdio.h>
  int scanf( const char *format, ... );

类似函数有

int scanf(const char *format, ...);
int fscanf(FILE *stream, const char *format, ...);//指定输入流
int sscanf(const char *str, const char *format, ...);//指定缓存区

scanf()函数根据由format(格式)指定的格式从stdin(标准输入)读取,并保存数据到其它参数. 它和printf()有点类似. format(格式)字符串由控制字符,空白字符和非空白字符组成. 控制字符以一个%符号开始,如下:

控制字符说明
%c一个单一的字符
%d一个十进制整数
%i一个整数
%e, %f, %g一个浮点数
%o一个八进制数
%s一个字符串
%x一个十六进制数
%p一个指针
%n一个等于读取字符数量的整数
%u一个无符号整数
%[]一个字符集
%%一个精度符号
  1. scanf()读取匹配format(格式)字符串的输入. 当读取到一个控制字符, 它把值放置到下一个变量. 空白(tabs, 空格等等)会跳过. 非空白字符和输入匹配, 然后丢弃. 如果是一个在%符号和控制符间的数量, 那么只有指定数量的字符转换到变量中. 如果scanf()遇到一个字符集(用%[]控制字符表示), 那么在括号中的任意字符都会读取到变量中. scanf()的返回值是成功赋值的变量数量, 发生错误时返回EOF.
  2. scanf()函数的一般格式为:scanf("格式字符串",输入项首地址表)
  3. scanf的格式控制的一般形式为:%[*][宽度][F|N][h|l]类型字符
    []中的控制字符为可选项
  4. "*"表示该输入项读入后不赋予任何变量,即跳过该输入值。
  5. "宽度"表示输入读入字符的长度,对于整型表示截取相应宽度的数字赋给后面列表中的相应变量;对于字符型表示读入相应长度的字符后把第一个字符赋给相应的变量,其余的自动舍弃。例如scanf("%2d%3d",&a, &b);如果输入为12345则将12赋给a,将45赋给b;scanf("%2c%3c",&a, &b);如果输入为12345则将'1'赋给a,将'3'赋给b .
范例说明
%s整个输入作为一个串,并设置末尾的\0
%nsn为整数,读入的串最长不超过n,然后在末尾补'0'
%nf读入的浮点数最多有n位整数,位数多于n,会截断。
%n[a-z]读入最多n个字符,如果遇到非a-z的字符,停止
%1读入任意多的字符,直到遇到"="停止
%n[^=]读入"="号前的至多n 个字符
  1. F 、N、h、l分别表示远指针、近指针、短整和长整型。
  2. 对于输入字符串还有一些比较有用的控制。
    例如经常需要读入一行字符串,而这串字符里面可能有空格、制表符等空白字符,如果直接用%s是不可以的,于是有些人就想到用gets(),当然这也是一种选择,但是懂C的人基本上都知道gets()是一个很危险的函数,而且很难控制,特别是与scanf()交替使用时前者的劣势更是一览无余,所以gets()一般是不推荐用的,其实用%[^\n]就可以很好的解决这个问题了,^表示"非",即读入其后面的字符就结束读入。这样想读入一行字符串直接用scanf("%[^\n]%*c",str);就可以了,%*c的作用是读入\n,否则后面读入的将一直是/n

所有对%s起作用的控制都可以用%[],比如%[0-9]表示只读入'0'到'9'之间的字符,%[a-zA-Z]表示只读入字母,
'-'是范围连接符,当然也可以直接列出你需要读入的字符。
如果你只需要读"abc"里面的字符就可以用%[abc] (或者%[cab]、%[acb]、%[a-c]、%[c-a].....),
如果想读入某个范围之外的字符串就在前面加一个'^',如:%[^a-z]就表示读入小写字母之外的字符。
例如从键盘输入的"1235ab86"中读取1235、86给n,有如下方法:

#include <stdio.h>  
bool skip(){  
     scanf("%*[^0-9]");  
     return true;  
}  
void main()  
{  
      int n;  
      while(skip() && scanf("%d", &n)!=EOF)  
        printf("%d\n", n);  
}

输出为:

1235
86

转载自:http://blog.csdn.net/wesweeky/article/details/6439777


  1. =

c的标准IO

文件的概念

  • 所谓文件是指一组相关数据的有序集合,这个数据集有一个名称,叫做文件名。如源程序文件,目标文件,可执行文件,头文件等
  • 文件通常时驻留在外部介质(如磁盘等)上的,在使用时才调入内存中来
  • 从用户角度看,文件可分为普通文件和设备文件两种

    • 普通文件:普通文件是指驻留在磁盘或其他外部介质上的一个有序数据集,可以是源文件,目标文件,可执行程序等
    • 设备文件:设备文件是指与主机相联的各种外部设备,如显示器,打印机,键盘等。在操作系统中,把外部设备也看作是一个文件来管理,把它们的输入,输出等同于磁盘文件的读和写
  • 从文件编码的形式看,文件可分为文本文件和二进制文件两种

    • 文本文件

      • ASCII码格式存放,一个字节放一个字符。文本文件的每一个字节存放一个ASCII码,代表一个字符。这便于对字符的逐个处理,但占用存储空间较多,转换为二进制速度慢,但直观易记。
      • 如整数 1000 => 0011000100110000001100000011000000110000
    • 二进制文件

      • 以补码形式存放。二进制文件是把数据以二进制数的格式存放在文件中的,其占用存储空间极少,无需转换。
      • 数据按其内存中的存储形式原样存放。一个字节不对应一个字符,故不能直接输出其字符样式。
      • 如:整数 1000 => 0010011100010000

文件系统的分类

目前c语言所使用的磁盘文件系统分为缓冲文件系统和非缓冲文件系统

  • 缓冲文件系统

    • 系统自动地在内存区为每一个正在使用的文件开辟一个缓冲区。从磁盘向内存读入数据时,则一次从磁盘文件将一些数据输入到内存缓冲区(充满缓冲区),然后再从缓冲区逐个地将数据送给变量。向磁盘文件输出数据时,先将数据送到内存中的缓冲区,装满缓冲区后才一起送到磁盘去
    • 用缓冲区可以一次读入一批数据,或输出一批数据,而不是执行一次输入或输出函数就去访问一次磁盘,这样做的目的是减少磁盘的实际读写次数,提高读写的效率。
  • 非缓冲的文件系统

    • 不是有系统自动设置缓冲区,而由用户自己根据需要设置
    • 用户在程序中为每个文件设定缓冲区
  • 在传统的UNIX文件系统下,用缓冲文件文件系统来处理文本文件,用非缓冲文件系统处理二进制文件
  • 1983年ANSI C标准决定不采用非缓冲文件系统,而只采用缓冲文件系统。即用缓冲文件系统处理文本文件,也用它来处理二进制文件。也就是将缓冲文件系统扩充为可以处理二进制文件。
  • 一般把缓冲文件系统的输入输出称为标准输入输出(标准IO),非缓冲文件系统的输入输出称为系统输入输出(系统IO)。
  • 在c语言中没有输入输出语句,对文件的读写都是用库函数来实现的。ANSI C规定了标准输入输出函数,用它们对文件进行读写,需要使用头文件stdio.h

文件流的概念

  • 在c语言对文件的操作最终转化为对缓存中的数据进行操作,流实际上就是内存中的一种具有自动顺序操作的特殊数据,流如同流动的河水,有它的源和目的地。
  • 流根据方向可分为输入流和输出流

    • 输入流

      • 从文件读取数据的流
    • 输出流

      • 将数据输出到文件的流
  • 流根据数据内容可分为文本流和二进制流

    • 文本流

      • 二进制流就是流动着的字符序列
    • 二进制流

      • 二进制流就是流动着的二进制序列
  • 三个标准流

    • 标准输入流stdin(用数字0表示):针对标准输入,键盘
    • 标准输出流stdout(用数字1表示):针对标准输出,屏幕
    • 标准错误流stderr(用数字2表示):针对标准输出,屏幕
  • 上述所有的流都统称为文件流

文件类型结构体FILE和文件指针

  • 文件类型结构体FILE

    • 缓冲文件系统为每个正使用的文件在内存开辟文件信息区
    • 文件信息用系统定义的名为FILE的结构体描述
    • FILE定义在stdio.h
  • 文件指针的定义
    FILE *指针变量名

    • 文件指针实际上是一个文件类型结构体指针
    • 通过文件指针即可找到存放某个文件信息的文件类型结构体变量,然后按结构体变量提供的信息找到该文件,实施对文件的操作
    • 习惯上也笼统地把文件指针称为指向一个文件的指针或流指针
    • 当文件打开时,系统会自动创建文件类型结构体变量,并把指向它的指针返回回来,程序通过这个指针获得文件信息并访问文件
    • 文件关闭后,文件指针指向的结构体变量会被释放

文件打开

FILE *fopen(char *filename,char *mode);

  • 功能:按指定方式打开文件
  • 参数

    • filename:为打开的文件路径(相对路径或绝对路径)
    • mode:使用文件的方式
  • 返回:正常打开,返回文件指针;打开失败,返回NULL
  • 标准输入,标准输出和标准错误是由系统打开的,可直接使用
  • 示例
FILE *fp;
fp =fopen("test.txt","w");

使用文件的方式

文件使用方式含义
rt只读打开一个文本文件,只允许读数据
wt只写打开或建立一个文本文件,只允许写数据
at追加打开一个文本文件,并在末尾写数据
rb只读打开一个二进制文件,只允许写数据
wb只写打开或建立一个二进制文件,只允许写数据
ab追加打开一个二进制文件,并在末尾写数据
rt+读写打开一个文本文件,允许读和写
wt+读写打开或建立一个文本文件,允许读和写
at+读写打开一个文本文件,允许读或在末尾追加数据
rb+读写打开一个二进制文件,允许读和写
wb+读写打开或建立一个二进制文件,允许读和写
ab+读写打开一个二进制文件,允许读或在末尾追加数据

符号说明

  • r(read):读
  • w(write):写
  • a(append):追加
  • t(text):文本文件,可以省略不写
  • b(binary):二进制文件
  • +:读和写

文件使用的处理方式

mode处理方式当文件不存在当文件存在写文件读文件
r读取出错打开文件不能
w写入建立新文件覆盖原有文件不能
a追加建立新文件在原有文件后追加不能
r+读取/写入出错打开文件
w+读取/写入建立新文件覆盖原有文件
a+读取/写入建立新文件在原有文件后追加

如果是二进制文件,在使用时只要在模式后添加字符b即可,如rb,rb+分别表示读取二进制文件和以读取/写入方式打开二进制文件


文件关闭

int fclose(FILE *fp);

  • 功能:关闭fp指向的文件,释放文件类型结构体和文件指针。
  • 参数:fp打开文件时返回的文件指针
  • 返回:成功返回0,失败返回-1
  • 注意点:不关闭文件可能会丢失数据

    • 向文件写数据时,是先将数据输出到缓冲区,待缓冲区充满后才正式输出给文件。如果当数据未充满缓冲区而程序结束允许,就会将缓冲区的数据丢失
    • fclose先把缓冲区的数据输出到磁盘文件(刷新缓存),然后才会释放文件类型结构体和文件指针

测试文件读写位置

int ftell(FILE *fp);

  • 功能:测试当前文件的读写位置
  • 返回:测试成功返回文件位置指针所在的位置(当前读写位置距离文件开头的字节数),失败则返回-1

常用的标准IO函数

getchar

int getchar();

  • 功能:从标准输入读取一个字符
  • 返回:成功返回读取的字符,否则返回EOF

putchar

int putchar();

  • 功能:将一字符ch写入到标准输出

fgetc

int fgetc(FILE *fp);

  • 功能:从fp指向的文件中读取一个字符
  • 返回:成功返回读取的字符,否则返回EOF(-1)
  • 可针对标准输入操作

fputc

int fputc(int ch,FILE *fp);

  • 功能:把一字符ch写入fp指向的文件中
  • 返回:成功返回写入的字符ch,失败返回EOF
  • 可针对标准输入输出操作

ungetc

int ungetc(int c,FILE *fp);

  • 功能:撤销一个字符

fgets

char *fgets(char *str,int siez,FILE *fp);

  • 功能:从fp指向的文件中至多读size - 1个字符,放到str指向的字符数组中,如果在读入size - 1个字符结束前遇到换行符或EOF,读入即结束,字符串读入后在最后加一个\0
  • 返回:成功返回str字符串指针,失败返回NULL
  • 可针对标准输入操作

fputs

int fputs(char *str,FILE *fp);

  • 功能:把str指向的字符串或字符数组写入fp指向的文件中
  • 返回:成功返回0,出错返回EOF
  • 可针对标准输出操作

fscanf和fprintf

int fscanf(FILE *fp,const char *format,...);
int fprintf(FILE *fp,const char *format,...);

  • 功能:按format格式对fp指向的文件进行IO操作
  • 返回:成功返回IO字节数,失败或到文件末尾返回EOF
  • 可针对标准输入和输出操作
  • 示例
#include <stdio.h>
#include <string.h>
int main(int argc,char *argv[])
{
        if(argc < 2)
  6         {
                fprintf(stdout,"parameter error\n");
                return 1;
        }   
        FILE *fp1 = fopen("/etc/passwd","r");
        FILE *fp2 = fopen(argv[1],"r");
        char str[1024] = {'\0'},name[20] = {'\0'},passwd[20] = {'\0'},description[20] = {'\0'},home[20] = {'\0'},bash[20] = {'\0'}; 
        int uid = 0,gid = 0;
        // 这里读取之后,整行的内容都在name中
        int flag = fscanf(fp1,"%[^:]:%[^:]:%d:%d:%[^:]:%[^:]:%[^\n]\n",name,passwd,&uid,&gid,description,home,bash); 
        while((flag = fscanf(fp1,"%[^:]:%[^:]:%d:%d:%[^:]:%[^:]:%[^\n]\n",name,passwd,&uid,&gid,description,home,bash))!= EOF)
        {   
                printf("%d\n",flag);                fprintf(stdout,"name=%s;passwd=%s;uid=%d;gid=%d;description=%s;home=%s;bash=%s\n",name,passwd,uid,gid,description,home,bash);
                // description位置可能会为空,为空的话,文件指针的位置不会移动到下一行,这个需要处理下
                if(0 == flag)
                {   
                        fscanf(fp1,"%*[^\n]\n");
                        // 清空description的数据
                        memset(description,'\0',sizeof(description));
                        //break;
                }           
        }           
        return 0;   
}

sscanf

int sscanf(char const *str,char const *format,...);
int sprintf(char const *str,char const *format,...);
  • 功能:按format格式对str指向的字符数组进行IO操作
  • 返回:成功返回I/O字节数,失败返回EOF
  • 实例
#include <stdio.h>
int main(void)
{
        char str1[20] = "666 jin";
        int id = 0;
        char name[10] = {'\0'};
        // 这里不字符串666转换成了数字
        sscanf(str1,"%d %s",&id,name);
        printf("id = %d,name = %s\n",id,name);
        // 不数字666转换成字符串666
        char number[5] = {'\0'};
        sprintf(number,"%d",id);
        printf("number = %s\n",number);
        return 0;
}

fread和fwrite

int fread(void *buffer,int num_bytes,int count,FILE *fp);
int fwrite(void *buffer,int num_bytes,int count,FILE *fp);
  • 功能:读写数据块,一般用于二进制文件的输入输出
  • 返回:成功返回读写的元素个数,失败或到文件末尾返回EOF
  • 参数:

    • buffer:一个指向要进行输入输出数据存储区的通用指针
    • num_bytes:每个要读写的元素的字节数
    • count:要读写的元素个数
    • fp:要读写的文件指针
  • fread和fwrite函数的使用注意点

    • fprintffscanf函数对磁盘读写,使用方便,容易理解,但由于在输入时要将ASCII码转换成二进制形式,在输出时又要将二进制形式转换成字符,花费时间较多。
    • 因此,在内存与磁盘频繁交换数据的情况下,最好不要用fprintffscanf函数,而用freadfwrite函数
  • 实例
#include <stdio.h>
struct User
{
        int id;
        char name[20];
};
int main(int argc,char *argv[])
{
        if(argc < 2)
        {
                printf("parameter error\n");
                return 1;
        }
        FILE *fp1 = fopen("/etc/passwd","r");
        FILE *fp2 = fopen(argv[1],"wb");
        if(fp1 == NULL || fp2 == NULL)
        {       
                printf("parameter error\n");
                return 1;
        }
        struct User user;
        while(EOF != fscanf(fp1,"%[^:]:%*[^:]:%d:%*[^\n]\n",user.name,&user.id))
        {
                if(EOF == fwrite(&user,sizeof(struct User),1,fp2))
                {
                        printf("fail to write file\n");
                        return 1;
                }
                //printf("uid = %i;name = %s\n",user.id,user.name);
        }
        fclose(fp1);
        fclose(fp2);
        fp2 = fopen(argv[1],"rb");
        /* 利用返回值判断是否到达文件尾
        while(0 != fread(&user,sizeof(struct User),1,fp2))
        {
                printf("uid = %i;name = %s\n",user.id,user.name);
        }
        */
        fread(&user,sizeof(struct User),1,fp2);
        // 使用feof判断是否是文件结尾
        while(!feof(fp2))
        {
                printf("uid = %i;name = %s\n",user.id,user.name);
                fread(&user,sizeof(struct User),1,fp2);
        }

        return 0;
}

fseek函数

int fseek(FILE *fp,long offset,int whence);

  • 功能:使fp所指文件的位置指针重置到指定位置(从whence位置移动offset个字节)
  • 返回:成功返回0,失败返回-1
  • offset:位移量,表示移动的字节数
  • whence:

    • SEEK_SET:文件首 0 offset非负
    • SEEK_CUR:文件当前读写位置 1 offset可正可负
    • SEEK_END:文件尾 2 offset可正可负

rewind函数

void rewind(FILE *fp);

  • 功能:使文件位置指针重新返回文件首

remove函数

int remove(const char *filename);

  • 功能:删除指定的文件
  • 返回:成功返回0,失败返回-1

fflush函数

void fflush(FILE *fp);

  • 功能:刷新缓冲区。如果打开文件进行读操作,该函数将清空文件的输入输出缓冲区,如果打开文件进行写操作时,该函数将文件的输出缓冲区内容写入文件中

c预处理操作符,预定义宏和其他指令

预处理操作符

c语言中有两个预处理操作符###,他们可以在#define中使用
操作符#通常称为字符串化的操作符,它把其后的串变成用双引号包围的串
连接操作符##可以把两个独立的字符串连接成一个字符串
示例

#define PRINT(FORMAT,VALUE) printf("the value of"#VALUE"is"FORMAT"\n",VALUE)
#define ADD_TO_SUM(sum_number,value) sum##sum_number+=value

案例
源码

#define PRINT(FORMAT,VALUE) printf("the value of "#VALUE" is "FORMAT"\n",VALUE)
#define ADD_TO_SUM(sum_number,value) sum##sum_number+=value
int main(void)
{
        PRINT("%d",888);
        int sum222 = 222;
        ADD_TO_SUM(222,666);
        PRINT("%d",sum222);
        return 0;
}

预处理后的代码

int main(void)
{
 printf("the value of ""888"" is ""%d""\n",888);
 int sum222 = 222;
 sum222+=666;
 printf("the value of ""sum222"" is ""%d""\n",sum222);
 return 0;
}

预定义宏

  • __FILE__进行编译的文件名
  • __LINE__文件当前行的行号
  • __DATE__文件被编译的日期(格式为"Mmm dd yyyy")
  • __TIME__文件被编译的时间(格式为"hh:mm:ss")
  • __func__当前所在函数名

其他预定义指令

  • #error
  • #line
  • #pragma

示例

#include <stdio.h>
/*
// 下面这句会中断程序的编译
// 与 __LINE__ 配合使用,设置了这个之后,下面的 __LINE__ 会输出1003 
#error "this is a test!!"*/
#line 1000
// 在编译时会输出下面的信息
#pragma message("this is a pragma message")
int main(void)
{
        printf("__FILE__ = %s\n",__FILE__);
        printf("__LINE__ = %d\n",__LINE__);
        printf("__DATE__ = %s\n",__DATE__);
        printf("__TIME__ = %s\n",__TIME__);
        printf("__func__ = %s\n",__func__);
}

c文件包含

文件包含时c预处理程序的另一个重要功能,被包含的文件名字必须要用双引号或一对尖括号括起来

文件包含的语法

#include <文件名>
#include "文件名"
  • 功能:一个源文件可将另一个源文件的内容全部包含进来,从而把指定的文件和当前的源程序文件连城一个源文件。
  • 处理过程:在预处理时,用被包含文件的内容替换该包含指令,再对包含后的文件作一个源文件编译
  • 一般而言,若调用标准库函数用#include <文件名>,若要包含用户自己编写的文件用#include "文件名"
  • 一个include指令只能指定一个被包含文件,允许潜逃包含。被包含的文件可以是源文件(.c)或者头文件(.h)

文件包含的搜索模式

#include <文件名>
若指定文件目录(如gcc -I选项指定的目录)则从此目录中找,否则按标准方式查找。
标准方式:从系统标准文件所在中寻找要包含的文件
#include "文件名"
先从存放c源文件的目录中查找,然后若用户指定目录(如gcc -I选项指定的目录),再从此目录中寻找要包含的文件,若找不到再按标准方式查找

文件包含的作用

  • 一个大的程序可以分为多个模块,由多个程序猿分别编程。有些公用的符号常量,结构体声明或宏定义等可单独组成一个文件,在其它文件的开头用包含指令包含该文件即可使用。
  • 可避免在每个文件开头都去书写那些公用量,从而节省时间,并减少出错

多重包含

  • 同一个文件被多次包含称为多重包含
  • 多重包含可能会出现重复定义的编译错误
  • 为了防止多重包含可使用条件编译,注意条件编译只适用于一个文件中
#ifndef __HEADERNAME_H__
#define __HEADERNAME_H__ 1
#include "headername.h"
#endif