大大数据结构实验问题详解

《大大数据结构实验问题详解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

实用文档《数据结构》实验指导2013/2014学年第2学期姓名：______________学号：_________班级：______________指导教师：______________潍坊学院计算机工程学院2014标准文案 实用文档预备实验C语言的函数数组指针结构体知识一、实验目的1、复习C语言中函数、数组、指针和结构体的概念。2、熟悉利用C语言进行程序设计的一般方法。二、实验内容和要求1、调试程序：输出100以内所有的素数（用函数实现）。#include/*判断一个数是否为素数*/intisprime(intn){for(intm=2;m*m<=n;m++){if(n%m==0)return0;return1;}/*输出100以内所有素数*/intmain(){inti;for(i=2;i<100;i++)if(isprime(i)==1)printf(“%4d”,i);return0;}运行结果：2、调试程序：对一维数组中的元素进行逆序排列。#include#defineN10intmain(){inta[N]={0,1,2,3,4,5,6,7,8,9},i,temp;printf(“theoriginalArrayis: ”);for(i=0;i#defineM3#defineN4intmain(){inta[M][N],i,j,k;printf(“请输入二维数组的数据： ”);for(i=0;ia[i][k])k=j;for(j=0;jintmain(){inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23};int*p;for(p=a[0];p#defineN10;structstudent{charnum[6];/*学号*/charname[8];/*姓名*/intscore[3];/*成绩*/floatavr;/*平均成绩*/}stu[N];intmain(){inti,j,max,maxi,sum;标准文案 实用文档floataverage;for(i=0;imax){max=sum;maxi=i;}}average/=10;printf(“学号姓名成绩1成绩2成绩3平均分 );for(i=0;i<10;i++){printf(“%8s%10s”,stu[i].num,stu[i].name);for(j=0;j<3;j++)printf(“%7d”,stu[i].score[j]);printf(“%6.2f ”,stu[i].avr);}printf(“平均成绩是：%5.2f ”,average);printf(“最好成绩的学生是：%s，总分是%d”,stu[maxi].name,max);return0;}运行结果标准文案 实用文档三、实验小结对C语言中函数、数组、指针和结构体的概念，有了进一步的加深。并且可以利用C语言进行初步程序设计。四、教师评语标准文案 实用文档实验一顺序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。二、实验内容和要求1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include#include#defineERROR0#defineOK1#defineINIT_SIZE5/*初始分配的顺序表长度*/#defineINCREM5/*溢出时，顺序表长度的增量*/typedefintElemType;/*定义表元素的类型*/typedefstructSqlist{ElemType*slist;/*存储空间的基地址*/intlength;/*顺序表的当前长度*/intlistsize;/*当前分配的存储空间*/}Sqlist;intInitList_sq(Sqlist*L);/*初始化顺序表L，并将其长度设为0*/intCreateList_sq(Sqlist*L,intn);/*构造顺序表的长度为n*/intListInsert_sq(Sqlist*L,inti,ElemTypee);/*在顺序线性表L中第i个元素之前插入新的元素e*/intPrintList_sq(Sqlist*L);/*输出顺序表的元素*/intListDelete_sq(Sqlist*L,inti);/*删除第i个元素*/intListLocate(Sqlist*L,ElemTypee);/*查找值为e的元素*/intInitList_sq(Sqlist*L){L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(!L->slist)returnERROR;L->length=0;L->listsize=INIT_SIZE;returnOK;}/*InitList*/intCreateList_sq(Sqlist*L,intn){标准文案 实用文档ElemTypee;inti;for(i=0;ilength;i++)printf("%5d",L->slist[i-1]);returnOK;}/*PrintList*/intListInsert_sq(Sqlist*L,inti,ElemTypee){intk;if(i<1||i>L->length+1)returnERROR;if(L->length>=L->listsize){L->slist=(ElemType*)realloc(L->slist,(INIT_SIZE+INCREM)*sizeof(ElemType));if(!L->slist)returnERROR;L->listsize+=INCREM;}for(k=L->length-1;k>=i-1;k--){L->slist[k+1]=k;}L->slist[i-1]=e;L->length++;returnOK;}/*ListInsert*//*在顺序表中删除第i个元素*/intListDelete_sq(Sqlist*L,inti){if((i<1)||(i>L->length))returnERROR;for(p=i-1;p<->length-1;p++)L->slist[p]=L->slist[p+1];标准文案 实用文档L->length--;returnOK;}/*在顺序表中查找指定值元素，返回其序号*/intListLocate(Sqlist*L,ElemTypee){}intmain(){Sqlistsl;intn;printf("pleaseinputn:");/*输入顺序表的元素个数*/scanf("%d",&n);if(n>0){printf(" 1-CreateSqlist: ");InitList_sq(&sl);CreateList_sq(&sl,n);printf(" 2-PrintSqlist: ");PrintList_sq(&sl);}elseprintf("ERROR");return0;}l算法分析与运行结果pleaseinputn:51-CreateSqlist:inputdata10inputdata25inputdata38inputdata43inputdata562-PrintSqlist:05836Pressanykeytocontinue标准文案 实用文档2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。算法代码：intListDelete_sq(Sqlist*L,inti){intp;if((i<1)||(i>L->length))returnERROR;for(p=i-1;plength-1;p++){L->slist[p]=L->slist[p+1];}L->length--;returnOK;}/*在顺序表中查找指定值元素，返回其序号*/intListLocate(Sqlist*L,ElemTypee){inti=0;while((i<=L->length)&&(L->slist[i]!=e))i++;if(i<=L->length)return(i+1);elsereturn(-1);}标准文案 实用文档3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include#include#defineERROR0#defineOK1typedefintElemType;/*定义表元素的类型*/typedefstructLNode{/*线性表的单链表存储*/ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListCreateList(intn);/构造顺序表的长度*/voidPrintList(LinkListL);/*输出带头结点单链表的所有元素*/标准文案 实用文档intGetElem(LinkListL,inti,ElemType*e);/*在顺序线性表L中，当第i个元素存在时，将其赋值为e*/LinkListCreateList(intn){LNode*p,*q,*head;inti;head=(LinkList)malloc(sizeof(LNode));head->next=NULL;p=head;for(i=0;idata);/*输入元素值*/q->next=NULL;/*结点指针域置空*/p->next=q;/*新结点连在表末尾*/p=q;}returnhead;}/*CreateList*/voidPrintList(LinkListL){LNode*p;p=L->next;/*p指向单链表的第1个元素*/while(p!=NULL){printf("%5d",p->data);p=p->next;}}/*PrintList*/intGetElem(LinkListL,inti,ElemType*e){LNode*p;intj=1;p=L->next;while(p&&jnext;j++;}if(!p||j>i)returnERROR;*e=p->data;returnOK;}/*GetElem*/intmain(){intn,i;ElemTypee;LinkListL=NULL;/*定义指向单链表的指针*/标准文案 实用文档printf("pleaseinputn:");/*输入单链表的元素个数*/scanf("%d",&n);if(n>0){printf(" 1-CreateLinkList: ");L=CreateList(n);printf(" 2-PrintLinkList: ");PrintList(L);printf(" 3-GetElemfromLinkList: ");printf("inputi=");scanf("%d",&i);if(GetElem(L,i,&e))printf("No%iis%d",i,e);elseprintf("notexists");}elseprintf("ERROR");return0;}l算法分析与运行结果pleaseinputn:51-CreateLinkList:inputdata1:8inputdata2:6inputdata3:3inputdata4:5inputdata5:42-PrintLinkList:863543-GetElemfromLinkList:inputi=2No2is6Pressanykeytocontinue标准文案 实用文档4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。l算法代码intListInsert_sq(LNode*L,inti,ElemTypee){intk;if(i<1||i>L->length+1)returnERROR;if(L->length>=L->listsize){L->data=(ElemType*)realloc(L->data,(INIT_SIZE+INCREM)*sizeof(ElemType));if(!L->data)returnERROR;L->listsize+=INCREM;}l标准文案 实用文档#include#include#defineERROR0#defineOK1typedefintElemType;/*定义表元素的类型*/typedefstructLNode{/*线性表的单链表存储*/ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListCreateList(intn);/*标准文案 实用文档以下为选做实验：5、循环链表的应用（约瑟夫回环问题）n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素。提示：用一个无头结点的循环单链表来实现n个元素的存储。l算法代码6、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。提示：指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p＝＝null为至，既完成了对整个链表元素的删除相同值。l算法代码三、实验小结具体的掌握线性表中元素的前驱、后续的概念。以及顺序表与链表的建立、插入元素、删除表中某元素的算法。并学习了对线性表相应算法的时间复杂度进行分析。四、教师评语标准文案 实用文档实验二栈和队列一、实验目的1、掌握栈的结构特性及其入栈，出栈操作；2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。二、实验内容和要求1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列12345e，运行结果如下所示。#include#include#defineERROR0#defineOK1#defineSTACK_INT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT5/*存储空间分配增量*/typedefintElemType;/*定义元素的类型*/typedefstruct{ElemType*base;ElemType*top;intstacksize;/*当前已分配的存储空间*/}SqStack;intInitStack(SqStack*S);/*构造空栈*/intpush(SqStack*S,ElemType*e);/*入栈*/intPop(SqStack*S,ElemType*e);/*出栈*/intCreateStack(SqStack*S);/*创建栈*/voidPrintStack(SqStack*S);/*出栈并输出栈中元素*/intInitStack(SqStack*S){S->base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType));标准文案 实用文档if(!S->base)returnERROR;S->top=S->base;S->stacksize=STACK_INT_SIZE;returnOK;}/*InitStack*/intPush(SqStack*S,ElemTypee){}/*Push*/intPop(SqStack*S,ElemType*e){}/*Pop*/intCreateStack(SqStack*S){inte;if(InitStack(S))printf("InitSuccess! ");else{printf("InitFail! ");returnERROR;}printf("inputdata:(Terminatedbyinputingacharacter) ");while(scanf("%d",&e))Push(S,e);returnOK;}/*CreateStack*/voidPrintStack(SqStack*S){ElemTypee;while(Pop(S,&e))printf("%3d",e);}/*Pop_and_Print*/intmain(){SqStackss;printf(" 1-createStack ");CreateStack(&ss);printf(" 2-Pop&Print ");PrintStack(&ss);return0;}l算法分析：输入元素序列12345，为什么输出序列为54321？体现了栈的什么特性？标准文案 实用文档2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。l实现代码voidconveshen(SqStack*S){ElemTypen,h;intm=0,k=0;InitStack(S);printf("Inputelement ");scanf("%d",&n);while(n){m++;Push(S,n%2);n=n/2;}while(k#include#include#defineM20#defineelemtypechartypedefstruct{elemtypestack[M];inttop;}stacknode;voidinit(stacknode*st);voidpush(stacknode*st,elemtypex);voidpop(stacknode*st);voidinit(stacknode*st){st->top=0;}voidpush(stacknode*st,elemtypex){if(st->top==M)标准文案 实用文档printf("thestackisoverflow! ");else{st->top=st->top+1;st->stack[st->top]=x;}}voidpop(stacknode*st){st->top=st->top-1;}intmain(){chars[M];inti;printf("createaemptystack! ");stacknode*sp;sp=malloc(sizeof(stacknode));init(sp);printf("inputaexpression: ");gets(s);for(i=0;itop==0)printf("'('match')'! ");elseprintf("'('notmatch')'! ");return0;}l输入：2+((c-d)*6-(f-7)*a)/6l运行结果：标准文案 实用文档l输入：a-((c-d)*6-(s/3-x)/2l运行结果：l程序的基本功能：以下为选做实验：标准文案 实用文档4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。l实现代码5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。实现代码：三、实验小结基本掌握栈的结构特性及其入栈，出栈操作；以及队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作四、教师评语标准文案 实用文档实验三串的模式匹配一、实验目的1、了解串的基本概念2、掌握串的模式匹配算法的实现二、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include#include#defineMAXSIZE100typedefstruct{chardata[MAXSIZE];intlength;}SqString;intstrCompare(SqString*s1,SqString*s2);/*串的比较*/voidshow_strCompare();voidstrSub(SqString*s,intstart,intsublen,SqString*sub);/*求子串*/voidshow_subString();intstrCompare(SqString*s1,SqString*s2){inti;for(i=0;ilength&&ilength;i++)if(s1->data[i]!=s2->data[i])returns1->data[i]-s2->data[i];returns1->length-s2->length;}voidshow_strCompare(){SqStrings1,s2;intk;printf(" ***showCompare*** ");printf("inputstrings1:");gets(s1.data);s1.length=strlen(s1.data);printf("inputstrings2:");gets(s2.data);s2.length=strlen(s2.data);if((k=strCompare(&s1,&s2))==0)printf("s1=s2 ");标准文案 实用文档elseif(k<0)printf("s1s2 ");printf(" ***showover*** ");}voidstrSub(SqString*s,intstart,intsublen,SqString*sub){inti;if(start<1||start>s->length||sublen>s->length-start+1){sub->length=0;}for(i=0;idata[i]=s->data[start+i-1];sub->length=sublen;}voidshow_subString(){SqStrings,sub;intstart,sublen,i;printf(" ***showsubString*** ");printf("inputstrings:");gets(s.data);s.length=strlen(s.data);printf("inputstart:");scanf("%d",&start);printf("inputsublen:");scanf("%d",&sublen);strSub(&s,start,sublen,&sub);if(sub.length==0)printf("ERROR! ");else{printf("subStringis:");for(i=0;i#include#defineMAXSIZE100typedefstruct{chardata[MAXSIZE];标准文案 实用文档intlength;}SqString;intindex_bf(SqString*s,SqString*t,intstart);voidgetNext(SqString*t,intnext[]);intindex_kmp(SqString*s,SqString*t,intstart,intnext[]);voidshow_index();intindex_bf(SqString*s,SqString*t,intstart){inti,j,pos;if(t->length==0)return(0);pos=start;i=pos;j=0;while(ilength&&jlength)if(s->data[i]==t->data[j]){i++;j++;}else{pos++;i=pos;j=0;}if(j>=t->length)return(pos);elsereturn(-1);}}voidgetNext(SqString*t,intnext[]){inti=0,j=-1;next[0]=-1;while(ilength){if((j==-1)||(t->data[i]==t->data[j])){i++;j++;next[i]=j;}elsej=next[j];}}intindex_kmp(SqString*s,SqString*t,intstart,intnext[]){inti,j;if(t->length==0)return(0);i=start;j=0;while(ilength&&jlength)标准文案 实用文档if(s->data[i]==t->data[j]){i++;j++;}elsej=next[j];if(j>=t->length)return(i-j);elsereturn(-1);}voidshow_index(){SqStrings,t;intk,next[MAXSIZE]={0},i;printf(" ***showindex*** ");printf("inputstrings:");gets(s.data);s.length=strlen(s.data);printf("inputstringt:");gets(t.data);t.length=strlen(t.data);printf("inputstartposition:");scanf("%d",&k);printf("BF: theresultofBFis%d ",index_bf(&s,&t,k));getNext(&t,next);printf("KMP: ");printf("next[]:");for(i=0;i#include#defineMAX20typedefstructBTNode{/*节点结构声明*/chardata;/*节点数据*/structBTNode*lchild;structBTNode*rchild;/*指针*/}*BiTree;voidcreateBiTree(BiTree*t){/*先序遍历创建二叉树*/chars;BiTreeq;printf(" pleaseinputdata:(exitfor#)");s=getche();if(s=='#'){*t=NULL;return;}q=(BiTree)malloc(sizeof(structBTNode));if(q==NULL){printf("Memoryallocfailure!");exit(0);}q->data=s;*t=q;createBiTree(&q->lchild);/*递归建立左子树*/createBiTree(&q->rchild);/*递归建立右子树*/}voidPreOrder(BiTreep){/*先序遍历二叉树*/if(p!=NULL){printf("%c",p->data);PreOrder(p->lchild);PreOrder(p->rchild);}}voidInOrder(BiTreep){/*中序遍历二叉树*/if(p!=NULL){标准文案 实用文档InOrder(p->lchild);printf("%c",p->data);InOrder(p->rchild);}}voidPostOrder(BiTreep){/*后序遍历二叉树*/if(p!=NULL){PostOrder(p->lchild);PostOrder(p->rchild);printf("%c",p->data);}}voidPreorder_n(BiTreep){/*先序遍历的非递归算法*/BiTreestack[MAX],q;inttop=0,i;for(i=0;idata);if(q->rchild!=NULL)stack[top++]=q->rchild;if(q->lchild!=NULL)q=q->lchild;elseif(top>0)q=stack[--top];elseq=NULL;}}voidrelease(BiTreet){/*释放二叉树空间*/if(t!=NULL){release(t->lchild);release(t->rchild);free(t);}}intmain(){BiTreet=NULL;createBiTree(&t);printf(" PreOrderthetreeis:");PreOrder(t);printf(" InOrderthetreeis:");InOrder(t);printf(" PostOrderthetreeis:");标准文案 实用文档PostOrder(t);printf(" 先序遍历序列（非递归）:");Preorder_n(t);release(t);return0;}l运行程序输入：ABC##DE#G##F###运行结果：2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。标准文案 实用文档算法代码：intPreOrder_num(BiTreep){intj=0;BiTreestack[MAX],q;inttop=0,i;for(i=0;irchild!=NULL)stack[top++]=q->rchild;if(q->lchild!=NULL)q=q->lchild;elseif(top>0)q=stack[--top];elseq=NULL;}returnj;}标准文案 实用文档3、在上题中补充求二叉树中求叶子结点总数算法（提示：可在某种遍历过程中统计遍历的叶子结点数），并在主函数中补充相应的调用验证正确性。算法代码：intBTNodeDepth(BiTreep){intlchilddep,rchilddep;if(p==NULL)return0;else{lchilddep=BTNodeDepth(p->lchild);rchilddep=BTNodeDepth(p->rchild);return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性。算法代码：intBTNodeDepth(BiTreep){标准文案 实用文档intlchilddep,rchilddep;if(p==NULL)return0;else{lchilddep=BTNodeDepth(p->lchild);rchilddep=BTNodeDepth(p->rchild);return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}选做实验：（代码可另附纸）5、补充二叉树层次遍历算法。（提示：利用队列实现）6、补充二叉树中序、后序非递归算法。三、实验小结掌握二叉树的基本特性，以及对递归和非递归的了解。并且通过实验对二叉树在算法的应用有了更深的理解。标准文案 实用文档四、教师评语标准文案 实用文档实验五图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法3、理解图的应用方法二、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include#defineN20#defineTRUE1#defineFALSE0intvisited[N];typedefstruct/*队列的定义*/{intdata[N];intfront,rear;}queue;typedefstruct/*图的邻接矩阵*/{intvexnum,arcnum;charvexs[N];intarcs[N][N];}graph;voidcreateGraph(graph*g);/*建立一个无向图的邻接矩阵*/voiddfs(inti,graph*g);/*从第i个顶点出发深度优先搜索*/voidtdfs(graph*g);/*深度优先搜索整个图*/voidbfs(intk,graph*g);/*从第k个顶点广度优先搜索*/voidtbfs(graph*g);/*广度优先搜索整个图*/voidinit_visit();/*初始化访问标识数组*/voidcreateGraph(graph*g)/*建立一个无向图的邻接矩阵*/{inti,j;charv;g->vexnum=0;g->arcnum=0;i=0;printf("输入顶点序列(以#结束)： ");while((v=getchar())!='#')标准文案 实用文档{g->vexs[i]=v;/*读入顶点信息*/i++;}g->vexnum=i;/*顶点数目*/for(i=0;ivexnum;i++)/*邻接矩阵初始化*/for(j=0;jvexnum;j++)g->arcs[i][j]=0;printf("输入边的信息： ");scanf("%d,%d",&i,&j);/*读入边i,j*/while(i!=-1)/*读入i,j为－1时结束*/{g->arcs[i][j]=1;g->arcs[j][i]=1;scanf("%d,%d",&i,&j);}}voiddfs(inti,graph*g)/*从第i个顶点出发深度优先搜索*/{intj;printf("%c",g->vexs[i]);visited[i]=TRUE;for(j=0;jvexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j]))dfs(j,g);}voidtdfs(graph*g)/*深度优先搜索整个图*/{inti;printf(" 从顶点%C开始深度优先搜索序列：",g->vexs[0]);for(i=0;ivexnum;i++)if(visited[i]!=TRUE)dfs(i,g);}voidbfs(intk,graph*g)/*从第k个顶点广度优先搜索*/{inti,j;queueqlist,*q;q=&qlist;q->rear=0;q->front=0;标准文案 实用文档printf("%c",g->vexs[k]);visited[k]=TRUE;q->data[q->rear]=k;q->rear=(q->rear+1)%N;while(q->rear!=q->front){i=q->data[q->front];q->front=(q->front+1)%N;for(j=0;jvexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j])){printf("%c",g->vexs[j]);visited[j]=TRUE;q->data[q->rear]=j;q->rear=(q->rear+1)%N;}}}voidtbfs(graph*g)/*广度优先搜索整个图*/{inti;printf(" 从顶点%C开始广度优先搜索序列：",g->vexs[0]);for(i=0;ivexnum;i++)if(visited[i]!=TRUE)bfs(i,g);}voidinit_visit()/*初始化访问标识数组*/{inti;for(i=0;i#include#defineN20typedefstructedgenode{/*图的邻接表：邻接链表结点*/intadjvex;/*顶点序号*/structedgenode*next;/*下一个结点的指针*/}edgenode;typedefstructvnode{/*图的邻接表：邻接表*/chardata;/*顶点信息*/intind;/*顶点入度*/structedgenode*link;/*指向邻接链表指针*/}vnode;voidcreateGraph_list(vnodeadjlist[],int*p)；/*建立有向图的邻接表*/voidtopSort(vnodeg[],intn)；/*拓扑排序*/voidcreateGraph_list(vnodeadjlist[],int*p){/*建立有向图的邻接表*/inti,j,n,e;charv;edgenode*s;i=0;n=0;e=0;标准文案 实用文档printf("输入顶点序列(以#结束)： ");while((v=getchar())!='#'){adjlist[i].data=v;/*读入顶点信息*/adjlist[i].link=NULL;adjlist[i].ind=0;i++;}n=i;*p=n;/*建立邻接链表*/printf(" 请输入弧的信息(i=-1结束)：i,j: ");scanf("%d,%d",&i,&j);while(i!=-1){s=(structedgenode*)malloc(sizeof(edgenode));s->adjvex=j;s->next=adjlist[i].link;adjlist[i].link=s;adjlist[j].ind++;/*顶点j的入度加1*/e++;scanf("%d,%d",&i,&j);}printf("邻接表:");for(i=0;i%d",s->adjvex);s=s->next;}}}voidtopSort(vnodeg[],intn){/*拓扑排序*/voidtopSort(vnodeg[],intn){/*拓扑排序*/intTopoSort(AdjListG){StackS;intindegree[MAX_VERTEX_NUM];inti,count,k;AreNode*p;FindID(G,indegree);InitStack(&s);标准文案 实用文档for(i=0;i#defineN20#defineTRUE1#defineINF32766/*邻接矩阵中的无穷大元素*/#defineINFIN32767/*比无穷大元素大的数*/typedefstruct{/*图的邻接矩阵*/intvexnum,arcnum;charvexs[N];intarcs[N][N];}graph;voidcreateGraph_w(graph*g,intflag);voidprim(graph*g,intu);voiddijkstra(graphg,intv);voidshowprim();voidshowdij();/*建带权图的邻接矩阵,若flag为1则为无向图，flag为0为有向图*/voidcreateGraph_w(graph*g,intflag){inti,j,w;charv;g->vexnum=0;g->arcnum=0;i=0;printf("输入顶点序列(以#结束)： ");while((v=getchar())!='#'){g->vexs[i]=v;/*读入顶点信息*/i++;}g->vexnum=i;for(i=0;i<6;i++)/*邻接矩阵初始化*/for(j=0;j<6;j++)g->arcs[i][j]=INF;printf("输入边的信息： ");scanf("%d,%d,%d",&i,&j,&w);/*读入边(i,j,w)*/while(i!=-1)/*读入i为－1时结束*/{g->arcs[i][j]=w;标准文案 实用文档if(flag==1)g->arcs[j][i]=w;scanf("%d,%d,%d",&i,&j,&w);}}voidprim(graph*g,intu)/*出发顶点u*/{intlowcost[N],closest[N],i,j,k,min;for(i=0;ivexnum;i++)/*求其他顶点到出发顶点u的权*/{lowcost[i]=g->arcs[u][i];closest[i]=u;}lowcost[u]=0;for(i=1;ivexnum;i++)/*循环求最小生成树中的各条边*/{min=INFIN;for(j=0;jvexnum;j++)/*选择得到一条代价最小的边*/if(lowcost[j]!=0&&lowcost[j]vexs[closest[k]],g->vexs[k],lowcost[k]);/*输出该边*/lowcost[k]=0;/*顶点k纳入最小生成树*/for(j=0;jvexnum;j++)/*求其他顶点到顶点k的权*/if(g->arcs[k][j]!=0&&g->arcs[k][j]arcs[k][j];closest[j]=k;}}}voiddijkstra(graphg,intv){/*dijkstra算法求单源最短路径*/intpath[N][N],dist[N],s[N];intmindis,i,j,u,k;for(i=0;i到各顶点的最短路径 ",g.vexs[v]);for(i=0;i顶点%c：",g.vexs[v],g.vexs[i]);if(dist[i]==INF)printf("无路径");else{printf("%d",dist[i]);printf("经过顶点：");for(j=0;j%c",g.vexs[j]);printf("->%c ",g.vexs[i]);}}}voidshowprim()/*最小生成树prim算法演示*/{graphga;createGraph_w(&ga,1);prim(&ga,0);标准文案 实用文档}voidshowdij(){/*dijstra算法演示*/graphga;createGraph_w(&ga,0);dijkstra(ga,0);}intmain(){showprim();/*prim算法演示*/getchar();showdij();/*dijstra算法演示*/return0;}§下面的输入分别验证prim算法和dijstra算法。输入的第一部分为无向图，求其最小生成树；输入的第二部分为有向图，求其最短路径。ABCDEF#0,1,60,2,10,3,51,2,51,4,32,3,52,4,62,5,43,5,24,5,6-1,-1,-1ABCDEF#0,2,100,5,1000,4,301,2,52,3,503,4,203,5,104,3,204,5,60-1,-1,-1§运行结果：（并画出两个图）标准文案 实用文档标准文案 实用文档三、实验小结学会了图的邻接矩阵和邻接表表示，并了解深度优先和广度优先搜索方法。理解图的应用方法四、教师评语标准文案 实用文档实验六查找一、实验目的1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。2、掌握线性表中顺序查找和折半查找的方法。3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。二、实验内容和要求1.静态查找表技术依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：查找表1：{8，15，19，26，33，41，47，52，64，90}，查找key=41查找表2：{12，76，29，15，62，35，33，89，48，20}，查找key=35查找key=41的比较次数：查找key=35的比较次数：l算法实现代码标准文案 实用文档2、哈希表的构造与查找/*采用开放地址法构造哈希表*/#include#include#defineMAXSIZE25#defineP13#defineOK1#defineERROR0#defineDUPLICATE-1标准文案 实用文档#defineTRUE1#defineFALSE0typedefstruct{/*哈希表元素结构*/intkey;/*关键字值*/intflag;/*是否存放元素*/}ElemType;typedefstruct{ElemTypedata[MAXSIZE];intcount;/*元素个数*/intsizeindex;/*当前哈希表容量*/}HashTable;intd1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};/*线性探测序列*/intd2[15]={0,1,-1,2*2,-2*2,3*3,-3*3,4*4,-4*4,5*5,-5*5,6*6,-6*6,7*7,-7*7};/*二次探测序列*/voiddataset(intds[],int*len);intInsertHash(HashTable*H,inte,intd[]);intCreateHash(HashTable*H,intds[],intlen,intd[]);intSearchHash(HashTable*H,inte,intd[]);voidmenu();/*输入查找表*/voiddataset(intds[],int*len){intn,m;n=0;printf(" 查找表输入：");while(scanf("%d",&m)==1){/*以输入一个非整数作为结束*/ds[n]=m;n++;}*len=n;}/*计算哈希地址，插入哈希表*/intInsertHash(HashTable*H,inte,intd[]){intk,i=1;k=e%P;while(H->data[k].flag==TRUE||k<0){k=(e%P+d[i])%MAXSIZE;i++;if(i>=15)returnERROR;}H->data[k].key=e;H->data[k].flag=TRUE;H->count++;标准文案 实用文档returnOK;}/*构造哈希表*/intCreateHash(HashTable*H,intds[],intlen,intd[]){inti;for(i=0;icount>=MAXSIZE)returnERROR;}returnOK;}/*初始化哈希表*/voidInitHash(HashTable*H){inti;for(i=0;idata[i].key=0;H->data[i].flag=FALSE;}}/*在哈希表中查找*/intSearchHash(HashTable*H,inte,intd[]){intk,i=1;k=e%P;while(H->data[k].key!=e){k=(e%P+d[i])%MAXSIZE;i++;if(i>=15)return-1;}returnk;}/*演示菜单*/voidmenu(){intchoice;int*p;HashTableh;h.count=0;h.sizeindex=MAXSIZE;inta[MAXSIZE]={0};inti,n,e;dataset(a,&n);/*建立查找表*/getchar();printf(" ");do{标准文案 实用文档printf(" ----哈希查找演示---- ");printf(" 1.线性探测构造哈希表 ");printf(" 2.二分探测构造哈希表 ");printf(" 3.退出 ");printf(" 输入选择：");scanf("%d",&choice);if(choice==1)p=d1;elseif(choice==2)p=d2;elsereturn;InitHash(&h);/*初始化哈希表*/if(!(i=CreateHash(&h,a,n,p)))/*构造哈希表*/printf(" 哈希表构造失败！ ");elseif(i==DUPLICATE)printf(" 哈希表具有重复关键字！ ");else{printf(" 哈希表： ");for(i=0;i#include#defineMAX50intslist[MAX];/*待排序序列*/voidinsertSort(intlist[],intn);voidcreateList(intlist[],int*n);voidprintList(intlist[],intn);voidheapAdjust(intlist[],intu,intv);voidheapSort(intlist[],intn);/*直接插入排序*/voidinsertSort(intlist[],intn){inti=0,j=0,node=0,count=1;printf("对序列进行直接插入排序： ");printf("初始序列为： ");printList(list,n);for(i=1;i=0&&node=0;i--){heapAdjust(list,i,n-1);/*建立初始堆*/}printf("建立的初始堆为： ");printList(list,n);for(i=n-1;i>=1;i--){/*循环，完成堆排序*/temp=list[0];list[0]=list[i];标准文案 实用文档list[i]=temp;/*将第一个元素同当前区间内最后一个元素对换*/heapAdjust(list,0,i-1);/*筛选出list[1]结点*/printf("第%d次排序结果： ",count++);printList(list,n);}}/*生成待排序序列*/voidcreateList(intlist[],int*n){inti=0,a;printf("请输入待排序序列(长度小于50,以输入一个字符结束): ");while(scanf("%d",&a)==1){list[i]=a;i++;}*n=i;getchar();}/*输出排序结果*/voidprintList(intlist[],intn){inti=0;for(;i