数据结构作业系统答案.doc

◆2.11② 设顺序表L中的数据元素递增有序。
试写一算法，将x插入到L的适当位置上,并保
持该表的有序性。

要求实现下列函数:
void InsertOrderList（SqList ＆L, ElemType x）
/* 在有序的顺序表 L 中保序插入数据元素 x ＊/

顺序表类型定义如下：
typedef struct ｛
ElemType ＊elem；
int length;
int listsize;
} SqList；
void InsertOrderList（SqList ＆L， ElemType x)
// 在有序的顺序表 L 中保序插入数据元素 x
{
int i=0，j；
while(L.elem[i]〈x&＆i〈L.length）
i++；
for（j=L.length；j>i;j——）
{
L。elem[j］=L。elem[j-1];
}
L.elem[i]=x；
L。length+=1;
｝
◆2.12③ 设A=（a1,…，am)和B=(b1，…，bn）均为有序顺序表，
A'和B'分别为A和B中除去最大共同前缀后的子表(例如,
A=(x，y,y，z，x,z），B=(x，y,y,z,y,x,x,z），则两者中最大
的共同前缀为(x，y，y,z）， 在两表中除去最大共同前缀后
的子表分别为A'=(x,z）和B'=（y,x，x，z）)。若A'=B’=空表，
则A=B;若A’=空表，而B'≠ 空表，或者两者均不为空表,
且A'的首元小于B'的首元,则A〈B;否则A>B。试写一个比
较A和B大小的算法。（注意:在算法中,不要破坏原表A
和B,也不一定先求得A’和B’才进行比较)。

要求实现下列函数:
char Compare（SqList A， SqList B)；
/* 比较顺序表A和B， ＊/
/* 返回'〈'， 若A<B; */
/* '=’， 若A=B； */
/* ’>’, 若A〉B ＊/

顺序表类型定义如下：
typedef struct ｛
ElemType *elem；
int length;
int listsize;
｝ SqList;
char Compare（SqList A， SqList B)
// 比较顺序表A和B,
// 返回'〈’, 若A<B；
// '='， 若A=B；
// '〉’, 若A>B
｛
int i=0;
while（A.elem［i］==B.elem［i]&＆i<A.length&＆i<B。length)
i++;
if（i==A.length＆＆i==B.length）
return ’='；
else if(A.elem［i］<B。elem[i］|｜i==A.length）
return '〈’；
else if（A.elem［i]〉B.elem［i］|｜i==B.length）
return ’〉’;
}
2。13② 试写一算法在带头结点的单链表结构上实现线性表操作
Locate（L，x）。

实现下列函数:
LinkList Locate（LinkList L, ElemType x)；
// If 'x' in the linked list whose head node is pointed
// by ’L'， then return pointer pointing node ’x’,
// otherwise return ’NULL'

单链表类型定义如下:
typedef struct LNode {
ElemType data；
struct LNode ＊next；
｝ LNode, *LinkList；
LinkList Locate（LinkList ＆L, ElemType x）
// If ’x’ in the linked list whose head node is pointed
// by ’L', then return pointer ha pointing node 'x’,
// otherwise return ’NULL'
{
LinkList p；
int i=0；
p=L—>next;
while(p—〉data!=x＆＆p！=NULL)
｛
i++；
p=p-〉next；
｝
return p；

｝
2.14② 试写一算法在带头结点的单链表结构上实现线性表
操作Length（L）.

实现下列函数：
int Length（LinkList L);
// Return the length of the linked list
// whose head node is pointed by 'L'

单链表类型定义如下：
typedef struct LNode｛
ElemType data;
struct LNode *next；
} LNode， *LinkList；
int Length(LinkList L)
// Return the length of the linked list
// whose head node is pointed by ’L'
{
LinkList p；
int i=0;
p=L-〉next；
while(p！=NULL）
｛
i++；
p=p—〉next；
｝
return i；
}
2。17② 试写一算法，在无头结点的动态单链表上实现
线性表操作INSERT（L,i，b)，并和在带头结点的动态单
链表上实现相同操作的算法进行比较.

实现下列函数:
void Insert（LinkList &L， int i， ElemType b）;

单链表类型定义如下：
typedef struct LNode｛
ElemType data;
struct LNode ＊next;
｝ LNode, *LinkList；
void Insert（LinkList &L, int i， ElemType b)
{
LinkList p，q;
int j=2;
p=L;
while（j<i)
{
j++;
p=p—〉next；
}
if(i！=0&&i!=1)
｛
q=（LinkList)malloc（sizeof(LNode)）;
q-〉data=b;
q->next=p—>next；
p-〉next=q;
｝
if(i==1)
{
q=(LinkList）malloc（sizeof(LNode));
q->data=b;
q—〉next=p；
L=q；
}
｝
2.18② 同2.17题要求.试写一算法,
实现线性表操作DELETE（L，i)。

实现下列函数:
void Delete(LinkList &L， int i）；

单链表类型定义如下：
typedef struct LNode｛
ElemType data；
struct LNode ＊next;
} LNode， ＊LinkList；
void Delete(LinkList &L， int i）
｛
LinkList p，q;
int j=2；
p=L;
while（j〈i＆＆p!=NULL)
{
j++;
p=p—〉next;
}
if（i！=0＆＆i!=1)
{
q=p—>next;
p->next=q->next；
free（q）;
}
if(i==1)
｛
q=L;
L=L—〉next;
free（q）；
}
｝
2。20② 同2.19题条件，试写一高效的算法，删除表中所
有值相同的多余元素 （使得操作后的线性表中所有元素的
值均不相同） 同时释放被删结点空间,并分析你的算法的
时间复杂度。

实现下列函数：
void Purge(LinkList ＆L)；

单链表类型定义如下：
typedef struct LNode｛
ElemType data;
struct LNode ＊next；
} LNode, *LinkList;
void Purge（LinkList ＆L）
｛
LinkList p,q;
int i=0;
p=L;
while（p！=NULL&&p—〉next!=NULL）
｛
if(p—>data==p->next—>data)
｛
q=p->next；
p-〉next=q->next；
free（q）;
｝
else
p=p—>next;
}
｝
◆2.21③ 试写一算法，实现顺序表的就地逆置，
即利用原表的存储空间将线性表（a1,a2,…，an)
逆置为(an，an—1,…,a1)。

实现下列函数：
void Inverse(SqList &L)；

顺序表类型定义如下:
typedef struct {
ElemType ＊elem;
int length；
int listsize;
｝ SqList；
void Inverse(SqList &L）
｛
int i=0,j=0;
i=L。length/2；
for(j=0；j〈i;j++）
｛
ElemType e=L.elem［j］；
L.elem[j］=L.elem[L。length—j—1］;
L.elem[L。length—j—1］=e;
｝
｝
◆2.22③ 试写一算法，对单链表实现就地逆置。

实现下列函数：
void Inverse（LinkList ＆L);
/* 对带头结点的单链表L实现就地逆置 ＊/

单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
｝ LNode， ＊LinkList;
void Inverse（LinkList ＆L）
/＊ 对带头结点的单链表L实现就地逆置 */
｛
LinkList p，q，k;
q=p=L-〉next;
while(p->next!=NULL)
{
k=q；
q=p->next;
p->next=q—〉next；
q-〉next=k;
｝
L-〉next=q；
}

