数据结构实验指导手册

实验一线性表的次序储存实验一、实验目的1、掌握用VisualC++上机调试次序表的基本方法2、掌握次序表的基本操作，插入、删除、查找、以及有序次序表的归并等算法的实现二、实验内容1、次序表基本操作的实现[问题描绘]当我们要在次序表的第i个地点上插入一个元素时，一定先将次序表中第i个元素以后的全部元素挨次后移一个地点，以便凌空一个地点，再把新元素插入到该地点。假如欲删除第i个元素时，也一定把第i个元素以后的全部元素前移一个地点。[基本要求]要求生成次序表时，能够键盘上读取元素，用次序储存结构实现储存。[实现提示]要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。[程序实现]#include<>#include<>typedefintDataType;definemaxnum20typedefstruct{intdata[maxnum];intlength;}SeqList;/*插入函数*/intinsert(SeqList*L,inti,DataTypex)/*将新结点x插入到次序表L第i个地点*/{intj;if(i<0||i>(*L).length+1){printf("\ni值不合法!");return0;}if((*L).length>=maxnum-1){printf("\n表满不可以插入!");return0;}for(j=(*L).length;j>=i;j--)(*L).data[j+1]=(*L).data[j];(*L).data[i]=x;(*L).length++;return1;}/*删除函数*/intdelete(SeqList*L,inti)/*从次序L中删除第i个结点*/{intj;if(i<0||i>(*L).length){printf("\n

删除地点错误

!");return0;}for(j=i+1;j<=(*L).length;j++)(*L).data[j-1]=(*L).data[j];(*L).length--;return1;}/*生成次序表*/voidcreatlist(SeqList*L){intn,i,j;printf("请输入次序表L的数据个数：\n");scanf("%d",&n);for(i=0;i<n;i++){printf("data[%d]=",i);scanf("%d",&((*L).data[i]));}(*L).length=n-1;printf("\n");}/*creatlist*//*输出次序表L*/printout(SeqList*L){inti;for(i=0;i<=(*L).length;i++){printf("data[%d]=",i);printf("%d",(*L).data[i]);}/*printout*/printf("\n");}main(){SeqList*L;charcmd;inti,t,x;clrscr();creatlist(L);do{printf("\ni,I-----printf("d,D-----printf("q,Q-----

插入\n");删除\n");退出\n");do{cmd=getchar();}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q'));switch(cmd){case'i':case'I':printf("\nPleaseinputtheDATA:");scanf("%d",&x);printf("\nWhere?");scanf("%d",&i);insert(L,i,x);printout(L);break;case'd':case'D':printf("\nWheretoDelete?");scanf("%d",&i);delete(L,i);printout(L);break;}}while((cmd!='q')&&(cmd!='Q'));}2、有序次序表的归并[问题描绘]已知次序表la和lb中的数据元素按非递减有序摆列，将la和lb表中的数据元素，归并成为一个新的次序表lc[基本要求]lc中的数据元素仍按非递减有序摆列，并且不损坏la和lb表[程序实现]#include<>#definemaxnum20typedefintDataType;typedefstruct{DataTypedata[maxnum];intlength;}SeqList;intMergeQL(SeqListla,SeqListlb,SeqList*lc){inti,j,k;if+1++1>maxnum){printf("\narrayoverflow!");return0;}i=j=k=0;while(i<=&&j<={if[i]<=[j])lc->data[k++]=[i++];elselc->data[k++]=[j++];}/*办理节余部分*/while(i<=lc->data[k++]=[i++];while(j<=lc->data[k++]=[j++];lc->length=k-1;return1;}main(){SeqListla={{3,4,7,12,15},4};SeqListlb={{2,5,7,15,18,19},5};SeqListlc;inti;if(MergeQL(la,lb,&lc)){printf("\n");for(i=0;i<=;i++)printf("%4d",[i]);}}实验二单链表实验一、实验目的1、掌握用VisualC++上机调试单链表的基本方法2、掌握单链表的插入、删除、查找、求表长以及有序单链表的归并算法的实现二、实现内容1、单链表基本操作的实现[问题描绘]要在带头结点的单链表h中第i个数据元素以前插入一个数据元素x，第一需要在单链表中找寻到第i-1个结点并用指针p指示，而后申请一个由指针s指示的结点空间，并置x为其数据域值，最后改正第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，第一要计数找寻到第i个结点并使指针p指向其前驱第i-1个结点，而后删除第i个结点并开释被删除结点空间。[基本要求]用链式储存结构实现储存[实现提示]链式储存结构不是随机储存结构，即不可以直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数找寻。[程序实现]include<>include<>typedefcharDataType;typedefstructnode{DataTypedata;structnode*next;

