线性表及其应用

以你之姓@ 2022-09-19 13:29 167阅读 0赞

**线性表及其应用**

**整理：Ackarlix**

**一、基本知识**

线性表是最常用且最简单的一种数据结构。简而言之，一个线性表是N个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数，或一个符号，也可以是一页书，甚至其它更复杂的信息。例如由每个英文字母组成的字母表：（A，B，C，……，Z）是一个线性表，表中的数据元素是单个字符。又如某校从1993年至1998年各种型号计算机的拥有量的变化情况，可以用线性表的形式给出（16，27，38，60，102，198），表中的数据元素是自然数。

**线性表的特点是**:

① 存在唯一的一个被称作“第一个”的数据元素；

② 存在唯一的一个被称为“最后一个”的数据元素；

③ 除第一个元素外，线性表中的每个数据元素均只有一个前驱；

④ 除最后一个元素之外，每个数据元素均只有一个后继。

⑤ 线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，即基类型相同。

**线性表的常见操作包括**：

①确定表的长度n，即求表中数据元素的个数；

②读表：从左到右（或从右到左）读表，即按a1，a2，……，an（或an，an-1，……，a1）读取数据元素的值；

③检索：即在表中查找具有某个特征值的数据元素；

④改写：修改、存入表中第i个数据元素（1≤i≤n），即给第i个数据元素赋值；

⑤插入：在第i-1个和第i个数据元素之间（1≤i≤n）插入一个新的数据元素，使原来的第i，i+1，……，n个数据元素变成为第i+1，i+2，……，n，n+1个数据元素；

⑥删除：删除第i个数据元素（1≤i≤n），使原来的第i+1，i+2，……，n个数据元素变成为第i，i+1，……，n-1个数据元素；

⑦排序：即按某个特征值递增（或递减）的顺序对表中的数据元素重新排列。

⑧归并：将两个以上的有序线性表合并成一个新表。

**二、****线性表的存储结构**

线性表可以用多种方法实现，最常用的、最简单的就是数组。其它的还有：字符串、栈、队列、链表等。在计算机内的存储分为顺序存储方式（数组）和链式存储方式（指针）。

对于不同的题目，选用不同的存储方式，其执行效果是不一样的，主要体现在空间复杂度、时间复杂度、编程复杂度三个方面。

在选择具体的存储结构实现算法时，必须考虑要进行的是哪些运算，充分估计这些运算执行次数的数量级，以及对存储容量的要求和编程量。

**1****、顺序存储方式（数组方式）**

在计算机内，存储线性表的最简单和最自然的方式，是把表中的数据元素一个接一个地放进一组连续的存储单元之中，也就是说，把表中相邻的数据元素存放在内存中邻接的存储单元里，这种存储方法叫做顺序存储，又称顺序映象。其特点是：逻辑上相邻的数据元素，它们的物理次序也是邻接的。缺点是要求有足够的、完整的、连续的存储空间供编程者开辟大数组。

假设每个数据元素占用Len个存储单元，则相邻的两个数据元素ai与ai+1在机器内的存储地址LOC（ai）与LOC(ai+1)将满足下面的关系：

LOC(ai+1) = LOC（ai）\+Len

一般把LOC（a1）称为基地址，而LOC（ai）的存储地址就为：

LOC（ai）= LOC（a1）\+(i - 1) \*Len

线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短。主要通过插入和删除操作进行。对于数组的插入操作，我想很简单，主要区分好前插和后插、插入在表头和表尾的特殊情况、以及插入后空间的溢出问题和下标范围。

除了插入和删除两种重要的操作外，线性表的查找和排序也很重要，查找可以用线性查找、哨兵查找和二分查找等。排序可以用插入排序、选择排序、冒泡排序、***快速排序***、堆排序等。

**例****1****、****Josephus(****约瑟夫****)****问题**

**\[****问题描述****\]**

M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N报数，凡报到N的猴子退出到圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和N由键盘输入，打印出最后剩下的那只猴子的编号。

**\[****问题分析****\]**

这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。

在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey\[k\]=1表示第k只猴子仍在圈中，monkey\[k\]=0则表示第k只猴子已经出圈。

程序采用模拟选举过程的方法，开始时将报数变量count置为1，用变量current表示当前报数的猴子的编号，初始时也置为1，变量out记录出圈猴子数。当count=n时，对当前报数的猴子作出圈处理，即monkey\[current\]：=0， count：=0，out：=out+1。然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。

**\[****程序****1-1\]**

const maxm=100;

var i，m，n，count，current，out:integer;

monkey:array \[1..maxm\] of integer;

begin

write('Input m，n:'); readln(m，n);

for i:=1 to m do monkey\[i\]:=1;

out:=0; count:=1; current:=1;

while out<m-1 do

begin

while count<n do

begin

repeat\{ 寻找圈上的下一只猴子\}

current:=current+1;

if current=m+1 then current:=1

until monkey\[current\]=1;

count:=count+1

end;

monkey\[current\]:=0; out:=out+1; count:=0

end;

for i:=1 to m do

if monkey\[i\]=1 then writeln('The monkey king is no.'，i)

end.

**\[****运行程序****\]**下划线表示输入

Input m，n:8 3

The monkey king is no.7

**\[****程序****1-2\]**

在组织数据时，也可以考虑只记录仍在圈中的猴子的情况。用一个线性表按编号由小到大依次记录圈中所有猴子的编号，每当有猴子出圈时，即从线性表中删除对应元素，表中元素减少一个。程序中用变量rest表示圈中剩余的猴子数，即线性表中元素的总数。

const maxm=100;

var i，m，n，current，rest:integer;

