实验报告-2.doc

第一次作业第一题

#include<stdio.h>
#define N 10

int main()
{
int a[N],i,t;
printf("请输入线性表\n:");
for(i=0;i<N;i++)
scanf("%d",&a[i]);
printf("逆转前的线性表为：\n");
for(i=0;i<N;i++)
printf("%d\t",a[i]);
for(i=0;i<N/2;i++)
{
t=a[i];
a[i]=a[N-i-1];
a[N-i-1]=t;
}
printf("逆转后的线性表为：\n");
for(i=0;i<N;i++)
printf("%d\t",a[i]);
printf("\n");
return 0;
}

第一次作业第二题

#include<stdio.h>
#include<malloc.h>

typedef struct node
{
int data;
struct node *next;
}node,*linklist;

linklist crelist();
void sqinsert(linklist head,int j,int i);
void sqdelete(linklist head,int i);
void sqprint(linklist head);
int sqlength(linklist head);

int main()
{
linklist head;
int x,t,j,i,z;
j=-1,t=1;
printf("建立单链表：\n");
head=crelist();
printf("建立的单链表为：");
sqprint(head);
printf("请选择操作：\n1、插入\n2、删除\n3、求长度\n0、退出\n");
while(t)
{
printf("请选择操作\n");
scanf("%d",&j);
switch(j)
{
case 1:
{
printf("请选择插入位置：\n");
scanf("%d",&i);
printf("请输入插入的数据\n");
scanf("%d",&x);
sqinsert(head,x,i);
break;
}
case 2:
{
printf("请输入删除元素位置\n");
scanf("%d",&i);
sqdelete(head,i);
sqprint(head);
break;
}
case 3:
{
z=sqlength(head);
printf("此链表的长度为%d\n",z);
break;
}
case 0:t=0;break;
}
}
return 0;
}

linklist crelist()
{
linklist head,r,s;
int x,flag=1;
head=(linklist )malloc(sizeof(node));
head->next=NULL;
r=head;
printf("请输入数据建立链表，以-1结束\n");
while(flag)
{
scanf("%d",&x);
if(x!=-1)
{
s=(linklist )malloc(sizeof(node));
s->data=x;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL;
}
}
return head;
}

void sqinsert(linklist head,int x,int i)
{
linklist p,s;
int k;
p=head;
k=0;
while(p!=NULL&&k<i-1)
{
p=p->next;
k++;
}
if(p==NULL||k>i-1)
printf("插入位置不合理\n");
s=(linklist )malloc(sizeof(node));
s->data=x;
s->next=p->next;
p->next=s;
sqprint(head);
}

void sqdelete(linklist head,int i)
{
linklist p,q;
int j,e;
p=head;
j=0;
while(p->next!=NULL&&j<i-1)
{
p=p->next;
j++;
}
if(p->next==NULL||j>i-1)
printf("删除位置不合理\n");
q=p->next;
p->next=q->next;
e=q->data;
free(q);
}

void sqprint(linklist head)
{
linklist p;
p=head->next;
while(p)
{
printf("%d\t",p->data);
p=p->next;
}
printf("\n");
}

int sqlength(linklist head)
{
linklist p,b;
int n=0;
b=head->next;
p=b;
while(p!=NULL)
{
n++;
p=p->next;
}
return n;
}

第二次作业第一题

#include<stdio.h>
#include<malloc.h>
#define maxsize 20

typedef struct
{
int *base;
int *top;
int stacksize;
}sqstack;

int initstack(sqstack &S);
int enstack(sqstack &S);
int delstack(sqstack &S);
void tip();

int main()
{
int j,a,b,k=0,i=0,c,d;
int x[50],y[50];
sqstack S;
initstack(S);
tip();
scanf("%d",&j);
while(j)
{
switch(j)
{
case 1:
{
a=enstack(S);
if(!a)
printf("栈已满且分配存储空间失败\n");
printf("进栈数为%d\n",a);
x[k++]=a;
printf("操作完成\n");
tip();
scanf("%d",&j);
break;
}
case 2:
{
b=delstack(S);
if(!b)
printf("栈为空\n");
printf("出栈数为%d\n",b);
y[i++]=b;
printf("操作完成\n");
tip();
scanf("%d",&j);
break;
}
case 0:j=0;break;
default :
{
printf("输入有误，请重新输入\n");
tip();
scanf("%d",&j);
break;
}
}
}
printf("进栈数的顺序为：\n");
for(c=0;c<k;c++)
printf("%d",x[c]);
printf("出栈数的顺序为：\n");
for(d=0;d<i;d++)
printf("%d",y[d]);
return 0;
}

int initstack(sqstack &S)
{
S.base=(int *)malloc(maxsize*sizeof(int));
if(S.base==NULL)
return 0;
S.top=S.base;
S.stacksize=maxsize;
return 1;
}

