数据结构线性表相关考研总结表

线性表特点顺序表

链式表

单链表双链表循环单链表循环双链表静态链表

1、元

素个

数有

限

2、逻

辑上

有序

3、数

据类

型都

相同

特

点

1、物理和逻辑上均相邻

2、随机存取访问（优）

3、插入删除操作不便（缺）

1、以链建立逻辑关系，即物理上不要求相邻

2、删除插入操作容易（相对）

3、非随机存取

4、不能直接找到表中某个节点，需从头遍历依次查找

5、多了一个后继指针

操

作

（

时

间

复

杂

度

分

析

）

插入

最好情况最坏情况平均头插尾插O(1)

（若只知道待删

序号则为O(n)）

循环单链表分为带尾指针的和不带尾指针的，区别

是前者有头指针后者无，故前者访问头节点时只能顺序

依次访问，后者直接访问。

表尾插入

O(1)

表头插入

O(n)

O(n)逆序

O(n)

顺序

O(n)

删除

删除表尾

O(1)

删除表头

O(n)

O(n)O(n)

O(1)（一般情况

比单链表方便）

查找

按

值O(1)O(n)O(n)O(n)

补充：

按

序O(1)O(n)

备

注

带头节点和不带头节点的单链表的区别：前者头指针指向头节点的位置；后者头指针指向第一个元素节点的位置

栈队列特点后进先出先进先出

存储结构

顺序存储链式存储顺序存储链式存储

双端队列顺序栈共享栈链栈顺序实现循环队列链队列

特征栈顶指针top，使

用一组连续的存

储单元

共用栈底，向中

间延伸

便于共享存储空间、

插入和删除，不会出

现上溢

头指针front指向队头

元素，尾指针rear指

向队尾元素下一位置

队首指针

Q.front=MaxSize-1后

再前进到0，取余运算

同时带有队头指

针和队尾指针的

单链表，一般用

带头结点的单链

表表示，适合于

数据元素变动较

大的情形，不会

产生溢出

允许两端都

可以进行入

队和出队操

作的队列，按

个端口功能

的受限不同

又分为输入

受限的双端

队列和输出

受限的双端

队列

初始状态S.top==-1Top0=-1&top1=

MaxSize

Q.front==Q.rear==0Q.front=Q.rear=0

入栈（队）栈顶指针先加1再送值到栈顶元素先送值到队尾元素再

将队尾指针加1

Q.front=(Q.front+1)%

MaxSize

出栈（队）先取栈顶元素值再栈顶指针减1先取队头元素值再将

队头指针加1

Q.rear=(Q.rear+1)%Ma

xSize

判空条件S.top==-1Top0=-1&top1=

MaxSize

Q.front==Q.rear==0Q.front==Q.rear

判满条件S.top==MaxSize-1Top1-top0=1

无法判满，出现假溢出(Q.rear+1)%MaxSize== Q.front（以牺牲一个单元为代价）

栈（队）

长S.top+1

(Q.rear+MaxSize-Q.fro

nt)%MaxSize

C语言数据结构线性表的基本操作实验报告

实验一线性表的基本操作 一、实验目的与基本要求 1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。 2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。 3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4．掌握运用C语言上机调试线性表的基本方法。 二、实验条件 1．硬件：一台微机 2．软件：操作系统和C语言系统 三、实验方法 确定存储结构后，上机调试实现线性表的基本运算。 四、实验内容 1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。 五、附源程序及算法程序流程图 1.源程序 （1）源程序(实验要求1和3) #include #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct arr {

数据结构试题及答案

数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放

该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i

(完整版)独立主格结构