monkey:array \[1..maxm\] of integer;

begin

write('Input m，n:'); readln(m，n);

for i:=1 to m do monkey\[i\]:=i;

rest:=m; current:=1;

while rest>1 do

begin

current:=(current + n - 1) mod rest;

if current=0 then current:=rest;

for i:=current to rest-1 do monkey\[i\]:=monkey\[i+1\];

rest:=rest-1

end;

writeln('The monkey king is no.'，monkey\[1\])

end.

**\[****程序****1-3\]** **题目修改一下：**

现在改成从第P个开始，每隔M只报数，报到的退出，直到剩下一只为止。最后剩下的为猴王。问：猴王是原来的第几只猴子？

Const maxn=1000;

Var monke:array\[1..maxn\] of integer;\{N个猴子的标记\}

N，nn，p，m，I，j:integer;

Function no(I:integer):integer;

Begin

While I>n do I:=I-n;

No:=I;

End;

Begin

Readln(n，p，m);

For I:=1 to n do monkey\[i\]:=I;

P:=no(p+m-1);

nn:=n;

For I:=1 to n-1 do

Begin

nn:=nn-1;

for j:=p to nn do monkey\[j\]:=monkey\[j+1\];

p:=no(p+1);

end;

writeln(‘THE KING OF MONKEY IS: ’，MONKEY\[P\]);

end.

**\[****程序****1-4\]****用数组模拟单向循环链表**

以上程序的缺点：移动很多元素，再改进如下：

Const maxn=1000;

Type node=record

No，next:integer; \{N个猴子的标记和下一个邻居\}

End;

Var monke:array\[1..maxn\] of node;

n，p，m，i:integer;

Begin

Readln(n，p，m);

For I:=1 to n do begin monkey\[i\].no:=I;monkey\[I\].next:=I+1;end;

Monkey\[n\].next:=1;

P:=p-1;if p=0 then p:=n;

While n>1 do

begin

for I:=1 to (m-1) mod n do

p:=monkey\[p\].next;

monkey\[p\].next:=monkey\[monkey\[p\].next\].next;

n:=n-1;

end;

writeln(p);

end.

**\[****程序****1-5\]** **再修改一下：**

你一定听说过约瑟夫问题吧？！即从n个人中找出唯一的幸存者。现在老约瑟夫将组织一个皆大欢喜的新游戏，假设n个人站成一圈，从第1人开始交替的去掉游戏者，但只是暂时去掉（例如，首先去掉2），直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人将得到1TK（一种货币），永久性的离开。其余剩下的人将重复以上的过程，比幸存者号码高的人每人将得到1TK后离开。一旦经过这样的过程后，人数不再减少，最后剩下的那些人将得到2TK。请你计算一下老约瑟夫一共要付出多少钱？

**2****、链式存储方式（链表）**

利用数组描述线性表时，其优点是对线性表中任一元素都可随机存取，具体反映为通过改变下标的值可以对线性表中的任一元素进行访问和修改。其缺点是在向线性表中插入和删除元素时，必须移动表中的部分元素。插入元素时，要将从插入位置直至最后的所有元素后移一个位置。大量的移动操作浪费了宝贵的CPU资源。

链表是一种可以实现动态分配的存储结构，它不需要一组地址连续的存储单元，而是一组任意的、甚至是在存储空间中零散分布的存储单元。

下面结合一个具体题目，给出链表的几个常用操作过程（函数），**以****BP7.0****环境为准**。

**例****2****用随机函数产生****N****（****N<=100000****）个小于****100000****的正整数，统计共产生了多少个不相同的正整数及每个数出现的次数。**

**\[****思考****\]** 1、数组，A\[i\]=x，表示数i出现了X次。但空间不够；

2、有人想，如果数据量很小（255个），也可以用集合做。

3、本题用单链表做。

4、**说明：选用什么样的数据结构和算法在很大程度上取决于数据规模！**

**（1）****单链表**

每个结点的存储单元分为两部分：一部分存储结点的数据域（data域，1个或多个），另一部分存储指向后续结点的指针(next域)。最后一个结点没有后续结点（next域为空NIL），另外，一般线性表的操作都是从表头开始的，所以一般设置一个表头指针head，指向链表的头结点，有时我们还会**把链表的实际结点个数存入到头结点中。**

类型定义如下：

type pointer=^node;

node=record

data:datatype;

next:pointer;

end;

**A.****建立一个单链表****(****输入一系列自然数，以****0****表示结束****)**

procedure creat;

var head，p，s:pointer;

b:Boolean;

x:integer;

begin

new(head);

p:=head;

b:=true;

while b do begin

readln(x)；

if x<>0 then begin new(s);s^.data:=x;p^.next:=s;p:=s; end

else b:=false;

end;

p^.next:=nil;

end;

**B****．查找**

p:=head^next;

while (p^.data<>x) and (p^.next<>nil) do p:=p^.next; \{ 找到第一个就结束\}

ifp^.data= xthen找到了处理else输出不存在；

**如果想找到所有满足条件的结点，则修改如下：**

p:=head^next;

whilep^.next<>nildo\{ 一个一个判断\}

begin

ifp^.data = xthen找到一个处理一个；

p:=p^.next;

end;

**取出单链表的第****i****个结点的数据域：**

functionget(head:pointer;i:integer):integer;

var p:pointer;j:integer;

begin

p:=head^.next;

j:=1;

while(p<>nil) and (j<i) do

begin

p:=p^.next;

j:=j+1;

end;

if(p <> nil)and(j=i)thenwriteln(p^.data)

elsewriteln(‘i not exsit!’);

end;

