工大数据结构第二章作业

数据结构与算法上机作业

第二章线性表

一、选择题

1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为。 A. O(log2n) B. O(1) C. O(n) D. O(n2) 2、以下关于线性表的说法中，不正确的是。 A. 线性表中的数据元素可以是数字、字符、结构等不同类型 B. 线性表中包含的数据元素个数不是任意的 C.线性表中的每一个结点都有且只有一个直接前驱和直接后继（单项链表） D.存在这样的线性表：表中各结点都没有直接前驱和直接后继（数组实现） 3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为。 A. O(1) B. O(n) C. O(n2) D. O(log2n)

4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 。 A. n B. (n-1)/2 C. n/2 D. (n+1)/2

已经有N个点了,再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动. i的取值服从1到N+1的平均分布,即概率是1/(N+1).

求期望得N/2,即平均要移动N/2个结点期望有计算公式，这里等于

(N+1-1)*1/(N+1)+(N+1-2)*1/(N+1)+(N+1-3)*1/(N+1)+...+(N+1-N-1)*1/(N+1)=N/2

5、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2

6、在顺序表中，只要知道，就可以求出任一结点的存储地址。 A. 基地址 B. 结点大小 C. 向量大小 D. 基地址和结点大小 7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是。 A. n B. 2n-1 C. 2n D. n-1 8、线性表采用链表存储时其存储地址要求。 A. 必须是连续的 B. 部分地址必须是连续的 C. 必须是不连续的 D. 连续的和不连续的都可以 9、下面关于线性表的描述中，错误的是。

A. 线性表采用顺序存储，必须占用一片连续的存储单元 B. 线性表采用顺序存储，便于进行插入和删除操作 C. 线性表采用链式存储，不必占用一片连续的存储单元 D. 线性表采用链式存储，便于插入和删除操作

10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 A. O(1) B. O(n) C. O(n2) D. O(log2n) 11、语句是。 A. HL=p; p->next=HL; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. p->next=HL->next; HL->next=p;

HL为链表的头指针。HL指示链表中第一个节点的存储位置，在表头插入一个由指针p指向的节点后，头指针指向p，p的指针域指向原链表中第一个节点

12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是。 A. p=q->next; p->next=q->next; B. p=q->next; q->next=p;

C. p=q->next; q->next=p->next; D. q->next=q->next->next; q->next=q;

？13、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为。 A. 1234 B. 1243 C. 1324 D. 1423

至少有14种。

①全进之后再出情况只有1种：4，3，2，1

②进3个后再出的情况有3种3,4,2,1 3,2,4,1 3,2,1,4

③进2个后再出的情况有5种2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 ④进1个后再出的情况，有5种1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

14、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是。 A. A B. B C. C D. D

15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 命令。 A. x=top; top=top->next; B. top=top->next; x=top->data; C. x=top->data; D. x=top->data; top=top->next; 16、向顺序栈中输入元素时。 A. 先存入元素，后移动栈顶指针 B. 先移动栈顶指针，后存入元素 C. 谁先谁后无关紧要 D. 同时进行 17、设有一个顺序栈，元素A, B, C, D, E, F依次进栈，如果6个元素出栈的顺序是B, D, C, F, E, A，则栈的容量至少为。 A. 3 B. 4 C. 5 D. 6

顺序如下A入栈B入栈然后B出栈,C入栈D入栈,D出栈,C出栈,E入栈,F入栈,F出栈,E出栈.栈里元素最多时候就是acd和aef,所以3个就够了

18、设已将元素A, B, C依次入栈，元素D正等待进栈。那么下列4个序列中不可能出现的出栈顺序为。 A. CADB B. CBDA C. CDBA D. DCBA 19、栈和队列的相同之处是。 A.元素的进出满足先进后出 B.元素的进出满足后进先出

C.只允许在端点进行插入和删除操作 D.无共同点 栈

Insert(L,n+1,x) Delete(L,n)

而栈只允许在表尾一端进行插入和删除 队列

Insert(L,n+1,x) Delete(L,1)

队列只允许在表尾一端进行插入，在表头一端进行删除

20、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是。

A. 6 B. 4 C. 3 D. 2

设栈长度为s,起始为0 因为栈后进先出,队列先进先出.

又因为元素E1..E6是顺序入栈,那么分析过程如下： 按照出栈过程分析,因为给定出栈顺序：E2,E4,E3,E6,E5,E1, E2要进栈,所以E1必须进栈,进栈顺序：E1,E2,所以s为2 下面E2出栈,打印出E2,剩余结果为E4,E3,E6,E5,E1,

因为E2出栈了,所以当前栈容量为2,但是只是用了1个,存放E1,下面继续 E3进栈,E4进栈,此时s为3,根据出栈结果,那么E4出栈,E3出栈,此时栈容量为3 但是只有E1在栈中,剩余结果为E6,E5,E1,

同理,E5进栈,E6进栈,此时栈被填满,容量为3,后E6出栈,E5出栈,E1出栈,栈空,容量为3.所以S的容量至少为3.

21、队列通常采用的两种存储结构是( )。

A.顺序存储结构和链式存储结构 B.散列方式和索引方式

C. 链表存储结构和线性存储结构 D.线性存储结构和非线性存储结构 22、循环队列SQ队满的条件是。 A. SQ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ->front B. SQ->rear==0 D. SQ->front==0

队空:Q.front=Q.rear