/*/*

结点的数据域结点的指针域

*/*/}ListNode;voidInit_List(ListNode**L){(*L)=(ListNode*)malloc(sizeof(ListNode));/*产生头结点*/(*L)->next=NULL;}intList_Length(ListNode*L){intn=0;ListNode*p=L->next;while(p!=NULL){n++;p=p->next;}returnn;}ListNode*GetNode(ListNode*L,inti){intj;ListNode*p;p=L;j=0;/*while(p->next&&j!=i)/*{p=p->next;j++;}if(i==j)returnp;/*找到了第elsereturnNULL;/*当i<0或}

从头结点开始扫描*/顺指针向后扫描,直到p->nexti个结点*/i>0时,找不到第i个结点*/

为NULL或i=j

为止*/voidInsertList(ListNode*L,DataTypex,inti){ListNode*p,*s;p=GetNode(L,i-1);/*if(p==NULL)/*i<1

找寻第i-1个结点*/或i>n+1时插入地点

i有错*/{printf("positionerror");return;}s=(ListNode*)malloc(sizeof(ListNode));s->data=x;s->next=p->next;p->next=s;}voidDeleteList(ListNode*L,inti){ListNode*p,*r;p=GetNode(L,i-1);/*if(p==NULL||p->next==NULL)/*i<1

找到第i-1或i>n

个结点*/时,删除地点错

*/{printf("positionerror");return;}r=p->next;p->next=r->next;

/*

/*

使r将ai

指向被删除的结点从链上删除*/

a*/free(r);}/*使用头插法成立带头结点链表算法*/ListNode*CreatListF(void){charch;ListNode*head=(ListNode*)malloc(sizeof(ListNode));/*ListNode*s;/*工作指针*/

生成头结点

*/head->next=NULL;ch=getchar();/*

读入第

1个字符*/while(ch!='\n'){s=(ListNode*)malloc(sizeof(ListNode));/*生成新结点*/s->data=ch;/*将读入的数据放入新结点的数据域中s->next=head->next;head->next=s;ch=getchar();/*读入下一字符*/

*/}returnhead;}/*使用尾插法成立带头结点链表算法*/ListNode*CreatListR1(void){charch;ListNode*head=(ListNode*)malloc(sizeof(ListNode));/*ListNode*s,*r;/*工作指针*/r=head;/*尾指针初值也指向头结点*/

生成头结点

*/while((ch=getchar())!='\n'){s=(ListNode*)malloc(sizeof(ListNode));s->data=ch;r->next=s;r=s;}r->next=NULL;/*终端结点的指针域置空,或空表的头结点指针域置空*/returnhead;}/*复制链表A中的内容到表B中*/voidcopy(ListNode*a,ListNode*b){ListNode*pa=a->next;ListNode*u;ListNode*rb=b;while(pa!=NULL){u=(ListNode*)malloc(sizeof(ListNode));u->data=pa->data;rb->next=u;rb=u;pa=pa->next;}rb->next=NULL;}/*输出带头结点的单链表*/voidDisplaySL(ListNode*la,char*comment){ListNode*p;p=la->next;if(p)printf("\n%s\n",comment);while(p){printf("%4c",p->data);p=p->next;}printf("\n");}/*主函数*/main(){ListNode*la,*lb,*lc,*p;intn,x,i;printf("\n用头插法成立链表la，请输入节点内容:");la=CreatListF();DisplaySL(la,"重生成链la节点内容:");printf("\n链表la的长度:%2d",List_Length(la));printf("\n请输入要插入的元素:");scanf("%c",&x);printf("\n请输入要插入的地点：");scanf("%d",&i);InsertList(la,x,i);DisplaySL(la,"插入后链la节点内容");printf("\n请输入要删除元素的地点：");scanf("%d",&i);DeleteList(la,i);DisplaySL(la,"删除后链la节点内容");printf("\n用尾插法成立链表lb，请输入节点内容:");fflush(stdin);lb=CreatListR1();DisplaySL(lb,"重生成链lb节点内容:");Init_List(&lc);copy(la,lc);DisplaySL(lc,"

复制生成的链

lc

节点内容

:");}2、有序单链表的归并[问题描绘]已知单链表la和lb中的数据元素按非递减有序摆列，将据元素,归并为一个新的单链表lc,lc中的数据元素仍按非递减有序摆列。[基本要求]不损坏la表和lb表的结构。[程序实现]

la和lb中的数include<>#include<>#defineNULL0typedefintDataType;typedefstructSLNode{DataTypedata;structSLNode*next;}slnodetype;intMergeSL(slnodetype*la,slnodetype*lb,slnodetype**lc);intCreateSL(slnodetype*la,intn);voidDisplaySL(slnodetype*la,char*comment);main(){slnodetype*la,*lb,*lc,*p;intn,m;la=(slnodetype*)malloc(sizeof(slnodetype));la->next=NULL;lb=(slnodetype*)malloc(sizeof(slnodetype));lb->next=NULL;lc=(slnodetype*)malloc(sizeof(slnodetype));lc->next=NULL;printf("\n输入链la节点数:");scanf("%d",&n);printf("\n输入链la节点内容:");CreateSL(la,n);DisplaySL(la,"链la节点内容:");printf("\n输入链lb节点数:");scanf("%d",&m);printf("\n输入链lb节点内容:");CreateSL(lb,m);DisplaySL(lb,"链lb节点内容:");if(MergeSL(la,lb,&lc))DisplaySL(lc,"getchar();}

合成后的链

lc:");intMergeSL(slnodetype*la,slnodetype*lb,slnodetype**lc){slnodetype*pa,*pb,*pc;lc=(slnodetype*)malloc(sizeof(slnodetype));pa=la->next;pb=lb->next;pc=*lc;while(pa&&pb){pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;if(pa->data<=pb->data){pc->data=pa->data;pa=pa->next;}else{pc->data=pb->data;pb=pb->next;}}while(pa)/*插入la链的节余段*/{pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;pc->data=pa->data;pa=pa->next;}/*插入lb链的节余段*/while(pb){pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;pc->data=pb->data;pb=pb->next;}/*生成单链表*/intCreateSL(slnodetype*la,intn){inti;slnodetype*p,*q;q=la;for(i=1;i<=n;i++){p=(slnodetype*)malloc(sizeof(slnodetype));scanf("%d",&p->data);q->next=p;q=p;}q->next=NULL;return1;}/*输出单链表*/voidDisplaySL(slnodetype*la,char*comment){slnodetype*p;p=la->next;if(p)printf("\n%s\n",comment);while(p){printf("\n%3d",p->data);p=p->next;}printf("\n");}实验三循环链表实验一、实验目的1、掌握用VisualC++上机调试循环链表的基本方法2、进一步掌握循环单链表的插入、删除、查找算法的实现二、实现内容1.约瑟夫环问题[问题描绘]设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始从头报数，数到M的人以出列，这样下去，直到全部人都出列为此。试设计确立他们的出列序次序列的程序。[基本要求]选择单向循环链表作为储存结构模拟整个过程，并挨次输出列的各人的编号。[实现提示

]

程序运转以后，第一要求用户指定初始报数的下限值，能够

n<=30,此题循环链表可不设头节点，并且一定注意空表和非空表的界线。如n=8,m=4时，若从第一个人，设每个人的编号挨次为1，2，3，开始报数，则获得的出列序次为4，8，5，2，1，3，7，6，以下列图所示，内层数字表示人的编号，每个编号外层的数字代表人出列的序号。[程序实现]#include<>#include<>typedefstructnode{intnum;structnode*next;}linklist;linklist*creat(head,n)/*使n个人围成一圈，并给每个人表记号数*/linklist*head;intn;{linklist*s,*p;inti;s=(linklist*)malloc(sizeof(linklist));head=s;s->num=1;p=s;for(i=2;i<=n;i++){s=(linklist*)malloc(sizeof(linklist));s->num=i;p->next=s;p=s;}p->next=head;return(head);}/*creat*/linklist*select(linklist*head,intm){linklist*p,*q;inti,t;p=head;t=1;q=p;/*q为p的前趋指针*/p=p->next;do{t=t+1;/*if(t%m==0)

报一次数

*/{printf("%4d",p->num);q->next=p->next;free(p);p=q->next;}else{q=p;p=p->next;}}while(q!=p);head=p;printf("%4d",p->num);return(head);}/*select*/main(){intn,m;linklist*head;printf("\ninputthetotalnumber:n=");scanf("%d",&n);printf("\ninputthenumbertocall:m=");scanf("%d",&m);head=creat(head,n);head=select(head,m);printf("\nthelastoneis:%d",head->num);}/*main*/思虑题：编程实现两个循环单链表的归并。实验四栈、行列的实现及应用一、实验目的1、掌握栈和行列的次序储存结构和链式储存结构，以便在实质背景下灵巧运用。2、掌握栈和行列的特色，即先进后出与先进先出的原则。3、掌握栈和行列的基本操作实现方法。二、实验内容1、实现栈的次序储存defineMAXSIZE100typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*s){s->top=0;return1;}intStackEmpty(SeqStack*s){if(s->top==0)return1;elsereturn0;}intStackFull(SeqStack*s){if(s->top==MAXSIZE-1)return1;elsereturn0;}voidPush(SeqStack*s,intx){if(StackFull(s)){printf("thestackisoverflow!\n");return0;}else{s->data[s->top]=x;s->top++;}}voidDisplay(SeqStack*s){if(s->top==0)printf("thestackisempty!\n");else{while(s->top!=0){printf("%d->",s->data[s->top]);s->top=s->top-1;}}}ElemTypePop(SeqStack*s){if(StackEmpty(s))return0;elsereturns->data[--s->top];}ElemTypeStackTop(SeqStack*s){inti;if(StackEmpty(s))return0;else{i=s->top-1;returns->data[i];}/*

返回栈顶元素的值，但不改变栈顶指针

*/}main(SeqStack*p){intn,i,k,h,x1,x2,select;printf("createaemptystack!\n");InitStack(p);printf("inputastacklength:\n");scanf("%d",&n);for(i=0;i<n;i++){printf("inputastackvalue:\n");scanf("%d",&k);Push(p,k);}printf("select1:Display()\n");printf("select2:Push()\n");printf("select3:Pop()\n");printf("select4:StackTop()\n");printf("inputayourselect(1-4):\n");scanf("%d",&select);switch(select){case1:{display(p);break;}case2:{printf("inputapushavalue:\n");scanf("%d",&h);Push(p,h);display(p);break;}case3:{x1=Pop(p);printf("x1->%d\n",x1);display(p);break;}case4:{x2=StackTop(p);printf("x2->%d",x2);break;}}}2、利用栈实现数制变换#defineMAXSIZE100typedefintElemType；/*将次序栈的元素定义为整型*/typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*s){s->top=0;return1;}intStackEmpty(SeqStack*s){if(s->top==0)return1;elsereturn0;}intStackFull(SeqStack*s){if(s->top==m-1)return1;elsereturn0;}voidPush(SeqStack*s,intx){if(StackFull(s)){printf("thestackisoverflow!\n");return0;}else{s->data[s->top]=x;s->top++;}}ElemTypePop(SeqStack*s){ElemTypey;if(StackEmpty(s)){printf("thestackisempty!\n");return0;}else{y=s->data[s->top];s->top=s->top-1;returny;}}ElemTypeStackTop(SeqStack*s){if(StackEmpty(s))return0;elsereturns->data[s->top];}voidDec_to_Ocx(intN)/*n

