📄 xtjd2.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>New Page 1</title>
</head>
<body>
<p align="left"><b><span style="font-size:24.0pt;font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";color:blue;mso-font-kerning:1.0pt;
mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">数据结构辅导站</span><span style="mso-spacerun: yes; font-size: 24.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; color: blue; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US">
</span></b><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:12.0pt;font-family:宋体;
mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:
EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"><a href="index.htm">返回主页</a></span></p>
<hr>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font face="宋体" size="3">2.11
设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。</font></span></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#0000FF" face="宋体" size="2">Status
OrderListInsert-sq(SqList va, ElemType x) {</font></span></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#0000FF" face="宋体" size="2">
//将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1)</font></span></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#0000FF" face="宋体" size="2">
if (va.length==va.listsize){</font></span></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#0000FF" face="宋体" size="2">
newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType));</font></span></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
if (!newbase) exit(OVERFLOW);</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
va.elem=newbase;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
va.listsize+=LISTINCREMENT;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
}//当前存储空间已满，增加分配空间</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
if (!va.length) {va.elem[0]=x; ++va.length; return OK;}</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
q=&(va.elem[0]);</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
while (*q<=x)&&(q<=&(va.elem[va.length-1])) ++q; //查找插入位置</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
for (p=&(va.elem[va.length-1]); p>=q; --p) *(p+1)=*p;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
*q=x;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
++va.length;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
return OK;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">}//OrderListInsert-sq</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"> </p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#0000FF" face="宋体" size="2">Status
OrderListInsert-sq(SqList va, ElemType x) {</font></span></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#0000FF" face="宋体" size="2">
//将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2)</font></span></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#0000FF" face="宋体" size="2">
if (va.length==va.listsize){</font></span></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#0000FF" face="宋体" size="2">
newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType));</font></span></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
if (!newbase) exit(OVERFLOW);</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
va.elem=newbase;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
va.listsize+=LISTINCREMENT;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
}//当前存储空间已满，增加分配空间</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
if (!va.length) {va.elem[0]=x; ++va.length; return OK;}</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
p=&(va.elem[va.length-1]);</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
while (P>=&(va.elem[0])&&*p>x) {*(p+1)=*p; --p;}</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
*(p+1)=x;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
++va.length;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
return OK;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">}//OrderListInsert-sq</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"> </p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">2.12
设A=(a<sub>1</sub>,...,a<sub>m</sub>)和B=(b<sub>1</sub>,...,b<sub>n</sub>)均为顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表。若A'=B'=空表，则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则A<B；否则A>B。试写一个比较A，B大小的算法。</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">int
Compare-List(SqList a, SqList b){</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
//a,b为顺序表，若a<b时，返回-1；a=b时，返回0；a>b时，返回1</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
i=0;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
while (i<=a.length-1) && (i<=b.length-1) && (a.elem[i]=b.elem[i])
++i;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
switch {</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
case i=a.length && i=b.length : return 0; break;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
case (i=a.length && i<=b.length-1)</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
||(i<=a.length-1 && i<=b.length-1 && a.elem[i]<b.elem[i])
: return -1;break;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
default : return 1;</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
}</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font color="#0000FF" face="宋体" size="2"><span style="mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">}//Compare-List</span></font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"> </p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font size="2" color="#0000FF">2.19<br>
status del-l(LinkList &la, int mink, int maxk){<br>
//la为带头结点的单链表的头指针，单链表中的结点以值递增有序排列</font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"><font size="2" color="#0000FF">
//本算法删除表中所有值大于mink且小于maxk的元素，mink<maxk<br>
if (mink>=maxk) return ERROR<br>
p=la;<br>
while (p->next<>NULL && p->next->data<=mink) p=p->next;<br>
q=p;<br>
while (q->next<>NULL && q->next->data<maxk) q=q->next ;<br>
q=q->next;<br>
p1=p->next;<br>
while (p1<>q) {q1=p1; p1=p1->next; free(q1);}<br>
p->next=q;<br>
}//del-l<br>
<br>
2.21 <br>
LinkList priou(LinkList la, LinkList q1){<br>
//返回指向单链表la中结点的指针p1，p1->next=q1<br>
p1=la;<br>
while (p1->next!=q1) p1=p1->next;<br>
return p1;<br>
}//priou<br>
<br>
void Reverse-List-l(LinkList &la) {<br>
//就地逆置单链表la（算法1）<br>
if (!la->next) return;<br>
p=la->next; q=priou(la, NULL);<br>
while (p!=q) {<br>
p->data〈-〉q->data;<br>
if (p=q) return;<br>
q=priou(la, q);<br>
}<br>
}//Reverse-List-l<br>
<br>
void Reverse-List-l(LinkList &la) {<br>
//就地逆置单链表la（算法2）<br>
p=priou(la, NULL); last=p;<br>
pre=priou(la,p);<br>
while (pre!=la) {<br>
p->next=pre;<br>
p=pre;<br>
pre=priou(la,p);<br>
}<br>
p->next=NULL;<br>
la->next=last;<br>
}//Reverse-List-l<br>
<br>
void Reverse-List-l(LinkList &la) {<br>
//就地逆置单链表la（算法3）<br>
if (!la->next) return;<br>
pre=la->next;<br>
if (!pre->next) return;<br>
p=pre->next; pre->next=NULL;<br>
next=p->next;<br>
while (p) {<br>
p->next=pre;<br>
pre=p;<br>
p=next;<br>
if (p) next=p->next;<br>
}<br>
la->next=pre;<br>
return;<br>
}//Reverse-List-l<br>
<br>
void Reverse-List-l(LinkList &la) {<br>
//就地逆置单链表la（算法4）<br>
p=la->next;<br>
if (!p || !p->next) return;<br>
pn=p->next; p->next=NULL;<br>
while (pn) {<br>
p=pn; pn=pn->next;<br>
p->next=la->next; la->next=p;<br>
}<br>
return;<br>
}//Reverse-List-l<br>
<br>
2.24<br>
void MergeList(LinkList &a, LinkList &b, LinkList &c) {<br>
//已知单链表a和b的元素按值递增有序排列<br>
//归并a和b得到新的单链表c，c的元素按值递减有序<br>
c=a; p=a->next; q=b->next; c->next=NULL;<br>
while (p && q) <br>
if (p->data<q->data) {<br>
pn=p->next; p->next=c->next; <br>
c->next=p; p=pn; <br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -