求助C++编写———跳表的实现
你的英语真好,看不懂
分几个步骤来做
|---给定一个两位数,将它的两位数兑换位置
|---求一个两位数的每一位上的数
|---求一个两位数各位上的数
|---求一个两位数十位上的数
|---判断素数:
|---能被2整除的不是素数
|---能被3整除的不是素数
|---....
|---能被这个数的平方根的整数部分整除的数不是素数
设计一个一元稀疏多项式简单计算器
【基本要求】
一元多项式简单计算器的基本功能是:
1,输入并建立多项式;
2,输出多项式,输出形式为整数序列:n,c1,e1,c2,c2,...,cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;
3,多项式a和b相加,建立多项式a+b;
4,多项式a和b相减,建立多项式a-b.
【测试数据】
1,(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7)
【实现提示】
用带表头结点的单链表存储多项式。
#include <stdio.h>
#include <malloc.h>
typedef struct node
{
float coef;
int expn;
struct node *next;
}Lnode, *polynmial;
void create(polynmial &L); //输入并建立多项式L
void display(polynmial L); //显示,输出多项式L
void sort(polynmial &L); //多项式L按指数排序
void reverse(polynmial &L); //逆置
void select(); //用户选择加减操作
void add(polynmial La, polynmial Lb, polynmial &Lc); //多项式La,Lb相加
void subtract(polynmial La, polynmial Lb, polynmial &Ld); //多项式La减去Lb,结果给Ld
void create(polynmial &L) //输入并建立多项式L
{
int i, n;
static struct node *p;
scanf("%d", &n);
L = (struct node *)malloc (sizeof(struct node));
L->next = NULL;
for(i = 0; i < n; i++)
{
p = (struct node *)malloc(sizeof(struct node));
scanf("%f %d", &p->coef, &p->expn);
p->next = L->next;
L->next = p;
}
}
void display(polynmial L)//显示,输出多项式L
{
struct node *p, *q;
int flag = 0;
int k = 0;
q = L->next;
while(q)
{
if(q->coef != 0)
k++;
q = q->next;
}
printf("%d, ", k);
p = L->next;
if(p->coef != 0)
{
printf("%.1f,%d, ", p->coef, p->expn);
flag++;
}
for(p = p->next; p; p = p->next)
{
if(p->coef != 0)
{
printf("%.1f,%d, ", p->coef, p->expn);
flag++;
}
}
if(flag == 0)
printf("%d\n", flag);
else
printf("\n");
}
void sort(polynmial &L)//多项式L按指数排序
{
polynmial p, q, r, u;
p = L->next;
L->next = NULL;
while(p != NULL)
{
r = L;
q = L->next;
while((q != NULL) && (q->expn <= p->expn))
{
r = q;
q = q->next;
}
u = p->next;
r->next = p;
p->next = q;
p = u;
}
}
void reverse(polynmial &L)//逆置
{
polynmial H;
static struct node *p, *q, *s;
H = (struct node*)malloc(sizeof(struct node));
H->next = NULL;
p = (struct node*)malloc(sizeof(struct node));
s = L->next;
p->coef = s->coef;
p->expn = s->expn;
p->next = s->next;
while(s)
{
p->coef = s->coef;
p->expn = s->expn;
p->next = s->next;
q = H->next;
H->next = p;
p->next = q;
p = (struct node*)malloc(sizeof(struct node));
s = s->next;
}
p = H->next;
q = L->next;
while(p)
{
q->coef = p->coef;
q->expn = p->expn;
q = q->next;
p = p->next;
}
}
void select() //用户选择加减操作
{
printf("请选择加减操作\n");
printf("1.两个一元多项式相加\n");
printf("2.两个一元多项式相减\n");
}
void add(polynmial La, polynmial Lb, polynmial &Lc)//多项式La,Lb相加
{
struct node *pa, *pb;
static struct node *pc;
Lc = (struct node*)malloc(sizeof(struct node));
pa = La->next;
pb = Lb->next;
Lc->next = NULL;
while(pa && pb)
{
pc = (struct node*)malloc(sizeof(struct node));
if(pa->expn < pb->expn)
{
pc->next = Lc->next;
Lc->next = pc;
pc->coef = pa->coef;
pc->expn = pa->expn;
pa = pa->next;
}
else
if(pa->expn == pb->expn)
{
pc->next = Lc->next;
Lc->next = pc;
pc->expn = pa->expn;
pc->coef = pa->coef + pb->coef;
pa = pa->next;
pb = pb->next;
}
else
{
pc->next = Lc->next;
Lc->next = pc;
pc->coef = pb->coef;
pc->expn = pb->expn;
pb = pb->next;
}
}
while(pa)
{
pc = (struct node*)malloc(sizeof(struct node));
pc->next = Lc->next;
Lc->next = pc;
pc->coef = pa->coef;
pc->expn = pa->expn;
pa = pa->next;
}
while(pb)
{
pc = (struct node*)malloc(sizeof(struct node));
pc->next = Lc->next;
Lc->next = pc;
pc->coef = pb->coef;
pc->expn = pb->expn;
pb = pb->next;
}
}
void subtract(polynmial La, polynmial Lb, polynmial &Ld)//多项式La减去Lb,结果给Ld
{
struct node *pa, *pb;
static struct node *pd;
Ld = (struct node*)malloc(sizeof(struct node));
pa = La->next;
pb = Lb->next;
Ld->next = NULL;
while(pa && pb)
{
pd = (struct node*)malloc(sizeof(struct node));
if(pa->expn < pb->expn)
{
pd->next = Ld->next;
Ld->next = pd;
pd->coef = pa->coef;
pd->expn = pa->expn;
pa = pa->next;
}
else
if(pa->expn == pb->expn)
{
pd->next = Ld->next;
Ld->next = pd;
pd->expn = pa->expn;
pd->coef = pa->coef - pb->coef;
pa = pa->next;
pb = pb->next;
}
else
{
pd->next = Ld->next;
Ld->next = pd;
pd->coef = pb->coef;
pd->expn = pb->expn;
pb = pb->next;
}
}
while(pa)
{
pd = (struct node*)malloc(sizeof(struct node));
pd->next = Ld->next;
Ld->next = pd;
pd->coef = pa->coef;
pd->expn = pa->expn;
pa = pa->next;
}
while(pb)
{
pd = (struct node*)malloc(sizeof(struct node));
pd->next = Ld->next;
Ld->next = pd;
pd->coef = -pb->coef;
pd->expn = pb->expn;
pb = pb->next;
}
}
int main()
{
int sign;
polynmial La, Lb, Lc, Ld;
printf("请输入第一个多项式:\n");
create(La);
sort(La);
printf("请输入第二个多项式:\n");
create(Lb);
sort(Lb);
select();
scanf("%d", &sign);
switch(sign)
{
case 1:
printf("多项式之和为:\n");
add(La, Lb, Lc);
sort(Lc);
reverse(Lc);
display(Lc);
break;
default:
printf("多项式之差为:\n");
subtract(La, Lb, Ld);
sort(Ld);
reverse(Ld);
display(Ld);
break;
}
return 0;
}
以前写的,用的也是单链表,参考下吧~~一些地方改成c++就行了哈~~
这个分我要,等一下,我把程序发给你.
共四个文件(skipnode.h,xcept.h,skip.h,skip.cpp),每个文件名我在前面有注释.
//file skipnode.h
#ifndef SkipNode_
#define SkipNode_
template <class E, class K> class SkipList;
template<class E, class K>
class SkipNode {
friend SkipList<E,K>;
private:
SkipNode(int size)
{link = new SkipNode<E,K> *[size];}
~SkipNode() {delete [] link;}
E data;
SkipNode<E,K> **link; // 1D array of pointers
};
#endif
//file xcept.h
// exception classes for various error types
#ifndef Xcept_
#define Xcept_
#include <new.h>
// bad initializers
class BadInitializers {
public:
BadInitializers() {}
};
// insufficient memory
class NoMem {
public:
NoMem() {}
};
// change new to throw NoMem instead of standard behavior
// Visual C++ requires following form of my_new_handler
int my_new_handler(size_t x)
{
throw NoMem();
// even though the following statement is unreachable,
// visual C++ will not compile successfully without it
return 0;
};
_PNH Old_Handler_ = _set_new_handler(my_new_handler);
// improper array, find, insert, or delete index
// or deletion from empty structure
class OutOfBounds {
public:
OutOfBounds() {}
};
// use when operands should have matching size
class SizeMismatch {
public:
SizeMismatch() {}
};
// use when zero was expected
class MustBeZero {
public:
MustBeZero() {}
};
// use when zero was expected
class BadInput {
public:
BadInput() {}
};
#endif
//file skip.cpp
// test skip list class
#include <iostream.h>
#include "skip.h"
class element {
friend void main(void);
public:
operator long() const {return key;}
element& operator =(long y)
{key = y; return *this;}
private:
int data;
long key;
};
void main(void)
{
SkipList<element, long> S(10001, 100, 0.5);
element e;
int i, n = 20;
for (i = 1; i <= n; i++) {
e.data = i; e.key = 2*i;
S.Insert(e);}
S.Output();
for (i=1; i <= n+1; i++) {
e.data = n+i; e.key = 2*i-1;
try {S.Insert(e);}
catch (BadInput)
{cout << "Unable to insert duplicate " << e << endl;}
catch (NoMem)
{cout << "Not enough memory to insert " << e << endl;}
}
S.Output();
for (i = 1; i <= n+1; i++) {
long k = 2*i-1;
try {S.Delete(k,e);
cout << "Deleted " << e.key << " " << e.data << endl;}
catch (BadInput)
{cout << "Delete of " << (2*i-1) << " failed" << endl;}
}
S.Output();
}
// file skip.h
#ifndef SkipList_
#define SkipList_
#include <stdlib.h>
#include <iostream.h>
#include <math.h>
#include "xcept.h"
#include "skipnode.h"
template<class E, class K>
class SkipList {
public:
SkipList(K Large, int MaxE = 10000,
float p = 0.5);
~SkipList();
bool Search(const K& k, E& e) const;
SkipList<E,K>& Insert(const E& e);
SkipList<E,K>& Delete(const K& k, E& e);
void Output();
private:
int Level();
SkipNode<E,K> *SaveSearch(const K& k);
int MaxLevel; // max permissible chain level
int Levels; // max current nonempty chain
int CutOff; // used to decide level number
K TailKey; // a large key
SkipNode<E,K> *head; // head node pointer
SkipNode<E,K> *tail; // tail node pointer
SkipNode<E,K> **last; // array of pointers
};
template<class E, class K>
SkipList<E,K>::SkipList(K Large, int MaxE, float p)
{// Constructor.
CutOff = p * RAND_MAX;
MaxLevel = ceil(log(MaxE) / log(1/p)) - 1;
TailKey = Large;
Levels = 0; // initial number of levels
// create head & tail nodes and last array
head = new SkipNode<E,K> (MaxLevel+1);
tail = new SkipNode<E,K> (0);
last = new SkipNode<E,K> *[MaxLevel+1];
tail->data = Large;
// head points to tail at all levels as empty
for (int i = 0; i <= MaxLevel; i++)
head->link[i] = tail;
}
template<class E, class K>
SkipList<E,K>::~SkipList()
{// Delete all nodes and array last.
SkipNode<E,K> *next;
// delete all nodes by deleting level 0
while (head != tail) {
next = head->link[0];
delete head;
head = next;
}
delete tail;
delete [] last;
}
template<class E, class K>
bool SkipList<E,K>::Search(const K& k, E& e) const
{// Search for element that matches k.
// Put matching element in e.
// Return false if no match.
if (k >= TailKey) return false;
// position p just before possible node with k
SkipNode<E,K> *p = head;
for (int i = Levels; i >= 0; i--) // go down levels
while (p->link[i]->data < k) // follow level i
p = p->link[i]; // pointers
// check if next node has key k
e = p->link[0]->data;
return (e == k);
}
template<class E, class K>
SkipNode<E,K> * SkipList<E,K>::SaveSearch(const K& k)
{// Search for k and save last position
// visited at each level.
// position p just before possible node with k
SkipNode<E,K> *p = head;
for (int i = Levels; i >= 0; i--) {
while (p->link[i]->data < k)
p = p->link[i];
last[i] = p; // last level i node seen
}
return (p->link[0]);
}
template<class E, class K>
int SkipList<E,K>::Level()
{// Generate a random level number <= MaxLevel.
int lev = 0;
while (rand() <= CutOff)
lev++;
return (lev <= MaxLevel) ? lev : MaxLevel;
}
template<class E, class K>
SkipList<E,K>& SkipList<E,K>::Insert(const E& e)
{// Insert e if not duplicate.
K k = e; // extract key
if (k >= TailKey) throw BadInput(); // too large
// see if duplicate
SkipNode<E,K> *p = SaveSearch(k);
if (p->data == e) throw BadInput(); // duplicate
// not duplicate, determine level for new node
int lev = Level(); // level of new node
// fix lev to be <= Levels + 1
if (lev > Levels) {lev = ++Levels;
last[lev] = head;}
// get and insert new node just after p
SkipNode<E,K> *y = new SkipNode<E,K> (lev+1);
y->data = e;
for (int i = 0; i <= lev; i++) {
// insert into level i chain
y->link[i] = last[i]->link[i];
last[i]->link[i] = y;
}
return *this;
}
template<class E, class K>
SkipList<E,K>& SkipList<E,K>::Delete(const K& k, E& e)
{// Delete element that matches k. Put deleted
// element in e. Throw BadInput if no match.
if (k >= TailKey) throw BadInput(); // too large
// see if matching element present
SkipNode<E,K> *p = SaveSearch(k);
if (p->data != k) throw BadInput(); // not present
// delete node from skip list
for (int i = 0; i <= Levels &&
last[i]->link[i] == p; i++)
last[i]->link[i] = p->link[i];
// update Levels
while (Levels > 0 && head->link[Levels] == tail)
Levels--;
e = p->data;
delete p;
return *this;
}
template<class E, class K>
void SkipList<E,K>::Output()
{
SkipNode<E,K> *y = head->link[0];
for (; y != tail; y = y->link[0])
cout << y->data << ' ';
cout << endl;
}
#endif
如何学习C语言
很多人对学习C语言感到无从下手,经常问我同一个问题:究竟怎样学习C语言? 我是一个教师,已经开发了很多年的程序,和很多刚刚起步的人一样,学习的第一个计算机语言就是C语言。经过这些年的开发,我深深的体会到C语言对于一个程序设计人员多么的重要,如果不懂C语言,你想写底层程序这几乎听起来很可笑,不懂C语言,你...
关于C语言的
要想学c ,最好先不用功能强大的集成的开发环境,这样有助于帮助你理解一些底层的东西,会对以后的学习很有帮住的这里给你介绍一个应用最普遍的编译器吧:Turbo C 2.0集成开发环境的使用 下载完以后,解压缩,双击TC.EXE,进入Turbo C 2.0集成开发环境中后, 屏幕上显示: ———--- File Edit Run Compile Proj...
计算机C语言有什么用啊??
用处:C语言是一种计算机程序设计语言。它可以作为系统设计语言,编写工作系统应用程序,也可以作为应用程序设计语言,编写不依赖计算机硬件的应用程序。特征:1、C语言是高级语言。它把高级语言的基本结构和语句与低级语言的实用性结合起来。C 语言可以像汇编语言一样对位、字节和地址进行操作,而这三者是...
如何高效的学好C 语言啊?
美河提供.C.精髓.软件工程方法.pdf,免费下载 链接:https:\/\/pan.baidu.com\/s\/17Q0JIVCI98FVDaRaisgA3A 提取码:ikzw C++是一种大型而复杂的语言,其设计目标是作为一种通用的工程语言。 本书分4个部分共19章,不仅详细介绍了C++语言的基本语法,而且讲解了 C++的高级应用(如虚函数、模板、异常...
教你如何在JavaScript中使用C程序的详解
即使没有语言,人类也可以用机器指令来编写程序。如果非要用 JavaScript 操作二进制,最终就类似这样:var flags = +enableXX1 << 16 | +enableXX2 << 15 | ...虽然能实现,但很丑陋。各种硬编码、各种位运算。然而,对于先天支持二进制的语言,看起来就十分优雅:union { struct { int enable...
c语言多行注释是由什么界定的
C程序注释是由 * 和 * 所界定的文字信息组成的。在编写C语言源代码时,应该多使用注释,这样有助于对代码的理解。在C语言中有两种注释方式:1、一种是以结束的块注释(block comment);2另一种是以\/\/开始、以换行符结束的单行注释(line comment)。可以使用分隔符来标注一行内的注释,也可以标注...
大学c语言怎么学
如何学习C语言?我说一下我是怎么学的吧,因为我就是计算机专业的学生 1. 首先选择一门入门的书籍,c primer plus 适合初学者入门 2. 制定详细的学习计划,遇到不懂的知识点,在网络上找一些对号的视频解决掉,然后回归继续书本学习 3.基础学完后开始在开源社区研究代码,先从看代码开始,然后尝试修改...
C语言编写串口通信程序在裸机下运行
C语言编写串口通信程序在裸机下运行 5 我想用C语言编写一个串口通信程序,然后再裸机下运行,有没有人有经验或者推荐我看些什么东西呢,谢谢!QQ:554287219... 我想用C语言编写一个串口通信程序,然后再裸机下运行,有没有人有经验或者推荐我看些什么东西呢,谢谢!QQ:554287219 展开 我来答 3个回答 #热议# ...
我在学软件测试,C语言学的很差,其它的还马马虎虎的,现在想认真学C语言...
建立坚实的基础。3. 学习进度:根据你的时间安排,制定每天或每周的学习进度表,确保按时完成学习任务。4. 实践项目:尝试编写小型C语言程序,以应用你所学的知识,这将有助于加深理解。5. 持续学习:定期回顾和巩固已学知识,保持学习的连续性。(二)寻找学习资源在学习C语言过程中,...
C程序注释由什么和什么所界定的文字信息组成
注释是由 \\* 和 *\\ 所界定的文字信息组成的。在编写C语言源代码时,应该多使用注释,这样有助于对代码的理解。在C语言中有两种注释方式:一种是以\/*开始、以*\/结束的块注释(block comment);另一种是以\/\/开始、以换行符结束的单行注释(line comment)。可以使用\/*和*\/分隔符来标注一行内的...
里戚肥儿: 实现了一下基本要求,包括了插入,删除和搜索. #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; struct SkipNode{ int value; int level; SkipNode *forword[1]; }; class SkipList { public: SkipList(); ~SkipList(); ...
东洲区18888406629: 超高分求助C++编写———跳表的实现1?
里戚肥儿: 第一:给定层数就肯定确定了有序链表元素个数,给定有序元素链表,就肯定确定了层数.所以有疑问. 第二:什么叫跳表的删除与插入;具体描述.
东洲区18888406629: 超高分求助C++编写———跳表的实现?
里戚肥儿: http://www.docin.com/p-20424557.html 你需要的
东洲区18888406629: 求助C++编写———跳表的实现?
里戚肥儿: #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; struct SkipNode{ int value; int level; SkipNode *forword[1]; }; class SkipList { public: SkipList(); ~SkipList(); SkipNode *insert(int value); SkipNode *search(int value); ...
东洲区18888406629: VC++如何利用跳表对一串数字进行排序 - ?
里戚肥儿: #include <stdio.h> const int MAXSIZE = 100; int main() { int i,j,t,n,N,a[MAXSIZE]; scanf("%d",&N); while(N--) { scanf("%d",&n); for(i = 0; i < n && i < MAXSIZE; ++i) scanf("%d",&a[i]); for(i = 0; i < n - 1; ++i) { for(j = i + 1; j < n; ++j) { if(a[i] < a[j]) {...
东洲区18888406629: c++编程中怎么进行跳跃? - ?
里戚肥儿: void main() {int a,b;while(1){intput();output();delay();}delete(); } 或者for(终止条件) 或者do{}while(终止条件)
东洲区18888406629: C++编写跳行读取数据 - ?
里戚肥儿: 用fgets()读一行 用sscanf()读相应的数据
东洲区18888406629: 求救:请高手帮我写一个简单的C++链表程序?
里戚肥儿: 由于c++是c的扩展,所以,c程序可以有c++编译.不过c程序要有c++编译需要一个头文件#include "stdafx.h"下面是我以前写的一个链表程序http://wenku.baidu.com/view/6c709ff9aef8941ea76e0573.html希望对你有帮助
东洲区18888406629: 用c++编一个 完整的顺序表的操作.. - ?
里戚肥儿: //顺序表的实现 模板类 #include<iostream> #include<string> using namespace std; const int MaxSize=100; bool error; template<class T> class SeqList { public:SeqList(){length=0;}; //无参构造函数SeqList(T a[],int n); //有参构造函数~...
东洲区18888406629: C++编程如何在条件成立时跳过一段执行下一段,但这段程序(就是所说的下一段)又不能在条件语句中 - ?
里戚肥儿: //假设条件成立时返回真 if(!条件成立) {//代码 }//另一段代码 另一种方法恐怕就是goto语句了吧