西电《软件技术基础》上机大作业答案

说明 每个实验题目含有一个main函数和一些函数，与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目要求设计算法，补充函数定义，然后对程序进行编译、调试。实验一 线性表一、 实验目的1 熟悉线性表的顺序和链式存储结构2 掌握线性表的基本运算3 能够利用线性表的基本运算完成线性表应用的运算二、 实验内容1 设有一个线性表E=e1, e2, , en-1, en，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E= en , en-1 , , e2 , e1 ，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆置、单链表逆置）2 已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。（文件夹：分解单链表）实验二 栈和队列一、 实验目的1 熟悉栈和队列的顺序和链式存储结构2 掌握栈和队列的基本运算3 能够利用栈和队列的基本运算完成栈和队列应用的运算二、 实验内容1 设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。）（文件夹：判字符串中心对称）2 假设以数组sequm存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq-quelen=0；队满的条件：sq-quelen=m。（文件夹：循环队列）实验三 串一、 实验目的1 熟悉串的顺序存储结构2 掌握串的基本运算及应用二、 实验内容1串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。（文件夹：模式匹配）2若S是一个采用顺序结构存储的串，利用C的库函数strlen和strcpy（或strncpy）编写一算法void SteDelete(char*S,int I,int m)，要求从S中删除从第i个字符开始的连续m个字符。若istrlen(S)，则没有字符被删除；若i+mstrlen(S)，则将S中从位置i开始直至末尾的字符均删除。（文件夹：删除子串）实验四 数组一、 实验目的1 熟悉数组的结构2 掌握矩阵的压缩存储3 能够对数组和矩阵的压缩存储进行运算二、 实验内容1. 若在矩阵Amn中存在一个元素Aij，其满足Aij是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Amn ，设计算法求出矩阵中所有马鞍点。（文件夹：找马鞍点）2. A和B是两个nn阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储存入一维数组A和B，编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。（文件夹：对称矩阵相乘）实验五 树一、 实验目的1 熟悉二叉树的链式存储结构2 掌握二叉树的建立、深度优先递归遍历等算法3 能够利用遍历算法实现一些应用二、 实验内容1 已知二叉树采用二叉链表存储结构，如果左、右子树非空，且左子树根结点大于右子树根结点，则交换根结点的左、右子树。即按要求交换二叉树及子树的左、右子树。（文件夹：交换左右子树）2 采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点总数。（文件夹：统计二叉树结点）实验六 图一、 实验目的1 熟悉图的邻接矩阵和邻接表的存储结构2 熟悉图的邻接矩阵和邻接表的建立算法3 掌握图的遍历算法二、 实验内容1 无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。（文件夹：无向图邻接矩阵）BCADEFGH实验七 排序一、 实验目的1 熟悉各种内部排序算法2 能够编写程序显示排序过程中各趟排序的结果3 能够编写一些排序的算法二、 实验内容1 采用希尔排序方法对顺序表中的证型数据进行排序，设计希尔排序算法并显示每趟排序的结果。（文件夹：希尔排序）2 编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序的结果。（文件夹：双向起泡排序）实验八 查找一、 实验目的1 熟悉线性表、二叉排序树和散列表的查找2 能够编写一些查找的算法二、 实验内容1 18个记录的关键字为22、12、13、8、9、20、33、42、44、38、24、48、60、58、74、49、86、53，编写分块查找的算法进行查找。（文件夹：分块查找）2 编写一个判别给定的二叉树是否为二叉排序树的算法，设二叉树以二叉链表存储表示，结点的数据域只存放正整数。（文件夹：判断二叉排序树）附录：原代码实验一：第1题（1）/顺序表逆置的程序代码#include#include/顺序表结构类型定义typedef char datatype;const int maxsize=1024;typedef struct datatype datamaxsize; int last;sequenlist;void create(sequenlist*&);void print(sequenlist*);void invert(sequenlist*);void main()sequenlist*L;create(L);/建立顺序表print(L);/输出顺序表invert(L);/调用顺序表逆值的函数print(L);/输出顺序表/建立顺序表void create(sequenlist*&L)L=(sequenlist*)malloc(sizeof(sequenlist);L-last=0;char ch;while(ch=getchar()!=*) L-last+;L-dataL-last=ch;/输出顺序表void print(sequenlist*L)for(int i=1;ilast;i+)printf(%2c,L-datai);printf(n);/顺序表逆置void invert(sequenlist*L)int n=L-last/2;for(int i=1;idatai;L-datai=L-dataL-last-i+1; L-dataL-last-i+1=temp;实验一：第1题（2）/单链表逆置的程序代码#include#include/单链表结构类型定义typedef char datatype;typedef struct nodedatatype data;struct node *next;linklist;void create(linklist*&);void print(linklist *);void invert(linklist*);void main()linklist*head;create(head);print(head);invert(head);/调用单链表逆置的函数print(head);/采用尾插法建立具有头结点的单链表void create(linklist*&head)char ch;linklist *s,*r;head=(linklist*)malloc(sizeof(linklist);r=head;while(ch=getchar()!=*)s=(linklist*)malloc(sizeof(linklist);s-data=ch;r-next=s;r=s;r-next=NULL;/输出单链表void print(linklist *head)linklist*p=head-next;while(p!=NULL)printf(%2c,p-data);p=p-next;printf(n);/单链表逆置void invert(linklist*head)linklist*p,*q,*r;p=head-next;q=p-next;while(q!=NULL)r=q-next;q-next=p;p=q;q=r;head-next-next=NULL;head-next=p;实验一：第2题/分解单链表的程序代码#include#include/链表结构类型定义typedef char datatype;typedef struct node datatype data; struct node *next;linklist;void create(linklist*&);void resolve(linklist*,linklist*,linklist*,linklist*);void insert(linklist*,linklist*);void print1(linklist*);void print2(linklist*);void main() linklist *head,*letter,*digit,*other; create(head); print1(head); letter=(linklist*)malloc(sizeof(linklist);/建立3个空循环链表 letter-next=letter; digit=(linklist*)malloc(sizeof(linklist); digit-next=digit; other=(linklist*)malloc(sizeof(linklist); other-next=other; resolve(head,letter,digit,other);/调用分解单链表的函数 print2(letter);/输出循环链表 print2(digit); print2(other);/建立单链表void create(linklist*&head) datatype x; linklist *s,*r; head=new linklist; r=head; while(x=getchar()!=$) s=(linklist*)malloc(sizeof(linklist); s-data=x; r-next=s; r=s; r-next=NULL;/在循环链表中插入void insert(linklist*h,linklist*p) linklist *q=h; while(q-next!=h) q=q-next; q-next=p; p-next=h;/输出单链表void print1(linklist*head) linklist *p=head-next; while(p!=NULL) printf(%c,p-data); p=p-next; printf(n);/输出循环链表void print2(linklist*head) linklist *p=head-next; while(p!=head) printf(%c,p-data); p=p-next; printf(n);/按字母、数字、其它字符分解单链表void resolve(linklist*head,linklist*letter,linklist*digit,linklist*other) linklist *p; while(head-next!=NULL) p=head-next; head-next=head-next-next; if(p-data=A&p-datadata=a&p-datadata=0&p-datanext; while(p!=NULL) if(p-data=a&p-datadata=A&p-datadata=0&p-datanext; 实验二：第1题/判字符串中心对称的程序代码#include#include#include/定义单链表结构类型typedef char datatype;typedef struct node datatype data; struct node *next;linklist;/定义顺序栈结构类型const int maxsize=40;typedef struct datatype elementsmaxsize; int top;stack;void setnull(stack *&);int length(linklist*);void printlink(linklist*);void create(linklist *&,datatype*);void push(stack*,datatype);datatype pop(stack*);int symmetry(linklist*,stack*);/判字符串是否中心对称的函数声明void main()linklist *head;stack *s;datatype str80;gets(str);create(head,str);printlink(head);setnull(s);if(symmetry(head,s) printf(字符串%s中心对称n,str);else printf(字符串%s不是中心对称n,str);/栈初始化void setnull(stack *&s)s=(stack*)malloc(sizeof(stack);s-top=-1;/求单链表长度int length(linklist*head) linklist *p=head-next; int n=0; while(p!=NULL) n+; p=p-next; return n;/输出单链表void printlink(linklist*head) linklist *p=head-next; while(p!=NULL) printf(%c,p-data); p=p-next; printf(n);/建立具有头结点的单链表void create(linklist *&head,datatype*str) datatype *p=str; linklist *s,*r; head=(linklist*)malloc(sizeof(linklist); r=head; while(*p!=0) s=(linklist*)malloc(sizeof(linklist); s-data=*p; r-next=s; r=s; p+; r-next=NULL;/顺序栈入栈void push(stack*s,datatype e)s-top+;s-elementss-top=e;/顺序栈出栈datatype pop(stack*s)datatype temp;s-top-;temp=s-elementss-top+1;return temp;/判字符串是否中心对称int symmetry(linklist*head,stack*s)int n=length(head)/2;linklist*p=head-next;datatype x;for(int i=0;idata);p=p-next;if(length(head)%2=1) p=p-next;while(p!=NULL)x=pop(s);if(x=p-data) p=p-next;else return 0;return 1;实验二：第2题/循环队列入队出队的程序代码#include#include#include/循环队列的结构类型定义const int m=5;typedef int datatype;typedef struct datatype sequm; int rear, quelen;qu;void setnull(qu*);void enqueue(qu*, datatype);datatype *dequeue(qu*);void main() qu *sq; datatype x, *p; int key; sq=(qu*)malloc(sizeof(qu); setnull(sq); do printf(1.Enter Queue 2.Delete Queue -1.Quit:); scanf(%d,&key); switch(key) case 1: printf(Enter the Data:); scanf(%d,&x); enqueue(sq,x); break; case 2: p=dequeue(sq); if(p!=NULL) printf(%dn,*p); break; case -1: exit(0); while(1);/置空队void setnull(qu *sq) sq-rear=m-1; sq-quelen=0;/入队void enqueue(qu *sq, datatype x) if(sq-quelen=m) printf(queue is fulln); else sq-quelen+; sq-rear=(sq-rear+1)%m; sq-sequsq-rear=x;/出队datatype *dequeue(qu *sq) datatype *temp; if(sq-quelen=0) printf(queue is emptyn); return NULL; else temp=(datatype*)malloc(sizeof(datatype); sq-quelen-; *temp=sq-sequ(sq-rear-sq-quelen+m)%m; return (temp); 实验三：第1题/模式匹配的程序代码#include#include#include/顺序串的结构类型定义#define maxsize 100typedef struct char strmaxsize; int len;seqstring;int Index(seqstring*, seqstring*);void main()seqstring*S,*subS;S=(seqstring*)malloc(sizeof(seqstring);subS=(seqstring*)malloc(sizeof(seqstring);printf(输入串：); gets(S-str);S-len=strlen(S-str);printf(输入子串：); gets(subS-str);subS-len=strlen(subS-str);if(Index(S,subS)0) printf(匹配成功！n);else printf(匹配失败！n);/顺序串的朴素模式匹配int Index(seqstring*S, seqstring*T) int i=1,j=1; /位序从1开始 while(ilen&jlen) if(S-stri-1=T-strj-1) i+; j+; /继续比较后面的字符 else i=i-j+2; j=1; /本趟不匹配，设置下一趟匹配的起始位序 if(jT-len) return(i-T-len); /匹配成功 else return(-1); /匹配不成功 实验三：第2题/删除子串的程序代码#include#include#include/顺序串的结构类型定义#define maxsize 100typedef struct char strmaxsize; int len;seqstring;void strPut(seqstring*);void strDelete(seqstring*,int,int);void main()seqstring*S;int i,m;S=(seqstring*)malloc(sizeof(seqstring);printf(输入串：); gets(S-str);S-len=strlen(S-str);strPut(S);printf(删除的开始位置:);scanf(%d,&i);printf(删除的字符个数:);scanf(%d,&m);strDelete(S,i,m);strPut(S);/输出串void strPut(seqstring*S)int i;for(i=0;ilen;i+)printf(%c,S-stri);printf(n);/删除子串void strDelete(seqstring*S,int i,int m)char tempmaxsize;if(ilen)strncpy(temp,S-str,i-1);strcpy(temp+i-1,S-str+i+m-1);strcpy(S-str,temp);if(ilen)if(i+m-1len) S-len=S-len-m;else S-len=S-len-i+1;实验四：第1题/找马鞍点程序代码#include#include/数组的结构类型定义const int m=3;const int n=3;typedef structint Am+1n+1;int maxm+1,minn+1;array;void minmax(array*);void main()array*pa=(array*)malloc(sizeof(array); int i, j; for (i=1;i=m;i+) for (j=1;jAij); minmax(pa);/找马鞍点void minmax(array*p) int i,j,have=0; for(i=1;imini=p-Ai1; for(j=2;jAijmini) p-mini=p-Aij; for (j=0;jmaxj=p-A1j; for(i=2;iAijp-maxj) p-maxj=p-Aij; for(i=1;i=m;i+) for(j=1;jmini=p-maxj) printf(%d,%d,%dn,i,j,p-Aij); have=1; if(!have) printf(矩阵中没有马鞍点！n);实验四：第2题/对称矩阵相乘的程序代码#include#include/数组结构类型的定义.hconst int n=3;const int size=n*(n+1)/2;typedef int datatype;typedef structdatatype Asize,Bsize,Cnn;array;void input(datatype);void output(datatypen);void mult(array*);void main()array*pa;pa=(array*)malloc(sizeof(array);printf(以行为主序输入矩阵A的下三角:n); input(pa-A);/以行为主序输入矩阵A的下三角printf(以行为主序输入矩阵B的下三角:n);input(pa-B);/以行为主序输入矩阵B的下三角mult(pa);output(pa-C);/输出矩阵C/对称矩阵的输入void input(datatype x)for(int i=0;isize;i+)scanf(%d,&xi);/矩阵的输出void output(datatype xn)for(int i=0;in;i+)for(int j=0;jn;j+)printf(%5d,xij); printf(n);/对称矩阵相乘void mult(array*p)int i,j,k,t1,t2;datatype s;for(i=0;in;i+)for(j=0;jn;j+)s=0;for(k=0;k=k)t1=i*(i+1)/2+k;else t1=k*(k+1)/2+i;if(k=j)t2=k*(k+1)/2+j;else t2=j*(j+1)/2+k;s=s+p-At1*p-Bt2;p-Cij=s;实验五：第1题/交换左右子树的程序代码#include#include/二叉链表的结构类型定义const int maxsize=1024;typedef char datatype;typedef struct nodedatatype data;struct node *lchild,*rchild;bitree;bitree*creattree();void preorder(bitree*);void swap(bitree*);void main()bitree*pb;pb=creattree();preorder(pb);printf(n);swap(pb);preorder(pb);printf(n);/二叉树的建立bitree*creattree()char ch;bitree*Qmaxsize;int front,rear;bitree*root,*s;root=NULL;front=1;rear=0;printf(按层次输入二叉树，虚结点输入，以#结束输入：n);while(ch=getchar()!=#)s=NULL;if(ch!=)s=(bitree*)malloc(sizeof(bitree);s-data=ch;s-lchild=NULL;s-rchild=NULL;rear+;Qrear=s;if(rear=1)root=s;elseif(s&Qfront)if(rear%2=0)Qfront-lchild=s;else Qfront-rchild=s;if(rear%2=1)front+;return root;/先序遍历按层次输出二叉树void preorder(bitree*p)if(p!=NULL)printf(%c,p-data);if(p-lchild!=NULL|p-rchild!=NULL)printf();preorder(p-lchild);if(p-rchild!=NULL)printf(,);preorder(p-rchild);printf();/交换左右子树void swap(bitree*p)bitree*t;if(p!=NULL)if(p-lchild!=NULL&p-rchild!=NULL&p-lchild-datap-rchild-data)t=p-lchild;p-lchild=p-rchild;p-rchild=t;swap(p-lchild);swap(p-rchild);实验五：第2题/统计结点总数及叶子结点总数的程序代码#include#include/二叉链表的结构类型定义const int maxsize=1024;typedef char datatype;typedef struct nodedatatype data;struct node *lchild,*rchild;bitree;bitree*creattree();void preorder(bitree*);int countnode(bitree*); int countleaf(bitree*); void main()bitree*root;int leafnum,nodenum;root=creattree();printf(删除子树之前的二叉树：);preorder(root);printf(n); nodenum=countnode(root); printf(结点总数是：%dn,nodenum);leafnum=countleaf(root); printf(叶子结点总数是：%dn,leafnum);/建立二叉树bitree*creattree()datatype ch;bitree*Qmaxsize;int front,rear;bitree*root,*s;root=NULL;front=1;rear=0;printf(按层次输入结点值，虚结点输入，以换行符结束：);while(ch=getchar()!=n)s=NULL;if(ch!=)s=(bitree*)malloc(sizeof(bitree);s-data=ch;s-lchild=NULL;s-rchild=NULL;rear+;Qrear=s;if(rear=1)root=s;elseif(s&Qfront)if(rear%2=0)Qfront-lchild=s;else Qfront-rchild=s;if(rear%2=1)front+;return root;/先序遍历输出二叉树void preorder(bitree*p)if(p!=NULL)printf(%c,p-data);if(p-lchild!=NULL|p-rchild!=NULL)printf();preorder(p-lchild);if(p-rchild!=NULL) printf(,);preorder(p-rchild);printf();/统计结点个数int countnode(bitree *p) static int node =0; if(p!=NULL) node=node+1;node = countnode(p-lchild); /统计左子树中结点个数node=countnode(p-rchild); /统计右子树中结点个数 return node; /统计叶子结点个数int countleaf(bitree *p) static int leaf =0; if(p!=NULL) leaf = countleaf( p-lchild ); /统计左子树中叶子结点个数if (p-lchild=NULL)&(p-rchild=NULL) leaf=leaf+1;leaf=countleaf(p-rchild); /统计右子树中叶子结点个数 return leaf; 实验六：第1题/无向图邻接矩阵搜索遍历的程序代码#include/图的邻接矩阵类型定义const int n=8;const int e=10;typedef char vextype;typedef int adjtype;typedef structvextype vexsn;adjtype arcsnn;graph;graph*g=new graph;void creatgraph();void dfsa(int);int visitedn;void main()creatgraph();int i;while(1)for(i=0;in;i+)visitedi=0;printf(输入出发点序号（0-7），输入-1结束：);scanf(%d,&i);if(i=-1) break; dfsa(i);/建立无向图邻接矩阵void creatgraph()int i,j,k;char ch;printf(输入8个顶点的字符数据信息:n);for(i=0;ivexsi=ch;for(i=0;in;i+)for(j=0;jarcsij=0;printf(输入10条边的起、终点i,j:n); for(k=0;karcsij=g-arcsji=1;/深度优先搜索遍历void dfsa(int i)int j;printf(Node:%cn,g-vexsi);visitedi=1;for(j=0;jarcsij=