c跳表算法
哈希查找、树表查找、跳表查找、基数查找。网上搜索最新文献好像都要钱的。
㈡ 在C语言中，什么是链表呀
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。
㈢ C语言中，select...case和 if...else if 哪个执行效率更高
没有select case
只有switch case
1、 总体上说，switch...case 效率要高于同样条件下的if...else，特别是当条件分支较多时。
2、switch...case占用较多的代码空间，因为它要生成跳表，特别是当case常量分布范围很大但实际有效值又比较少的情况，switch...case的空间利用率将变得很低。例如上面的代码，如果把case 10改成case 100，则会生成101个表项，而大部分表项是指向同一分支(default分支)。switch...case是在以空间换时间。
3、switch...case只能处理case为常量的情况，对非常量的情况是无能为力的。例如 if (a > 1 && a < 100)，是无法使用switch...case来处理的。
转自CSDN博客
㈣ 求助C++编写———跳表的实现
【问题描述】
设计一个一元稀疏多项式简单计算器
【基本要求】
一元多项式简单计算器的基本功能是：
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++就行了哈~~
㈤ 跳跃表（skip list）
我们知道二叉搜索算法能够高效的查询数据，但是需要一块连续的内存，而且增删改效率很低。
跳表，是基于链表实现的一种类似“二分”的算法。它可以快速的实现增，删，改，查操作。
当我们要在该单链表中查找某个数据的时候需要的时间复杂度为O(n).
怎么提高查询效率呢？如果我们给该单链表加一级索引，将会改善查询效率。
如图所示，当我们每隔一个节点就提取出来一个元素到上一层，把这一层称作索引，其中的down指针指向原始链表。
当我们查找元素16的时候，单链表需要比较10次，而加过索引的两级链表只需要比较7次。当数据量增大到一定程度的时候，效率将会有显着的提升。
如果我们再加多几级索引的话，效率将会进一步提升。 这种链表加多级索引的结构，就叫做跳表 。
与二分查找类似，跳跃表能够在 O(㏒n)的时间复杂度之下完成查找，与红黑树等数据结构查找的时间复杂度相同，但是相比之下，跳跃表能够更好的支持并发操作，而且实现这样的结构比红黑树等数据结构要简单、直观许多。
跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美：查找、删除、添加等操作都可以在对数期望时间下完成。跳跃表体现了“ 空间换时间 ”的思想,
从本质上来说，跳跃表是在单链表的基础上在选取部分结点添加索引，这些索引在逻辑关系上构成了一个新的线性表，并且索引的层数可以叠加，生成二级索引、三级索引、多级索引，以实现对结点的跳跃查找的功能。
与二分查找类似，跳跃表能够在 O(㏒n)的时间复杂度之下完成查找，与红黑树等数据结构查找的时间复杂度相同，但是相比之下，跳跃表能够更好的支持并发操作，而且实现这样的结构比红黑树等数据结构要简单、直观许多。
但是现在问题来了，上文我举的例子是一个很完美的跳跃表，它严格地按照二分法的思想建立了捷径。从理论上讲，单个跳跃表的层数按照严格二分的条件建立，层数就应该是 ㏒n 层(以2为底，n 为结点个数),但是在实际操作中，我们的数据会刚刚好是 2 的 n 次方吗？如果不是这么刚好的数据，没办法严格地二分，我要怎么开辟捷径呢？如果我对这个跳跃表进行插入或删除操作，破坏了严格地二分结构，又该怎么办？如果我们要强行解决这些问题，那就又要引入一大堆七七八八又难以实现的规则了，只怕这么做比建一棵树更为困难了。
既然我们没有办法很好地严格二分，也没有很好的规则去描述这些问题的处理方式，那么我们就不使用严格二分的方法就行了啊，不要一条绝路走到黑嘛！分析一下我们的目的，我们希望的事情是让查找操作的效率提升，如果我只开辟一条捷径，效率也确确实实是提升了的，如果能继续开辟捷径，如果最后我们能达到严格地二分，效率就会被提升，那也就是说我们并不是为了要实现二分，而是通过不断地努力去尽量地实现二分。
我们无法直接证明这个事实，但是我们可以通过“频率的稳定性”得到启发，提出了概率的定义，进而确定了事件的概率。从我举的例子里，我们不仅得到了启发，更是找到了解决问题的方法。也就是说，我们找到某种方式来实现捷径的开辟，这种方式在统计学的角度来说，可以往严格二分的情况趋近，在理论上实现 O(㏒n) 的时间复杂度。
跳跃表只需要从最上层开始遍历，由于每一层的链表都是有序的，因此当查找的“键”不存在于某一层中的时候，只需要在比查找目标的“键”要大的结点向下一次跳跃即可，重复操作，直至跳跃到最底层的链表。
1、先从顶层开始遍历,与16进行对比小，进入下一层。
2、与4进行比较,比4大,当前结点置为4结点，与16进行比较,进入下一层。
3、 与8进行比较,没有比8大,切换为当前结点4。
4、将节点4的下一个节点8和当前值进行比较,相同,取出。
1、函数实现向跳跃表中插入一个“键”为 key，“值”为 value 的结点。由于我们进行插入操作时，插入结点的层数先要确定因此需要进行抛硬币实验确定占有层数。
2、由于新结点根据占有的层数不同，它的后继可能有多个结点，因此需要用一个指针通过“键”进行试探，找到对应的“键”的所有后继结点，在创建结点之后依次修改结点每一层的后继，不要忘了给结点判空。在插入操作时，“键”可能已经存在，此时可以直接覆盖“值”就行了，也可以让用户决定，可以适当发挥。
寻找节点的位置，获取到插入节点的前一个节点,
3、与链表的操作执行相同的节点操作,地址替换。
模拟插入操作
首先我们需要用一个试探指针找到需要插入的结点的前驱，即用红色的框框出来的结点。需要注意的是，由于当前的跳跃表只有 2 层，而新结点被 3 层占有，因此新结点在第 3 层的前驱就是头结点。
接下来的操作与单链表相同，只是需要同时对每一层都操作。如图所示，红色箭头表示结点之间需要切断的逻辑联系，蓝色的箭头表示插入操作新建立的联系。
插入的最终效果应该是如图所示的。
由于需要删除的结点在每一层的前驱的后继都会因删除操作而改变，所以和插入操作相同，需要一个试探指针找到删除结点在每一层的前驱的后继，并拷贝。接着需要修改删除结点在每一层的前驱的后继为删除结点在每一层的后继，保证跳跃表的每一层的逻辑顺序仍然是能够正确描述。
1、根据删除的值找到当前值在跳表中的前驱结点 head 4
2、判断结点4的后驱结点的值是否为8，不是，直接跳出。当前值在跳表中不存在。
3、循环遍历每一层,执行地址变更。当前结点可能在其他层不存在结点，因此在变更的时候要判断是当前层是否存在该结点。
// 跳表中存储的是正整数，并且存储的数据是不重复的
public class SkipListTest {
//最大索引层数
private static int MAX_LEVEL =16;
//头节点
private Node head;
//索引的层级数,默认为1
private int levelCount =1;
private Random random;
class Node{
//结点值
private int value;
//当前节点的所有后驱节点。1-maxlevel 层。
private Node[]nodes =new Node[MAX_LEVEL];
//当前节点的层数
private int maxLevel;
public Node(int value,int maxLevel) {
this.value = value;
this.maxLevel = maxLevel;
}
}
public Node get(int value){
//1、从最高层开始遍历
Node cur =head;
for (int i =levelCount-1; i >=0 ; i--) {
//找到比该值小的那个结点
while (cur.nodes[i]!=null && cur.nodes[i].value < value){
cur = cur.nodes[i];
}
//开始寻找下一层,直到找到最后一层
}
if(cur.nodes[0]!=null&&cur.nodes[0].value == value){
return cur.nodes[0];
}
return null;
}
public void insert(int number){
//1、获取要插入的索引层数量
int level = randomLevel();
//2、创建新节点
Node newNode =new Node(number,level);
//3、获取每一层的前驱结点
Node update[] =new Node[level];
//遍历索引层
Node c =head;
for (int i =level-1; i >=0 ; i--) {
while (c.nodes[i]!=null&&c.nodes[i].value
c = c.nodes[i];
}
update[i] = c;
}
//4、更新每一层的索引结构
for (int i =0; i
//当前结点的后驱结点
newNode.nodes[i] =update[i].nodes[i];
//当前结点的前驱
update[i].nodes[i] =newNode.nodes[i];
}
//5、更新索引层
if(levelCount
levelCount =level;
}
}
public void delete(int value){
//1、获取每一层比当前值小的前一个结点
Node[]update =new Node[levelCount];
Node p =head;
for(int i =levelCount -1; i >=0; --i){
while(p.nodes[i] !=null && p.nodes[i].value < value){
p = p.nodes[i];
}
update[i] = p;
}
//2、如果最后一层的结点的与当前值相同,进入变更指针操作。
if(p.nodes[0] !=null && p.nodes[0].value == value){
for(int i =levelCount -1; i >=0; --i){
//从最高层开始变更,如果值相等才进行变更
if(update[i].nodes[i] !=null &&update[i].nodes[i].value == value){
update[i].nodes[i] =update[i].nodes[i].nodes[i];
}
}
}
}
// 随机函数
private int randomLevel(){
int level =1;
for(int i =1; i
if(random.nextInt() %2 ==1){
level++;
}
}
return level;
}
}
㈥ 出租车起步价是5块钱三公里，，5块钱后每公里一跳表,跳一次两元钱 。做一个C语言程序
#include<stdio.h>
int main()
{
int dis;//距离
printf("请输入汽车里程数\n");
scanf("%d",&dis);
if(dis <= 3)
{
printf("总价为5元");
}
else
{
printf("总价为%d元",(dis -3) * 2);
}
return 0;
}
有其他问题可私聊
㈦ C语言，创建一个链表并赋值1、2、3、4、5，麻烦把全部程序写下
// DLink.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "malloc.h"
typedef struct LNode
{
int data;
struct LNode *next;
}Dlink;
int _tmain(int argc, _TCHAR* argv[])
{
Dlink *l,*s1;
Dlink *s=(Dlink *)malloc(sizeof(Dlink));
l=s;
for(int i=0;i<5;i++)
{
s->data=i+1;
s1=(Dlink *)malloc(sizeof(Dlink));
s->next=s1;
s=s1;
}
s->next=NULL;
//数据就保存到以l为头结点的链表中了
return 0;
}
(7)c跳表算法扩展阅读：
对于非线性的链表，可以参见相关的其他数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn），和平衡二叉树一样。
其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。
由分别表示,，…，的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表。
㈧ php-红黑树、散列表、跳表理解入门
就是把链表的结构稍加改造，这种数据结构叫
为了提升链表的查询效率，怎么让链表支持类似‘数组’那样的‘二分’算法呢
跳表是一个各方面性能都比较优秀的 动态数据结构 ，可以支持快速地插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树。
Redis 中的有序集合（Sorted Set）就是用跳表来实现的。
那 Redis 为什么会选择用跳表(和散列表)来实现有序集合呢？ 为什么不用红黑树呢？这个问题一会在回答，先看看跳表的数据结构
其实概念很简单，就是在链表上加上了
当我们在不停插入数据，如果我们不更新索引，可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。
红黑树、AVL 树这样平衡二叉树，是通过左右旋的方式保持左右子树的大小平衡，而跳表是通过 随机函数 来维护平衡性。
插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是， 按照区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。
Redis 键值构建一个散列表，这样按照 key 来删除、查找一个成员对象的时间复杂度就变成了 O(1)。同时，借助跳表结构，其他操作也非常高效。
散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)。查找时根据这个对应关系匠互给定的 key 的映射 f(key)
这种关系 f 称为散列函数（又称哈希函数）。散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。那么关键字对应的记录存储位置称为散列地址。
散列函数的构造方法特点就是：计算简单、散列地址分布均匀
大家一定听说过 hash 碰撞。就是2个不同的 key 对应着不同的 f 关系。但这是几乎不可能的，即便像业界着名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。
我们只能通过其它途径来寻找方法。我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。
所谓的开放寻址法就是一但发生了冲突，就去寻找下一个空的散地址，只要散列表足够大，空的散列表地址总能找到，并将记录存入。
链地址法又称链表法，其实当发生冲突时存入链表，如下图很容易就可以看明白。此时，已经不存在什么冲突地址的问题，无论有多少冲突，都只是在当前位置给单链表增加结点的问题。
这种不常见，就是把冲突的单独找个地方。
顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑
平衡二叉树 是一种二叉排序树，其中每一个节点的左子树和右子树的高度不能大于 1
红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。
平衡二叉查找树其实有很多，比如，Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。
红黑树在众多里面，表现的最为平衡。
“近似平衡”就等价为性能不会退化得太严重。
一棵红黑树还需要满足这样几个要求：
看到这里你会很头大，什么黑的红的，完全不懂。赋上连接，有时间在看
散列表 ：插入删除查找都是O(1), 是最常用的，但其缺点是不能顺序遍历(存入的数据是无顺序的)以及扩容缩容的性能损耗。适用于那些不需要顺序遍历，数据更新不那么频繁的。
散列表总和链表、跳表一起出现组合使用。
跳表 ：插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便。
跳表还可以和散列表组合让删除、查找一个成员对象操作变为O(1)，也就是说利用了散列表查找速度，跳表的顺序结构
红黑树 ：插入删除查找都是O(logn), 中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。其实跳表更佳，但红黑树已经用于很多地方了。