spfa pascal 队列加邻接表

var

n,m:longint;

dis:array[1..1000,1..1000] of longint;

map:array[1..1000,1..1000] of integer;

du:array[1..1000] of integer;

dd:array[1..1000] of longint;

i,j:longint;

s,t:longint;

a,b,c:longint;

f:array[1..1000] of longint;

procedure haltt;

begin

writeln('You show me the wrong map!');

halt;

end;

procedure spfa;

var

top,tail,i:longint;

t,tot:array[1..1000] of longint;

flag:array[1..1000] of boolean;

x,y:longint;

begin

fillchar(tot,sizeof(tot),0);

fillchar(flag,sizeof(flag),0);

top:=0;tail:=1;t[1]:=s; flag[s]:=true; dd[s]:=0; tot[s]:=1; while top<>tail do

begin

inc(top);

x:=t[top];

flag[x]:=false;

for i:=1 to du[x] do

begin

y:=map[x,i]; //writeln(dd[3]); ////

if dd[x]+dis[x,y]

begin

f[y]:=x;

dd[y]:=dd[x]+dis[x,y];

if not(flag[y]) then

begin

flag[y]:=true;

inc(tail);

t[tail]:=y;

inc(tot[y]);

if tot[y]>n+1 then haltt;

end;

end;

end;

end;

// writeln(tot[3]);

end;

procedure sea(t:longint);

begin

if f[t]<>t then sea(f[t]);

write(t,' ');

end;

begin

//assign(input,'1.in'); reset(input);

for i:=1 to 1000 do begin dd[i]:=maxlongint div 2-1; f[i]:=i; end; readln(s,t);

readln(n,m);

for i:=1 to m do

begin

readln(a,b,c);

dis[a,b]:=c;

//dis[b,a]:=c;

inc(du[a]);

map[a,du[a]]:=b;

//inc(du[b]);

//map[b,du[b]]:=a;

end;

//init;

spfa;

writeln(dd[t]);

sea(t);

//close(input);

end.

单链表的创建、插入和删除

单链表的创建、插入和删除 （数据结构） ——SVS #include #include #include typedef int ElemType; typedef int Status; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; void InitList_Link(LinkList L) //创建空链表 { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; } Status InsertList_Link(LinkList L,int i,ElemType e) //插入链表 { LinkList s,p=L; int j=0; while(p&&jnext;j++;} if(!p||j>i-1)return -1; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return 1; }

Status DeleteList_Link(LinkList L,int i,ElemType e) //删除链表{ LinkList q,p=L;int j=0; while(p->next&&jnext;j++;} if(!(p->next)||j>i-1)return -1; q=p->next; e=q->data; p->next=q->next; free(q); return 1; } void OutPutList_Link(LinkList L) //输出链表 { printf("表中值为："); LinkList p=L->next; while(p) { printf("%d ",p->data); p=p->next; } printf("\n"); } void CreateList_Link(LinkList L,int len) //创建链表 { int i; LinkList s,p=L; for(i=0;idata); s->next=NULL; p->next=s; p=s; } } int main() { int len; LinkList L; ElemType e; L=(LinkList)malloc(sizeof(LNode));

数据结构考研真题 栈和队列

第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p 1,p 2 ,p 3 ，…，p N ,若p N 是n，则 p i 是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素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 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是

第4章栈与队列自测卷答案

head 栈和队列 一、填空题（每空1分，共15分） 1.向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU 中也用队列。 （ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ × ）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 （ × ）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底 分别设在这片内存空间的两端。 （ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分） （B ）1.栈中元素的进出原则是 Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出 （C ）2. 若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，则pi 为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n ，即n 是最先出栈的，根据栈的原理，n 必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n ，则出栈的序列是n ，…，3，2，1。（若不要求顺序出栈，则输出序列不确定） （B ）3.判定一个栈ST （最多元素为m0）为空的条件是 Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0

C语言链表的建立、插入和删除

数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要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 ( )函数向系统申请分配一个节点。 4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新 节点接到表尾。 5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束。 ?单链表的输出过程有以下几步 1) 找到表头。

栈和队列答案

栈和队列 一选择题 1. 对于栈操作数据的原则是（）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ①B ),在作退栈运算时应先判别栈是否( ②A)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j 个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为 p1,p2,p3，…，pN,若pN 是n，则pi 是( )。 A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素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 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2

