《数据结构》实验教学大纲_数据结构实验试做记录
《数据结构》实验教学大纲由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验试做记录”。
《数据结构》实验教学大纲
实验1 线性表的基本操作
1实验目的(1)熟练掌握线性表的逻辑特征。
（2）熟练掌握线性表的基本操作在两种存储结构上的实现。2实验内容
（1）设计一个顺序表的基本操作的演示程序（2）设计一个单链表的基本操作的演示程序（3）设计一个双链表的基本操作的演示程序 【基本要求】
实现下列4种基本运算：（1）初始化线性表；（2）在第I个元素前插入一个元素e；（3）删除第I个元素；（4）遍历线性表；（5）将单链表逆置
【测试数据】自定 参考程序如下： //顺序表的基本操作 #include //顺序表的定义 #define MAX 15
typedef struct{
int elem[MAX];
int length;}Sqlist;
void Initlist_sq(Sqlist &L);void ListInsert_sq(Sqlist &L,int i, int e);void ListDel_sq(Sqlist &L,int i, int &e);void print_sq(Sqlist L);
// 函数的定义
void Initlist_sq(Sqlist &L){
L.length =0;}
void ListInsert_sq(Sqlist &L,int i, int e){
int *p,*q;if(iL.length +1)return;
q=&L.elem[i-1];//插入位置
for(p=&L.elem[L.length-1];p>=q;--p)
*(p+1)=*p;*q=e;++L.length;return;} void ListDel_sq(Sqlist &L,int i, int &e){
if(iL.length)return;e=L.elem[i-1];
for(int j=i;j
L.elem[j-1]=L.elem[j];--L.length;}
void print_sq(Sqlist L){ int *p,*q=L.elem+L.length-1;for(p=L.elem;p
cout
void main(){ int a[11]={10,20,30,40,50,60,70,80,90,100};Sqlist L;
//初始化顺序表
Initlist_sq(L);cout
// 插入10个数据元素
for(int i=1;i
ListInsert_sq(L, i, a[i-1]);
cout
//遍历
print_sq(L);
cout
//删除第5个元素
int x;
ListDel_sq(L,5, x);
cout
cout
print_sq(L);
cout
// 单链表的操作 #include struct NODE {
int data;NODE *next;};
void print(NODE *&head);//遍历
int data[6]={25,41,17,98,5,6};void Setup_L(NODE *&head,int n);//生成单链表 void Insert_L(NODE *&head, int I, int e);//插入
void Delete_L(NODE * &head, int I,int
&e);//删除 void Convert_L(NODE *&head)； //逆序 void main()
{
NODE *L;
Setup_L(L,6);print(L);//Insert_L(L,7,50);print(L);int x;Delete_L(L,0,x);cout
print(L);Convert_L(L);print(L);
}
void print(NODE *&head){ NODE *p;p=head->next;
while(p){
coutdata
p=p->next;//后移指针
}
cout
NODE *q,*p;head=(NODE*)new NODE;
head->next=NULL;//先建立一个带头结点的单链表
q=head;
for(int i=0;i
p=(NODE *)new NODE;//生成新结点
p->data=data[i];
q->next=p;q=p;//插入到表头
} q->next =NULL;}
void Insert_L(NODE *&L,int i, int e){ NODE *p=L,*q;int j=0;while(p&&jnext;
j++;
}
if(!p||j>i-1){ cout
return;} q=(NODE*)new NODE;q->data=e;q->next =p->next;p->next =q;}
void Delete_L(NODE *&L,int i,int &e){ NODE *p=L,*q;int j=0;while(p&&jnext;
j++;
}
if(!p||j>i-1){ cout
return;}
q=p->next;e=q->data;p->next =q->next;delete q;} void Convert_L(NODE *&L){ NODE *p,*q,*r;p=L->next;
q=p->next;p->next =NULL;while(q){
r=q->next;
q->next =p;
L->next=q;
p=q;
q=r;
} }
//双链表的基本操作 struct NODE { int data;NODE *next;NODE *prior;};int data[6]={3,5,7,19,20,21};//测试用数据 // 函数声明
void print(NODE *&head);void Setup_L(NODE*&head,int n);void Insert_L(NODE *&L,int i,int e);void Delete_L(NODE *&L,int i,int &e);void Convert_L(NODE*&L);// 主函数和各函数的定义 void main(){ NODE *L;Setup_L(L,6);print(L);Insert_L(L,7,50);print(L);int x;Delete_L(L,1,x);cout
void print(NODE *&head){ // 从头开始顺序输出双链表中的数据
NODE *p;p=head->next;while(p){coutdatanext;} cout
NODE *q,*p;head=(NODE*)new NODE;head->next=NULL;q=head;for(int i=0;i
p=(NODE*)new NODE;
p->data=data[i];
//cin>>p->data;
p->prior=q;q->next=p;q=p;} q->next=NULL;//return(head);} void Insert_L(NODE *&L,int i,int e){//在带头结点的双链表中第i个位置插入元素e NODE*p=L,*q;int j=0;//j为计数器
while(p&&jnext;j++;} //寻找第i-1个结点
if(!p||j>i-1)//i小于1或大于表长
{cout
q->data=e;if(p->next==NULL){q->next=p->next;p->prior=q;p->next=q;} else {q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;} //插入L中 } void Delete_L(NODE*&L,int i,int &e){//在带头结点的双链表L中，删除第i个元素，并由e返回其值
NODE *p=L,*q;int j=0;while(p&&j
{p=p->next;j++;} if(!p||j>i-1){cout
return;} q=p->next;e=q->data;q->next->prior=p;p->next=q->next;delete q;}//删除并释放结点 3 实验要求
按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。
实验2 栈和队列的基本操作
1实验目的(1)(2)(3)(4)
深入了解栈和队列的基本特性
熟练掌握栈的基本操作在两种存储结构上的实现。熟练掌握循环队列的基本操作 熟练掌握链队列的基本操作2实验内容
（1）设计一个顺序栈的基本操作的演示程序（2）设计一个链栈的基本操作的演示程序（3）设计一个循环队列的基本操作的演示程序（4）设计一个链队列的基本操作的演示程序 【基本要求】
实现下列6种基本运算：（1）初始化；（2）入栈（队列）；（3）出栈（队列）；（4）遍历；（5）求栈（队列）的长度
【测试数据】自定 参考程序如下： //顺序栈的基本操作 #include #define MAX 10 typedef struct{
int base;
int top;
int st[MAX];}SqStack;
//基本操作说明
void InitStack(SqStack &S);void push(SqStack &S, int e);void pop(SqStack &S,int &e);
//基本操作的算法描述 void InitStack(SqStack &S){ S.base=S.top=0;} void push(SqStack &S, int e){ if(S.top==MAX)
{cout
return;} S.st[S.top] =e;S.top+=1;} void pop(SqStack &S,int &e){
if(S.top ==0)
{ cout
S.top-=1;
e=S.st[S.top];} void print(SqStack S){ cout
for(int I=0;I
cout
“;
cout
void main(){ SqStack S;
//初始化
cout
cout
for(int I=0;I
push(S, 2*I+1);
cout
int x;pop(S,x);cout
} //循环队列的基本操作 #include #define MAX 8 typedef struct { int base[MAX];int front;int rear;} SqQueue;
/*********** 初始化 **************/ void InitQueue(SqQueue &Q)
{
Q.front=Q.rear=0;}
//******求队列长度******// int QueueLength(SqQueue Q){
return(Q.rear-Q.front+MAX)%MAX;} //*****入队列****************// void EnQueue(SqQueue &Q,int e){ if((Q.rear+1)%MAX==Q.front)
cout
else
{ Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAX;} } //*******遍历队列******// void traverse(SqQueue &Q){
int I, k;
if(Q.front
k=0;
else
k=1;
switch(k)
{
case 0:
for(I=Q.front;I
cout
“;
break;
case 1:
for(I=Q.front;I
cout
“;
for(I=0;I
cout
} }
/**************出队************/ int DeQueue(SqQueue &Q,int &e){
if(Q.rear==Q.front)return –1;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAX;
return 1;}
void main(){
SqQueue Q;
InitQueue(Q);int j,m,x;for(j=0;j
EnQueue(Q,2*j);traverse(Q);m=QueueLength(Q);cout
“;
m=QueueLength(Q);cout
按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。
实验3 二叉树的基本操作
1实验目的（1）掌握二叉树的非线性和递归特点。（2）熟练掌握二叉树的存储结构。
（3）熟练掌握二叉树的各种遍历操作和其它操作的实现方法。2 实验内容
设计一个可进行二叉树基本操作的演示程序。【基本要求】实现下列六种基本运算：（1）创建二叉树；（2）先序遍历二叉树；（3）中序遍历二叉树；（4）后序遍历二叉树；（5）层序遍历二叉树；（6）求度为1的结点的个数；（7）求叶子结点的个数；（8）求度为2的结点的个数。
二叉树以链式结构表示，主程序以菜单方式的用户界面。【测试数据】自定
//二叉树的基本操作 #include
typedef struct node
//定义结点 {
char data;
struct node *lchild, *rchild;} BinTNode;
typedef BinTNode *BinTree;//定义二叉树
void CreateBinTree(BinTree &T);
//先序创建二叉树 void PreOrder(BinTree T);
//先序遍历二叉树 void InOrder(BinTree T);
//中序遍历二叉树 void PostOrder(BinTree T);
//后序遍历二叉树
int onechild(BinTree T);
//求度为1的结点的个数 int leafs(BinTree T);
//求叶子结点的个数 int twochild(BinTree T);
//度为2的结点的个数 void translevel(BinTree b)
//层序遍历二叉树
void main(){
int n;
BinTree T;
char ch1,ch2;
cout
cout
ch1='y';
while(ch1=='y'||ch1=='Y')
{
cout
cout
cout
cout
cout
cout
cout
cout
cout
cin>>ch2;
switch(ch2)
{
case 'a':
case 'A':
cout
CreateBinTree(T);
break;
case 'b':
case 'B':
cout
PreOrder(T);
break;
case 'c':
case 'C':
cout
InOrder(T);
break;
case 'd':
case 'D':
cout
PostOrder(T);
break;
case 'f':
case 'F':
cout
n=onechild(T);
cout
break;
case 'g':
case 'G':
cout
n=twochild(T);
cout
break;
case 'h':
case 'H':
cout
n=leafs(T);
cout
break;case „e‟: case „E‟:
cout
translevel(T);
break;
case 'x':
case 'X':
ch1='x';
break;
}
}
}
void CreateBinTree(BinTree &T){
char ch;
cin>>ch;
if(ch=='0')
T=NULL;
else
{
T=(BinTNode *)new BinTNode;
T->data=ch;
CreateBinTree(T->lchild);
CreateBinTree(T->rchild);
} }
void InOrder(BinTree T){ if(T){
InOrder(T->lchild);
coutdata
InOrder(T->rchild);
} }
void PostOrder(BinTree T){ if(T){
PostOrder(T->lchild);
PostOrder(T->rchild);
coutdata
void PreOrder(BinTree T){ if(T){
coutdata
PreOrder(T->lchild);
PreOrder(T->rchild);} }
//层序遍历二叉树
//采用一个队列q，先将二叉树的根 结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。
因为队列的特点是先进先出，从而达到按层序遍历的目的。
#define MAXLEN 100 void translevel(BinTree b){
struct node {
BinTree vec[MAXLEN];
int f, r;}q;//定义队列q，f 表示队头指针，r队尾指针 q.f=0;
//置队列为空队列 q.r=0;
if(b!=NULL)coutdata
//结点指针进入队列 q.r=q.r+1;
//队尾指针后移
while(q.f
//队列不为空 { b=q.vec[q.r];
//队头出队列 q.f=q.f+1;if(b->lchild!=NULL)
//输出左孩子，并入队列 {
coutlchild->data
q.vec[q.r]=b->lchild;
q.r=q.r+1;} if(b->rchild!=NULL)
//输出右孩子，并入队列 {
coutrchild->data
q.vec[q.r]=b->rchild;
q.r=q.r+1;} } }
int onechild(BinTree T){ int num1,num2;if(T==NULL)return 0;else if(T->lchild ==NULL && T->rchild!=NULL||T->lchild!=NULL && T->rchild==NULL)
return 1;else {
num1=onechild(T->lchild);
num2=onechild(T->rchild);
return num1+num2;
} } int leafs(BinTree T){ int num1,num2;if(T==NULL)return 0;else if(T->lchild==NULL &&T->rchild ==NULL)return 1;else
{
num1=leafs(T->lchild);
num2=leafs(T->rchild);
return num1+num2;} } 3 实验要求
按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。
实验4 哈夫曼树及哈夫曼编码
1实验目的（1）熟练掌握哈夫曼树的特点。（2）熟悉哈夫曼树的构造方法 实验内容
哈夫曼算法 3 实验要求
按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。参考代码： #include #include #define MAX 21 typedef struct{ char data;
int weight;
int parent,lchild,rchild;}huffnode;typedef struct { char cd[MAX];int start;}huffcode;
void main(){ huffnode ht[2*MAX];huffcode hcd[MAX],d;int i, k,f ,l,r, n,c,m1,m2;printf(“元素个数:”);
cout
for(i=1;int结点值:“;
cin>>ht[i].data);cout
ht[i].parent=ht[i].lchild=ht[i].rchild=0;for(i=n+1;i
m1=m2=32767;
l=r=0;
for(k=1;k
if(ht[k].parent==0)
if(ht[k].weight
{
m2=m1;
r=1;
}
m1=ht[k].weight;
l=k;
}
else if(ht[k].weight
{
m2=ht[k].weight;
r=k;
}
ht[l].parent=i;
ht[r].parent=i;
ht[i].weight=ht[l].weight+ht[r].weight;
ht[i].lchild=l;
ht[i].rchild=r;} for(i=1;i
if(ht[f].lchild==c)
d.cd[--d.start]='0';
else d.cd[--d.start]='1';
c=f;
f=ht[f].parent;} hcd[i]=d;} cout
for(k=hcd[i].start;k
cout
实验5 图的基本操作
1实验目的（3）熟练掌握图的非线性结构的特点。
（4）掌握图的邻接矩阵和邻接表的存储结构。
（5）掌握图的两种常用存储结构下的深度优先搜索和广度优先搜索操作和其它操作的实现 2 实验内容
(1)设计一个基于图的邻接矩阵的图的基本操作的演示程序。(2)设计一个基于图的邻接表的图的基本操作的演示程序。【基本要求】
实现下列六种基本运算：（1）创建图；（2）深度优先遍历图；（3）广度优先遍历图；（4）转换图的存储结构
分别在图的邻接矩阵和邻接表的存储结构实现 【测试数据】自定 参考程序如下：
//图的邻接矩阵的基本操作
#define MAX_VERTEX_NUM 20 typedef struct ArcCell { int adj;}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct {
int vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;//邻接矩阵图的定义
typedef struct ArcNode{ int adjvex;struct ArcNode *next;}ArcNode;typedef struct VNode{ int data;ArcNode *first;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{ AdjList vertices;int vexnum,arcnum;}ALGraph;
//图的邻接表的定义
bool visited[MAX_VERTEX_NUM];void CreateUDG(MGraph &G);void printMGraph(MGraph G);void DFSTraverse(MGraph G);void DFSM(MGraph G,int i);void BDFTraverse(MGraph G);void change(ALGraph &R,MGraph G);void printALGraph(ALGraph R);
void main(){
MGraph G;ALGraph R;cout
CreateUDG(G);cout
BDFTraverse(G);
change(R,G);printALGraph(R);} void CreateUDG(MGraph &G){
int v1,v2;
int i,j,k;cout
cin>>G.vexnum >>G.arcnum;
cout
for(i=0;i
cin>>G.vexs[i];
for(i=0;i
for(j=0;j
G.arcs[i][j].adj=0;for(k=0;k
cout
cin>>v1>>v2;
i=v1-1;
j=v2-1;
G.arcs[i][j].adj=1;
G.arcs[j][i].adj=G.arcs[i][j].adj;}}
void printMGraph(MGraph G){ int i,j;cout
for(j=0;j
{cout
”;
if((1+j)%G.vexnum ==0)
cout
if(G.arcs[i][j].adj==1 &&!visited[j])
DFSM(G,j);} void DFSTraverse(MGraph G){
int i;
for(i=0;i
visited[i]=0;
for(i=0;i
if(!visited[i])
DFSM(G,i);} void change(ALGraph &R,MGraph G){ int i,j;ArcNode *p;R.arcnum =G.arcnum;R.vexnum =G.vexnum;for(i=0;i
R.vertices[i].data=G.vexs[i];
R.vertices[i].first =NULL;}
for(i=0;i
for(j=0;j
if(G.arcs[i][j].adj ==1)
{ p= new ArcNode;
p->adjvex =j;
p->next =R.vertices[i].first;
R.vertices[i].first =p;
} }
void printALGraph(ALGraph R){
int i;
ArcNode *p;
for(i=0;i
{ cout
p=R.vertices[i].first;
while(p!=NULL)
{
cout“adjvex+1;
p=p->next;
}
cout
void BDFTraverse(MGraph G){
int queue[MAX_VERTEX_NUM];
int front=0,rear=0;
int j,v;
cout
for(v=0;v
visited[v]=0;
//初始顶点为 1
v=0;
visited[v]=1;
cout
queue[rear]=v;//入队
rear=(rear+1)%MAX_VERTEX_NUM;
while(front!=rear){
v=queue[front];
front=(front+1)% MAX_VERTEX_NUM;//出队
//访问与v邻接的顶点
for(j=0;j
if(G.arcs[v][j].adj==1 &&!visited[j])
{
queue[rear]=j;//入队
rear=(rear+1)%MAX_VERTEX_NUM;
cout
visited[j]=1;
}
} } //基于邻接表的图的基本操作 #include
#define MAX_VERTEX_NUM 10
//最大顶点数 #define NULL 0 typedef enum{FALSE,TRUE} Boolean;
//false表示0，TRUE表示1 typedef struct ArcNode
//弧结点类型{ int adjvex;
//以i为顶点（弧尾）的另一个顶点j在表头数组中的位置
struct ArcNode *nextarc;
//指向下一条弧的指针 }ArcNode;typedef struct VNode //表头结点顶点类型 {
int data;
//顶点 i的数据，按编号，从1开始。
ArcNode *firstarc;//该顶点的第一条弧指针 }VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
//邻接表图 {
AdjList vertices;
int vexnum,arcnum;}ALGraph;
typedef struct ArcCell { int adj;}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct {
int vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;//邻接矩阵图的定义
Boolean visited[MAX_VERTEX_NUM];//访问数组
void CreateALGraph(ALGraph *G)
//创建图 {
ArcNode *s;
int i,j,k;
cout
//对于有向图指弧的数目，对无向图边数为弧的2倍
cin>>G->vexnum>>G->arcnum;
coutvexnum
for(i=0;ivexnum;i++)
{
cin>>G->vertices[i].data;
G->vertices[i].firstarc =NULL;
}
coutarcnum
for(k=0;karcnum;k++)
{
cout
cin>>i>>j;
s=(ArcNode *)new ArcNode;
s->adjvex =j-1;
s->nextarc =G->vertices [i-1].firstarc;
G->vertices[i-1].firstarc =s;
} }
void BFS(ALGraph *G,int k)
//宽度优先搜索 { for(int v=0;vvexnum;v++)
visited[v]=FALSE;ArcNode *p;int i,Q[MAX_VERTEX_NUM],front,rear;front=rear=0;coutvertices[k].data;visited[k]=TRUE;Q[rear]=k;rear=(rear+1)%MAX;
while(front!=rear){
i=Q[front];
front=(front+1)%MAX;
p=G->vertices[i].firstarc;
while(p)
{
if(!visited[p->adjvex])
{
coutvertices [p->adjvex ].data;
visited[p->adjvex]=TRUE;
Q[rear]=p->adjvex;
rear=(rear+1)%MAX;
}
p=p->nextarc;
} } } void DFS(ALGraph *G,int v);
void DFSTraverse(ALGraph *G)//深度优先搜索 { int i;
for(i=0;ivexnum;i++)
visited[i]=FALSE;cout
for(i=0;ivexnum;i++)
if(!visited[i])DFS(G,i);} void DFS(ALGraph *G,int v){
coutvertices[v].data;
visited[v]=TRUE;
ArcNode *p;
p=G->vertices[v].firstarc;
while(p)
{
if(!visited[p->adjvex])DFS(G,p->adjvex);
p=p->nextarc;
} }
void change(ALGraph G,MGraph &M){
M.arcnum=G.arcnum;
M.vexnum=G.vexnum;
int i,j;
ArcNode *p;
for(i=0;i
for(j=0;j
M.arcs[i][j].adj =0;
for(i=0;i
{
p=G.vertices[i].firstarc;
while(p)
{ j=p->adjvex;
M.arcs[i][j].adj=1;
p=p->nextarc;
} } } void printMGraph(MGraph G){ int i,j;cout
for(j=0;j
{cout
”;
if((1+j)%G.vexnum ==0)
cout
printMGraph();void main(){ ALGraph G;MGraph M;int v;CreateALGraph(&G);for(v=0;v
if(!visited[v])
BFS(&G,v);
cout
DFSTraverse(&G);cout
3 实验要求
按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。
中央广播电视大学“开放教育试点”计算机科学与技术专业（本科）《数据结构》课程教学大纲第一部分 大纲说明一、课程的性质和任务《数据结构》是计算机科学与技术专业本科生的......
《数据结构与算法》教学大纲课程编号：030816 适用专业：教育技术学 总学时数：64 学 分：4 编制单位：茂名学院理学院教育与信息技术系 编制时间：2008年6月20日 一、课程地位、性质和......
《数据结构课程设计》课程设计教学大纲Course Design of Data Structure课程代码：适用专业：信息计算、信息安全 总学时数：1周编写年月：2004年7月执 笔：刘科峰、李小英、高学军课......
数据结构课程教学大纲一、课程基本概况课程名称：数据结构课程名称（英文）： Data Structures 课程编号：B09042 课程总学时：60（其中，讲课48，实验12）课程学分：3 课程分类：专业选修课开设学......
《数据结构》课程设计教学大纲适用专业：计算机科学与技术 课程周数：2周一、大纲说明本大纲根据计算机科学与技术专业人才培养方案制订。（一）课程设计性质课程设计是学生对课程所......
