《数据结构》上机练习题1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。

2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”；否则，将它插入到序列中使它仍然有序，并输出排序后的序列。

3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出“NO”，否则，将它从序列中删除它，并输出删除后的序列。

4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果是有序的。

5、从键盘输入一组任意数据，建立一个包含所有输入数据的单向循环链表，并从链表的任意开始，依次输出该链表中的所有结点。

10、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果不在，则输出“NO“，否则，将它从链表中删除，并输出删除后的链表。

11、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链头，并输出插入后的链表。

12、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链尾，并输出插入后的链表。

13、编写栈的压栈push、弹栈pop函数，从键盘输入一组数据，逐个元素压入堆栈，然后再逐个从栈中弹出它们并输出。

14、编写栈的压栈push、弹栈pop函数，用它判别（）的匹配问题。

15、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树中序遍历的结果。

16、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树先序遍历的结果。

17、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树后序遍历的结果。

18、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树的总结点数。

19、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树叶子结点数。

20、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出此二叉树的高度。

21、给出一个无向图的邻接矩阵，输出各个顶点的度。

22、给出一个有向图的邻接矩阵，输出各个顶点的入度与出度。

23、输入一个有序序列，利用折半查找来查找一个数是否在序列中，如在，则输出其位置，否则输出“NO”。

24、用插入排序方法对一组数据进行排序，并输出每趟排序的结果。

25、用选择排序方法对一组数据进行排序，并输出每趟排序的结果。

26、用希尔（SHELL）排序方法对一组数据进行排序，并输出每趟排序的结果。

27、用快速排序方法对一组数据进行排序，并输出每趟排序的结果。

