数据结构实验二报告

第一篇：数据结构实验二报告

数据结构实验二报告

——简单计算器

姓名：王稀宾 班 级：06111106 学号：1120111699 一实验目的

按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

二实验内容

要求：

从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。

三程序设计

程序模块：

1输入模块，输入多项式；

2计算模块，根据输入内容，判断分析，计算出结果； 3输出模块，输出计算结果。

定义结构创建结点： typedef struct { double data[50];int top;}OPND_Stack;//运算符结构体 typedef struct { char data[50];int top;}OPTR_Stack;主函数部分： void main(){ char a[80];int m;char b[80];printf(“============简易计算器============n”);printf(“[四则运算.如:-1+(2+3)*9/(-2)-6].n请输入一个表达式:n”);while(1){

gets(a);

strcpy(b,a);

while(1)

{

int p;

m=strlen(a);

p=Can(a,m);

if(p==0)break;

printf(“输入错误.请从新输入表达式:n”);

gets(a);

strcpy(b,a);

}

printf(“=*=*=*=*=*=*表达式结果=*=*=*=*=*=*n”);

printf(“该表达式的结果为:n%s=%-10.3lfn”,b,EvaluateExpression(a));

printf(“=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n”);

printf(“继续使用[四则运算.如:-1+(2+3)*9/(-2)-6].<关闭退出>.n请再输入 一个表达式:n”);} }

四程序调试分析

1在四则混合运算中，运算符号的优先级比较难判断。2心得体会: 我对编程是有很浓厚兴趣的。在编程的过程中，我深深地体会到力不从心—有些知识没能深入地理解和掌握以及VC++的许多功能没能探索和了解使我编程时有好多的思想运用不上(如设计一个美观的操作界面)。另外，我也感受到了数据结构的重要性，有了结构才能将好的思想付诸实践。同时经过查询资料了解到栈由多种运用方法，其中包括栈的顺序存储结构和链式存储结构，栈是计算表达式的经典应用。数据结构中的许多结构都是很经典思想，只有把编程语言和数据结构都熟练掌握的情况下，才能做出一些很好的作品。在编程过程中，虽然有时候是很发闷的，尤其是程序无错但结果不对，但是在完成一个完整的程序时所带来的喜悦是其它事情所不能替代的。我很喜欢编程，即使我的知识和能力有限，但我相信经过努力，一切皆有可能。

五用户使用说明

按要求正确输入表达式即可得到结果。

六程序运行结果 附程序清单

#include #include #include //算符优先级表 char First[7][7]= { //'+','-','*','/','(',')','^' /*'+'*/ '>','>','<','<','<','>','<', /*'-'*/ '>','>','<','<','<','>','<', /*'*'*/ '>','>','>','>','<','>','<', /*'/'*/ '>','>','>','>','<','>','<', /*'('*/ '>','>','>','>','>','>',' >', /*')'*/ '<','<','<','<','< ','>','<', /*'^'*/ '>','>','>','>','<','> ','<' };//运算符数组

char OP[7]={'+','-','*','/','(',')','#'};//数据结构体 typedef struct { double data[50];int top;}OPND_Stack;//运算符结构体 typedef struct

{ char data[50];int top;}OPTR_Stack;//初始化运算符栈函数

void InitStack_R(OPTR_Stack *a){ a->top=-1;} //初始化数据站函数

void InitStack_D(OPND_Stack *a){ a->top=-1;} //运算符进栈函数

void Push_R(OPTR_Stack *a,char b){ a->top++;a->data[a->top]=b;} //数据进栈函数

void Push_D(OPND_Stack *a,double b){ a->top++;a->data[a->top]=b;} //取运算符栈顶符函数

void GetTop_R(OPTR_Stack *a,char *b){ *b=a->data[a->top];} //取数据栈顶数函数

void GetTop_D(OPND_Stack *a,double *b){ *b=a->data[a->top];} //判断数据是否为运算符函数 int In(char a,char *s){ for(int i=0;i<7;i++)

if(a==s[i])

return 1;return 0;} //算符优先级判断函数

char Precede(char a,char b){ int m,n;for(int i=0;i<7;i++){

if(a==OP[i])

m=i;

if(b==OP[i])

n=i;} return First[m][n];} //删除运算符栈顶元素，并取新栈的栈顶元素 void Pop_R(OPTR_Stack *a,char *b){ a->top--;*b=a->data[a->top];} //取数据站的栈顶元素，并从栈中删除此元素 void Pop_D(OPND_Stack *a,double *b){ *b=a->data[a->top];a->top--;} //算符优先算法求值核心函数

double EvaluateExpression(char *s){ OPND_Stack OPND;OPTR_Stack OPTR;char ch,theta;double x,a,b;int k=0;strcat(s,“#”);InitStack_R(&OPTR);Push_R(&OPTR,'#');InitStack_D(&OPND);GetTop_R(&OPTR,&ch);while(s[k]!='#'||ch!='#'){

if(In(s[k],OP)==0)

{

x=Getdouble(s,&k);

Push_D(&OPND,x);

}

else

{

switch(Precede(ch,s[k]))

{

case'<':Push_R(&OPTR,s[k]);

k++;

break;

case'=':Pop_R(&OPTR,&ch);

k++;

break;

case'>':GetTop_R(&OPTR,&theta);Pop_R(&OPTR,&ch);

Pop_D(&OPND,&b);Pop_D(&OPND,&a);

Push_D(&OPND,Operate(a,theta,b));

break;

}

}

GetTop_R(&OPTR,&ch);} GetTop_D(&OPND,&x);return x;InitStack_R(&OPTR);Push_R(&OPTR,'#');InitStack_D(&OPND);} //判断表达式是否输入正确.int Can(char a[],int n){ int p=0,s=0,t=0;for(int i=0;i

if(a[i]=='('||a[i]==')')

p++;

if((a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/')&&((a[i+1]<'0'&&a[i+1]!='(')||a[i+1]>'9'))

s++;

if(a[i]=='/'&&a[i+1]=='0')

s++;

if((a[i]=='('&&(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'))||(a[i]==')'&&a[i+1]=='('))

s++;

if(a[i]==')'&&a[i+1]!=''&&(a[i+1]!='+'&&a[i+1]!='-'&&a[i+1]!='*'&&a[i+1]!='/'))

s++;

if(a[i]=='.'&&a[i+1]=='.')

s++;} if(p%2==0&&s==0)

return 0;return 1;} //主函数 void main(){ char a[80];int m;char b[80];printf(“============简易计算器============n”);printf(“[四则运算.如:-1+(2+3)*9/(-2)-6].n请输入一个表达式:n”);while(1){

gets(a);

strcpy(b,a);

while(1)

{

int p;

m=strlen(a);

p=Can(a,m);

if(p==0)break;

printf(“输入错误.请从新输入表达式:n”);

gets(a);

strcpy(b,a);

}

printf(“=*=*=*=*=*=*表达式结果=*=*=*=*=*=*n”);

printf(“该表达式的结果为:n%s=%-10.3lfn”,b,EvaluateExpression(a));

printf(“=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n”);

printf(“继续使用[四则运算.如:-1+(2+3)*9/(-2)-6].<关闭退出>.n请再输入一个表达式:n”);} }

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

实验五报告

课程名称： 数据结构 实验名称：二叉树的创建与遍历

实验日期

2011/11/16

一、实验目的：

通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。

二、实验内容与要求：

基于二叉链表存储结构实现二叉树的基本运算，要求：

⑴能建立非空二叉树；

⑵实现二叉树的先、中、后序递归遍历算法；

⑶实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法；

⑷记录运行结果并对递归算法和非递归算法的效率加以分析。

三、算法设计 结构体的定义：

typedef struct BiTNote{

struct Node{

};类的定义： class CStack{

//栈 private:

};

class LinkQueue{ //队列 public: BiTree base;BiTree top;int stacksize;//当前空间分配量 static const int STACK_INIT_SIZE=100;static const int STACKINCREMENT=10;CStack();

void Push(BiTree T);//入栈 void Pop(BiTree &T);//出栈 bool StackEmpty();//判断是否是空栈 friend class CBiTree;Node(BiTree &d):num(d),next(NULL){} BiTree num;Node *next;char data;struct BiTNote *lchild,*rchild;}BiTNote,*BiTree;public:

};LinkQueue();bool QueueEmpty();void EnQueue(BiTree &T);void DeQueue(BiTree &T);friend class CBiTree;int length;//队列元素的个数 Node *front;

//队列的头指针 Node *rear;

//队列的尾指针 private: class CBiTree{ public:

};CStack::CStack():stacksize(STACK_INIT_SIZE){ //构造函数，初始化

} void CStack::Push(BiTree T){...} //入栈 void CStack::Pop(BiTree &T){...} //出栈 bool CStack::StackEmpty(){} int i=0;//全局变量

int CBiTree::CreatBiTree(BiTree &T){}//构造二叉树 //LinkQueue类函数的实现 LinkQueue::LinkQueue(){} bool LinkQueue::QueueEmpty(){} void LinkQueue::EnQueue(BiTree &T){} void LinkQueue::DeQueue(BiTree &T){} int CBiTree::PreOrderTraverse1(BiTree T, int(*Visit)(char)){...} //前序遍历（递归）int CBiTree::InOrderTraverse(BiTree T, int(*Visit)(char)){...} //中序遍历（递归）int CBiTree::PostOrderTraverse(BiTree T, int(*Visit)(char)){...}//后序遍历（递归）int CBiTree::PreOrderTraverse2(BiTree T, int(*Visit)(char)){ //前序遍历（非递归）

BiTree p=T;while(p!=NULL||!s.StackEmpty()){ BiTree p=(BiTree)malloc(STACK_INIT_SIZE*sizeof(BiTNote));base=p;top=base;int CreatBiTree(BiTree &T);//建立二叉树

int PreOrderTraverse1(BiTree T,int(*Visit)(char e));

//前序遍历（递归）int PreOrderTraverse2(BiTree T,int(*Visit)(char e));

//前序遍历（非递归）

int InOrderTraverse(BiTree T,int(*Visit)(char e));

//中序遍历（递归）int PostOrderTraverse(BiTree T,int(*Visit)(char e));//后序遍历（递归）int LevelOrderTraverse(BiTree T,int(*Visit)(char e));//层序遍历（非递归）CStack s;LinkQueue link;private:

}

} while(p!=NULL){

} if(!s.StackEmpty()){

} s.Pop(p);p=p->rchild;Visit(p->data);s.Push(p);p=p->lchild;return 1;int CBiTree::LevelOrderTraverse(BiTree T, int(*Visit)(char))//层序遍历（非递归）{

} //main.cpp #include“BiTree.h” #include“Function.h” #include int PrintData(char e){

}

