算法
1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
LinkedList Union(LinkedList la,lb)
∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。
{ pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针
la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空。
while(pa!=null && pb!=null) ∥当两链表均不为空时作
if(pa->data<=pb->data)
{ r=pa->next; ∥将pa 的后继结点暂存于r。
pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。
la->next=pa;
pa=r; ∥恢复pa为当前待比较结点。
}
else
{r=pb->next;∥将pb 的后继结点暂存于r。
pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。
la->next=pb;
pb=r; ∥恢复pb为当前待比较结点。
}
while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。
{r=pa->next; pa->next=la->next; la->next=pa; pa=r; }
while(pb!=null)
{r=pb->next; pb->next=la->next; la->next=pb; pb=r; }
}∥算法Union结束。
类似本题的另外叙述有：
（1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】
PROCEDURE merge(ha,hb);
LinkedList Union(LinkedList ha, hb)
∥ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在ha 中的数据合并到ha中，合并中不能破坏hb链表。
｛LinkedList la;
la=(LinkedList)malloc(sizeof(LNode));
la->next=ha;∥申请头结点，以便操作。
pa=ha; ∥pa是ha链表的工作指针
pb=hb; ∥pb是hb链表的工作指针
pre=la; ∥pre指向当前待合并结点的前驱。
while(pa&&pb)
if(pa->data
{pre->next=pa;pre=pa;pa=pa->next;}
else if(pa->data>pb->data)∥处理hb中数据。
{r=(LinkedList)malloc(sizeof(LNode));∥申请空间
r->data=pb->data; pre->next=r;
pre=r;∥将新结点链入结果链表。
pb=pb->next;∥hb链表中工作指针后移。
}
else∥处理pa->data=pb->data;
{pre->next=pa; pre=pa;
pa=pa->next;∥两结点数据相等时，只将ha的数据链入。
pb=pb->next;∥不要hb的相等数据
}
if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表。
else pre->next=pb;
free(la);∥释放头结点.ha,hb指针未被破坏。
}∥算法nion结束。
（2）已知头指针分别为la和lb 的带头结点的单链表中，结点按元素值非递减有序排列。写出将la 和 lb两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc），并计算算法的时间复杂度。【燕山大学 1998 五（20分）】
pa=la->next;pb=hb->next;
lc=(LinkedList )malloc(sizeof(LNode));
pc=lc;∥pc是结果链表中当前结点的前驱
while(pa&&pb)
if(pa->data
{pc->next=pa;pc=pa;pa=pa->next;}
else {pc->next=pb;pc=pb;pb=pb->next;}
if(pa)pc->next=pa; else pc->next=pb;
free(la);free(lb);∥释放原来两链表的头结点。
算法时间复杂度为O（m+n），其中m和n分别为链表la和lb的长度。
2. 图（编者略）中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。【北京邮电大学 1992 二（15分）】
LinkedList Union(LinkedList ha,hb)
∥线性表A和B代表两个集合，以链式存储结构存储，元素递增有序。ha和hb分
别是其链表的头指针。本算法求A和B的并集A∪B，仍用线性表表示，结果链表
元素也是递增有序。
{ pa=ha->next;pb=hb->next;∥设工作指针pa和pb。
pc=ha;∥pc为结果链表当前结点的前驱指针。
while(pa&&pb)
if(pa->data
{pc->next=pa;pc=pa;pa=pa->next;}
else if(pa->data>pb->data)
{pc->next=pb;pc=pb;pb=pb->next;}
else∥处理pa->data=pb->data.
{pc->next=pa;pc=pa;pa=pa->next;
u=pb;pb=pb->next;free(u);}
if(pa) pc->next=pa;∥若ha表未空，则链入结果表。
else pc->next=pb;∥若hb表未空，则链入结果表。
free(hb); ∥释放hb头结点
return(ha);
}∥算法Union结束。
(1)已知递增有序的两个单链表A，B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=A∪B【合肥工业大学 1999 五、1（8分）】
LinkedList Union(LinkedList ha,hb)
∥线性表A和B代表两个集合，以链式存储结构存储，元素递增有序。ha和hb分
别是其链表的头指针。本算法求A和B的并集A∪B，仍用线性表表示，结果链表
元素也是递增有序。
{ pa=ha->next;pb=hb->next;∥设工作指针pa和pb。
pc=ha;∥pc为结果链表当前结点的前驱指针。
while(pa&&pb)
if(pa->data
{pc->next=pa;pc=pa;pa=pa->next;}
else if(pa->data>pb->data)
{pc->next=pb;pc=pb;pb=pb->next;}
else∥处理pa->data=pb->data.
{pc->next=pa;pc=pa;pa=pa->next;
u=pb;pb=pb->next;free(u);}
if(pa) pc->next=pa;∥若ha表未空，则链入结果表。
else pc->next=pb;∥若hb表未空，则链入结果表。
free(hb); ∥释放hb头结点
return(ha);
}∥算法Union结束。
（2）已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航天大学 2001 六（10分）】
pa=la->next;pb=lb->next;∥设工作指针pa和pb；
pc=la;∥结果表中当前合并结点的前驱的指针。
while(pa&&pb)
if(pa->data==pb->data)∥交集并入结果表中。
{ pc->next=pa;pc=pa;pa=pa->next;
u=pb;pb=pb->next;free(u);}
else if(pa->data
else {u=pb; pb=pb->next; free(u);}
while(pa){ u=pa; pa=pa->next; free(u);}∥释放结点空间
while(pb) {u=pb; pb=pb->next; free(u);}∥释放结点空间
pc->next=null;∥置链表尾标记。
free(lb); ∥注：本算法中也可对B表不作释放空间的处理
（3）设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法（即L1∩L2）。要求结果链表仍是从小到大排序，但无重复元素。【南京航空航天大学1996 十一（10分）】
pa=L1->next;pb=L2->next;∥pa、pb是两链表的工作指针。
pc=L1;∥L1作结果链表的头指针。
while(pa&&pb)
if(pa->data
else if (pa->data>pb->data) pb=pb->next; ∥pb指针后移
else∥处理交集元素
{if(pc==L1) {pc->next=pa;pc=pa;pa=pa->next;} ∥处理第一个相等的元素。
else if(pc->data==pa->data){ u=pa;pa=pa->next;free(u);} ∥重复元素不进入L1表。
else{ pc->next=pa;pc=pa;pa=pa->next;} ∥交集元素并入结果表。
} ∥while
while(pa) {u=pa;pa=pa->next;free(u);} ∥删L1表剩余元素
pc->next=null; ∥置结果链表尾。
注：本算法中对L2表未作释放空间的处理。
（4）己知两个线性表A ，B均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A与B的交集C，要求C另开辟存储空间，要求C同样以元素值的递增序的单链表形式存贮。
pa=L1->next;pb=L2->next;∥pa、pb是两链表的工作指针。
pc=L1;∥L1作结果链表的头指针。
while(pa&&pb)
if(pa->data
else if (pa->data>pb->data) pb=pb->next; ∥pb指针后移
else∥处理交集元素
{if(pc==L1) {pc->next=pa;pc=pa;pa=pa->next;} ∥处理第一个相等的元素。
else if(pc->data==pa->data){ u=pa;pa=pa->next;free(u);} ∥重复元素不进入L1表。
else{ pc->next=pa;pc=pa;pa=pa->next;} ∥交集元素并入结果表。
} ∥while
while(pa) {u=pa;pa=pa->next;free(u);} ∥删L1表剩余元素
pc->next=null; ∥置结果链表尾。
注：本算法中对L2表未作释放空间的处理。
（5）已知递增有序的单链表A,B和C分别存储了一个集合，设计算法实现A：=A∪（B∩C），并使求解结构A仍保持递增。要求算法的时间复杂度为O(|A|+|B|+|C|)。其中,|A|为集合A的元素个数。
LinkedList union(LinkedList A,B,C)
∥A,B和C均是带头结点的递增有序的单链表，本算法实现A= A∪（B∩C），使求解
结构保持递增有序。
{pa=A->next;pb=B->next;pc=C->next;∥设置三个工作指针。
pre=A; ∥pre指向结果链表中当前待合并结点的前驱。
if(pa->data
{pre->next=pa;pre=pa;pa=pa->next;}
else{while(pb&&pc) ∥找B表和C表中第一个公共元素。
if(pb->data
else if(pb->data>pc->data)pc=pc->next;
else break; ∥找到B表和C表的共同元素就退出while循环。
if(pb&&pc)∥因共同元素而非B表或C表空而退出上面while循环。
if(pa->data>pb->data)∥A表当前元素值大于B表和C表的公共元素，先将
B表元素链入。
{pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}∥ B，C公共元素为结
果表第一元素。
}∥结束了结果表中第一元素的确定
while(pa&&pb&&pc)
{while(pb&&pc)
if(pb->data
else if(pb->data>pc->data) pc=pc->next;
else break; ∥B表和C表有公共元素。
if(pb&&pc)
{while(pa&&pa->data
{pre->next=pa;pre=pa;pa=pa->next;}
if(pre->data!=pb->data){pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}
else{pb=pb->next;pc=pc->next;}∥若A中已有B，C公共元素，则不再存入结果表。
}
}∥while(pa&&pb&&pc)
if(pa) pre->next=pa; ∥当B，C无公共元素（即一个表已空），将A中剩余链入。
}∥算法Union结束
3. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。【东北大学1996 二 (12分)】
LinkedList Union(LinkedList L1,L2;int m,n)
∥L1和L2分别是两循环单链表的头结点的指针，m和n分别是L1和L2的长度。
∥本算法用最快速度将L1和L2合并成一个循环单链表。
{if(m<0||n<0) {printf(“表长输入错误\n”)；exit(0);}
if(m {if(m==0)return(L2);∥L1为空表。 else{p=L1; while(p->next!=L1) p=p->next;∥查最后一个元素结点。 p->next=L2->next;∥将L1循环单链表的元素结点插入到L2的第一元素结点前。 L2->next=L1->next; free(L1);∥释放无用头结点。 } }∥处理完m else∥下面处理L2长度小于等于L1的情况 {if(n==0)return(L1);∥L2为空表。 else{p=L2; while(p->next!=L2) p=p->next;∥查最后元素结点。 p->next=L1->next;∥将L2的元素结点插入到L1循环单链表的第一元素结点前。 L1->next=L2->next; free(L2);∥释放无用头结点。 } }∥算法结束。 （1）试用类Pascal语言编写过程PROC join（VAR la：link； lb：link）实现连接线性表la和lb(lb在后)的算法，要求其时间复杂度为0（1），占用辅助空间尽量小。描述所用结构。 LinkedList Union(LinkedList la,lb) ∥la和lb是两个无头结点的循环单链表的尾指针，本算法将lb接在la后，成为 一个单循环链表。 { q=la->next; ∥q指向la的第一个元素结点。 la->next=lb->next; ∥将lb的最后元素结点接到lb的第一元素。 lb->next=q; ∥将lb指向la的第一元素结点，实现了lb接在la后。 return(lb); ∥返回结果单循环链表的尾指针lb。 }∥算法结束。 [算法讨论]若循环单链表带有头结点，则相应算法片段如下： q=lb->next; ∥q指向lb的头结点； lb->next=la->next; ∥lb的后继结点为la的头结点。 la->next=q->next; ∥la的后继结点为lb的第一元素结点。 free(q); ∥释放lb的头结点 return(lb); ∥返回结果单循环链表的尾指针lb。 （2）设有两个链表，ha为单向链表，hb为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与链表长度无关。【南京航空航天大学 1997 四（8分）】 其核心算法片段如下（设两链表均有头结点） q=hb->next; ∥单向循环链表的表头指针 hb->next=ha->next; ∥将循环单链表最后元素结点接在ha第一元素前。 ha->next=q->next; ∥将指向原单链表第一元素的指针指向循环单链表第一结点 free(q); ∥释放循环链表头结点。 若两链表均不带头结点，则算法片段如下： q=hb->next; ∥q指向hb首元结点。 hb->next=ha; ∥hb尾结点的后继是ha第一元素结点。 ha=q; ∥头指针指向hb的首元结点。 4. 顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类PASCAL语言给出一种高效算法，将LB中元素合到LA中，使新的LA 的元素仍保持非递减有序。高效指最大限度的避免移动元素。 PROC Union(VAR LA:SeqList;LB:SeqList) ∥LA和LB是顺序存储的非递减有序线性表，本算法将LB合并到LA中，元素仍非递减有序。 m:=https://www.wendangku.net/doc/d317921897.html,st;n:=https://www.wendangku.net/doc/d317921897.html,st;∥m，n分别为线性表LA和LB的长度。 k:=m+n; ∥k为结果线性表的工作指针（下标）。 i:=m;j:=n; ∥i，j分别为线性表LA和LB的工作指针（下标）。 WHILE(i>0)AND(j>0)DO IF LA.elem[i]>=LB.elem[j] THEN[LA.elem[k]:=LA.elem[i];k:=k-1;i:=i-1;] ELSE[LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;] WHILE(j>0) DO [LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;] https://www.wendangku.net/doc/d317921897.html,st:=m+n; ENDP; 5.已知不带头结点的线性链表list，链表中结点构造为（data、link），其中data为数据域，link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。【北京航空航天大学 1998 五（15分）】 LinkedList LinkListSort(LinkedList list) ∥list是不带头结点的线性链表，链表结点构造为data和link两个域，data是数据域，link是指针域。本算法将该链表按结点数据域的值的大小，从小到大重新链接。 {p=list->link; ∥p是工作指针，指向待排序的当前元素。 list->link=null;∥假定第一个元素有序，即链表中现只有一个结点。 while(p!=null) {r=p->link; ∥r是p的后继。 q=list; if(q->data>p->data)∥处理待排序结点p比第一个元素结点小的情况。 {p->link=list; list=p;∥链表指针指向最小元素。 } else∥查找元素值最小的结点。 {while(q->link!=null&&q->link->data p->link=q->link;∥将当前排序结点链入有序链表中。 q->link=p; } p=r;∥p指向下个待排序结点。 } } p=list->link;∥p指向第一元素结点。 list->link=null;∥有序链表初始化为空 while(p!=null) {r=p->link;∥保存后继 q=list; while(q->link!=null && q->link->data p->link=q->link; q->link=p; q=r; } 6. 设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。【东北大学 1996 六 (14分)】 LinkedList LinkListInsertSort(LinkedList la) ∥la是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成 递增的有序链表。 {if(la->next!=null)∥链表不为空表。 {p=la->next->next;∥p指向第一结点的后继。 la->next->next=null;∥直接插入原则认为第一元素有序，然后从第二元素起依次插入。 while(p!=null) {r=p->next;∥暂存p的后继。 q=la; while(q->next!=null&&q->next->data p->next=q->next;∥将p结点链入链表。 q->next=p; p=r; } （1）设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将此链表的记录按照key递增的次序进行就地排序.【中科院计算所 1999 五、1（10分）】 LinkedList LinkListInsertSort(LinkedList la) ∥la是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成 递增的有序链表。 {if(la->next!=null)∥链表不为空表。 {p=la->next->next;∥p指向第一结点的后继。 la->next->next=null;∥直接插入原则认为第一元素有序，然后从第二元素起依次插入。 while(p!=null) {r=p->next;∥暂存p的后继。 q=la; while(q->next!=null&&q->next->data p->next=q->next;∥将p结点链入链表。 q->next=p; p=r; } 7. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一PASCAL过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。【山东大学1993六( 15分)】 PROC discreat(VAR listhead,P,Q:linkedlist) ∥listhead是单链表的头指针，链表中每个结点由一个整数域DATA和指针域NEXT组成。本算法将链表listhead分解成奇数链表和偶数链表，分解由P和Q指向，且P和Q链表是有序的。 P:=NIL;Q:=NIL;∥P和Q链表初始化为空表。 s:=listhead; WHILE(s<>NIL)DO [r:=s^.NEXT; ∥暂存s的后继。 IF s^.DATA DIV 2=0 ∥处理偶数。 THEN IF P=NIL THEN[P:=s;P^.NEXT:=NIL;] ∥第一个偶数链结点。 ELSE[pre:=P; IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre;P:=s;∥插入当前最小值结点修改头指针] ELSE[WHILE pre^.NEXT<>NIL DO IF pre^.NEXT^.DATA s^.NEXT:=pre^.NEXT; ∥链入此结点。 pre^.NEXT:=s; ] ] ELSE∥处理奇数链。 IF Q=NIL THEN[Q:=s;Q^.NEXT:=NIL;] ∥第一奇数链结点。 ELSE[pre:=Q; IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre; Q:=s; ]∥修改头指针。 ELSE[WHILE pre^.NEXT<>NIL DO∥查找插入位置。 IF pre^.NEXT^.DATA s^.NEXT:=pre^.NEXT;∥链入此结点。 pre^.NEXT:=s; ] ]∥结束奇数链结点 s:=r;∥s指向新的待排序结点。 ]∥结束“WHILE(s<>NIL)DO” ENDP；∥结束整个算法。 （1）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B 表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。【北京理工大学 2000 四、2（4分）】 void DisCreat1(LinkedList A) ∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点的数据大于零。 {B=A; C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间。 C->next=null ∥C初始化为空表。 p=A->next; ∥p为工作指针。 B->next=null; ∥B表初始化。 while(p!=null) {r=p->next; ∥暂存p的后继。 if (p->data<0)∥小于0的放入B表。 {p->next=B->next; B->next=p; }∥将小于0的结点链入B表。 else {p->next=C->next; C->next=p; } p=r;∥p指向新的待处理结点。 } }∥算法结束。 (2)设L为一单链表的头指针，单链表的每个结点由一个整数域 data和指针域NEXT组 成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，分别由P，Q指向，每个链中的数据按由小到大排列，算法中不得申请新的结点空间。【青岛海洋大学 1999 三（12分）】 PROC discreat(VAR listhead,P,Q:linkedlist) ∥listhead是单链表的头指针，链表中每个结点由一个整数域DATA和指针域NEXT组成。本算法将链表listhead分解成奇数链表和偶数链表，分解由P和Q指向，且P和Q链表是有序的。 P:=NIL;Q:=NIL;∥P和Q链表初始化为空表。 s:=listhead; WHILE(s<>NIL)DO [r:=s^.NEXT; ∥暂存s的后继。 IF s^.DATA DIV 2=0 ∥处理偶数。 THEN IF P=NIL THEN[P:=s;P^.NEXT:=NIL;] ∥第一个偶数链结点。 ELSE[pre:=P; IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre;P:=s;∥插入当前最小值结点修改头指针] ELSE[WHILE pre^.NEXT<>NIL DO IF pre^.NEXT^.DATA s^.NEXT:=pre^.NEXT; ∥链入此结点。 pre^.NEXT:=s; ] ] ELSE∥处理奇数链。 IF Q=NIL THEN[Q:=s;Q^.NEXT:=NIL;] ∥第一奇数链结点。 ELSE[pre:=Q; IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre; Q:=s; ]∥修改头指针。 ELSE[WHILE pre^.NEXT<>NIL DO∥查找插入位置。 IF pre^.NEXT^.DATA s^.NEXT:=pre^.NEXT;∥链入此结点。 pre^.NEXT:=s; ] ]∥结束奇数链结点 s:=r;∥s指向新的待排序结点。 ]∥结束“WHILE(s<>NIL)DO” ENDP；∥结束整个算法。 (3) 将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原 表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。 1) 写出其类型定义： 2) 写出算法。【山东大学 1998 九 (9分)】【山东工业大学 2000 九（9分）】 void DisCreat3(LinkedList A) ∥A是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A表中含原表中序号为奇数 ∥的结点，B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。 {i=0;∥i记链表中结点的序号。 B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头。 B->next=null; ∥B表的初始化。 LinkedList ra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。 ra=A;rb=B; p=A->next; ∥p为链表工作指针，指向待分解的结点。 A->next=null; ∥置空新的A表 while(p!=null) {r=p->next; ∥暂存p的后继。 i++; if(i%2==0) ∥处理原序号为偶数的链表结点。 {p->next=rb->next;∥在B表尾插入新结点； rb->next=p; rb=p;∥rb指向新的尾结点； } else∥处理原序号为奇数的结点。 {p->next=ra->next; ra->next=p; ra=p; } p=r; ∥将p恢复为指向新的待处理结点。 }∥算法结束 8. 已知线性表（a1 a2 a3 …an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x …x）变为（-x,-x,-x…x,x,x）。 int Rearrange（SeqList a; int n) ∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重排线性表a， ∥使所有值为负数的元素移到所有值为正数的数的前面。 {i=0; j=n-1; ∥ i,j为工作指针（下标），初始指向线性表a的第1个和第n个 元素。 t=a[0]; ∥暂存枢轴元素。 while(i {while(i if(i while(i if(i } a[i]=t; ∥将原第一元素放到最终位置。 } 类似本题的另外叙述有： （1）设有一元素为整数的线性表L=(a1,a2,a3,…,a n),存放在一维数组A[N]中,设计一个算法,以表中a n作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于a n,右半部分每个元素都大于a n, a n位于分界位置上(要求结果仍存放在A[N]中)。【北京理工大学 1999 八（6分）】 i=1;j=n; t=a[n]; ∥暂存参考元素。 while(i {while(i if(i while(i if(i } a[i]=t; ∥参考元素置于分界位置。 （2）顺序存储的线性表A,其数据元素为整型,试编写一算法,将A拆成B和C两个表,使A 中元素值大于等于0的元素放入B,小于0的放入C中.. 要求: 1）表B和C另外设置存储空间; 2）表B和C不另外设置,而利用A的空间.【山东大学 2001 九、1 (12分)】 void Rearrange2(int A[],B[],C[]) ∥线性表A有n个整型元素，顺序存储。本算法将A拆成B和C 两个表，B中存 放大于 ∥等于零的元素，C中存放小于零的元素。 {i=0; ∥i，j，k是工作指针，分别指向A、B和C表的当前元素。 j=k=-1; ∥j，k初始化为-1。 while(i {if(A[i]<0) C[++k]=A[i++]; ∥将小于零的元素放入C表。 else B[++j]=A[i++]; ∥将大于零的元素放入B表。 （3）知线性表（a1, a2,a3,…,an）按顺序存储，且每个元素都是整数均不相同，设计把所有奇数移到所有偶数前边的算法。（要求时间最少，辅助空间最少）【东北大学 1997 三 (15分)】 int Rearrange（SeqList a; int n) ∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重排线性表a， ∥使所有值为奇数的元素移到所有值为偶数的数的前面。 {i=0; j=n-1; ∥ i,j为工作指针（下标），初始指向线性表a的第1个和第n个元素。 t=a[0]; ∥暂存枢轴元素。 while(i {while(a[i]%2==0) j--; ∥若当前元素为偶数，则指针前移。 if(i while(a[i]%2==0)i++; ∥当前元素为奇数时指针后移。 if(i } a[i]=t; ∥将原第一元素放到最终位置。 } (4) 编写函数将一整数序列中所有负数移到所有正数之前，要求时间复杂度为O（n）int Rearrange（SeqList a; int n) ∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重排线性表a， ∥使所有值为负数的元素移到所有值为正数的数的前面。 {i=0; j=n-1; ∥ i,j为工作指针（下标），初始指向线性表a的第1个和第n个元素。 t=a[0]; ∥暂存枢轴元素。 while(i {while(i if(i while(i if(i } a[i]=t; ∥将原第一元素放到最终位置。 } (5) 已知一个由n（设n=1000）个整数组成的线性表，试设计该线性表的一种存储结构，并用标准pascal语言描述算法，实现将n个元素中所有大于等于19的整数放在所有小于 19的整数之后。要求算法的时间复杂度为O(n),空间复杂度O(1)。【西安交通大学1996 六（11分）】 TYPE arr=ARRAY[1..1000] OF integer； VAR a：arr； PROCEDURE Rearrange5（VAR a：arr）； ∥a是n（设n=1000）个整数组成的线性表，用一维数组存储。本算法将n个元 素中所有大于等于19的整数放在所有小于19的整数之后。 VAR i,j,t：integer； BEGIN i:=1；j:=n；t:=a[1] ；∥i,j指示顺序表的首尾元素的下标，t暂存分界元素 WHILE（i BEGIN WHILE（i IF（i WHILE（i IF（i END； a[i]:=t； END; 9. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void delete （Linklist &L） LinkedList Delete（LinkedList L） ∥L是带头结点的单链表，本算法删除其最小值结点。 {p=L->next；∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L；∥pre指向最小值结点的前驱。 q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null） {if（p->next->data p=p->next；∥指针后移。 } pre->next=q->next；∥从链表上删除最小值结点 free（q）；∥释放最小值结点空间 }∥结束算法delete。 10.已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。【北京航空航天大学 2001 四（10分）】 LinkedList delinsert（LinkedList list） ∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域。 ∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->link；∥p是链表的工作指针 pre=list；∥pre指向链表中数据域最小值结点的前驱。 q=p；∥q指向数据域最小值结点，初始假定是第一结点 while（p->link!=null） {if（p->link->data p=p->link； } if (q!=list->link) ∥若最小值是第一元素结点，则不需再操作 {pre->link=q->link；∥将最小值结点从链表上摘下； q->link= list->link；∥将q结点插到链表最前面。 list->link=q； } }∥算法结束 11.已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。【首都经贸大学 1997 二、2（15分）】 void Exchange（LinkedList p） ∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。 {q=p->llink； q->llink->rlink=p；∥p的前驱的前驱之后继为p p->llink=q->llink；∥p的前驱指向其前驱的前驱。 q->rlink=p->rlink；∥p的前驱的后继为p的后继。 q->llink=p；∥p与其前驱交换 p->rlink->llink=q；∥p的后继的前驱指向原p的前驱 p->rlink=q；∥p的后继指向其原来的前驱 }∥算法exchange结束。 12. 线性表(a1,a2,a3,…,a n)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成： （1）用最少时间在表中查找数值为x的元素。 （2）若找到将其与后继元素位置相交换。 （3）若找不到将其插入表中并使表中元素仍递增有序。【东北大学 1996 三 ( 12分)】 void SearchExchangeInsert（ElemType a[]；ElemType x） ∥a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序。 { low=0；high=n-1；∥low和high指向线性表下界和上界的下标 while（low<=high） {mid=（low+high）/2；∥找中间位置 if（a[mid]==x）break；∥找到x，退出while循环。 else if （a[mid] else high=mid-1；∥到中点mid的左部去查。 } if（a[mid]==x && mid!=n）∥若最后一个元素与x相等，则不存在与其后继交换的 操作。 {t=a[mid]；a[mid]=a[mid+1]；a[mid+1]=t；} ∥数值x与其后继元素位置交 换。 if（low>high）∥查找失败，插入数据元素x {for（i=n-1；i>high；i--） a[i+1]=a[i]；∥后移元素。 a[i+1]=x；∥插入x。 } ∥结束插入 }∥结束本算法。 13.设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称。例如 xyx, xyyx都是中心对称。【首都经贸大学1998三、9（15分）】 int dc（LinkedList h，int n） ∥ h是带头结点的n个元素单链表，链表中结点的数据域是字符。本算法判断链表是 否是中心对称。 {char s[]; int i=1；∥i记结点个数， s字符栈 p=h->next；∥p是链表的工作指针，指向待处理的当前元素。 for（i=1；i<=n/2；i++）∥链表前一半元素进栈。 {s[i]=p->data；p=p->next；} i--; ∥恢复最后的i值 if（n%2==1）p=p->next；} ∥若n是奇数，后移过中心结点。 while（p!=null && s[i]==p->data）{i--；p=p->next；} ∥测试是否中心对称。 if（p==null）return（1）；∥链表中心对称 else return（0）；∥链表不中心对称 }∥算法结束。 14. 已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。 【中国矿业大学 2000 三（10分）】 LinkedList DelInsert（LinkedList heada，headb，int i，j，len） ∥heada和headb均是带头结点的单链表。本算法删除heada链表中自第i个元素起的共len个元素，然后将单链表heada插入到headb的第j个元素之前。 {if（i<1 || len<1 || j<1）{printf（“参数错误\n”）；exit（0）；}∥参数错，退出算法。 p=heada；∥p为链表A的工作指针，初始化为A的头指针，查到第i个元素时，p指向第i-1个元素 k=0；∥计数 while（p!=null && k {k++；p=p->next；} if（p==null）{printf（“给的%d太大\n”,i）；exit（0）；} ∥i太大，退出算法 q=p->next；∥q为工作指针，初始指向A链表第一个被删结点。 k=0； while（q!=null && k if（k p->next=q；∥A链表删除了len个元素。 if (heada->next!=null) ∥heada->next=null说明链表中结点均已删除，无需往B 表插入 {while（p->next!=null）p= p->next；∥找A的尾结点。 q=headb；∥q为链表B的工作指针。 k=0；∥计数 while（q!=null && k {k++；q= q->next；} ∥查找成功时，q指向第j-1个结点 if（q==null）{printf（“给的%d太大\n”,j）；exit（0）；} p->next=q->next；∥将A链表链入 q->next=heada->next；∥A的第一元素结点链在B的第j-1个结点之后 }//if free（heada）；∥释放A表头结点。 }∥算法结束。 类似本题的另外叙述有： （1）h1、h2为两个链表的表头指针，结点结构为data和link两个域组成。写出算法inde(h1,h2,i,j,l),将链表h1从第i个结点起的l个结点删除，并插入到h2表的第j个结点之前。 LinkedList DelInsert（LinkedList heada，headb，int i，j，len） ∥heada和headb均是带头结点的单链表。本算法删除heada链表中自第i个元素起的共len个元素，然后将单链表heada插入到headb的第j个元素之前。 {if（i<1 || len<1 || j<1）{printf（“参数错误\n”）；exit（0）；}∥参数错，退出算法。 p=heada；∥p为链表A的工作指针，初始化为A的头指针，查到第i个元素时，p指向第i-1个元素 k=0；∥计数 k=1；q=p->next； //q指向第一个被删除结点 while（q!=null && k {k++；q= q->next；} if（k k=0； while（q!=null && k if（k p->next=q；∥A链表删除了len个元素。 if (heada->next!=null) ∥heada->next=null说明链表中结点均已删除，无需往B 表插入 {while（p->next!=null）p= p->next；∥找A的尾结点。 q=headb；∥q为链表B的工作指针。 k=0；∥计数 while（q!=null && k {k++；q= q->next；} ∥查找成功时，q指向第j-1个结点 if（q==null）{printf（“给的%d太大\n”,j）；exit（0）；} p->next=q->next；∥将A链表链入 q->next=heada->next；∥A的第一元素结点链在B的第j-1个结点之后 }//if free（heada）；∥释放A表头结点。 }∥算法结束。 15. 设线性表存于A[1..size]的前num各分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。 【西安电子科技大学 1999计应用 1997 二（10分）】 void Insert（ElemType A[]，int size, ElemType x） ∥ A是有size个元素空间目前仅有num（num {low=1；high=num； //题目要求下标从1开始 while（low<=high）∥对分查找元素x的插入位置。 {mid=（low+high）/2； if（A[mid]==x）{low=mid+1；break；} else if（A[mid]>x）high=mid-1 ；else low=mid+1 ； } for（i=num；i>=low；i--） A[i+1]=A[i]；∥元素后移。 A[i+1]=x；∥将元素x插入。 }算法结束。 类似本题的另外叙述有： (1)试编制在线性表L={12,13,21,24,28,30,42,}中插入数据元素26的程序。（要求该程序用turbo Pascal语言编制并能在计算机上运行，结点类型为链式结构）【大连海事大学 1996 二、1 (16分)】 PROGRAM example（input，output）； TYPE pointer=^node； node=RECORD data：integer； next：pointer； END； VAR head，q：pointer； PROCEDURE create（VAR la：pointer）； VAR x：integer； p,q：pointer； BEGIN new（la）；la^.next:=NIL；{建立头结点。} read（x）；q:=la；{q用以指向表尾。} WHILE NOT EOF DO {建立链表} BEGIN new（p）；p^.data:=x；p^.next:=q^.next；q^.next:=p；q:=p; read(x); END； END； PROCEDURE insert（VAR la：pointer；s：pointer）； VAR p,q：pointer；found：boolean； BEGIN p:= la^.next；{p为工作指针。} q:=la；{q为p的前驱指针。} found:=false； WHILE（p<>NIL）AND NOT found IF（p^.data ELSE found:=true； s^.next:=p；{将s结点插入链表} q^.next:=s； END； BEGIN {main} writeln（“请按顺序输入数据，建立链表”） create（head）； writeln（“请输入插入数据”） new（q）； readln（q^.data）； insert（head，q）； END.{程序结束} 16. 假设一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，它的值为空指针（NIL）；link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。 【西安电子科技大学 1999软件五（10分）】 void StoDouble（LinkedList la） ∥la是结点含有pre，data，link三个域的单循环链表。其中data为数据域,pre为空指针域，link是指向后继的指针域。本算法将其改造成双向循环链表。 {while（la->link->pre==null） {la->link->pre=la；∥将结点la后继的pre指针指向la。 la=la->link；∥la指针后移。 } } ∥算法结束。 17. 已知递增有序的单链表A,B分别存储了一个集合，请设计算法以求出两个集合A和B 的差集A-B（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。 【西安电子科技大学2000计应用1997 二（10分）】 void Difference（LinkedList A，B，*n） ∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0 {p=A->next；∥p和q分别是链表A和B的工作指针。 q=B->next； pre=A；∥pre为A中p所指结点的前驱结点的指针。 while（p!=null && q!=null） if（p->data else if（p->data>q->data）q=q->next；∥B链表中当前结点指针后移。 else {pre->next=p->next；∥处理A，B中元素值相同的结点，应删除。 u=p； p=p->next； free（u）；} ∥删除结点 18. 已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断 该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false. 【西安电子科技大学2000软件1997 二（10分）】 int Judge（LinkedList la） ∥la是结点的元素为整数的单链表。本算法判断从第二结点开始，每个元素值是否等于其序号的平方减去其前驱的值，如是返回true；否则，返回false。 {p=la->next->next；∥p是工作指针，初始指向链表的第二项。 pre=la->next；∥pre是p所指结点的前驱指针。 i=2；∥i是la链表中结点的序号，初始值为2。 while（p!=null） if（p->data==i*i-pre->data）{i++；pre=p；p=p->next；} ∥结点值间的关系符合题目要求 else break；∥当前结点的值不等于其序号的平方减去前驱的值。 if（p!=null）return（false）；∥未查到表尾就结束了。 else return（true）；∥成功返回。 }∥算法结束。 [算法讨论]本题不设头结点也无影响。另外，算法中还可节省前驱指针pre，其算法片段如下： p=la；∥假设无头结点，初始p指向第一元素结点。 i=2； while（p->next!=null）∥初始p->next指向第二项。 if（p->next->data= =i*i-p->data） {i++；p=p->next；} if（p->next!=null）return（false）；∥失败 else return（true）；∥成功 19．两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。【东北大学 1999 二 (10分)】int Pattern（LinkedList A，B） ∥A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列。如是，返回1；否则，返回0表示失败。 {p=A；∥p为A链表的工作指针，本题假定A和B均无头结点。 pre=p；∥pre记住每趟比较中A链表的开始结点。 q=B；∥q是B链表的工作指针。 while（p && q） if（p->data==q->data） {p=p->next；q=q->next；} else{pre=pre->next；p=pre；∥A链表新的开始比较结点。 q=B；} ∥q从B链表第一结点开始。 if（q==null）return（1）；∥B是A的子序列。 else return（0）；∥B不是A的子序列。 }∥算法结束。 20．L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字 2.两点乘积算法： 程序： %两点乘积算法,输入正弦波，取得电气角度相隔pi/2的采样时刻的数据值，计算出正弦量的有效值。 clear; N=12; %每周期采12个点 for n=0:48; t=0.02*n/N; y=sin(2*pi*n/N); %输入正弦波量y=sin(w*t) s(1,n+1)=y; %将y采样所得的值赋值给s if n>3 a=s(1,n-3); %输出相差0.5*pi的两点采样值 b=s(1,n); Ym=sqrt(a^2+b^2); Y=Ym/1.414; %输出正弦量的有效值 subplot(211) %绘制t-Y，即正弦量有效值与时间关系的图形 plot(t,Y,'-bo'); pause(0.005); xlim([-0.01,0.08]); ylim([0,1]); hold on end subplot(212); %绘制t-y，输入与时间关系的即图形 plot(t,y,'-bo'); pause(0.005); hold on end 基于两点乘积及全波傅里叶算法的应用 利用全波傅里叶算法和两点乘积算法计算 1.全波傅里叶算法： 程序： %全波傅里叶算法 clear N=24; %每周期采24个点 for n=0:96; t=0.02*n/N; y=sin(2*pi*n/N); %输入正弦波量y=sin(w*t) x1(1,n+1)=y; %将y采样所得的值赋值给x1 if n>24 X1s=0; X1c=0; for k=(n-24):(n-1) a1=x1(1,k); a2=a1*sin(2*k*pi/N); X1s=a2+X1s; end for j=(n-24):(n-1) b1=x1(1,j); b2=b1*cos(2*j*pi/N); X1c=b2+X1c; end X1s=(2/N)*X1s; %输出正弦系数 x1(2,n+1)=X1s; X1c=(2/N)*X1c; %输出余弦系数 x1(3,n+1)=X1c; X=sqrt(0.5*(X1s^2+X1c^2)); %求出基波分量有效值 x1(4,n+1)=X; end if n<24 X=0; end subplot(212); %绘制t-X，即基波分量有效值与时间关系的图形 plot(t,X,'-bo'); xlim([0,0.1]); ylim([0,1]); pause(0.0005); hold on subplot(211); %绘制t-y，即输入与时间关系的图形 plot(t,y,'-ok'); G001、无人机是指根据无人机需要完成的任务、无人机的数量以及携带任务载荷的类型，对无人机制定飞行路线并进行任务分配。 A.航迹规划 B.任务规划 C.飞行规划 正确答案: B（解析：P174） G002、任务规划的主要目标是依据地形信息和执行任务环境条件信息，综合考虑无人机的性能，到达时间、耗能、威胁以及飞行区域等约束条件。为无人机规划出一条或多条自 的，保证无人机高效，圆满的完成飞行任务，并安全返回基地。 A.起飞到终点，最短路径 B.起飞点到着陆点，最佳路径 C.出发点到目标点，最优或次优航迹 正确答案: C（解析：P174） G003、无人机任务规划是实现的有效途径，他在很大程度上决定了无人机执行任务的效率 A.自主导航与飞行控制 B.飞行任务与载荷导航 C.航迹规划与自主导航 正确答案: A（解析：P174） G004、无人机任务规划需要实现的功能包括 A.自主导航功能，应急处理功能，航迹规划功能 B.任务分配功能，航迹规划功能，仿真演示功能 C.自主导航功能，自主起降功能，航迹规划功能 正确答案: B（解析：P174） G005、无人机任务规划需要考虑的因素有、，无人机物理限制，实时性要求 A.飞行环境限制，飞行任务要求 B.飞行赶任务范围，飞行安全限制 C.飞行安全限制，飞行任务要求 正确答案: A（解析：P175） G006、无人机物理限制对飞行航迹有以下限制：，最小航迹段较长度，最低安全飞行高度 A.最大转弯半径，最小俯仰角 B.最小转弯半径，最小俯仰角 C.最小转弯半径，最大俯仰角 正确答案: C（解析：P175） G007、动力系统工作恒定的情况下，限制了航迹在垂直平面内上升和下滑的最大角度 A.最小转弯半径 B.最大俯仰角 向量- 向量叉乘向量点乘 2010年07月28日星期三14:33 向量（Vector） 在几乎所有的几何问题中，向量（有时也称矢量）是一个基本点。向量的定义包含方向和一个数（长度）。在二维空间中，一个向量可以用一对x和y来表示。例如由点（1,3）到（5,1的向量可以用(4,-2）来表示。这里大家要特别注意，我这样说并不代表向量定义了起点和终点。向量仅仅定义方向和长度。 向量加法 向量也支持各种数学运算。最简单的就是加法。我们可以对两个向量相加，得到的仍然是一个向量。我们有： V1（x1, y1）+V2（x2, y2）=V3(x1+x2, y1+y2) 下图表示了四个向量相加。注意就像普通的加法一样,相加的次序对结果没有影响（满足交换律），减法也是一样的。 点乘（Dot Product） 如果说加法是凭直觉就可以知道的，另外还有一些运算就不是那么明显的，比如点乘和叉乘。点乘比较简单，是相应元素的乘积的和： V1( x1, y1) V2(x2, y2) = x1*x2 + y1*y2 注意结果不是一个向量，而是一个标量（Scalar）。点乘有什么用呢，我们有： A B = |A||B|Cos(θ) θ是向量A和向量B见的夹角。这里|A|我们称为向量A的模(norm)，也就是A的长度，在二维空间中就是|A| = sqrt(x2+y2)。这样我们就和容易计算两条线的夹角：Cos(θ) = A B /(|A||B|) 当然你知道要用一下反余弦函数acos()啦。（回忆一下cos(90)=0 和cos(0) = 1还是有好处的，希望你没有忘记。）这可以告诉我们如果点乘的结果，简称点积，为0的话就表示这两个向量垂直。当两向量平行时，点积有最大值 另外，点乘运算不仅限于2维空间，他可以推广到任意维空间。（译注：不少人对量子力学中的高维空间无法理解，其实如果你不要试图在视觉上想象高维空间，而仅仅把它看成三维空间在数学上的推广，那么就好理解了） 数据结构课程设计报告 实验一：计算器 设计要求 1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。 2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。 具体事例如下： 3、输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。 具体事例如下： 知识点：堆栈、队列 实际输入输出情况： 正确的表达式 对负数的处理 表达式括号不匹配 表达式出现非法字符 表达式中操作符位置错误 求余操作符左右出现非整数 其他输入错误 数据结构与算法描述 解决问题的整体思路： 将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。 解决本问题所需要的数据结构与算法： 用到的数据结构是堆栈。主要算法描述如下： A．将中缀表达式转换为后缀表达式： 1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况： 1）数字 2）小数点 3）合法操作符+ - * / % 4）左括号 5）右括号 6）非法字符 2. 首先为操作符初始化一个map 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 设计过程在硬件与软件方面进行同步设计。硬件方面从功能考虑，首先选择内部存储资源丰富的AT89C51单片机，输入采用4×4矩阵键盘。显示采用3位7段共阴极LED动态显示。软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C 语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C51芯片、汇编语言、数码管、加减乘除 目录 摘要 (01) 引言 (01) 一、设计任务和要求............................. 1、1 设计要求 1、2 性能指标 1、3 设计方案的确定 二、单片机简要原理............................. 2、1 AT89C51的介绍 2、2 单片机最小系统 2、3 七段共阳极数码管 三、硬件设计................................... 3、1 键盘电路的设计 3、2 显示电路的设计 四、软件设计................................... 4、1 系统设计 4、2 显示电路的设计 五、调试与仿真................................. 5、1 Keil C51单片机软件开发系统 5、2 proteus的操作 六、心得体会.................................... 参考文献......................................... 附录1 系统硬件电路图............................ 附录2 程序清单.................................. 微机课程设计报告 题目简易计算器仿真 学院（部）信息学院 专业通信工程 班级2011240401 学生姓名张静 学号33 12 月14 日至12 月27 日共2 周 指导教师（签字）吴向东宋蓓蓓 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C52芯片、汇编语言、数码管、加减乘除 安卓应用程序设计 ——简易计算器的实现院（系）名称 专业名称 学生姓名 学生学号 课程名称 2016年6月日 1.系统需求分析 Android是以Linux为核心的手机操作平台，作为一款开放式的操作系统，随着Android 的快速发展，如今已允许开发者使用多种编程语言来开发Android应用程序，而不再是以前只能使用Java开发Android应用程序的单一局面，因而受到众多开发者的欢迎，成为真正意义上的开放式操作系统。计算器通过算法实行简单的数学计算从而提高了数学计算的效率，实现计算器的界面优化，使界面更加友好，操作更加方便。基于android的计算器的设计,系统具有良好的界面；必要的交互信息；简约美观的效果。使用人员能快捷简单地进行操作，即可单机按钮进行操作，即时准确地获得需要的计算的结果，充分降低了数字计算的难度和节约了时间。 2.系统概要设计 2.1计算器功能概要设计 根据需求，符合用户的实际要求，系统应实现以下功能：计算器界面友好，方便使用，，具有基本的加、减、乘、除功能，能够判断用户输入运算数是否正确，支持小数运算，具有清除功能。 图2.1系统功能图 整个程序基于Android技术开发，除总体模块外主要分为输入模块、显示模块以及计算模块这三大部分。在整个系统中总体模块控制系统的生命周期，输入模块部分负责读取用户输入的数据，显示模块部分负责显示用户之前输入的数据以及显示最终的计算结果，计算模块部分负责进行数据的运算以及一些其他的功能。具体的说，总体模块的作用主要是生成应用程序的主类，控制应用程序的生命周期。 输入模块主要描述了计算器键盘以及键盘的监听即主要负责读取用户的键盘输入以及 响应触屏的按键，需要监听手机动作以及用指针事件处理方法处理触屏的单击动作。同时提供了较为直观的键盘图形用户界面。 显示模块描述了计算器的显示区，即该区域用于显示用户输入的数据以及最终的计算结 VB应用程序的设计方法 ——“简易计算器”教学设计 揭阳第一中学卢嘉圳 教学内容：利用所学知识制作Visual Basic程序“简易计算器” 教学目标：能熟练运用CommandButton控件及TextBox控件进行Visual Basic(以下简称VB)程序的设计，能熟练运用条件语句编写代码 教学重点:运用开发VB程序一般过程的思路来开发“简易计算器” 教学难点:分析得出实现“简易计算器”各运算功能的算法。 教材分析： 当我刚开始进行程序设计的教学时，便感觉比较难教。这是因为程序设计本身枯燥、严谨，较难理解，而且学生大多数都是初学者，没有相应的知识基础。对于《程序设计实例》，我们选用的教材是广东教育出版社出版的《信息技术》第四册，该书采用的程序设计语言是VB，而学生是仅学过了一点点简单的QB编程之后就进入《程序设计实例》的学习的。 教材为我们总结了设计VB程序的一般步骤：创建用户界面；设置控件属性；编写事件程序代码；运行应用程序。我总结了一下，其实VB程序设计可分为设计用户界面及编写程序代码两个环节。 教学过程： 一、引入新课 任务：让学生按照书上提示完成一个非常简单的VB程序——“计算器”（仅包含开方、平方、求绝对值功能）的制作。 目的：加强对CommandButton控件及TextBox控件的掌握，复习对开方、求绝对值函数的使用。 引入本节课的学习任务：设计一个简易计算器，包含加、减、乘、除、开方、平方等运算。程序界面可参考下图。 具体功能为：在Text1中输入一个数值，然后单击代表运算符的按钮则运算结果会在text2中显示出来；比如在text1中输入一个2，然后按“+”按钮，再输入一个3按“-”按钮，再输入一个-4按“*”按钮，则实际为(2-3)*(-4)；最后在text2中显示结果为4。 模拟计算器 学生姓名：**** 指导老师：**** 摘要本课程设计的课题是设计一个模拟计算器的程序，能够进行表达式的计算，并且表达式中可以包含Abs()和Sqrt()运算。在课程设计中，系统开发平台为Windows ，程序设计设计语言采用C++，程序运行平台为Windows 或*nix。本程序的关键就是表达式的分离和处理，在程序设计中，采用了将输入的中缀表达式转化为后缀表达式的方法，具有可靠的运行效率。本程序做到了对输入的表达式（表达式可以包含浮点数并且Abs()和Sqrt()中可以嵌套子表达式）进行判定表达式是否合法并且求出表达式的值的功能。经过一系列的调试运行，程序实现了设计目标，可以正确的处理用户输入的表达式，对海量级数据都能够通过计算机运算快速解决。 关键词C++程序设计；数据结构；表达式运算；栈；中缀表达式；后缀表达式；字符串处理；表达式合法判定； 目录 1 引言 (3) 1.1课程设计目的 (3) 1.2课程设计内容 (3) 2 设计思路与方案 (4) 3 详细实现 (5) 3.1 表达式的合法判定 (5) 3.2 中缀表达式转化为后缀表达式 (5) 3.3 处理后缀表达式 (7) 3.4 表达式嵌套处理 (8) 4 运行环境与结果 (9) 4.1 运行环境 (9) 4.2 运行结果 (9) 5 结束语 (12) 参考文献 (13) 附录1：模拟计算器源程序清单 (14) 1 引言 本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的后进先出的基本性质。利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。该算法的复杂度为O(n)，能够高效、快速地求解表达式的值，提高用户的效率。 1.1课程设计目的 数据结构主要是研究计算机存储，组织数据，非数值计算程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 模拟计算器程序主要利用了“栈”这种数据结构来把中缀表达式转化为后缀表达式，并且运用了递归的思想来解决Abs()和Sqrt()中嵌套表达式的问题，其中还有一些统计的思想来判定表达式是否合法的算法。 1.2课程设计内容 本次课程设计为计算器模拟程序，主要解决表达式计算的问题，实现分别按表达式处理的过程分解为几个子过程，详细的求解过程如下：1 用户输入表达式。 2 判定表达式是否合法。 3 把中缀表达式转化为后缀表达式。 4 求出后缀表达式的结果。 5 输出表达式的结果。通过设计该程序，从而做到方便的求出一个表达式的值，而不需要一步一步进行运算。 课题：用计算器计算 教学内容：三年级下册第48—51页内容 教学目标： 1、在运算中了解计算器的结构和基本功能；能正确、熟练地运用计算器进行一、两步的式题运算。 2、能运用计算器解决一些简单的实际问题，探索一些基本的数学规律。 3、培养观察、比较、分析、归纳、概括等能力。 教学过程： 一、尝试运用 师：开学到现在，我们一直在学习计算，下面这些题，哪些你一眼能看出来答案的，直接说的得数。 1、初步尝试 90＋56= 45×99≈ 87546—3469= 42×30= 2102÷30≈ 43×365= 师：最后两道看来有困难，列竖式算算。 师：先不报答案，要你自己检验做的对不对，你准备怎么样？试一试用计算器来验算，你们会吗？ 师：谁愿意带上你的竖式计算上来展示意下，向大家演示一下你用计算器验算的过程可以吗？（鼓励和表扬） 师：看来，大家还真的会用计算器！想不想“再显身手”？ 2、再次尝试：探索用计算器进行混合运算的方法 ①546×28－4276 ②2940 ÷28＋763 ③15021-87×99 ④25120÷（449－289） （1）这4题与上面4题相比，有什么不一样？会做吗？请试一试。 （2）交流操作方法。 （3）你有没有感觉到这4道题在计算过程中有什么不一样？ （4）用计算器计算③、④该怎么操作呢？我们以第③题为例，谁来介绍介绍？ （突出“记住中间数”、“使用MR键”、倒减等方法。） （①、②两题只要按顺序依次输入，③、④题要先算后一步，③④可以“记住过程得数”，③还可以倒减等） （5）介绍用存储键计算，尝试用“MR键”计算③④题。 二、解决生活问题 师：通过这几道题计算，你感觉计算器怎么样？你们喜欢用计算器吗？下面我们就发挥计算器的作用，用它来完成一个非常有价值的问题。 1、出示：一个水龙头滴水的动态画面。据统计一个没有关紧的水龙头，每天大约滴18千克的水，这些水就这样白白流掉了。 （1）照这样计算一年(按365天计算)要浪费多少千克水？ （2）把这些水分别装在饮水桶中(每桶约重15千克)算算大约能装多少桶？ （3）你家每月用几桶水？算算这些水够你家用几个月？大约合多少年？ 师：目前我国西南大旱，一些地区粮食因为缺水绝收。云南山区的孩子们喝脏水解渴。联系我们刚才的这些计算数据，你想到什么？ 三、探索计算规律： 师：既然人们发明了这么好的计算器，我们就应该更好地运用它。让我们来挑战一下自己，探索计算的规律好不好？ 1、找出规律后再填写每组的后2题得数，并用计算器检验。 19+9×9= 118+98×9= 1117+987×9= 11116+9876×9= 111115+98765×9= 学生汇报自己的发现。按这样一种规律写下去，下一题该是什么样的？ 2、自己探索规律。 1122÷34= 111222÷334= 11112222÷3334= …… 111…1222…2÷333…34= 2001个1 2001个2 2000个3 “移动应用开发”实验报告 1 而受至到众多开发者的欢迎，成为真正意义上的开放式操作系统。计算器通 过算法实行简单的或学计算从而提高了数学计算的效率，实现计算器的界面 优化，使界面更加友好，操作更加方便。基于android的计算器的设计系统具 有良好的界面；必要的英互信息：简约美观的效票，使用人员能快捷简单地 进行操作，即可单机按钮进行操作，即时准确地获得需要的计算的结果，充 分降低了数字计算的难度和节约了时间。 2.系统概要设计 2.1计算器功能概要设计 根据需求，符合用户的实际需求，系统应实现以下功能：计算器界面友好， 方便使用，具有基本的加，减，乘，除功能。能够判断用户输入运算数是否 正确，支持小数运算，具有清除功能。 整个程序基于Android 技术开发，除总体模块外主要分为输入模块、显 示模块以及计算模块这三大部分。在整个系统中总体模块控制系统的生命周期，输入模块部分负责读取用户输入的数据，显示模块部分负责显示用户之 前输入的数据以及显示最终的计算结果，计算模块部分负责进行数据的运算 以及一些其他的功能。具体的说，总体模块的作用主要是生成应用程序的主类，控制应用程序的生命周期。 输入模块主要描述了计算器键盘以及键盘的监听即主要负责读取用户的 键盘输入以及响应触屏的按键，需要监听手机动作以及用指针事件处理方法 处理触屏的单击动作。同时提供了较为直观的键盘图形用户界面。 显示模块描述了计算器的显示区，即该区域用于显示用户输入的数据以 及最终的计算结果，同时负责显示一些其他的信息。 计算器模块主要描述了计算器的整体，实现了计算器的界面，负责用户 2 输入数据，计算，显示，清零等功能。 2.2输入模块设计 系统如果想完成计算器中各种功能，首先用户要能进行数据输入，由于 是在触屏手机上开发计算器程序，所以要求输入可以直接使用触屏进行，所 以在设计的时候就要充分的考虑这一点。正是由于考虑到这个特殊的地方， 所以在进行模块设计中，选择编写输入模块类的时候会特意选取使用可以支 持触屏输入的特殊增强型图形用户界面类。 输入模块主要的任务是描述计算器键盘以及实现键盘的监听，即当用户 点击按键或者屏幕的时候监听会去调用相应的处理办法，本模块还需要为系 统提供一个较为直观的键盘图形用户界面。输入模块的功能图如图 2.3显示模块设计 作为手机计算器系统，显示部分也是必不可少的一部分。没有显示部分 就没有办法显示用户输入的数字是否正确，甚至不能显示计算出的结果，由 此可见显示模块即包括输入的部分（因个人技术原因不能显示表达式的形式）也包括输出的部分。 显示模块主要完成的任务是描述计算器的显示区，该区域用于显示用户 输入的数据以及最终的计算结果和一些其他信息。同时本模块还将提供调用 和设置显示的具体方法。 3 计算器算法原理 除法也用类似竖式的方法，从高位到低位逐一得出结果。大概过程如下：（注意，是二进制运算） 1、先左移除数，直到除数不小于被除数，同时记录移动的位数； 2、开始循环，循环次数为前一步移动的位数加1； 3、比较被除数与除数的大小，如果被除数不小于除数，则该位结果为1，否则为0； 4、除数右移一位，继续循环。 这种方法同样可以进行小数运算，根据需要的有效数字位数确定循环次数。 漏了一点，修改一下： 3、比较被除数与除数的大小，如果被除数不小于除数，则该位结果为1，并把被除数减去除数，否则为0 加减乘除求余： #include 奥地利符号计算研究所（Research Institute for Symbolic Computation，简称RISC）做了一个调查，投票选出32个最重要的算法： 1.A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一 种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定 次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。 2.集束搜索（又名定向搜索，Beam Search）——最佳优先搜索算法的优化。使用启 发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最 前面的m个最符合条件的节点，m是固定数字——集束的宽度。 3.二分查找（Binary Search）——在线性数组中找特定值的算法，每个步骤去掉一半 不符合要求的数据。 4.分支界定算法（Branch and Bound）——在多种最优化问题中寻找特定最优化解决 方案的算法，特别是针对离散、组合的最优化。 5.Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几 里得算法和线性系统中高斯消元法的泛化。 6.数据压缩——采取特定编码方案，使用更少的字节数（或是其他信息承载单元）对 信息编码的过程，又叫来源编码。 7.Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况 下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一 起，加密后续通讯。 8.Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。 9.离散微分算法（Discrete differentiation） 10.动态规划算法（Dynamic Programming）——展示互相覆盖的子问题和最优子架构 算法 11.欧几里得算法（Euclidean algorithm）——计算两个整数的最大公约数。最古老的 算法之一，出现在公元前300前欧几里得的《几何原本》。 12.期望-最大算法（Expectation-maximization algorithm，又名EM-Training）——在 统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值；第二步是最大化，最大化在第一 步上求得的最大可能值来计算参数的值。 13.快速傅里叶变换（Fast Fourier transform，FFT）——计算离散的傅里叶变换（DF T）及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。 14.梯度下降（Gradient descent）——一种数学上的最优化算法。 15.哈希算法（Hashing） 16.堆排序（Heaps） 17.Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统 和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。 18.LLL算法（Lenstra-Lenstra-Lovasz lattice reduction）——以格规约（lattice）基数 为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用： 背包加密系统（knapsack）、有特定设置的RSA加密等等。 import java.awt.BorderLayout; import java.awt.Color; import java.awt.GridLayout; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.JButton; import javax.swing.JFrame; import javax.swing.JPanel; import javax.swing.JTextField; /** * 一个计算器，与Windows附件自带计算器的标准版功能、界面相仿。但还不支持键盘操作。 */ public class Calculator extends JFrame implements ActionListener { /** 计算器上的键的显示名字*/ private final String[] KEYS = { "7", "8", "9", "/", "sqrt", "4", "5", "6", "*", "%", "1", "2", "3", "-", "1/x", "0", "+/-", ".", "+", "=" }; /** 计算器上的功能键的显示名字*/ private final String[] COMMAND = { "Backspace", "CE", "C" }; /** 计算器左边的M的显示名字*/ private final String[] M = { " ", "MC", "MR", "MS", "M+" }; /** 计算器上键的按钮*/ private JButton keys[] = new JButton[KEYS.length]; /** 计算器上的功能键的按钮*/ private JButton commands[] = new JButton[COMMAND.length]; /** 计算器左边的M的按钮*/ private JButton m[] = new JButton[M.length]; /** 计算结果文本框*/ private JTextField resultText = new JTextField("0"); // 标志用户按的是否是整个表达式的第一个数字,或者是运算符后的第一个数字 private boolean firstDigit = true; // 计算的中间结果。 private double resultNum = 0.0; // 当前运算的运算符 private String operator = "="; // 操作是否合法 private boolean operateValidFlag = true; /** * 构造函数 */ 用VC++6实现计算器具有优先功能（一） 摘要在计算器的设计中，加、减、乘、除和括号功能是有优先级的，括号优先于乘除，乘除优先于加减，实现了这部分功能，就完成了计算器的主要框架的设计，在此基础上就可 扩充其它的功能，如各种函数功能。 关键词计算器，加、减、乘、除、括号，优先级 所使用的计算器一般具备加、减、乘、除功能，好一点的计算器还具有括号功能，使计算器能完成较复杂一些的设计，更好一点的计算器还具有各种函数功能，使计算器用起来更加实用和方便。总之，加、减、乘、除功能和括号功能是科学计算器所必须具有的功能，在此基础上可以很容易地扩充各种函数功能，如sin、cos、tan、log、lnx、x n等等，以实现复杂的运算。 一、优先功能 任何一个计算表达式，如a＋b×c÷( d－e×f＋g )－h，计算的规则是：先乘、除后,加、减，遇到括号先执行括号里的表达式，并且括号里的表达式同样遵循这一原则。因此，要获得正确的运算结果，首先是如何来实现先乘除后加减呢？这就要对操作符定义一个优先级，即谁先执行，而操作符的优先级通常是用自然数来表示的，称为优先数。＋、－的优先数小于×、÷的优先数，而×、÷优先数小于括号〔〕，等号“＝”的优先数最低，低于＋、－的优先数；由于在一个计算表达式中既有操作数（整数或实数等）和操作符（＋、－、×、÷、＝等），还有操作符的优先数，这就至少需要二个堆栈，一个是暂存操作数或中间结果的堆栈，简称操作数栈；另一个是暂存操作符优先数的堆栈，称为操作符栈。为了编程的方便，这里操作符栈用了二个，一个用于暂存操作符的字符堆栈，另一个用于暂存操作符优先数（自然数）的堆栈。三个堆栈的栈深M取为常数，这里取M=50，用定长数组来表示，可保证堆栈不会出现上溢，当然用可变数组或链栈来表示则最好。 加、减的优先数，用整数int ADD=SUB=1来表示；乘、除的优先数用整数int MUL=DIV=2来表示。当然你可以取其它整数来表示，只要乘、除的优先数大于加、减的优先数即可。等号的优先数最低，用int EQU=0来表示。从上述表达式可看出，左括号“（”的优先数高于左边操作符的优先数，而低于右边操作符的优先数，这样一个左括号就有二个优先数，这样会使编程复杂化，因此须对左括号作特殊处理：就是遇到左括号直接压栈，而不做优先数的比较。另外，为了保证左括号右边的操作符能正常压栈，因此，左括号的优先数应低于加、减操作符的优先数，即左括号的优先数应取为int LPARENT=0；而对右括号的处理是：右括号一律不进栈。 实现加、减、乘、除和括号功能的算法步骤：首先从左向右读取计算表达式，读一个操作数或一个操作符，统称为读一个单词。 ⑴从左向右扫描表达式，读一个单词。 1）当前单词是操作数，压栈；继续本步。 2）当前单词是操作符，则转⑵。 3）当前单词是左括号“（”，则转⑶。 4）当前单词是右括号“）”，则转⑷。 5）当表达式扫描完毕，即单词是等号，则转⑸。 ⑵若操作符栈空，则操作符进栈，转⑴；若操作符栈不空，则比较当前操作符与栈顶操作符的优 先数。 J I A N G S U U N I V E R S I T Y 科学计算器的的设计 —windows窗体应用程序学院：计算机科学与通信工程 专业班级：计算机科学与技术1102班 姓名：戴桂明 学号: 3110602041 指导老师：曹汉青 日期：2013年12月20日 目录 1选题原因及理由..................... 错误！未定义书签。2设计思想及框架................................ 错误！未定义书签。 一. 主体功能.............................................. 错误！未定义书签。 二. 开发环境 (3) 3相关表格和流程图 ............................. 错误！未定义书签。 一. 系统功能表 (4) 二. 系统流程图 (5) 4设计特点及关键算法........................... 错误！未定义书签。 5 测试结果及测试分析 (6) 6设计总结 (7) 7附录（源代码） (8) 计算器的设计与实现 1 选题原因及理由 我们在学习生活中，常会遇到一些繁杂的数值运算，这时候我们就必须用到科学计算器，所以便着手开发了这个计算器程序，以便用于自己的学习工作。要计算功能有以下几个方面：加法，减法，乘法，除法，求幂，求e的指数次方，求平方根，求Sin，求Cos，求Tan及其反函数等。 也可达到以下目的： 1、巩固并加深学生对C++语言程序设计知识的理解； 2、培养学生面向对象的程序设计思想，使学生认识面向过程和面向对象两种设计方法的区别； 3、进一步掌握和应用VC++ 2008集成开发环境； 4、提高运用C++语言解决实际问题的能力； 5、初步掌握开发小型实用软件的基本方法，能独立设计、实现基本的窗体应用系统； 6、掌握书写程序设计开发文档的能力。 2 设计思想及框架 课题名称：高级计算器的实现 说明：实现一个计算器。 要求： 1）用“计算器”的标准视图执行简单的计算。 2）用其科学型视图执行高级的科学计算。 一．主体功能 1、十进制数的加、减、乘、除、乘方、取模等简单计算。 2、科学计算函数，包括(反)正弦、(反)余弦、(反)正切、(反)余切、开方、指数等函数运算。 3、以角度、弧度两种方式实现上述部分函数。 二．开发环境 VC++ 2008 基于堆栈的计算器实现算法 运算符的优先级 对于计算器，有很多成熟的理论。本文章讨论的是利用一个操作数堆栈和一个运算符堆栈进行运算的方法。这种算法已经有很完善的解决方案，此处讨论的是最简化的模型，旨在让初学者在最短的时间内学到此算法的精髓，并能灵活的应用到科研的任何一个领域。 简单表达式的计算 首先请看这个表达式： 3＋5＋6＊7＊8＾2＾3 （8＾2指的是82） 这里运算有三种优先级“＾”--＞ “＊”--＞“＋”，如何实现优先级运算呢？ 当扫描字符串3＋5＋6＊7＊8＾2＾3的时候。 1.先移进3＋5，发现下一个运算符是＋，优先级与上一个相同，于是就先计算3＋5，将它们改为8。于是式子变为：8＋6＊7＊8＾2＾3 2.现在下一运算符＊优先级比上一个＋要高，于是继续前移：8＋6 ＊7＊8＾2＾3 3.现在下一个运算符是＊，与上一个相同，于是先计算6＊7，式子变为：8＋42＊8＾2＾3 4.继续：8＋42＊8＾2＾3 5.8＋42＊64＾3 6.8＋42＊262144 7.8＋1．101＊107 8.1．101＊107 现在式子变成一个数，整个运算也就结束了。 但怎样在计算机中完成这个过程呢？当遇到8＋6＊7时必须先运算6＊7，但这时8和＋保存在哪里呢？这里使用的方法是：建立一个操作数堆栈和一个运算符堆栈，把8和＋分别压到两个堆栈中。 对于式子：3＋5＋6＊7-8＾2 剩余式子操作数堆栈运算符堆栈优先级比较操作 3＋5＋6＊7-8＾2 ±6＊7 -8＾2 3，5 ±相等计算3＋5＝8 ＋6＊7-8＾2 8 ＊7 -8＾2 8，6 ±大于 -8＾2 8，6，7 ＋，＊小于计算6＊7＝42 -8＾2 8，42 ＋等于计算8＋42＝50 -8＾2 50 ＾2 50，8 - 大于 50，8，2 -，＾计算8＾2＝64 50，64 - 计算50-64＝-14 -14 ＾ -------------------------------------------------------------------------------------------------------------- 可以看出，如果利用操作数堆栈和运算符堆栈的话，只要： 1．步进扫描表达式。 2．遇到操作数就压入操作数堆栈中，遇到运算符就将它的优先级与运算符堆栈栈顶运算符的优先级比较，如果它的优先级更大，就将它压入堆栈，否则就将栈顶运算符弹出来进行运算。 只要这样就可以实现优先级的运算。 优先级的改变 在我的示例程序中规定了3种优先级 界面设计&算法实现 界面设计： 基于两点乘积及全波傅里叶算法的应用
AOPA最新理论题库第7章任务规划
向量 - 向量叉乘 向量点乘
数据结构课程设计计算器
简易计算器
微机课设简易计算器
基于安卓的计算器的设计与实现
计算器制作
模拟计算器程序-课程设计
用计算器计算(教案)
移动应用开发实验---简单计算器
计算器算法原理
计算机中的常用算法
基于Java的计算器算法(源代码).(精选)
计算器程序
计算器的设计与实现
基于堆栈的计算器实现算法
简单计算器设计源代码