数据结构顺序存储结构 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<

else

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<data<<"->";

p=p->next;

}

cout<data;

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()

{

int n;

elemtype x,y;

link *p,*q;

linklist a;

p=a.hcreat();

a.print(p);

cout<<"请输入要删除的元素";

cin>>y;

a.deletel(p,y);

a.print(p);

cout<<"请输入插入位置的元素值（将待插元素插入它的后面）";

cin>>x;

cout<<"请输入待插元素值";

cin>>y;

a.insert(p,x,y);

a.print(p);

cout<<"请输入要修改前、后的元素值";

cin>>x>>y;

a.change(p,x,y);

a.print(p);

cout<<"请输入要查找的元素值";

cin>>x;

q=a.Locate(p,x);

if(q==NULL)

cout<

else

cout<

n=a.count(p);

cout<<"链表中结点个数为:"<

}

实验结果

顺序表

C语言程序设计 实验报告1顺序结构

福建农林大学金山学院实验报告 系(教研室): 专业: 年级: 实验课程: C语言程序设计姓名: 学号: 实验室号:_ 计算机号: 实验时间: 指导教师签字: 成绩: 实验1:顺序结构程序设计 一、实验目的与要求 1.了解Visual C++ 6、0/DEV_C++的基本操作方法 2.掌握C程序设计的基本步骤:编辑、编译、连接与运行 3.掌握各种类型数据的输入输出方法 4.能够编写一个简单的程序 二、实验内容与原理 1、输入并运行一个简单、正确的程序。 # include int main( ) { printf ("This is a c program!\n"); return 0; } 2、要使下面程序的输出语句在屏幕上显示:A,B,34,则从键盘输入的数据格式应为AB34__________ 。 #include int main() { char a, b; int c; scanf("%c%c%d",&a,&b,&c); printf("%c,%c,%d\n",a,b,c); return0; 问题1:要使上面程序的键盘输入数据格式为a=A,b=B,34,输出语句在屏幕上显示的结果也为A,B,34,则应修改程序中的哪条语句？怎样修改？ scanf( “a=%c,b=%c,%d”,&a,&b,&c ); 问题2:要使上面程序的键盘输入数据格式为A,B,34,而输出语句在屏幕上显示的结果为“A”,“B”,34,则应修改程序中的哪两条语句？怎样修改？ scanf( “%c,%c,%d”,&a,&b,&c); printf(“\”%c\”,\”%c\”,%d\n”,a,b,c);

顺序结构选择结构和循环结构的程序设计典型例题分析与解答

顺序结构、选择结构和循环结构的程序设计典型例题分析与解答 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.在顺序表中插入或删除一个元素，需要平均移动( 一半 )元素，具体移动的元素个数与( 插入或删除的位置 )有关。插入时平均 次数（n/2 ）,删除时平均次数（(n-1)/2 ）。 2.有一个含头结点的循环链表，头指针为 head, 则其为空的条件是：( C ) A)head==NULL B)head->next==NULL C)head->next==head 3.在长度为 n 的顺序表的第 i 个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：( A ) A) n – i + 1 B) n – i C) i D) i – 1 4.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( C ) A)顺序表B) 用头指针表示的循环单链表 C) 用尾指针表示的循环单链表D) 单链表 5.设单链表中结点的结构为（data, link）。已知指针 q 所指结点是指针 p 所指结点的直接前驱，若在*q 与*p 之间插入结点*s，则应执行下列哪一个操作？（ B ） A)s->link = p->link;p->link = s;(B) q->link = s;s->link = p; (C) p->link = s->link;s->link = p;(D) p->link = s;s->link = q; 6.设单链表中结点的结构为（data, link）。已知指针 p 所指结点不是尾结点，若在*p 之后插入结点*s，则应执行下列哪一个操作？（B）

A)s->link = p;p->link = s;(B) s->link = p->link;p->link = s; (C) s->link = p->link;p = s;(D) p->link = s;s->link = p; 7.设单链表中结点的结构为（data, link）。若想摘除结点*p 的直接后继，则应执行下列哪一个操作？（A） (A) p->link = p->link->link; (B) p = p->link;p->link = p->link->link; (C) p->link = p->link;(D) p = p->link->link; 8.设单循环链表中结点的结构为（data, link），且 rear 是指向非空的 带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？（D） (A)s = rear;rear = rear->link;delete s; (B)rear = rear->link;delete rear; (C)rear = rear->link->link;delete rear; (D)s = rear->link->link;rear->link->link = s->link; delete s; （rear 指向尾结点，rear->link->link 指向第一个结点，第一个结点变为原来的第二个结点） 9.设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头 结点。若想在指针 p 所指结点之后插入指针 s 所指结点，则应执 行下列哪一个操作？( D )