**C****．插入一个结点（在单链表中第****i****个结点（****i>=0****）之后插入一个结点（值为****X****））**

Procedure insert(var head:pointer;i，X:integer);

Var s，p:pointer;

J:integer;

Begin

New(s);s^.data:=X;

If i=0 then begin s^.next:=head^.next;head:=s;end\{ 插在第一个结点之前\}

Else begin

P:=head;

J:=1;

While (p<>nil) and (j<i) do\{ 找位置\}

Begin

J:=j+1;

P:=p^.next;

End;

If (p<>nil) then begin s^.next:=p^.next;p^.next:=s;end

Else writeln(‘not found i’)

end

End;

**D****．删除某个结点（从单链表中删除其值为****X****的结点）**

Procedure delete(var head:pointer;x:integer);

Var p，q:pointer;

Begin

If head=nil then writeln(‘no element’)

Else begin q:=head;p:=head^.next;

While(p<>nil) and (p^.data<>X) do

Begin

q:=p;p:=p^.next

End

If p<>nil then begin q^.next:=p^.next;

Dispose(p);

End

Else writeln(‘not found X’)

end

End;

**E****．求单链表的实际长度**

functionlen(head:pointer):integer;

var n:integer;

begin

p:=head;

n:=0;

whilep<> nildo

begin

n:=n+1;

p:=p^.next;

end;

len:=n;

end;

**F****．插入排序**

建表的过程中实现了排序。本质是插入排序。

**G****．单链表的归并操作**

**\[****问题描述****\]**

已知线性表L1和L2中的数据元素按值非递减有序排列，现要求将L1和L2归并成一个新的线性表L3，使L3中的数据元素仍按非递减有序排列。例如：L1=（1，3，4，5，8，9，10，11，12），L2=（2 ，4， 6， 8），则L3=（1，2，3，4，4，5，6，8，8，9，10，11，12）。

注意：相同元素照算。

**\[****参考程序****\]**

proceduremerge(h1，h2:pointer; varh3:pointer);

\{ 将头指针分别为h1，h2的两个单链表归并成一个新的单链表，该链表头指针为h3\}

varp1，p2，p3:pointer;\{ 临时用工作指针，一般不能破坏头指针\}

begin

p1:=h1^.next;

p2:=h2^.next;

h3:=h1;\{ 新链表共用第一个链表，简化，也可以另外开辟一个头结点\}

p3:=h3;

while(p1<>nil) and (p2<>nil)do\{ 归并\}

begin

ifp1^.data<=p2^.datathenbegin\{ 将p1结点链接到p3中去\}

p3^.next:=p1;\{ 指向\}

p3:=p1;\{p3后移\}

p1:=p1^.next\{p1后移\}

end

elsebegin\{ 将p2结点链接到p3中去\}

p3^.next:=p2;

p3:=p2;

p2:=p2^.next

end;

ifp1<>nilthenp3^.next:=p1\{ 将p1中剩下的结点一起链接到p3中\}

elsep3^.next:=p2;\{ 将p2中剩下的结点一起链接到p3中\}

end;

**（2）****双链表**

单链表的缺点是任何操作都必须从表头开始，线性检索进行。假如要你把一个链表从尾到头输出，那效率就太低了。所以有时还用到双链表，每个结点有两个指针域和若干数据域，其中一个指针域指向它的前趋结点，一个指向它的后继结点。它的优点是访问、插入、删除更方便，速度也快了。但增加了空间开销。它的类型定义如下：

type pointer=^node;

node=record

data:datatype;

pre，next:pointer; \{pre指向前趋，next指向后继\}

end;

双链表的操作与单链表基本一致，我们可以通过画图来说明。

Procedure insert(var head:pointer;i，x:integer);

\{ 在双向链表的第i个结点之前插入X\}

Vars，p:pointer;j:integer;

Begin

New(s);

S^.data:=x;

P:=head;

j:=0;

while(p^.next<>nil) and (j<i) do

begin

p:=p^.next;

j:=j+1;

end;\{p指向第i个结点\}

if p=nil then writeln(‘no this position!’)

elsebegin\{ 将结点S插入到结点P之前\}

s^.pre:=p^.pre;\{ 将S的前趋指向P的前趋\}

p^.pre:=s;\{ 将S作为P的新前趋\}

s^.next:=p;\{ 将S的后继指向P\}

p^.pre^.next:=s;\{ 将P的本来前趋结点的后继指向S\}

end;

End;

Proceduredelete(var head:pointer;i:integer);\{ 删除双向链表的第i个结点\}

Varp:pointer;j:integer;

Begin

P:=head;

j:=0;

while(p^.next<>nil) and (j<i) do

begin

p:=p^.next;

j:=j+1;

end;\{p指向第i个结点\}

if p=nil then writeln(‘no this position!’)

elsebegin\{ 将结点P删除\}

p^.pre^next:=p^.next;\{P的前趋结点的后继赋值为P的后继\}

p^.next^.pre:=p^.pre;\{P的后继结点的前趋赋值为P的前趋\}

end;

End;

**（3）****循环链表**

**A****．单向循环链表：**最后一个结点的指针指向头结点。如下图：

**B****．双向循环链表**：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个结点。如下图：

**例****3****、循环链表的应用举例：约瑟夫问题。**

n只猴子报到m时退出到圈外。任务是从键盘读入n，m，输出最后的大王是几号？

**\[****数据结构****\]**显然是一个单向循环链表。数据域为猴子的编号，指针指向下一个猴子。

**\[****算****法****\]**报数实际上是计数，只要设一个计数器就可以了。当计数器由0变化到m时，删除该结点，计数器回0继续计数（或者用求余运算）。直到链表中剩下一个结点。

**\[****程序****1-5\]** **模拟法**

typepointer=^monkey;

monkey=record

num:integer;

next:pointer;

end;

varhead，p，q:pointer;

n，m:integer;

procedurecreat(var head:pointer;n:integer);\{ 建立一个单向循环链表\}

var p，q:pointer;

i:integer;

begin

new(p);\{ 建立头结点\}

head:=p;

p^.num:=1;

q:=p;\{q指向链表的尾结点\}

for i:=2tondo\{ 建立链表\}

begin

new(p);

p^.num:=i;

q^.next:=p;\{ 把P结点连接到q的后面\}

q:=p;

end;

q^.next:=head;\{ 建立循环链表\}

end;

procedure selectking(var head:pointer;var m:integer);

var p，q:pointer;

i，count:integer;

begin

p:=head;

count:=1;\{ 指向第一个结点，洋计数1\}

q:=p;\{q为p的前趋\}

repeat

p:=q^.next;

count:=count+1;

if count mod m=0thenbegin\{ 该猴子出圈，即删除结点\}

q^.next:=p^.next;

dispose(p);

end

elseq:=p;\{ 指针往后移一个\}

untilp^.next=p;\{ 只剩下一个结点\}

head:=p;

end;

begin\{main\}

write(‘input monkey num :’);

readln(n);

writeln(‘the baoshu number:’);

readln(m);

creat(head，n);

selectking(head，m);

writeln(‘the moneyking is no.’，head^.num);

readln

end.

**\[****运行测试****\]**

输入：input monkey num :13

the baoshu number:5

输出：the moneyking is no.6

**三、线性表应用举例**

**例****4****、编码问题**

**\[****问题描述****\]**

设有一个数组A：ARRAY\[0..N-1\] OF INTEGER；数组中存储的元素为0-N-1之间的整数，且A\[I\]≠A\[J\] (当I≠J)时。

例如：N=6时，有：（4，3，0，5，1，2）

此时，数组A的编码定义如下：

A\[0\]的编码为0：

A\[I\]的编码为：在A\[0\]，A\[1\]，……A\[I-1\]中比A\[I\]的值小的元素的个数（I=1，2，……N-1）

所以上面数组A的编码为:B=(0，0，0，3，1，2)

程序要求解决以下问题

①给出数组A后，求出其编码；

②给出数组A的编码后，求出A的原数据。

**\[****算法设计****\]**

问题①比较简单，只要统计一下即可。

问题②是一个线性表的删除问题，将0到 N-1之间的N个整数顺序放在一个线性表C中，取出编码数组B中的最后一个元素b\[N-1\]，则C中的第b\[N-1\]个元素为数组A的最后一个元素，取出该元素后从C中删除之，再取编码数组B中的前一个元素，重复上述操作，直到数组A的所有元素都得到为止。

**\[****参考程序****\]**

const maxn=50;

type arraytype=array \[0..maxn\] of integer;

var n，select:integer;

a，b:arraytype;

procedure init(var v:arraytype);

var i:integer;

begin

write('Input n:');

readln(n);

write('Input '，n，' integer number:');

for i:=0 to n-1 do read(v\[i\]);

readln

end;

procedure print(v:arraytype);

var i:integer;

begin

for i:=0 to n-1 do write(v\[i\]，' ');

writeln

end;

procedure task1;

var i，j:integer;

begin

init(a);

for i:=0 to n-1 do

begin

b\[i\]:=0;

for j:=0 to i-1 do

if a\[i\]>a\[j\] then b\[i\]:=b\[i\]+1;

end;

writeln('The code of array A is:');

print(b)

end;

procedure delete(var v:arraytype;var n:integer;i:integer);

var j:integer;

begin

for j:=i to n-2 do v\[j\]:=v\[j+1\];

n:=n-1

end;

procedure task2;

var i，len:integer;

c:arraytype;

begin

init(b);

for i:=0 to n-1 do c\[i\]:=i;

len:=n;

for i:=n-1 downto 0 do

begin

a\[i\]:=c\[b\[i\]\];

delete(c，len，b\[i\])

end;

writeln('Array A is:');

print(a)

end;

begin\{main\}

writeln(' ':20，'1--Task1');

writeln(' ':20，'2--Task2');

write(' ':20，'Input your select(1 or 2):');

readln(select);

if select=1 then task1 else task2

end.

**例****5****、全排列问题**

**\[****问题描述****\]**

将1到N的N个自然数排成一列，共有1\*2\*3……\*N种不同的排列方法，如N=3时，有6种排列方案，分别为123，132，213，231，312，321.试编程序输出1到N的全部排列，假设N<10.

**\[****问题分析****\]**

为了设计出由计算机输出1到N的全部排列程序，就必须寻找不同排列之间的规律.通过观察N=5(参见本例的运行结果)的排列情况，可以发现，如果把每个排列看作一个自然数，则所有排列对应的数是按从小到大的顺序排列，从当前的排列产生下一个排列时必然会造成某一位置上的数字变大，这一位置显然应该尽量靠右，并且在它左边位置上的数字保持不变，这就意味着这一位置变成的数字来自于它的右边，并且变大的幅度要尽可能小，也就是说在它右边如有几个数同时比它大时，应该用其中最小的来代替它.由于这一位置是满足上述条件的最右边的一位，所以在它右边的所有数字按逆序排列，即在这些数字的右边没有一个大于它的数.程序中先从右至左找到第一个位置，该位置上的数比它右边的数小，这个位置就是所要找的满足上述条件的位置，然后再从右到左找到第一个比该位置上的数字大的数字所在的位置，将这两个位置上的数字交换，再将该位置右边的所有元素颠倒过来，即将它们按从小到大的顺序排列，就得到了下一个排列.

