《软件技术基础》实验指导

PAGE1PAGE32说明每个实验题目含有一个main函数和一些函数，与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目要求设计算法，补充函数定义，然后对程序进行编译、调试。实验一线性表实验目的熟悉线性表的顺序和链式存储结构掌握线性表的基本运算能够利用线性表的基本运算完成线性表应用的运算实验内容设有一个线性表E={e1,e2,…,en-1,en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={en,en-1,…,e2,e1}，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆置、单链表逆置）已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。（文件夹：分解单链表）实验二栈和队列实验目的熟悉栈和队列的顺序和链式存储结构掌握栈和队列的基本运算能够利用栈和队列的基本运算完成栈和队列应用的运算实验内容设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。）（文件夹：判字符串中心对称）假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。（文件夹：循环队列）实验三串实验目的熟悉串的顺序存储结构掌握串的基本运算及应用实验内容1．串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。（文件夹：模式匹配）2．若S是一个采用顺序结构存储的串，利用C的库函数strlen和strcpy（或strncpy）编写一算法voidSteDelete(char*S,intI,intm)，要求从S中删除从第i个字符开始的连续m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾的字符均删除。（文件夹：删除子串）实验四数组实验目的熟悉数组的结构掌握矩阵的压缩存储能够对数组和矩阵的压缩存储进行运算实验内容若在矩阵Am×n中存在一个元素A[i][j]，其满足A[i][j]是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Am×n，设计算法求出矩阵中所有马鞍点。（文件夹：找马鞍点）A和B是两个n×n阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储存入一维数组A和B，编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。（文件夹：对称矩阵相乘）实验五树实验目的熟悉二叉树的链式存储结构掌握二叉树的建立、深度优先递归遍历等算法能够利用遍历算法实现一些应用实验内容已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。（文件夹：交换左右子树）采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点总数。（文件夹：统计二叉树结点）实验六图实验目的熟悉图的邻接矩阵和邻接表的存储结构熟悉图的邻接矩阵和邻接表的建立算法掌握图的遍历算法实验内容无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。（文件夹：无向图邻接矩阵）BBCADEFGH实验七排序实验目的熟悉各种内部排序算法能够编写程序显示排序过程中各趟排序的结果能够编写一些排序的算法实验内容采用希尔排序方法对顺序表中的证型数据进行排序，设计希尔排序算法并显示每趟排序的结果。（文件夹：希尔排序）编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序的结果。（文件夹：双向起泡排序）实验八查找实验目的熟悉线性表、二叉排序树和散列表的查找能够编写一些查找的算法实验内容18个记录的关键字为22、12、13、8、9、20、33、42、44、38、24、48、60、58、74、49、86、53，编写分块查找的算法进行查找。（文件夹：分块查找）编写一个判别给定的二叉树是否为二叉排序树的算法，设二叉树以二叉链表存储表示，结点的数据域只存放正整数。（文件夹：判断二叉排序树）附录：原代码实验一：第1题（1）//顺序表逆置的程序代码#include<stdio.h>#include<malloc.h>//顺序表结构类型定义typedefchardatatype;constintmaxsize=1024;typedefstruct{datatypedata[maxsize];intlast;}sequenlist;voidcreate(sequenlist*&);voidprint(sequenlist*);voidinvert(sequenlist*);voidmain(){ sequenlist*L; create(L);//建立顺序表 print(L);//输出顺序表 invert(L);//调用顺序表逆值的函数 print(L);//输出顺序表}//建立顺序表voidcreate(sequenlist*&L){ L=(sequenlist*)malloc(sizeof(sequenlist)); L->last=0; charch; while((ch=getchar())!='*') { L->last++; L->data[L->last]=ch; }}//输出顺序表voidprint(sequenlist*L){ for(inti=1;i<=L->last;i++) printf("%2c",L->data[i]); printf("\n");}//顺序表逆置voidinvert(sequenlist*L){inti;chara[maxsize];for(i=1;i<L->last+1-i;i++){ a[i]=L->data[i];L->data[i]=L->data[L->last+1-i];L->data[L->last+1-i]=a[i];}}实验一：第1题（2）//单链表逆置的程序代码#include<malloc.h>#include<stdio.h>//单链表结构类型定义typedefchardatatype;typedefstructnode{ datatypedata; structnode*next;}linklist;voidcreate(linklist*&);voidprint(linklist*);voidinvert(linklist*);voidmain(){ linklist*head; create(head); print(head); invert(head);//调用单链表逆置的函数 print(head);}//采用尾插法建立具有头结点的单链表voidcreate(linklist*&head){ charch; 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;}//输出单链表voidprint(linklist*head){ linklist*p=head->next; while(p!=NULL) { printf("%2c",p->data); p=p->next; } printf("\n");}//单链表逆置voidinvert(linklist*head){ linklist*p,*q; //定义结构体指针p,q p=head->next; head->next=NULL; while(p!=NULL) { q=p->next;//q指向p的后继结点 p->next=head->next; head->next=p; p=q; }}实验一：第2题//分解单链表的程序代码#include<stdio.h>#include<malloc.h>//链表结构类型定义typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}linklist;voidcreate(linklist*&);voidresolve(linklist*,linklist*,linklist*,linklist*);voidinsert(linklist*,linklist*);voidprint1(linklist*);voidprint2(linklist*);voidmain(){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);}//建立单链表voidcreate(linklist*&head){datatypex;linklist*s,*r;head=newlinklist;r=head;while((x=getchar())!='$'){ s=(linklist*)malloc(sizeof(linklist));s->data=x; r->next=s; r=s;}r->next=NULL;}//在循环链表中插入voidinsert(linklist*h,linklist*p){linklist*q=h;while(q->next!=h)q=q->next;q->next=p;p->next=h;}//输出单链表voidprint1(linklist*head){linklist*p=head->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}//输出循环链表voidprint2(linklist*head){linklist*p=head->next;while(p!=head){ printf("%c",p->data);p=p->next;}printf("\n");}//按字母、数字、其它字符分解单链表voidresolve(linklist*head,linklist*letter,linklist*digit,linklist*other){linklist*p=head->next;linklist*q=letter;linklist*r=digit;linklist*v=other;linklist*s;while(p!=NULL){ s=(linklist*)malloc(sizeof(linklist));s->data=p->data; if(s->data>=65&&s->data<=122)//如果为字母 { s->next=letter; q->next=s; q=q->next; } elseif(s->data>=48&&s->data<=57)//如果为数字 { s->next=digit; r->next=s; r=r->next; } else//其他{ s->next=other; v->next=s; v=v->next; } //free(s);为什么不能释放呢？？ p=p->next;}}实验二：第1题//判字符串中心对称的程序代码#include<stdio.h>#include<malloc.h>#include<string.h>//定义单链表结构类型typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}linklist;//定义顺序栈结构类型constintmaxsize=40;typedefstruct{datatypeelements[maxsize];inttop;}stack;voidsetnull(stack*&);intlength(linklist*);voidprintlink(linklist*);voidcreate(linklist*&,datatype*);voidpush(stack*,datatype);datatypepop(stack*);intsymmetry(linklist*,stack*);//判字符串是否中心对称的函数声明voidmain(){ linklist*head;stack*s; datatypestr[80]; gets(str); create(head,str); printlink(head); setnull(s); if(symmetry(head,s))printf("字符串\"%s\"中心对称\n",str); elseprintf("字符串\"%s\"不是中心对称\n",str);}//栈初始化voidsetnull(stack*&s){ s=(stack*)malloc(sizeof(stack)); s->top=-1;}//求单链表长度intlength(linklist*head){linklist*p=head->next;intn=0;while(p!=NULL){n++;p=p->next;}returnn;}//输出单链表voidprintlink(linklist*head){linklist*p=head->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}//建立具有头结点的单链表voidcreate(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;}//顺序栈入栈voidpush(stack*s,datatypee){ s->top++; s->elements[s->top]=e;}//顺序栈出栈datatypepop(stack*s){ datatypetemp; s->top--; temp=s->elements[s->top+1]; returntemp;}//判字符串是否中心对称intsymmetry(linklist*head,stack*s){ inti=1,j=1;intn=length(head);// printf("n=%d\n",n); linklist*p=head->next; //先把前一半字符依次进栈 //datatypem; for(i=1;i<=n/2;i++) {push(s,p->data); p=p->next; } //依次出栈与另一半字符进行比较 if(n%2!=0)//判断n的奇偶 p=p->next; else p=p;while(s->elements[s->top]==p->data&&p!=NULL&&s->top>0)//循环至不等或其中一个为空 { j++; pop(s); p=p->next; } //printf("j=%2d;n/2=%2d\n",j,n/2); if(j==n/2) return1; else return0; }实验二：第2题//循环队列入队出队的程序代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>//循环队列的结构类型定义constintm=5;typedefintdatatype;typedefstruct{datatypesequ[m];intrear,quelen;}qu;voidsetnull(qu*);voidenqueue(qu*,datatype);datatype*dequeue(qu*);voidmain(){qu*sq;datatypex,*p;intkey;sq=(qu*)malloc(sizeof(qu));setnull(sq);do{printf("1.EnterQueue2.DeleteQueue-1.Quit:");scanf("%d",&key);switch(key){case1:printf("EntertheData:");scanf("%d",&x); enqueue(sq,x);break; case2:p=dequeue(sq); if(p!=NULL)printf("%d\n",*p); break; case-1:exit(0);}}while(1);}//置空队voidsetnull(qu*sq){sq->rear=m-1;sq->quelen=0;}//添加入队算法voidenqueue(qu*sq,datatypex){ if(sq->quelen==m)//判队满{printf("队列上溢");}else{sq->rear=(sq->rear+1)%m;//尾指针加1sq->sequ[sq->rear]=x;sq->quelen++;}}//添加出队算法datatype*dequeue(qu*sq)//出队{//datatypetmp;if(sq->quelen==0)//判队空{printf("队列下溢");}else{//tmp=sq->sequ[(sq->rear-sq->quelen+m)%m]; sq->quelen--;return(&sq->sequ[(sq->rear-sq->quelen+m)%m]);}}实验三：第1题//模式匹配的程序代码#include<stdio.h>#include<string.h>#include<malloc.h>//顺序串的结构类型定义#definemaxsize100typedefstruct{ charstr[maxsize];intlen;}seqstring;intIndex(seqstring*,seqstring*);voidmain(){ 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"); elseprintf("匹配失败！\n");}//顺序串的朴素模式匹配intIndex(seqstring*S,seqstring*subS){inti=1,j=1;//目标串从第一个字符开始与模式串的第一个字符开始进行比较while(i<=S->len&&j<=subS->len)//循环至i超出目标串的长度或j超出模式串的长度 { if(S->str[i-1]==subS->str[j-1])//若相等 {i++; j++; printf("A:i=%2d,j=%2d\n",i,j); }else//若不等 {i=i-j+2; j=1; printf("B:i=%2d,j=%2d\n",i,j); } } if(j>subS->len) { printf("i-subS->len=%2d\n",i-subS->len);return(i-subS->len);} elsereturn(0);}实验三：第2题//删除子串的程序代码#include<stdio.h>#include<string.h>#include<malloc.h>//顺序串的结构类型定义#definemaxsize100typedefstruct{ charstr[maxsize];intlen;}seqstring;voidstrPut(seqstring*);voidstrDelete(seqstring*,int,int);voidmain(){ seqstring*S; inti,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);}//输出串voidstrPut(seqstring*S){ inti; for(i=0;i<S->len;i++) printf("%c",S->str[i]); printf("\n");}//删除子串voidstrDelete(seqstring*S,inti,intm){ intn=strlen(S->str); chartemp[maxsize];if(i>=n)printf("没有字符被删除\n");elseif(i+m>=n){ printf("从位置%2d至末尾的字符均删除\n",i);//strcpy(temp,S->str); //strcpy(S->str,temp); S->len=i-1;}else{ printf("删除从第%2d个字符开始的连续%2d个字符\n",i,m);strcpy(temp,S->str+i-2);//把i个字符前的i-1个（str[0]--str[i-2]）字符放入指针temp中 strcpy(temp+i-1,S->str+i+m-1);//把 //strcpy(temp,S->str+i+m-1); strcpy(S->str,temp);S->len=S->len-m;}}实验四：第1题//找马鞍点程序代码#include<stdio.h>#include<malloc.h>//数组的结构类型定义constintm=3;constintn=3;typedefstruct{ intA[m+1][n+1]; intmax[m+1],min[n+1];}array;voidminmax(array*);voidmain(){ array*pa=(array*)malloc(sizeof(array));inti,j;for(i=1;i<=m;i++)for(j=1;j<=n;j++)scanf("%d",&pa->A[i][j]);minmax(pa);}//找马鞍点voidminmax(array*pa){inti,j,k=0; for(i=1;i<=m;i++)//打印出矩阵形式 { for(j=1;j<=n;j++) { printf("%3d",pa->A[i][j]); } printf("\n"); } for(i=1;i<=m;i++)//计算找出每行的最小元素，放入pa->min[M]中 { pa->min[i]=pa->A[i][1]; for(j=1;j<=n;j++) { if(pa->min[i]>pa->A[i][j]) { pa->min[i]=pa->A[i][j]; } } } for(i=1;i<=n;i++)//计算找出每列的最大元素，放入pa->max[N]中 { pa->max[i]=pa->A[1][i]; for(j=1;j<=m;j++) { if(pa->max[i]<pa->A[j][i]) { pa->max[i]=pa->A[j][i]; } } } for(i=1;i<=m;i++)//按照题目意思，进行匹配 { for(j=1;j<=n;j++) { if(pa->min[i]==pa->max[j]) { printf("马鞍点是:(%d,%d):%d\n",i,j,pa->A[i][j]); k=1; } } } if(k==0) { printf("没有马鞍点!\n"); }}实验四：第2题//对称矩阵相乘的程序代码#include<stdio.h>#include<malloc.h>//数组结构类型的定义.hconstintn=3;constintsize=n*(n+1)/2;typedefintdatatype;typedefstruct{ datatypeA[size],B[size],C[n][n];}array;voidinput(datatype[]);voidoutput(datatype[][n]);voidmult(array*);voidmain(){ 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}//对称矩阵的输入voidinput(datatypex[]){ for(inti=0;i<size;i++) scanf("%d",&x[i]);}//矩阵的输出voidoutput(datatypex[][n]){ for(inti=0;i<n;i++){ for(intj=0;j<n;j++) printf("%5d",x[i][j]); printf("\n"); }}//对称矩阵相乘voidmult(array*pa){inti,j,k=0,a[n][n],b[n][n],p,q;for(i=0;i<n;i++)//先还原矩阵A,B{ for(j=0;j<n;j++) { if(i>=j)//还原下三角 { a[i][j]=pa->A[k]; b[i][j]=pa->B[k]; k++; } if(i>j)//根据对称还原上三角 { a[j][i]=a[i][j];b[j][i]=b[i][j]; } }}printf("矩阵A:\n");output(a);printf("矩阵B:\n");output(b);printf("矩阵C:\n");for(i=0;i<n;i++)//求相乘后的矩阵Cfor(j=0;j<n;j++) { pa->C[i][j]=0; for(p=0;p<n;p++) pa->C[i][j]=pa->C[i][j]+a[i][p]*b[p][j]; } }实验五：第1题//交换左右子树的程序代码#include<stdio.h>#include<malloc.h>//二叉链表的结构类型定义constintmaxsize=1024;typedefchardatatype;typedefstructnode{ datatypedata; structnode*lchild,*rchild;}bitree;bitree*creattree();voidpreorder(bitree*);bitree*swap(bitree*);voidmain(){ bitree*pb; pb=creattree(); preorder(pb); printf("\n"); swap(pb); preorder(pb); printf("\n");}//二叉树的建立bitree*creattree(){ charch; bitree*Q[maxsize]; intfront,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++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; elseQ[front]->rchild=s; if(rear%2==1)front++; } } returnroot;}//先序遍历按层次输出二叉树voidpreorder(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(")"); } }}//交换左右子树bitree*swap(bitree*r){ bitree*p=r; bitree*q; if(p) { //printf("%c",p->data); q=p->lchild; p->lchild=p->rchild; p->rchild=q; swap(p->lchild); swap(p->rchild); }return(r);}实验五：第2题//统计结点总数、叶子结点总数及树深的程序代码#include<stdio.h>#include<malloc.h>//二叉链表的结构类型定义constintmaxsize=1024;typedefchardatatype;typedefstructnode{ datatypedata; structnode*lchild,*rchild;}bitree;bitree*creattree();voidpreorder(bitree*);intcountnode(bitree*);intcountleaf(bitree*);intdeep(bitree*p)；voidmain(){ bitree*root; intleafnum,nodenum，treedeep; root=creattree(); printf("删除子树之前的二叉树："); preorder(root); printf("\n");nodenum=countnode(root);printf("结点总数是：%d\n",nodenum); leafnum=countleaf(root);printf("叶子结点总数是：%d\n",leafnum);treedeep=deep(root);printf(“树深为：%d\n”,treedeep);}//建立二叉树bitree*creattree(){ datatypech; bitree*Q[maxsize]; intfront,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++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; elseQ[front]->rchild=s; if(rear%2==1)front++; } } returnroot;}//先序遍历输出二叉树voidpreorder(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(")"); } }}//添加统计结点个数算法(先根，中根，后根遍历均可)intcountnode(bitree*p){staticintn=0;if(p!=NULL){ countnode(p->lchild);n++;printf("%c",p->data);countnode(p->rchild);}returnn;}//添加统计叶子结点个数算法(先根、中根、后根均可)intcountleaf(bitree*p){staticintn=0;if(p!=NULL){countleaf(p->lchild);//遍历左子树if(p->lchild==NULL&&p->rchild==NULL) { n++;printf("%c",p->data);//打印叶子节点 }//endifcountleaf(p->rchild);//遍历右子树}//endifreturnn;}//求树深(三种遍历均可)intdeep(bitree*p){ intdl,dr; if(p) { dl=deep(p->lchild); printf("%c",p->data); dr=deep(p->rchild); if(dl>dr) return(dl+1); else return(dr+1); }return(0);}实验六：第1题//无向图邻接矩阵搜索遍历的程序代码#include<stdio.h>//图的邻接矩阵类型定义constintn=8;constinte=10;typedefcharvextype;typedefintadjtype;typedefstruct{ vextypevexs[n]; adjtypearcs[n][n];}graph;graph*g=newgraph;voidcreatgraph();voiddfsa(int);intvisited[n];voidmain(){ creatgraph(); inti; while(1) { for(i=0;i<n;i++) visited[i]=0; printf("输入出发点序号（0-7），输入-1结束："); scanf("%d",&i); if(i==-1)break; dfsa(i); }}//建立无向图邻接矩阵voidcreatgraph(){ inti,j,k; charch; printf("输入8个顶点的字符数据信息:\n"); for(i=0;i<n;i++) if((ch=getchar())!='\n')g->vexs[i]=ch; for(i=0;i<n;i++) for(j=0;j<n;j++) g->arcs[i][j]=0; printf("输入10条边的起、终点i,j:\n"); for(k=0;k<e;k++) { scanf("%d,%d",&i,&j);//顶点序号从0开始 g->arcs[i][j]=g->arcs[j][i]=1; }}//深度优先搜索遍历实验七：第1题//希尔排序的程序代码#include<stdio.h>//顺序表结构类型定义typedefintdatatype;typedefstruct{ intkey; datatypedata;}rectype;constintN=10;constintD1=5;voidcreate(rectype[],int);voidprint(rectype[],int);voidshellsort(rectype[],int[]);voidmain(){rectyper[N+D1];//D1个元素存放监视哨，N个元素存放记录intd[3]={5,3,1};//设置3趟的增量 create(r,N);//建立存放记录的顺序表 printf("排序前的数据："); print(r,N);//输出排序前的记录表 shellsort(r,d);//希尔排序 printf("排序后的数据："); print(r,N);//输出排序后的记录表}//建立顺序表voidcreate(rectyper[],intn){ printf("输入10个整型数："); for(inti=0;i<n;i++) scanf("%d",&r[D1+i].key);}//输出顺序表voidprint(rectyper[],intn){ for(inti=0;i<n;i++) printf("%5d",r[D1+i].key); printf("\n");}//希尔排序voidshellsort(rectypeR[],intd[]){ intk,i,j,s; for(k=0;k!=3;++k) { for(i=D1+d[k];i<N+D1;++i) { s=D1-d[k]+(i-D1)%d[k]; R[s]=R[i]; j=i-d[k]; while(R[s].key<R[j].key) { R[j+d[k]]=R[j]; j-=d[k]; } R[j+d[k]]=R[s]; } }}实验七：第2题//双向起泡排序的程序代码#include<stdio.h>#include<stdlib.h>#include<time.h>//顺序表结构类型定义typedefintdatatype;typedefstruct{ intkey; datatypedata;}sequenlist;voidcreate(sequenlist[],int);voidprint(sequenlist[],int);voiddbubblesort(sequenlist[],int);voidmain(){ constintn=10; sequenlistr[n+1]; create(r,n); printf("排序前的数据："); print(r,n); dbubblesort(r,n); printf("排序后的数据："); print(r,n);}//建立顺序表voidcreate(sequenlistr[],intn){ srand(time(0)); for(inti=1;i<=n;i++) r[i].key=rand()%90;}//输出顺序表voidprint(sequenlistr[],intn){ for(inti=1;i<=n;i++) printf("%5d",r[i].key); printf("\n");}//双向起泡排序实验八：第1题//分块查找的程序代码#include<stdio.h>//类型定义typedefintkeytype;typedefstruct{ keytypekey; intlow,high;}index;typedefstruct{ keytypekey;}record;constintrecN=18;constintidxN=3;intblksearch(record[],index[],keytype,int);voidmain(){ recordr[recN]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53}; indexidx[idxN]={{22,0,5},{48,6,11},{86,12,17}}; keytypekey; intloc,i; printf("待查找的记录关键字表：\n"); for(i=0;i<recN;i++) printf("%5d",r[i]); printf("\n"); printf("输入所要查找记录的关键字："); scanf("%d",&key); loc=blksearch(r,idx,key,idxN); if(loc!=-1)printf("查找到，是第%d个记录。\n",loc+1); elseprintf("记录查找不到！\n");}//折半查找索引表，块内顺序查找实验八：第2题//判断二叉排序树的程序代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>//二叉链表的结构类型定义constintmaxsize=1024;typedefintkeytype;typedefstructnode{ keytypekey; structnode*lchild,*rchild;}bitree;bitr