教学编制问题 c语言 数据结构实现[五篇范例]

第一篇：教学编制问题 c语言 数据结构实现

数据结构 课程设计报告

主题：教学计划编制问题 学号：20091003768 班级：计科四班 姓名：熊金莲 指导老师：郭艳

内容概要

（1）题目要求

（2）教学计划编制问题的要点

（3）函数模块及各函数可实现的功能简介（4）具体的源代码（5）使用说明（6）实验心得

一：题目要求如下：

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

要求

（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）学分和直接先修课的课程号。

（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。

（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。

二：教学计划编制问题的要点：

根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题——输出每学期的课程。

1）采用第二种策略：使课程尽可能地集中在前几个学期中； 2）根据教学计划中的课程及其关系和学分定义图的顶点和 边的结构体

3）创建图CreateGraph（）：结合先修关系的AOV网，显示代号所对应课程及课程的先修课程

4）拓扑排序TopologicalOrder(G)：将课程排序后并决定出每学期所学课程，输出图G的信息Display(G)：将图的顶点和弧边输出

三：程序模块及可实现的功能简介：

1）、图的邻接表的存储表示，即结构体的定义

typedef struct ArcNode { int AdjOfV;

// 该弧所指向的顶点的位置 struct ArcNode *next;

//指向下一条弧的指针

}ArcNode;

typedef char VertexType[MAXOfNAME];typedef struct

//链接表 {

VertexType data;

//顶点信息 int grades;

//存储学分信息

ArcNode *first;

//指向第一条依附该顶点的弧的指针

}VNode, AdjList[MAX_VER];

// 头结点

typedef struct { AdjList ver;

//vertices 存储课程名

int vexnum, arcnum;

// 图的当前顶点数和弧数

}ALGraph;

2）、利用前插法，建立图的邻接链表

printf(“请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)n”);

for(h=0;h

// 构造表结点链表,利用前插法

{

printf(“%s的先修课程:”,G.ver[h].data);

scanf(“%s”,va);getchar();

while(va[0]!='0')

{

i = LocateVex(G, va);

//弧头

j = h;

//弧尾

p =(ArcNode*)malloc(sizeof(ArcNode));

p->AdjOfV = j;

p->next = G.ver[i].first;// 插在表头

G.ver[i].first = p;

scanf(“%s”,va);

getchar();

}

}

3）、输出图的顶点和边

printf(“%d个顶点”, G.vexnum);

for(i = 0;i < G.vexnum;++i)printf(“%4s”, G.ver[i].data);

printf(“ n%d条弧边:n”,G.arcnum);

for(i = 0;i < G.vexnum;i++)

{

p = G.ver[i].first;

while(p)

{

printf(“%s---->%sn”,G.ver[i].data,G.ver[p->AdjOfV].data);

p = p->next;

}

}

4）、通过栈实现拓扑排序

int TopologicalOrder(ALGraph G,AdjList R,struct Name name[]){

int i, k, j = 0, count, indegree[MAX_VER];SqStack S;ArcNode *p;FindInDegree(G, indegree);

// 对各顶点求入度 InitStack(S);

// 初始化栈 for(i = 0;i < G.vexnum;++i)

//建零入度顶点栈S

if(!indegree[i])Push(S, i);// 入度为0者进栈 count = 0;

// 对输出顶点计数 while(!StackEmpty(S)){

} Pop(S, i);printf(“%s(%d学分),”,G.ver[i].data,G.ver[i].grades);R[j++] = G.ver[i];//将当前的拓扑序列保存起来 ++count;

// 输出i号顶点并计数

for(p =G.ver[i].first;p;p=p->next)// 对i号顶点的每个邻接点的入度减1 {

} k = p->AdjOfV;if(!(--indegree[k]))// 若入度减为0,则入栈

Push(S, k);

}

if(count < G.vexnum){

} else printf(“

为一个拓扑序列”);printf(“n”);

int q=1,Z=0;while(q <= TotalOfTerms){

int C = R[Z].grades;printf(“n第%d个学期应学课程:”,q);while(C <= MaxScores){ C = C + R[Z+1].grades;printf(“此有向图有回路无法完成拓扑排序”);return 0;if(Z < G.vexnum)

{

CmpOfStr(R[Z].data,name,N);/*让C1~C12分别与12门课程对应起来*/

}

return 1;/**/ ++Z;} printf(“n”);if(q == TotalOfTerms)printf(“nOK Over!”);q++;} 依次将入度为0的顶点存入InDegree中，对每个顶点求入度，并存入数组InDegree[i]中（i=0…n），初始化栈Stack,Counter=0，对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Counter++)，推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Counter++），堆栈是否为空？，n个顶点全输出，依次将入度为0的顶点存入InDegree中

5)根据学分上限决定出每学期应学课程，其中R[ ]中存储的是经过拓扑排序后的课程先后顺序。

int q=1,Z=0;

while(q <= TotalOfTerms){

int C = R[Z].grades;printf(“n第%d个学期应学课程:”,q);while(C <= MaxScores)

{

C = C + R[Z+1].grades;if(Z < G.vexnum){ CmpOfStr(R[Z].data,name,N);/*让C1~C12分别与12门课程对应起来*/

++Z;}

} } printf(“n”);if(q == TotalOfTerms)printf(“nOK Over!”);q++;四：具体的源代码

本程序分为三部分 A:::::::::SeqStack.h

1）2）3）4）5）6）7）8）9）10）11）12）13）14）15）16）17）18）19）20）21）22）23）24）25）26）27）28）29）30）31）32）33）34）35）36）37）38）#define StackofNUM 20

//存储空间初始分配量 #define StackforMore 5

// 存储空间分配增量