队满:(Q.rear+1)%MAXQSIZE=Q.front

23、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为。 A. 5和1 B. 4和2 C. 2和4 D. 1和5 24、链栈与顺序栈相比，有一个较为明显的优点是。 A. 通常不会出现满栈的情况 B. 通常不会出现栈空的情况 C. 插入操作更加方便 D. 删除操作更加方便

25、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为。 A. 42 B. 16 C. 17 D. 41 26、串是一种特殊的线性表，其特殊性体现在。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链式存储 D. 数据元素可以是多个字符

27、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为。 A. O(m) B. O(n) C.O(m+n) D. O(m×n) 28、已知串S=“abab”，其Next数组值为。 A. 0123 B. 0121 C. 0112 D. 0122

29、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为。 A. 20% B. 40% C. 50% D. 33.3%

存储密度;结点数据本身所占的存储量/结点结构所占的存储量 1/（1+3）

30、在双向链表中，在指针p所指的结点前插入一个指针q所指向的结点，操作是。 A. p->Prior=q; q->Next=p; p->Prior->next=q; q->Prior=q; B. p->Prior=q; p->Prior->next=q; q->next=p; q->Prior=p->Prior; C. q->Next=p; q->Prior=p->Prior; p->Prior->Next=q; p->Prior=q; D. q->Prior=p->Prior; q->Next=q; p->Prior=q; p->Next=q; 31、已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是。 A. 0, 0 B. 0, n-1 C. n-1, 0 D. n-1, n-1

32、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a, b, c, d, e元素依次进队，则不可能得到的顺序是。 A. bacde B. dbace C. dbcae D. ecbad

33、在双向链表中间插入一个结点时，需要修改修改个指针域。 A. 1 B. 2 C. 3 D. 4

34、在按行优先顺序存储的三元组表中，下述陈述错误的是。 A. 同一行的非零元素，是按列号递增次序存储的 B. 同一列的非零元素，是按行号递增次序存储的 C. 三元组表中三元组行号是非递减的 D. 三元组表中三元组列号是非递减的

35、在稀疏矩阵的三元组表示法中，每个三元组表示。 A. 矩阵中非零元素的值 B. 矩阵中数据元素的行号和列号 C. 矩阵中数据元素的行号、列号和值 D. 矩阵中非零数据元素的行号、列号和值 36、对特殊矩阵采用压缩存储的目的主要是为了。 A. 表达变得简单 B. 对矩阵元素的存取变得简单 C. 去掉矩阵中的多余元素 D.减少不必要的存储空间 37、广义表是线性表的推广，它们之间的区别在于。 A. 能否使用子表 B. 能否使用原子项 C. 表的长度 D. 是否能为空 38、已知广义表(a, b, c, d)的表头是，表尾是。 A. a B. () C. (a, b, c, d) D. (b, c, d) 39、下面说法不正确的是。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构表示 D. 广义表可以是一个多层次的结构 40、若广义表A满足Head(A)=Tail(A)，则A为。 A. ( ) B. (()) C. (( ),( )) D. (( ), ( ), ( ))

二、填空题

1、线性表中结点的集合是有限的，结点之间的关系是一对一关系。 2、顺序表中访问任一个结点的时间复杂度为 O（1）。 3、线性表中第一个结点没有直接前驱，称为头结点。

4、在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。

5、在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n-i-1个元素，在插入操作中，移动元素的均值为（n+1）/2。

6、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单向链表和双向链表。

7、链式存储的特点是利用指针来表示数据元素之间的逻辑关系。 8、静态链表(线性表的游标实现)是指用数组下标表示单链表的指针。

9、在静态链表中，一般都有一个变量available表示的结点链，其中的结点为空闲结点。 10、在栈中，可进行插入和删除操作的一端称栈顶。

11、在进栈运算时，应先判别栈是否满。在出栈运算时应先判别栈是否空。当栈中元素为n个时，进栈运算时发生上溢，则说明该栈的最大容量为n。 12、设有一空栈，现有输入序列为1, 2, 3, 4, 5，经过push, push, pop, push, pop, push, push, pop, pop之后，输出序列为2354。

13、对于循环向量的循环队列，求队列长度的公式为（rear-front+n+1）%n。

14、栈的逻辑特点是先进后出。队列的逻辑特点是先进先出。两者的共同特点是只允许在它们的端点出插入和删除数据元素，区别是栈在栈顶进行插入删除，队列在两端操作，队尾插入，队首删除。

15、链队列LQ为空时，LQ->front->next=NULL.

16、在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为front.next==rear。

17、设串S=“Ilikecomputer”，T=“com”，则Length(S)=13。Index(S, T)=6。 18、在KMP算法中，next[j]只与子串有关，而与主串无关。 19、字符串“ababaab“的Next数组值是0112342。

20、稀疏矩阵一般压缩存储的方式有三种，分别是三原组存储、行指针链表和 十字链表。 21、二维数组M中每个元素的长度是3字节，行下标i从0~7，列下标j从0～9，从首地址&M[0][0]开始连续存放在存储器中。若按行优先的方式存放，元素M[7][5]的起始地址为 M[0][0]+225；若按列优先方式存放，元素M[7][5]的起始地址为M[0][0]+141。 22、广义表(a, (a, b), d, e, ((i, j), k))的长度是5，深度是3。