英语中的独立主格结构 独立主格结构是由一个相当于主语的名词或代词加上非谓语动词、形容词、副词或介词短语构成的一种独立主格成分。With( without) 的复合结构可看作是独立主格结构的一种形式。 一、独立主格结构的特点 1）独立主格结构的逻辑主语与句子的主语不同，它独立存在。 2）名词或代词与后面的分词，形容词，副词，不定式，介词等是主谓关系。 3）独立主格结构一般有逗号与主句分开。 The test finished, we began our holiday. = When the test was finished, we began our holiday. 4）当表示人体部位的词做逻辑主语时，及物动词用现在分词，不及物动词用过去分词 二、独立主格结构的构成: 名词普通格或代词主格+ 现在分词/过去分词/不定式/名词/形容词/副词/介词短语。 1．名词（或代词）+ 现在分词 现在分词表示前面的名词或代词主动进行的动作或状态。 He seating himself at the desk, his mother began to tell him a story. Everyone being ready, the teacher began his class. The food being cooked, the boy was watching TV. 注意：现在分词being或having been在独立主格结构中可以省略。 The weather（being）fine, we decided to go on an outing. 独立主格结构中的being在下列两种情况下一般不能省略， 一是在“There being + 名词”结构中，There being no bus, we had to walk home. 二是在逻辑主语是代词的情况下。It being Sunday, all the offices are closed. 2．名词（或代词）+ 不定式（短语）不定式表示将来的动作。 He suggested going for a picnic, Mary to provide the food. Many flowers and grass to be planted, our newly-built school will look even more beautiful. 3．名词（或代词）+ 过去分词 过去分词表示前面的名词或代词被动完成的动作。 The girls lay on her back, her hands crossed under her head. The workers worked still harder, their living conditions greatly improved. He was listening attentively in class, his eyes fixed on the blackboard. 4．名词（或代词）+ 形容词（短语） 形容词（短语）在独立主格结构中说明前面名词或代词的性质、状态 The floor wet, we had to stay outside for a while. He turned to me, his eyes sleepy. 5．名词（或代词）+ 副词 副词在独立主格结构中也多是说明名词或代词的状态。 The meeting over, we all went home. School over, we all went home. 6．名词（或代词）+ 介词短语 A robber burst into the room, knife in hand. He left the office, tears in eyes. 注意：在“逻辑主语+介词短语”构成的独立主格结构里，当介词是in时，其前后的两个名词均不加任何修饰成分。但with 的复合结构不受此限制。例如：The teacher came in, with a book in his hand.

数据结构_实验1_线性表的基本操作

实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题

要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE;

数据结构线性表2答案

习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i

独立主格结构详细总结(附习题)

独立主格结构的用法说明与注意点 一、有关独立主格结构的基本概念 独立主格结构是一个名词或代词（作为逻辑主语），加上一个形容词、副词、介词短语、分词、不定式等在句中作状语。它有以下三个特点： 1. 独立主格结构的逻辑主语与句子的主语不同，它独立存在。 2. 名词或代词与后面的形容词、副词、介词短语、分词、不定式等存在逻辑上的主谓关系。 3. 独立主格结构一般用逗号与主句分开，但与主句之间不能使用任何连接词。 二、独立主格结构的常见形式 独立主格类型1：名词（代词）+现在分词 The question being settled, we went home. 问题解决之后，我们就回家了。 We shall play the match tomorrow, weather permitting. 明天假设天气好，我们就进行比赛。 The monitor being ill, we’d better put the meeting off. 班长病了，我们最好还是延期开会吧。 独立主格类型2：名词（代词）+过去分词 The job finished, we went home. 工作结束后我们就回家了。 The last bus having gone, we had to walk home. 最后一班公车已经走了，我们必须走路回家。 More time given, we should have done the job much better. 如果给我们更多的时间，我们会把工作做得更好。 独立主格类型3：名词（代词）+不定式 Nobody to come tomorrow, we will have to put off the meeting till next week. 如果明天没有人来，我们将把会议推迟到下周。 So many people to help him, he is sure to succeed. 有如此多的人来帮助他，他一定会成功的。 独立主格类型4：名词（代词）+介词短语 The soldiers dashed in, rifle in hand. 士兵们端着枪冲了进来。 A girl came in, book in hand. 一个少女进来了，手里拿着书。 He was waiting, his eyes on her back. 他在等着，眼睛望着她的背影。 独立主格类型5：名词（代词）+形容词或副词 He sat in the front row, his mouth half open. 他坐在前排，嘴半开着。 She sat at the table, collar off, head down, and pen in position, ready to begin the long letter. 她坐在桌前，衣领已解掉，头低了下来，拿好钢笔，准备开始写一封长信。 独立主格类型6：There being +名词（代词） There being nothing else to do, we went home. 没有别的事可做，我们就回家了。 There being no further business, I declare the meeting closed. 没有再要讨论的事了，我宣布散会。 独立主格类型7：It being +名词（代词） It being Christmas, the government offices were closed. 由于圣诞节的缘故，政府机关都休息。 It being a holiday, all the shops were shut. 由于今天是假日，所有商店都关门了。 说明：独立主格结构有时可在其前加上介词with。如： Don’t sleep with the windows open. 别开着窗睡觉。 He stood before his teacher with his head down. 他低着头站在老师面前。 He was lying on the bed with all his clothes on. 他和衣躺在床上。 She came in with a book in her hand. 她手里拿着一本书走了进来。 He fell asleep with the lamp burning. 他没熄灯就睡着了。

数据结构线性表答案

第一章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？

解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。 解：

2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： 2.6 已知L是无表头结点的单链表，且P结点既不是

