C 2015年真题【保】
2024-09-19 22:48:59
1、编写一个完整的程序，使之能完成以下功能：从键盘中输入若干个整数，用链表储存这些输入的数，并要求存储的顺序与输入的顺序相反。
分析：链表建立【头插法】
代码：
#include <stdio.h>
#include <stdlib.h> //定义单链表
typedef struct slist{
int data;
struct slist *next;
}; void main()
{
struct slist *head,*temp; //head为头结点
head = (struct slist *)malloc(sizeof(struct slist));
head ->next = NULL;
int i,s; printf("输入元素：\n");
scanf("%d",&s);
while(s != 9999)
{
temp = (struct slist *)malloc(sizeof(struct slist));
temp ->data = s;
//头插法，建立逆序链表
temp ->next = head ->next;
head ->next = temp;
scanf("%d",&s);
} printf("输出链表：\n");
temp = head ->next;
while(temp != NULL)
{
printf("%d\t",temp ->data);
temp = temp ->next;
}
}
2、编写一个函数，把整数序列分成两个部分，使得左边部分都不大于右边部分，不需要排序。 （ 考察的是快速排序的部分）
函数代码：
//链表划分
int partition(int arr[],int low,int high)
{
int pos=low;
int i=low, j=high;
int temp; while(i!=j)
{
while(arr[j]>=arr[pos] && i<j)j--;
while(arr[i]<=arr[pos] && i<j)i++;
if(i<j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp; return i;
}完整代码：
#include <stdio.h>
#include <stdlib.h>
const int m = 7; //链表划分
int partition(int arr[],int low,int high)
{
int pos=low;
int i=low, j=high;
int temp; while(i!=j)
{
while(arr[j]>=arr[pos] && i<j)j--;
while(arr[i]<=arr[pos] && i<j)i++;
if(i<j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp; return i;
} //快速排序递归式
void quicksort(int a[],int low,int high)
{
if(low < high)
{
int pivotpos = partition(a,low,high);
quicksort(a,low,pivotpos - 1);
quicksort(a,pivotpos+1,high);
}
} void main()
{
int a[] = {1,4,7,8,5,2,3};
int low = 0, high = m - 1,i;
quicksort(a,low,high); printf("排序后：\n");
for(i = 0; i < m; i++)
{
printf("%d\t",a[i]);
}
}
3、有两个整数数组A和B，它们分别有m、n个整数。并且都是按非递减序列，现将B数组插入A数组中，使得A数组中各元素不大于B数组中各元素，非递减序列。
实例：将B[2,3,6,9] 数组插入A[1,4,7] 数组，顺序排序
思路一：将B插入A后，再顺序排序
代码：
#include <stdio.h>
#include <stdlib.h> void main()
{
int n = 3,m = 4;
int a[7] = {1,4,7},b[] = {2,3,6,9},i = 0,j;
j = n;
//将B插入到A后
while(i < m)
{
a[j++] = b[i++];
}
//将A进行排序【冒泡】
for(i = 0;i < m+n-1;i++)
{
for(j =0;j < m+n-1-i;j++)
{
int tmp;
if(a[j] > a[j+1])
{
tmp = a[j+1];
a[j+1] = a[j];
a[j] = tmp;
}
}
}
printf("将B插入A中，顺序排序：\n");
for(i = 0;i < m+n;i++)
{
printf("%d\t",a[i]);
}
}
思路二：使用附加数组C
代码：
#include <stdio.h>
#include <stdlib.h>
const int n = 3;
const int m = 4;
void main()
{
int a[] = {1,4,7},b[] = {2,3,6,9},c[7] = {0},i = 0,j = 0,k = 0;
do
{
if(a[i] > b[j])
{
c[k++] = b[j++];
}
else
c[k++] = a[i++];
if(i >= n)
c[k++] = a[j++];
if(j >= m)
c[k++] = b[i++];
}while((i >= n && j >= m) == 0); printf("将B插入A中，顺序排序：\n");
for(i = 0;i < m+n;i++)
{
printf("%d\t",c[i]);
}
}
4、两个递增有序整数数列链表La和Lb，将他们合并后，变成一个新的链表，要求该链表递减排序。（结点node由整型data和节点指针next构成）
代码：
#include <stdio.h>
#include <stdlib.h>
typedef struct slist
{
int data;
struct slist *next;
};
//合并【头插法逆序】
void unionslist(struct slist *la,struct slist *lb)
{
struct slist *p=la->next;
struct slist *q=lb->next;
struct slist *temp;
la->next=0; while(p&&q)
{
if(p->data <= q->data)
{
temp = p->next;
p->next = la->next;
la->next = p;
p=temp;
}
else
{
temp = q->next;
q->next = la->next;
la->next = q;
q=temp;
}
}
//若La比Lb短，La遍历完，Lb依序插入
if(q) //若q不为空
p=q;
while(p)
{
temp = p->next;
p->next = la->next;
la->next = p;
p=temp;
}
}
//打印输出
void input(struct slist *head)
{
struct slist *p = head ->next;//p为工作指针
while(p != NULL)
{
printf("%d\t",p ->data);
p = p ->next;
}
}
int main()
{
//构建链表La和Lb
struct slist *La,*Lb,*p;// La为La链表的头结点，Lb为Lb链表的头结点，p为尾指针
La = (struct slist*)malloc(sizeof(struct slist));
Lb = (struct slist*)malloc(sizeof(struct slist));
La ->next = NULL;
Lb ->next = NULL;
int a[] = {1,4,7,8},b[] = {2,3,5,6,9},i,j;
p = La;
for(i = 0; i < 4; i++)
{
//尾插法顺序
struct slist *node = (struct slist*)malloc(sizeof(struct slist));
node ->data = a[i];
node ->next = p ->next;
p ->next = node;
p = node;
}
p = Lb;
for(i = 0; i < 5; i++)
{
//尾插法顺序
struct slist *node = (struct slist*)malloc(sizeof(struct slist));
node ->data = b[i];
node ->next = p ->next;
p ->next = node;
p = node;
}
//输出
printf("La:");
input(La);
printf("\nLb:");
input(Lb);
//合并
printf("\n合并后：");
unionslist(La,Lb);
input(La);
return 0;
}
5、编写一个函数，删除链表中的最小值。（结点node由整型data和节点指针next构成）
代码：
#include <stdio.h>
#include <stdlib.h> typedef struct slist
{
int data;
struct slist *next;
};
//删除最小值
void delmin(struct slist *la)
{
struct slist *p = la ->next,*pre = la; //p为工作指针，pre为p的前驱，min记录最小值，premin是min的前驱
struct slist *min = p,*minpre = la;
while(p)
{
if(p ->data < min ->data)
{
min = p;
minpre = pre;
}
pre = p;
p = p ->next;
}
minpre ->next = min ->next;
free(min);
}
//打印输出
void input(struct slist *head)
{
struct slist *p = head ->next;//p为工作指针
while(p != NULL)
{
printf("%d\t",p ->data);
p = p ->next;
}
}
int main()
{
//构建链表La
struct slist *La,*p;// La为La链表的头结点，p为尾指针
La = (struct slist*)malloc(sizeof(struct slist));
La ->next = NULL;
int a[] = {3,6,9,8,1,5,2},i;
p = La;
for(i = 0; i < 7; i++)
{
//尾插法顺序
struct slist *node = (struct slist*)malloc(sizeof(struct slist));
node ->data = a[i];
node ->next = p ->next;
p ->next = node;
p = node;
}
//输出
printf("La:");
input(La);
//删除最小值
delmin(La);
//删除最小值后输出
printf("\n删除最小值后La:");
input(La); return 0;
}
6、编写函数判断小括号是否匹配。
分析：由于限定了只有小括号，故不需要栈来实现
代码：
#include <stdio.h>
#include <stdlib.h> int ismarry(const char *str)
{
int top=-1;
char c; while(*str)
{
if(*str == '(')++top;
if(*str == ')')
{
if(top == -1)return -1; //若此时指针指向“）”，top = -1,这说明前面的已匹配成功
top--;
}
str++;
}
if(top == -1)return 0;
return -1;
} int main()
{
char str[] = "((())))";
if(ismarry(str) == 0)
printf("匹配成功！");
else
printf("匹配不成功！");
return 0;
}
7、【】对多个字符串进行字典排序
对一个字符串进行字典排序：
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h> void Sort(char parr[],int n)
{
int i,j;
char *str1, *str2;
//冒泡排序
for(i=0; i<n-1; i++)
{
for(j=i+1; j<=n-1; j++)
{
str1=parr[i];
str2=parr[j];
while(((*str1) && (*str2) && (*str1==*str2)) == 1)
{
str1++;
str2++;
}
if(*str1-*str2>0)
{
char *temp = parr[i];
parr[i] = parr[j];
parr[j] = temp;
}
}
}
}
int main()
{
char ch[] = "helloworld!";
printf("排序前：%s",ch); //字符串输出
Sort(ch,strlen(ch));
printf("\n排序后：%s",ch); //字符串输出
return 0;
}对多个字符串按字典顺序排序
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h> //对数组内前n个字符串进行字典排序
int main()
{
char *str[] = {"hello","world","shao","hang"}; //指针数组
int i,j,n;
char *temp; scanf("%d",&n);
for(i =0; i < n-1; i++)
{
for(j = i+1; j <n; j++)
{
//strcmp(str1,str2)，比较函数，若str1 > str2，则返回正数
if(strcmp(str[i],str[j]) > 0)
{
temp = str[j];
str[j] = str[i];
str[i] = temp;
}
}
}
for(i = 0;i < n;i++)
{
printf("%s\t",str[i]);
}
return 0;
}
8、【不懂】编写一个函数，使之能完成以下功能：利用递归方法找出一个数组中的最大值和最小值
要求递归调用函数的格式如下：MinMaxValue(arr,n,&max,&min)，其中arr是给定的数组，n是数组的个数，max、min分别是最大值和最小值
代码：
void MinMaxValue(int arr[], int n, int *max, int *min)
{
if(n==1)
{
*max = arr[0];
*min = arr[0];
}
else
{
int _max=arr[0], _min=arr[0];
MinMaxValue(arr+1, n-1, max, min);
if(*max<_max)*max=_max;
if(*min>_min)*min=_min;
}
}
9、有两字符数组s和t，求t在s中出现第一次的开始位置，如果没有则输出“No”，有则输出开始位置
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h> int start(char s[],char t[])
{
int s_length = strlen(s);
int i;
char *str1, *str2;
for(i=0; i<s_length; i++)
{
str1 = s+i;
str2 = t;
while(*str1 && *str2 && *str1==*str2)str1++,str2++; //str1与str2相同，
if(*str1-*str2 == *str1) //str2为空，判断str2在sre1中
{
printf("%d",i);
return 0;
} }
printf("NO!\n");
return -1;
}
int main()
{
char a[] = "helloworld",b[] = "o";
start(a,b);
return 0;
}
最新文章
- URL、URI和URN三者之间的区别
- Objective－C（ 语法二）
- Linux驱动开发学习笔记(1)：LINUX驱动版本的hello world
- iOS之微博UI实例--拟物化设计(成功了90%)
- First & First
- 基于jquery左侧带选项卡切换的焦点图
- Mac 系统下安装 MySql
- DB天气app冲刺第二天
- VJP1100 加分二叉树（树形DP）
- 源码安装apache及配置转发
- Equinox OSGi应用嵌入Jersey框架搭建REST服务
- [UE4]瞬移前后屏幕亮度变化，Get Player Camera Manager.Start Camera Fade
- cocoapods 安装中出的太多问题
- 快速排序的java实现
- CodeForces 113B Petr#
- wdcp环境redis的位置
- 团队作业——Beta冲刺4
- [C语言]声明解析器cdecl修改版
- 被动式pocscan扫描神器搭建
- VirtualBox安装虚拟机全过程