1. 从键盘输入10个整数建立一个顺序表,编程求这10个整数的最大值和次大值并输出。
答:程序如下所示:
思路提示:将10个数字先排序,若由小到大排序,则最大值和次大值分别对应排序后的数组中最后一个和倒数第二个;若由大到小排序,则最大值和最小值分别对应排序后的数组中第一个和第二个。
#include<stdio.h>
int main(){
void select_sort(int arr[],int n);
int arr[10] = {0};
for (int i = 0; i < 10; i++) {
printf("请输入第%d个元素:",i+1);
scanf("%d",&arr[i]);
}
select_sort(arr, 10);
printf("最大值为:%d\n",arr[9]);
printf("此大值为:%d\n",arr[8]);
return 0;
}
// 选择排序
void select_sort(int a[],int n){
for(int i=0; i<n-1; i++){
int min_index = i;
for(int j=i+1; j<n; j++){
if(a[j] < a[min_index]){
min_index = j;
}
}
if( i != min_index){
int temp = a[i];
a[i] = a[min_index];
a[min_index] = temp;
}
}
}
2. 从键盘输入10个整数到一个一维数组,采用起泡排序法对这10个整数进行从小到大排序,输出排序结果。
答:程序如下所示:
#include<stdio.h>
int main(){
void bubble_sort(int arr[],int n);
int arr[10];
printf("请输入数组元素:");
for (int i = 0; i < 10; i++) {
scanf("%d",&arr[i]);
}
printf("排序后的结果(由大到小)为:");
bubble_sort(arr, 10);
for (int i =0; i < 10; i++) {
printf("%2d",arr[i]);
}
printf("\n");
return 0;
}
// 起泡排序法
void bubble_sort(int arr[],int n){
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-1-i; j++) {
if(arr[j] <= arr[j+1]){
int temp;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
3. 编程判定一棵二叉树是否为二叉排序树。(假定二叉树的每个节点的数据域都是整数)
答:程序如下所示:
思路:判断一棵二叉树是不是二叉排序树?二叉排序树的特点是,若左子树非空,则左子树上结点的值均小于根结点的值;若右子树非空,则右子树上结点的值均大于根结点的值。所以根据这一特点,可以看出二叉排序树的中序遍历是一个递增序列。
#include<stdio.h>
#include<stdlib.h>
#define MIN -256
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;
int prev = MIN;
int flag = true;
int main(){
bool InOrderTraverse(BiTree T);
void CreateBiTree(BiTree * T);
BiTree root;
printf("请输入数据:\n");
CreateBiTree(&root);
bool flag = InOrderTraverse(root);
if(flag){
printf("该二叉树是排序二叉树\n");
}else{
printf("该二叉树不是排序二叉树\n");
}
return 0;
}
bool InOrderTraverse(BiTree T){
if(T->lchild != NULL && flag){
InOrderTraverse(T->lchild);
}
if(T->data < prev){
flag = false;
}
prev = T->data;
if(T->rchild != NULL && flag){
InOrderTraverse(T->rchild);
}
return flag;
}
// 二叉树的建立
void CreateBiTree(BiTree * T){
int data;
scanf("%d",&data);
if(data == -1){
*T=NULL;
}else{
*T=(BiTree)malloc(sizeof(BiTNode));
}
if(!*T){
return ;
}else{
(*T)->data=data;
//构造左子树
CreateBiTree(&(*T)->lchild);
//构造右子树
CreateBiTree(&(*T)->rchild);
}
}
4. 假设以不带头节点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针。编程实现队列的入队和出队操作。
答:程序如下所示:
#include<stdio.h>
#include<stdlib.h>
struct CycleList{
int data;
struct CycleList *next;
struct CycleList *rear;
};
// 建立循环链表
void createClist(CycleList *&L,int a[],int n) {
CycleList *temp,*node;
L = (CycleList *)malloc(sizeof(CycleList));
L->data = a[0];
L->next = NULL;
L->rear = NULL;
temp=L;
for(int i=1; i<n; i++) {
node=(CycleList *)malloc(sizeof(CycleList));
node->data = a[i];
temp->next = node;
temp = node;
}
temp->next = L;
L->rear = temp;
}
// 打印链表信息
void printList(CycleList *L) {
CycleList *temp;
temp=L;
while(true) {
printf("%d\t",temp->data);
temp = temp->next;
if(temp == L){
break;
}
}
printf("\n");
}
// 入队列
void enQueue(CycleList *&rear,int x) {
CycleList *newNode=(CycleList *)malloc(sizeof(CycleList));
newNode->data=x;
newNode->next=rear->next;
rear->next=newNode;
rear=newNode;
}
// 出队列
int deQueue(CycleList *&rear,int &x) {
CycleList *tempDelNode;
if(rear->next==rear) {
return 0;
} else {
tempDelNode = rear->next;
x = tempDelNode->data;
rear->next = tempDelNode->next;
free(tempDelNode);
return 1;
}
}
int main() {
CycleList *list,*t1,*t2;
int x;
int a[]= {1,3,5,7,9};
createClist(list,a,5);
printf("原始数据:\n");
printList(list);
printf("入队数据为11:\n");
enQueue(list->rear,11);
printList(list);
printf("入队数据为22:\n");
enQueue(list->rear,22);
printList(list);
printf("入队数据为33:\n");
enQueue(list->rear,33);
printList(list);
deQueue(list->rear,x);
printf("第一个出队元素为:%d\n",x);
printf("剩余元素分别为:\n");
printList(list->rear->next);
return 0;
}
5. 以二叉链表为存储结构,在二叉树中删除以值x
为根结点的子树。
答:程序如下所示:
思路:对二叉链表进行遍历,在遍历的过程中查找结点x
并记载其双亲,然后将结点x
的双亲结点中指向结点x
的指针置空。
// p为全局变量,初值为空
void Delete(BitNode *root,T x){
if(root){
if(root->data == x){
if(!p){
root == NULL;
}else if(p->lchild==root){
p->lchild = NULL;
}else{
p->rchild = NULL;
}
}else{
p = root;
Delete(root->lchild,x);
Delete(root->rchild,x);
}
}else{
printf("该树不存在!\n");
}
}
1. 已知数组A[n]
中的元素为整型,设计一个函数将这个数组调整为左右两部分,左边所有元素为负数,右边所有元素为正数。数组和元素个数n
作为参数传入。
#include<iostream>
#define NUM 10
using namespace std;
// 交换两元素值
void swap(int *arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 划分元素
void paritition(int *arr, int n){
int left = 0;
int right = n - 1;
while(left < right){
while(left < right && arr[left] < 0){
left++;
}
while(left < right && arr[right] > 0){
right--;
}
if(left < right){
swap(arr, left, right);
}
}
}
int main(){
int arr[NUM] = {0};
cout<<"请输入数组元素:\n";
for (int i = 0; i < NUM; i++) {
cin >> arr[i];
}
paritition(arr, NUM);
for(int i = 0; i < NUM; i ++){
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
2. 已知一个顺序表L
是一个结构体,包括一个一维数组和顺序表长度。编写一个函数,从该顺序表一维数组中删除自第i
个元素开始的k
个元素。顺序表、i
、k
都作为参数传入。
void deleteItems(int arr[],int i,int k){
int length = strlen(arr);
int array[length-k];
// i表示要删除元素的起始位置,k表示删除的个数
for (int index = 0;index < length; index++) {
if(index < i){
array[index] = arr[index];
}else{
array[index] = arr[index+k];
}
}
for (int index = 0;index < length-k; index++) {
printf("%d\t",array[index]);
}
}
#include <stdio.h>
int main(){
int a[5] = {1,2,3,4,5};
int b[4];
int Index;
int i;
int num;
printf("请输入要删除的值的下标:");
scanf("%d", &Index);
printf("请输入要删除元素的个数:");
scanf("%d",&num);
for (i=0; i<5; ++i){
if (i < Index){
b[i] = a[i];
}
else{
b[i] = a[i+num];
}
}
for (i=0; i<5-num; ++i){
printf("%d\t", b[i]);
}
printf("\n");
return 0;
}
3. 编写完整的程序,包括main
函数或其他函数或类,单链表的结点使用类或结构定义均可,程序功能有:从键盘输入单链表的数据(整型,以-1结束),计算单链表中的数据的和并输出。
#include<stdio.h>
#include<stdlib.h>
struct student{
int data;
struct student *next;
};
// 输入链表数据
struct student *createList();
// 对所有数据求和
void sumList(struct student *head);
struct student *head = NULL;
int main(){
head = createList();
sumList(head);
return 0;
}
// 1. 输入数据
struct student *createList(){
struct student *head;//头节点
struct student *p1;//开辟新节点
struct student *p2;//与p1连接
int data,count=2;
head = NULL;
printf("请输入第1个数据:");
scanf("%d",&data);
while (data!=-1) {
p1 = (struct student*)malloc(sizeof(struct student));
p1->data = data;
p1->next = NULL;
if(head == NULL){
head = p1;
}else{
p2->next = p1;
}
p2 = p1;
printf("请输入第%d个数据:",count++);
scanf("%d",&data);
}
return head;
}
// 对所有数据求和
void sumList(struct student *head){
struct student *p;
int sum = 0;
if(head!=NULL){
printf("所有数据之和为:");
for(p=head;p!=NULL;p=p->next){
sum += p->data;
}
printf("sum=%d\n",sum);
}else{
printf("空链表!\n");
}
}
4. 写出二叉树前序遍历的非递归算法程序。
void PreOrderWithoutRecursion1(BTNode* root){
if (root == NULL){
return;
}
BTNode* p = root;
stack<BTNode*> s;
while (!s.empty() || p){
//边遍历边打印,并存入栈中,以后需要借助这些根节点(不要怀疑这种说法哦)进入右子树
while (p){
cout << setw(4) << p->data;
s.push(p);
p = p->lchild;
}
//当p为空时,说明根和左子树都遍历完了,该进入右子树了
if (!s.empty()){
p = s.top();
s.pop();
p = p->rchild;
}
}
cout << endl;
}
5. 编写完整的程序,包括main
函数和其他函数或类,程序功能有:从键盘输入一个无向图(最多10个顶点),求这个无向图中度为2的顶点并输出结果。
#include<stdio.h>
void AdjMatrix(int a[][9]);
char vextex[10] = {'1','2','3','4','5','6','7','8','9','10'};
char tempVex[10]={};//符合度为2的节点的数组
int N=0;//记录符合满度为2的数组中节点的个数
void count(int arc[][9]);
int main(){
// 1、简单解法。利用邻接矩阵存储节点的信息,
// 由于是无向无权图,所以图的度只需要遍历邻接矩阵每一行,不为0的点即为该节点的度
int arc[9][9]={0};//矩阵信息初始化;
AdjMatrix(arc);//调用函数传入矩阵用于输入边信息;
count(arc); //计算所有度为2的点;存储到新的数组中;
int i;
for(i=0;i<N;i++){
printf("符合度为2的节点为%c\n",tempVex[i]);
}
}
void count(int arc[][9]){
int i,j,k;
k=0;
int t[10]={0};//假设所有节点的度都是0;
for(i=0;i<9;i++){
for(j=0;j<9;j++){
if(i==j){
continue; //对角线是0,
}
// 只要不是-1就是有度
if(arc[i][j]!=-1 || arc[i][j]!=0){
t[i]++;
N++;
}
}
}
for(i=0;i<10;i++){
if(t[i]==2){
tempVex[i]=vextex[i];//把节点的名称复制给需要输出的数组;
}
}
}
void AdjMatrix(int arc[][9]){
int i,j;
char ch;
//初始化矩阵;
for(i=0;i<9;i++){
for(j=0;j<9;j++){
arc[i][j]=-1; //假设所有节点与节点直接的距离都是无限大;
}
}
for(i=0;i<9;i++){
for(j=0;j<9;j++){
printf("请输入%d个节点与第%d个节点的距离,无连接处用-1代表\n",i+1,j+1);
scanf("%d",&arc[i][j]);
}
}
}
1. 已知数组A[n]
中的元素为整型,设计一个函数将这个数组调整为左右两部分,左边所有元素为奇数,右边所有元素为偶数。数组和元素个数n
作为参数传入。
#include<iostream>
#define NUM 10
using namespace std;
// 交换两元素值
void swap(int *arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 划分元素
void paritition(int *arr, int n){
int left = 0;
int right = n - 1;
while(left < right){
while(left < right && arr[left]%2==1){
left++;
}
// 奇数
while(left < right && arr[right]%2==0){
right--;
}
// 偶数
if(left < right){
swap(arr, left, right);
}
}
}
int main(){
int arr[NUM] = {0};
cout<<"请输入数组元素:\n";
for (int i = 0; i < NUM; i++) {
cin >> arr[i];
}
paritition(arr, NUM);
for(int i = 0; i < NUM; i ++){
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
2. 已知单链表中各结点的元素值为整型且递增有序,设计一个函数删除链表中所有大于mink
且小于maxk
的元素,并释放被删结点的存储空间,链表头指针和mink
、maxk
作为参数传入。
#include<stdio.h>
#include<stdlib.h>
#define N 5
typedef struct node{
int data;
struct node *next;
}node,*LinkList;
// 链表初始化
int LinkList_Init(LinkList &L){
L=(LinkList)malloc(sizeof(node));
if(L==NULL)
exit(-1);
L->next=NULL;
return 1;
}
// 建立链表
void LinkList_create(LinkList &L,int n){
int i;
node *p,*q;
q=L;
printf("请输入递增的链表元素:");
for(i=0;i<n;i++){
p=(LinkList)malloc(sizeof(node));
scanf("%d",&p->data);
p->next=NULL;
q->next=p;
q=p;
}
}
// 输出链表
void LinkList_print(LinkList &L){
node *p;
p=L->next;
printf("单链表的元素为:");
while(p){
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
//
void LinkList_delete(LinkList &L,int mink,int maxk){
node *q,*t,*p,*r;
p = L->next;
// 查找第一个值大于mink的结点
while (p!=NULL&& p->data <= mink){
t = p;
p = p->next;
}
if (p!=NULL){
// 当数小于maxk的时候一直往下找
while (p && p->data < maxk){
p = p->next;
}
q = t->next;
t->next = p;
// 释放节点空间
while (q != p){
r = q->next;
delete q;
q = r;
}
}
}
int main(){
LinkList L;
int n=N;
int mink,maxk;
LinkList_Init(L);
LinkList_create(L,n);
LinkList_print(L);
printf("请输入mink和maxk的值:");
scanf("%d %d",&mink,&maxk);
// 删除介于mink和maxk中间的值
LinkList_delete(L,mink,maxk);
LinkList_print(L);
return 0;
}
3. 设计一个函数统计出单链表HL
中结点的值等于给定值x
的结点数,链表头指针和x
作为参数传入。
#include<stdio.h>
#include<stdlib.h>
struct student{
int data;
struct student *next;
};
// 输入链表数据
struct student *createList();
// 对所有数据求和
void countX(struct student *head,int x);
struct student *head = NULL;
int main(){
int num;
printf("请输入num值:");
scanf("%d",&num);
head = createList();
countX(head,num);
return 0;
}
// 1. 输入数据
struct student *createList(){
struct student *head;//头节点
struct student *p1;//开辟新节点
struct student *p2;//与p1连接
int data,count=2;
head = NULL;
printf("请输入第1个数据:");
scanf("%d",&data);
while (data!=-1) {
p1 = (struct student*)malloc(sizeof(struct student));
p1->data = data;
p1->next = NULL;
if(head == NULL){
head = p1;
}else{
p2->next = p1;
}
p2 = p1;
printf("请输入第%d个数据:",count++);
scanf("%d",&data);
}
return head;
}
// 对所有数据求和
void countX(struct student *head,int x){
struct student *p;
int num = 0;
if(head!=NULL){
for(p=head;p!=NULL;p=p->next){
if(p->data == x){
num++;
}
}
printf("%d出现的次数为%d\n",x,num);
}else{
printf("空链表!\n");
}
}
4. 写出二叉树前序遍历的递归算法。
// 前序遍历
void preTreverse(struct BTree *T){
if(T){
printf("%d ",T->data);
preTreverse(T->left);
preTreverse(T->right);
}
}
// 中序遍历
void inTreverse(struct BTree *T){
if(T){
inTreverse(T->left);
printf("%d ",T->data);
inTreverse(T->right);
}
}
// 后序遍历
void postTreverse(struct BTree *T){
if(T){
postTreverse(T->left);
postTreverse(T->right);
printf("%d ",T->data);
}
}
5. 设计一个函数,求用邻接矩阵表示的有向图中序号为num
的顶点的度(入度和出度之和),其中邻接矩阵、有向图的顶点数、num
的值作为参数传入。
#include<stdio.h>
#include<Stdlib.h>
#include<string.h>
#define MAXV 100 //最大顶点个数;
#define INF 32767 //定义无穷
#define isLetter(a) ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
//typedef InfoType int; //假设顶点的其他类型是权重,且是int类型
//typedef struct{
// char no; //顶点的编号 字符型
// InfoType info; //顶点的其他信息;
//}VertexType; //顶点的类型
typedef struct{
int edges[MAXV][MAXV]; //邻接矩阵数组;
int vexnum; //顶点数
int edgnum; //,边数;
// VertexType vexs[MAXV]; //存放顶点信息;
char vexs[MAXV]; //顶点信息
}Graph,*PGraph; //完整的图邻接矩阵类型;
int count(MatGraph G);
/*
* 读取一个输入字符
*/
static char read_char()
{
char ch;
do {
ch = getchar();
} while(!isLetter(ch));
return ch;
}
/*
* 返回ch在邻接矩阵中的位置
*/
static int get_position(Graph g, char ch)
{
int i;
for(i=0; i<g.vexnum; i++)
if(g.vexs[i]==ch)
return i;
return -1;
}
Graph *PG // 指向图的指针
int main()
{
Graph* create_graph();
PG = create_graph();
printf("请输入要查找顶点的编号\n");
char ch;
ch = read_char();
int n = count(*PG->edges.*PG->vexnum,ch)
if(n!=-1)
{
printf("顶点%c的度是%d\n",ch,n);
}
else{
printf("未找到\n");
}
return 0;
}
int count(int edges[][PG->edgnum],int vexnum,char ch){
int i,j;
int flag=0;
int sum=0;
for(i=0;i<PG->vexnum;i++)
{
if(PG->vex[i]==ch)
{
flag=1;
for(j=0;j<PG->edgnum;j++)
{
if(deges[i][j]==1)
{
sum+=1;
}
}
}
}
if(flag)
{
return sum;
}
return -1;
}
/*
* 创建图(自己输入)
*/
Graph* create_graph()
{
char c1, c2;
int v, e;
int i, p1, p2;
Graph* pG;
// 输入"顶点数"和"边数"
printf("input vertex number: ");
scanf("%d", &v);
printf("input edge number: ");
scanf("%d", &e);
if ( v < 1 || e < 1 || (e > (v * (v-1))))
{
printf("input error: invalid parameters!\n");
return NULL;
}
if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
return NULL;
memset(pG, 0, sizeof(Graph));
// 初始化"顶点数"和"边数"
pG->vexnum = v;
pG->edgnum = e;
// 初始化"顶点"
for (i = 0; i < pG->vexnum; i++)
{
printf("vertex(%d): ", i);
pG->vexs[i] = read_char();
}
// 初始化"边"
for (i = 0; i < pG->edgnum; i++)
{
// 读取边的起始顶点和结束顶点
printf("edge(%d):", i);
c1 = read_char();
c2 = read_char();
p1 = get_position(*pG, c1);
p2 = get_position(*pG, c2);
if (p1==-1 || p2==-1)
{
printf("input error: invalid edge!\n");
free(pG);
return NULL;
}
pG->matrix[p1][p2] = 1;
}
return pG;
}
1. 假设顺序表L
中的元素递增排列,设计算法在顺序表中插入元素x
,要求插入后仍保持其递增有序性。
#include <stdio.h>
#define M 100
typedef struct{
int elem[M];
int length;
}List;
void Input(List *L){
int d,i=0;
// 顺序表的结束标志为-1
scanf("%d",&d);
while(d!=-1){
L->elem[i]=d;
i++;
scanf("%d",&d);
}
L->length=i-1;
}
void addNode(List *list,int x){
int i,k,temp;
for(i=0;i <= list->length;i++){
if(list->elem[i] < x)
list->elem[i] = list->elem[i];
else{
k=i;
break;
}
}
// 后移元素
for(i = list->length;i >= k;i--){
list->elem[i+1] = list->elem[i];
}
// 将待插元素插入
list->elem[k]=x;
// 长度增加
list->length++;
}
// 输出列表顺序表
void Output(List *list){
for(int i=0;i <= list->length;i++){
printf("%d ",list->elem[i]);
}
}
int main(){
int x;
List LA;
printf("请输入待插入元素:");
scanf("%d",&x);
printf("请输入顺序表元素(以-1结束):");
Input(&LA);
addNode(&LA,x);
printf("插入元素之后顺序表为:\n");
Output(&LA);
return 0;
}
2. 设计算法将递增顺序表A
、B
中的元素合并成一个递增有序顺序表C
。
#include<stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct list{
int data[MAXSIZE];
int len;
}SqList;
void Mergelist_sq(SqList La, SqList Lb, SqList& Lc){
int i = 0, j = 0, k = 0;
// la == lb
while (i < La.len && j < Lb.len){
if (La.data[i] < Lb.data[j]){
Lc.data[k] = La.data[i];
i++;
k++;
}
else if (La.data[i] > Lb.data[j]){
Lc.data[k] = Lb.data[j];
j++;
k++;
}
else{
Lc.data[k] = La.data[i]; i++; k++;
Lc.data[k] = Lb.data[j]; j++; k++;
}
}
// la > lb
while (i < La.len){
Lc.data[k] = La.data[i]; i++; k++;
}
// la < lb
while (j < Lb.len){
Lc.data[k] = Lb.data[j]; j++; k++;
}
Lc.len = k;
}
int main(){
SqList sqa, sqb, sqc;//定义结构体变量
int a, b;
// 顺序表A
printf("请输入顺序表A的元素个数:");
scanf("%d",&a);
printf("请输入顺序表A的数据:");
for (int i = 0; i < a; i++){
scanf("%d", &sqa.data[i]);
}
sqa.len = a;
// 顺序表B
printf("请输入顺序表B的元素个数:");
scanf("%d",&b);
printf("请输入顺序表B的数据:");
for (int j = 0; j < b; j++){
scanf("%d", &sqb.data[j]);
}
sqb.len = b;
// 合并有序表
Mergelist_sq(sqa, sqb, sqc);
printf("A顺序表的元素为:");
for (int i = 0; i <sqa.len; i++){
printf("%2d", sqa.data[i]);
}
printf("\n");
printf("B顺序表的元素为:");
for (int j = 0; j <sqb.len; j++){
printf("%2d", sqb.data[j]);
}
printf("\n");
printf("C顺序表的元素为:");
for (int n = 0; n < sqc.len; n++){
printf("%2d", sqc.data[n]);
}
printf("\n");
return 0;
}
3. 已知递增有序链表A
、B
分别表示集合A
、B
,设计算法实现集合C
=A
∩B
,要求C
是链表且仍递增有序。
#include<stdio.h>
#include<stdlib.h>
// 头节点初始化
int InitHeadNode(struct Node* &, struct Node* &);
// 尾插法插入节点
int RearInsert(struct Node* &, struct Node* &, short);
// 判断元素是否在表中
int IsElemIn(struct Node* &, short);
// 找出两个表中的公共元素
void FindNodeIn1andIn2(struct Node* &, struct Node* &, struct Node* &, struct Node* &);
// 遍历链表
void Traversal(struct Node* &);
struct Node{
short data;
struct Node *next;
};
int main(){
struct Node *head1;
struct Node *rear1;
struct Node *head2;
struct Node *rear2;
struct Node *head3;
struct Node *rear3;
/* 初始化1#链表的头结点 */
if(InitHeadNode(head1, rear1) == -1){
/* 头结点申请失败, 程序直接结束 */
exit(0);
}
int temp;
/* 向链表中插入数据结点 */
printf("请输入顺序表1数据(以-1结束):");
while(1){
while(scanf("%d", &temp) != 1){
while(getchar() != '\n') ;
printf("请输入合法数据.\n");
}
if(temp == -1){
break;
}
if(RearInsert(head1, rear1, temp) == -1){
/* 申请结点失败 */
exit(0);
}
}
/* 初始化2#链表的头结点 */
if(InitHeadNode(head2, rear2) == -1){
/* 头结点申请失败, 程序直接结束 */
exit(0);
}
/* 向链表中插入数据结点 */
printf("请输入顺序表2数据(以-1结束):");
while(1){
while(scanf("%d", &temp) != 1){
while(getchar() != '\n') ;
printf("请输入合法数据.\n");
}
if(temp == -1){
break;
}
if(RearInsert(head2, rear2, temp) == -1){
/* 申请结点失败 */
exit(0);
}
}
/* 初始化3#链表的头结点 */
if(InitHeadNode(head3, rear3) == -1){
/* 头结点申请失败, 程序直接结束 */
exit(0);
}
/* 至此, 三个链表均已初始化 */
FindNodeIn1andIn2(head1, head2, head3, rear3);
// 遍历链表
printf("两个链表中的公共元素为:\n");
Traversal(head3);
return 0;
}
/* 判断数据元素value是否在链表中 */
int IsElemIn(struct Node* &head, short value){
struct Node *p = head -> next;
while(p != NULL){
if(p -> data == value){
/* 找到数据元素value */
return 1;
}
p = p -> next;
}
/* 未找到数据元素value */
return -1;
}
/* 求出1#集合和2#集合的交集, 并将结果保存到3#链表中 */
void FindNodeIn1andIn2(struct Node* &head1, struct Node* &head2, struct Node* &head3, struct Node* &rear3){
struct Node *p2 = head2 -> next;
/* */
while(p2 != NULL){
if(IsElemIn(head1, p2 -> data) == 1){
/* 将结果保存到3#链表中 */
RearInsert(head3, rear3, p2 -> data);
}
p2 = p2 -> next;
}
}
/* 遍历单链表并输出 */
void Traversal(struct Node* &head){
struct Node *p = head -> next;
while(p != NULL){
printf("%3d", p -> data);
p = p -> next;
}
putchar('\n');
}
/* 尾插法 */
int RearInsert(struct Node* &head, struct Node* &rear, short value){
struct Node *p = (struct Node*)malloc(sizeof(struct Node));
if(p != NULL){
/* 结点申请成功 */
rear -> next = p;
p -> next = NULL;
p -> data = value;
rear = p;
return 1;
}
else{
/* 结点申请失败 */
return -1;
}
}
/* 初始化头结点 */
int InitHeadNode(struct Node* &head, struct Node* &rear){
struct Node *p = (struct Node*)malloc(sizeof(struct Node));
if(p != NULL){
/* 头结点申请成功 */
head = p;
head -> data = 0;
head -> next = NULL;
rear = head;
return 1;
}
else{
/* 头结点申请失败 */
return -1;
}
}
4. 设计一个递归算法按中序次序输出二叉树T
中度为1的结点的值。
void InorderPrintNodes( BiTree T)
{
if(T==NULL) return ;
if(!T->lchild&&!T->rchild) return ;
else if(T)
{
InorderPrintNodes(T->lchild);
if(!T->lchild||!T->rchild)
printf(" %c",T->data);
InorderPrintNodes(T->rchild);
}
}
5. 写出冒泡(起泡)排序算法的程序代码。
#include<stdio.h>
int main(){
int arr[10],t;
printf("请输入数组元素:");
for (int i = 0; i < 10; i++) {
scanf("%d",&arr[i]);
}
printf("顺序输出结果为:");
for (int i = 0; i < 10; i++) {
printf("%2d",arr[i]);
}
printf("\n");
printf("排序后的结果(由小到大)为:");
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9-i; j++) {
if(arr[j]>=arr[j+1]){
t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
}
for (int i =0; i < 10; i++) {
printf("%2d",arr[i]);
}
printf("\n");
return 0;
}