．答案：1. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0//链表的存储结构typedef struct LNode{int data;struct LNode *next;}LNode,*list;//顺序创建链表void creatList(list &l,int n){int i;list p,q;l=(list)malloc(sizeof(LNode)); //开辟头结点p=l; //指针p指向头结点for(i=0;i<n;i++){q=(list)malloc(sizeof(LNode)); //新的结点scanf("%d",&q->data);p->next=q; //p的下一个结点指向新开辟的结点qp=q; //将p指针指向q}p->next=NULL;}//归并排序void mergeList(list &la,list &lb,list &lc){ //将已经排好序的la,lb中的数重新排列成有序（非递减）list pa,pb,pc;pa=la->next;pb=lb->next;lc=pc=la; //默认将la做为lc的头结点（lb亦可）while(pa&&pb){ //让pc接到数据小的结点上，直到pa,pb两者有一指向空结点if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; }else{ pc->next=pb;pc=pb;pb=pb->next; }}pc->next=pa?pa:pb; //如果最后la有剩余结点，即将其直接加入到lc中，反之将lb的剩余结点加到lc中free(lb);}void printList(list l){list p;p=l->next;while(p){ printf("%d ",p->data);p=p->next;}}void main(){list la,lb,lc;printf("创建两个含%d个元素的链表，请输入：\n",N);creatList(la,N);creatList(lb,N);mergeList(la,lb,lc);printList(lc);}2. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0//链表的存储结构typedef struct LNode{int data;struct LNode *next;}LNode,*list;//创建链表void creatList(list &l,int n){list p,q;l=(list)malloc(sizeof(LNode));p=l;for(int i=0;i<n;i++){q=(list)malloc(sizeof(LNode));scanf("%d",&q->data);p->next=q;}p->next=NULL;}//判断元素e是否在链表中int inList(list l,int e){list p;p=l->next;while(p){if(p->data==e)return OK; //发现在里面，返回真值p=p->next; //否则指针后移,继续找}return ERROR; //未找到，返回假值（没有执行return OK;语句）}//插入元素void insertList(list &l,int &e){list p,q,s; //q为新插入的元素开辟一个存储空间的指针，s为p前一个指针，方便插入p=l->next;s=l;while(p){if(e<=p->data){//发现要插入的元素e比后面的小,开辟空间，并将e放入空间的数据域中q=(list)malloc(sizeof(LNode));q->data=e;while(s->next!=p) s=s->next; //找到p前的一个指针q->next=p; // 画图好好理解--->s--->p--->s->next=q; // q--->break;}p=p->next;}}//输出链表void printList(list l){list p;while(p){ printf("%d ",p->data); p=p->next;}}void main(){list l;int e;printf("创建%d个元素的链表，请输入%d个元素：\n",N,N);creatList(l,N);printf("请输入要判断的元素：");scanf("%d",&e);if(inList(l,e))printf("YES ");else{insertList(l,e);printList(l);}}3. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0//链表的存储结构typedef struct LNode{int data;struct LNode *next;}LNode,*list;//创建链表void creatList(list &l,int n){list p,q;l=(list)malloc(sizeof(LNode));p=l;for(int i=0;i<n;i++){q=(list)malloc(sizeof(LNode));scanf("%d",&q->data);p->next=q;p=q;}p->next=NULL;}//判断元素e是否在链表中int insertDeleteList(list l,int e){list p,q;p=l->next; q=l;while(p){if(p->data==e){while(q->next!=p) q=q->next; //找到p前一个结点，方便删除操作q->next=p->next; //删除结点pfree(p);return OK;} //发现在里面，返回真值p=p->next; //否则指针后移,继续找}return ERROR; //未找到，返回假值（没有执行return OK;语句）}//输出链表void printList(list l){list p;p=l->next;while(p){ printf("%d ",p->data); p=p->next;}}void main(){list l;int e;printf("创建%d个元素的链表，请输入%d个元素：\n",N,N);creatList(l,N);printf("请输入要判断的元素");scanf("%d",&e);if(!insertDeleteList(l,e))printf("NO ");elseprintList(l);}4. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0//链表的存储结构typedef struct LNode{int data;struct LNode *next;}LNode,*list;//创建链表void creatList(list &l,int n){list p,q;l=(list)malloc(sizeof(LNode));p=l;for(int i=0;i<n;i++){q=(list)malloc(sizeof(LNode));scanf("%d",&q->data);p->next=q;p=q;}p->next=NULL;}//链表排序void sortList(list &l){list p,q,r; //p标记排序的轮数int chang; //用于交换结点中的数据p=l->next;while(p->next!=NULL){q=l->next; //每次比较从首结点开始while(q->next!=NULL){r=q->next;if(q->data>r->data) //发现前一个比后一个大，交换数据{ chang=q->data;q->data=r->data;r->data=chang; }q=q->next; //相邻间下一个比较}p=p->next; //下一轮比较}}//输出链表void printList(list l){list p;p=l->next;while(p){ printf("%d ",p->data); p=p->next;}}void main(){list l;printf("创建%d个元素的链表，请输入%d个元素：\n",N,N);creatList(l,N);sortList(l);printList(l);}5. #include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0//链表的存储结构typedef struct LNode{int data;struct LNode *next;}LNode,*list;//创建链表void creatList(list &l,int n){list p,q;l=(list)malloc(sizeof(LNode));scanf("%d",&l->data); //头结点也添加元素，方便输出p=l;for(int i=1;i<n;i++){q=(list)malloc(sizeof(LNode));scanf("%d",&q->data);p->next=q;p=q;}p->next=l; //让最后一个p->next指针指向头结点，构成循环链表}//输出链表void printList(list l,int pos){list p,q;int i;p=l;for(i=1;i<pos-1;i++) p=p->next; //找到指定位置的前一个位置q=p->next;do{if(pos==1) {printf("%d ",p->data); p=p->next;} //如果指定位置为1，即按原样输出else {p=p->next; printf("%d ",p->data);} //不然，p先移到指定的位置，输出其数据}while(p->next!=q); //结束条件（p移到的下一个位置不是q，即不是最初的p,完成循环输出）}void main(){list l;int pos;printf("创建%d个元素的循环链表，请输入%d个元素：\n",N,N);creatList(l,N);printf("请指明从第几个位置输出循环链表中的元素：");scanf("%d",&pos);while(pos<=0||pos>N){printf("输入的位置不存在，请重新输入... ");scanf("%d",&pos);}printList(l,pos);}11#include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0//链表的存储结构typedef struct LNode{int data;struct LNode *next;}LNode,*list;//创建链表void creatList(list &l,int n){list p,q;l=(list)malloc(sizeof(LNode));scanf("%d",&l->data); //头结点也添加元素，方便输出p=l;for(int i=1;i<n;i++){q=(list)malloc(sizeof(LNode));scanf("%d",&q->data);p->next=q;p=q;}p->next=l; //让最后一个p->next指针指向头结点，构成循环链表}//输出链表void printList(list l,int pos){list p,q;int i;for(i=1;i<pos-1;i++) p=p->next; //找到指定位置的前一个位置q=p->next;do{if(pos==1) {printf("%d ",p->data); p=p->next;} //如果指定位置为1，即按原样输出else {p=p->next; printf("%d ",p->data);} //不然，p先移到指定的位置，输出其数据}while(p->next!=q); //结束条件（p移到的下一个位置不是q，即不是最初的p,完成循环输出）}void main(){list l;int pos;printf("创建%d个元素的循环链表，请输入%d个元素：\n",N,N);creatList(l,N);printf("请指明从第几个位置输出循环链表中的元素：");scanf("%d",&pos);while(pos<=0||pos>N){printf("输入的位置不存在，请重新输入... ");scanf("%d",&pos);}printList(l,pos);}12#include <stdio.h>#include <stdlib.h>#define N 5#define NULL 0#define OK 1#define ERROR 0//链表的存储结构typedef struct LNode{int data;struct LNode *next;}LNode,*list;//创建链表void creatList(list &l,int n){l=(list)malloc(sizeof(LNode));p=l;for(int i=0;i<n;i++){q=(list)malloc(sizeof(LNode));scanf("%d",&q->data);p->next=q;p=q;}p->next=NULL;}//判断元素e是否在链表中int inList(list l,int e){list p,q;q=p=l->next;while(p){if(p->data==e)return OK; //发现在里面，返回真值p=p->next; //否则指针后移,继续找}//没有执行return OK;语句,说明未找到while(q->next!=p) q=q->next; //找到链尾p=(list)malloc(sizeof(LNode)); //为链尾重新开辟空间p->data=e; //接到链尾p->next=q->next;q->next=p;return ERROR; //未找到，返回假值}//输出链表void printList(list l){list p;p=l->next;while(p){ printf("%d ",p->data); p=p->next;}}void main(){list l;int e;printf("创建%d个元素的链表，请输入%d个元素：\n",N,N);creatList(l,N);printf("请输入要判断的元素：");scanf("%d",&e);if(inList(l,e))printf("YES ");elseprintList(l);}13#include <stdio.h>#include <stdlib.h>#define OK 1#define Error 0#define NULL 0#define maxSize 100//栈的存储结构typedef struct{int *base;int *top;int size;}stack;//栈的初始化（顺序存储）int initStack(stack &s){ //开辟maxSize大小的空间，base和top都指向基地址,同时判断是否开辟成功，不成功返回0if(!(s.base=s.top=(int*)malloc(maxSize*sizeof(int)))) return Error;s.size=maxSize; //栈的大小为maxSizereturn OK;}//进栈操作int push(stack &s,int e){*s.top=e; //先将元素e赋值给s.top所指的存储空间s.top++; //top指针上移return OK;}//出栈操作int pop(stack &s,int &e){if(s.base==s.top) return Error; //如果栈为空，返回0s.top--; //top指针先后移e=*s.top; //将其所指的元素值赋给e return e;}void main(){stack s;int n,e;printf("请输入要创建栈的元素的个数：");scanf("%d",&n);initStack(s);for(int i=0;i<n;i++){scanf("%d",&e);push(s,e);}while(s.base!=s.top){printf("%d ",pop(s,e));}}14#include <stdlib.h>#include <stdio.h>#include <stdio.h>#include <stdlib.h>#define stackincrement 8#define OK 1#define Error 0#define NULL 0#define maxSize 100//栈的存储结构typedef struct{char *base; //由于要存放括号，所以为char类型char *top;int size;}stack;//栈的初始化（顺序存储）int initStack(stack &s){ //注意开辟的空间为char类型if(!(s.base=s.top=(char*)malloc(maxSize*sizeof(char)))) return Error;s.size=maxSize; //栈的大小为maxSizereturn OK;}//进栈操作int push(stack &s,int e){*s.top=e; //先将元素e赋值给s.top所指的存储空间s.top++; //top指针上移return OK;}int isEmpty(stack s){return s.base==s.top?OK:Error;}//出栈操作char pop(stack &s,char &e){if(isEmpty(s)) return Error; //如果栈为空，返回0s.top--; //top指针先后移e=*s.top; //将其所指的元素值赋给ereturn e;}//括号匹配int match(){stack s;initStack(s);char ch[100],e;int flag=1,i=0 ,lenth; //flag用于标记，如果匹配，值为1，否则为0scanf("%c",&ch[i]);while(ch[i]!='\n') scanf("%c",&ch[++i]); //先将所有输入的括号存放在数组ch[]中lenth=i-1; //数组的长度，不包括'\n'i=0;push(s,ch[i]); //先将第一个括号压栈if(ch[i]==']'||ch[i]==')'||ch[i]=='}') flag=0; //如果第一个压入的是右括号，则肯定不匹配，flag=0else while(i<lenth)//||!emptystack(s){i++;char t;if(ch[i]==']'||ch[i]==')'||ch[i]=='}'){ t=pop(s,e); //弹出先前压入的元素，将后继输入的括号与先前压入的比较if((t!=ch[i]-1)&&(t!=ch[i]-2)) {flag=0;break;} //左右小括号与左右大括号的ASCII码都相差1，左右中括号相差2，如果不满足，则不匹配，直接退出循环}else push(s,ch[i]); //输入的是左括号，直接压入}if(!isEmpty(s)) flag=0; //通过不断的压栈和弹栈，如果最后栈不为空，则肯定是左括号多于右括号，不匹配return flag;}void main(){int result;printf("判断输入的各种括号是否匹配：\n");result=match();if(result) printf("括号匹配正确^_^\n");else printf("括号匹配错误*.*\n");}15#include "stdio.h"#include "stdlib.h"#define stackinitsize 100#define OK 1#define ERROR 0//二叉树的二叉链表存储结构typedef struct BiTNode{int data;struct BiTNode *lchild,*rchild; //左右孩子指针}BiTnode,*BiTree;int CreateBiTree(BiTree &T){//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。