求助C++编写———跳表的实现

Question

跳表的实现
题目描述：有序表的二分搜索具有很高的搜索效率，但是要将该方法移植到链表中具有较大的难度，跳表提供了一种解决方案。如图2所示的跳表结构，例如要搜索关键字43，首先由第2层表头指针开始向右搜索，令22与43比较，因为22<43，向右搜索，又令∞与43比较，现满足∞>=43，所以下降到1层；令48与43比较，这时有48>=43，再次下降到0层，最后令43与43比较。
实现跳表类及其各种常规操作。
基本要求：(1) 能够根据给定有序序列创建给定层数的跳表并实现跳表的搜索；
(2) 能够实现跳表的插入和删除操作。
提高要求：能够根据给定有序序列采用特定的算法创建出适合层数的跳表并分析其性能。
设计提示：参考单链表的实现及其各种操作。
QQ184566896 也可直接发到QQ

Answer 1

【问题描述】
设计一个一元稀疏多项式简单计算器
【基本要求】
一元多项式简单计算器的基本功能是：
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++就行了哈~~

参考资料：http://hi.baidu.com/zhangna_307/blog/item/e32408dec246e71b485403e9.html

Answer 2

这个分我要,等一下,我把程序发给你.
共四个文件(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

参考资料：<<数据结构算法与应用>> P222-229

本回答被提问者采纳