2020编程题
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]); return0; } // 选择排序 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"); return0; } // 起泡排序法 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 typedefstruct 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"); } return0; } 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) { return0; } else { tempDelNode = rear->next; x = tempDelNode->data; rear->next = tempDelNode->next; free(tempDelNode); return1; } } 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); return0; }
5. 以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树。
答：程序如下所示：
思路：对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲，然后将结点x的双亲结点中指向结点x的指针置空。
// p为全局变量，初值为空 void Delete(BitNode *root,T x){ if(root){ if(root->data == x){ if(!p){ root == NULL; }elseif(p->lchild==root){ p->lchild = NULL; }else{ p->rchild = NULL; } }else{ p = root; Delete(root->lchild,x); Delete(root->rchild,x); } }else{ printf("该树不存在!\n"); } }
2019编程题
1. 已知数组A[n]中的元素为整型，设计一个函数将这个数组调整为左右两部分，左边所有元素为负数，右边所有元素为正数。数组和元素个数n作为参数传入。
#include<iostream> #define NUM 10 usingnamespacestd; // 交换两元素值 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; return0; }
2. 已知一个顺序表L是一个结构体，包括一个一维数组和顺序表长度。编写一个函数，从该顺序表一维数组中删除自第i个元素开始的k个元素。顺序表、i、k都作为参数传入。
void deleteItems(int arr[],int i,int k){ int length = strlen(arr); intarray[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"); return0; }
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); return0; } // 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]); } } }
2018编程题
1. 已知数组A[n]中的元素为整型，设计一个函数将这个数组调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数。数组和元素个数n作为参数传入。
#include<iostream> #define NUM 10 usingnamespacestd; // 交换两元素值 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; return0; }
2. 已知单链表中各结点的元素值为整型且递增有序，设计一个函数删除链表中所有大于mink且小于maxk的元素，并释放被删结点的存储空间，链表头指针和mink、maxk作为参数传入。
#include<stdio.h> #include<stdlib.h> #define N 5 typedefstruct 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; return1; } // 建立链表 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); return0; }
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); return0; } // 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; //顶点的类型 typedefstruct{ 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"); } return0; } 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"); returnNULL; } if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL ) returnNULL; 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); returnNULL; } pG->matrix[p1][p2] = 1; } return pG; }
2017编程题
1. 假设顺序表L中的元素递增排列，设计算法在顺序表中插入元素x，要求插入后仍保持其递增有序性。
#include <stdio.h> #define M 100 typedefstruct{ 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); return0; }
2. 设计算法将递增顺序表A、B中的元素合并成一个递增有序顺序表C。
#include<stdio.h> #include <stdlib.h> #define MAXSIZE 100 typedefstruct 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++; } elseif (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"); return0; }
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); return0; } /* 判断数据元素value是否在链表中 */ int IsElemIn(struct Node* &head, short value){ struct Node *p = head -> next; while(p != NULL){ if(p -> data == value){ /* 找到数据元素value */ return1; } 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; return1; } 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; return1; } else{ /* 头结点申请失败 */ return-1; } }
4. 设计一个递归算法按中序次序输出二叉树T中度为1的结点的值。
void InorderPrintNodes( BiTree T) { if(T==NULL) return ; if(!T->lchild&&!T->rchild) return ; elseif(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"); return0; }