数据结构课程设计单链表操作汇总

《数据结构课程设计》报告 题目：单链表操作 专业：计算机科学与技术 班级： 单链表操作 针对带头结点的单循环链表，编写实现以下操作的算法函数。

实现要求： ⑴单链表建立函数create：先输入数据到一维数组A[M]中，然后根据一维 数组A[M]建立一个单循环链表，使链表中个元素的次序与A[M]中各元素的次序相同，要求该函数的时间复杂度为O(m)； ⑵定位查找函数Locate：在所建立的单循环链表中查找并返回值为key的 第1个元素的结点指针；若找不到，则返回NULL； ⑶求出该链表中值最大和次大的元素值，要求该算法的时间复杂度为O(m)， 最大和次大的元素值通过指针变量带回，函数不需要返回值； ⑷将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结 点前驱，所有值比key大的结点作为值为key的结点后继，并尽量保持原有结点之间的顺序，要求该算法的时间复杂度为O(m); ⑸设计一个菜单，具有上述处理要求和退出系统功能。 ⒈本人完成的工作： 一、定义结构体：LNode 二、编写以下函数： （1）建立单循环链表 （2）建立定位查找函数 （3）求出链表中最大和次大值 （4）将链表中的值和输入的Key比较，小的作为key前驱结点，大的作为key 的后继结点 三、设计具有上述处理要求和退出系统菜单 ⒉所采用的数据结构：单链表 数据结构的定义： typedef struct Node //定义结点的结构体 { DataType data; //数据域 struct Node *next; //指针域

}LNode; //结点的类型 ⒊所设计的函数 （1）Create(void) LNode *Create(void) //建立单循环链表，链表头结点head作为返回值{ int i,j,n,A[M]; //建立数组A【M】 LNode *head,*p,*move; head=(LNode*)malloc(sizeof(LNode)); //创建空单循环链表head->next=head; move=head; printf("请输入数组元素的个数："); //输入数组 scanf("%d",&n); printf("请输入数组："); for(i=0;idata=A[j]; p->next=move->next; move->next=p; move=move->next; } return head; //返回头指针

线性表、栈、队列

1.线性表的顺序存储结构是一种的存储结构，而链式存储结构是一种___的存储结构。 A．随机存取B．索引存取C．顺序存取D．散列存取 2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 3.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s 结点，则执行____。 A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q; 4.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。 A. s->next=p; p->next=s; B. s->next=p->next; p->next=s; C. s->next=p->next; p=s; D. p->next=s; s->next=p; 5.在一个单链表中，若删除p所指结点的后续结点，则执行____。 A. p->next= p->next->next； B. p= p->next; p->next= p->next->next； C. p->next= p->next; D. p= p->next->next； 6.链表不具备的特点是____ 。 A可随机访问任何一个元素 B 插入、删除操作不需要移动元素 C 无需事先估计存储空间大小 D 所需存储空间与线性表长度成正比 7.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____ 。 A4，3，2，1 B 1，2，3，4 C 1，4，3，2 D 3，2，4，1 8.栈与一般线性表区别主要在方面。 A元素个数 B 元素类型 C 逻辑结构 D 插入、删除元素的位置 9.在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是。 A R=F->next; B R=R->next; C F=F->next; D F=R->next; 10. 数据三种最主要的逻辑结构是线性结构和（）。 A. 线性表、树 B. 树形结构、图状结构 C. 线性表、图 D. 树形结构、堆

链表建立

#include /*这个头文件在动态的建立结点时要用到*/ /* * 这就是表示单链表的一个结点的结构体了， * 简单起见没有使用模板之类的复杂东西。 */ struct Node { /*这个表示结点的值，这里为了简单，就用int型的吧*/ int data; /* * 这是指向结点结构体的一个指针， * 这里用它指向该结点的下一个结点， * 以此使单个的结点形成链表 */ struct Node* next; };/*至此链表的结点就定义完了*/ int main() { /*下面展示如何建立成为一个带头结点的单链表：L={12，13，21，24}*/ struct Node* head = NULL; /*这是链表的头结点*/ struct Node* p = NULL, *q = NULL; /*临时指针，建立链表时会用到*/ /*链表很短，我不用循环，直接建立，可以让你看的更清楚*/ /*建立头结点*/ head = (struct Node*)malloc(sizeof(struct Node)); /*指定结点的值*/ head->data = 12; /*指定下一个结点，现在还没有先给NULL*/ head->next = NULL; /*用q保存刚生成的结点*/ q = head; /*第二个结点，建立的方法和第一个一样*/ p = (struct Node*)malloc(sizeof(struct Node)); p->data = 13; p->next = NULL; /*注意，此时需要调整一下上一个结点的next指针，使各结点可以连接起来*/ q->next = p; q = p; /*第三个结点*/