**\[****参考程序****\]**

const maxn=9;

type arraytype=array \[0..maxn\] of integer;

var i，j，n，temp:integer;

k，total:longint;

a:arraytype;

begin

write('Input n:'); readln(n);

for i:=1 to n do a\[i\]:=i;

total:=1;

for i:=1 to n do total:=total\*i;\{ 计算全排列数n!\}

for k:=1 to total do

begin

for i:=1 to n do write(a\[i\]); write(' ');

if k mod 10=0 then writeln;

i:=n-1;

while (i>0) and (a\[i\]>a\[i+1\]) do i:=i-1;

j:=n;

while a\[j\]<a\[i\] do j:=j-1;

temp:=a\[i\]; a\[i\]:=a\[j\]; a\[j\]:=temp;

i:=i+1; j:=n;

while i<j do

begin temp:=a\[i\]; a\[i\]:=a\[j\]; a\[j\]:=temp;

i:=i+1; j:=j-1

end

end;

writeln

end.

**\[****运行程序****\]**下划线表示输入

Input n:5

12345 12354 12435 12453 12534 12543 13245 13254 13425 13452

13524 13542 14235 14253 14325 14352 14523 14532 15234 15243

15324 15342 15423 15432 21345 21354 21435 21453 21534 21543

23145 23154 23415 23451 23514 23541 24135 24153 24315 24351

24513 24531 25134 25143 25314 25341 25413 25431 31245 31254

31425 31452 31524 31542 32145 32154 32415 32451 32514 32541

34125 34152 34215 34251 34512 34521 35124 35142 35214 35241

35412 35421 41235 41253 41325 41352 41523 41532 42135 42153

42315 42351 42513 42531 43125 43152 43215 43251 43512 43521

45123 45132 45213 45231 45312 45321 51234 51243 51324 51342

51423 51432 52134 52143 52314 52341 52413 52431 53124 53142

53214 53241 53412 53421 54123 54132 54213 54231 54312 54321

**例** **6** **、****n****级法雷序列**

**\[****问题描述****\]**

对任意给定的一个自然数n(n<=100)，将分母小于等于n的不可约的真分数按上升的次序排序，并且在第一个分数前加上0/1，而在最后一个分数后加上1/1，这个序列称为n级法雷序列，以Fn表示.例如，F8为:

0/1，1/8，1/7，1/6，1/5，1/4，2/7，1/3，3/8，2/5，3/7，1/2，4/7，3/5，5/8，2/3，5/7，3/4，4/5，5/6，6/7，7/8，1/1.

编程求出n级法雷序列，每行输出10个分数.

**\[****算法设计****\]**

由于程序要求以分数的形式输出法雷序列，对每个真分数必需分别存放其分子分母，这就要用两个线性表来实现.开始时线性表中只有两个元素，分别是0/1和1/1，线性表用两个数组fp和fq来表示，fp存放分子，fq存放分母.所有的真分数用一个两重循环来产生，每次将当前产生的真分数p/q插入到线性表中去.为了保证线性表中所有元素在插入新元素后仍然按从小到大的次序排列，首先要从表中找出第一个不小于p/q的元素，如果该元素等于p/q，则说明p/q不是不可约的真分数，p/q无需插入，否则p/q应插入在表中第一个大于它的元素的位置.当向线性表中插入新元素时，如果该线性表是用数组实现的，则插入新元素之前要将从插入位置直到最后的所有元素都后移一位，然后再插入新元素.删除线性表中元素时，只要将从删除位置之后的那个元素直到最后的所有元素都前移一位即可.由于对实数要避免等或不等的比较，程序中在对两个分数进行比较时，将它们化成了乘式进行.

**\[****参考程序****\]**

const maxn=100;

type arraytype=array \[1..maxn\*maxn\] of integer;

var i，k，n，p，q，total:integer;

fp，fq:arraytype;

begin

write('Input n:'); readln(n);

fp\[1\]:=0; fq\[1\]:=1; fp\[2\]:=1; fq\[2\]:=1; total:=2;

for q:=2 to n do\{ 列举分母\}

for p:=1 to q-1 do\{ 列举分子\}

begin

k:=1;

while p\*fq\[k\]>q\*fp\[k\] do k:=k+1; \{ 寻找插入位置\}

if p\*fq\[k\]<>q\*fp\[k\] then \{ p/q不在表中\}

begin

for i:=total downto k do fp\[i+1\]:=fp\[i\];

for i:=total downto k do fq\[i+1\]:=fq\[i\];

fp\[k\]:=p; fq\[k\]:=q; total:=total+1

end

end;

for i:=1 to total do

begin

write(fp\[i\]，'/'，fq\[i\]，'');

if i mod 10=0 then writeln

end;

writeln

end.

**\[****运行程序****\]**下划线表示输入

Input n:15

0/11/151/141/131/121/111/101/91/82/15

1/72/131/62/111/53/142/93/131/44/15

3/112/73/104/131/35/144/113/85/132/5

5/123/74/95/11 6/137/151/28/157/136/11

5/94/77/123/58/135/87/119/142/39/13

7/105/78/1111/153/410/137/911/144/59/11

5/611/136/713/157/88/99/1010/1111/1212/13

13/14 14/151/1

**例** **7****、构造字串**

**\[****问题描述****\]**

