跳到主要内容C 语言数据结构与算法基础:文件操作、排序查找及链表简介 | 极客日志C算法
C 语言数据结构与算法基础:文件操作、排序查找及链表简介
C 语言基础数据结构与算法,涵盖文件操作(fopen、读写、指针)、基础排序算法(冒泡、选择)及查找算法(顺序、二分查找及其递归实现),并简述了单向链表的存储特点。通过原理讲解与代码示例,帮助读者理解核心概念。
无尘19K 浏览 第十三章 基础数据结构
第 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(,c);
}
}
微信扫一扫,关注极客日志
微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
- Markdown转HTML
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
"%x\n"
案例 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;
}
程序在向文件中写入数据时,并不是直接写入磁盘,而是先写入内存缓冲区,当内存已满或明确调用了 fclose 函数后,才一次性将数据写入文件。
当程序中没有 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 次,得到一个由小到大的序列。
#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;
}
#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(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。
在链表中,通过指向接后结点位置的指针实现将链表中的每个节点'链'到一起,链表中第一个结点称之为头结点。