typedef struct SqStack { int *a;

int *top;

int size;

//分配的存储空间 }SqStack;

int InitStack(SqStack &S)

/*栈的初始化*/ {

S.a=(int *)malloc(StackofNUM * sizeof(int));if(!S.a)exit(-1);S.top =S.a;S.size =StackofNUM;return 1;}

int StackEmpty(SqStack S)

/*判断栈是否为空*/ {

if(S.top == S.a)return 1;else return 0;} int Push(SqStack &S, int x)/*入栈*/

{ if(S.top-S.a >= S.size){

S.a =(int *)realloc(S.a,(S.size + StackforMore)* sizeof(int));

if(!S.a)exit(-1);

S.top =S.a +S.size;

S.size +=StackforMore;} *S.top++ = x;return 1;}

int Pop(SqStack &S, int &x)

/*出栈*/ 39）40）41）42）43）{

if(S.top == S.a)return 0;x = *--S.top;

return 1;}

B:::::::::ALGraph.h 44）45）46）47）48）49）50）51）52）53）54）55）56）57）58）59）60）61）62）63）64）65）66）67）68）69）70）71）72）73）74）75）76）77）78）79）80）#define MAXOfNAME 3

//最多字符个数 #define MAX_VER 100 //最大顶点数

typedef struct ArcNode { int AdjOfV;

// 该弧所指向的顶点的位置

struct ArcNode *next;

//指向下一条弧的指针 }ArcNode;

typedef char VertexType[MAXOfNAME];

typedef struct

//链接表

{ VertexType data;

//顶点信息

int grades;

//存储学分信息

ArcNode *first;

//指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VER];

// 头结点

typedef struct { AdjList ver;

//vertices 存储课程名

int vexnum, arcnum;

// 图的当前顶点数和弧数 }ALGraph;

int TotalOfTerms;

//学期总数 int MaxScores;

//学分上限

int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */

{

int i;

for(i = 0;i < G.vexnum;++i)

if(strcmp(u,G.ver[i].data)==0)return i;

return-1;}

int CreateGraph(ALGraph &G)

/*采用邻接表存储结构*/ {

int i, j, h;81）82）83）84）85）86）87）88）89）90）91）92）93）94）95）96）97）98）99）100）101）102）103）

VertexType va;

ArcNode *p;

printf(“请输入教学计划的课程数: ”);

scanf(“%d”,&G.vexnum);

getchar();

printf(“请输入各个课程的先修课程的总和(弧总数): ”);

scanf(“%d”,&G.arcnum);

getchar();

printf(“请输入%d个课程的课程号(最多%d个字符,字母+数字如C10):”, G.vexnum,MAXOfNAME);

for(i = 0;i < G.vexnum;++i)

{

scanf(“%s”,&G.ver[i].data);

getchar();

G.ver[i].first = NULL;

}

printf(“请输入%d个课程的学分值:”,G.vexnum);

for(i = 0;i < G.vexnum;++i)

{

scanf(“%d”,&G.ver[i].grades);getchar();

}

printf(“请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)n”);

for(h=0;h

// 构造表结点链表,利用前插法

104）

{

105）

printf(“%s的先修课程:”,G.ver[h].data);106）107）108）109）110）

scanf(“%s”,va);getchar();

while(va[0]!='0')

{

i = LocateVex(G, va);

//弧头

j = h;

//弧尾

111）

p =(ArcNode*)malloc(sizeof(ArcNode));112）

p->AdjOfV = j;113）

p->next = G.ver[i].first;// 插在表头 114）115）116）117）118）119）120）121）

G.ver[i].first = p;

scanf(“%s”,va);getchar();

}

}

return 1;}

void Display(ALGraph G)

/* 输出图G的信息*/ 122）{ 123）124）125）126）

int i;

ArcNode *p;

printf(“有向图n”);

printf(“%d个顶点”, G.vexnum);127）

for(i = 0;i < G.vexnum;++i)printf(“%4s”, G.ver[i].data);128）

printf(“ n%d条弧边:n”,G.arcnum);129）130）131）132）133）134）135）136）137）138）139）140）141）142）143）144）145）146）147）148）149）150）151）152）153）154）155）156）157）158）159）160）161）162）163）164）165）

for(i = 0;i < G.vexnum;i++)

{

p = G.ver[i].first;

while(p)

{

printf(“%s---->%sn”,G.ver[i].data,G.ver[p->AdjOfV].data);

p = p->next;

}

} }

void FindInDegree(ALGraph G, int indegree[])

/*求顶点的入度*/ {

int i;

ArcNode *p;

for(i = 0;i < G.vexnum;i++)indegree[i] = 0;

for(i = 0;i < G.vexnum;i++)

{

p = G.ver[i].first;

while(p)

{

indegree[p->AdjOfV]++;

p = p->next;

}

} } struct Name {

char c[20];}name;

void CmpOfStr(VertexType str,struct Name name[],int n)

/*让C1~C12分别与12门课程对应起来*/ {

if(strcmp(str,name[0].c)==0)printf(“ 程序设计基础”);

if(strcmp(str,name[1].c)==0)printf(“ 离散数学”);

if(strcmp(str,name[2].c)==0)printf(“ 数据结构”);

if(strcmp(str,name[3].c)==0)printf(“ 汇编语言 ”);

if(strcmp(str,name[4].c)==0)printf(“ 语言的设计和分析 ”);166）167）168）169）170）171）172）

if(strcmp(str,name[5].c)==0)printf(“ 计算机原理”);

if(strcmp(str,name[6].c)==0)printf(“ 编译原理”);

if(strcmp(str,name[7].c)==0)printf(“ 操作系统 ”);

if(strcmp(str,name[8].c)==0)printf(“ 高等数学”);

if(strcmp(str,name[9].c)==0)printf(“ 线性代数”);

if(strcmp(str,name[10].c)==0)printf(“ 普通物理”);

if(strcmp(str,name[11].c)==0)printf(“ 数值分析”);C::::::::::::::::::教学计划编制问题.Cpp

#include #include #include #include #include “SeqStack.h” #include “ALGraph.h” #define N 12 int TopologicalOrder(ALGraph G,AdjList R,struct Name name[]){

int i, k, j = 0, count, indegree[MAX_VER];

SqStack S;ArcNode *p;FindInDegree(G, indegree);

// 对各顶点求入度

InitStack(S);

// 初始化栈

for(i = 0;i < G.vexnum;++i)

//建零入度顶点栈S

if(!indegree[i])Push(S, i);// 入度为0者进栈

count = 0;

// 对输出顶点计数

while(!StackEmpty(S))

{

Pop(S, i);

printf(“%s(%d学分),”,G.ver[i].data,G.ver[i].grades);

R[j++] = G.ver[i];//将当前的拓扑序列保存起来

++count;

// 输出i号顶点并计数

for(p =G.ver[i].first;p;p=p->next)// 对i号顶点的每个邻接点的入度减1

{

k = p->AdjOfV;

if(!(--indegree[k]))// 若入度减为0,则入栈

Push(S, k);

}

}

if(count < G.vexnum)

{

printf(“此有向图有回路无法完成拓扑排序”);

return 0;

}

else printf(“

为一个拓扑序列”);

printf(“n”);

int q=1,Z=0;

while(q <= TotalOfTerms)

{

int C = R[Z].grades;

printf(“n第%d个学期应学课程:”,q);

while(C <= MaxScores)

{

C = C + R[Z+1].grades;

if(Z < G.vexnum)

{

CmpOfStr(R[Z].data,name,N);/*让C1~C12分别与12门课程对应起来*/

++Z;

}

}

printf(“n”);

if(q == TotalOfTerms)printf(“nOK Over!”);

q++;

}

return 1;/**/ } void main(){

ALGraph G;

AdjList R;

struct Name name[N]={{“C1”},{“C2”},{“C3”},{“C4”},{“C5”},{“C6”},{“C7”},{“C8”},{“C9”},{“C10”},{“C11”},{“C12”}};

printf(“

***************教学计划编制问题**************n”);

printf(“请以课件9-2上课程先序图为例输入学期总数:”);

scanf(“%d”,&TotalOfTerms);

getchar();

printf(“请输入学期的学分上限（8或9）:”);

scanf(“%d”,&MaxScores);

getchar();

CreateGraph(G);

Display(G);

TopologicalOrder(G,R,name);} 五：说明：

本程序按照课件9-2所显示的那12门课程编排，示列6个学期，每学期不超过学分数示例输入9。程序示例运行如下：

六：实验心得：

经过此次课程设计，我深刻地认识到自己写程序的不足，认识到了仅仅只是从课本上学到算法原理是远远不够的，理论与实践结合才是最重要的。实验中，我总是不经意间出现各种错误，这就要求 今后的我要以脚踏实地的态度来思考处理问题。总之本次课程设计，让我进一步熟悉了C语言的语句用法，学到了很多有用的知识。

第二篇：c语言迷宫问题代码实现

C语言迷宫问题代码如下：

#include

#include

#define LEN sizeof(SEAT)

#define MAXSIZE 100

#define LENGTH 30

typedef struct

{

int x;//横坐标

int y;//纵坐标

int di;//表示方向，0-3分别表示东南西北。

}SEAT;

struct StackList

{

SEAT stack[MAXSIZE];

int top;

}*Stack;

int EmptyStack(StackList*Stack)//判断是否为空栈

{

if(Stack->top==0)

return 0;

else

return 1;

}

int Move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//分别表示向东、西、南、北需要加上的坐标

int Mase[LENGTH][LENGTH]={0};//初始化为0

int length,width;

void InitMase()//在迷宫的外围添加一层“墙壁”（赋值为1），使得迷宫的任意一点都有四个方向

{

int i,j;

for(i=0;i

{

for(j=0;j

Mase[i][j]=1;

}

for(i=0;i

{

for(j=0;j

Mase[j][i]=1;

}

}

void InitStack(StackList*Stack)//初始化

{

Stack->top=0;

return;

}

int PushStack(StackList*Stack,SEAT CurSeat)//进栈

{

if(Stack->top==MAXSIZE-1)

return false;

else

{

Stack->stack[Stack->top].x=CurSeat.x;

Stack->stack[Stack->top].y=CurSeat.y;

Stack->stack[Stack->top].di=CurSeat.di;

Stack->top++;

return true;

}

}

int PopStack(StackList*Stack)//出栈

{

if(Stack->top==0)

return false;

else

{

Stack->top--;

return true;

}

}

int Pass(SEAT p)//判断当前是否可行

{

if(Mase[p.x][p.y]==0)

{

return true;

}

else

return false;

}

SEAT NextSeat(SEAT CurSeat)//查找下一个点，并返回

{

SEAT temp;

temp.x=CurSeat.x+Move[CurSeat.di][0];

temp.y=CurSeat.y+Move[CurSeat.di][1];

return temp;

}

void Mark(SEAT p)//标记已经走过的点，避免重复

{

Mase[p.x][p.y]=-1;

}

int PathWay(SEAT start,SEAT end)//找路线

{

Stack=(struct StackList*)malloc(sizeof(struct StackList));

InitStack(Stack);

SEAT CurSeat;

CurSeat.x=start.x+1;//由于多加了一层墙壁，因此坐标的值要加1

CurSeat.y=start.y+1;//

CurSeat.di=start.di;//

do

{

if(Pass(CurSeat))

{

PushStack(Stack,CurSeat);

Mark(CurSeat);

if(CurSeat.x==end.x+1&&CurSeat.y==end.y+1)//如果找到出口，返回{

return true;

}

else

{

int find=0;

while(CurSeat.di<3&&find==0)//找下一个结点的方向

{

CurSeat.di++;

SEAT temp;

temp=NextSeat(CurSeat);

if(Mase[temp.x][temp.y]==0)

{

temp.di=-1;

CurSeat=temp;

find =1;

}

}

}

}

else

{

if(EmptyStack(Stack))//当前的点不能走，出栈

PopStack(Stack);

if(EmptyStack(Stack))//当前的点变为前一个点

{

CurSeat=Stack->stack[Stack->top-1];

}

while(CurSeat.di==3&&EmptyStack(Stack))////当前的点找不到下一个点，出栈

{

PopStack(Stack);

CurSeat=Stack->stack[Stack->top-1];//当前的点变为前一个点}

if(EmptyStack(Stack))

{

int find=0;

while(CurSeat.di<3&&find==0)////找下一个结点的方向

{

CurSeat.di++;

SEAT temp;

temp=NextSeat(CurSeat);

if(Mase[temp.x][temp.y]==0)

{

temp.di=-1;

CurSeat=temp;

find =1;

}

}

}

}

}while(EmptyStack(Stack));

return false;

}

void PrintStack(StackList*Stack)//输出路线

{

if(Stack->top==0)

printf(“There is no route can be out of the mazen”);

else

{

int i;

for(i=0;itop;i++)

{

if(i!=0)

printf(“->(%d,%d)”,Stack->stack[i].x-1,Stack->stack[i].y-1);

else

printf(“(%d,%d)”,Stack->stack[i].x-1,Stack->stack[i].y-1);

}

}

}

void PrintMase()//输出迷宫

{

int i,j;

for(i=1;i

{

for(j=1;j

{

if(j!=1)

printf(“ %d”,Mase[i][j]);

else

printf(“%d”,Mase[i][j]);

}

printf(“n”);

}

}

int main()

{

int n;

SEAT start,end;

printf(“Please enter the maze of the length and width:n”);

scanf(“%d%d”,&length,&width);

printf(“Please enter the number of the maze wall unit(0

printf(“Please enter the labyrinth of the coordinates of the wall unit(0<=row,column):n”);while(--n>=0)

{

int x,y;

scanf(“%d%d”,&x,&y);

Mase[x+1][y+1]=1;

}

InitMase();

PrintMase();

printf(“Please enter the coordinates entrance(0<=x<%d,0<=y<%d):n”,length,width);

scanf(“%d%d”,&start.x,&start.y);

start.di=-1;

printf(“Please enter the coordinates exports(0<=x<%d,0<=y<%d):n”,length,width);

scanf(“%d%d”,&end.x,&end.y);

end.di=0;

if(PathWay(start,end))

PrintStack(Stack);

else

printf(“There is no route can be out of the mazen”);return 0;

} of the of the maze maze

第三篇：数据结构实验报告(报告+C语言源代码)

目录

前言..................................................................................................................2 概要设计..................................................................................................................3 1.1 数据结构设计...........................................................................................3 2.1 算法设计...................................................................................................3 2.1.1 建立链表的算法..............................................................................3 2.1.2 链表插入一个元素的算法..............................................................3 2.1.3 链表删除一个元素的算法..............................................................3 3.1 ADT描述..................................................................................................4

4.1

详细设计…………………………………………… ……………………………… 4

4.1.1

数据存储结构……………………………… ……………………………… 4.4.1.2

主要伪代码…… …………………… ……………………………………… 4 软件测试..................................................................................................................7 心得体会................................................................................................................11 源代码...................................................................................................................12 参考文献………………………………………………………………………...21

前言

数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。

随着计算机科学的技术和发展，计算机的功能和运算速度不断地提高，其应用于信息处理的范围日益扩大。与之相应的，计算机的加工处理对象也从简单的数据发展到一般的符号，进而发展到更复杂的数据结构。数据结构是计算机程序设计的重要理论技术基础，数据结构的表示和操作都涉及到算法，如何描述数据的结构和讨论有关的算法，又涉及到程序设计语言。因此，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。我们通过对这门基础课程的学习，要学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适合的逻辑结构，储存结构及其相应的算法，并初步掌握算法时间分析和空间分析的技术。通过实际操作去了解数据结构原理，练习编写代码的能力，以及抽象能力。

从课程性质上讲，“数据结构”是一门专业技术基础课。它的要求是学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读，符合软件工程的规范。

概要设计

1.1 数据结构设计

采用链式储存结构。typedef struct LNode{ ElemType data;struct LNode *next;}LNode,*LinkList;2.1 算法设计

2.1.1 建立链表的算法

（1）算法思想分析

首先从表尾到表头逆向建立单链表,然后再建立的单链表基础上进行对链表上的元素进行查询,删除,插入的操作。（2）要点描述

首先建立一个带头结点的单链表，通过申请内存，先建立一个空链表。然后结点的插入，建立一个有多个结点的链表。在进行查询等操作。（3）时间和空间复杂度分析

程序的时间复杂度为O(n)。

2.1.2 链表插入一个元素的算法

（1）算法思想分析

要生成一个新数据域为X的结点，然后插入在单链表中。（2）要点描述

在链表中插入结点只需要修改指针。若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。

（3）时间和空间复杂度分析

时间复杂度O(n)2.1.3 链表删除一个元素的算法

（1）算法思想分析

要删除一个结点，必须修改指针并且释放空间。（2）要点描述

找到线性表中第i-1个结点，修改其指向后继的指针。

（3）时间和空间复杂度分析

时间复杂度O(n)

3.1 ADT描述

ADT LinkList{

数据对象：D={ e | e∈LNode }

数据关系：R1={ | e∈LNode ,e >0}

基本操作：

GreateList_L(&L, n)

操作结果：构造了一个长为n的数据链表

ListDelete_L(&L, i, &e)

初始条件：链表L已存在而且非空

操作结果：删除L的第i个数据，并且用e返回其值

ListInsert_L(&L, i, e)

初始条件：链表L已存在

操作结果： 在L的第i个位置插入数据e

GetElem(L, i, e)

初始条件：链表L已存在

操作结果：用e返回L中的第i个数据 }ADT LinkList

4.1

详细设计 4.1.1数据存储结构设计

采用单链式线性表实现

4.1.2

主要伪代码

Status GetElem(LinkList L, int i, ElemType *e){ int j=0;int d;LinkList p = L;while(p&&jnext;j++;

} if(!p || j > i)return ERROR;printf(“您要查询的元素是:n”);d=p->data;printf(“%d”,d);printf(“n”);}

void InitList(LinkList *L){ *L =(LinkList)malloc(sizeof(struct LNode));if(!*L)exit(OVERFLOW);(*L)->next = NULL;}

Status ListInsert(LinkList L, int i, ElemType e){ int j = 0;LinkList p = L, s;while(p && j < i-1){ p = p->next;j++;} if(!p|| j > i-1)return ERROR;s =(LinkList)malloc(sizeof(struct LNode));s->data = e;s->next = p->next;p->next = s;return OK;}

Status ListDelete(LinkList L, int i, ElemType *e){ int j = 0;LinkList p = L, q;while(p->next && j < i-1){ p = p->next;

j++;} if(!p->next || j > i-1)return ERROR;q = p->next;p->next = q->next;*e = q->data;free(q);return OK;}

void ListTraverse(LinkList L, void(*vi)(ElemType)){ LinkList p = L->next;while(p){ vi(p->data);p = p->next;} printf(“n”);}

void ListPrint(LinkList L){ LinkList p = L->next;while(p){ printf(“%d ”, p->data);p = p->next;} printf(“n”);}

void printInt(int data){ printf(“%d ”, data);}.软件测试

图一(主界面)

图二(插入学生信息)

图三(显示所有学生信息)

图四(查询个人信息)

图五(统计信息)

图六(修改信息)

图七(保存数据)

图八(删除信息)

心得体会

通过本程序的设计，我对数据结构作了以下总结：要解决一道程序题必须先要认真捕捉改程序中的有用信息，找出解决方法。先规划好，程序需要什么样的数据结构，什么函数，对程序有什么要求。然后从整体把握对程序设计进行分工，相应地把程序分成若干模块，具体实现各部分实行相应的功能。一个程序要顺利地进行设计，一是要对程序的功能有全面的了解，如果漏了某些部分，都会使得这个程序调试不出来或者是令该程序没有达到预想的效果。其次，在程序的编译中，必须注重程序设计过程中的细节，像单链表的程序，就要理解链表的概念，理解链表的数据特点，要清楚知道数据域和指针域的作用，否则，很容易会浪费大量时间在检测错误上面。要说到解题的思考方向，如果要总结成规律，我认为要灵活的进行方法的设计，通过不同的方法来实现不同的功能，如通过结点的插入来实现链表的创建。同时应该注意各种语句的选择，要先预想好需要什么样的语句来实现函数定义，尽量简单快捷地完成，避免出错。

要规范面向对象程序设计师的书写协管，在这次课程设计中，我们再次感受到，规范的程序书写，可以更好的进行后期的差错补漏。还应该注意各种面向对象语言语法的运用，例如继承的方法，都要严格按照语法来进行，否则很容易就会出现错误，甚至严重影响课程设计的进度。

源代码

#include “stdio.h” #include “stdlib.h” #include “string.h” int shoudsave=0;// struct student {

char num[10];//学号

char name[20];

char sex[4];

int cgrade;

int mgrade;

int egrade;

int totle;

int ave;

char neartime[10];//最近更新时间

};

typedef struct node {

struct student data;

struct node *next;}Node,*Link;

int menu(){

char m[3];

int n;

printf(“ ************************欢迎进入学生成绩管理系统******************************nn”);

printf(“t欢迎使用本学生管理系统，本系统将为您提供历史学生信息查询，学生成绩信息管理功能。n”);

printf(“********************************************************************************”);

printf(“t1输入学生资料ttttt2删除学生资料n”);

printf(“t3查询学生资料ttttt4修改学生资料n”);

printf(“t5显示学生资料ttttt6统计学生成绩n”);

printf(“t7保存学生资料n”);

printf(“ttplease choose a operation(1-7):n”);

printf(“***********************************************************************

*********n”);

scanf(“%s”,m);

n=atoi(m);

return(n);}

void printstart(){

printf(“---------n”);}

void Wrong(){

printf(“n=====>提示:输入错误!n”);}

void Nofind(){

printf(“n=====>提示:没有找到该学生!n”);}

void printc()// 本函数用于输出中文

{

printf(“学号t 姓名

性别

英语成绩 数据库成绩 数据结构成绩

总分平均分n”);}

void printe(Node *p)//本函数用于输出英文

{

printf(“%-12s%stt%st%dtt%dt%dt%dt %dn”,p->data.num,p->data.name,p->data.sex,p->data.egrade,p->data.mgrade,p->data.cgrade,p->data.totle,p->data.ave);}

Node* Locate(Link l,char findmess[],char nameornum[])//该函数用于定位连表中符合要求的接点，并返回该指针

{

Node *r;

if(strcmp(nameornum,“num”)==0)//按学号查询

{

r=l->next;

while(r!=NULL)

{

if(strcmp(r->data.num,findmess)==0)

return r;

r=r->next;

}

}

else if(strcmp(nameornum,“name”)==0)//按姓名查询

{

r=l->next;

while(r!=NULL)

{

if(strcmp(r->data.name,findmess)==0)

return r;

r=r->next;

}

}

return 0;}

void Add(Link l)//增加学生

{

Node *p,*r,*s;

char num[10];

r=l;

s=l->next;

while(r->next!=NULL)

r=r->next;//将指针置于最末尾

while(1)

{

printf(“请你输入学号(以'0'返回上一级菜单:)”);

scanf(“%s”,num);

if(strcmp(num,“0”)==0)

break;

while(s)

{

if(strcmp(s->data.num,num)==0)

{

printf(“=====>提示:学号为'%s'的学生已经存在,若要修改请你选择'4 修改'!n”,num);

printstart();

printc();

printe(s);

printstart();

printf(“n”);

return;

}

s=s->next;

}

p=(Node *)malloc(sizeof(Node));

strcpy(p->data.num,num);

printf(“请你输入姓名:”);

scanf(“%s”,p->data.name);

getchar();

printf(“请你输入性别:”);

scanf(“%s”,p->data.sex);

getchar();

printf(“请你输入数据结构成绩:”);

scanf(“%d”,&p->data.cgrade);

getchar();

printf(“请你输入数据库成绩:”);

scanf(“%d”,&p->data.mgrade);

getchar();

printf(“请你输入英语成绩:”);

scanf(“%d”,&p->data.egrade);

getchar();

p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade;

p->data.ave=p->data.totle / 3;

//信息输入已经完成p->next=NULL;

r->next=p;

r=p;

shoudsave=1;

} }

void Qur(Link l)//查询学生

{

char findmess[20];

Node *p;

if(!l->next)

{

printf(“n=====>提示:没有资料可以查询!n”);

return;

}

printf(“请你输入要查找的学号:”);

scanf(“%s”,findmess);

p=Locate(l,findmess,“num”);

if(p)

{

printf(“tttt查找结果n”);

printstart();

printc();

printe(p);

printstart();

}

else

Nofind();}

void Del(Link l)//删除

{

Node *p,*r;

char findmess[20];

if(!l->next)

{

printf(“n=====>提示:没有资料可以删除!n”);

return;

}

printf(“n=====>确定进行删除操作请按 1，按其他按键退出该操作nnnn”);

if(menu()==1)

{

printf(“请你输入要删除的学号:”);

scanf(“%s”,findmess);

p=Locate(l,findmess,“num”);

if(p)

{

r=l;

while(r->next!=p)

r=r->next;

r->next=p->next;

free(p);

printf(“n=====>提示:该学生已经成功删除!n”);

shoudsave=1;

}

else

Nofind();

}

else

exit;}

void Modify(Link l)//修改函数 {

Node *p;

char findmess[20];

if(!l->next)

{

printf(“n=====>提示:没有资料可以修改!n”);

return;

}

printf(“请你输入要修改的学生学号:”);

scanf(“%s”,findmess);

p=Locate(l,findmess,“num”);

if(p)

{

printf(“请你输入新学号(原来是%s):”,p->data.num);

scanf(“%s”,p->data.num);

printf(“请你输入新姓名(原来是%s):”,p->data.name);

scanf(“%s”,p->data.name);

getchar();

printf(“请你输入新性别(原来是%s):”,p->data.sex);

scanf(“%s”,p->data.sex);

printf(“请你输入新的数据结构成绩(原来是%d分):”,p->data.cgrade);

scanf(“%d”,&p->data.cgrade);

getchar();

printf(“请你输入新的数据库成绩(原来是%d分):”,p->data.mgrade);

scanf(“%d”,&p->data.mgrade);

getchar();

printf(“请你输入新的英语成绩(原来是%d分):”,p->data.egrade);

scanf(“%d”,&p->data.egrade);

p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade;

p->data.ave=p->data.totle/3;

printf(“n=====>提示:资料修改成功!n”);

shoudsave=1;

}

else

Nofind();

}

void Disp(Link l)//显示函数 {

int count=0;

Node *p;

p=l->next;

if(!p)

{

printf(“n=====>提示:没有资料可以显示!n”);

return;

}

printf(“tttt显示结果n”);

printstart();

printc();

printf(“n”);

while(p)

{

printe(p);

p=p->next;

}

printstart();

printf(“n”);}

void Tongji(Link l)//统计函数 {

Node *pm,*pe,*pc,*pt,*pa;//用于指向分数最高的接点

Node *r=l->next;

if(!r)

{

printf(“n=====>提示:没有资料可以统计!n”);

return;

}

pm=pe=pc=pt=pa=r;

while(r!=NULL)

{

if(r->data.cgrade>=pc->data.cgrade)

pc=r;

if(r->data.mgrade>=pm->data.mgrade)

pm=r;

if(r->data.egrade>=pe->data.egrade)

pe=r;

if(r->data.totle>=pt->data.totle)

pt=r;

if(r->data.ave>=pa->data.ave)

pa=r;

r=r->next;

}

printf(“------------------------------统计结果-n”);

printf(“总分最高者:t%s %d分n”,pt->data.name,pt->data.totle);

printf(“平均分最高者:t%s %d分n”,pa->data.name,pa->data.ave);

printf(“英语最高者:t%s %d分n”,pe->data.name,pe->data.egrade);

printf(“数据库最高者:t%s %d分n”,pm->data.name,pm->data.mgrade);

printf(“数据结构最高者:t%s %d分n”,pc->data.name,pc->data.cgrade);

printstart();}

void Save(Link l)//保存函数 {

FILE* fp;

Node *p;

int flag=1,count=0;

fp=fopen(“c:student”,“wb”);

if(fp==NULL)

{

printf(“n=====>提示:重新打开文件时发生错误!n”);

exit(1);

}

p=l->next;

while(p)

{

if(fwrite(p,sizeof(Node),1,fp)==1)

{

p=p->next;

count++;

}

else

{

flag=0;

break;

}

}

if(flag)

{

printf(“n=====>提示:文件保存成功.(有%d条记录已经保存.)n”,count);

shoudsave=0;

}

fclose(fp);}

void main(){

Link l;//连表

FILE *fp;//文件指针

char ch;

char jian;

int count=0;

Node *p,*r;

l=(Node*)malloc(sizeof(Node));

l->next=NULL;

r=l;

fp=fopen(“C:student”,“rb”);

if(fp==NULL)

{

fp=fopen(“C:student”,“wb”);

exit(0);

}

printf(“n=====>提示:文件已经打开,正在导入记录......n”);

while(!feof(fp))

{

p=(Node*)malloc(sizeof(Node));

if(fread(p,sizeof(Node),1,fp))//将文件的内容放入接点中

{

p->next=NULL;

r->next=p;

r=p;//将该接点挂入连中

count++;

}

}

fclose(fp);//关闭文件

printf(“n=====>提示:记录导入完毕,共导入%d条记录.n”,count);

for(;;)

{

switch(menu())

{

case 1:Add(l);break;//增加学生

case 2:Del(l);break;//删除学生

case 3:Qur(l);break;//查询学生

case 4:Modify(l);break;//修改学生

case 5:Disp(l);break;//显示学生

case 6:Tongji(l);break;//统计学生

case 7:Save(l);break;//保存学生

default: Wrong();

getchar();

break;

}

}

}

参考文献

《数据结构（C语言版）》----------------清华大学出版社 严蔚敏 吴伟民 编著 《C语言程序设计》------------------------中国铁道出版社 丁峻岭 余坚 编著

第四篇：C语言数据结构与指针

数据结构【第四次】实验报告

学院：

班级：

学号：

姓名：

实验四

（一）实验名称：C语言数据结构与指针

（二）实验目的：巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。

（三）实验内容：

1)学生信息的显示，具体要求如下：

定义一个结构体描述学生信息(学号，姓名，性别，年龄，住址)；

设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型；

设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于5人）。

2)输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元素值。要求用指针和动态内存分配方法实现。例如 输入：10 2 30 4 5，逆置后显示为：5 4 30 2 10。

（四）源代码：

#define MAXSIZE 100

#include #include typedef int ElemType;typedef struct {

ElemType data[MAXSIZE];int length;

} SqList;SqList l;

void InitList(SqList &L)

{

L.length = 0;} void CreatSqlist(SqList &L,int n)

{

printf(“请输入节点”);int i;for(i=0;i

} void Output(SqList &L)

{ int i;for(i=0;i

printf(“n”);} int chazhao(SqList &L,int x){ int i,k;printf(“n请输入你要查找的元素 x=?”);scanf(“%d”,&x);for(i=0;i<=(L.length+1);i++){

if(x==L.data[i])

{printf(“要查找的元素%d位于线性表第%d位上nn”,x,i+1);

k=0;

break;

} } if(k!=0)printf(“所要查找的元素%d不在线性表中”,x);return 0;} int GET(SqList &L,int i){ int m;if((i<0)||(i>L.length)){printf(“所查找范围超出线性表长度”);return 1;} else if((i>=1)&&(i<=L.length)){

m=L.data[i-1];}printf(“%d ”,m);return 0;} int DELETE(SqList &L,int i){ int j;if(i<1||i>L.length){printf(“删除错误”);return 0;} else {

for(j=i;j

L.data[j-1]=L.data[j];

L.length--;

} return 1;} int INSERT(SqList &L,int x,int i){ int j;if(L.length>=MAXSIZE-1){printf(“over flow”);return 1;} else if((i<1)||(i>L.length+1)){printf(“插入错误”);return 1;} else

{for(j=L.length;j>=i-1;j--)L.data[j+1]=L.data[j];L.data[i-1]=x;L.length=L.length+1;} return 0;} int main(){int n,i,k,x;InitList(l);printf(“请输入线性表的长度 ”);scanf(“%d”,&n);CreatSqlist(l,n);Output(l);

printf(“请输入你要查找的数所在的节点位置”);scanf(“%d”,&i);GET(l,i);chazhao(l,x);printf(“请输入你要删除元素的位置=?”);scanf(“%d”,&k);DELETE(l,k);Output(l);printf(“请输入你要插入的数和位置x,i=?”);scanf(“%d,%d”,&x,&i);INSERT(l,x,i);Output(l);return 0;}

（五）代码运行结果：

（六）需求分析

1、输入的形式和输出值的范围：1）输入10个整数。2）输出整个顺序线性表。

2、输出的形式：完成各种功能后的线性表。

3、程序所能达到的功能：1）所存储顺序线性表的显示、元素的查找、删除和插入。

（七）所用到的函数：

void CreatSqlist void Output Int chazhao int GET int INSERT int DELETE

（八）心得体会：

此次实验的过程中还是遇到了很多意想不到的问题，让我再一次深刻的体会到了理论和实践的差距。使我清楚的知道技术上的东西，细节更显得尤为重要和值得重视。困难虽有，但在我的努力下，最后还是成功完成了实验。总而言之，这次实验又增长了我不好知识。

第五篇：c数据结构实验报告

c数据结构实验报告

数据结构(C语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____XX40703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;XX年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目

数据结构(C语言版)实验报告

专业：计算机科学与技术、软件工程

学号:____XX40703061___________________

班级:_________软件二班______________

姓名:________朱海霞______________

指导教师:___刘遵仁________________

青岛大学信息工程学院

XX年10月

实验1

实验题目：顺序存储结构线性表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。

实验主要步骤：

1、分析、理解给出的示例程序。

2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。

程序代码:

#include

#include

#define OK 1

#define ERROR 0

#define OVERFLOW-2

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

typedef struct{

int* elem;

int length;

int listsize;

}Sqlist;

int InitList_Sq(Sqlist &L){

=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!)return-1;

=0;

=LIST_INIT_SIZE;

return OK;

}

int ListInsert_Sq(Sqlist&L,int i,int e){

if(i+1)return ERROR;

if(==){

int *newbase;

newbase=(int*)realloc(,(+LISTINCREMENT)*sizeof(int));

if(!newbase)return-1;

=newbase;

+=LISTINCREMENT;

}

int *p,*q;

q=&();

for(p=&();p>=q;--p)

*(p+1)=*p;

*q=e;

++;

return OK;

}

int ListDelete_Sq(Sqlist &L,int i,int e){

int *p,*q;

if(i)return ERROR;

p=&();

e=*p;

q=+;

for(++p;p *(p-1)=*p;

--;

return OK;

}

int main(){

Sqlist L;

InitList_Sq(L);//初始化

int i,a={3,-5,6,8,2,-5,4,7,-9};

for(i=1;i ListInsert_Sq(L,i,a);

for(i=0;i printf(“ %d”,);

printf(“ ”);//插入9个数

ListInsert_Sq(L,3,24);

for(i=0;i printf(“ %d”,);

printf(“ ”);//插入一个数

int e;

ListDelete_Sq(L,2, e);

for(i=0;i printf(“ %d”,);//删除一个数

printf(“ ”);

return 0;

}

实验结果：

3，-5,6,8,2，-5,4,7，-9

3，-5,24,6,8,2，-5,4,7，-9

3,24,6,8,2，-5,4,7，-9

心得体会：

顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结构简单，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享 实验2

实验题目：单链表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符;根据输入的字符，先找到相应的结点，后删除之。

实验主要步骤：

3、分析、理解给出的示例程序。

4、调试程序，并设计输入数据(如：A，C，E，F，H，J，Q，M)，测试程序的如下功能：不允许重复字符的插入;根据输入的字符，找到相应的结点并删除。

5、修改程序：

(1)增加插入结点的功能。

(2)建立链表的方法有“前插”、“后插”法。

程序代码:

#include

#include

#define NULL 0

#define OK 1

#define ERROR 0

typedef struct LNode{

int data;

struct LNode *next;

}LNode,*LinkList;

int InitList_L(LinkList &L){

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;

return OK;

} int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s;

int j;

p=L;j=0;

while(p&&j

p=p->next;++j;

}

if(!p||j>i-1)

return ERROR;

s=(LinkList)malloc(sizeof(LNode));s->data=e;

s->next=p->next;

p->next=s;

return OK;

} int

ListDelete_L(LinkList&L,int

i,int &e){ LinkList p,q;

int j;

p=L;j=0;

while(p->next&&j

p=p->next;++j;

}

if(!(p->next)||j

return ERROR;

q=p->next;p->next=q->next;e=q->data;free(q);

return OK;

}

int main(){

LinkList L,p;

char a={'A','C','E','F','H','J','Q','U'};int i,j;

InitList_L(L);

for(i=1,j=0;i p=L->next;

while(p!=NULL){

printf(“%c ”,p->data);p=p->next;}//插入八个字符

printf(“;实验结果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通过扫描指针P进行单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：;

1、掌握栈的顺序存储结构和链式存储结构，以便在实;

2、掌握栈的特点，即后进先出和先进先出的原则;

3、掌握栈的基本运算，如：入栈与出栈

}

}//插入八个字符 printf(” “);i=2;int e;ListInsert_L(L,i,'B');

p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;}//插入一个字符 printf(” “);i=3;ListDelete_L(L,i,e);p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;} printf(” “);return 0;

实验结果：

A C E F H J Q U

A B C E F H J Q U

A B E F H J Q U

心得体会：

单链表是通过扫描指针P进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。

实验3

实验题目：栈操作设计和实现

实验目的：

1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈的特点，即后进先出和先进先出的原则。

3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。

实验要求：

回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如

“abba”是回文，而“abab”不是回文。

实验主要步骤

(1)数据从键盘读入;

(2)输出要判断的字符串;

(3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。

程序代码:

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW-2

#define N 100

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct{

int *base;// 在栈构造之前和销毁之后，base的值为NULL int *top;// 栈顶指针

int stacksize;// 当前已分配的存储空间，以元素为单位

} SqStack;

int InitStack(SqStack &S)

{ // 构造一个空栈S

if(!(=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))

exit(OVERFLOW);// 存储分配失败

=;

=STACK_INIT_SIZE;

return OK;

}

int StackEmpty(SqStack S)

{ // 若栈S为空栈，则返回TRUE，否则返回FALSE

if(==)

return TRUE;

else

return FALSE;

}

int Push(SqStack &S, int e)

{ // 插入元素e为新的栈顶元素

if(>=)// 栈满，追加存储空间

{

=(int *)realloc(,(+STACKINCREMENT)*sizeof(int));if(!)

exit(OVERFLOW);// 存储分配失败

=+;

+=STACKINCREMENT;

}

*()++=e;

return OK;

}

int Pop(SqStack &S,int &e)

{ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(==)

return ERROR;

e=*--;

return OK;

}

int main(){

SqStack s;

int i,e,j,k=1;

char ch = {0},*p,b = {0};

if(InitStack(s))// 初始化栈成功

{

printf(”请输入表达式: “);

gets(ch);

p=ch;

while(*p)// 没到串尾

Push(s,*p++);

for(i=0;i

if(!StackEmpty(s)){// 栈不空

Pop(s,e);// 弹出栈顶元素

b=e;

}

}

for(i=0;i

if(ch!=b)

k=0;

}

if(k==0)

printf(”NO!“);

else

printf(”输出:“)

printf(”YES!“);

}

return 0;

}

实验结果：

请输入表达式：

abcba

输出：YES!

心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。

实验4

实验题目：二叉树操作设计和实现

实验目的：

掌握二叉树的定义、性质及存储方式，各种遍历算法。

实验要求：

采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

实验主要步骤：

1、分析、理解程序。

2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)，如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

程序代码:

实验结果：

心得体会：

实验5

实验题目：图的遍历操作

实验目的：

掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。

实验要求：

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。

实验主要步骤：

设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。

1.邻接矩阵作为存储结构

#include”“

#include”“

#define MaxVertexNum 100 //定义最大顶点数

typedef struct{

char vexs;//顶点表

int edges;//邻接矩阵，可看作边表 int n,e;//图中的顶点数n和边数e

}MGraph;//用邻接矩阵表示的图的类型

//=========建立邻接矩阵=======

void CreatMGraph(MGraph *G)

{

int i,j,k;

char a;

printf(”Input VertexNum(n)and EdgesNum(e): “);

scanf(”%d,%d“,&G->n,&G->e);//输入顶点数和边数

scanf(”%c“,&a);

printf(”Input Vertex string:“);

for(i=0;in;i++)

{

scanf(”%c“,&a);

G->vexs=a;//读入顶点信息，建立顶点表

}

for(i=0;in;i++)

for(j=0;jn;j++)

G->edges=0;//初始化邻接矩阵

printf(”Input edges,Creat Adjacency Matrix “);

for(k=0;ke;k++){ //读入e条边，建立邻接矩阵

scanf(”%d%d“,&i,&j);//输入边(Vi，Vj)的顶点序号

G->edges=1;;G->edges=1;//若为;//=========定义标志向

量，为

全

局

变

量=;typedefenum{FALSE,TRUE}B;Booleanvisited=1;

G->edges=1;//若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 }

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited;

//========DFS：深度优先遍历的递归算法======

void DFSM(MGraph *G,int i)

{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵

给出你的编码

//===========BFS：广度优先遍历=======

void BFS(MGraph *G,int k)

{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索

给出你的编码

//==========主程序main =====

void main()

{

int i;

MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph));//为图G请内存空间

CreatMGraph(G);//建立邻接矩阵

printf(”Print Graph DFS: “);

DFS(G);//深度优先遍历

printf(” “);

printf(”Print Graph BFS: “);

BFS(G,3);//以序号为3的顶点开始广度优先遍历

printf(” “);

}

2.邻接链表作为存储结构

#include”“

#include”“

#define MaxVertexNum 50 //定义最大顶点数

typedef struct node{ //边表结点

int adjvex;//邻接点域

struct node *next;//链域

申

}EdgeNode;

typedef struct vnode{ //顶点表结点

char vertex;//顶点域

EdgeNode *firstedge;//边表头指针

}VertexNode;

typedef VertexNode AdjList;//AdjList是邻接表类型 typedef struct {

AdjList adjlist;//邻接表

int n,e;//图中当前顶点数和边数

} ALGraph;//图类型

//=========建立图的邻接表=======

void CreatALGraph(ALGraph *G)

{

int i,j,k;

char a;

EdgeNode *s;//定义边表结点

printf(”Input VertexNum(n)and EdgesNum(e): “);

scanf(”%d,%d“,&G->n,&G->e);//读入顶点数和边数

scanf(”%c“,&a);

printf(”Input Vertex string:“);

for(i=0;in;i++)//建立边表

{

scanf(”%c“,&a);

G->adjlist.vertex=a;//读入顶点信息

G->adjlist.firstedge=NULL;//边表置为空表

}

printf(”Input edges,Creat Adjacency List “);

for(k=0;ke;k++){ //建立边表

scanf(”%d%d“,&i,&j);//读入边(Vi，Vj)的顶点对序号

s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成边表结点

s->adjvex=j;//邻接点序号为j

s->next=G->adjlist.firstedge;

G->adjlist.firstedge=s;//将新结点*S插入顶点Vi的边表头部

s=(EdgeNode *)malloc(sizeof(EdgeNode));

s->adjvex=i;//邻接点序号为i

s->next=G->adjlist.firstedge;

G->adjlist.firstedge=s;//将新结点*S插入顶点Vj的边表头部

}

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited;

//========DFS：深度优先遍历的递归算法======

void DFSM(ALGraph *G,int i)

{ //以Vi为出发点对邻接链表表示的图G进行DFS搜索

给出你的编码

//==========BFS：广度优先遍历=========

void BFS(ALGraph *G,int k)

{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索

给出你的编码

//==========主函数===========

void main()

{

int i;

ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph));

CreatALGraph(G);

printf(”Print Graph DFS: “);

DFS(G);

printf(” “);

printf(”Print Graph BFS: “);

BFS(G,3);

printf(” ");

}

实验结果：

1.邻接矩阵作为存储结构

2.邻接链表作为存储结构

心得体会：

实验6

实验题目：二分查找算法的实现

实验目的：

掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。

实验要求：

编写程序构造一个有序表L，从键盘接收一个关键字key，用二分查找法在L中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。

实验主要步骤：

1.建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。

2.给出算法的递归和非递归代码;

3.如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性?

程序代码

实验结果：

心得体会：

实验7

实验题目：排序

实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

实验要求：

实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。

实验主要步骤：

程序代码

实验结果：

心得体会：