求助一数据结构问题 数据结构迷宫问题
一个数据结构问题C语言版
这种问题 其实可以在百度上搜出来的 帮你搜到 看看吧：
队列 是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列具有先进先出（FIFO）的特点。
队列空的条件： front = rear
队列满的条件： rear = MAXSIZE
队列可以用数组Q[1…m]来存储，数组的上界m即是队列所容许的最大容量。在队列的运算中需设两个指针：head：队头指针，指向实际队头元素的前一个位置tall：队尾指针，指向实际队尾元素所在的位置一般情况下，两个指针的初值设为0，这时队列为空，没有元素。图1 ( a)画出了一个由6个元素构成的队列，数组定义Q[1…10]。Q(i) i=3,4,5,6,7,8头指针head＝2，尾指针tail＝8。队列中拥有的元素个数为:L=tail-head现要让排头的元素出队，则需将头指针加1。即head=head+1这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。见图1 (b)。如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q(9)入队，见图1 (c)。当队尾已经处理在最上面时，即tail=10，如果还要执行入队操作，则要发生"上溢"，但实际上队列中还有三个空位置，所以这种溢出称为"假溢出"。
克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为1。在结构上采用这种技巧来存储的队列称为循环队列
循环队的入队算法如下：
1、tail=tail+1；
2、若tail=n+1，则tail=1；
3、若head=tail尾指针与头指针重合了，表示元素已装满队列， 则作上溢出错处理；
4、否则，Q(tail)=X，结束（X为新入出元素）。
队列和栈一样，有着非常广泛的应用。
操作 类型 作用 返回值 例子
length(s) 函数 求字符串s的长度 整型 s:='123456789';
l:=length(s);{l的值为9}
copy（s,w,k) 函数 复制s中从w开始的k位 字符串 s:='123456789';
s1:=copy(s,3,5);{s1的值是'34567'}
val(s,k,code) 过程 将字符串s转为数值，存在k中；code是错误代码 var s:string;k,code:integer;
begin
s:='1234';
val(s,k,code);
write(k);{k=1234}
str(i,s) 过程 将数值i转为字符串s i:=1234;
str(i,s);
write(s);{s='1234'}
Delete(s,w,k) 过程 在s中删除从第w位开始的k个字符 s := 'Honest Abe Lincoln';
Delete(s,8,4);
Writeln(s); { 'Honest Lincoln' }
Insert(s1, S, w) 过程 将s1插到s中第w位 S := 'Honest Lincoln';
Insert('Abe ', S, 8); { 'Honest Abe Lincoln' }
Pos(c, S) 函数 求字符c在s中的位置 整型 S := ' 123.5';
i :=Pos(' ', S);{i的值为1}
+ 运算符 将两个字符串连接起来 s1:='1234';
s2:='5678';
s:=s1+s2;{'12345678'}
一道数据结构 时间复杂度的题目，求助！
首先要弄清楚 O 记号是什么意思，用它来表示一个算法运行时间的渐近上界，对于函数g（n），用O（g（n））表示一个函数集合。
算法导论书上有这样的定义：O(g(n)) = {f(n): 存在正整数c和n0，使对所有的n>=n0,有0<=f(n)<=cg(n)}
上面的看不懂也可以忽略，你只需要知道一个渐近正函数中的低阶项在决定上下界时可以被忽略，因为当n很大时它们就相对地不重要了，指数最高项很小的一部分就足已超越所有的低阶项。同样最高阶项的常系数也可以忽略，举个例子，要求O（f（n）），其中f（n）=an²+bn+c
a,b,c为常数，且a>0,怎么求呢，就是按上面所说的求，舍掉低阶项并忽略常数项就得出
f(n) = O（n²）
所以你上面的题目
f(n) = O(n³)
O(g(n)) = O(n³)
h(n) = O(n的1.5次方)
O(nlogn) = O(nlogn)
所以1 式成立 2式不成立
数据结构有难题
1、下列数据中，（ D ）是非线性的数据结构。
A、线 B、队列 C、串 D、图
2、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。
A、一定是不连续的 B、必须是连续的
C、部份地址须是连续的 D、连续或不连续都可以
3、树最适合用来表示（ C ）
A、有序元素 B、无序元素
C、元素之间具有分支层次关系的数据 D、元素之间无联系的元素
4、线性表是具有n个（ C ）的有限序列（n>0）。
A、表元素 B、字符 C、数据元素 D、数据项
5、循环链表H的尾结点P的特点是（ A ）。
A、P^.NEXT：==H B、P^.NEXT：==H^.NEXT C、P：==H D、P:=H^.NEXT
6、对于栈操作数据的原则是（ C ）。
A先进先出 B、后进先出 C、后进后出 D、不分顺序
7、有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）
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
8、下面关于串的叙述中，哪一个是不正确的？（ D ）
A、串是字符的有限序列 B、串既可以采用顺序存储，也可以采用链式存储
C、模式匹配是串的一种重要运算 D、空串是由空格构成的串
9、一个有n个顶点的无向完全图有（ C ）条边。
A、n B、n(n-1) C、n(n-1)/2 D、n(n+1)
10、冒泡排序是属于（ C ）
A、插入 B、选择 C、交换 D、基数
11、要连通具有n个顶点的有向图、至少需要（ A ）条边。
A、n-1 B、n C、n+1 D、n*(n-1)/2
12、当采用索引表查找时，数据的组织方式为（ C ）
A、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大
（或最小）的数据组成索引块
C、数据分成若干块，每块内数据有序，每块内最朋（或最小）的数据组成索引块
D、数据分成若干块，每块（除最后一块外）中数据个数需相同
13、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）
A、求子串 B、联接 C、匹配 D、求串长
14、假设以行序为主序存储二维数据组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。
A、808 B、818 C、1010 D、1020
15、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）
A、9 B、11 C、15 D、不确定
16、图中有关路径的定义是（ A ）。
A、由顶点和相邻顶点序偶构成的边所形成的序列
B、由不同顶点所形成的序列
C、由不同边所形成的序列 D、上述定义都不是
17、设有向图的顶点个数为n，则该图最多有（ A ）条边。
A、(n-1)n B、n(n-1)/2 C、n(n+1) D、n2
18、适用于折半查找的表的存储方式及元素排列要求为（ C ）
A、链接方式存储，元素无序 B、链接方式存储，元素有序
C、顺序方式存储，元素无序 D、顺序方式存储，元素有序
19、在下面的排序方法中，辅助空间为0（n）的是（ D ）。
A、希尔排序 B、堆排序 C、选择排序 D、归并排序
20、链表不具有的特点是（ B ）
A、插入、删除不需要移动元素 B、可随机防问任一元素
B、不必事先估计存储空间 D、所需空间与线性长度成正比
哪个题不明白的话可以先查查课本，课本上都有。
谁给我详细讲一下关于数据结构
1．1 数据结构的概念
数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。
1.1.1 为什么要学习数据结构
在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。例如，求解梁架结构中应力的数学模型的线性方程组，该方程组可以使用迭代算法来求解。
由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。下面所列举的就是属于这一类的具体问题。
[例1] 学生信息检索系统。当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如图1.1所示。由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定姓名）对学生信息文件进行查询。
诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种简单的线性关系，这类数学模型可称为线性的数据结构。
[例2] 八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。如图1.2所示（为了描述方便，将八皇后问题简化为四皇后问题）。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。
[例3] 教学计划编排问题。一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图1.3所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边<vi，vj>，则表示课程i必须先于课程j进行。
由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。
学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。
1.1.2 有关概念和术语
在系统地学习数据结构知识之前，先对一些基本概念和术语赋予确切的含义。
数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。计算机科学中，所谓数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。
数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，学生信息检索系统中学生信息表中的一个记录、八皇后问题中状态树的一个状态、教学计划编排问题中的一个顶点等，都被称为一个数据元素。
有时，一个数据元素可由若干个数据项（Data Item）组成，例如，学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫做初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割的最小单位；另一种叫做组合项，如学生的成绩，它可以再划分为数学、物理、化学等更小的项。通常，在解决实际应用问题时是把每个学生记录当作一个基本单位进行访问和处理的。
数据对象（Data Object）或数据元素类（Data Element Class）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A和顶点B各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。
数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性，通常有下列四类基本的结构：
⑴集合结构。在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。
⑵线性结构。该结构的数据元素之间存在着一对一的关系。
⑶树型结构。该结构的数据元素之间存在着一对多的关系。
⑷图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。