int enstack(sqstack &S)
{
int e,length=10;
if(S.top-S.base==S.stacksize*sizeof(int))
{
S.base=(int *)realloc(S.base,(S.stacksize+length)*sizeof(int));
if(S.base==NULL)
return 0;
S.stacksize=S.stacksize+length;
S.top=S.base+S.stacksize*sizeof(int);
}
printf("请输入入栈数字：\n");
scanf("%d",&e);
*S.top++=e;
return e;
}

int delstack(sqstack &S)
{
int e;
if(S.top==S.base)
return 0;
e=*--S.top;
return e;
}

void tip()
{
printf("请输入操作：1、进栈\n2、出栈\n0、退出\n");
}

第二次作业第二题

#include<stdio.h>
#include<malloc.h>
#define maxsize 20

typedef struct
{
int *base;
int front;
int rear;
}sqqueue;

int initqueue(sqqueue &Q);
int enqueue(sqqueue &Q);
int delqueue(sqqueue &Q);
void tip();

int main()
{
int j,a,b,k=0,i=0,c,d;
int x[50],y[50];
sqqueue Q;
initqueue(Q);
tip();
scanf("%d",&j);
while(j)
{
switch(j)
{
case 1:
{
a=enqueue(Q);
if(!a)
printf("队列已满\n");
printf("进队数为%d\n",a);
x[k++]=a;
printf("操作完成\n");
tip();
scanf("%d",&j);
break;
}
case 2:
{
b=delqueue(Q);
if(!b)
printf("队列为空\n");
printf("出队数为%d\n",b);
y[i++]=b;
printf("操作完成\n");
tip();
scanf("%d",&j);
break;
}
case 0:j=0;break;
default :
{
printf("输入有误，请重新输入\n");
tip();
scanf("%d",&j);
break;
}
}
}
printf("进队数的顺序为：\n");
for(c=0;c<k;c++)
printf("%d",x[c]);
printf("出队数的顺序为：\n");
for(d=0;d<i;d++)
printf("%d",y[d]);
return 0;
}

int initqueue(sqqueue &Q)
{
Q.base=(int *)malloc(maxsize*sizeof(int));
if(!Q.base)
return 0;
Q.front=Q.rear=0;
return 1;
}
int initqueue(sqqueue &Q)
{
Q.base=(int *)malloc(maxsize*sizeof(int));
if(!Q.base)
return 0;
Q.front=Q.rear=0;
return 1;
}

int enqueue(sqqueue &Q)
{
int e;
if((Q.rear+1)%maxsize==Q.front)
return 0;
printf("请输入入队数字：\n");
scanf("%d",&e);
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%maxsize;
return e;
}

int delqueue(sqqueue &Q)
{
int e;
if(Q.front==Q.rear)
return 0;
e=Q.base[Q.front];
Q.front=(Q.front+1)%maxsize;
return e;
}

void tip()
{
printf("请输入操作：\n1、进队\n2、出队\n0、退出\n");
}

第三次作业

#include<stdio.h>
#include<string.h>
#include<malloc.h>

typedef struct
{
char ch[100];
int length;
}seqstrin;

seqstrin Substr(seqstrin s,int i,int j);
seqstrin Instr(seqstrin s,int i,char s1[]);
seqstrin Delstr(seqstrin s,int i,int j);
int strIndex(seqstrin s,char t[]);
void tip();

int main()
{
int j,p;
seqstrin s,str1,str2,str3;
char s1[]="xyz";
char t[]="hijk";
strcpy(s.ch,"abcdefghijklmn");
s.length=strlen(s.ch);
tip();
scanf("%d",&j);
while(j)
{
switch(j)
{
case 1:
{
str1=Substr(s,2,10);
if(!(strcmp(str1.ch,s.ch)))
printf("位置不合理\n");
puts(str1.ch);
tip();
scanf("%d",&j);
break;
}
case 2:
{
str2=Instr(s,9,s1);
if(!(strcmp(str2.ch,s.ch)))
printf("位置不合理\n");
puts(str2.ch);
tip();
scanf("%d",&j);
break;
}
case 3:
{
str3=Delstr(s,2,5);
if(!(strcmp(str3.ch,s.ch)))
printf("位置不合理\n");
puts(str3.ch);
tip();
scanf("%d",&j);
break;
}
case 4:
{
p=strIndex(s,t);
if(p==0)
printf("长度太长或在s中找不到字符串t\n");
printf("t在s中出现的位置为第%d个字符处\n",p);
tip();
scanf("%d",&j);
break;
}
case 0:j=0;break;
default :
{
printf("输入错误，请重新输入\n");
tip();
scanf("%d",&j);
break;
}
}
}
return 0;
}