数据结构实验一题目一线性表实验报告

北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表

2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法

a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;idata=a[i]; r->next=s; r=s; } r->next=NULL; } 时间复杂度：O(n) 3、按位查找 a、伪代码实现: 初始化工作指针p和计数器j，p指向第一个结点，j=1 循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1 若p为空，说明第i个元素不存在，抛出异常 否则，说明p指向的元素就是所查找的元素，返回元素地址 b、代码实现 Node* Linklist::Get(int i)//得到指向第i个数的指针 {Node*p=front->next; int j=1; while(p&&j!=i)//p非空且j不等于i，指针后移 {p=p->next; j++;

数据结构课后习题及答案

填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/

独立主格结构小结

独立主格结构小结 一．独立主格结构含义 独立主格结构，又叫独立结构（absolute construction）。它在句法上游离于句子主体之外，跟主句没有任何句法联系；但在意义上却与主句紧密联系在一起，共同构成一个完整的语义环境。独立主格结构没有主语和谓语，只有逻辑上的主语，因此，它在句法上不是句子，而是一个独立于句子成分之外的独特结构形式。 独立主格结构可置于句首、句尾，用逗号与主句隔开。 二、独立主格结构的形式 独立主格结构可分为两部分，一部分是名词或代词（主格），起着逻辑主语的作用；另一部分由形容词、副词、名词、分词、不定式、介词短语等构成，表示前面名词或代词的状态、状况或动作。 1）名词／代词＋形容词 I heard that she got injured in the accident，my heart full of worry． 我听说她在这场事故中受了伤，内心充满担忧。 He stood silent in the moon-light，his door open． 月光下，门开着，他默默地站立在那。 2）名词／代词＋现在分词 Winter coming，it gets colder and colder．冬天来了，天气越来越冷了。 The rain having stopped ，he went out for a walk．雨停了，他出去散步。 3）名词／代词＋过去分词 More time given，we should have done it much better． 如果给我们更多的时间，我们会做得更好。 The boy stood there，his right hand raised．那个男生站在那里，右手高举。 4）名词／代词（主格）＋不定式 Here are the first two volumes，the third one to come out next month． 这是前两卷，第三卷将于下月问世。 The two boys said good-bye to each other，one to go home，the other to go to his friend's．两个男孩彼此道了别，一个回了家，另一个去了他朋友家。 5）名词／代词十介词短语 The huntsman entered the forest，gun in hand．那位猎人手里提着枪走进了树林。 注意：这里，gun in hand还可以说成with a gun in his hand，但不可以说a gun in hand或gun in his hand。 6）名词／代词十副词 Nobody in，the thief took a lot of things away． 由于没有人，小偷拿走了许多东西。 Lunch over，he left the house．But he was thinking． 午饭结束，他离开屋。但他还在考虑。 7）名词／代词＋名词 He fought the wolf，a stick his only weapon． 他和狼搏斗着，唯一的武器是一根棍棒。 8）There being +名词（代词）如： There being nothing else to do, we went home. 没有别的事可做，我们就回家了。

数据结构实验一顺序表的实现

数据结构实验一顺序表的实现 班级学号分数 一、实验目的： 1.熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现； 2.以线性表的各种操作的实现为重点； 3.通过本次学习帮助学生加深C语言的使用，掌握算法分析方法并对已经设计 出的算法进行分析，给出相应的结果。 二、实验要求： 编写实验程序，上机运行本程序，保存程序的运行结果，结合程序进行分析并写出实验报告。 三、实验容及分析： 1.顺序表的建立 建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 程序如下： 头文件SqList.h的容如下： #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; typedef struct{ ElemType *elem; int length; int listsize; }SqList; Status InitList_Sq(SqList *L) { L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L->elem) return(OVERFLOW); L->length=0; L->listsize=LIST_INIT_SIZE; return OK; } Status CreatList_Sq(SqList *L,int n) { int i; printf("输入%d个整数:\n",n); for(i=0;ielem[i]); return OK; } //以下是整个源程序： #include #include"SqList.h" int main() { int i,n; SqList a; SqList *l = &a; if(InitList_Sq(l)==-2) printf("分配失败"); printf("\n输入要建立的线性表l的长度n:");//输入线性表得长度scanf("%d",&n); l->length=n; printf("线性表的长度是:%d\n",l->length); CreatList_Sq(l,n);//生成线性表 printf("输出线性表l中的元素值：");//输出线性表中的元素 for(i=0;ilength;i++) printf("%7d",l->elem[i]); getchar(); } 程序的运行结果：

数据结构线性表实验报告

《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求：

数据结构试题答案