是非负的十进制整数，输出等值的八进制数

*/{SeqStack*S；

/*

定义一个次序栈

*/ElemTypex；Init_SeqStack(S)

；

/*

初始化栈*/if(N<0){printf("\nError,Thenumbermustbeover0

。")；return

；}if(!N)Push(S,0)

；while(N){Push(SN=N/8

/*自右向左产生八进制的各位数字，并将其进栈，N%8)；/*余数入栈*/；/*商作为被除数*/

*/}printf("Number%dconvertedtoOCT:",N);while(StackEmpty(S))/*栈非空时退栈输出

*/{x=Pop(S)

；printf(

“%d”

,x)

；}printf("\n");}main(){intn;printf("InputanumbertoconverttoOCT:\n");scanf("%d",&n);Dec_to_Ocx(n);}3、实现循环行列的次序储存#definemaxsize100typedefstruct{intdata[maxsize];intfront;intrear;}seqqueue;intsqinit(seqqueue*p){p->front=0;p->rear=0;return1;}intenqueue(seqqueue*q,inte){if((q->rear+1)%maxsize==q->front)return0;elseq->data[q->rear]=e;q->rear=(q->rear+1)%maxsize;return1;}intdequeue(seqqueue*q){inte;if(q->front==q->rear)return0;e=q->data[q->front];q->front=(q->front+1)%maxsize;returne;}intempty(seqqueue*q){intv;if(q->front==q->rear)v=1;elsev=0;returnv;}intgethead(seqqueue*q){inte;if(q->front==q->rear)e=-1;elsee=q->data[q->front];returne;}voiddisplay(seqqueue*q){ints;s=q->front;printf("thesequeueisdisplay:\n");if(q->front==q->rear)printf("thesequeueisempty!");else{while(s<q->rear){printf("->%d",q->data[s]);s=(s+1)%maxsize;}printf("\n");}}main(seqqueue*head){intn,i,m,x,y,select,xq;printf("createaemptysequeue\n");sqinit(head);printf("pleaseinputthesequeuelength:\n");scanf("%d",&n);for(i=0;i<n;i++){printf("pleaseinputasequeuevalue:\n");scanf("%d",&m);enqueue(head,m);}printf("head->rear:%d\n",head->rear);printf("head->front:%d\n",head->front);display(head);printf("select1****enqueue()\n");printf("select2****dequeue()\n");printf("select3****empty()\n");printf("select4****gethead()\n");printf("select5****display()\n");printf("pleaseselect(1--5):");scanf("%d",&select);switch(select){case1:{printf("pleaseinputavalue:\n");scanf("%d",&x);enqueue(head,x);display(head);break;}case2:{dequeue(head);display(head);break;}case3:{if(empty(head))printf("thesequeueisempty");elseprintf("thesequeueisfull");}case4:{y=gethead(head);printf("outputheadvalue:%d\n",y);break;}case5:{display(head);break;}}}实验五串及数组的实验一、实验目的1、认识串及数组的两种储存方法，掌握数组在作为储存结构中的地点计算方法。2、认识稀少矩阵的两种压缩储存方法的特色和合用范围，领悟稀少矩阵运算采纳的办理方法。二、实验内容1、次序串的基本操作#defineMaxSize100typedefstruct{charstr[MaxSize];intlen;}strtype;voidassign(strtype*s,chart[]){inti=0;while(t[i]!='\0'){s->str[i]=t[i];i++;}s->str[i]='\0';s->len=i;}voidstrcopy(strtype*s,strtypet){inti;for(i=0;i<=;i++)s->str[i]=[i];}intlength(strtypes){return;}intequal(strtypes,strtypet){inti=0;if!=return(0);else{for(i=0;i<;i++)if[i]!=[i])return(0);return(1);}}strtypeconcat(strtypes,strtypet){strtyper;inti,j;for(i=0;i<;i++)[i]=[i];for(j=0;j<=;j++)[+j]=[j];=i+j;return(r);}intindex(strtypes,strtypet){inti,j,k;for(i=0;[i];i++)for(j=i,k=0;[j]==[k];j++,k++)if(![k+1])return(i);return(-1);}strtypesubstr(strtypes,inti,intk){strtypet;intj;for(j=i;j<i+k;j++)[j-i]=[j];=k;[]='\0';return(t);}voidinsert(strtype*s,inti,strtypet){strtyper;intj;if(i>s->len)printf("

地点参数值错误

\n");else{for(j=i;j<s->len;j++)

/*

将s的第

i个地点以后的字串复制到

r中*/[j-i]=s->str[j];=j-i;[]='\0';for(j=0;j<;j++)

/*

将t

串通接到

s的第

i

个字符以后

*/s->str[i+j]=[j];for(j=0;j<;j++)

/*

将r

串通接到

s串以后*/s->str[i++j]=[j];s->len=s->len+;

/*

改正

s串长度*/s->str[s->len]='\0';}}voiddelete(strtype*s,inti,intk){intj;if(i>s->len||i+k>s->len)printf("地点参数值错误\n");else{for(j=i+k;j<s->len;j++)

/*

将s的第

i+k

个地点以后的字串前移

k位*/s->str[j-k]=s->str[j];s->len=s->len-k;

/*

改正

s的长度*/s->str[s->len]='\0';}}strtypereplace(strtypes,strtypet,strtypev){inti;i=index(s,t);while(i>=0){delete(&s,i,;insert(&s,i,v);i=index(s,t);}return(s);}voiddisplay(strtypes){printf("字符串:%s\n",;}main(){strtypes,t,r,v;assign(&s,"aababababad");assign(&t,"aba");assign(&v,"121");display(s);display(t);display(v);printf("sprintf("t

长度=%d\n",length(s));与v连结");display(concat(t,v));printf("s

中的

t

替代成

v后的");display(replace(s,t,v));}2、三元组稀少矩阵的基本操作#include<>#defineMax100#defineM3#defineN3#defineK3typedefintsmat[Max][3];voiddisplay();voidcreatmat(intA[M][N],smatB)/*A是一个稀少矩阵,B是产生的相对应的三元组储存*/{inti,j,k=1;for(i=0;i<M;i++)/*按行优先次序扫描A的元素,不为0者存入B中*/for(j=0;j<N;j++)if(A[i][j]!=0){B[k][0]=i;B[k][1]=j;B[k][2]=A[i][j];k++;}B[0][0]=M;B[0][1]=N;B[0][2]=k-1;/*

存入非0元素个数

*/}intfindval(smatA,intx){inti,t;t=A[0][2];/*非0元素个数i=1;while(i<=t&&A[i][2]!=x)i++;/*if(i<=t)return(1);elsereturn(0);

*/

查找等于

x的元素值

*/}voidtrsmat(smatA,smatB)/*A

是稀少矩阵的三元组形式

,B是寄存A的转置矩阵的三元组

*/{intm,n,p,q,t,col;/*m:A中的行数;n:A中的列数;t:A/*q:B的下一个项地点;p:A

的非0元素个数的目前项*/

*/m=A[0][0];n=A[0][1];t=A[0][2];B[0][0]=n;B[0][1]=m;B[0][2]=t;/*if(t>0)/*{

产生第0行的结果非0元素才做转置

*/*/q=1;for(col=0;col<n;col++)

/*

按列转置

*/for(p=1;p<=t;p++)if(A[p][1]==col){B[q][0]=A[p][1];B[q][1]=A[p][0];B[q][2]=A[p][2];q++;}}}voidmatadd(smatA,smatB,smatC){inti=1,j=1,k=1;while(i<=A[0][2]&&j<=B[0][2])/*若A的目前项的行号等于B的目前项的行号,则比较其列号/*存入C中,假如列号也相等,则将对应的元素值相加后存入

,将较小列的项C中*/

*/if(A[i][0]==B[j][0])if(A[i][1]<B[j][1]){C[k][0]=A[i][0];C[k][1]=A[i][1];C[k][2]=A[i][2];k++;i++;}elseif(A[i][1]>B[j][1]){C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=B[j][2];k++;j++;}else{C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=A[i][2]+B[j][2];k++;i++;j++;}elseif(A[i][0]<B[j][0])/*若A的目前项的行号小于B的目前项的行号,则将A的项存入C中*/{C[k][0]=A[i][0];C[k][1]=A[i][1];C[k][2]=A[i][2];k++;i++;}else/*若A的目前项的行号大于B的目前项的行号,则将B的项存入C中*/{C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=B[j][2];k++;j++;}C[0][0]=A[0][0];/*产生第0行的结果*/C[0][1]=A[0][1];C[0][2]=k-1;}voidmatmul(intm,intn,intk,smatA,smatB,smatC){inti,j,l,p=1,s;for(i=0;i<m;i++)for(j=0;j<k;j++){s=0;/*计算C[i][j]之值*/for(l=0;l<n;l++)s=s+value(A,i,l)*value(B,l,j);if(s!=0)/*产生一个三元组元素*/{C[p][0]=i;C[p][1]=j;C[p][2]=s;p++;}}C[0][0]=m;/*产生第0行的结果*/C[0][1]=k;C[0][2]=p-1;}intvalue(smatC,inti,intj)/*

用在matmul函数之中

,计算C[i][j]

的值*/{intk=1;while(k<=C[0][2]&&(C[k][0]!=i||C[k][1]!=j))k++;if(k<=C[0][2])return(C[k][2]);/*elsereturn(0);/*

找到了返回该地点的值未找到说明该元素为

*/0*/}voiddisplay(char*s,smatA){inti;printf("%s三元组:\n\tRowColVal\n",s);for(i=1;i<=A[0][2];i++)printf("\t%4d%4d%4d\n",A[i][0],A[i][1],A[i][2]);}main(){intA[M][N]={{0,1,0},{6,0,0},{1,0,0}};intB[M][N]={{1,2,0},{0,4,0},{0,3,0}};smatC,D,E,F,G;creatmat(A,C);creatmat(B,D);display("C

矩阵",C);printf("C(0,1)处的值:%d\n",value(C,0,1));printf("元素3能否存在:%d\n",findval(C,2));matadd(C,D,E);display("E=A+B",E);matmul(M,N,K,C,D,F);display("F=A×B",F);trsmat(C,G);display("C'",G);}c实验七查找一、实验目的1、掌握查找的不一样方法，并能用高级语言实现查找算法。2、娴熟掌握次序表的查找方法和有序次序表的折半查找算法以及静态查找树的结构方法和查找算法。3、掌握二叉排序树的生成、插入、删除、输出运算。二、实验内容1、次序表的次序查找#include<>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intseq_search(KEYTYPEk,SSTABLE*st){/*次序表上查找元素*/intj;j=st->len;st->r[0].key=k;while(st->r[j].key!=k)returnj;

/*/*st->r[0]j--;/*/*j=0,

次序表元素个数*/单元作为监督哨*/次序表从后向前查找*/找不到；j<>0找到*/}main(){SSTABLEa;inti,j,k;printf("请输入次序表元素(整型量)，用空格分开，j=0;k=1;i=0;scanf("%d",&i);while(i!=-99){j++;[k].key=i;k++;scanf("%d",&i);}/*=j;printf("\n次序表元素列表显示：");for(i=1;i<=;i++)printf("%d",[i].key);printf("\n");printf("\n输入待查元素重点字:");scanf("%d",&i);k=seq_search(i,&a);if(k==0)printf("表中待查元素不存在\n\n");elseprintf("表中待查元素存在,为第%d个元素\n"}

-99为结束标记输入次序表元素，k);

：");*/2、有序次序表的二分查找的递归算法#include<>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intsearch_bin(KEYTYPEk,intlow,inthigh){/*有序表上二分法查找,递归算法*/intmid;mid=-1;if(low<=high)/*low表示目前表中第1个元素所在下标*//*high表示目前表中最后一个元素所在下标*/{mid=(low+high)/2;/*mid表示目前表中中间一个元素所在下标*/if[mid].key<k)mid=search_bin(k,mid+1,high);/*二分法递归查找*/elseif[mid].key>k)mid=search_bin(k,low,high-1);}returnmid;/*mid=-1查找不行功；mid!=-1查找成功*/}main(){SSTABLEa;inti,j,k;printf("请输入有序表元素，元素为整型量（从小到大输入），用空格分开，-99为结束标记：");j=0;k=1;i=0;scanf("%d",&i);while(i!=-99){j++;[k].key=i;k++;scanf("%d",&i);}/*输入有序表元素*/=j;printf("\n有序表元素列表显示：");for(i=1;i<=;i++)printf("%d",[i]);printf("\n");printf("\n输入待查元素重点字:");scanf("%d",&i);k=search_bin(i,1,;if(k==-1)printf("表中待查元素不存在\n\n");elseprintf("表中待查元素存在,为第%d个元素\n"，k);}3、在用拉链法解决矛盾的散列表上插入元素#include<>#include<>#defineKEYTYPEint#defineMAXSIZE100typedefstructnode{KEYTYPEkey;structnode*next;}CHAINHASH;voidcreat_chain_hash(CHAINHASH*HTC[]){/*成立开散列表*/CHAINHASH*p;inti,j;scanf("%d",&i);/*输入开散列表元素重点字值*/while(i!=-99){j=i%13;/*散列函数：ADD(rec(key))=keyMOD13*/p=(CHAINHASH*)malloc(sizeof(CHAINHASH));/*

生成结点，挂入开散列表中

*/p->next=HTC[j];p->key=i;HTC[j]=p;scanf("%d",&i);}

/*

输入开散列表元素重点字值

*/}voidprint_chain_hash(CHAINHASH*HTC[]){/*显示开散列表*/inti;CHAINHASH*p;for(i=0;i<13;i++){if(HTC[i]==NULL)printf("%3d|^\n",i);else{p=HTC[i];printf("%3d|->",i);while(p!=NULL){printf("%5d->",p->key);p=p->next;}printf("\n");}}}intsearch_chain_hash(CHAINHASH*HTC[],intk){/*开散列表中查找元素*/CHAINHASH*p;intj;j=k%13;/*散列函数：ADD(rec(key))=keyMOD13*/p=HTC[j];if(p!=NULL)/*开散列表中查找元素*/{while((p->key!=k)&&(p->next!=NULL))p=p->next;if(p->key==k)return1;/*查找成功，返回1*/elsereturn0;/*查找不行功，返回0*/}elsereturn0;}insert_chain_hash(CHAINHASH*HTC[],inti){/*元素插入散列表中

*/CHAINHASH*p;intj;j=i%13;/*

散列函数：

ADD(rec(key))=keyMOD13*/p=(CHAINHASH*)malloc(sizeof(CHAINHASH));/*生成结点，挂入开散列表中*/p->next=HTC[j];p->key=i;HTC[j]=p;}main(){CHAINHASH*HTC[MAXSIZE];inti,k;printf("\n成立开散列表\n\n");for(i=0;i<MAXSIZE;i++)HTC[i]=NULL;printf("请输入开散列表元素重点字值,重点字为正整型量，用空格分开，-99为结束标记:");creat_chain_hash(HTC);printf("显示成立的开散列表:\n\n");print_chain_hash(HTC);printf("\n输入待插入元素重点字:");scanf("%d",&i);k=search_chain_hash(HTC,i);if(k==0){printf("表中待插入元素不存在,可插入散列表中\n\n");insert_chain_hash(HTC,i);printf("显示插入后的开散列表:\n\n");print_chain_hash(HTC);}elseprintf("表中待插入元素存在，不行插入散列表中\n\n");}实验八排序一、实验目的1、掌握常用的排序方法，并能用高级语言实现排序算法。2、深刻理解排序的定义和各样排序方法的特色，并能加以灵巧运用。3、认识各样方法的排序过程及依照的原则，并掌握各样排序方法的时间复杂度的剖析方法。二、实验内容1、排序综合练习#include<>#defineKEYTYPEint#defineMAXSIZE100intcreateList(RECNODE*r){intj,k;printf("\n\n输入待排序数据(整数，以空格分开，0scanf("%d",&j);

结束):");

k=

0;while(j!=0){k++;r[k].key=j;scanf("%d",&j);}returnk;}frontdisplayList(RECNODE*r,intn){inti;printf("\n排序前:");for(i=0;i<n;i++)printf("%d",r[i+1].key);printf("\n\n");}reardisplayList(RECNODE*r,intn){inti;printf("\n\n排序后:");for(i=0;i<n;i++)printf(