seqstrin Substr(seqstrin s,int i,int j)
{
seqstrin str;
int k,h=0;
str.length=0;
if(i<0||i>s.length||j<0||i+j-1>s.length)
return s;
for(k=i-1;k<i+j-1;k++)
str.ch[h++]=s.ch[k];
str.ch[h]='\0';
str.length=j;
return str;
}

seqstrin Instr(seqstrin s,int i,char s1[])
{
seqstrin str,*p;
int k,l,j,c,t;
p=&s;
l=strlen(s1);
if(i<0||i>s.length+1)
return s;
if(l)
{
if(l+s.length>=100)
if((p=(seqstrin *)realloc(p,(s.length+l)*sizeof(char)))==NULL)
return s;
for(k=s.length-1;k>=i-1;k--)
str.ch[k+l]=s.ch[k];
for(j=i-1,c=0;j<=i+l-1,c<=l-1;j++,c++)
str.ch[j]=s1[c];
for(t=0;t<i-1;t++)
str.ch[t]=s.ch[t];
str.length+=l;
}
str.ch[s.length+l]='\0';
return str;
}

seqstrin Delstr(seqstrin s,int i,int j)
{
seqstrin str;
int k;
if(i<0||i>s.length||i+j>s.length)
return s;
for(k=0;k<=i-1;k++)
str.ch[k]=s.ch[k];
for(k=i+j-1;k<s.length;k++)
str.ch[k-j]=s.ch[k];
str.length=s.length-j+1;
str.ch[s.length-j]='\0';
return str;
}

int strIndex(seqstrin s,char t[])
{
seqstrin str;
int j,k,n,m,y;
n=s.length;
m=strlen(t);
str.length=m;
if(m<=n)
{
for(j=0;j<=n-m+1;j++)
{
for(k=0;k<m;k++)
{
str.ch[k]=s.ch[j+k];
str.ch[k+1]='\0';
}
if(strcmp(str.ch,t)!=0)
continue;
else
return (j+1);
}
}
return 0;
}

void tip()
{
printf("请输入操作：\n1、求子串\n2、插入串\n3、串删除\n4、子串定位\n0、退出\n");
}

第四次作业

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100

typedef struct
{
int i,j;
int e;
}Triple;

typedef struct
{
Triple data[MAXSIZE+1];
int mu,nu,tu;
}TSMatrix;

TSMatrix InitArray(TSMatrix T);
TSMatrix Transpose(TSMatrix M,TSMatrix T1);

int main()
{
int i,j;
TSMatrix M,T,T1,T2;
T1=M=InitArray(T);
printf("你输入的矩阵为：\n");
for(i=1;i<=M.tu;i++)
printf("%d\n%d\n%d\n",M.data[i].i,M.data[i].j,M.data[i].e);
T2=Transpose(M,T1);
printf("转置后的矩阵为：\n");
for(j=1;j<=M.tu;j++)
printf("%d\n%d\n%d\n",M.data[j].i,M.data[j].j,M.data[j].e);
return 0;
}

TSMatrix InitArray(TSMatrix T)
{

int i;
&T=(TSMatrix *)malloc(sizeof(TSMatrix));
printf("请输入此矩阵的行数、列数及非零元素个数:\n");
scanf("%d%d%d",T.mu,T.nu,T.tu);
printf("请输入相关数据完成此矩阵:\n");
for(i=0;i<T.tu;i++)
{
printf("请输入此矩阵非零元素的行下标和列下标\n");
scanf("%d%d",T.data[i].i,T.data[i].j);
printf("请输入此矩阵非零元素的值\n");
scanf("%d",T.data[i].e);
&T=(TSMatrix *)malloc(sizeof(TSMatrix));
}
return T;
}

TSMatrix Transpose(TSMatrix M,TSMatrix T1)
{
int col,t,p,q;
int num[100],cpot[100];
T1.mu=M.mu,T1.nu=M.nu,T1.tu=M.tu;
if(T1.tu)
{
for(col=1;col<=M.tu;++col)
num[col]=0;
for(t=1;t<=M.tu;++t)
++num[M.data[t].j];
cpot[1]=1;
for(col=2;col<=M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=M.tu;++p)
{
col=M.data[p].j;
q=cpot[col];
T1.data[q].i=M.data[p].j;
T1.data[q].j=M.data[p].i;
T1.data[q].e=M.data[p].e;
++cpot[col];
}
}
return T1;
}

第五次作业

#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct node
{
char data;
struct node *lChild;
struct node *rChild;
}BTnode,*BTtree;

BTtree Creat_BT(BTtree T);
void preorder(BTtree T1);
void Inorder(BTtree T1);
void Postorder(BTtree T1);
int Leaf_Sum(BTtree T1);
void tip();