生成长度为n的字串，其字符从26个英文字母的前p(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3,n=5时

‘A B C B A’满足条件

‘A B C B C’不满足条件

**\[****输入****\]**

n,p

**\[****输出****\]**

满足条件的字串

**\[****算法分析****\]**

设：

s—字串；m—s串的指针；

s1、s2—s的两个相邻子串；l—s1和s2的串长；

good—合理标志；

我们从空串出发，逐个字符地延长字串。若当前字符添入后使得字串保持合理的性质，则添入该字符；否则改变字串。

**1、****检查当前字串是否符合条件**

设当前串s=s1‥sm-1sm且s1‥sm-1合理。按照下述方法判断s是否仍然保持其合理性质：分别判断s的后缀中长度为1的两个相邻子串sm-1与sm是否相等；长度为2的两个相邻子串sm-3sm-2与sm-1sm是否相等，……‥，长度为的两个相邻子串s1‥与‥sm是否相等。即：

sm -2l +1‥sm-1与sm-l+1‥sm是否相等（1≤l≤）

若其中一旦出现了两个相邻子串不相等的情况，则说明s1‥sm不合理，good=false，并退出判断过程；若经过次判断后未出现不合理情况，则说明s1‥sm满足条件，good=true。上述判断过程由子程序check完成:

procedure check；

var l:integer；\{ 子序列长度\}

begin

good←true； l←0；\{ 合理标志和子序列长度初始化\}

while good and (l< m div 2) do

\{ 若目前两个相邻子序列不相等且子序列的长度可以延长，则循环\}

begin

l←l+1；\{ 子序列的长度\+1\}

s1←copy(s,m-2\*l+1,l)； \{ 从s的后缀中截出两个长度为l的相邻子序列 \}

s2←copy(s,m-l+1,l)；

good←s1<>s2；\{ 计算两个子序列是否相等的标志\}

end；\{while\}

end；\{check\}

**2、****延长字串**

我们从空串（s=’’,m=0）出发逐个地延长字串。若当前串s1‥sm合理，，则往当前串添入一个字母’a’(m←m+1,sm←’a’)；否则从sm出发，向左搜索小于第p个英文字母顺序的字符，该字符设为它的后继字母。依次类推上述过程，直至长度为n的合理序列产生为止。具体计算过程如下：

输入n和p；

m←0； good←true； s←’’；\{ 从空序列开始延长，合理标志初始化\}

repeat

if good

then begin\{ 若当前序列合理，则加入字母’a’\}

m←m+1； s←s+'a'；

end \{then\}

else if s\[m\]<chr(ord('a')+p-1) \{ 若尾字符存在后继值，则尾字符修正为后继值\}

then s\[m\]←succ(s\[m\])

else begin\{ 否则向左搜索第一个存在后继值的字符\}

repeat

m←m-1；

until (m≤0) or(s\[m\]<chr(ord('a')+p-1))；

if m>0 then s\[m\]←succ(s\[m\])\{ 该字符修正为后继值\}

else输出无解信息并退出程序；

end；\{else\}

check；\{ 检查新序列是否合理\}

until good and (m=n)；\{ 直至产生一个长度为n的合理序列为止\}

writeln(s)；\{ 输出合理序列\}

**四、课后作业**

**作业****1****、一元多相式的表示和加减运算**

\[问题描述\]

在数学上，一个一元n次多项式Pn(x)，可以按升幂写成：

Pn(x)=P0 + P1X + P2X2 \+ P3X3 \+……+ PnXn

它由n+1个系数唯一确定。因此，在计算机里，它可以用一个线性表 P来表示：

P = （P0，P1，P2，……Pn）

每一项的指数i隐含在系数Pi的序号里。

\[任务\]

给定一个一元n次多项式Pn(x) 和一个一元m次多项式Qm(x)，求它们的和与差。

\[数据结构\]

方法1：按n，m分别生成n+1和m+1个结点的两个单链表，即不管系数是否为0都生成一个结点。一个指针域指向后继结点，一个数据域存放系数（不存在的项系数为0）。

浪费了很多空间，尤其是指数很高，而项数很少的情况下，浪费更严重。

方法2：只生成存在的项，实际多少项就有多少结点，每个结点有2个数据域，一个存放系数，一个存放指数。

如有以下多项式P8(x)=3+8x+9x5\+6x8，用上述两种方法表示的示意图分别如下：

方法1示意图

方法2示意图

\[算法分析\]

算法非常简单，遍历两个单链表，根据指数和系数进行相应的加减，生成一个新链表。系数为0的结点删除掉（或不生成这种结点），输出该链表。

**附：计算多项式的和**

设An(x)=a1xe1\+a2xe2\+……+amxen

Bm(x)=b1xe1\+b2xe2\+……+bmxemm≤n

求 cn(x)=An(x)+Bm(x)

=c1xe1\+……+cnxen

**输入：**

(a1，e1)…(an，en)和(b1，e1)…(bm，em)分别表示多项式A和B，

**输出：**

(c1，e)…(cn，en)，表示和多项式c．

**算法分析：**

考虑到如下因素

1．有效利用存贮空间（用cn(x)的存贮空间覆盖An(x)和Bm(x)的存贮空间）；

2．求和运算仅需一个方向的查找；

我们采取单链表存贮多项式

Type

Link=↑node；

node=record

coef： real；\{ 系数\}

exp： integer；\{ 指数\}

next： Link；\{ 后继指针\}

end；

var pa， pb， pc：Link； \{ 多项式A、B及和多项式c对应的三个单链表的“哨兵”\}

例如A4(x)=7+3x+9x8\+5x17

B3(x)=8x+22x7\-9x8

C4(x)=7+11x+22x7\+5x17

“哨兵”的系数域（coef）为空，指数域（exp）为\-1。

**1****、生成多项式链表**

在输入一个多项式的同时，构造其对应链表。该链表的“哨兵”为h。

procedure inpoLy(var h：link)；

begin

输入a，e；\{ 输入第一项的系数和指数\}

while e≥0do

begin

new(p)； p↑．coef←a；p↑．exp←e；\{ 生成单链表的一个结点\}

p↑．next←h；h←p；\{ 该结点插入表首\}

输入 a，e；

end；\{while\}

new(p)；p↑．exp←-1；p↑．next←h； h←p；\{ 生成“哨兵”\}

end；\{inpoly\}

**2****、输出多项式**

输出“哨兵”为h的单链表对应的多项式

procedure outpoly (h：link)；

begin

p←h↑．next；

while p<>nil do

begin

输出p↑．coef和p↑．exp；

p←p↑．next；

end；\{while\}

end；\{outply\}

**3****、和运算**

一元多项式相加的运算规则很简单：两个多项式中所有指数相同的项，对应系数相加。若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复制到“和多项式”中。设p和q分别为多项式A和多项式B的指针。

为了不再生成“和多项式”的结点，我们将多项式B加到多项式A上(pc←pa)。由此得出如下规则：

若p↑．exp<q↑．exp，则多项式A中的p结点应是和多项式中的一项，p指针向后移；

若p↑．exp>q↑exp，则将多项式B中的q结点插在p结点前，且q指针往后移；

若p↑．exp=q↑．exp，则将两个结点中的系数相加。当和不为零时，修改多项式A中p结点的系数，释放多项式B中的q结点；当和为零时，“和多项式”中无此项，从A表中删去p结点，同时释放p结点和多项式B中的q结点，相加过程如下：

procedure polyadd (pa，pb：link； var pc：link)；

begin

p←pa↑．next；q←pb↑．next；

\{p，q分别指向A多项式链表和B多项式链表的第一个结点\}

s←pa；pc←pa；\{s指向A多项式链表的哨兵\}

while (p<>nil)and(q<>nil) do\{ 若A表和B表均未结束，则循环\}

ifp↑．exp<q↑．exp

then begin s←p； p←p↑．next；end\{then\}\{p指针后移\}

else if p↑．exp>q↑exp\{q结点插在p结点之前，q指针后移\}

then begin

u←q↑．next；q↑．next←p；s↑．next←q；s←q；q←u；

end\{then\}

else begin

x←p↑．coef+q．coef；

if x<>0

then begin

p↑．coef←x； s←p；\{ 修改p结点的系数域\}

end；\{then\}

else begin\{ 删除p结点\}

s↑．next←p↑．next； dispose(p)；

end；\{else\}

p←s↑．next；u←q；

q←q↑．next； dispose(u)；

end；\{else\}

if q<>nil then s↑．next←q；\{ 将多项式B中剩余结点链入和多项式c中\}

dispose(pb)；\{ 释放多项式B的哨兵\}

end；\{polyadd\}

由此得出算法：

inpoly(pa)；\{ 生成多项式A\}

inpoly(pb)；\{ 生成多项式B\}

polyadd(pa，pb，pc)；\{ 计算和多项式c\}

outpoly（pc）；\{ 输出和多项式c\}

**作业****2****、多项式的乘法**

**\[****问题描述****\]**

请编程序把含有乘法运算的代数多项式表达式改写成不含乘法的代数多项式。为简化计算，特做以下约定：

(1) 代数多项式表达式中只涉及一个代数符号*a*；

(2) 含有乘法运算的代数多项式表达式都是两个不含乘法运算的代数多项式直接相乘的形式，而且这两个参加乘法的代数多项式都用圆括号括起来了。乘法用符号表示，不得省略。

(3) 常数项以外的各项都是 *xa*^ y的形式，其中*x*为该项的系数，而*y*是该项的指数。x =1 时，不得简写成 *a*^ y，应写成1 *a*^ y 。而y =1时，不得简写成*xa*，应写成 xa^ 1。

**输入：**文件中每行存放一个含有乘法的代数多项式表达式。

**输出：**每行输出一个问题的解。要求指数大的项不能出现在指数小的项之后，指数

相同的项必须合并同类项。不允许出现不必要的空白字符。

例如：

输入

(5a^2+3a^1+2)\*(4a^1+1)

(5a^1+1)\* (5a^1+1)

输出

20a^3+17a^2+11a^1+2

25a^2+10a^1+1

**\[****算法分析****\]**

多项式乘法可以模仿高精度乘法来做，但它不需要进位，而要合并同类项。

首先，要设计好读入过程，既不要太繁琐，充分利用题目上的限制条件，又要有一定的健壮性。要确保正确地读入多项式。

然后，可以设计出打印输出的程序，以验证读入程序的准确性。要注意两点：一是不输出系数为0的项，而是指数为0，只打系数。

相对来说，乘法过程就比较简单了。用两重循环，把多项式①的每一项依次乘以多项式②的每一项，即系数相乘、指数相加，然后把新产生的项按指数递减的顺序插入多项式③中。插入的过程，用插入排序即可，遇到指数相同的项，只需把系数加进去，否则就在合适位置插入一个新的项。

最后，多设计几组“危险数据”，找找程序错误，如果注意了上面几点，程序结构清晰，模块化很好的话，即可完成此题。

**\[****参考程序****\]**

const

inf='t2.in';

outf ='t2.out';

type

Texp =array\[0..5000,1..2\] of integer;

var

a,b,c :Texp;

len1,len2,len3:integer;

ch :char;

procedure readnum(var num:integer);\{ 读字符串\}

begin

num:=0;

while (ch<='9') and (ch>='0') do

begin

num:=num\*10+ord(ch)-ord('0');

read(ch);

end;

if ch='+' then read(ch);

end;

procedure readin(var exp:Texp;var len:integer);\{ 读表达式\}

begin

len:=0;

read(ch);

while ch<>')' do

begin

inc(len);

readnum(exp\[len,1\]);

if ch='a' then

begin

read(ch);read(ch);

readnum(exp\[len,2\]);

end

else exp\[len,2\]:=0;

end;

procedure init;

begin

readin(a,len1);

read(ch);

readin(b,len2);

readln;

fillchar(c,sizeof(Texp),0);

len3:=0;

c\[0,2\]:=maxint;

end;

procedure work;\{ 表达式相乘，并合并同类项\}

var

i,j,k,p,t1,t2 :integer;

begin

for i:=1 to len1 do

for j:=1 to len2 do

begin

t1:=a\[i,1\]\*b\[j,1\];

t2:=a\[i,2\]+b\[j,2\];

k:=len3;

while c\[k,2\]<t2 do dec(k);

if c\[k,2\]=t2 then inc(c\[k,1\],t1)

else begin

inc(len3);inc(k);

for p:=len3 downto k+1 do c\[p\]:=c\[p-1\];

c\[k,1\]:=t1;

c\[k,2\]:=t2;

end;

procedure out;

var

i :integer;

begin

write(c\[1,1\]);

if c\[1,2\]>0 then write('a^',c\[1,2\]);

for i:=2 to len3 do

begin

write('+',c\[i,1\]);

if c\[i,2\]>0 then write('a^',c\[i,2\]);

end;

writeln;

end;

BEGIN

assign(input,inf);reset(input);

assign(output,outf);rewrite(output);

while not eof do

begin

init;

work;

out;

if eoln then readln;

end;

close(output);

close(input);

END.

**\[****测试数据****\]**

输入：

(1)\*(2)

(1a^1+1)\*(5)

(2a^1+5)\*(1a^1+6)

(3a^1+3)\*(2a^1+3)

(2a^2+3a^1+2)\*(2a^1+3)

(1a^1+8)\*(4a^2+1a^1+3)

(1a^2+1a^1+1)\*(1a^2+1a^1+1)

(1a^20+2a^19+3a^18+4a^17+5a^16+6a^15+7a^14+8a^13+9a^12+10a^11+11a^10+12a^9+13a^8+14a^7+15a^6+16a^5+17a^4+18a^3+19a^2+20a^1+2)\*(20a^20+19a^19+18a^18+17a^17+16a^16+15a^15+14a^14+13a^13+12a^12+11a^11+10a^10+9a^9+8a^8+7a^7+6a^6+5a^5+4a^4+3a^3+2a^2+1a^1+1)

输出：

5a^1+5

2a^2+17a^1+30

6a^2+15a^1+9

4a^3+12a^2+13a^1+6

4a^3+33a^2+11a^1+24

1a^4+2a^3+3a^2+2a^1+1

20a^40+59a^39+116a^38+190a^37+280a^36+385a^35+504a^34+636a^33+780a^32+935a^31+1100a^30+1274a^29+1456a^28+1645a^27+1840a^26+2040a^25+2244a^24+2451a^23+2660a^22+2870a^21+2701a^20+2491a^19+2283a^18+2078a^17+1877a^16+1681a^15+1491a^14+1308a^13+1133a^12+967a^11+811a^10+666a^9+533a^8+413a^7+307a^6+216a^5+141a^4+83a^3+43a^2+22a^1+2

**作业****3****、魔术师与扑克问题**

\[问题描述\]

13张黑桃扑克（A 2 3 4 5 6 7 8 9 10 J Q K），预先排好，正面朝下拿在魔术师的手里，从最上面开始，第一次数一张牌翻过来放在桌面上，正好是“A”；第二次数两张牌，数1的那张放在手中扑克的最下面，数2的那张翻过来放在桌面上正好是“2”；……，如此下去，放在桌面上的牌最后正好是“A 2 3 4 5 6 7 8 9 10 J Q K”的顺序（从下向上）。

\[任务\] 编程找出魔术师手中扑克原来的排列顺序（从下向上）。

**作业****4****、****0-1****游戏**

\[问题描述\]

你和你的朋友玩以下的游戏：你的朋友写下一个由0和1组成的字符串，你从中选择连续的子串（例如从第3个到第5个连续的3个数字），然后问他这个子串中1的个数是奇数还是偶数，你的朋友回答了，然后你再继续问类似的问题。你估计你朋友的回答中有一些是错误的，你想证明他的错误，所以你决定编写一个程序来帮你解决这个问题。这个程序会根据你的问题以及他的回答来判断他是否错了，你程序的目标是找到第1个可能的错误回答，也就是说存在一个数字串满足前面所有的问题，但对于当前的问题不满足而且没有一个数字串满足。

\[输入\]

第1行：一个数字，告诉你该数字串的个数（<=1000000000）；

第2行：一个数字，告诉你总共提了多少问题（<=5000）；

剩下的各行，每行是一个问题和对应的回答，每行共有3部分组成，每部分之间有一个空格隔开，第1部分是一个整数表示子串的开始位置，第2部分也是一个整数表示子串的结束位置，第3部分是一个单词（even表示子串中1的个数是偶数；odd表示子串中1的个数是奇数）。

\[输出\]

只有1个整数X，该整数表示存在一个01的数串满足前X个奇偶条件，但不满足第X+1个奇偶条件。若存在一个01串满足所有的条件，则X就是所有问题的个数。

\[样例输入与输出\]

输入：

1 2 even

3 4 odd

5 6 even

1 6 even