23、设广义表A((( ), (a, (b), c)))，则Cal(Cdr(Cal(Cdr(Cal(A))))=（b）

三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表）） 要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。

四、已知一个单向链表，试给出复制该链表的算法。

要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作

3、在1，2的基础上，完成本题。 4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。

五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数： int delete(LIST &L, int x);如果x在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。

2、定义线性表的基本操作

3、在1，2的基础上，完成本题。

4、在main函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。

三，四，五

#include using namespace std;

typedef int elementtype;//元素类型 struct celltype//链表节点 { elementtype elements; celltype *next; };

typedef celltype *LIST;

typedef celltype *position;//线性表的“型”与位置的“型”相同 position End(LIST L) //返回L中指向最后一个节点的指针 { position p; p=L;

while(p->next!=NULL) p=p->next; return p; }

void Insert(elementtype x, position p, LIST &L ) //创建元素x的节点插在p的后面 { position q q = new celltype q->elements = x q->next = p->next p->next = q

} //时间复杂性：O(1)

position Locate( elementtype x, LIST L ) //返回元素x在线性表中的位置 { position p p = L

while ( p->next != NULL ) if ( p->next->elements == x ) return p else

p = p->next; return p } //时间复杂性：O(n)

elementtype Retrieve( position p , LIST L ) {

return ( p->next ->elements ); } //时间复杂性：O(1)

void Delete( position p, LIST &L ) //删除位置p的下一个节点

{ position q

if ( p->next != NULL ) {

q = p->next p->next = q->next delete q }

} //时间复杂性：O(1)

position Previous ( position p, LIST L ) //返回位置p的前驱元素 { position q

if ( p == L->next )

cout<<”不存在前驱元素！\ else { q = L

while ( q->next != p ) q = q->next return q }

} //时间复杂度O(n)

position Next ( position p, LIST L ) //返回位置p的后驱元素 {

position q

if ( p->next == NULL )

cout<<\不存在后继元素！\else {

q = p->next; return q

}

} //时间复杂度O(1)

position MakeNull ( LIST &L ) {

L = new celltype

L->next = NULL; return L } //时间复杂性：O(1) position First ( LIST L )

{ return L; } //时间复杂性：O(1) void Travel( LIST L )//遍历线性表元素 { position p

p = L->next while ( p != NULL)

{

cout << p->elements<next } }

//=================================================

void Merge(LIST &L,LIST L1,LIST L2) //合并两个线性表(链表)，将L1，L2合并到L中

{

position p1=0,p2=0,p3=0; for(p3=L1;p3;p3=p3->next) { p1=new celltype; p1->elements=p3->elements; If(L==0)

{

L=p1; p2=p1; } else {

p2->next=p1; p2=p1; } }

for(p3=L2;p3;p3=p3->next) { p1=new celltype; p1->elements=p3->elements;

if(L==0) { L=p1; p2=p1; }

else { p2->next=p1; p2=p1; } p2->next=NULL;

}

//============================================== //复制链表

void copy(LIST &L1,LIST L2) {

position p1=0,p2=0,p3=0; for(p3=L2;p3;p3=p3->next)

{

p1=new celltype;

p1->elements=p3->elements;

I f(L1==0) { L1=p1; p2=p1; }

else

{ p2->next=p1; p2=p1; }

}

p2->next=NULL;

} //===================================================== //删除指定元素的节点

}

int Delete(LIST &L,int x) {

int m=1;//指定元素在线性表中的位置 position p1=0,p2=0; if(L->elements==x) { p1=L;

L=L->next;

delete p1;

return m; } else {

p1=p2=L;

while(p1->elements!=x && p1->next!=NULL) {

p2=p1; m++;

p1=p1->next; }

p2->next=p1->next; delete p1;

return m; }

return -1;//不存在元素x }

void Read(LIST &L,int i) //输入数据 {

cout<<\请输入第\个线性表\LIST p1=0,p2=0; elementtype x; for(;;) {

cout<<\请输入数据(-1作为结束标志):\ cin>>x;

if(x==-1) break; p1=new celltype; p1->elements=x;

if(L==0) { L=p1; p2=p1; } else { p2->next=p1; p2=p1; } }

p2->next=NULL; }

void Write(LIST L) //输出 {

position p=L;

for(;p;p=p->next)

cout<elements<<'\\t'; cout<

cout<<\本次测试的类型为int\LIST L=NULL,L1=NULL,L2=NULL; Read(L1,1);

cout<<\的元素为：\ Write(L1); Read(L2,2);

cout<<\的元素为：\Write(L2);

Merge(L,L1,L2);

cout<<\合并后L的元素为：\Write(L);

/* LIST L=NULL,L1=NULL; read(L); cout<<\原有的元素：\write(L); copy(L1,L);

cout<<\复制之后的元素：\write(L1);

LIST head=NULL; read(head);

cout<<\删除前：\ cout<<\请输入要删除的数据：\Elementtype x; cin>>x;

int m=Delete(head,x); cout<<\删除后：\write(head); if(m==-1)

cout<<\需要删除的数不存在\ else

cout<<\需要删除的数是第\个\ */

} //线性表的数组实现-线性表的合并 #include using namespace std;

#define maxlength 100 typedef int position;//位置类型 typedef int Elementtype;//下标类型 struct LIST {

Elementtype elements[maxlength]; int last;//最后一个元素的下标 };

position End(LIST L)//线性表的长度

{

return (L.last+1); }