int main()
{
BTtree T,T1;
BTnode b;
int t,j,z;
t=1;
T=&b;
printf("建立二叉树：\n");
T1=Creat_BT(T);
{
while(t)
scanf("%d",&j);
switch(j)
{
case 1:
{
preorder(T1);
tip();
break;
}
case 2:
{
Inorder(T1);
tip();
break;
}
case 3:
{
Postorder(T1);
tip();
break;
}
case 4:
{
z=Leaf_Sum(T1);
printf("此二叉树的长度为:%d\n",z);
tip();
break;
}
case 0:t=0;break;
default :
{printf("你输入的数据有误，请重新输入:\n");
tip();
break;
}
}
}
return 0;
}

BTtree Creat_BT(BTtree T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
if(!(T=(BTnode *)malloc(sizeof(BTnode))))
printf("error:\n");
T->data=ch;
T->lChild=Creat_BT(T->lChild);
T->rChild=Creat_BT(T->rChild);
}
return T;
}

void Preorder(BTtree T1)
{
if(T1)
{
printf("%c\n",T1->data);
Preorder(T1->lChild);
Preorder(T1->rChild);
}
}

void Inorder(BTtree T1)
{
if(T1)
{
Inorder(T1->lChild);
printf("%c\n",T1->data);
Inorder(T1->rChild);
}
}

void Postorder(BTtree T1)
{
if(T1)
{
Postorder(T1->lChild);
Postorder(T1->rChild);
printf("%c\n",T1->data);
}
}

int Leaf_Sum(BTtree T1)
{
if(!T1)
return 0;
else if(T1->lChild==NULL&&T1->rChild==NULL)
return 1;
else
return Leaf_Sum(T1->lChild)+Leaf_Sum(T1->rChild);
}

void tip()
{
printf("1、先序遍历\n2、中序遍历\n3、后序遍历\n4、叶子节点个数\n0、退出\n请输入操作：");
}

第六次作业

#include<stdio.h>
#include<malloc.h>
#define INFINITY 32767
#define MAX_VEX 20
#define QUEUE_SIZE (MAX_VEX+1)

bool *visited;

typedef struct
{
char *base;
int front;
int rear;
}Queue;

typedef struct
{
char *vexs;
int arcs[MAX_VEX][MAX_VEX];
int vexnum,arcnum;
}Graph;

void CreateUDN(Graph &G);
void DFS(Graph G,int k);
void BFS(Graph G);
int Locate(Graph G,char c);
int FirstVex(Graph G,int k);
int NextVex(Graph G,int i,int j);
void InitQueue(Queue Q);
void EnQueue(Queue Q,int e);
void DeQueue(Queue Q,int &e);
void tip();

int main()
{
int j;
Graph G;
CreateUDN(G);
tip();
scanf("%d",&j);
while(j)
{
switch(j)
{
case 1:
{
printf("\n深度优先遍历: ");
BFS(G);
printf("操作完成\n");
tip();
scanf("%d",&j);
break;
}
case 2:
{
printf("\n广度优先遍历: ");
DFS(G,-1);
printf("操作完成\n");
tip();
scanf("%d",&j);
break;
}
case 0:j=0;break;
default :
{
printf("输入有误，请重新输入\n");
tip();
scanf("%d",&j);
break;
}
}
}
printf("\n程序结束.\n");
return 0;
}

void CreateUDN(Graph &G)
{
int i,j,w,s1,s2;
char a,b,temp;
printf("输入顶点数和弧数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar();
G.vexs=(char *)malloc(G.vexnum*sizeof(char));
printf("输入%d个顶点.\n",G.vexnum);
for(i=0;i<G.vexnum;i++)
{
printf("输入顶点%d:",i);
scanf("%c",&G.vexs[i]);
temp=getchar();
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条弧.\n",G.arcnum);
for(j=0;j<G.arcnum;j++)
{
printf("输入弧%d:",j);
scanf("%c %c %d",&a,&b,&w);
temp=getchar();
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}

void DFS(Graph G,int k)
{
int i;
if(k==-1)
{
for(i=0;i<G.vexnum;i++)
if(!G.vexs[i])
DFS(G,i);
}
else
{
visited[k]=true;
printf("%c ",G.vexs[k]);
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!G.vexs[i])
DFS(G,i);
}
}

void BFS(Graph G)
{
int k;
Queue Q;
InitQueue(Q);
for(int i=0;i<G.vexnum;i++)
if(!visited[i])
{
visited[i]=true;
printf("%c ",G.vexs[i]);
EnQueue(Q,i);
while(Q.front!=Q.rear)
{
DeQueue(Q,k);
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w])
{
visited[w]=true;
printf("%c ",G.vexs[w]);
EnQueue(Q,w);
}
}
}
}

int Locate(Graph G,char c)
{
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c)
return i;
return -1;
}

int FirstVex(Graph G,int k)
{
if(k>=0&&k<G.vexnum)