7.请分析以下代码的运行结果(-1或0或1),并解释其原因。
考点:scanf的返回值的含义 scanf函数返回 int型 成功读入的数据项数, 读入数据时遇到了“文件结束”则返回EOF -1。
答案
# include <stdio.h> int main() { int n; printf("%d", scanf("%d", &n));//输入非数值型为0,输入数值型为1,输入Ctrl+Z为-1 return 0; }
补充:printf的返回值的含义:输出字符的数量
#include<stdio.h> int main(){ int a=43; printf("%d",printf("%d",printf("%d",a)));//4321 }
8.你知道哪些排序算法?你知道它们是怎样实现的吗?(大致思路)
简单选择排序
在第i趟的记录序列中选取关键字第i小(大)的记录作为有序序列的第i个记录
#include <stdio.h> #define N 10 int main() { int a[N],n,i,k,j,t; scanf("%d",&n); for(i=0;i<n;i++) scanf ("%d",&a[i]); for(i=0;i<n-1;i++){ k=i; for(j=i+1;j<n;j++){ if(a[k]<a[j]) k=j; } if(k!=i){ t=a[i]; a[i]=a[k]; a[k]=t; } } for (i=0;i<n;i++) printf("%d ",a[i]); }
冒泡排序
冒泡排序也叫相邻比逆法,即在扫描待排序序列时,顺次比较相邻记录的关键字大小,如果逆序就 交换位置
冒泡排序1.0版
#include <stdio.h> #define N 100 int main() { int a[N],n,i,j; //输入 scanf("%d",&n); for(i=0;i<n;i++){ scanf ("%d",&a[i]); } for(i=0;i<n;i++){ for(j=0;j<n-1-i;j++){ if(a[j]>a[j+1]){ int t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for (i=0;i<n;i++) { //输出 if(i==0) printf("%d",a[i]); else printf(" %d",a[i]); } }
冒泡排序2.1版
#include <stdio.h> #define N 100 int main() { int a[N],n,i,j; //输入 scanf("%d",&n); for(i=0;i<n;i++){ scanf ("%d",&a[i]); } int change=1; for(i=0;i<n&&change;i++){ change=0; for(j=0;j<n-1-i;j++){ if(a[j]>a[j+1]){ int t=a[j]; a[j]=a[j+1]; a[j+1]=t; change=1; } } } for (i=0;i<n;i++) { //输出 if(i==0) printf("%d",a[i]); else printf(" %d",a[i]); } }
冒泡排序2.2版
#include <stdio.h> #define N 100 int main() { int a[N],n,i,j; //输入 scanf("%d",&n); for(i=0;i<n;i++){ scanf ("%d",&a[i]); } int flag; for(i=0;i<n;i++){ flag=0; for(j=0;j<n-1-i;j++){ if(a[j]>a[j+1]){ flag=1; int t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } if(flag){ break; } } for (i=0;i<n;i++) { //输出 if(i==0) printf("%d",a[i]); else printf(" %d",a[i]); } }
补充:简单桶排序
简单桶排序:相当于计数器数组 给要排序的数组元素计数 计数器数组的索引为要排序的数组元素 计数器数组元素为要排序的数组元素出现个数
#include<stdio.h> #define N 9 int main(){ int num[N]={1,2,3,4,2,3,5,4,6}; int i=0; //输出原数组 for(i;i<N;i++){ printf("%d ",num[i]); } printf("\n"); //建立空桶 int count[9]={0}; //桶中放每一个桶的序号count[]的对应于num数组每个数num[i]的个数 for(i=0;i<N;i++){ count[num[i]]++; } //输出桶 for(i=0;i<N;i++){ printf("%d-%d ",i,count[i]); } printf("\n"); //输出排序 for(i=0;i<N;i++){ int j; for(j=0;j<count[i];j++){ printf("%d ",i); } } }
9.字符串翻转
设计一个程序实现字符串翻转,即将abcdefg反转成gfedcba,已经为你写好了部分代码,请在规定的区域添加代码来实现程序。 不允许在规定地方之外写代码,不允许删除写过的代码。 代码本来就定义了一个字符串和一个字符变量和一个整型数,不允许声明新的任何类型的变量。
考点:字符串翻转 要求:空间复杂度为O(1),即不允许声明新的任何类型的变量。 实现:字符串内部操作
答案
# include <stdio.h> # include <string.h> int main() { char s[32]; scanf("%s", s); int n = strlen(s); char ch; int i; /* 规定区域开始 */ for(i = 0;i<=n/2;i++){ ch=s[i]; s[i]=s[n-1-i]; s[n-1-i]=ch; } /* 规定区域结束 */ printf("%s", s); return 0; }
扩展:去掉ch变量
用加减法实现交换
# include <stdio.h> # include <string.h> int main() { char s[32]; scanf("%s", s); int n = strlen(s); int i; /* 规定区域开始 */ i=0; n=n-1; while(i<n){ //交换元素是s[i]与s[n] s[i]=s[i]+s[n]; s[n]=s[i]-s[n]; s[i]=s[i]-s[n]; i++; n--; } /* 规定区域结束 */ printf("%s", s); return 0; }
用异或实现交换
# include <stdio.h> # include <string.h> int main() { char s[32]; scanf("%s", s); int n = strlen(s); int i; /* 规定区域开始 */ i=0; n=n-1; while(i<n){ //交换元素是s[i]与s[n] s[i]=s[i]^s[n]; s[n]=s[i]^s[n]; s[i]=s[i]^s[n]; i++; n--; } /* 规定区域结束 */ printf("%s", s); return 0; }
补充:用递归实现
#include<stdio.h> void reverseSentence(); int main(){ printf("输入:"); reverseSentence(); return 0; } void reverseSentence(){ char c; scanf("%c",&c); if(c != '\n'){ reverseSentence(); printf("%c",c); } }
10. 单链表逆置,要求在原有空间进行逆置。
答案
#include<stdio.h> #include<stdlib.h> #include<string.h> #define DataType int #define ERROR 0 #define TRUE 1 typedef struct node{ DataType data; struct node *next; }LNode,*LinkList; //1.建立单链表 //尾插法建立单链表 LinkList CreatByBear(){ LinkList H=(LinkList)malloc(sizeof(LNode)); //生成头结点 H->next=NULL; //空表 LNode *s, *r=H; int x; printf("输入(-1结束)"); scanf("%d",&x); while(x!=-1){ s=(LinkList)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; //r指向新的尾结点 printf("输入(-1结束)"); scanf("%d",&x); } r->next=NULL; return H; } //单链表的逆置 void Reverse(LinkList H){ LNode * p,*q; p=H->next; //p指向第一个数据结点 H->next= NULL; //将原链表置为空表H while(p){ q=p; p=p->next; q->next=H->next; //将当前结点插到头结点的后面(头插) H->next=q; } } //遍历输出 void OutPut(LinkList head){ LNode *p; p=head->next; while(p){ printf("(%d)\n",p->data); p=p->next; } } void main(){ //建立 LinkList h=CreatByBear(); printf("输出"); OutPut(h); Reverse(h); printf("逆置"); OutPut(h); }