void Insert(Elementtype x,position p,LIST &L) //在表L的位置p处插入x {

position q;

if(L.last>=maxlength-1) cout<<\ else if((p>L.last+1) || (p<1))

cout<<\ else

{ for(q=L.last;q>=p;q--)

L.elements[q+1]=L.elements[q]; L.last=L.last+1; L.elements[p]=x; } }

void Delete(position p,LIST &L) //删除位置p处的元素 { position q; i

f((p>L.last+1) || (p<1))

cout<<\ else

{ L.last=L.last-1; for(q=p;q<=L.last;q++) L.elements[q]=L.elements[q+1]; } }

position Locate(Elementtype x,LIST L) //返回x在表L中的位置 { position q;

for(q=0;q

return q; return (L.last+1); //x不存在 }

Elementtype Retrive(position p,LIST L) //返回L中位置为p的元素 { if((p<1) || (p>L.last+1))

{ cout<<\ return -1; }

return L.elements[p];

} //====================================================== //将两个线性表合并

void Merge(LIST &L,LIST L1,LIST L2)

{ position p,p1,p2; position len1=End(L1);//L1的长度 position len2=End(L2);//L2的长度 L.last=len1+len2-1;//合并后L的最后一个元素的位置 p=p1=p2=0

for(;p1

{ L.elements[p]=L1.elements[p1]; p++; p1++; } for(;p2

{ L.elements[p]=L2.elements[p2]; p++; p2++; } }

void Read(LIST &L,int i) //输入线性表 {

cout<<\请输入第\个线性表的长度：\ cout<<\请输入第\个线性表的元素：\

for(position p=0;p<=L.last;p++) cin>>L.elements[p]; }

void Write(LIST L) //输出线性表

{ cout<<\线性表的长度为：\线性表的元素为：\ for(position p=0;p<=L.last;p++) cout<

void main() {

cout<<\本次测试的类型为int\ LIST L,L1,L2; Read(L1,1); Read(L2,2);

Merge(L,L1,L2); Write(L); }

六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数：

void Merge(cursor M, cursor N); 合并的方法是将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中。 要求：1、定义静态链表的结点的结构以及结点的型SPACE以及位置（position）和游标（cursor）的型。 2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M中的位置为p的元素后面添加一个值为x的结点；void Delete (cursor M, position p ); 在链表M中删除位置为p的元素的后一个元素。 3、在1、2的基础上完成本题。

4，在main函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态表，最后将这两个静态表合并。

#include using namespace std;

#define maxsize 100 typedef int elementtype;

typedef struct { elementtype element int next } spacestr; /*结点类型*/

spacestr SPACE[ maxsize ] /*存储池*/ typedef int position, cursor;

cursor available;/* 标识线性表/空闲池*/ void Initialize() { int j; /* 依次链接池中结点*/ for (j=0; j

SPACE[j].next=-1;/* 最后一个接点指针域为空*/

available=0;/* 标识线性表,将所有存储池中的结点设置为空闲，avilable为头结点，不利用*/ } // 可用空间的分配操作,从空闲链中获取一个结点 cursor GetNode() // q=new spacest { cursor p;

if (SPACE[available].next ==-1) p=-1; else {

p= SPACE[available].next

SPACE[available].next = SPACE[ p ].next }

return p; }/* 将空闲池头结点的下一个节点从空闲池中删除*/ void FreeNode(cursor q) //delete q; {

SPACE [ q ].next =SPACE[available].next

SPACE[available].next = q }/* 将q指向的节点放回池中*/ // 在位置p后面插入元素值为x的结点

void Insert ( elementtype x, position p) {

position q q = GetNode( ) SPACE[ q ].element = x

SPACE[ q ].next = SPACE[ p ].next SPACE[ p ].next = q } // 删除位置p后的一个结点 void Delete ( position p) {

position q；

if ( SPACE[ p ].next != -1 ) {

q = SPACE[ p ].next ；

SPACE[ p ].next = SPACE[ q ].next ；

FreeNode( q ) }

} //创建静态链表 void Create(cursor M) {

elementtype input;

position p = M; while(1) {

cout<<\请输入静态链表的值，输入-1结束：\ cin>>input; if(input != -1) { I

nsert(input,p);

p = SPACE[p].next;

}

else break; }

}

void Merge(cursor M,cursor N) //连接两个链表,将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中 {

position p; p=M;

while(SPACE[p].next!=-1) p=SPACE[p].next; position q;

q=SPACE[N].next; SPACE[p].next=q; FreeNode(N);

} //输出静态链表 void Print(cursor M) { position p; p = M;

while(SPACE[p].next != -1)

{ cout<

spacestr s; Initialize();

position p=GetNode(); cursor M=GetNode(); SPACE[M].next = -1; cursor N=GetNode(); SPACE[N].next = -1;

cout<<\创建静态链表M：\Print(M);

cout<<\创建静态链表N：\ Create(N); Print(N);

cout<<\将M和N合并后：\

Merge(M,N); Print(M); }

七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：A(x)?amtem?am?1xem?1e?...?a1x1

其中，系数ai≠0，指数ei满足em>em-1>…>e2>e1>=0。 要求：1、定义多项式每一项的结构。 2、定义两个多项式的相加和相乘运算函数。 3、在main函数中，构建两个多项式，并测试相加和相乘运算。 #ifndef POLYNOMIAL_H #define POLYNOMIAL_H #include #include #include