2.23③ 设线性表A=（a1，..。,am）， B=(b1，...,bn），试写
一个按下列规则合并A、B为线性表C的算法,即使得
C=(a1，b1，。.。,am,bm,bm+1,...,bn) 当m≤n时;
或者 C=（a1，b1，...,an，bn,an+1,。.。,am) 当m＞n时。
线性表A、B和C均以单链表作存储结构，且C表利用A表和
B表中的结点空间构成。注意:单链表的长度值m和n均未
显式存储。

实现下列函数:
void Merge(LinkList ha, LinkList hb， LinkList ＆hc)
/＊ 依题意，合并带头结点的单链表ha和hb为hc */

单链表类型定义如下:
typedef struct LNode{
ElemType data；
struct LNode ＊next；
} LNode， ＊LinkList;

void Merge（LinkList ha, LinkList hb， LinkList ＆hc）
/* 依题意，合并带头结点的单链表ha和hb为hc ＊/
｛
LinkList p，q,k，r；
p=ha—〉next；
q=hb-〉next;
if（p==NULL)hc=hb;
else if(q==NULL) hc=ha;
else
｛
while（p—〉next！=NULL＆＆q->next！=NULL）
｛
k=p—>next;
r=q—>next;
p-〉next=q；
p=k；
q->next=p；
q=r;
｝
if(p-〉next！=NULL）
q—>next=p—>next;
p-〉next=q;
hc=ha；

｝
}

◆2.24④ 假设有两个按元素值递增有序排列的线性表
A和B，均以单链表作存储结构,请编写算法将A表和B表
归并成一个按元素值递减有序（即非递增有序，允许表
中含有值相同的元素)排列的线性表C， 并要求利用原
表(即A表和B表）的结点空间构造C表。

实现下列函数：
void Union（LinkList &lc, LinkList la， LinkList lb)；
/* 依题意，利用la和lb原表的结点空间构造lc表 */