int main(){

CBiTree Tree;BiTree T;T=(BiTree)malloc(sizeof(BiTNote));cout<<“构造二叉树：”;Tree.CreatBiTree(T);cout<<“先序遍历（递归）：”;Tree.PreOrderTraverse1(T,PrintData);cout<

link.EnQueue(T);while(!link.QueueEmpty()){

} return 0;BiTree p;link.DeQueue(p);Visit(p->data);link.EnQueue(p->lchild);link.EnQueue(p->rchild);

} cout<

四、测试结果

五、心得体会

这次实验尝试用C++写，好长时间没接触了，所以写的比较吃力，在写的过程中温习了C++的一些知识，但代码写的很乱，没有用模板，C++的引用也忘了等。这次还发现自己对指针还是不熟练（一个指针赋值的小错误多花了好多时间才找到）。总之觉得自己的编程水平很有待提高。

第三篇：数据结构实验六报告

实验六报告

课程名称： 数据结构 实验名称：二叉树的应用

实验日期

2011/11/23

一、实验目的：

掌握赫夫曼二叉树的建立及赫夫曼编码的生成。

二、实验内容与要求：

根据给定的n个权值生成赫夫曼二叉树，输出赫夫曼编码。

三、数据结构设计

顺序表的存储结构，建立了二叉树的关系

Struct HTNode{

int weight;

unsigned int parent,lchild,rchild;};

四、算法设计

1、从数据中选择较小的两个数据元素

void Select(HTNode *HT, const int n, int &a, int &b){ //选择较小的两个元素

} int x,y;