栈和队列练习题答案

第3章栈和队列练习题答案 一、填空题 1. 线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 二、判断正误 （√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （×）3. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）6. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）7. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （B）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （C）2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ａ．i Ｂ．n-i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （D）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 （Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n E：①1 ②2 ③3 ④0 四、阅读理解 1.【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); x=’c’;y=’k’;

第 3 章 特殊线性表---栈、队列和串

1. 填空 ⑴设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push 后，输出序列是（），栈顶指针为（）。 【解答】23，1003H ⑵栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。 【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间 ⑶（）可作为实现递归函数调用的一种数据结构。 【解答】栈 【分析】递归函数的调用和返回正好符合后进先出性。 ⑷表达式a*(b+c)-d的后缀表达式是（）。 【解答】abc+*d- 【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。 ⑸栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 ⑹循环队列的引入是为了克服（）。 【解答】假溢出 ⑺数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。 【解答】（rear-front+n）% n 【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。 ⑻用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。 【解答】Ｏ(1)，Ｏ(n) 【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。 ⑼串是一种特殊的线性表，其特殊性体现在（）。 【解答】数据元素的类型是一个字符 ⑽两个串相等的充分必要条件是（）。 【解答】长度相同且对应位置的字符相等 【分析】例如"abc"≠"abc "，"abc"≠"bca"。 2. 选择题 ⑴若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。 A 不确定 B n-i C n-i-1 D n-i+1

实验二单链表基本操作技巧

实验二单链表基本操作 一实验目的 1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体 的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。 2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。二实验要求 1．预习C语言中结构体的定义与基本操作方法。 2．对单链表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。 三实验内容 1．编写程序完成单链表的下列基本操作： (1)初始化单链表La。 (2)在La中第i个元素之前插入一个新结点。 (3)删除La中的第i个元素结点。 (4)在La中查找某结点并返回其位置。 (5)打印输出La中的结点元素值。 2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、 Lb合并成一个有序单链表Lc。 合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc 指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc 之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。 3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。 （即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。） 四思考与提高 1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？ 2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？

头插法建立单链表

#include #include typedefstruct node { int data; struct node *next; }lnode,*linklist; \*定义头结点的函数*\ linklistInitlist_l(); \*定义头插法的函数*\ linklistCreatelist_f(linklistl,int n); \*定义输出链表数据的函数*\ voidPrintlist(linklist); \*主函数*\ int main(void) { inti,s,n; linklist l; l=Initlist_l(); printf("Please input number of datas:\n"); scanf("%d",&n); Createlist_f(l,n); Printlist(l); return 0; } linklistInitlist_l() { linklist l; l=(linklist)malloc(sizeof(lnode)); l->next=0; return l; } linklistCreatelist_f(linklistl,int n) { int i; linklist p; for(i=0;idata); p->next=l->next; l->next=p; }

return l; } voidPrintlist(linklist l) { linklist p; p=l->next; while(p) { printf("%d\t",p->data); p=p->next; } printf("\n"); }

栈和队列自测题

第3章栈和队列自测卷 一、填空题 1. 向量(线性表)、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能 在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称 为。 3. 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的位置。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 向栈中压入元素的操作是先，后。 7. 从循环队列中删除一个元素时，其操作是先，后。 8. 带表头结点的空循环双向链表的长度等于。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （）5. 栈和链表是两种不同的数据结构。 （）6. 栈和队列是一种非线性数据结构。 （）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 三、单项选择题（每小题1分，共20分） （）1. 栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出

c数据结构单链表的建立与基本应用

