《数据结构实验》由会员分享，可在线阅读，更多相关《数据结构实验（23页珍藏版）》请在金锄头文库上搜索。
1、实 验 1( C 语 言 补 充 实 验)有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一个顺序表C,且C的元素也是从小到大的升序排列。#includemain()intn,m,i=0,j=0,k=0,a5,b5,c10;/*必须设个m做为数组的输入的计数器，不能用i,不然进行到 while 时 i 直接为 5*/for(m=0;m=4;m+)scanf(%d,&am);/ 输入数组afor(m=0;m=4;m+)scanf(%d,&bm);/ 输入数组bwhile(i5&j5)if(aibj)ck=bj;k+;j+;elseck=ai;k+;i+;j+;/使输入的两组数组中
2、相同的数只输出一个if(i5)for(n=i;n5;n+)ck=an;k+;elseif(j5)for(n=j;n5;n+)ck=bn;k+;for(i=0;ik;i+)printf(%3d,ci);printf(n); 求AAB#includemain()inti,j,k=0,a5,b5,c5;/A=a5,B=b5,A n B=c5for(i=0;i5;i+)scanf(%d,&ai);/ 输入a 数组for(i=0;i5;i+)scanf(%d,&bi);/ 输入b 数组for(i=0;i5;i+) for(j=0;j5;j+) if(ai=bj)ck=ai;k+;/ 当有元素重复时，只取
3、一个放入 c 中for(i=0;ik;i+)printf(%3d,ci);printf(n);实验2 (C语言补充实验)已知一个有序整型数组，编程将一个整型数m 插入到该数组中，使得插入后的数组任然有序。#include#defineN4main()inti,j,m,k,aN+1;/k 为最后输出数组的长度变量printf( 请输入有序整型数组a%dn,N);for(i=0;iN;i+)scanf(%d,&ai);printf( 请输入整型数mn);scanf(%d,&m);if(a0a1)/ 递增有序数组for(i=0;iN;i+)if(m=ai)k=N;break;/m 和数组元素相同if
4、(mi;j-)aj=aj-1;ai=m;k=N+1;break;if(i=N)k=N+1;aN=m;/m 比所有元素大if(a0a1)/ 递减有序数组for(i=0;iai)/m 比当前元素大，数组右移for(j=N;ji;j-)aj=aj-1;ai=m;k=N+1;break;if(i=N)k=N+1;aN=m;/m 比所有元素小for(i=0;ik;i+)printf(%3d,ai);printf(n);补充实验已知线性表LA和LB中的数据元素按值非递减有序排序，现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列。#includeintGetelem(int
5、a,intt);/ 声明得到数组元素函数voidListInsert(intb,intp,intq);/ 声明插入数组函数main()intm,i=0,j=0,k=0,LA5,LB5,LC10,ai,bj;for(m=0;m5;m+)scanf(%d,&LAm);输入 La数组for(m=0;m5;m+)scanf(%d,&LBm);/输入 Lb数组while(i5&j5)ai=Getelem(LA,i);/通过函数得到数组元素bj=Getelem(LB,j);if(aibj)ListInsert(LC,k+,bj);j+;/ 将较小的元素赋给新的数组else/相同的元素只要取一个ListIn
6、sert(LC,k+,ai);i+;j+;while(i5)/ 此时 LB 的元素都比 LA 小 ai=Getelem(LA,i);ListInsert(LC,k+,ai);i+;直接将LA整体插入LCwhile(j5)此时LA的元素都比LB小bj=Getelem(LB,j);ListInsert(LC,k+,bj);j+;/ 直接将 LA 整体插入 LC for(i=0;ik;i+)printf(%3d,LCi);printf(n);intGetelem(inta,intt)returnat;voidListInsert(intb,intp,intq)bp=q;实验 3 输入 n 个整型数据
7、，用链表的方法存储这些数据并输出。#include#include typedefstructLNode intdate; structLNode*next;LNode,*LinkList;/此指针变量就是指LNode类型的结构体voidCreatList(LinkList*L,intn)/顺序输入n个元素的值，建立头结点L inti;LinkListp,S;/S为暂存结点(*L)=(LinkList)malloc(sizeof(LNode);S=(LinkList)malloc(sizeof(LNode);(*L)-next=NULL;S=(*L);for(i=0;idate);p-next
8、=S-next;S-next=p;S=S-next;/S# 向下一个 voidPRINTF(LinkListL)瑜出函数LinkListq;q=L-next;while(q)printf(%4d,q-date);q=q-next; printf(n); main() LinkListM; intn;/n 为插入数的个数 printf( 请输入插入数的个数n);scanf(%d,&n);printf(请输入这d个数n,n);CreatList(&M,n);printf( 该线性表顺序输出为 n);PRINTF(M);实验 4约瑟夫环算法/*约瑟夫环问题是一个数学的应用问题：已知 n个人(以编号1
9、, 2, 3n分别表示)围坐在一 张圆桌周围。从编号为 k 的人开始报数， 数到 m 的那个人出列； 他的下一个人又从1 开始报数， 数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 */#include#include typedefstructNode intdate;structNode*next;LinkList;LinkList*CreatList(intn)/ 创建n 个数的循环链表 inti=1;LinkList*p,*q,*head;p=(LinkList*)malloc(sizeof(LinkList);p-date=i;head=p;for(i=2;i
10、date=i;p-next=q;p=q;p-next=head;returnhead;voidPrint(LinkList*L)/ 输出 n 个数LinkList*p;p=L;printf(%d,p-date);p=p-next;while(p!=L)printf(%d,p-date);p=p-next;printf(n);voidFreeNode(LinkList*L,intk,intm)/ 输出每个第m 的数inti,j;LinkList*p,*q;p=L;for(i=1;inext;while(p-next!=p)for(j=1;jnext;printf(%d,p-date);q-nex
11、t=p-next;p=p-next;printf(%d,p-date);voidmain()LinkList*L;intn,k,m;printf( 请输入人数，从第几个人数，数到几： nkm=n);scanf(%d%d%d,&n,&k,&m);L=CreatList(n);printf(n 个数分别为);Print(L);printf( 每次出列数为);FreeNode(L,k,m);printf(n);实验 5利用栈，判断输入的括号序列是否配对，若配对则将序列输出，否则输出ERROR。#include#include#defineSTACK_INIT_SIZE100typedefstruct
12、SqStackchar*base;在栈构造之前和销毁之后，base的值为NULLchar*top;/ 栈顶指针intstacksize; / 当前已分配的存储空间，以元素为单元SqStack;/ 建立栈voidInitStack(SqStack*S) / 初始化栈(*S).base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE/;/ 初始存储容量intStackEmpty(SqStackS)/ 判断栈是否为空if(S.top=S.base)return1;/栈为空的条件的栈顶 二栈尾elsereturn0;voidPush(SqStack*S,chare)/插入元素e为第一个栈顶新的元素*(*S).to