单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next；
} LNode, ＊LinkList；

void Union（LinkList &lc， LinkList la, LinkList lb）
｛
LinkList pa=la—>next;
LinkList pb=lb-〉next;
LinkList pre=NULL;
LinkList q，pc;
while（pa｜|pb)
｛
if((pa—>data〈pb-〉data&&pa！=NULL)||pb==NULL）
{
pc=pa;
q=pa->next;
pa->next=pre；
pa=q；

}
else
｛
pc=pb;
q=pb—>next；
pb—>next=pre;
pb=q；

}
pre=pc;
printf（”%s”，"done")；
｝
lc=la；
la->next=pc; //构造新表头

/* LinkList pa = la—>next；
LinkList pb = lb-〉next；
LinkList pc = la;
lc = la；
while( pa ＆＆ pb )
{
if( pa—>data <= pb-〉data ）
｛

pc->next = pa；
pc = pa；
pa = pa-〉next；
｝
else
{
pc—〉next = pb；
pc = pb；
pb = pb->next；
}
}
pc—>next = pa? pa： pb；
free（ lb ）;
//将c实现就地逆置 ’
LinkList p，q；
p = lc->next;
while( p—〉next )
{
q = p->next;
p—〉next = p—>next->next；
q-〉next = lc—>next;
lc—>next = q；
}
＊/
｝

2.31② 假设某个单向循环链表的长度大于1，且表
中既无头结点也无头指针.已知s为指向链表中某个
结点的指针,试编写算法在链表中删除指针s所指结
点的前驱结点。

实现下列函数：
ElemType DeleteNode（LinkList s);
/＊ 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */

单链表类型定义如下：
typedef struct LNode{
ElemType data；
struct LNode *next；
} LNode, *LinkList;

ElemType DeleteNode（LinkList s）
/* 删除指针s所指结点的前驱结点,并返回被删结点的元素值 */
｛
LinkList p;
p=s—>next；
while（p-〉next—>next!=s）
p=p—〉next;
ElemType e=p—>next->data；
p-〉next=s；
return e;
}

2.32② 已知有一个单向循环链表，其每个结点中
含三个域：prev、data和next，其中data为数据域,
next为指向后继结点的指针域，prev也为指针域，
但它的值为空（NULL），试编写算法将此单向循环链
表改为双向循环链表，即使prev成为指向前驱结点
的指针域。

实现下列函数：
void PerfectBiLink（BiLinkList &CL）;

双向循环链表类型定义如下:
typedef struct BiNode {
ElemType data;
int freq； // 2。38题用
struct BiNode ＊prev，
*next;
} BiNode， *BiLinkList；

void PerfectBiLink（BiLinkList ＆CL)
{
BiLinkList p，q，k；
k=p=q=CL;
while(p—>next!=q）
｛
p=p—〉next;
p->prev=k；
k=p；
}
q—〉prev=p；
}

◆2。33③ 已知由一个线性链表表示的线性表中含有
三类字符的数据元素（如:字母字符、数字字符和其
它字符)，试编写算法将该线性链表分割为三个循环
链表，其中每个循环链表表示的线性表中均只含一类
字符。

实现下列函数:
void Split(LinkList &lc， LinkList ＆ld, LinkList ＆lo, LinkList ll）;

单链表类型定义如下:
typedef struct LNode｛
ElemType data；
struct LNode ＊next；
} LNode, ＊LinkList;