四种基本的存储结构

四种基本的存储结构 Prepared on 22 November 2020

数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 由此得到的存储表示称为顺序存储结构（Sequential Storage Structure），通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。 （3）索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。

索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是： (关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。 （4）散列存储方法 该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 数据结构三方面的关系

数据结构顺序表的查找插入与删除

一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include #include /*顺序表的定义：*/ #include #define ListSize 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { SeqList L; int i,x; int n=10; /*欲建立的顺序表长度*/ L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i); CreateList(&L,n); /*建立顺序表*/ PrintList(L,n); /*打印顺序表*/ printf("输入要查找的值："); scanf("%d",&x); i=LocateList(L,x); /*顺序表查找*/ printf("输入要插入的位置："); scanf("%d",&i); printf("输入要插入的元素："); scanf("%d",&x); InsertList(&L,x,i); /*顺序表插入*/

实验3选择结构程序设计

《C语言程序设计》实验报告 ---------------------------------------------------------------------------------------------- 实验3选择结构程序设计 一．实验目的 1.了解C语言表示逻辑量的方法（以0代表“假”，以非0代表“真”）。 2.学会正确使用逻辑运算符和逻辑表达式 3.熟练掌握if语句和switch语句； 4.结合程序掌握一些简单的算法。 5.学习调试程序 二．实验内容和步骤 1.基础知识和概念 （1）分析下面程序，掌握关系表达式的运算规则。 #include int main() { char ch='w'; int a=2,b=3,c=1,d,x=10; printf("%d",a>b==c); printf("%d",d=a>b); printf("%d",ch>'a'+1); printf("%d",d=a+b>c); printf("%d",3<=x<=5); printf("%d\n",b-1==a!=c); return 0; } 总结与反思：1.运用关系运算符比较的结果，真为1，假为0；2.注意掌握运 算符的优先顺序；3. (3<=x)<=5结果为真=1，(1==1)!=1结果为假=0 （2）分析运行下面的程序，掌握逻辑表达式的运算规则。 #include int main() { char ch='w';

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 int main() { int a=3,b=5,c=8; if(a++<3&&c--!=0) b=b+1; printf("a=%d\tb=%d\tc=%d\n",a,b,c); return 0; } 总结与反思：该程序中的条件判断表达式“a++<3&&c--!0”是一个逻辑表达式， 关系表达式“a++<3”的值为假，因此后一部分“c--!=0”不再计算。 2.程序改错和填空 （1）给定程序c3-4.c的功能是，对于以下函数： y=x(x<1) y=2x-1(1<=x<10) y=3x-11(x>=10) 用scanf函数输入x的值，求y的值。 #include int main() { int x,y; scanf("%d",&x); if (x<1) y=x; else if (1<=x&&x<10) y=2*x-1; else y=3*x-11; printf("y=%d\n",y); return 0; } 反思与总结：1.在紧跟着if选择语句的条件表达式的圆括号之后没有分号；2.

数据结构复习要点(整理版).docx

第一章数据结构概述 基本概念与术语 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 )

数据结构实现顺序表的各种基本运算(20210215233821)

实现顺序表的各种基本运算 一、实验目的 了解顺序表的结构特点及有关概念，掌握顺序表的各种基本操作算法思想及其实现。 二、实验内容 编写一个程序，实现顺序表的各种基本运算： 1、初始化顺序表； 2 、顺序表的插入； 3、顺序表的输出； 4 、求顺序表的长度 5 、判断顺序表是否为空； 6 、输出顺序表的第i位置的个元素； 7 、在顺序表中查找一个给定元素在表中的位置； 8、顺序表的删除； 9 、释放顺序表 三、算法思想与算法描述简图

主函数main

