C 语言数据结构与算法基础：文件操作、排序查找及链表简介

第十三章 基础数据结构

第 1 课：复习文件操作

fopen 函数的参数中，没有写具体路径，则表示在程序运行的当前目录下（相对路径）；写了具体路径就是绝对路径。

文件结尾标识符 EOF 的使用

案例 1：用 feof 判断读取下面文件中一个个字符：

代码：

int main(){
    FILE *p=fopen("d:/c1/gcc/test/1.txt","rb");
    char c=0;
    while(!feof(p)){
        c=getc(p);
        printf("%x\n",c);
    }
}

结果为：

案例 2：用 EOF 判断读取案例 1 所用文件中一个个字符：

int main(){
    FILE *p=fopen("d:/c1/gcc/test/1.txt","rb");
    char c=0;
    while(c!=EOF){
        c=getc(p);
        printf("%x\n",c);
    }
}

或者用 EOF 的值 -1 来判断也行：

int main(){
    FILE *p=fopen("d:/c1/gcc/test/1.txt","rb");
    char c=0;
    while(c!=-1){
        c=getc(p);
        printf("%x\n",c);
    }
}

案例 3：用 EOF 简化法判断读取案例 1 所用文件中一个个字符：

int main(){
    FILE *p=fopen("d:/c1/gcc/test/1.txt","rb");
    char c=0;
    while((c=getc(p))!=EOF){
        printf("%x\n",c);
    }
}

案例：用读写方式（+）打开文件，配合 fseek 函数同时到文件进行读取和改写：

#include<stdio.h>
#include<string.h>
struct student{
    char name[10];
    int age;
};
int main(){
    struct student s={"tom",20};
    struct student st={0};
    FILE *p=fopen("d:/c1/gcc/test/st.dat","rb+");
    fseek(p,sizeof(struct student),SEEK_SET); //从文件开头向后移动一个结构大小的字节数
    fwrite(&s,sizeof(struct student),1,p);
    fseek(p,0,SEEK_SET);     //将文件指针移动到文件开始位置
    while(!feof(p)){
        memset(&st,0,sizeof(struct student));
        fread(&st,sizeof(struct student),1,p);
        printf("name=%s,age=%d\n",st.name,st.age);
    }
    fclose(p);
    return 0;
}

fflush 函数

程序在向文件中写入数据时，并不是直接写入磁盘，而是先写入内存缓冲区，当内存已满或明确调用了 fclose 函数后，才一次性将数据写入文件。

使用 fflush 函数可以实时将数据写入磁盘。

当程序中没有 fflush 函数，也没有 fclose 函数时，数据能否正常写入文件？ 答：可以的，因为程序退出时，系统会自动调用 fclose 函数（这里的退出是指程序运行完 return 0;后的自动退出，而不是手动关闭的退出），但是这不等于写程序时可以省略 flcose 不写。因为： 程序没有退出的时候，会有很多文件打开； 一个程序可以同时打开的文件数量是有限的； 在一个程序中尽量不要同时打开多个文件。最好是用完一个文件，就执行 fclose 关闭文件。

案例：用 sprintf 自动创建文件名，并 fputs 写入数据

#include<stdio.h>
#include<string.h>
int main(){
    char filename[100]={0};
    int i;
    for(i=10;i<20;i++){
        sprintf(filename,"d:/c1/gcc/test/%d.txt",i);
        FILE *p=fopen(filename,"w");
        if(p!=NULL){
            fputs("hello",p);
            fclose(p);
        }else{
            printf("error\n");
        }
    }
    return 0;
}

以上代码只能用 GCC 编译，因为在 VS 中会报错，主要是因为 VS 中打开文件的操作最好在代码开头。

第 2 课：冒泡排序与选择排序

数据结构：了解即可，不宜花太多时间去研究。因为实践中很少用到。

冒泡排序： 基本思想：以数组 array[]={a1,a2,a3,a4,……an-1,an,};为例 首先，a1 和 a2 比较，如果 a1>a2，则两者交换，然后比较 a2 和 a3，以此类推，直到第 a(n-1) 和 an 进行比较为止。这是第一次冒泡 第二次冒泡：对前 n-1 个成员进行同样操作。 第三次冒泡：对前 n-2 个成员进行同样操作 …………直到所有成员都完成冒泡排序为止。

选择排序： 基本思想是： 第一次从 R[0]~R[n-1] 中选取最小值，与 R[0] 交换，第二次从 R[1]~R[n-1] 中选取最小值，与 R[1] 交换，第三次从 R[2]~R[n-1] 中选取最小值，与 R[2] 交换，……第 n-1 次从 R[n-2]~R[n-1] 中选取最小值，与 R[n-2] 交换，总共通过 n-1 次，得到一个由小到大的序列。

选择排序跟冒泡排序，思想其实很相似

选择排序案例，写法 1：

#include<stdio.h>
void swap(int *a,int *b){  //交换
    int tmp=*a;
    *a=*b;
    *b=tmp;
}