void Split（LinkList ＆A， LinkList ＆B, LinkList ＆C， LinkList L)
{
LinkList s,p,q,r；
s=L->next;
A=（LinkList）malloc（sizeof(LNode)）;p=A;
B=(LinkList)malloc（sizeof(LNode））;q=B；
C=（LinkList）malloc（sizeof(LNode))；r=C； //建立头结点
while（s)
{
if(（s->data>='a’&＆s->data<=’z’）｜|(s—〉data<='Z'&&s->data〉=’A’）)
｛
p—>next=s;p=s；
｝
else if（s->data〉='0'＆&s->data〈='9’）
｛
q—>next=s;q=s；
｝
else
{
r->next=s；r=s；
｝
s=s—〉next；
｝//while
p-〉next=A；q—>next=B；r-〉next=C； //完成循环链表
}

2.37④ 设以带头结点的双向循环链表表示的线性
表L=(a1,a2,。..，an）。试写一时间复杂度为O(n）的
算法,将L改造为L=(a1,a3,.。。，an，.。。,a4，a2）。

实现下列函数：
void ReverseEven(BiLinkList &L）；

双向循环链表类型定义如下：
typedef struct BiNode ｛
ElemType data；
int freq； // 2。38题用
struct BiNode ＊prev,
*next;
} BiNode， *BiLinkList;

void ReverseEven(BiLinkList ＆L)
｛
BiLinkList p=NULL；
p=L-〉next;
while(p—>next！=L&&p—>next—〉next!=L）
{
p->next=p—>next-〉next；
p=p—>next;
｝ //此时p指向最后一个奇数结点
if(p-〉next==L） p->next=L—>prev->prev;
else p—〉next=L->prev；
p=p—〉next; //此时p指向最后一个偶数结点
while(p-〉prev—>prev!=L)
｛
p—〉next=p->prev—>prev;
p=p—>next；
}
if（p!=L)
p—>next=L; //按题目要求调整了next链的结构,此时pre链仍为原状
for（p=L；p-〉next！=L；p=p-〉next） p—>next—>prev=p；
L—〉prev=p; //调整pre链的结构,同2.32方法
}

◆2。39③ 试对稀疏多项式Pn(x）采用存储量同多项式项
数m成正比的顺序存储结构，编写求Pn（x0)的算法（x0为
给定值）,并分析你的算法的时间复杂度。

实现下列函数:
float Evaluate（SqPoly pn, float x）;
/＊ pn。data［i］。coef 存放ai， ＊/
/＊ pn.data[i].exp存放ei （i=1,2，.。.，m） */
/＊ 本算法计算并返回多项式的值.不判别溢出。 */
/＊ 入口时要求0≤e1〈e2<.。.〈em,算法内不对此再作验证＊/

多项式的顺序存储结构:
typedef struct {
int coef；
int exp;
} PolyTerm;

typedef struct {
PolyTerm ＊data；
int length；
} SqPoly；

float f(float x，int j）
｛
int i；
float s = 1;
for（ i = 0 ; i 〈 j； ++i )｛
s *= x；
｝
return s；
｝
float Evaluate（SqPoly pn, float x)
/* pn.data[i].coef 存放ai, */
/＊ pn.data［i］.exp存放ei (i=1,2，。..,m) ＊/
/* 本算法计算并返回多项式的值.不判别溢出。 */
/* 入口时要求0≤e1<e2〈...<em,算法内不对此再作验证＊/
{
int i;
float s = 0；
for( i = 0； i < pn.length; ++i ）{
s += pn。data[i].coef * f（ x, pn。data［i］。exp ）;
}
return s；
｝

◆2。41② 试以循环链表作稀疏多项式的存储结构,
编写求其导函数的算法，要求利用原多项式中的结
点空间存放其导函数(多项式)，同时释放所有无
用（被删）结点。

实现下列函数：
void Difference(LinkedPoly &pa）;
/* 稀疏多项式 pa 以循环链表作存储结构， ＊/
/＊ 将此链表修改成它的导函数，并释放无用结点 ＊/

链式多项式的类型定义:
typedef struct PolyNode ｛
int coef;
int exp;
struct PolyNode *next；
} PolyNode， ＊PolyLink; // 多项式元素(项）结点类型

typedef PolyLink LinkedPoly； // 链式多项式

void Difference（LinkedPoly ＆pa)
/＊ 稀疏多项式 pa 以循环链表作存储结构， */
/* 将此链表修改成它的导函数，并释放无用结点 ＊/
{
LinkedPoly p，t；
t = pa—〉next;
if（ t->exp == 0 ）｛
free（t)；
pa—〉next = pa—>next-〉next；
}
p = pa-〉next;
while（ p ！= pa ）{
p—>coef *= p—>exp；
p—〉exp-—;
//if( p—>next—>exp == 0 ） p-〉next = p—>next—>next；
p = p-〉next；
｝
｝
◆3。17③ 试写一个算法，识别依次读入的一个以＠
为结束符的字符序列是否为形如'序列1＆序列2'模式
的字符序列。其中序列1和序列2中都不含字符’＆'，
且序列2是序列1的逆序列。例如，’a+b&b+a’是属该
模式的字符序列，而'1+3＆3—1’则不是。

实现下列函数:
Status match(char ＊str）;
/* 若str是属该模式的字符序列，*/
/＊ 则返回TRUE，否则返回FALSE ＊/

Stack是一个已实现的栈.
可使用的相关类型和函数:
typedef char SElemType； // 栈Stack的元素类型
Status InitStack(Stack ＆s）；
Status Push(Stack &s， SElemType e）;
Status Pop（Stack &s, SElemType &e)；
Status StackEmpty（Stack s);
Status GetTop(Stack s， SElemType &e）;

Status match（char ＊str）
/＊ 若str是属该模式的字符序列，*/
/* 则返回TRUE,否则返回FALSE ＊/
{
Stack s;
SElemType e;
InitStack(s）；
while（＊str!='＆'）
｛
Push(s，＊str）；
str++;
｝
str++;
while（＊str!=’@’）
｛
if（StackEmpty（s))
return FALSE；
Pop（s,e);
if（＊str！=e)
return FALSE；
str++；
｝
if(！StackEmpty(s)）
return FALSE；
else return TRUE;
｝

3。18② 试写一个判别表达式中开、闭括号是否配对出现的算法。

实现下列函数：
Status MatchCheck(SqList exp);
/* 顺序表exp表示表达式; */
/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */
/＊ 注：本函数不使用栈 */

顺序表类型定义如下：
typedef struct ｛
ElemType *elem;
int length；
int listsize；
｝ SqList； // 顺序表

Status MatchCheck（SqList exp)
/＊ 顺序表exp表示表达式； ＊/
/* 若exp中的括号配对，则返回TRUE，否则返回FALSE ＊/
/＊ 注：本函数不使用栈 ＊/
{
int i,j=0；
for（i=0;i〈exp.length;i++）
｛
if(exp。elem[i]==’('）
j++;
else if(exp。elem[i］==’)'&&j==0）
return FALSE;
else
j-—；
}
if(j==0) return TRUE；
else return FALSE；
｝

◆3.19④ 假设一个算术表达式中可以包含三种括号：圆括号”(" 和
")",方括号"["和”]”和花括号”｛"和”｝"，且这三种括号可按任意的
次序嵌套使用（如:…［…｛…｝…[…］…］…[…]…(…)…）。编写判别给定表达
式中所含括号是否正确配对出现的算法（已知表达式已存入数据元素
为字符的顺序表中)。

实现下列函数：
Status MatchCheck(SqList exp);
/＊ 顺序表exp表示表达式； ＊/
/* 若exp中的括号配对,则返回TRUE,否则返回FALSE */

顺序表类型定义如下：
typedef struct {
ElemType ＊elem;
int length；
int listsize；
} SqList； // 顺序表

Stack是一个已实现的栈。
可使用的相关类型和函数：
typedef char SElemType； // 栈Stack的元素类型
Status InitStack（Stack &s)；
Status Push(Stack &s, SElemType e);
Status Pop(Stack ＆s, SElemType &e);
Status StackEmpty(Stack s);
Status GetTop(Stack s, SElemType &e)；

Status MatchCheck(SqList exp)
/* 顺序表exp表示表达式； */
/* 若exp中的括号配对，则返回TRUE,否则返回FALSE */
｛
Stack s;
int i；
SElemType e;
InitStack（s）;
for(i=0;i<exp.length；i++）
{
if(exp。elem[i]==’｛’|｜exp.elem［i］==’[’｜|exp.elem[i]==’(’）
Push(s，exp。elem［i］）；
else if（exp。elem[i］==’｝'｜｜exp。elem［i]=='］'｜|exp.elem［i］==')'）
｛
if(StackEmpty(s))
return FALSE；
else
{
Pop（s，e）；
if（e==’{'&&exp.elem[i]!=’}'） return FALSE；