四、实验步骤与算法实现 #in clude #in clude #defi ne MaxSize 50 typedef char ElemType; typedef struct {ElemType data[MaxSize]; in t le ngth; void In itList(SqList*&L)〃 初始化顺序表 L {L=(SqList*)malloc(sizeof(SqList)); L->le ngth=0; for(i=0;ile ngth;i++) prin tf("%c ",L->data[i]); } void DestroyList(SqList*&L)〃 {free(L); } int ListEmpty(SqList*L)〃 {retur n( L->le ngth==O); } int Listle ngth(SqList*L)〃 {return(L->le ngth); } void DispList(SqList*L)〃 {int i; 释放顺序表 L

实验一 顺序结构程序设计

实验一顺序结构程序设计 一、实验目的 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章顺序结构程序设计练习题及答案

第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））；

数据结构C语言版 串的定长顺序存储表示和实现

#include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define MAXSTRLEN 255 typedef int ElemType; typedef int Status; typedef unsigned char SString[MAXSTRLEN+1]; //串赋值操作 Status StrAssign(SString T,char chars[]){ // 生成一个其值等于chars的串T int i; if(strlen(chars)>MAXSTRLEN) return ERROR; T[0]=strlen(chars); for(i=0;i<=T[0];i++){ T[i+1]=chars[i];} return OK; }//StrAssign //输出串 void StrPrint(SString S){ int i; for(i=1;i<=S[0];i++){ printf("%c",S[i]); } printf("\n"); }//PrnStr //串复制操作 Status StrCopy(SString T,SString S){ // 由串S复制得串T int i; for(i=1;i<=S[0];i++) T[i]=S[i]; T[0]=S[0]; return OK; }//StrCopy //判空操作 Status StrEmpty(SString S){ if(S[0]==0) return OK;

顺序、选择、循环三种基本结构程序设计.

昆明理工大学信息工程与自动化学院学生实验报告 （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 #include int main() {float r5,r3,r2,r1,r0,p,p1,p2,p3,p4,p5; p=1000; r5=0.0585; r3=0.054; r2=0.0468; r1=0.0414; r0=0.0072; p1=p*((1+r5)*5); p2=p*(1+2*r2)*(1+3*r3); p3=p*(1+3*r3)*(1+2*r2); p4=p*pow(1+r1,5); p5=p*pow(1+r0/4,4*5); printf("p1=%f\n",p1); printf("p2=%f\n",p2); printf("p3=%f\n",p3); printf("p4=%f\n",p4);

第八讲：顺序结构程序设计举例

第八讲：顺序结构程序设计举例 所谓的顺序结构就是从头到尾一步步按部就班的执行下去，不会中途出现放弃或者跳转的情况。利用这样的思想实现的程序我们称之为顺序结构程序。在前面学习了许多知识点之后我们就可以开始最基本的顺序结构程序的设计了。 8.1 顺序结构 所谓的顺序结构可以用一个成语形容叫“按部就班”。任何事情都遵循着先做什么，再做什么的思想进行。这样的结构是我们日常生活中最常见的结构。在顺序结构中当一件事情开始后就再也不会停下，直到最后一步完成，整件事情做完为止，中途不会有放弃或者选择性放弃的过程。 8.2 经典算法—数据交换 很多语言的程序设计大多数都是从数据交换这个最经典的算法开始的，所谓的数据交换是将两个同等性质的物质进行对换，例如有两个整数a和b，a = 1,b = 2，在交换之后，使得a = 2,b = 1。 交换的算法是由于变量的性质所决定的，由于变量在同一时刻只能够存储一个数据，因此我们不能直接使用 a = b,b = a的方式对数据进行交换。此时我们就需要想出一些方法，帮助程序实现最正确的交换。 对于任何的数据我们都可以采用“第三变量法”进行交换。所谓的“第三变量法”即借助第三个变量实现对数据的交换，例如对a和b的数据交换，就有： 接下来我们将通过如下示意图对“第三变量法”进行简单的介绍： b

在程序未执行交换前，a = 1,b = 2。在执行交换算法的过程中，首先执行“t = a;”一句，将a中的值1转移到t中暂存，接下来执行“a = b;”一句，将b之中的值2存放到变量a中，a中原先的1被覆盖；最后执行“b = t;”一句，将t中所暂存的原先a的值1存放到变量b中，b中原有的2被覆盖。此时 a = 2,b = 1,t = 1。 当然，读者也可以使用先暂存b的方式对a和b之中的数据进行交换。下面给出该案例的完整代码： [例] 使用“第三变量法”交换a和b之中的数据。 当然对于一些数值型的数据（所谓的数值型数据是指单纯的数字或者ASCII 码），我们也可以直接采用“算数交换法”进行交换。所谓的算数交换法是指利用数值型数据可进行算术运算的特性进行交换。以上例a与b的值交换为例，则有： 假设a = 1,b = 2。首先执行“a = a + b;”，此时a = a + b = 1 +2 = 3，而b = 2；

