回看经典！第十三章 C语言数据结构与算法基础：文件操作、排序查找实现及链表简介（2015年C语言培训班笔记重读）
目录
本文汇总了C语言在数据结构入门阶段的多个核心主题。包括文件操作（fopen、读写、指针）、基础排序算法（冒泡、选择）与查找算法（顺序、二分查找及其递归实现）的原理与代码实现，并简要介绍了单向链表的存储特点。通过对比和多个代码示例，为理解更复杂的数据结构与算法打下坚实基础。第十三章 基础数据结构
第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个成员进行同样操作
…………直到所有成员都完成冒泡排序为止。
案例之前已使用多次，这里省略
【Word上下标符号怎么打】
在Word中使用快捷键进行输入，既方便又快捷。
1. 加上标:使用Ctrl+Shift+=组合键，按一次后就可进入上标输入状态，再按一次可恢复到正常状态。
2. 加下标:使用Ctrl+ =组合键，同样按一次后就可进入下标输入状态，再次按就可恢复到正常状态。
选择排序：
基本思想是：
第一次从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;
elseif(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>
intbin_rec(int *arr,int low,int high,int key){
int mid;
if(low<=high){
mid=(low+high)/2;
if(arr[mid]==key)
return mid;
elseif(arr[mid]<key)
returnbin_rec(arr,mid+1, high,key);
else
returnbin_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。
在链表中，通过指向接后结点位置的指针实现将链表中的每个节点“链”到一起，链表中第一个结点称之为头结点。
计算机科学与技术 & 计算机网络技术：双专业课程体系完全导航指南
本系列目录
1、回看经典！第一章 从“Hello World”到理解编译本质（2015年C语言培训班笔记重读）
2、回看经典！第二章 数据类型与运算符详解（2015年C语言培训班笔记重读）
3、回看经典！第三章 流程控制全解 逻辑/分支/循环/图形实战（2015年C语言培训班笔记重读 ）
4、回看经典！第四章 · C语言数组与字符串核心实战 从定义、遍历到排序与算法详解（2015年C语言培训班笔记重读）
5、回看经典！第五章 C语言数组高级应用实战：字符串处理、安全防范与多文件编程（2015年C语言培训班笔记重读）
6、回看经典！第六章 C语言综合能力提升：多文件编程与递归函数核心解析及实战（2015年C语言培训班笔记重读）
7、回看经典！第七章 全面解析C语言指针：从核心概念到高效应用（2015年C语言培训班笔记重读）
8、回看经典！第八章 C语言指针完全指南：深度解析二维数组、多级指针与内存操作实战（2015年C语言培训班笔记重读）
9、回看经典！第九章 C语言内存管理完全指南：四区模型、堆栈操作与malloc/free核心实践（2015年C语言培训班笔记重读）
10、回看经典！第十章 C语言结构体完全指南：内存对齐、动态管理与指针应用实战（2015年C语言培训班笔记重读）
11、回看经典！第十一章 C语言文件操作与数据处理实战：从结构体到文本加密、排序全解析（2015年C语言培训班笔记重读）
12、回看经典！第十二章 C语言二进制文件操作实战：fread/fwrite读写、fseek随机访问与加密排序案例（2015年C语言培训班笔记重读）