x=y=0x7fff;for(int j=0;j

if(HT[j].parent==0)

if(HT[j].weight

2、建立赫夫曼树

void CreatHuff(HTNode *HT,int *p,const int n){

} int m=2*n-1;int i,a,b;for(i=0;i

Select(HT ,i,a,b);HT[a].parent=HT[b].parent=i;HT[i].weight=HT[a].weight+HT[b].weight;HT[i].lchild=a;HT[i].rchild=b;}

3、生成赫夫曼编码

void HuffCoding(HTNode *HT, Huffcode &HC, const int n){

//

}HC=new

char*[n+1];

char *code=new char[n];code[n-1]='';int i,j,p,k;for(i=0;i

} delete[] code;j=n-1;k=i;while(HT[k].parent){

p=HT[k].parent;if(HT[p].lchild==k)code[--j]='0';else code[--j]='1';k=p;} HC[i]=(char*)malloc((n-j)*sizeof(char));HC[i]=new char[n-j];strcpy(HC[i],&code[j]);

五、测试结果

测试数据一：

测试数据二：

六、心得体会

这次实验是在前面的实验基础之上，加上只用了顺序表的存储结构，所以比较简单。尽管实验内容少，但还是学到一些知识。首先学会了赫夫曼编码的简单实现，认识到其应用的实际价值。然后，学会了用指针数组，前面几次试验有过尝试，但没写成。这次实验最初也是用C++写的，但错误“无法解析的外部符号“public: void __thiscall HuffmanTree::HuffCoding(struct HTNode *,char * * &,int)”(?HuffCoding@HuffmanTree@@QAEXPAUHTNode@@AAPAPADH@Z)，该符号在函数_main 中被引用”改不过来，所以迫于无奈，只得稍微改成像C的代码。

第四篇：数据结构实验二 求解约瑟夫问题

数据结构实验二

求解约瑟夫问题

问题描述：使用代表头节点的循环单链表解决此问题。设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人离开。接着从出列的下一个人开始重新从1开始报数，数到m的人又出列，如此下去直到所有的人都出列为止。求出他们的出列序列。

问题分析：例如，当n=8,m=4时，若从第一个人开始报数（设从1开始编号），则得到的序列是：4，8，5，2，1，3，7，6。算法：

void Josephus(int n, int m,int s)

{ //生成表头节点，空单循环链表

LNode * HL = new LNode;

HL-> next = HL;

int i;//生成含有 n 个节点的、节点值依次为1，2……，n的带表头节点的循环单链表

For(i = n;i>=1;i--)

{ LNode * newptr = new LNode;

Newptr-> data = i;

newptr-> next = HL-> next;

HL-> next = newptr;}

//从表头开始顺序查找出第s个节点，对应第一个开始报数的人 LNode * ap = HL, *cp = HL->next;for(i= 1;i

ap = cp;

cp = cp->next;if(cp = = HL){ ap = HL;cp = HL->next;} } //依次使n-1个人出列 for(i=1;i

//顺序查找出待出列的人，即为循环结束后cp所指向的节点

for(int j=1;jnext;if(cp ==HL){ ap = HL;cp = HL->next;} } //输出cp节点的值，即出列的人

cout << cp->data <<”

“;//从单链表中删除cp节点

ap-> next = cp-> next;delete cp;//使cp指向被删除节点的后续节点

cp = ap-> next;//若cp指向了表头节点，则后移ap和cp指针 if(cp = = HL){ ap = HL;cp = HL-> next;} }

//使最后一人出列

count << HL->next-> data << end1;

//删除表头节点和表头附加节点

delete HL->next;

delete HL;}

补充操作系统练习：

1、有一个虚拟存储系统, 每个进程在内存占有3页数据区、1页程序区.刚开始时数据区为空.有以下访页序列: 1、5、4、1、2、3、2、1、5、4、2、4、6、5、1

试给出下列情形下的缺页次数:

(1)系统采用先进先出(FIFO)淘汰算法.(2)系统采用最近最少使用(LRU)淘汰算法.(3)若采用优化(OPT)淘汰算法呢?

2、设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下：

最大需求量

已分配资源量

剩余资源量

A

B

C

A

B

C

A

B

C

P1 8

P2 4

P3 10 1

P4 3

P5 5(1)系统是否处于安全状态？如是，则给出进程安全序列.(2)如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？

3、在一个两道的批处理操作系统中，有6个作业进入系统，它们的进入时刻、估计运行时间和优先级如下表所示.作业号

进入时刻

估计运行时间

优先级

JOB1

8：00

90分钟

JOB2

8：10

30分钟

JOB3

8：30

20分钟

JOB4

8：50

15分钟

JOB5

9：20

10分钟

JOB6

9：40

5分钟系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出.但当有新的作业投入运行时，可以按照优先级进行进程调度.（1）试给出各个作业的运行时间序列.（例如：JOB1：8：00-8：30，9：10-9：20，…）

（2）试计算出作业的平均周转时间.

第五篇：《数据结构》实验指导书

《数据结构》实验(训)指导书

电气与信息工程学院实验中心

前 言

《数据结构》是计算机相关专业的一门核心基础课程，也是很多高校研究生入学考试专业课必考课程之一。它主要介绍线性结构、树型结构、图形结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法分析、设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法的最佳途径是上机实验。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写该实验指导书。

一、实验目的、要求和任务

计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。

1.熟练掌握C语言的编辑、编译、调试程序。2.会书写类C语言的算法，并将算法转变为程序实现。

3.正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。4.有较强的逻辑分析能力。

5.针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。

6.学会分析研究计算机加工的数据结构的特性，以便为应用设计的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。

7.本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力。

8.通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序做一些铺垫。

二、实验基本内容及学时分配

为了达到实验目的，本课程安排了4个实验单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实验单元与教科书的各章只具有粗略的对应关系，一个实验题常常涉及到几部分教学内容。总学时：8学时。

1、线性表（2学时）

（1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；（2）以线性表的各种操作（建立、插入、删除等）的实现为重点；

（3）通过本次实验帮助学生提高C语言的编程能力（特别是函数参数、指针类型、链表的使用）。

2、数组和广义表（2学时）（1）掌握稀疏矩阵的压缩存储

（2）掌握稀疏矩阵的转置算法

3、树与二叉树（2学时）

常见的二叉树遍历算法有先序遍历，中序遍历和后序遍历算法。实现简单的先序遍历，中序遍历和后序遍历算法。

4、排序（2学时）

常见的内部排序算法，插入类排序算法，如直接插入排序和希尔排序；交换类排序算法，如冒泡排序和快速排序；选择类排序算法，如简单选择排序、树形选择类排序和堆排序。实冒泡排序或者直接插入排序算法。

三、说明

该课程采用理论与实践相结合的教学方法，集知识性与趣味性于一体，达到良好的教学效果。硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供电脑等设备。学生每次上机实验都必须遵守实验室的有关规定。

四、实验报告规范 实验报告的内容包括：

1、实验目的：说明实验所验证的知识点。

2、需求分析：以无歧义的陈述说明程序设计的任务、约束条件、输入输出要求、对功能的规定及模型。

3、逻辑设计：说明本程序中用到的所有抽象的数据类型的定义、主程序的流程以及各程序模块之间的层次调用关系。

4、详细设计：逻辑设计中定义的所有数据类型的实现，核心算法的设计描述、人机界面设计、函数之间调用关系的描述，主要功能的算法框架，测试数据设计。

5、测试分析：测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。

6、心得：软件设计与实现过程中的经验与体会，进一步改进的设想。

7、程序清单：源程序中应有足够的注释。如果提交源程序软盘，列出程序文件名。

五、如何提高上机效率

为了提高上机的效率，真正达到实验目的，要求同学做好实验前的准备工作，写好实验预习报告，即实验报告规范中的1）、2）、3）、4）部分，编写好程序，并用一组测试数据手工执行程序静态检查程序是否有错，通过阅读、执行程序或给别人讲解自己的程序而深入全面地理解程序逻辑，提高程序的正确性。对C语言程序不熟悉的同学，上机时最好带上C语言程序设计的教材，以备查阅。调试中遇到问题，应认真分析，确定可疑点，设置调试断点或输出断点处变量的值，以便发现问题，迅速排除问题，加快调试速度。

实验室要求：

不能旷课，不迟到，不穿拖鞋进实验室

实验需预习报告（不能单纯抄写，预习程序代码）实验报告（总结，注释，实验结果）

目 录

实验一 线性表实验（设计性实验）..........................................4 实验二 数组和广义表实验（设计性实验）....................................6 实验三 树与二叉树（设计性实验）..........................................8 实验四 排序（设计性实验）................................................9

实验一

线性表实验（设计性实验）

一、实验目的

1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。

3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。

二、实验内容

1.顺序线性表的建立、插入及删除。2.链式线性表的建立、插入及删除。

三、实验仪器设备与器材 上机电脑

四、实验步骤

1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。

五、实验提示

1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。

在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype;/*

线性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/*

顺序表的长度 */ }sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。