int small(int *arr,int low,int high){     //选择/查找最小的值，并返回其下标
    int i;
    int index=low;
    int min=arr[low];
    for(i=low+1;i<high;i++){
        if(min>arr[i]){
            min=arr[i];
            index=i;
        }
    }
    return index;
}

void select(int *arr,int n){
    int i,j;
    for(i=0;i<n;i++){
        j=small(arr,i,n);
        if(j!=i)
            swap(&arr[i],&arr[j]);
    }
}

int main(){
    int i;
    int arr[10]={20,50,89,65,16,32,45,12,26,23};
    select(arr,10);
    for(i=0;i<10;i++){
        printf("arr[%d]=%d\n",i,arr[i]);
    }
    return 0;
}

效果如下:

选择排序案例，写法 2：

#include<stdio.h>
int main(){
    int i,j,tmp;
    int arr[10]={20,50,89,65,16,32,45,12,26,23};
    for(i=0;i<10;i++){
        for(j=i+1;j<10;j++){
            if(arr[i]<arr[j]){
                tmp=arr[i];
                arr[i]=arr[j];
                arr[j]=tmp;
            }
        }
    }
    for(i=0;i<10;i++){
        printf("arr[%d]=%d\n",i,arr[i]);
    }
    return 0;
}

冒泡排序与选择排序的 for 区别：

冒泡排序：

for(i=0;i<10;i++){
    for(j=1;j<10-i;j++){
        if(arr[j-1]>arr[j])
            执行交换
    }
}

选择排序：

for(i=0;i<10;i++){
    for(j=i+1;j<10;j++){
        if(arr[i]<arr[j])
            执行交换
    }
}

第 3 课：二分查找算法

查找

顺序查找 顺序查找的过程为：从表的最后一个记录开始，逐个进行记录与给定值比较，如果某个记录与给定值相等，则查找成功，反之，则查找失败。

二分查找 在一个已经排序的顺序表中查找，可以使用二分查找来实现。 二分查找的过程是：先确定待查记录所在的范围，然后逐步缩小查找范围，直到找到或找不到记录为止。 二分查找，它有一个重要前提：就是该数组必须是一个有序数组，如果数组不是有序的，则必须先排序。

顺序查找案例：

#include<stdio.h>
int seq(int *arr,int low,int high,int key){
    int i;
    for(i=low;i<high;i++){
        if(arr[i]==key)
            return i;
    }
    return -1;
}

int main(){
    int arr[8]={20,60,24,15,36,95,12,58};
    int i=seq(arr,0,8,15);
    printf("%d\n",i);
    return 0;
}

二分查找案例：

#include<stdio.h>
int bin(int *arr,int low,int high,int key){
    int mid;
    while(low<=high){
        mid=(low+high)/2;
        if(arr[mid]==key)     //中间切一刀，正好和要查找的数相等
            return mid;
        else if(arr[mid]<key)//如果要找的数大于中间的数，则在右边部分继续找
            low=mid+1;
        else
            high=mid-1; //如果要找的数小于中间的数，则在左边部分继续找
    }
    return -1;
}

int main(){
    int arr[10]={12,20,32,36,45,65,78,85,96,99};     //此数组必须是有序的
    int i=bin(arr,0,10,36);
    printf("%d\n",i);
    return 0;
}

第 4 课：用递归实现二分查找

二分查找算法--递归案例：

#include<stdio.h>
int bin_rec(int *arr,int low,int high,int key){
    int mid;
    if(low<=high){
        mid=(low+high)/2;
        if(arr[mid]==key)
            return mid;
        else if(arr[mid]<key)
            return bin_rec(arr,mid+1, high,key);
        else
            return bin_rec(arr,low, mid-1,key);
    }else
        return -1;
}

int main(){
    int arr[10]={12,20,32,36,45,65,78,85,96,99};
    int i=bin_rec(arr,0,10,99);
    printf("%d\n",i);
    return 0;
}

第 5 课：单向链表的实现

单向链表定义 对于数组，逻辑关系上相邻的两个元素的物理位置也是相邻的，这种结构的优点是可以随机存储任意位置的元素，但缺点是如果从数组中间删除或插入元素，需要大量移动元素，效率不高。

链式存储结构的特点，元素的存储单元可以是连续的，也可以是不连续的，因此为了表示每个元素 a，与其接后的元素 a+1 之间的关系，对于元素 a，除了存储其本身的信息外，还需要存储一个指示其接后元素的位置。这两部分数据成为结点（node）。

一个结点中存储的数据元素被称为数据域，存储接后存储位置的域叫做指针域。n 个结点的存储映像链接成一个链表。

整个链表必须从头结点开始运行，头结点的指针指向下一结点的位置，最后一个结点的指针指向 NULL。

在链表中，通过指向接后结点位置的指针实现将链表中的每个节点'链'到一起，链表中第一个结点称之为头结点。