#include"stdio.h" #include"stdlib.h" typedef struct node { int data; struct node *next; }Lnode,*Linklist; input(Lnode *p,int n)//实现用键盘顺序输入链表数据{ Lnode *s;int i,d; printf("请输入数据："); for(i=1;i<=n;i++) { if(i==1) { scanf("%d",&d); p->data=d; continue; } if(n==1)break; scanf("%d",&d);

s=(Linklist)malloc(sizeof(Lnode)); s->data=d; p->next=s; s->next=NULL; p=s;//使当前指针指向链表尾部节点 } } output(Lnode *p,int n)//实现输出当前链表所有数据 { int i=1; printf("当前链表的值为："); while(p->next!=NULL) { printf("%d ",p->data); p=p->next; i++; } if(i==n)//当是最后一个节点时，其next已经是空，所以最后一个节点数据无法用while循环写出，所以另用了一个计数器i printf("%d",p->data); }

insert(Lnode *p,int i,int e)//实现在第i个元素之后插入新元素{ int j=0;Lnode *s; while(p&&jnext;++j;}if(!p||j>i-1)return 0; s=(Linklist)malloc(sizeof(Lnode)); s->data=e;s->next=p->next;p->next=s; return 1; } delet(Lnode *p,int i)//实现删除链表中第i+1个元素 { int j=0;Lnode *q; while(p->next&&jnext;++j; } if(!(p->next)||j>i-1)return 0; q=p->next;p->next=q->next; free(q); return 1; } search(Lnode *p,int e,int n) {

《数据结构》习题集：第3章 栈和队列

第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; C 、s->next=Q.rear；Q.rear=s; D 、s->next=Q.front；Q.front=s; 14.在一个链队列Q 中，删除一个结点需要执行的指令是（） A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next;

栈和队列答案

第3章栈和队列答案 一、填空题 1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性 表。 4. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。 5. 带表头结点的空循环双向链表的长度等于0。 解：Array 二、判断正误 （×）1. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧调用子程序或函数常用，CPU中也用队列。 （√）2. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）3. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同 而已。 （×）4. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同 类项。 （×）5. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不 同而已。 （√）6. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）7. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个 栈的栈底分别设在这片内存空间的两端。 （×）8. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）9. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （ B）1. 栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （C）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定

单链表的建立及其基本操作的实现(完整程序)

#include "stdio.h"/*单链表方式的实现*/ #include "malloc.h" typedef char ElemType ; typedef struct LNode/*定义链表结点类型*/ { ElemType data ; struct LNode *next; }LNode,*LinkList;/*注意与前面定义方式的异同*/ /*建立链表，输入元素，头插法建立带头结点的单链表(逆序)，输入0结束*/ LinkList CreateList_L(LinkList head) { ElemType temp; LinkList p; printf("请输入结点值(输入0结束)"); fflush(stdin); scanf("%c",&temp); while(temp!='0') { if(('A'<=temp&&temp<='Z')||('a'<=temp&&temp<='z')) { p=(LinkList)malloc(sizeof(LNode));/*生成新的结点*/ p->data=temp; p->next=head->next; head->next=p;/*在链表头部插入结点，即头插法*/ } printf("请输入结点值(输入0结束)："); fflush(stdin); scanf("%c",&temp); } return head; } /*顺序输出链表的内容*/ void ListPint_L(LinkList head) { LinkList p; int i=0; p=head->next; while(p!=NULL) { i++; printf("单链表第%d个元素是：",i);

栈和队列练习题答案

栈和队列（答案） 1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是__ C __。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为__ C __。 A. i B. n=i C. n-i+1 D. 不确定 3. 栈结构通常采用的两种存储结构是__ A __。 A. 顺序存储结构和链式存储结构 散列方式和索引方式 链表存储结构和数组 线性存储结构和非线性存储结构 4. 判定一个顺序栈ST（最多元素为m0）为空的条件是_ B ___。 A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-1 5. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是__ D __。 A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-1 6. PUSH 和POP 命令常用于（C）操作。

A 队列 B 数组 C 栈 D 记录 7. 向一个栈顶指针为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; 8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x 保存被删结点的值，则执行_ B _ __。(不带空的头结点) A. x=HS; HS= HS—＞next; B. x=HS—＞data; C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞next; 9. 一个队列的数据入队序列是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 9. 栈和队列的共同点是__ C __。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素