数据结构顺序存储结构_C++实现
数据结构实验报告
实验目的
1.熟练掌握线性表的顺序存储结构、链式存储结构，并分别实现线性表的基本操作。
2.熟练掌握顺序存储结构中算法的实现。
3.培养编程和上机调试能力。
实验容
1.建立含有若干元素的顺序表，并实现插入、删除、修改、查找等基本操作。并在屏幕上
输出。
2.建立含有若干元素的链式表，并实现插入、删除、修改、查找等基本操作。并在屏幕上
输出。
实验步骤
打开VC6.0，新建文件。编写代码，运行、调试、输出结果。
实验代码
顺序表
#include
#define elemtype int
const int maxsize=1000;
class sequenlist
{
protected:
elemtype a[maxsize];
int len;
public:
void setnull()
{
len=0;
}
void input(int n)
{
for(int j=1;j<=n;j++)
cin>>a[j];
len=n;
}
void print()
{
for(int i=1;i<=len;i++)
cout< cout< } void length() { cout<<"现表长度"< } void insert(elemtype x,int i) { int j; if(len>=maxsize-1) cout<<"overflow"< else if((i<1)||(i>len+1)) cout<<"position is not correct!"< else { for(j=len;j>=i;j--) a[j+1]=a[j]; a[i]=x; len++; } } void deletel(int i) { int j; if((i<1)||(i>len)) cout<<"position is not correct!"< else{ for(j=i+1;j<=len;j++) a[j-1]=a[j]; len--; } } int locate(elemtype x) { int j=1; while((j<=len)&&(a[j]!=x)) j++; if(j<=len) return j; else return 0; } void change(elemtype x,elemtype y) { int j; for(j=1;j<=len;j++) if(a[j]==x) a[j]=y; } }; void main() { sequenlist L; elemtype x,y; int n,j; L.setnull(); cout<<"请输入表中元素个数："; cin>>n; cout<<"请输入"< L.input(n); L.print(); L.length; cout<<"请输入要插入的元素及位置："; cin>>x>>j; L.insert(x,j); L.print(); cout<<"请输入要删除的元素位置："; cin>>j; L.deletel(j); L.print(); L.length; cout<<"请输入要查找的元素："; cin>>x; j=L.locate(x); if(j!=0) cout< cout<<"找不到"; cout< L.print(); cout<<"请输入要更新前的元素值："; cin>>x; cout<<"请输入要更新后的元素值："; cin>>y; L.change(x,y); L.print(); } 链式表： #include #define elemtype int class link { public: elemtype data; link *next; }; class linklist { protected: link *head; public: link *hcreat() { link *s,*p; elemtype i; cout<<"输入多个结点数值（用空格分隔），为0时算法结束"; cin>>i; p=new link; p->next=NULL; while(i) { s=new link; s->data=i; s->next=p->next; p->next=s; cin>>i; return p; } void print (link *head) { link *p; p=head->next; while(p->next!=NULL) { cout< p=p->next; } cout< cout< } link *Locate(link *head,elemtype x) { link *p; p=head->next; while((p!=NULL)&&(p->data!=x)) p=p->next; return p; } void deletel(link *head,elemtype x) { link *p,*q; q=head; p=head->next; while((p!=NULL)&&(p->data!=x)) { q=p; p=p->next; } if(p==NULL) cout<<"要删除的结点不存在"; else { q->next=p->next; delete(p); } } void insert(link *head,elemtype x,elemtype y) { link *p,*s; s=new link; s->data=y; if(head->next==NULL) { head->next=s; s->next=NULL; } p=Locate(head,x); if(p==NULL) cout<<"插入位置非法"; else { s->next=p->next; p->next=s; } } void change(link *p,elemtype x,elemtype y) { link *q; q=p->next; while(q!=NULL) { if(q->data==x) q->data=y; q=q->next; } } int count(link *h) { link *p; int n=0; p=h->next; while(p!=NULL) { n++; p=p->next; } return n; } }; void main() { 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i O(m+n) 6、算法是（D ）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（A ）。 i=s=0; while(s 福建农林大学金山学院实验报告 系(教研室): 专业: 年级: 实验课程: C语言程序设计姓名: 学号: 实验室号:_ 计算机号: 实验时间: 指导教师签字: 成绩: 实验1:顺序结构程序设计 一、实验目的与要求 1.了解Visual C++ 6、0/DEV_C++的基本操作方法 2.掌握C程序设计的基本步骤:编辑、编译、连接与运行 3.掌握各种类型数据的输入输出方法 4.能够编写一个简单的程序 二、实验内容与原理 1、输入并运行一个简单、正确的程序。 # include 顺序结构、选择结构和循环结构的程序设计典型例题分析与解答 1 在三种选择结构中,能用2个条件,控制从3个操作中选择一个操作执行的选择结构是______选择结构 【分析】能用1个条件,控制某个操作做或不做的选择结构是单分支结构；能用1个条件，控制从2个操作中选择一个操作执行的选择结构是双分支结构；能用n(n＞l)个条件，控制从n＋ l个操作中选择一个操作执行的选择结构是多分支结构。【答案】多分支 2 在三种循环结构中，先执行循环操作内容(即循环体），后判断控制循环条件的循环结构是______循环结构。 【分析】当型循环结构是先判断控制循环的条件，条件成立，执行循环体；条件不成立，则退出循环体。次数型循环结构也是先判断是否达到循环次数，没有达到循环次数，执行循环体；达到循环次数的，退出循环。只有直到型循环结构才是先执行循环体，然后再判断控制循环的条件，如果条件成立，进行循环；条件不成立，退出循环。 【答案】直到型 3 使用“getchar( )”函数时,程序的开头必须写一条包含命令为____________。 【分析】凡是使用系统函数的程序，都要在程序的开头写一条包含命令，包含命令中的“头函数．h”是一个文件，其中有关于该系统函数的定义。系统函数“getchar( )”是在名为“stdio．h（标准输入输出函数）”的头函数文件中定义的。【答案】#include"stdio.h"或#include＜stdio.h＞ 4 执行输入语句“scanf("x＝％c，y＝％d"，&x，&y);”，要使字符型变量X的值为'A'、整型变量y的值为12，则从键盘上正确的输入是( ) ①'A'/②A/③x＝A/ ④x=A，y＝12/ 12/ 12/ y＝12/ 说明:备选答案中的"/"表示回车换行键 【分析】输入语句的格式控制符串中的“x＝”、“，”、“y＝”都是非格式控制符， 在输入时必须原样位置输人，所以只有备选答案④才符合这个要求。【答案】④ 5 设有下列程序段，则执行该程序段后的输出是( ) int i＝012； float f＝1．234E－2； printf("i=%-5df＝%5．3f"，i，f)； ... ①i=__012f＝1．234 ②i＝10___f＝0．012 ③10___O．012 ④___100.012 注：答案中的_代表一个空格。 【分析】输出语句的格式控制符串中的“i＝”、“f＝”都是非格式控制符，在输出时必须原样，原位置输出，所以只有备选答案①和②才符合这个要求；格式控制符“%-5d”的格式控制是数据左对齐、宽度为5的整型数据，备选答案①中的数据是右对齐的；此外，该答案中的实数“1．234E－2”应该代表“0．01234”，而不是“1．234”。只有备选答案②符合题意。【答案】② 6 在Turbo C的主屏幕中，将当前编辑的源程序以原名存盘，可以选用___________菜单项，也可以直热键________。 【分析】如果选用“File／Save”菜单项，或者使用热键(f12)，当前编辑的源程序将以原来的文件名存盘；如果选用“File ／Write to”，当前编辑的源程序将以新的文件名存盘。 【答案】File／Save F2 7 下列各种选择结构的问题中，最适合用if－else语句来解决的是( ) ①控制单个操作做或不做的问题 ②控制两个操作中选取一个操作执行的问题 ③控制三个操作中选取一个操作执行的问题 ④控制10个操作中选取一个操作执行的问题 【分析】if－else语句是专门解决“双分支结构”的，而“双分支结构”的问题就是用单个条件控制从两个操作中选取一个操作来执行的问题。 【答案】② 8 下列程序是输入一个小写字母，转换成对应大写字母的后一个字母输出。例如：'a'将转换成’B’、…、‘y’将转换成’Z’，其中的’Z’将转换成’A’。请填写程序中所缺少的语句。 main() {char ch ； scanf(”%c”,&ch〕； ch＝ch－ 32+1； ___________________； printf("%c\n"，ch）； } 【分析】分析程序库中的“ch＝ch－ 32＋ 1；”语句，可知是将字符型变量 ch中的小写字母转换成对应的大写字母（－ 32）的后一个字母（＋ l）。如果ch中的字母是' a'、' b'、··，'y'，转换结果都不会出错，但是，如果 ch中的字母是'Z'，则-32后是大写字母'Z'，再+l后将不是大写字母了。为了使其转换成'A'，需要用一个单分支结构来实现：如果ch的值等于'Z'+ l，则硬性将 ch的值改成'A'。完成这个任务的语句是一条单分支语句，正是所缺少的语句。 【答案】 if （ch＝＝'Z'+l） h＝'A'； 9不能正确计算下列分段函数的程序段是_________ |-1 x<0 y＝|0 x＝0 x>0 ① switch（x＜ 0）② if（x＞ 0） {case1：y＝－1；break； y=1； case 0：switch（x＝＝0）else {casel：y＝0；break；if（x＝＝0） case 0： y＝ l；y＝0 } else } &ny＝-l ③ y＝ l；④ y＝ l； if（x＝＝0）if（x＜0） y＝0； y ＝－l； else else y＝－ l； if（x＝＝ 0） y＝0; 【分析】先来分析备选答案①：表达式“x＜0”的值只有两种可能性，成立值为1、不成立值为on如果“x＜0”的值为 1（即 x＜ 0），则执行“easel：”后的语句“y＝－l”后，退出 switch语句，符合分段函数要求。如果“x＜0”的值为0（即x＞＝0），则执行“case 0：”后的switch语句。该switch语句的表达式是“x＝＝0”，结果也有两种：成立为1、不成立为0.如果“x＝＝0”的值为1(即x＝0)，则执行“case l：”后的语句“y＝0”后，退出 switch语句，符合分段函数要求。如果“x＝＝0”的值为0（即x＞0），则执行“case 0：”后的语句“y=1”，也符合分段函数要求。再分析备选答案②：这是标准的用嵌套双分支结构来实现三分支的分段函数，结果显然是能求解分段函数的。分析备选答案③：双分支语句的条件是“x＝＝0”，条件成立时，y值为0，符合分段函数的要求，条件不成立时(包含x＞0和x＜0两种情况)，结果y值为－l，显然不符合分段函数的要求，所以本题要选该答案。至于备选答案④，是能正确计算分段函数的，首先置y为1；接着用双分支结构处理“x＜0”和“x＞＝0”的两种情况：前者使得y值为一l；后者再执行一个单分支结构，如果“x＝＝0”则使y值为0，否则不改变y值，保持y的原值1，符合分段函数的要求。 【答案】③ 10 三种循环语句都能解决循环次数已经确定的次数型循环，其中__________循环语句最适合。 【分析】当“for(表达式 1；表达式 2；表达式 3)语句；”中的表达式1为：整型变量 k＝l；表达式 2为：整型变量 k＜＝ n；表达式 3为：整型变量 k++；则这个 for循环就是次数为n次的标准次数型循环结构。 【答案】for 11执行下列程序段后的输出是() x＝l； while(x＜＝3) x++，y＝x+++x； printf("%d，%d"，x，y)； ① 6，10 ②5，8 ③4，6 ④3，4 【分析】我们可以使用逐步记录运行结果的方法来获得输出结果，记录如下： x＝1； 进入循环，条件满足执行循环体：计算x+十得x为2，计算y＝x+++x，得y为4、x为3； 继续循环，条件满足执行循环体：计算x+十得x为4，计算y＝x+++x，得y为8、x为5； 继续循环，条件不满足退出循环； 输出x和y的值为5，8。 【答案】② 12 执行下列程序段，其中的do－while循环一共执行＿次。 static int x； do x+＝x*x； while (x)； 【分析】对静态型变量，不赋初值也有值，对整型变量，其值为 0。执行循环语句 do-while 的循环体,x+＝x* x是x＝x+(x* 单元练习 一单项选择题 1.文件系统与数据库系统相比较，其缺陷主要表现在数据联系弱、数据冗余和（）。 A.数据存储低 B.处理速度慢 C.数据不一致 D.操作烦琐 2.数据的存储结构与数据逻辑结构之间的独立性称为数据的（）。 A.结构独立性 B.物理独立性 C.逻辑独立性 D.分布独立性 数据存储结构：即内模式。 数据逻辑结构：即模式 用户视图：即外模式 3.在数据库系统中，对数据操作的最小单位是（）。 A.字节 B.数拯项 C.记录 D.字符 4.数据的逻辑结构与用户视图之间的独立性称为数据的（）。 A.结构独立性 B.物理独立性 C.逻辑独立性 D.分布独立性 5.下述各项中，属于数据库系统的特点的是（）。 A.存储量大 B.存取速度快 C.数据共享 D.操作方便 6.在数据库系统中，模式/内模式映像用于解决数据的（）。 A.结构独立性 B.物理独立性 C.逻辑独立性 D.分布独立性 7.在数据库系统中，模式/外模式映像用于解决数据的（）。 A.结构独立性 B.物理独立性 C.逻辑独立性 D.分布独立性 8.数据库结构的描述，称为（）。 A.数据库模型 B.数据库 C.数据库管理系统 D.数据字典 数据库模型有层次模型网状和关系模型 9.数据库中全体数据的逻辑结构描述称为（ A. 存储模式 B.内模式 C.外模式 D.模式 10.保证数摇库中数摇及语义的正确性和有效性，是数据库的（）。 A.完全性 B.准确性 C.完整性 D.共享性 11.在数据库系统中，数据独立性是指（）。 A.用户与计算机系统的独立性 B.数据库与il?算机的独立性 C.数据勺应用程序的独立性 D.用户与数摇库的独立性 12.结构数据模型的三个组成部分是数据结构、数据操作和（）。 A.数据安全性控制 B.数摇一致性规则 C.数^]^完整性约束 D.数摇处理逻辑 13.在数据操纵语言（DML）的基本功能中，不包括的是（）。 A.插入新数据 B.描述数据库结构 C.对数据库中数据排序 D.删除数据库中数据 14.控制数摇库整体结构、负责数据库物理结构和逻辑结构的注义打修改的人员是（）。 A.系统分析员 B.应用程序员 C.专业用户 D.数据库管理员 15.K列关于数据库系统正确的叙述是（）。 A.数据库系统比文件系统存储数据量大 B.数据库系统中数据存储没有冗余 C.数据库系统中数据存储冗余较小 D.数据库系统比文件系统存取速度快 16.在数据库中，发生数据不一致现象的根本原因是（）。 A.数据存储量太大 B.数摇安全性差 C.数据相互关系复杂 D.数据冗余 17.层次型、网状型和关系型数据模型的划分根据是（）。 A.数据之间联系方式 B.数据之间联系的复杂程度 数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 -------------------------------------------------------------------------------- 四种基本的存储结构 Prepared on 22 November 2020 数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 由此得到的存储表示称为顺序存储结构（Sequential Storage Structure），通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。 （3）索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是： (关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。 （4）散列存储方法 该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 数据结构三方面的关系 《数据结构》填空作业题答案 第1章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3. 数据结构的形式定义为：数据结构是一个二元组：Data Structure =（D，S）。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7. 在树形结构中，数据元素之间存在一对多的关系。 8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9. 数据的逻辑结构包括线性结构、树形结构和图形结构3种类型，树型结构和有向图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。 12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14. 数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。 16. 数据元素可由若干个数据项组成。 17. 算法分析的两个主要方面是时间复杂度和空间复杂度。 18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 21. 下面程序段的时间复杂度为㏒3n 。 《C语言程序设计》实验报告 ---------------------------------------------------------------------------------------------- 实验3选择结构程序设计 一．实验目的 1.了解C语言表示逻辑量的方法（以0代表“假”，以非0代表“真”）。 2.学会正确使用逻辑运算符和逻辑表达式 3.熟练掌握if语句和switch语句； 4.结合程序掌握一些简单的算法。 5.学习调试程序 二．实验内容和步骤 1.基础知识和概念 （1）分析下面程序，掌握关系表达式的运算规则。 #include int a=2,b=0,c=0; float x=3.0; printf("%d",a&&b); printf("%d",a||b&&c); printf("%d",!a&&b); printf("%d",a||3+10&&2); printf("%d",!(x==2)); printf("%d",!x==2); printf("%d\n",ch||b); return 0; } 总结与反思：1.运用逻辑运算符比较的结果，真为1，假为0；2.逻辑与&&优 先级11大于逻辑或||优先级12 （3）分析运行下面的程序，掌握关系及逻辑混合表达式的运算规则。 #include 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 答案： （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。 （3）树结构 实验一顺序结构程序设计 一、实验目的 1. 掌握C语言数据类型，熟悉如何定义一个整型、字符型、实型变量，以及对它们赋值的方法，了解以上类型数据输出时所用的格式转换符。2 2. 学会使用有关算术运算符，以及包含这些运算符的表达式。 3. 掌握数据的输入输出方法，能正确使用各种格式转换符。 二、实验学时数 4学时 三、实验内容和步骤 1..启动TC 2.0编译系统，进入编辑界面，建立一个新文件。文件名自定。（要求每个学生建立一个自己的文件夹，每个同学的练习和作业的源程序命名形成系列，便于检查、查找和考核）。 利用一个小程序验证常量、变量的使用方法与特点，验证数据类型和表达式值的计算规则及其输出格式。 参考程序： main( ) { char c1,c2; c1=97;c2=98; printf(″％c,％c\n″,c1,c2); } （1）在此基础上加入以下printf语句，并运行。 printf(″％d,％d\n″,c1,c2); （2）将第二行改为以下语句，并运行。 int c1,c2; （3）将第三行改为以下语句，并运行。 c1=300;c2=400; 分别写出三次运行结果。 2．编程并调试运行 （1）编程序，用getchar函数读入两个字符给c1、c2，然后分别用putchar函数和printf 函数输出这两个字符。上机运行此程序，比较putchar和printf函数输出字符的特点。 （2）试编写程序，从键盘输入一个大写字母，要求改用小写字母输出。 3．写出下面程序的运行结果： 1）main() { int x=1,y=1,z=1; y=y+x; x=x+y; printf(″%d\n″,x); printf(″%d\n″,y); } 2) main() 第3章顺序 一、单选题： 1．己知int k,m=1;执行语句k=-m++;后k的值是（ A）。（提示：负号与自加运算符同级，结合方向从右向左） A)-1 B) 0 C)1 D)2 2．若变量a, b已正确定义，且a,b均已正确赋值，下列选项中合法的语句是（ B） A) a=b B)++a; C) a+=b++=1; D)a=int(b); （提示：a=b 只是表达式非语句； b++是个表达式）3．若有定义int x=4；则执行语句 x + = x * = x + 1；后，x的值为（ C ）。 A)5 B)20 C)40 D)无答案 4．若有定义和语句： int s，p； s=p=5； p=s++，++p，p+2，p++；则执行语句后 p的值是（ C） A)9 B)8 C)7 D)6 5．若有定义：int a，b；则表达式 a=4，b=3，a+b+2，a++，a+b+2的值为（ C）。 A) 12 B)11 C)10 D)无答案 6．若有定义：float a=3.0，b=4.0，c=5.0；则表达式 1/2*(a+b+c)的值为（ C ）。 A)6.0 B)6 C)0.0 D)无答案 7．以下程序段的输出结果是（ C ）。（提示：a当约束过严时，约束失效。按自由格式输出。） int a=1234; printf("%2d\n",a); A)12 B)34 C)1234 D)提示出错，无结果 8.下列程序段的输出结果是（C）。 int a=1234； float b=123.456； double c=12345.54321； printf（"%2d，%3.2f，%4.1f"，a，b，c）； A)无输出 B)12, 123.46, 12345.5 C)1234,123.46,12345.5 D)1234,123.45, 1234.5 9.设x, y均为整型变量，且x=8, y=5,则以下语句的输出结果是（D）。 printf（"%d，%d\n"，x--，++y）； A)8,5 B)7,5 C) 7,6 D) 8,6 10.以下程序的输出结果是（ A ）。 void main（） ｛ int a=20，b=10； printf（"%d,%%d\n"，a+b，a-b）； } A) 30,%d B)30,10 C)30,%10 D)以上答案均不正确（%%d中第一个%后面的表示字符）11．下列程序的运行结果是（A）。 void main（） ｛ float x=2.5； int y; y=（int）x； printf（"x=%f，y=%d"，x，y）；｝ A) x=2.500000,y=2 B)x=2.5,y=2 C)x=2,y=2 D) x=2.500000,y=2.000000 12.己知int k=10 , m=3,n;则下列语句的输出结果是（B）。 printf（"%d\n"，n=（k%m，k/m））； #include 数据结构习题集（自编） 第一章绪论 一、选择题 1．数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。 A．结构B．关系 C．运算 D．算法 2．在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3．线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。 A．正确B．不正确 C．无法确定 D．以上答案都不对4．算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 5. 算法的时间复杂度取决于（） A．问题的规模B待处理数据的初态 C. A和B 6．一个算法应该是（）。 A．程序B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 7. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法与为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．在下面的程序段中，对x的赋值语句的频度为（） for（i=0;i 昆明理工大学信息工程与自动化学院学生实验报告 （2012 —2013 学年第一学期） 课程名称：结构化程序设计与C语言开课实验室：系机房444 2012 年10月21日 一、实验的目的 1、学习在VC++环境下编辑调试C语言程序的方法。 2、掌握在C语言中的各种数据类型，以及如何定义整型、实型、字符型的变量，并进 行赋值的方法。 3、掌握顺序程序的思路，特别是赋值语句的使用方法。 4、掌握各种类型数据的输入输出方法的正确应用，熟悉各种格式控制符的作用。 5、学会在选择结构中正确应用关系表达式及逻辑表达式。 6、熟练掌握if语句和switch语句的使用。 7、学会选择结构问题算法的编制与调试应用。 8、熟练掌握while语句、do-while语句和for语句实现循环的方法。 9、学会循环问题的编制与调试、运行。 二、实验内容与要求 本实验涵盖顺序、选择、循环三部分程序设计的应用，要求每部分完成两个问题的源代码的编辑、编译、连接与运行，最终产生相关的运行结果，按规定要求提交相应的实验报告。具体要求完成的问题如下：（注意：在模板中给出了题的页数与题号，请写正式报告时将书上的题目内容代替页数与题号） （1）P82/2 （2）P84/6 （3）P112/6 （4）P113/9 （5）P140/5 （6）P141/16 三、算法设计思想或程序流程图 （1）设：五年期，三年期，二年期，一年期，活期存款分别为：r5,r2,r3,r0； 第一种，第二种，第三种，第四种，第五种五年期存款的本息和分别为 p1,p2,p3,p4,p5。 则有： p1=p*((1+r5)*5); 一次存5年期 p2=p*(1+2*r2)*(1+3*r3); 先存2年期，到期后将本息再存3年期 p3=p*(1+3*r3)*(1+2*r2); 先存3年期，到期后将本息再存2年期 p4=p*pow(1+r1,5); 存1年期，到期后将本息存再存1年期，连续存5次 p5=p*pow(1+r0/4,4*5); 存活期存款。活期利息每一季度结算一次 再将所得数据一一输出即可。 (2) 先分别把c1,c2,c3,c4,c5分别赋初值为c,h,I,n,a. 想要让它们的字母分别增加四位。只需将它们的ASCII码增加4个数就可以。便有 c1=c1+4; c2=c2+4 c3=c3+4; c4=c4+4; c5=c5+4;再将所得值以字符型输出便可 （3）输入x，用if语句判断X的值的范围。X<1将x的值赋给y并输出。 除此情况之外（x>1）再进行分类。若x<10则y=2*x-1。除此情况之外，y=3*x-11. （4）先判断它的位数。如果这个数大于9999则输出5；排除这种情况，大于999则输出4…以此类推。 分别输出每一位数字：几位数字便除以此位数的最小值。如9999便除以1000，由于都是整型，便得到9。依次除下去。得到的各位整数在赋给各个变量，反序输出。 （5）用tn=tn+a语句代表赋值后的tn为i个 a组成数的值 用 sn=sn+tn语句代表赋值后的sn为多项式前i项之和 用while语句实现在I数据结构试题集(包含答案 完整版)
C语言程序设计 实验报告1顺序结构
顺序结构选择结构和循环结构的程序设计典型例题分析与解答
数据库复习题汇总
试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
四种基本的存储结构
《数据结构》填空作业题(答案)
实验3选择结构程序设计
数据结构复习要点(整理版).docx
数据结构课后标准答案
实验一 顺序结构程序设计
第3章顺序结构程序设计练习题及答案
数据结构C语言版 串的定长顺序存储表示和实现
数据结构习题(包含全部答案解析)
顺序、选择、循环三种基本结构程序设计.
相关文档
- 实验3--最简单的C程序设计——顺序程序设计
- 第3章 顺序结构程序设计
- 01顺序结构程序设计
- C语言程序设计顺序结构程序设计举例
- 基本语句与顺序结构程序设计
- 实验三 顺序结构程序设计实验报告
- c3顺序程序设计
- 顺序、选择、循环三种基本结构程序设计.
- c程序设计第三版习题参考解答(全)
- c语言顺序结构实验报告
- 顺序、选择、循环三种基本结构程序设计
- C语言程序设计 实验报告1顺序结构
- VB顺序结构程序设计实验报告
- 实验3 最简单的C程序设计——顺序程序设计(实验指导书)
- 实验三 选择结构程序设计
- 实验一 顺序结构程序设计
- 专升本C语言程序设计模拟试卷C3
- 顺序结构程序设计练习题
- C3-三种基本结构的程序设计
- 程序设计的三大结构