//链表结构

typedef struct Node{ struct Node *next; double coefficient; int exponent;

} Node, *Polynomial; //链表初始化 void initList(Polynomial *L) { //头结点

if (NULL == *L) {

*L = (Polynomial)malloc(sizeof(Node));

(*L)->coefficient = 0.0; (*L)->exponent = -1;

(*L)->next = NULL; } else

{

cout<<\表已经存在！\ }

} //判断指数同否

int compareExponent(Polynomial nodeA, Polynomial nodeB) {

int a = nodeA->exponent; int b = nodeB->exponent; if (a == b) {

return 0; } else {

return a > b ? 1 : -1; }

} //系数判断

bool isZeroByCoefficient(Polynomial node) {

if (node->coefficient >= -LDBL_EPSILON && node->coefficient <= LDBL_EPSILON) {

return true; } else {

return false; }

} //判断2 //系数判断

bool isZeroByDouble(double a) {

if (a >= -LDBL_EPSILON && a <= LDBL_EPSILON) {

return true; else {

return false; }

} //尾插法建表

void creatListByTail(Polynomial *L, int n) {

//头结点

if (NULL == *L) {

*L = (Polynomial)malloc(sizeof(Node)); (*L)->coefficient = 0.0; (*L)->exponent = -1; (*L)->next = NULL; Polynomial tail = NULL;

Polynomial ptr = *L; //初始化？ if (NULL == (*L)->next) {

Cout<<\请按照指数升幂，连续的输入项的系数（double）和指数（int）：（中间 空格隔开）\循环建表

for (int i = 0; i < n; i++) {

tail = (Polynomial)malloc(sizeof(Node)); tail->next = NULL;

scanf(\

while (getchar() != '\\n') {

continue; }

//链接

ptr->next = tail; //移动指针 ptr = ptr->next; //尾结点 } } else {

Cout<<\表已经建立！\ } } else {

Cout<<\表头已经存在！\ } } //遍历

void traverseList(Polynomial L) {

Polynomial ptr = L->next; int i = 1;

while (ptr != NULL) {

Cout<<\一元多项式的第%d项：%g X ^ %d\\n\

<coefficient <exponentendl;

i++;

ptr = ptr->next; }

} //求最高阶数

int getMaxExp(Polynomial L) {

Polynomial ptr = L;

while (ptr->next != NULL)

{

ptr = ptr->next; }

return ptr->exponent;

} //删除结点,删除L中ptr指向的结点

void deleteNode(Polynomial L, Polynomial ptr) {

Polynomial p = L;

while (p->next != ptr) {

p = p->next; }

ptr = p->next;

p->next->next = ptr->next; free(ptr);

ptr = NULL; 165 }//多项式相加，本质是链表的归并算法

//可以另外开辟空间，也可以使用已存在的空间存储，这里使用后者的算法 void addPolynomial(Polynomial LA, Polynomial LB) { //不再开辟内存

Polynomial a = LA->next; Polynomial b = LB->next; Polynomial LC = LB; Polynomial tail = LC;

while (a != NULL && b != NULL)

{//判断指数的关系 a > b ? 1 : -1 else 0 switch (compareExponent(a, b)) {

case 1: tail->next = b; tail = tail->next; b = b->next;

break;

case -1: tail->next = a;

tail = tail->next; a = a->next; break; default:

double temp = a->coefficient + b->coefficient;// 0？ if (isZeroByDouble(temp)) {

a = a->next;

b = b->next; //删除

deleteNode(LC, tail->next); } else {

tail->next = b; tail = tail->next;

b->coefficient = temp; a = a->next;

b = b->next; }// end of if }// end of switch }//end of while //一表比完

if (NULL == a) {

tail->next = b; } else {

tail->next = a; }// end of if

free(LA); LA = NULL; }

//多项式相乘

void mulPolynomial(Polynomial LA, Polynomial LB, Polynomial LC) {

Polynomial a = LA->next; Polynomial b = LB->next; Polynomial c = LC;

Polynomial ptr = NULL; //两多项式的阶数

int numA = getMaxExp(LA); int numB = getMaxExp(LB); //结果多项式的阶数

int maxNum = numA + numB; //动态开辟数组空间

double *receive = (double *)malloc((maxNum + 1) * sizeof(double)); //为数组赋值

for (int i = 0; i < maxNum + 1; i++) {

//i相当于指数，数组值就是相应指数的系数 receive[i] = 0.0; }

//指数及数组下标 int expByIndex = 0; //顺次扫描A while (a != NULL)

{//A不空，顺次扫描B while (b != NULL) {

//两项做乘法之后的指数和

expByIndex = a->exponent + b->exponent;

//系数之间做乘，结果保存到对应的指数下（下标）， receive[expByIndex] += (a->coefficient) * (b->coefficient); b = b->next; }

b = LB->next; a = a->next; }// end of while

//数组保存的是全部项，两两分别乘法之后的结果，保存在对应的下标（数组位置） for (int i = 0; i < maxNum + 1; i++) { // 0？

if (isZeroByDouble(receive[i])) {//not do sth } else

{ //生成结点

ptr = (Polynomial)malloc(sizeof(Node)); //接到 LC 表 c->next = ptr;

c = c->next; //赋值

c->coefficient =receive[i]; c->exponent = i;

}// end of if }// end of for

c->next = NULL; }

//链表销毁

void destroyList(Polynomial *L) {

Polynomial ptr = NULL; while (*L != NULL) {

ptr = (*L)->next; free(*L); *L = ptr;

} //

*L = NULL;

cout<<\销毁完毕\ }

#endif

八、试编写一个整数进制转换的通用函数convert(int num, STACK S, int n)，要求将整数m转换为n进制数，n进制数的各位依次存放在栈S中。并在主函数中进行测试。 要求：1、定义栈以及栈的型。

2、定义栈的各种操作。 3、实现函数convert。

4、在main函数中，通过调用函数convert将num的n进制数存放到一个栈中，并通过出栈的方法输出该n进制数 //栈的数组实现

//此处将栈底规定在数组的底部，即让maxlength-1指向栈底的第一个元素 #include using namespace std;

#define maxlength 100//栈的容量 typedef int Elementtype;

struct STACK//定义整型线性数组栈 { int top; Elementtype elements[maxlength]; };

bool isEmpty(STACK S)//栈是否为空 { if(S.top>=maxlength) return true; else return false; }

void makeNull(STACK &S)//栈置空 { S.top = maxlength; }

Elementtype top(STACK S)//返回栈顶元素 { if(isEmpty(S)) cout<<\栈为空！\ else return(S.elements[S.top]); }

void pop(STACK &S)//出栈,删除栈顶元素 { if(isEmpty(S)) cout<<\栈为空！\ else S.top++; }

void push(STACK &S, Elementtype x)//进栈 { if(S.top == 0) cout<<\栈已满！\ else { --S.top; S.elements[S.top] = x; } }

void convert(int num,STACK &S,int n)//进制转换函数 { while(num!=0) { push(S,num%n); num/=n; } }

void print(STACK S)//输出转后的结果 { while(!isEmpty(S)) { cout<

cout<

void main() { STACK S; makeNull(S); int num = 1024; int n = 2; cout<<\转化前的十进制数为：\ cout<<\转化后的\进制数为：\ convert(num,S,n); print(S); }

九、设有一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断队列空、判断队列满、出队算法和入队算法。 要求：

1、定义相应的循环队列的型（只有头指针，没有尾指针，但有一个元素个数的计数器）； 2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法； 3、在main函数验证算法的正确性。

//没有尾指针的队列，但有一个计数器，所以尾指针rear可以用头指针表示出来 #include using namespace std;

#define maxlength 20 typedef int elementtype;

struct QUEUE {

elementtype elements[maxlength]; int front;

int count;//元素个数计数器：rear=(front+count-1)%maxlength };

int addone( int i )//指针后移 { return ((i+1)%maxlength); }

bool isEmpty(QUEUE Q)//队列是否为空 { if (Q.count==0) return true ;

else return false ; }

bool isFull(QUEUE Q)//队列是否已满 {

if (Q.count==maxlength) return true; else

return false; }

elementtype front(QUEUE Q)//返回队头元素 { if (isEmpty(Q)) return NULL ; else return(Q.elements[Q.front]); }

void enQueue(elementtype x,QUEUE &Q)//队列后插入一个元素，入队 { if (isFull(Q)) cout<<\队列已满\ else { Q.count++; Q.elements[(Q.front+Q.count-1)%maxlength]=x; } }

void deQueue (QUEUE &Q)//删除队头元素,出队 { if(isEmpty(Q)) cout<<\队列为空\ else { Q.front=addone(Q.front); Q.count--; } }

void print(QUEUE Q) {

for (int j=0;j

cout<

void main() {

QUEUE Q; Q.front=0; Q.count=0;

for (int i=1; i<10; i++) enQueue(i, Q); cout<<\队头：\ print(Q);

for (i=0; i<6; i++) deQueue(Q); cout<<\删除前六个元素后的队列：\ print(Q); }

十、设主串T=“abcaabbabcabaacbacba“，模式为p=“abcabaa”。 1、计算模式p的nextval函数值

2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。 要求：

1、写出模式p的nextval值；

2、画出KMP算法的每一趟匹配过程（可参照教材P61从第8行开始的内容）； 3、不需要编写程序。

Nextval：a b c a b a a 011 0 1 3 2 第一趟匹配： i=5,j=5

abcaabbabcabaacbacba abcab(匹配失败) 第二趟匹配： i=5,j=1

abca abbabcabaacbacba abc（匹配失败） 第三趟匹配： i=7,j=1

abcaab babcabaacbacba a（匹配失败） 第四趟匹配： i=8,j=1

Abcaabbabcabaacbacba abcabaa 匹配成功！

十一、假设表达式中允许包含三种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈（用数组表示的栈）判断表达式中的括号是否正确配对。 要求：

1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Boolean，其中两个元素分别为TRUE和FALSE。

2、定义栈的各种操作。

3、定义函数Boolean check(char *s); 判断s中的括号是否正确配对，如果正确配对，返回TRUE，否则返回FALSE。

4、在主函数中验证所编写函数的正确性。

//栈的数组实现

//此处将栈底规定在数组的底部，即让maxlength-1指向栈底的第一个元素 #include using namespace std;

#define maxlength 100//栈的容量

//typedef int Elementtype;//数制转换中元素类型为int

typedef char Elementtype;//括号匹配中元素类型为字符型char enum Boolean{TRUE,FALSE};

struct STACK//定义整型线性数组栈 { int top; Elementtype elements[maxlength]; };

bool isEmpty(STACK S)//栈是否为空 { if(S.top>=maxlength) return true; else return false; }

void makeNull(STACK &S)//栈置空 { S.top = maxlength; }

Elementtype top(STACK S)//返回栈顶元素 {

if(isEmpty(S)) return NULL; else return(S.elements[S.top]); }

void pop(STACK &S)//出栈,删除栈顶元素 { if(isEmpty(S)) cout<<\栈为空！\ else S.top++; }

void push(STACK &S, Elementtype x)//进栈 { if(S.top == 0) cout<<\栈已满！\ else { --S.top; S.elements[S.top] = x; } }

//=====================================================数制转换 void convert(int num,STACK &S,int n)//进制转换函数 { while(num!=0) { push(S,num%n); num/=n; } }

void print(STACK S)//输出转后的结果 { while(!isEmpty(S)) { cout<

//====================================================括号匹配

Boolean check(char *s) { STACK S; makeNull(S); int j=0; while(s[j]!='\\0') { switch(s[j]) { case '(': push(S,'('); break; case ')': if(top(S) == '(') pop(S); else return FALSE; break; case '[': push(S,'['); break; case ']': if(top(S) == '[') pop(S); else return FALSE; break; case '{': push(S,'{'); break; case '}': if(top(S) == '{') pop(S); else return FALSE; break; } j++; } if(isEmpty(S)) return TRUE; else return FALSE;

}

void main() {/* STACK S; makeNull(S); int num = 1024; int n = 2; cout<<\转化前的十进制数为：\ cout<<\转化后的\进制数为：\ convert(num,S,n); print(S); */ char *s = \ char *p = \ if(check(s) == TRUE) cout<<\括号匹配！\ else cout<<\括号不匹配！\ if(check(p) == TRUE) cout<<\括号匹配！\ else cout<<\括号不匹配！\}

十二、设有一个带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。 要求：

1、定义带头结点的双向链表的型DLIST。 2、定义双向链表DLIST的基本操作。

3、定义函数int swap(elementtype x, DLIST &h)，查找第一个元素之为x的结点，如果在链表中存在元素值为x的结点，并其与其前驱结点进行交换，并返回1，否则返回0。 4、在主函数中测试所编写函数的正确性。

//带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。 #include using namespace std; typedef int Elementtype;

struct celltype{ Elementtype element;//数据域 celltype *previous,*next;//前驱和后驱 };

typedef celltype *position;//位置的型 typedef celltype *DLIST;//双向链表的型

//插入元素,在p后面插入

void insert(position p,Elementtype x) { if(p->next){ position q = new celltype; q->element = x; q->next = p->next; q->previous = p; p->next->previous = q; p->next = q; } else { position q = new celltype; q->element = x; q->next = p->next; q->previous = p; p->next = q; } }

//删除中间结点

void Delete(position p) { if(p->next != NULL && p->previous != NULL)//删除的不是头尾结点 { p->previous->next = p->next; p->next->previous = p->previous; delete p; } else cout<<\不能删除头尾结点！\}

void create(DLIST &head)//创建双向链表 { head->previous = NULL;//让头结点的前驱指向自己 head->next = NULL; position p = head; int x=0,i=1; while(1){

cout<<\请输入第\个插入的元素（输入-1结束创建）：\ cin>>x; if(x !=-1) { insert(p,x); p = p->next; } else break; } }

void print(DLIST head)//输出链表元素 { position temp = head; while (temp->next) { temp=temp->next; cout<element<<'\\t'; } cout<

int swap(Elementtype x,DLIST &head)//查找交换 { position temp,L; temp = head; while (temp->next) { temp=temp->next; if (temp->element==x&&temp->previous!=head)//元素匹配并且前驱不能是头结点 { L = temp->previous; L->previous->next = temp; temp->previous = L->previous; L->next = temp->next; temp->next->previous = L; L->previous = temp; temp->next = L; return 1; } } return 0; }

void main() { DLIST head = new celltype; create(head); print(head); Elementtype x; cout<<\请输入你想查找的元素：\ cin>>x; if(swap(x,head)) { cout<<\查找交换成功！\ print(head); } else cout<<\查找失败！\}

十三、试编写一个求三元组顺序表示的稀疏矩阵对角线元素之和的算法

十四、当具有相同行值和列值的稀疏矩阵A和B均以三元组顺序表方式存储时，试写出矩阵相加的算法，其结果存放在以行逻辑链接顺序表方式存储的矩阵C中。

十三，十四 算法分析:

矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。

//三元组表示的稀疏矩阵对角线元素相加，以及稀疏矩阵相加 #include using namespace std;

#define NumVertices 6//稀疏矩阵非零元素个数

struct node{ int row;//行 int col;//列 int data;//值 };

typedef node triple;//三元组

void Input(triple a[])//输入三元组

{ cout<<\请输入系数矩阵的行、列数和非零元素个数：\ cin>>a[0].row>>a[0].col>>a[0].data; if(a[0].row != a[0].col) cout<<\请注意您输入的系数矩阵不是n阶矩阵，无法求对角元素的和！\ for(int i=1;i<=a[0].data;i++) { cout<<\请以按行优先的规则依次输入第<>a[i].row>>a[i].col>>a[i].data; } }

void Init(triple a[])//初始化三元祖 { a[0].row = 4; a[0].col = 4; a[0].data = 6; a[1].row = 0; a[1].col = 0; a[1].data = 50; a[2].row = 1; a[2].col = 0; a[2].data = 10; a[3].row = 1; a[3].col = 2; a[3].data = 20; a[4].row = 3; a[4].col = 0; a[4].data = -30; a[5].row = 3; a[5].col = 2; a[5].data = -60; a[6].row = 3; a[6].col = 3; a[6].data = 5; }

int Find(triple a[],int row,int col)//判断三元组A所标示的稀疏矩阵是否存在下标[row][col]的非零元素,存在的话返回该非零元素 { for(int i=1;i<=a[0].data;i++){ if(a[i].row == row && a[i].col == col) return a[i].data; } return 0; }

int Sum(triple a[])//求对角矩阵对角元素的和 {

int i,sum=0;

if (a[0].row!=a[0].col)

cout<<\此稀疏矩阵不是n*n矩阵，无法求对角元素和\ else

for (i=1; i<=a[0].data; i++)

if (a[i].row==a[i].col ||a[i].row+a[i].col == a[0].row-1) sum+=a[i].data; return sum; }

void Print(triple *a)//输出三元组 { for(int j=0;j<=a[0].data;j++) cout<

void PrintMT(triple *a)//输出三元组所表示的稀疏矩阵 { for(int i=0;i

void Combine(triple a[],triple b[],triple c[])//三元组表示的稀疏矩阵相加 { c[0].row = a[0].row; c[0].col = a[0].col; int cdata = a[0].data+b[0].data;//c的临时非零元素个数 int cmark = 1; for(int i = 0;i

c[cmark].row = i; c[cmark].col = j; c[cmark].data = Find(b,i,j); cmark++; } } c[0].data = cdata;//最终c的非零元素个数 }

void main(){ triple a[NumVertices+1]; Init(a); cout<<\您输入的三元组：\ Print(a); cout<<\您输入的三元组表示的稀疏矩阵：\ PrintMT(a); cout<<\稀疏矩阵对角元素之和为：\ cout<<\和a相加：\ triple c[20];

Combine(a,a,c);//将a和a相加放进c里面 cout<<\相加后c三元组为：\ Print(c); cout<<\相加后的稀疏矩阵为：\ PrintMT(c); }

十五、设有一个稀疏矩阵：

?04?00??80??00?0?7???00000000000??3001??0000??

5000?0020??6000??0 1、写出三元组顺序表存储表示

2、写出十字链表存储的顺序表示

1. 行 列 元素

6 7 8 6行7列 8 个非零元素 0 1 4 1 3 -3

1 6 1 2 0 8 3 3 5 4 1 -7 4 5 2 5 3 6 2.

.

十六、画出广义表LS=(( ), (e), (a, (b, c, d)))的头尾链表存储结构(类似于教材P70图2-27.9)。 要求：按照教材中的事例画出相应的图形，不需要编程。 其中第一个节点如下：

t 解：

t t t

t a t e t

t

t c t b t

^^^^ ^ d ^

十七、试编写求广义表中原子元素个数的算法。 要求：

1、定义广义表的节点的型； 2、定义广义表的基本操作；

3、定义本题要求的函数int elements(listpointer L)；函数返回值为广义表中原子的个数。例如，广义表(a, b, c, d)原子的个数为4，而广义表(a, (a, b), d, e, ((i, j), k))中院子的个数为3。 提示：先利用基本操作Cal(L)获得表头，判断表头是不是原子，再利用基本操作Cdr(L)获得除第一个元素外的其他元素所形成的表L1，利用递归的方法求L1中原子的个数。 递归有问题

#include using namespace std;

//广义表结构的型 struct listnode{ listnode *link;

bool tag;//false表示该结点为原子，true表示结点为指向子表的指针 union{

char data;

listnode *dlink; }element;//共用体 };

typedef listnode *listpointer;

//表头

listpointer Cal(listpointer S){ if (S==NULL) return NULL; else {

listpointer temp; temp->tag=S->tag; temp->link=S->link;

temp->element=S->element; return temp; } }

//表尾

listpointer Cdr(listpointer S){ if (S->link==NULL)

return NULL; else {

listpointer temp;

temp->tag=S->link->tag; temp->link=S->link->link;

temp->element=S->link->element; return temp; } }

int elements(listpointer L){

//如果广义表为空，返回原子个数为零 if(L==NULL) return 0; //如果广义表第一个结点是原子返回其他结点的原子个数+1 if(Cal(L)->tag==false) //表头为原子 return(elements(Cdr(L))+1); else //表头为广义表 return(elements(Cdr(L))); }

void main(){

//建立广义表（a,(b,c),d,e） listpointer A; A->tag=false;

A->element.data='a'; listpointer B; B->tag=false;

B->element.data='b'; listpointer C; C->tag=false; C->link=NULL; C->element.data='c'; B->element.dlink=C; listpointer F; F->tag = true; A->link=F; listpointer D; D->tag=false;

D->element.data='d'; F->link = D; listpointer E;

E->tag=false;

E->element.data='e'; E->link=NULL; B->link=D; D->link=E;

cout<<\广义表的原子元素个数为：\ }

要求：

1、上述作业要求在单独完成；

2、完成后，于规定期限内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个Word文件中，文件名格式为“学号+姓名”

本文来源：https://www.bwwdw.com/article/eiw6.html