第一章概论 一、选择题 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

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、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s

5种基本句型和独立主格结构讲解

英语中的五种基本句型结构 一、句型1：Subject (主语) ＋Verb (谓语) 这种句型中的动词大多是不及物动词，所谓不及物动词，就是这种动词后不可以直接接宾语。常见的动词如：work, sing, swim, fish, jump, arrive, come, die, disappear, cry, happen等。如： 1) Li Ming works very hard.李明学习很努力。 2) The accident happened yesterday afternoon.事故是昨天下午发生的。 3）Spring is coming. 4) We have lived in the city for ten years. 二、句型2：Subject (主语) ＋Link. V(系动词) ＋Predicate(表语) 这种句型主要用来表示主语的特点、身份等。其系动词一般可分为下列两类： (1)表示状态。这样的词有：be, look, seem, smell, taste, sound, keep等。如： 1) This kind of food tastes delicious.这种食物吃起来很可口。 2) He looked worried just now.刚才他看上去有些焦急。 (2)表示变化。这类系动词有：become, turn, get, grow, go等。如： 1) Spring comes. It is getting warmer and warmer.春天到了，天气变得越来越暖和。 2) The tree has grown much taller than before.这棵树比以前长得高多了。 三、句型3：Subject(主语) ＋V erb (谓语) ＋Object (宾语) 这种句型中的动词一般为及物动词, 所谓及物动词，就是这种动词后可以直接接宾语，其宾语通常由名词、代词、动词不定式、动名词或从句等来充当。例： 1) He took his bag and left.（名词）他拿着书包离开了。 2) Li Lei always helps me when I have difficulties. (代词)当我遇到困难时，李雷总能给我帮助。 3) She plans to travel in the coming May Day.（不定式）她打算在即将到来的“五一”外出旅游。 4) I don’t know what I should do next. (从句)我不知道下一步该干什么。 注意：英语中的许多动词既是及物动词，又是不及物动词。 四、句型4：Subject(主语)＋Verb(谓语)＋Indirect object(间接宾语)＋Direct object (直接宾语) 这种句型中，直接宾语为主要宾语，表示动作是对谁做的或为谁做的，在句中不可或缺，常常由表示“物”的名词来充当；间接宾语也被称之为第二宾语，去掉之后，对整个句子的影响不大，多由指“人”的名词或代词承担。引导这类双宾语的常见动词有：buy, pass, lend, give, tell, teach, show, bring, send等。如： 1) Her father bought her a dictionary as a birthday present.她爸爸给她买了一本词典作为生日礼物。 2）The old man always tells the children stories about the heroes in the Long March. 老人经常给孩子们讲述长征途中那些英雄的故事。上述句子还可以表达为： 1）Her father bought a dictionary for her as a birthday present. 2）The old man always tells stories about the heroes to the children in the Long March. 五、句型5：Subject(主语)＋Verb (动词)＋Object (宾语)＋Complement(补语) 这种句型中的“宾语＋补语”统称为“复合宾语”。宾语补足语的主要作用或者是补充、说明宾语的特点、身份等；或者表示让宾语去完成的动作等。担任补语的常常是名词、形容词、副词、介词短语、分词、动词不定式等。如： 1）You should keep the room clean and tidy. 你应该让屋子保持干净整洁。（形容词） 2) We made him our monitor.(名词)我们选他当班长。 3) His father told him not to play in the street.(不定式)他父亲告诉他不要在街上玩。

数据结构线性表的主要程序代码

数据结构顺序表的主要代码（LIZHULIN） 1．/***有头结点的单链表的初始化、建立（表头插入、表尾插入）、求长度、插入、删除、输出***/ /***********单链表的初始化、建立、输出*****************/ #include #include typedef struct Lnode { /*定义线性表的单链表存储结构*/ int data; struct Lnode *next; }LinkList; /****************单链表的初始化*************************/ Initlist(LinkList *L) { /*动态申请存储空间*/ L = (LinkList *)malloc(sizeof(struct Lnode));/*建立头结点*/ L->next = NULL; } /*************建立一个带头结点的单链表，在表尾插入***************/ Create_L(LinkList *L,int n) { LinkList *p,*q; int i; Initlist(L); /*单链表初始化*/ q=L; printf("input the value\n"); for(i = n;i>0;--i) { p = (LinkList*)malloc(sizeof(struct Lnode)); scanf("%d",&p->data); /*输入元素值*/ q->next = p; p->next = NULL; q=p; /*插入到表尾*/ } } /* Create_L */ /*************建立一个带头结点的单链表，在表头插入************** Create_L(LinkList *L,int n) { LinkList *p; int i;