2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。

3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：

typedef int elemtype;typedef struct node { elemtype data;//数据域

struct node *next;//指针域

}linklist;

注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：

p=(linklist *)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。

六、实验总结与思考

1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2.在main函数里如果去掉L=&a语句，会出现什么结果？

实验二

数组和广义表实验（设计性实验）

一、实验目的

1.掌握稀疏矩阵的压缩存储 2.掌握稀疏矩阵的转置算法

二、实验内容

1.实现上三角阵的压缩存储。

2.用三元组顺序表存储稀疏矩阵，并实现矩阵的转置。

三、实验仪器设备与器材 上机电脑

四、实验步骤

1.创建一个数组。2.输入数据

3.给定矩阵任一元素的下标，4.打印给定下标所对应的数据。5.创建三元组顺序表。a22 7.A输出对应的矩阵。

21五、实验提示 aaa6.输入矩阵中的数据。11a11a313233a21221.对于如下对称矩阵： Aaaa424341a31a32a331个位置，a21存入到第二个位置，将它们存入到一个线性数组中B，不存非零元素，a11存入到第a41a42aija44aij的位则aij能存到第几个位置，我们要以用梯形公式算面积。置是它上面的元素之和再加上左边的元素之和。

它上面的元素之和为((1+(i-1))×(i-1)/2，左边的元素为(j-1)所以这个元素存储的位置为k=i(i-1)/2+j-1。

因为矩阵A为对称矩阵，(另一部分没有写出)，所以另一部分的元素为 k=j(j-1)/2+i-1.所以存在关系k=i(i-1)/2+j-1(i>j)和k=j(j-1)/2+i-1(i

2.结点结构

struct triple{ int i,j;//非零元的行下标和列下标 elemtype e;//非零元数据} 三元组顺序表存储类型 struct tsmatrix{ triple data[12500];aaa44

int mu,nu,tu;} 三元顺序表的转置 方法：(1)将矩阵行列互换，(2)重排矩阵

六、实验总结与思考

1.如何存储三对角阵？

2.如何用行逻辑链接顺序表及十字链表存储稀疏矩阵？

实验三

树与二叉树（设计性实验）

一、实验目的

1.掌握稀疏矩阵的压缩存储 2.掌握稀疏矩阵的转置算法

二、实验内容

1.练习二叉树的建立与存储 2.练习二叉树的遍历

三、实验仪器设备与器材 上机电脑

四、实验步骤

1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。

2.建立二叉树,并通过调用函数,，输出先序遍历、中序遍历与后序遍历的结果。

五、实验提示

建立二叉树的代码如下： BTCHINALR * createbt(){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf(“建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开nn”);printf(“i,x = ”);scanf(“%d,%c”,&i,&x);while(i!= 0 && x!= '$')

{q =(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一个新结点q*/

q->data = x;q->lchild = NULL;q->rchild = NULL;

s[i] = q;/*q新结点地址存入s指针数组中*/

if(i!= 1)/*i = 1，对应的结点是根结点*/

{j = i / 2;/*求双亲结点的编号j*/

if(i % 2 == 0)s[j]->lchild = q;/*q结点编号为偶数则挂在双亲结点j的左边*/

else s[j]->rchild = q;} /*q结点编号为奇数则挂在双亲结点j的右边*/

printf(“i,x = ”);

scanf(“%d,%c”,&i,&x);} return s[1];/*返回根结点地址*/ }

六、实验总结与思考

1.如何用孩子兄弟表示法存储树？ 2.熟悉及难赫夫曼树。

实验四

排序（设计性实验）

一、实验目的

1.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； 2.深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用； 3.了解各种方法的排序过程及其时间复杂度的分析方法。

二、实验内容

统计成绩

给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：

（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；（2）按名次列出每个学生的姓名与分数。

三、实验仪器设备与器材 上机电脑

四、实验步骤

1.定义结构体。2.定义结构体数组。

3.定出主程序，对数据进行排序。

五、实验提示

#define n 30 typedef struct student { char name[8];int score;} student R[n];main(){ int num, i, j, max, temp;printf(“n请输入学生成绩: n”);for(i=0;iR[max].score)max=j;

if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score

六、实验总结与思考

1.快速排序算法解决本问题。2.较各种排序算法的优缺点及。

3.使用其它排序算法实现该问题（直接插入排序、希尔排序、简单选择排序、堆排序等）。