实验一 链表的操作
一、实验目的与要求：
1、掌握线性表中元素的前驱、后续的概念。
2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。
3、对线性表相应算法的时间复杂度进行分析。
4、理解顺序表、链表数据结构的特点（优缺点）。
二、实验内容：
建立一个带头结点的单链表，然后对该单链表进行插入删除结点操作，输出各种操作的结果
微机+windows操作系统+VC++6.0
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{char data;
struct node *next;
}LINKLIST;
/*以下程序段的功能为尾插入法建立单链表*/
void creat(LINKLIST *head)
{
LINKLIST *t,*p;
char ch;
p=head;
printf("请从键盘上输入一串字符，以字符$作为输入的结束符号：");
while((ch=getchar())!='$')
{
t=(LINKLIST *)malloc(sizeof(LINKLIST));
t->data=ch;
t->next=p->next;
p->next=t;
p=p->next;
}
}
/*以下程序段的功能为输出单链表的各结点的值*/
void print(LINKLIST *head)
{
LINKLIST *p;
p=head->next;
printf("head");
while(p!=NULL)
{printf("-->%c",p->data);
p=p->next;
}
printf("\n");
}
/*以下程序段的功能为在单链表中插入一个元素*/
void insert(LINKLIST *head,int x)
{
LINKLIST *p,*t;
char ch;
int i=0;
printf("请输入要输入的结点的值：");
scanf("%c",&ch);
p=head;
while(p->next!=NULL&&i<x)
{i++;
p=p->next;
}
t=(LINKLIST *)malloc(sizeof(LINKLIST));
t->data=ch;
t->next=p->next;
p->next=t;
}
/*以下程序段的功能为在单链表中删除一个元素*/
void deletenode(LINKLIST *head,int i)
{
LINKLIST *p,*s;
p=head;
int j=0;
while(p->next!=NULL&&j<i-1)
{j++;
p=p->next;
}
s=p->next;
p->next=s->next;
free(s);
}
/*主函数*/
void main()
{
LINKLIST *head;
int i;
head=(LINKLIST *)malloc(sizeof(LINKLIST));
head->next=NULL;
creat(head);
printf("建立的单链表为：");
print(head);
printf("请输入要插入结点的位置(0-n)：");
scanf("%d",&i);
getchar();
insert(head,i-1);
printf("插入元素后的单链表为：");
print(head);
printf("请输入要删除的结点 (0-n)：");
scanf("%d",&i);
deletenode(head,i);
print(head);
}
通过程序可以看出链表对各种不同操作所花的时间：
插入操作的时间：o(1)
删除操作的时间：o(1)
定位操作的时间：o(n)
实验二 栈的运算
一、实验目的与要求：
1、掌握栈的结构特性及其入栈，出栈操作；
二、实验内容：
括号配对，从键盘输入三种不同类型的括号，通过对栈的调用，对三种不同括号进行正确配对
微机+windows操作系统+VC++6.0
/*括号配对算法*/
#include "stdio.h"
#define MAXSIZE 100
typedef struct
{
char data[MAXSIZE];
int top;
}SEQSTACK;
/*初始化栈*/
void intistack(SEQSTACK *s)
{
s->top=0;
}
/*判断栈空*/
int empty(SEQSTACK *s)
{
if(s->top==0)
return 1;
else
return 0;
}
/*进栈*/
int push(SEQSTACK *s,char x)
{
if(s->top==MAXSIZE-1)
{
printf("overflow\n");
return 0;}
else{
s->top++;
(s->data)[s->top]=x;
return 1;}
}
/*出栈*/
char pop(SEQSTACK *s)
{
char x;
if(empty(s))
{
printf("underflow\n");
x=NULL;}
else{
x=(s->data)[s->top];
s->top--;}
return x;
}
/*从键盘输入括号进行匹配*/
int check(SEQSTACK *s)
{
char ch,x;
while((ch=getchar())!='\n')
{
switch(ch)
{
case '(':
case '[':
case '{':push(s,ch);break;
case ')':if(empty(s))return 0;
else {x=pop(s);
if(x!='(')return 0;}break;
case ']':if(empty(s))return 0;
else {x=pop(s);
if(x!='[')return 0;}break;
case '}':if(empty(s))return 0;
else {x=pop(s);
if(x!='{')return 0;}break;
default:break;
}
}
if(empty(s)) return 1;
else return 0;
}
void main()
{int m;
SEQSTACK stack ,*s;
s=&stack;
intistack(s);
printf("请输入各种括号进行配对：\n");
m=check(s);
if(m)printf("括号匹配成功！\n");
else
printf("括号匹配不成功！\n");
}
通过实验可以看出栈是一种后进先出的线性表，主要应用在编译系统中
实验三 队列的运算
一、实验目的与要求：
1、掌握队列的结构特性及其入队，出队操作；
二、实验内容：
杨辉三角：利用队列的先进先出的特征，输出杨辉三角形
微机+windows操作系统+VC++6.0
#include "stdio.h"
#define QUEUESIZE 100
typedef struct{
int data[QUEUESIZE];
int front,rear;
}CYQUEUE;
/*初始化队列*/
void initqueue(CYQUEUE *q)
{
q->front=q->rear=0;
}
/*判队列空*/
int emptyqueuq(CYQUEUE *q)
{
if(q->rear==q->front)
return 1;
else return 0;
}
/*入队*/
int inqueue(CYQUEUE *q,int x)
{
if(q->front==(q->rear+1)%QUEUESIZE)
return 0;
else
q->rear=(q->rear+1)%QUEUESIZE;
q->data[q->rear]=x;
return 1;
}
/*出队*/
int outqueue(CYQUEUE *q)
{
int x;
if(q->rear==q->front)
return 0;
else
q->front=(q->front+1)%QUEUESIZE;
x=q->data[q->front];
return x;
}
/*输出杨辉三角*/
void printyanghui(int n)
{
int s1,s2,i,j;
CYQUEUE q;
initqueue(&q);
printf("i\n");
inqueue(&q,1);
for(i=2;i<=n;i++)
{
s1=0;
for(j=1;j<=i-1;j++)
{
s2=outqueue(&q);
printf("%d ",s1+s2);
inqueue(&q,s1+s2);
s1=s2;
}
printf("1\n");
inqueue(&q,1);
}
}
void main()
{
int n;
printf("输入杨辉三角要显示的行数:");
scanf("%d",&n);
printyanghui(n);
}
队列是一种先进先出的线性表，杨辉三角主要体现在下一行的数值是通过上一行的前两个元素相加二得到，正好和队列的入队出队联系在一起，通过做入队出队操作可以完成该程序
实验四 串的模式匹配算法
一、实验目的与要求：
1、了解串的基本概念
2、掌握串的模式匹配算法的实现
二、实验内容：
在字符串S1中查找是否存在字符串S2，若存在返回字符串S2在字符串S1中的位置
微机+windows操作系统+VC++6.0
#include <stdio.h>
int index(char *s,char *t)
{
int i=0,j=0;
while(s[i]!='\0'&&t[j]!='\0')
if(s[i]==t[j])
{i++;
j++;
}
else
{i=i-j+1;
j=0;
}
if(t[j]=='\0')
return i-j+1;
else return 0;
}
void main()
{
char s[100],t[20];
int i;
printf("请输入符串s：\n");
gets(s);
printf("请输入符串t：\n");
gets(t);
i=index(s,t);
if(i!=0)
printf("字符串t在字符串s中存在，位置为%d\n",i);
else
printf("字符串t在字符串s中不存在\n");
}
串的模式匹配中，在进行匹配的时候如果匹配成功串的下标会增加，而在匹配失败的时候怎么让下标回撤，如何对下标的回撤进行操作是程序的关键
实验五 二叉树的遍历
一、实验目的与要求：
1、掌握二叉树的基本特性
2、掌握二叉树的先序、中序、后序的递归遍历算法
3、理解二叉树的先序、中序、后序的非递归遍历算法
4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性
二、实验内容：
采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作
微机+windows操作系统+VC++6.0
#include <stdio.h>
#include <stdlib.h>
typedef struct node1
{ char data;
struct node1 *lchild,*rchild;
}BTCHINALR;
/*二叉树的建立*/
BTCHINALR *createbt()
{
BTCHINALR *q;
struct node1 *s[30];
int i,j;
char x;
printf("请输入节点编号i和节点的值x:\n");
printf("i,x=");
scanf("%d,%c",&i,&x);
while(i!=0&&x!='$')
{q=(BTCHINALR *)malloc(sizeof(BTCHINALR));
q->data=x;
q->lchild=NULL;
q->rchild=NULL;
s[i]=q;
if(i!=1)
{j=i/2;
if(i%2==0)
s[j]->lchild=q;
else
s[j]->rchild=q;
}
printf("请输入节点编号i和节点的值x:\n");
printf("i,x=");
scanf("%d,%c",&i,&x);
}
return s[1];
}
/*二叉树的先序遍历*/
void preorder(BTCHINALR *bt)
{
if(bt!=NULL)
{
printf("%c",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
/*二叉树的中序遍历*/
void inorder(BTCHINALR *bt)
{
if(bt!=NULL)
{
inorder(bt->lchild);
printf("%c",bt->data);
inorder(bt->rchild);
}
}
/*二叉树的后序遍历*/
void postorder(BTCHINALR *bt)
{
if(bt!=NULL)
{
postorder(bt->lchild);
postorder(bt->rchild);
printf("%c",bt->data);
}
}
/*二叉树结点总数*/
int sumnodes(BTCHINALR *bt)
{
if(bt==NULL)
return 0;
else if(bt->lchild==NULL&&bt->rchild==NULL)
return 1;
else return sumnodes(bt->lchild)+sumnodes(bt->rchild)+1;
}
/*二叉树叶子结点总数*/
int leaf(BTCHINALR *bt)
{
if(bt==NULL)
return 0;
else if(bt->lchild==NULL&&bt->rchild==NULL)
return 1;
else return sumnodes(bt->lchild)+sumnodes(bt->rchild);
}
/*二叉树的深度*/
int depth(BTCHINALR *bt)
{
int dep1,dep2;
if(bt==NULL)
return 0;
else {dep1=depth(bt->lchild);
dep2=depth(bt->rchild);
if(dep1>dep2)return (dep1+1);
else return (dep2+1);
}
}
void main()
{ BTCHINALR *bt;
int m,n,k,p;
bt=createbt();
printf("先序遍历的结果是：");
preorder(bt);
printf("\n");
printf("中序遍历的结果是：");
inorder(bt);
printf("\n");
printf("后序遍历的结果是：");
postorder(bt);
printf("\n");
m=sumnodes(bt);
printf("二叉树结点总数是：%d\n",m);
n=leaf(bt);
printf("二叉树叶子结点总数是：%d\n",n);
k=depth(bt);
printf("二叉树的深度是：%d\n",k);
}
通过实验加深了对二叉树的性质的理解，以及二叉树的顺序和链式存储结构的结合，递归函数的编写及运行
实验六 图的应用
一、实验目的与要求：
1、掌握图的邻接矩阵和邻接表表示
2、掌握图的深度优先和广度优先搜索方法
3、理解图的应用方法
二、实验内容：
给定若干个路由器（顶点）及各路由器之间的代价值（顶点之间的权值），求从指定路由器（始点v0）开始，到其它各路由器（其余各顶点）的最短路径，直到所有路由器（顶点）计算完成为止
微机+windows操作系统+VC++6.0
#include "stdio.h"
#include "stdlib.h"
#define VEXTYPE int
#define ADJTYPE int
#define MAXLEN 40
#define MAX 10000
typedef struct
{
VEXTYPE vexs[MAXLEN];
ADJTYPE arcs[MAXLEN][MAXLEN];
int vexnum,arcnum;
int kind;
}MGRAPH;
MGRAPH create_mgraph()
{
int i,j,k,h;
MGRAPH mg;
mg.kind=3;
printf("请输入顶点数和边数：");
scanf("%d,%d",&i,&j);
mg.vexnum=i;
mg.arcnum=j;
for(i=0;i<mg.vexnum;i++)
{printf("第%d个顶点的信息 ：",i+1);
scanf("%d",&mg.vexs[i]);}
for(i=0;i<mg.vexnum;i++)
for(j=0;j<mg.vexnum;j++)
mg.arcs[i][j]=MAX;
for(k=1;k<=mg.arcnum;k++)
{
printf("第%d条边的起始顶点编号和终止顶点编号：",k);
scanf("%d,%d",&i,&j);
while(i<1||i>mg.vexnum||j<1||j>mg.vexnum)
{
printf(" 编号超出范围，重新输入：");
scanf("%d,%d",&i,&j);
}
printf("此边的权值:");
scanf("%d",&h);
mg.arcs[i-1][j-1]=h;
}
return mg;
}
void main()
{
MGRAPH mg;
int cost[MAXLEN][MAXLEN];
int path[MAXLEN],s[MAXLEN];
int dist[MAXLEN];
int i,j,n,v0,min,u;
mg=create_mgraph();
printf("请输入开始的顶点的编号：");
scanf("%d",&v0);
v0--;
n=mg.vexnum;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cost[i][j]=mg.arcs[i][j];
cost[i][i]=0;
}
for(i=0;i<n;i++)
{
dist[i]=cost[v0][i];
if(dist[i]<MAX&&dist[i]>0)
path[i]=v0;
}
for(i=0;i<n;i++)
s[i]=0;
s[v0]=1;
for(i=0;i<n;i++)
{
min=MAX;
u=v0;
for(j=0;j<n;j++)
if(s[j]==0&&dist[j]<min)
{
min=dist[j];
u=j;
}
s[u]=1;
for(j=0;j<n;j++)
if(s[j]==0&&dist[u]+cost[u][j]<dist[j])
{
dist[j]=dist[u]+cost[u][j];
path[j]=u;
}
}
for(i=0;i<n;i++)
if(s[i]==1)
{
u=i;
while(u!=v0)
{printf("%d<-",u+1);
u=path[u];}
printf("%d",u+1);
printf("d=%d\n",dist[i]);
}
else
printf("%d<-%d d=X\n",i+1,v0+1);
}
图的遍历，图的最短距离，建立在图的各种不同的存储结构上，程序中体现出了图的邻接矩阵的存储方式
实验七 快速排序
一、实验目的与要求：
1、掌握内部排序的基本算法；
2、分析比较内部排序算法的效率。
3、掌握快速排序的方法
二、实验内容：
通过一趟将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小。再对两个部分分别进行快速排序。
微机+windows操作系统+VC++6.0
#include "stdio.h"
#define N 10
//快速排序
void quicksort(int *r,int start,int end)
{int i,j,temp;
i=start;
j=end;
temp=r[i];
while(i<j)
{
while(i<j&&temp<=r[j])
j--;
r[i]=r[j];
while(i<j&&temp>=r[i])
i++;
r[j]=r[i];
}
r[i]=temp;
if(start<i-1)
quicksort(r,start,i-1);
if(i+1<end)
quicksort(r,i+1,end);
}
void main()
{int r[N],i;
printf("从键盘输入%d个整数:",N);
for(i=0;i<N;i++)
scanf("%d",&r[i]);
printf("输入的数据是:");
for(i=0;i<N;i++)
printf("%d ",r[i]);
printf("\n");
quicksort(r,0,N-1);
printf("排序之后的结果是:");
for(i=0;i<N;i++)
printf("%d ",r[i]);
}
快速排序的排序过程：
快速排序的时间效率：o(nlog2n)
快速排序的优缺点：当待排数据有序的情况下，排序的效率反而更低