实验一数据结构顺序表的插入和删除

实验一顺序表的操作 1. 实验题目：顺序表的操作 2.实验目的和要求： 1)了解顺 序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、 删除、查找以及线性表合并 )。 2)通过在 Turbo C ( WinTc ，或 visual stdio6 )实现以上操作的 C 语言 代码。 3)提前了解实验相关的知识(尤其是 C 语 言)。 3.实验内容：(二选一) 1) 顺序表的插入算法, 删除算法, 顺序表的合并算法 2) 与线性表应用相关的实例( 自己选择具体实例) 4.部分参考实验代码： ⑴ 顺序表结构的定义： #include #define MAXLEN 255 typedef int ElemType; typedef struct { ElemType elem[MAXLEN]; int length; }sqList; ⑵ 顺序表前插(在第i 号元素前插入一个新的元素) int ListInsert(sqList *la,int i,int x) { int j; if(i<0||i>la-> length +1) { printf( “ n the value of i is wrong! ” ); return 0; } if(la-> length +1>=MAXLEN) { printf( “ n overflow! ” ); return 0; }

. for(j=la-> length;j>=i;j--) la->list[j+1]=la->list[j]; la->list[i]=x; la-> length ++; return 1; } ⑶ 顺序表删除 int ListDelete(sqList *la,int i) { if(i<0||i>la-> length ) { printf( “ return 0; n”); } for(i;i length;i++) la->list[i-1]=la->list[i]; la-> length --; return 1; } 5.附录：实验预备知识： ⑴ 复习 C 语言中数组的用法。 ⑵ 了解线性表和顺序表的概念，顺序表的定义方法； 线性表是n 个数据元素的有限序列，至于每个数据元素的具体含义，在不同的情况下各不相同。 顺序表是线性表的顺序存储表示，是用一组地址连续的存储单元依次存储线性表的数据元素。 在 C 语言中，顺序表是用数组来实现的。 ⑶ 掌握线性表在顺序存储结构上实现基本操作：查找、插入、删除和 合并的算法。 在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容： 在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果（查到时输出查到的数据，未查到时给出未查到提 示）。 在实现插入的时候，首先要判断该顺序表是否为满，如为满则报错 （此时要注意：顺序表是用数组来实现的，它不能随机分配空 间）；如不为满，则需判断要插入的位置是否合法（例如：如果 一个线性表的元素只有10 个，而要在第0 个元素前插入或在第 11 个元素后插入就为不合法）。其次要注意是前插还是后插，两

数据结构顺序存储结构

数据结构顺序表 第一种方法： #include #define MAX_SIZE 50 typedefintElemType; //自定义类型 typedefstruct { //结构体 ElemTypedata[MAX_SIZE]; intlen; }SqList; /*参数一：顺序表参数二:一个数组参数三：顺序表长度*/ voidcreateSqList(SqList&L,int a[], int n){ for(int i = 0; i < n; i++){ L.data[i]=a[i]; } L.len = n; } //打印输出顺序表 voidprintSqList(SqList L){ printf("打印顺序表:"); for(int i = 0; i

第二种方法： #include #include #define MAX_SIZE 50 typedefintElemType; //自定义类型 typedefstruct { //结构体 ElemTypedata[MAX_SIZE]; intlen; }SqList; /*参数一：顺序表参数二:一个数组参数三：顺序表长度*/ voidcreateSqList(SqList *L,int a[], int n){ for(int i = 0; i < n; i++){ L->data[i]=a[i]; } L->len = n; } //打印输出顺序表 voidprintSqList(SqList *L){ printf("打印表:"); for(int i = 0; i < L->len; i++){ printf("%d ",L->data[i]); } printf("\n"); } int main(){ //初始化一个空表 SqList *L; L=(SqList *)malloc(sizeof(SqList)); L->len=0; int i; //初始化数组 int array[5]; for(i=0;i<5;i++){ array[i]=i; } createSqList(L,array, 5); printSqList(L); }