第一篇:数据结构(C语言版)实验报告格式
姓名:学号:实验日期:
实验<实验序号>
<题号>、<题目内容>
算法思路:<算法的主要实现方法和主要数据结构的实现方法>
算法描述:<算法描述内容>
算法分析:<算法的时间复杂度>(要说明基本操作是什么)
数据分析:<输入数据>+<输出数据>
……
第二篇: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
实验题目:排序
实验目的:
掌握各种排序方法的基本思想、排序过程、算法实现,能进行时间和空间性能的分析,根据实际问题的特点和要求选择合适的排序方法。
实验要求:
实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。
实验主要步骤:
程序代码
实验结果:
心得体会:
第三篇:数据结构实验报告(报告+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={
基本操作:
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语言版)实验报告
专业:计算机科学与技术、软件工程
学号:____201240703061___________________
班级:_________软件二班______________ 姓名:________朱海霞______________ 指导教师:___刘遵仁________________
青岛大学信息工程学院
2013年10月
实验1
实验题目:顺序存储结构线性表的插入和删除
实验目的:
了解和掌握线性表的逻辑结构和顺序存储结构,掌握线性表的基本算法及相关的时间性能分析。
实验要求:
建立一个数据域定义为整数类型的线性表,在表中允许有重复的数据;根据输入的数据,先找到相应的存储单元,后删除之。
实验主要步骤:
1、分析、理解给出的示例程序。
2、调试程序,并设计输入一组数据(3,-5,6,8,2,-5,4,7,-9),测试程序的如下功能:根据输入的数据,找到相应的存储单元并删除,显示表中所有的数据。
程序代码:
#include
int *newbase;
newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase)return-1;
L.elem=newbase;
L.listsize+=LISTINCREMENT;} int *p,*q;q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1)=*p;*q=e;++L.length;return OK;} int ListDelete_Sq(Sqlist &L,int i,int e){ int *p,*q;if(i<1||i>L.length)return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)
*(p-1)=*p;--L.length;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<10;i++)
ListInsert_Sq(L,i,a[i-1]);for(i=0;i<9;i++)
printf(“ %d”,L.elem[i]);
printf(“n”);//插入9个数
ListInsert_Sq(L,3,24);for(i=0;i<10;i++)
printf(“ %d”,L.elem[i]);
printf(“n”);//插入一个数
int e;ListDelete_Sq(L,2, e);for(i=0;i<9;i++)
printf(“ %d”,L.elem[i]);//删除一个数
printf(“n”);
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
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[8]={'A','C','E','F','H','J','Q','U'};int i,j;InitList_L(L);for(i=1,j=0;i<=8,j<8;i++,j++) ListInsert_L(L,i,a[j]);p=L->next;while(p!=NULL){ printf(“%ct”,p->data); p=p->next; } }//插入八个字符 printf(“n”);i=2;int e;ListInsert_L(L,i,'B');p=L->next;while(p!=NULL){ printf(“%ct”,p->data);p=p->next;}//插入一个字符 printf(“n”);i=3;ListDelete_L(L,i,e);p=L->next;while(p!=NULL){ printf(“%ct”,p->data);p=p->next;} printf(“n”);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 #define STACKINCREMENT 10 typedef struct{ int *base; // 在栈构造之前和销毁之后,base的值为NULL int *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间,以元素为单位 } SqStack; int InitStack(SqStack &S){ // 构造一个空栈S if(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)))) exit(OVERFLOW); // 存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackEmpty(SqStack S){ // 若栈S为空栈,则返回TRUE,否则返回FALSE if(S.top==S.base) return TRUE; else return FALSE;} int Push(SqStack &S, int e){ // 插入元素e为新的栈顶元素 if(S.top-S.base>=S.stacksize)// 栈满,追加存储空间 { S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) exit(OVERFLOW);// 存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *(S.top)++=e; return OK;} int Pop(SqStack &S,int &e){ // 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR if(S.top==S.base) return ERROR; e=*--S.top; return OK;} int main(){ SqStack s; int i,e,j,k=1; char ch[N] = {0},*p,b[N] = {0}; if(InitStack(s))// 初始化栈成功 { printf(“请输入表达式:n”); gets(ch); p=ch; while(*p)// 没到串尾 Push(s,*p++); for(i=0;i if(!StackEmpty(s)){// 栈不空 Pop(s,e);// 弹出栈顶元素 b[i]=e; } } for(i=0;i if(ch[i]!=b[i]) 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“stdio.h” #include“stdlib.h” #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵,可看作边表 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;i { scanf(“%c”,&a); G->vexs[i]=a; //读入顶点信息,建立顶点表 } for(i=0;i for(j=0;j G->edges[i][j]=0; //初始化邻接矩阵 printf(“Input edges,Creat Adjacency Matrixn”); for(k=0;k //读入e条边,建立邻接矩阵 scanf(“%d%d”,&i,&j); //输入边(Vi,Vj)的顶点序号 G->edges[i][j]=1; G->edges[j][i]=1;//若为无向图,矩阵为对称矩阵;若建立有向图,去掉该条语句 } } //=========定义标志向量,为全局变量======= typedef enum{FALSE,TRUE} Boolean;Boolean visited[MaxVertexNum];//========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(“n”); printf(“Print Graph BFS: ”); BFS(G,3); //以序号为3的顶点开始广度优先遍历 printf(“n”);} 2. 邻接链表作为存储结构 #include“stdio.h” #include“stdlib.h” #define MaxVertexNum 50 //定义最大顶点数 typedef struct node{ //边表结点 int adjvex; //邻接点域 struct node *next; //链域 }EdgeNode;typedef struct vnode{ //顶点表结点 char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 }VertexNode;typedef VertexNode AdjList[MaxVertexNum]; //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;i //建立边表 { scanf(“%c”,&a);G->adjlist[i].vertex=a; //读入顶点信息 G->adjlist[i].firstedge=NULL;//边表置为空表 } printf(“Input edges,Creat Adjacency Listn”); for(k=0;k //建立边表 scanf(“%d%d”,&i,&j); //读入边(Vi,Vj)的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点 s->adjvex=j; //邻接点序号为j s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i; //邻接点序号为i s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部 } } //=========定义标志向量,为全局变量======= typedef enum{FALSE,TRUE} Boolean;Boolean visited[MaxVertexNum];//========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(“n”); printf(“Print Graph BFS: ”); BFS(G,3); printf(“n”);} 实验结果: 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 实验题目:排序 实验目的: 掌握各种排序方法的基本思想、排序过程、算法实现,能进行时间和空间性能的分析,根据实际问题的特点和要求选择合适的排序方法。 实验要求: 实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。 实验主要步骤: 程序代码 实验结果: 心得体会: 学号:__________ 姓名:__________ 班级:__________ 日期:__________ 指导教师:__________ 成绩:__________ 实验一 上机操作初步和简单的C程序设计 一、实验目的1、熟悉C语言运行环境Turbo C++3.02、会简单的程序调试 3、熟悉C语言各种类型数据的输入输出函数的使用方法 4、掌握顺序结构程序设计 二、实验内容 1、上机运行本章3个例题,熟悉所用系统的上机方法与步骤。(习题1.7) 2、编写一个C程序,输入a、b、c 3个值,输出其中最大者。(习题1.6) 3、设圆半径r=1.5,圆柱高h=3,求圆周长、圆面积、圆球表面积、圆球体积、圆柱体积。用scanf输入数据,输出计算结果,输出时要求有文字说明,取小数点后2位数字。注意:在Trubo C++ 3.0中不能输入汉字,只能输入英文或拼音。(习题4.8) 4、运行如下程序,写出运行结果。第一┆范文网www.xiexiebang.com整理该文章,版权归原作者、原出处所有...#include void main() { int a=1,b=2; a=a+b;b=a-b;a=a-b; printf(“%d,%dn”,a,b); } 三、实验步骤与过程 四、程序调试记录第五篇:c语言实验报告