数据结构实验.doc

精选实验1（C语言补充实验）有顺序表A和B，其元素值均按从小到大的升序排列，要求将它们合并成一个顺序表C，且C的元素也是从小到大的升序排列。#includemain() int n,m,i=0,j=0,k=0,a5,b5,c10;/*必须设个m做为数组的输入的计数器，不能用i，不然进行到while时i直接为5*/ for(m=0;m=4;m+) scanf(%d,&am);/输入数组a for(m=0;m=4;m+) scanf(%d,&bm);/输入数组b while(i5&j5) if(aibj)ck=bj;k+;j+; elseck=ai;k+;i+;j+; /使输入的两组数组中相同的数只输出一个 if(i5) for(n=i;n5;n+) ck=an;k+; else if(j5) for(n=j;n5;n+) ck=bn;k+; for(i=0;ik;i+) printf(%3d,ci); printf(n);求AB#includemain() int i,j,k=0,a5,b5,c5; /A=a5,B=b5,AB=c5 for(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+;/当有元素重复时，只取一个放入c中 for(i=0;ik;i+) printf(%3d,ci); printf(n);实验2（C语言补充实验）已知一个有序整型数组，编程将一个整型数m插入到该数组中，使得插入后的数组任然有序。#include#define N 4main() int i,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(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中的数据元素仍按值非递减有序排列。#includeint Getelem(int a, int t);/声明得到数组元素函数void ListInsert(int b, int p,int q );/声明插入数组函数main()int m,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/相同的元素只要取一个ListInsert(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整体插入LCfor(i=0;ik;i+)printf(%3d,LCi);printf(n);int Getelem(int a,int t) return at;void ListInsert(int b,int p,int q) bp=q;实验3输入n个整型数据，用链表的方法存储这些数据并输出。#include#includetypedef struct LNode int date; struct LNode *next;LNode ,*LinkList;/此指针变量就是指LNode类型的结构体void CreatList(LinkList *L,int n)/顺序输入n个元素的值，建立头结点L int i; LinkList p,S;/S为暂存结点 (*L)=(LinkList)malloc(sizeof(LNode); S=(LinkList)malloc(sizeof(LNode); (*L)-next=NULL; S=(*L); for(i=0;idate);p-next=S-next;S-next=p;S=S-next;/S移向下一个 void PRINTF(LinkList L)/输出函数 LinkList q; q=L-next; while(q)printf(%4d,q-date);q=q-next; printf(n); main() LinkList M; int n;/n为插入数的个数 printf(请输入插入数的个数n); scanf(%d,&n); printf(请输入这%d个数n,n); CreatList( &M,n); printf(该线性表顺序输出为n); PRINTF(M);实验4约瑟夫环算法/*约瑟夫环问题是一个数学的应用问题：已知n个人（以编号1，2，3n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。*/#include#includetypedef struct Node int date; struct Node *next;LinkList;LinkList *CreatList(int n)/创建n个数的循环链表 int i=1;LinkList *p,*q,*head; p=(LinkList*)malloc(sizeof(LinkList); p-date=i; head=p; for(i=2;idate= i; p-next=q; p=q; p-next=head; return head;void Print(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);void FreeNode(LinkList *L,int k,int m) /输出每个第m的数 int i,j; LinkList *p,*q; p=L; for(i=1;inext; while(p-next!=p) for(j=1;jnext; printf(%d ,p-date); q-next=p-next; p=p-next; printf(%d ,p-date);void main() LinkList *L; int n,k,m;printf(请输入人数，从第几个人数，数到几：n k m=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 #define STACK_INIT_SIZE 100typedef struct SqStack char *base;/在栈构造之前和销毁之后，base的值为NULL char *top;/栈顶指针 int stacksize;/当前已分配的存储空间，以元素为单元SqStack;/建立栈void InitStack(SqStack *S)/初始化栈 (*S).base=(char*)malloc(STACK_INIT_SIZE*sizeof(char); (*S).top=(*S).base; (*S).stacksize = STACK_INIT_SIZE;/初始存储容量int StackEmpty(SqStack S) /判断栈是否为空 if(S.top=S.base) return 1;/栈为空的条件的栈顶=栈尾 else return 0;void Push(SqStack *S,char e) /插入元素e为第一个栈顶新的元素 *(*S).top)=e; (*S).top+;void Pop(SqStack *S,char *e) /删除S1的栈顶元素,并输出e (*S).top-; *e=*(*S).top);main() int i; char a,e; /a为输入元素 SqStack p; InitStack(&p); /初始化栈p printf(请输入需要判断的括号n); a=getchar(); /输入a while(a!=n) /printf(+%cn,a); if(a=(|a=|a=)Push(&p,a); else if(a=)|a=|a=) Pop(&p,&e);i=0; /printf(*%cn,e); switch(e)case (: if(a=) i=1; break; case : if(a=) i=1; break;case : if(a=) i=1; break;/*default不能用来判断字符*/ /printf($%dn,i); if(i=0)break; a=getchar(); if(!StackEmpty(p) printf(括号不匹配n); /栈不为空 else if(StackEmpty(p) printf(括号匹配n); /栈为空 实验6利用循环队列模拟舞伴配对问题：在舞会上，男女各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对的者等待下一轮舞曲，舞曲结束后，按照先配对的先分开进入各自的队列。假设初始男女人数及舞会的轮数由参数给出，模拟上述舞伴配对问题。输出第n个舞曲男女配对的序列。#include#include#include#define SIZE 100/最大队列长度typedef struct NameQueuechar BoyName10;char GirlName10;NameQueue;/定义名字结构体typedef struct SqQueueNameQueue *base;/初始化动态分配空间int front;int rear;SqQueue; /定义循环队列void InitQueue(SqQueue *Q)/构造一个空队列Q-base=(NameQueue *)malloc(SIZE*sizeof(NameQueue);Q-front=Q-rear=0;int QueueEmpty(SqQueue Q)/判断队列是否为空if (Q.rear=Q.front) return 1;else return 0;void EnQueue(SqQueue *Q,NameQueue e)/插入元素e为Q的新的队尾元素if (Q-rear+1)%SIZE=Q-front)/队满exit(0);elseQ-baseQ-rear=e;Q-rear=(Q-rear+1)%SIZE;/入队void DeQueue(SqQueue *Q,NameQueue *e)/ 删除Q的队头元素, 并用e返回其值if (Q-rear=Q-front)/队满exit(0);else(*e)=Q-baseQ-front;Q-front=(Q-front+1)%SIZE;/出队 void main() int i,time,BoyNum,GirlNum;/time为舞会曲数,BoyNum为男生人数，Girl为女生人数 char name10;/name字符串数组储存姓名 SqQueue Boy,Girl,Dancer;/定义Boy,Girl,Dancer三个队列 NameQueue e1,e2; printf(请输入舞会曲数,男生人数,女生人数n); scanf(%d %d %d,&time,&BoyNum,&GirlNum); InitQueue(&Boy); InitQueue(&Girl); InitQueue(&Dancer); getchar(); printf(输入男生姓名n); for(i=1;i=BoyNum;i+) gets(e1.BoyName);/输入男生姓名strcpy(e1.GirlName, );EnQueue(&Boy,e1); printf(输入女生姓名n); for(i=1;i=GirlNum;i+) gets(e1.GirlName);/输入女生姓名strcpy(e1.BoyName, );EnQueue(&Girl,e1); printf(*舞会配对顺序*n); for(i=1;i=time;i+) printf(第%d配对结果为n,i);while(!QueueEmpty(Boy)&!QueueEmpty(Girl) DeQueue(&Boy,&e1); strcpy(name,e1.BoyName);/用name字符串存储男生姓名 DeQueue(&Girl,&e1); strcpy(e1.BoyName,name); /此时e1里存有男生和女生姓名 EnQueue(&Dancer,e1); printf( %s-%s ,e1.BoyName,e1.GirlName); while(!QueueEmpty(Dancer) /当舞会配对完成输出舞会队列里的男女姓名 DeQueue(&Dancer,&e1); strcpy(e2.BoyName,e1.BoyName); strcpy(e2.GirlName, ); EnQueue(&Boy,e2); strcpy(e1.BoyName, ); EnQueue(&Girl,e1);printf(n); 实验7已知一个MN的稀疏矩阵A，用三元组的方法压缩存储该矩阵，输出该三元组及矩阵转置后的三元组。（用跳着找，顺着存方法）#include#define M 10 /数组A的行数#define N 10 /数组A的列数#define SIZE 100 /假设非零元个数的最大值为100typedef struct int i,j; /该非零元的行下标和列下标 int e; /该非零元素的值Three; /(三元组)typedef struct Three dataSIZE+1; /非零元三元组,data0不用 int mu,nu,tu; /矩阵的行数，列数和非零元个数TSMatrix;/（矩阵）void zhuanzhi(TSMatrix A,TSMatrix *T) /采用三元组表存储表示，求稀疏矩阵A的转置矩阵T int p,q,col; / p为现在三元组下标，q为原三元组下标,col列数 T-mu=A.nu;/ 矩阵T的行数等于矩阵A的列数 T-nu=A.mu;/ 矩阵T的列数等于矩阵A的行数 T-tu=A.tu;/ 矩阵T的非零元素数等于矩阵A的非零元素数 if(A.tu)/ 把A中每一个非零元素转换到T中相应位置 q=0; for(col=0;col=A.nu;col+)/ 按列号作扫描，做col趟 for(p=0;pdataq.i= col;/ 新三元组的行号 T-dataq.j= A.datap.i;/ 新三元组的列号 T-dataq.e= A.datap.e;/ 新三元组的值 q+; void Create(TSMatrix *A) / 创建一个稀疏矩阵A int aMN,i,j, k=0; / k为三元组的下标 int m,n;/ m、n为A矩阵的行、列数 printf(请输入矩阵的行、列数:n); scanf(%d %d,&m,&n); printf(请输入数组a:n); for(i=0;im;i+) for(j=0;jn;j+) scanf(%d,&aij); for(i=0;im;i+) for(j=0;jdatak.i=i+1; / 该元素的行位置赋给三元组的i A-datak.j=j+1; / 该元素的列位置赋给三元组的jA-datak.e=aij; / 该元素的值赋给三元组的ek+; / 三元组下标加一 A-mu=m;A-nu=n;A-tu=k; / 给稀疏矩阵的行数，列数和非零元个数赋值void PRINT(TSMatrix A) int i; /k为计数器 for(i=0;iA.tu;i+) printf(%4d%4d%4dn,A.datai.i,A.datai.j,A.datai.e); / 依次输出三元组 printf(n);main() TSMatrix A,T; Create(&A); / 创建一个稀疏矩阵A printf(A的三元组表(下标从1开始):n); printf( i j en); PRINT(A); zhuanzhi(A,&T); / 采用三元组表存储表示，求稀疏矩阵A的转置矩阵T printf(转置后的三元组表(下标从1开始):n); printf( i j en); PRINT(T);实验8已知一个MN的稀疏矩阵A，用三元组的方法压缩存储该矩阵，输出该三元组及矩阵转置后的三元组。（用顺着找，跳着存方法）#include#define M 10 /数组A的行数#define N 10 /数组A的列数#define SIZE 100 /假设非零元个数的最大值为100typedef struct int i,j; /该非零元的行下标和列下标 int e; /该非零元素的值Triple; /(三元组)typedef struct Triple dataSIZE+1; /非零元三元组,data0不用 int mu,nu,tu; /矩阵的行数，列数和非零元个数TSMatrix;/（矩阵）void FastTransposeSMatrix(TSMatrix A,TSMatrix *T) /采用三元组表存储表示，求稀疏矩阵A的转置矩阵T int t,p,q,col,numN,cpotN; T-mu=A.nu; T-nu=A.mu; T-tu=A.tu; if(T-tu) for(col=0;colA.nu;col+)numcol=0; for(t=0;tA.tu;t+)numA.datat.j+; /求A中每一列含非零元个数cpot0=0; /求第col列中第一个非零元在新的三元组里面的序号 for(col=1;colA.nu;col+)cpotcol=cpotcol-1+numcol-1; /*numcol表示矩阵A中非零元的个数 cpotcol表示A中第col列的第一个非零元在新的三元组中的位置*/for(p=0;pdataq.i=col; T-dataq.j=A.datap.i; T-dataq.e=A.datap.e; cpotcol+; void Create(TSMatrix *A)/ 创建一个稀疏矩阵A int aMN,i,j, k=0; / k为三元组的下标 int m,n; / m、n为M矩阵的行、列数 printf(请输入矩阵的行、列数:n); scanf(%d %d,&m,&n); printf(请输入行，列的数组a:n); for(i=0;im;i+) for(j=0;jn;j+) scanf(%d,&aij); for(i=0;im;i+) for(j=0;jdatak.i=i; / 该元素的行下标赋给三元组的i A-datak.j=j; / 该元素的列下标赋给三元组的jA-datak.e=aij; / 该元素的值赋给三元组的ek+; / 三元组下标加一 A-mu=m;A-nu=n;A-tu=k; / 给稀疏矩阵的行数，列数和非零元个数赋值void PRINT(TSMatrix A) int k; for(k=0;kA.tu;k+) printf(%4d%4d%4dn,A.datak.i,A.datak.j,A.datak.e); / 依次输出三元组 printf(n);main() TSMatrix A,T; Create(&A); / 创建一个稀疏矩阵A printf(A的三元组表:n); printf( i j en); PRINT(A); FastTransposeSMatrix(A,&T); / 采用三元组表存储表示，求稀疏矩阵A的转置矩阵T printf(转置后的三元组表:n); printf( i j en); PRINT(T);实验9已知有10个字符型数据，试将这十个字符按照从上到下、从左到右的次序建立一个二叉链表，并依次输出这10个字符。（提示：链表存储二叉树通常用具有两个指针域的链表作为二叉树的存储结构，其中每个结点由数据域Data、左指针域和右指针域组成。两个指针域分别指向该结点的左、右孩子。若某结点没有左孩子或右孩子，则对应的指针域为空。最后，还需要一个链表的头指针指向根结点。）先序、后序遍历并输出（用递归方法）。#include#includetypedef struct BiTNode char data; struct BiTNode *lchild, *rchild; /左右孩子指针BiTNode,*BiTree;BiTree CreateBiTree(BiTree T) char a; /scanf(%c,&a); a=getchar(); if(a=0) T=NULL; else T=(BiTree)malloc(sizeof(BiTNode); T-data=a; /生成跟结点 T-lchild=CreateBiTree(T-lchild); /构造左子树 T-rchild=CreateBiTree(T-rchild); /构造右子树 return T; void PreOrder(BiTree T) /先序遍历 if(T) printf(%c ,T-data); PreOrder(T-lchild); PreOrder(T-rchild); void InOrder(BiTree T) /中序遍历 if(T) InOrder(T-lchild); printf(%c ,T-data); InOrder(T-rchild); void PostOrder(BiTree T) /后序遍历 if(T) PostOrder(T-lchild);PostOrder(T-rchild);printf(%c ,T-data); void main() BiTree L; printf(请输入二叉树序列n); L=(BiTree)malloc(sizeof(BiTNode); L=CreateBiTree(L); printf(n递归方法n); printf(先序遍历二叉树序列为n); PreOrder(L); printf(n); printf(中序遍历二叉树序列为n); InOrder(L); printf(n); printf(后序遍历二叉树序列为n); PostOrder(L); printf(n);实验11将一个已知二叉树，中序遍历并输出（用非递归方法）。#include#includetypedef struct BiTNode char data; int flag; /标志变量 struct BiTNode *lchild, *rchild; /左右孩子指针BiTNode,*BiTree;#define SIZE 100typedef struct SqStack BiTree *base;/在栈构造之前和销毁之后，base的值为NULL BiTree *top;/栈顶指针 int stacksize;/当前已分配的存储空间，以元素为单元SqStack;/建立栈void InitStack(SqStack *S) /初始化栈 S-base=(BiTree *)malloc(SIZE *sizeof(BiTNode); S-top=S-base; S-stacksize = SIZE; /初始存储容量int StackEmpty(SqStack S) /判断栈是否为空 if(S.top=S.base) return 1; /栈为空的条件的栈顶=栈尾 else return 0;void Push(SqStack *S,BiTree e) /插入元素e为第一个栈顶新的元素 *(*S).top)=e; (*S).top+;void Pop(SqStack *S,BiTree *e) /删除S1的栈顶元素,并输出e (*S).top-; *e=*(*S).top);BiTree CreateBiTree(BiTree T) char a; /scanf(%c,&a); a=getchar(); if(a=0) T=NULL; else T=(BiTree)malloc(sizeof(BiTNode);T-data=a; /生成跟结点T-lchild=CreateBiTree(T-lchild); /构造左子树T-rchild=CreateBiTree(T-rchild); /构造右子树 return T; void PreOrder(BiTree T) /先序非递归 BiTree p;SqStack S;InitStack(&S);p=(BiTree)malloc(sizeof(BiTNode); p=T;while(p|!StackEmpty(S) if(p) printf(%c ,p-data); Push(&S,p); /预留p指针在栈中 p=p-lchild; else Pop(&S,&p); p=p-rchild; /左子树为空, 进右子树 void InOrder(BiTree T) /中序非递归 BiTree p;SqStack S;InitStack(&S);p=(BiTree)malloc(sizeof(BiTNode); p=T;while(p|!StackEmpty(S) if(p) Push(&S,p); /预留p指针在栈中 p=p-lchild; else Pop(&S,&p); printf(%c ,p-data); p=p-rchild; / 左子树为空, 进右子树 void PostOrder(BiTree T) /后序非递归 BiTree p; SqStack S; InitStack(&S); p=(BiTree)malloc(sizeof(BiTNode); p=T; while(p|!StackEmpty(S) if(p) p-flag=0; Push(&S,p); /将P指针以及flag压入栈 p=p-lchild; else Pop(&S,&p); if(p-flag=0) p-flag=1; Push(&S,p); /再将P指针以及flag压入栈 p=p-rchild; else printf(%c ,p-data);p=NULL;/把p赋为空是表示当前结点处理完毕需要从栈中弹出下个结点 void main() BiTree L; printf(请输入二叉树序列