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), 中序遍歷即是順序遍歷，穩定。缺點是難以實現，去查找不方便。其實跳錶更佳，但紅黑樹已經用於很多地方了。