数据结构C语言版_单链栈
/*
数据结构C语言版单链栈
编译环境：Dev-C++ 4.9.9.2
日期： 2011年2月12日
*/
#include <stdio.h>
#include <malloc.h>
typedef int SElemType; // 定义栈元素的类型
typedef SElemType ElemType; // 栈结点类型和链表结点类型一致
// 线性表的单链表存储结构
typedef struct LNode
{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
typedef LinkList LinkStack; // LinkStack是指向栈结点的指针类型
// 构造一个空的线性表L
int InitList(LinkList *L)
{
/*
产生头结点L,并使L指向此头结点，头节点的数据域为空，不放数据的。void * malloc(size_t)
这里对返回值进行强制类型转换了，返回值是指向空类型的指针类型。
*/
(*L) = (LinkList)malloc( sizeof(struct LNode) );
if( !(*L) )
exit(0); // 存储分配失败
(*L)->next = NULL; // 指针域为空
return 1;
}
// 销毁线性表L，将包括头结点在内的所有元素释放其存储空间。
int DestroyList(LinkList *L)
{
LinkList q;
// 由于单链表的每一个元素是单独分配的，所以要一个一个的进行释放
while( *L )
{
q = (*L)->next;
free( *L ); //释放
*L = q;
}
return 1;
}
/*
将L重置为空表，即将链表中除头结点外的所有元素释放其存
储空间，但是将头结点指针域置空，这和销毁有区别哦。不改变L，所以
不需要用指针。
*/
int ClearList( LinkList L )
{
LinkList p, q;
p = L->next; // p指向第一个结点
while( p ) // 没到表尾则继续循环
{
q = p->next;
free( p ); //释放空间
p = q;
}
L->next = NULL; // 头结点指针域为空，链表成了一个空表
return 1;
}
// 若L为空表（根据头结点L->next来判断，为空则是空表），则返回1，否则返回0。int ListEmpty(LinkList L)
{
if( L->next ) // 非空
return 0;
else
return 1;
}
// 返回L中数据元素个数。
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L->next; // p指向第一个结点
while(p) // 没到表尾，则继续循环
{
i++;
p=p->next;
}
return i;
}
// 返回表头元素的值
int GetFirstElem(LinkList L,ElemType *e)
{
LinkList p=L->next; //第一个结点给p
if(!p) // 空表
return 0;
else // 非空表
*e=p->data;
return 1;
}
// L的头部插入新的数据元素e,作为链表的第一个元素
int HeadInsert(LinkList L,ElemType e)
{
LinkList s;
s=(LinkList)malloc(sizeof(struct LNode)); // 生成新结点s->data=e; // 给结点赋值
s->next=L->next; // 插在表头
L->next=s;
return 1;
}
// 删除L的第一个数据元素，并由e返回其值
int DeleteFirst(LinkList L,ElemType *e)
{
LinkList p=L->next;
if(p)
{
*e=p->data;
L->next=p->next;
free(p);
return 1;
}
else
return 0;
}
#define InitStack InitList // InitStack()
与InitList()作用相同，下同
#define DestroyStack DestroyList
#define ClearStack ClearList
#define StackEmpty ListEmpty
#define StackLength ListLength
#define GetTop GetFirstElem
#define Push HeadInsert
#define Pop DeleteFirst
// 依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败int ListTraverse(LinkList L,void(*vi)(ElemType))
{
LinkList p=L->next;
//对所有元素调用函数vi
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
return 1;
}
// 从栈底到栈顶依次对栈中每个元素调用函数visit()
int StackTraverse(LinkStack S,void(*visit)(SElemType))
{
SElemType e;
LinkStack temp,p=S;
InitStack(&temp); // 初始化temp栈
while(p->next)
{
GetTop(p,&e);
Push(temp,e);
p=p->next;
}
ListTraverse(temp,visit);
return 1;
}
void print(SElemType c)
{
printf("%d ",c);
}
int main()
{
int j;
LinkStack s;
SElemType e;
if(InitStack(&s))
for(j=1;j<=5;j++)
Push(s,2*j);
printf("栈中的元素从栈底到栈顶依次为: ");
StackTraverse(s,print);
Pop(s,&e);
printf("弹出的栈顶元素为%d\n",e);
printf("栈空否: %d(1:空 0:否)\n",StackEmpty(s));
GetTop(s,&e);
printf("当前栈顶元素为%d，栈的长度为%d\n",e,StackLength(s)); ClearStack(s);
printf("清空栈后，栈空否: %d(1:空 0:否)，栈的长度为%d\n", StackEmpty(s),StackLength(s));
printf("是否销毁栈了: %d(1:是 0:否)\n",DestroyStack(&s));
system("pause");
return 0;
}
/*
输出效果：
栈中的元素从栈底到栈顶依次为: 2 4 6 8 10
弹出的栈顶元素为10
栈空否: 0(1:空 0:否)
当前栈顶元素为8，栈的长度为4
清空栈后，栈空否: 1(1:空 0:否)，栈的长度为0 是否销毁栈了: 1(1:是 0:否)
请按任意键继续. . .
*/
数据结构C语言版期末考试试题(有答案)
“数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均
数据结构(C语言版)期末复习
数据结构（C语言版）期末复习汇总 第一章绪论 数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。 数据结构分为：逻辑结构、物理结构、操作三部分 逻辑结构：集合、线性结构、树形结构、图（网）状结构 物理结构（存储结构）：顺序存储结构、链式存储结构 算法：是为了解决某类问题而规定的一个有限长的操作序列。 算法五个特性：有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准（4个）：正确性、可读性、健壮性、高效性及低存储量 语句频度的计算。 算法的时间复杂度： 常见有：O(1)，O(n)，O(n2)，O(log2n)，O(nlog2n)，O(2n) 第二章线性表 线性表的定义和特点： 线性表：由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度，n=0时称为空表。 非空线性表或线性结构，其特点： （1）存在唯一的一个被称作“第一个”的数据元素； （2）存在唯一的一个被称作“最有一个”的数据元素； （3）除第一个之外，结构中的每个数据元素均只有一个前驱； （4）除最后一个之外，结构中的每个数据元素均只有一个后继。 顺序表的插入：共计n个元素，在第i位插入，应移动（n-i+1）位元素。 顺序表的删除：共计n个元素，删除第i位，应移动（n-i）位元素。 线性表的两种存储方式：顺序存储、链式存储。 顺序存储 概念：以一组连续的存储空间存放线性表； 优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑； 缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充； 操作：查找、插入、删除等 查找： ListSearch(SqlList L,ElemType x,int n) { int i; for (i=0;i 第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< 《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法； 队列链式存储结构下的基本算法； 实验内容： 第一题链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写主函数进行测试。 程序代码： 第一题： （1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/ 《数据结构与算法》复习题 一、选择题。 1在数据结构中，从逻辑上可以把数据结构分为 C 。 A ?动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2?数据结构在计算机内存中的表示是指_A_。 A .数据的存储结构B.数据结构 C .数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的A结构。 A .逻辑 B .存储C.逻辑和存储 D .物理 4.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_C A .数据的处理方法 B .数据元素的类型 C.数据元素之间的关系 D .数据的存储方法 5.在决定选取何种存储结构时，一般不考虑A A .各结点的值如何C.对数据有哪些运算 B .结点个数的多少 D .所用的编程语言实现这种结构是否方 6.以下说法正确的是D A .数据项是数据的基本单位 B .数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D .一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ，算法分析的两个主要方面是 A 。 (1) A .找出数据结构的合理性B.研究算法中的输入和输出的关系 C .分析算法的效率以求改进C.分析算法的易读性和文档性 (2) A .空间复杂度和时间复杂度B.正确性和简明性 &下面程序段的时间复杂度是0( n2) s =0; for( I =0; i 链表专题复习 数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个元素大小的数组，有时需要5 0个数组元素的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。 我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。 链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面只介绍单向链表。 7.4.1 单链表 图7 - 3是单链表的结构。 单链表有一个头节点h e a d，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为N U L L。 图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。 看一下链表节点的数据结构定义： struct node { int num; struct node *p; } ; 在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。 在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。 ?单链表的创建过程有以下几步： 1 ) 定义链表的数据结构。 2 ) 创建一个空表。 3 ) 利用m a l l o c ( )函数向系统申请分配一个节点。 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; 数据结构C语言版顺序表和单链表的逆置 公司标准化编码 [QQX96QT-XQQB89Q8-NQQJ6Q8-MQM9N] 实验1-1 顺序表的逆置操作 程序原码 #include<> // 创建顺序表，确定元素个数，插入各个元素，逆置列表。#include<> #include<> #define max_list_size 100 //定义给顺序表分配空间大小 typedef struct{ int *elem; int length; }list_node; //指向顺序表首地址的结构体单元 list_node L; //这里使用了全局变量，在所有的函数里可以随意修改其值int list[max_list_size]; void init(); // 初始化操作 void inversion(); // 倒置部分 void creat(); // 建表部分 void display(); // 显示部分 //*************主函数****************** int main() { init(); creat(); printf("\n您输入的顺序表的结点数: \n"); display(); inversion(); printf("\n倒置顺序表的结点数: \n"); display(); } //*************初始化操作分配空间****************** void init() { = (int *) malloc (max_list_size * sizeof(int) ); if (! { printf("顺序表已满"); exit(-1); } = 0; } //*************以下为建表部分****************** void creat(){ int a, b, i; printf("请输入顺序表的结点数: "); scanf("%d", &a); if(a<=0){ 数据结构练习第三章栈和队列 一、选择题 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．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include } 实验 1-1 顺序表的逆置操作 程序原码 // 创建顺序表，确定元素个数，插入各个元素，逆置列表。 #include 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 《数据结构(C语言版)》复习重点 重点在二、三、六、七、九、十章，考试内容两大类：概念，算法 第1章、绪论 1. 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 3. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 其4类基本结构：集合、线性结构、树形结构、图状结构或网状结构 4. 逻辑结构：是数据元素之间的逻辑关系的描述。 5. 物理结构（存储结构）：是数据结构在计算机中的表示（又称映像）。 其4种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构6. 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 其5个重要特性：有穷性、确定性、可行性、输入、输出 7. 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n))；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。例如： (a) {++x;s=0;} (b) for(i=1;i<=n;++i){++x;s += x;} (c) for(j=1;j<=n;++j) for(k=1;k<=n;++k){++x;s += x;} 含基本操作“x增1”的语句的频度分别为1、n和n2，则这3个程序段的时间复杂度分别为O(1)、O(n)和O(n2)，分别称为常量阶、线性阶和平方阶。还可呈现对数阶O(log n)、指数阶O(2的n次方)等。 8. 空间复杂度：算法所需存储空间的度量记作，S(n)=O(f(n))。 第2章、线性表 1. 线性表：是最常用最简单的一种数据结构，一个线性表是n个数据元素的有限序列。 2. 线性表的顺序存储结构：是用一组地址连续的存储单元依次存储线性表的数据元素。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻，可以随机存取表中任一元素。 存储位置计算：假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，线性表的第i个数据元素ai的存储位置为LOC(ai)=LOC(a1)+(i-1)*L 式中LOC(a1)是线性表第一个元素a1的存储位置，通常称做线性表的起始位置或基地址。 3. 线性表的链式存储结构：是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。 实验二栈和队列 一、实验目的 1. 掌握栈的顺序表示和实现 2. 掌握队列的链式表示和实现 二、实验内容 1. 编写一个程序实现顺序栈的各种基本运算。 2. 实现队列的链式表示和实现。 三、实验步骤 1. 初始化顺序栈 2. 插入元素 3. 删除栈顶元素 4. 取栈顶元素 5. 遍历顺序栈 6. 置空顺序栈 7. 初始化并建立链队列 8. 入链队列 9. 出链队列 10. 遍历链队列 四、实现提示 1. /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->top 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include /*单链表的各种操作*/ #include struct LNode *head,*q; /*定义静态变量*/ int select,x1,x2,x3,x4; int i,n; int m,g; char e,y; setnull(&head); /*建设链表并设置为空表*/ printf("请输入数据长度: "); scanf("%d",&n); for(i=1;i<=n;i++) { printf("将数据插入到单链表中: "); scanf("%d",&y); insert(&head,y,i); } /*插入数据到链表*/ display(&head); /*显示链表所有数据*/ printf("select 1 求长度 length()\n"); printf("select 2 取结点 get()\n"); printf("select 3 求值查找 locate()\n"); printf("select 4 删除结点 delete()\n"); printf("select 0 退出\n"); printf("input your select: "); scanf("%d",&select); 实验名称：实验一单链表的基本操作 实验目的 熟练掌握线性表两类存储结构的描述方法。 实验内容 从键盘读入若干个整数，建一个整数单链表，并完成下列操作： （1）打印该链表； （2）在链表中插入一个结点，结点的数据域从键盘读入，打印该链表； （3）在链表中删除一个结点，被删结点的位置从键盘读入，打印该链表； （4）在链表中做查找：从键盘读入要查找的整数，将该整数在链表中的位置打印出来，若要查找的整数不在链表中，返回一个信息。 算法设计分析 （一）数据结构的定义 单链表存储结构定义为： struct Node; typedef struct Node * pnode; struct Node { int info; pnode link; }; typedef struct Node * LinkList; （二）总体设计 程序由主函数、创建单链表函数、链表长度函数、链表打印函数、插入正整数函数、删除函数、查询函数组成。其功能描述如下： （1）主函数：调用各个函数以实现相应功能 int main(void) //主函数 { printf("单链表的基本操作实验：\n"); struct list *pnode; pnode = creat(); //创建 print(pnode); //输出 insert(pnode); //插入 print(pnode); //输出 _delete(pnode); //删除 print(pnode); //输出 _located(pnode); //查找 print(pnode); //输出 return 0 ; } （三）各函数的详细设计： Function1: struct list *creat()//创建链表；完整版数据结构习题集第3章栈和队列
数据结构_实验三_栈和队列及其应用
(完整版)数据结构(c语言版)期末考试复习试题
数据结构堆栈与队列实验报告
数据结构c语言版期末考试复习试题
C语言链表专题复习
数据结构第三章栈和队列3习题
数据结构C语言版顺序表和单链表的逆置
数据结构练习 第三章 栈和队列
数据结构栈和队列实验报告.doc
(数据结构C语言版)顺序表和单链表的逆置
数据结构栈和队列习题及答案
《数据结构(C语言版)》复习重点要点
数据结构栈和队列
数据结构栈和队列实验报告
数据结构C语言版单链表源代码
数据结构(C语言)单链表的基本操作
- C语言-链表(课堂PPT)
- 数据结构(c语言版)
- 单链表数据结构C语言
- C语言链表专题复习
- 数据结构(C语言)单链表的基本操作
- 数据结构课后习题答案详解(C语言版_严蔚敏) 2
- C语言单链表实现19个功能完全详解
- 严蔚敏版数据结构建立学生信息单链表C语言版适合VC++
- (完整版)数据结构(c语言版)期末考试复习试题.docx
- 数据结构实验报告(C语言)单链表的基本操作
- 数据结构C语言版 循环链表表示和实现
- 数据结构(C语言)考试重点必背
- 单链表数据结构C语言
- 数据结构(第4版)习题及实验参考答案 数据结构复习资料完整版(c语言版)
- (完整版)数据结构(c语言版)期末考试复习试题
- 链表(数据结构C语言写法) 完全版
- 数据结构c语言章节练习题
- 数据结构单链表及插入删除C语言
- C语言链表专题复习
- 数据结构C语言单链表建立、输出、倒置、倒置输出