29.算法入门

算法与数据结构基础

一、基础算法思想
二分：

while(guess != price) {
  if(guess > price) printf("high\n");
  else if(guess < price) printf("low\n");
  printf("please guess again\n");
  scanf("%d",&guess);
  count++;
}

递推：

for(int i = 2;i < 24;i++)
  fab[i] = fab[i-1] + fab[i-2];

枚举：

for(i1 = 1;i1 < 10;i1++)
for(i2 = 0;i2 < 10;i2++)
for(i3 = 0;i3 < 10;i3++)
for(i4 = 0;i4 < 10;i4++)
for(i5 = 0;i5 < 10;i5++)
{
  count = i1*10000 + i2*1000 + i3*100 + i4*10 +i5;
  if(count * i1 = i5 *111111) printf("%d %d %d %d %d\n",i1,i2,i3,i4,i5);

递归：

int main(){
  int i;
  scanf("&d",&i);
  printf("%d fact is:%d\n",i,fact(i));
  return 0;
}
int fact(int n){
  if(n <= 1) return 1;
  else return n*fact(n-1);
}

分治：

void gamecal(int k,int n) {
  int i,j;
  if(n == 2) {
    a[k][1] =k;
    a[k][2] = k+1;
    a[k+1][1] = k+1;
    a[k+1][2] = k;
  } else {
    gamecal(k,n/2);
    gamecal(k+n/2,n/2);
    for(i=k;i<k+n/2;i++){
    for(j=n/2+1;j<=n;j++){
      a[i][j] = a[i+n/2][j-n/2];
    }}
    for(i=k+n/2;i<k+n;i++)
    for(j=n/2+1;j<=n;j++)
      a[i][j] = a[i-n/2][j-n/2];
  }
}
int main() {
  int m,i,j;
  scanf("%d",&m);
  j=2;
  for(i=2;i<8;i++){
    j = j * 2;
    if(j == m) break;
  }
  gamecal(1,m);
  for(i=2;i<=m;i++)
    printf("%2d day",i-1);
  for(i=1;i<=m;i++){
    for(j=1;j<=m;j++) printf(%4d",a[i][j]);
    printf("\n");
  }
  return 0;
}

贪心：

int exchange(int n){
  int i,j;
  for(i=0;i<MAXN;i++)  if(n>parvalue[i]) break;
  while(n>0 && i<MAXN){
    if(n>=parvalue[i]){
      n -= parvalue[i];
      num[i]++;
    } else if(n<10 && n>=5)
    {
      num[MAXN-1]++;
      break;
    }
  return 0;
}

试探：

int main(){
  int i[7],j;
  for(i[0]=1;i[0]<30;i[0]++){
  for(i[1]=1;i[1]<30;i[1]++){
  if(i[0] == i[1] ) continue;
  for(i[2]=1;i[2]<30;i[2]++){
  if(i[0]==i[2] || i[1] == i[2]) continue;
  ......
  for(j=0;j<7;j++)
  printf("%3d",i[j]);
  printf("\n");
  }}}

模拟：

srand(time(NULL));
r=rand()%6 + 1;

二、简单数据结构
线性表：

typedef struct{
  char key[15];
  char name[20];
  int age;
}DATA;

typedef stuct Node{
  DATA data;
  struct Node* next;
}ChainListType;

ChainListType* ChainListAddEnd(ChainListType* head,DATA data){
  ChainListType *node,*h;
  if(!(node=(ChainListType*)malloc(sizeof(ChainListType)))){ printf("erron\n"); return NULL;}
  node->data = data;
  node-next = NULL;
  if(head == NULL){ head=node;return head;}
  h=head;
  while(h->next !=  NULL) h=h->next;
  h->next = node;
  return head;
}

ChainListType* ChainListAddFirst(ChainListType* head,DATA data){
  ChainListType *node,*h;
  if(!(node=(ChainListType*)malloc(sizeof(ChainListType)))){ printf("error\n"); return NULL;}
  node->data = data;
  node->next = head;
  head = node;
  return head;
}

ChainListType* ChainListInsert(ChainListType* head,char* findkey,DATA data){
  ChainListType *node,*node1;
  if(!(node=(ChainListType*)malloc(sizeof(ChainListType)))){ printf("error\n"); return NULL; }
  node->data = data;
  node1 = ChainListFind(head,findkey);
  if(node1) { node->next = node1->next; node1->next = node; }
  else { free(node); printf("unfind the position\n"); }
  return head;
}

ChainListType* ChainListFind(ChainListType* head,char* key){
  ChainListType *h;
  h=head;
  while(h){
    if(strcmp(h->data.key,key) == 0) return h;
    h=h->next;
  }
  return NULL;
}

int ChainListDelete(ChainListType* head,char* key) {
  ChainListType *node,*h;
  node = h = head;
  while(h){
    if(strcmp(h->data.key,key) == 0) { node-next = h->next; free(h); return 1;}
    else { node = h;  h = h->next; }
  }
  return 0;
}

队列：

typedef struct{
  DATA data[QUEUEMAX];
  int head;
  int tail;
}SeqQueue;

SeqQueue* SeqQueueInit(){
  SeqQueue *q;
  if(q=(SeqQueue*)malloc(sizeof(SeqQueue))) {
    q->head = 0;
    q->tail = 0;
    return q;
  } else return NULL;
}

void SeqQueueFree(SeqQueue *q){
  if(q!=NULL) free(q);
}

void SeqQueueIsEmpty(SeqQueue* q){
  return q->head == q->tail;
}

void SeqQueue(SeqQueue *q) {
  return q->tail - q-> head;
}

int SeqQueueIn(SeqQueue *q,DATA data){
  if(q->tail == QUEUEMAX){ printf("the queue full\n"); return 0; }
  else { q->data[q->tail++] = data; return 1; }
}

DATA *SeqQueueOut(SeqQueue *q){
  if(q->head == q->tail){
    printf("the queue empty\n");
  } else {
  return &(q->data[q-head++]);
  }
}

栈：

typedef struct{
  char name[15];
  int age;
}DATA;

typedef struct stack{
  DATA data[SIZE+1];
  int top;
}SeqStack;

SeqStack *SeqStackInit() {
  SeqStack *p;
  if(p=(SeqStack*)malloc(sizeof(SeqStack))) { p->top = 0; return p;}
  return NULL;
}

void SeqSTackFree(SeqSTack *s){
  if(s) free(s);
}

int SeqStackIsEmpty(SeqStack *s){
  return s->top == 0;
}

void SeqStackClear(SeqStack *s){
  s->top = 0;
}

void SeqStackIsFull(SeqStack *s){
  return s->top == SIZE;
}

int SeqStackPush(SeqStack *s,DATA data){
  if((s->top + 1) > SIZE) {printf("stack full\n"); return 0; }
  s->data[++s->top] = data;  
}

DATA SeqStackPop(SeqStack *s){
  if(s->top == 0){ printf("stack empty"); exit(0); }
  return (s->data[s->top --]);
}

三、复杂数据结构
树：
满二叉树和完全二叉树的区别

typedef char DATA;
typedef struct ChainTree{
  DATA data;
  struct ChainTree *left;
  struct ChainTree *right;
}ChainBinTree;

ChainBinTree *BinTreeInit(ChainBinTree *node){
  if(node != NULL) return node;
  else return NULL;
}

int BinTreeAddNode(ChainBinTree *bt,ChainBinTree *node,int n){
  if(bt == NULL) {printf("father node not avaliable\n"); return 0; }
  switch(n) {
    case 1: 
      if(bt->left) {printf("left son node empty\n"); return 0; }
      else bt->left = node; 
      break;
    case 2:
      if(bt->right) {printf("right son node not empty\n"); return 0; }
      else bt->right = node;
      break;
    default: printf("parameter wrong\n"); return 0;

ChainBinTree *BinTreeLeft(ChainBinTree *bt){
  if(bt) return bt->left;
  else return NULL;
}

int BinTreeIsEmpty(ChainBinTree *bt){
  if(bt) return 0;
  else return 1;
}

int BinTreeDepth(ChainBinTree *bt){
  int dep1,dep2;
  if(bt == NULL) return 0;
  else {
    dep1 = BinTreeDepth(bt->left);
    dep2 = BinTreeDepth(bt->right);
    if(dep1 > dep2) return dep1 + 1;
    else return dep2 + 1;
  }
}

ChainBinTree *BinTreeFind(ChainBinTree *bt,DATA data){
  ChainBinTree *p;
  if(bt == NULL) return NULL;
  else {
    if(bt->data == data) return bt;
    else {
      if(p=BinTreeFind(bt->left,data)) return p;
      else if(p=BinTreeFind(bt->right,data)) return p;
      else return NULL;
    }
  }
}

void BinTreeClear(ChainBinTree *bt) {
  if(bt) {
    BinTreeClear(bt->left);
    BinTreeClear(bt->right);
    free(bt);
  }
}

void BinTree_DLR(ChainBinTree *bt,void (*oper)(ChainBinTree *p)) {
  if(bt) {
    oper(bt);
    BinTree_DLR(bt->left,oper);
    BinTree_DLR(bt->right,oper);
  }
}

void BinTree_LDR(ChainBinTree *bt,void (*oper)(ChainBinTree *p)) {
  if(bt) {
    BinTree_LDR(bt->left,oper);
    oper(bt);
    BinTree_LDR(bt->right,oper);
  }
}

void BinTree_LRD(ChainBinTree *bt,void (*oper(ChainBinTree *p)) {
  if(bt) {
    BinTree_LRD(bt->left,oper);
    BinTree_LRD(bt->right,oper);
    oper(bt);
  }
}

void oper(ChainBinTree *p){
  printf("%c",p->data);
  return;
}

ChainBinTree *InitRoot() {
  ChainBinTree *node;
  if(node = (ChainBinTree*)malloc(sizeof(ChainBinTree))){
    printf("input:");
    scanf("%s",&node->data);
    node->left = NULL;
    node->right = NULL;
    return node;
  }
  return NULL;
}

void AddNode(ChainBinTree *bt) {
  ChainBinTree *node,*parent;
  DATA data;
  char select;
  if(node=(ChainBinTree*)malloc(sizeof(ChainBinTree))){
    scanf("%s",&node->data);
    node->left = NULL; node->right = NULL;
    scanf("%s",&data);
    parent = BinTreeFind(bt,data);
    if(!parent) {printf("unfind father node"); free(node); return; }
    do{
      select = getch(); select -= '0';
      if(select == 1 || select == 2)
        BinTreeAddNode(parent,node,select)
    }while(select != 1 && select != 2);
  }
  return;
}:


  图：

typedef struct{
char Vertex[VERTEX_MAX];
int Edges[VERTEX_MAX][VERTEX_MAX];
int isTrav[VERTEX_MAX];
int VertexNum;
int EdgeNum;
int GraphType;
}MatrixGraph;

void CreateMatrixGraph(MatrixGraph *G){
int i,j,k,weight;
char start,end;
for(i=0;i<G->VertexNum;i++) scanf("%c",&(G->Vertex[i]));
for(k=0;k<g->EdgeNum;k++){
scanf("%c,%c,%d",&start,&end,&weight);
for(i=0;start!=G->Vertex[i];i++)
for(j=0;end!=G->Vertex[j];j++)
G->Edges[i][j] = weight;
}
}

void OutMatrix(MatrixGraph *G) {
int i,j;
for(j=0;j<G->VertexNum;j++) printf("%c",G->Vertex[j]);
printf("\n");
for(i=0;i<G->VertexNum;i++){
printf("%c",G->Vertex[i]);
for(j=0;j<G->VertexNum;j++){
if(G->Edges[i][j] == MAXVALUE) printf("\t=");
else printf9"\n%d",G->Edges[i][j]);
}
printf("\n");
}
}

邻接表存储：

typedef struct edgeNode{
int Vertex;
int weight;
struct edgeNode *next;
}EdgeNode;

typedef struct{
EdgeNode *AdjList[VERTEX_MAX];
int VertexNum,EdgeNum;
int GraphType;
}ListGraph;

void CreateGraph(ListGraph *G) {
int i,weight;
int start,end;
EdgeNode s;
for(i=1;i<=G->VertexNum;i++) G->AdjList[i]=NULL;
for(i=1;i<=G->EdgeNum;i++) {
scanf(%d,%d,%d",&start,&end,&weight);
s=(EdgeNode)malloc(sizeof(EdgeNode));
s->next = G->AdjList[start];
s->Vertex = end;
s->weight=weight;
G->AdjList[start]=s;
if(G->GraphType == 0){
s=(EdgeNode *) malloc(sizeof(EdgeNode));
s->next = G->AdjList[end];
s->Vertex = start;
s->weight = weight;
G->AdjList[end]=s;
}
}
}

void OutList(ListGraph *G){
int i;
EdgeNode *s;
for(i=1;i<=G->VertexNum;i++) {
printf("vertex %d",i);
s=G->AdjList[i];
while(s){
printf9"->%d(%d)",s->Vertex,s->weight);
s=s->next;
}
printf("\n");
}
}

BFS、DFS:

typedef strcut{
int Data[QUEUE_MAXSIZE];
int head;
int tail;
}SeqQueue;

void QueueInit(SeqQueue *Q) {
Q->head = Q->tail = 0;
}

int QueueIsEmpty(SeqQueue Q) {
return Q.head==Q.tail;
}

int QueueIn(SeqQueue *Q,int ch) {
if((Q->tail + 1)%QUEUE_MAXSIZE == Q->head) return 0;
Q->Data[Q-tail] = ch;
Q->tail = (Q->tail + 1)%QUEUE_MAXSIZE;
return 1;
}

int QueueOut(SeqQueue *Q,int *ch) {
if(Q->head == Q->tail) return 0;
*ch = Q->Data[Q->head];
Q->head = (Q->head + 1)%QUEUE_MAXSIZE;
return 1;
}

void BFSTraverse(MatrixGraph *G) {
int i;
for(i=0;i<G->VertexNum;i++) G->isTrav[i]=0;
printf("BFS:");
for(i=0;i<G->VertexNum;i++) if(!G->isTrav[i]) BFS(G,I);
}

void BFSM(MatrixGraph *G,int k) {
int i,j;
SeqQueue Q;
QueueInit(&Q);
G->isTrav[k]=1;
printf("->%c",G->Vertex[k]);
QueueIn(&Q,k);
while(!QueueIsEmpty(Q)) {
QueueOut(&Q,&I);
for(j=0;j<G->VertexNum;j++)
if(G->Edges[i][j]!=MAXVALUE && !G->IsTrav[i]){
printf("->%c",G->Vertex[j]);
G->isTrav[j]=1;
QueueIn(&Q,j);
}
}
}

void DFSTraverse(MatrixGraph *G) {
int i;
for(i=0;i<G->VertexNum;i++) G->isTrav[i] = 0;
for(i=0;i<G->VertexNum;i++)
if(!G->isTrav[i]) DFSM(G,I);
}

void DFSM(MatrixGraph *G,int i) {
int j;
G->isTrav[i] = 1;
printf("->%c",G->Vertex[i]);
for(j=0;j<G->VertexNum;j++)
if(G->Edges[i][j]!=MAXVALUE && !G->isTrav[i])
DFSM(G,j);
}


最小生成树Prim算法:从一个顶点出发，然后选权值最小的边，构成边后，依次进行。

define USED 0

define NOADJ -1

void Prim(MatrixGraph G) {
int i,j,k,min,sum=0;
int weight[VERTEX_MAX];
char temvertex[VERTEX_MAX];
for(i=1;i<G.VertexNum;i++) {
weight[i] = G.Edges[0][i];
if(weight[i] == MAXVALUE) temvertex[i] = NOADJ;
else temvertex[i] = G.Vertex[0];
}
temvertex[0] = USED;
weight[0] = MAXVALUE;
for(i=1;i<G.VertexNum;i++) {
min = weight[0];
k=i;
for(j=1;j<G.VertexNum;j++)
if(weight[i] < min && tmpvertex[j] != 0) {min = weight[j]; k=j; }
sum += min;
printf("(%c,%c),",tmpvertex[k],G.Vertex[k]);
tmpvertex[k] = USED;
weight[k] = MAXVALUE;
for(j=0;j<G>VertexNum;j++)
if(G.Edges[k][j]<weight[j] && tmpvertex[j] != 0) { weight[j] = G.Edges[k][j]; tmpvertex[j] = G.Vertex[k]; }
}
printf("\n the sum is:%d\n",sum);
}


最短路径Dijkstra算法：按照从源点到其他各顶点的最短路径的升序依次堆溢出从源点到各顶点的最短路径，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。。

void Dijkstra(MatrixGraph G) {
int weight[VERTEX_MAX];
int path[VERTEX_MAX];
int tmpvertex[VERTEX_MAX];
int i,j,k,v0,min;
printf("\n input origin vertex:");
scanf("%d",&v0);
v0--;
for(i=0;i<G>VertexNum;i++) {
weight[i]=G.Edges[v0][i];
if(weight[i]<MAXVALUE && weight[i] > 0) path[i] = v0;
tmpvertex[i] = 0;
}
tmpvertex[v0] = 1;
weight[v0] = 0;
for(i=0;i<G.VertexNum;i++) {
min = MAXVALUE;
k=v0;
for(j=0;j<G.VertexNum;j++)
if(tmpvertex[j]==0 && weight[j]<min) {min = weight[j]; k=j;}
tmpvertex[k]=1;
for(j=0;j<G.VertexNum;j++)
if(tmpvertex[j]==0 && weight[k]+G.Edges[k][j]<weight[j]) {
weight[j] = weight[k] + G.Edges[k][j]; path[j] = k;
}
}
printf("\n vertex %c go eigher vertex short length is:\n",G.Vertex[v0];
for(i=0;i<G.VertexNum;i++) {
if(tmpvertex[i] == 1) {
k=i;
while(k != v0) { j=k; printf("%c<",G.Vertex[k]); k=path[k]; }
printf("%c\n",G.Vertex[k]);
} else printf("%c<-%c:no path\n",G.Vertex[i],G.Vertex[v0]);
}
}



四、排序
冒泡排序：
平均和最坏都是O(n平方)。

void BubbleSort(int a[],int n) {
int i,j,t,flat=0;
for(i=0;i<n-1;i++) {
for(j=i;j<n-1;j++) {
if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; flag=1; }
if(flag == 0)
break;
else flag = 0;
}
}


快速排序：
平均O(nlogn)。最坏O(n平方)。

int Division(int a[],int left,int right) {
int base = a[left];
while(left<right) {
while(left<right && a[right]>base) right--;
a[left]=a[right];
while(left<right && a[left]>base) left++;
a[right]=a[left];
}
a[left]=base;
return left;
}

void QuickSort(int a[],int left,int right){
int i,j;
if(left<right) {
i=Division(a,left,right);
QuickSort(a,left,i-1);
QuickSort(a,i+1,right);
}
}

//简化代码
void quickSort(int a[],int low,int high) {
if(low >= high) return;
int middle = low+(high-low)/2;
int pivot=a[middle];
int i=low,j=high;
while(i<=j) {
while(a[i]<pivot) { i++; }
while(a[j]>pivot) { j--; }
if(i<=j) { int temp=a[i]; a[i]]=a[j]; a[j]=temp; i++; j--; }
}
if(low < j) quickSort(a,low,j);
if(hight > i) quickSort(a,i,high);
}


简单选择排序：
平均和最坏都是O(n平方)。

void SelectSort(int a[],int n) {
int i,j,k,t;
for(i=0;i<n-1;i++) {
k=i;
for(j=i+1;j<n;j++) if(a[k]>a[j]) k=j;
t=a[i]; a[i]=a[k]; a[k]=t;
}
}


堆排序：堆是一个完全二叉树，树中每个结点对应于原始数据的一个记录，并且每个结点应满足以下条件，非叶结点的数据大于或等于其左、右孩子结点的数据。
平均和最坏都是O(nlogn)。

void HeapAdjust(int a[],int s,int n) {
int j,t;
while(2s+1 < n) {
j=2s+1;
if(j+1<n) { if(a[j]<a[j+1]) j++; }
if(a[s]<a[j]) { t=a[s]; a[s]=a[j]; a[j]=t; }
else break;
}
}

void HeapSort(int a[],int n) {
int t,i,j;
for(i=n/2-1;i>=0;i--) HeapAdjust(a,i,n);
for(i=n-1;i>0;i--) { t=a[0]; a[0]=a[i]; a[i]=t; HeadAdjust(a,0,i); }
}


插入排序：
平均和最坏都是O(n平方)。

void InsertSort(int a[],int n) {
int i,j,t;
for(i=1;i<n;i++) {
t=a[i];
for(j=i-1;j>=0 && t<a[j];j--) a[j+1]=a[j];
a[j+1]=t;
}
}


希尔排序：将需要排序的序列划分为若干个较小的序列，对这些序列进行直接插入排序，通过这样的操作可使需要排序的数列基本有序，最后再使用一次直接插入排序。
在希尔排序中首先要解决的是怎样划分子序列。对于子序列的构成不是简单地分段，而是采取相隔某个增量的数据组成一个序列。一般选择增量的规则是：取上一个增量的一半作为此次子序列划分的增量，一般初始值取元素的总数量。
平均O(n的3/2次方)，最坏O(n平方)。

void ShellSort(int a[],int n){
int d,i,j,x;
d=n/2;
while(d>=1){
for(i=d;i<n;i++){
x=a[i];
j=i-d;
while(j>=0 && a[j]>x){ a[j+d]=a[j]; j=j-d; }
a[j+d]=x;
}
d/=2;
}
}


合并排序：
平均和最坏情况下都是O(nlogn)。

void MergeStep(int a[],int r[],int s,int m,int n){
int i,j,k;
k=s;
i=s;
j=m+1;
while(i<=m && j<=n){
if(a[i]<=a[j]) r[k++]=a[i++];
else r[k++]=a[j++];
}
while(i<=m) r[k++]=a[i++];
while(j<=n) r[k++]=a[j++];
}

void MergePass(int a[],int r[],int n,int len){
int s,e;
s=0;
while(s+len < n){
e=s+2*len-1;
if(e>=n) e=n-1;
MergeSte[(a,r,s,s+len-1,e);
s=e+1;
}
if(s<n) for(;s<n;s++) r[s]=a[s];
}

void MergeSort(int a[],int n){
int p;
int len=1;
int f=0;
if(!(p=(int)malloc(sizeof(int)n))) { printf("wrong\n"); exit(0); }
while(len<n){
if(f) MergePass(p,a,n,len);
else MergePass(a,p,n,len);
len=2;
f=1-f;
}
if(f) for(f=0;f<n;f++) a[f]=p[f];
free(p);
}



五、常用算法——查找
顺序查找和二分查找

二叉排序树
  定义，二叉树或者是一棵空树，或者是一棵具有以下性质的二叉树：若它有左子树，则左子树上所有结点的数据均小于根结点的数据；或它有右子树，则右子树上所有结点的数据均存在于根结点的数据；左右子树本身又各是一棵二叉排序树。

typedef struct bst{
int data;
struct bst *left;
struct bst *right;
}BSTree;

void InsertBST(BSTree t,int key){
BSTree p,parent,head;
if(!(p=(BSTree *)malloc(sizeof(BSTree *)))){ printf("wrong\n"); exit(0); }
p->data=key;
p->left=p->right=NULL;
head=t;
while(head){
parent=head;
if(key < head->data) head=head->left;
else head=head->right;
}
if(key < parent->data) parent->left = p;
else parent->right = p;
}

void CreateBST(BSTree *t,int data[],int n){
int i;
t->data=data[0];
t->left=t->right=NULL;
for(i=1;i<n;i++) InsertBST(t,data[i]);
}

void BST_LDR(BSTree *t){
if(t){
BST_LDR(t->left);
printf("%d ",t->data);
BST_LDR(t->right);
}
return;
}

BSTree *SerarchBST(BSTree *t,int key){
if(!t || t->data==key) return t;
else if(key > t->data) return SearchBST(t->right,key);
else return SearchBST(t->left,key);
}

void BST_Delete(BSTree t,int key){
BSTree p,parent,l,*l1;
int child=0;
if(!t) return;
p=t;
parent=p;
while(p){
if(p->data == key){
if(!p->left && !p->right){
if(p==t) free(p);
else if(child==0) { parent->left == NULL; free(p); }
else { parent->right == NULL; free(p);
}
} else if(!p->left){
if(child==0) parent->left=p->right;
else parent->left = p->left;
free(p);
}else if{
if(child=0) parent->right = p->right;
else parent->right = p->left;
free(p);
} else {
l1=p;
l=p->right;
while(l->left){ l1=l; l=l->left; }
p->data = l->data;
l1->left = NULL;
free(l1);
}
p=NULL;
} else if(key < p->data){
child=0;
parent=p;
p=p->left;
} else{
child=1;
parent=p;
p=p->right;
}
}
}


索引查找
  创建索引的基本思想：将一个线性表（主表）按一定的函数关系或条件划分为若干个子表，每个子表创建一个索引项，由这些索引项构成主给的一个索引表。接着，采用线性或链接方式分别保存索引表和各个子表。

typedef struct item{
int index;
int start;
int length;
}INDEXITEM;
long stu[30]={1080101,2938472,2384201,24382......};
INDEXITEM indextable[3]={{10801,0,6},{10802,10,4},{10803,20,4}};

int IndexSearch(int key){
int i,index1,start,length;
index1=key/100;
for(i=0;i<30;i++){
if(indetable[i].index=index1){
start=indextable[i].start;
length=indextable[i].length;
break;
}
}
if(i>=3) return -1;
for(i=start;i<start+length;i++){
if(stu[i]==key) return 1;
}
return -1;
}

int InsertNode(key){
int i,index1,start,length;
index1=key/100;
for(i=0;i<3;i++){
if(indextable[i].index == index1){
start=indextable[i].start;
length=indextable[i].length;
break;
}
}
for(i=0;i<3;i++){
if(indextable[i].index == index1){
start=omdextable[i].start;
length=indextable[i].length;
break;
}
}
if(i>=3) return -1;
stu[start+length]=key;
indextable[i].length++;
return 0;
}


散列表
  基本思想：以线性表中每个元素的关键字key为自变量，通过一定的函数关系h(key)计算出函数的值，把这个值作为数组的下标，将元素存入对应的数组元素中。
  构造散列函数：1.直接定址法h(key)=key+C；2.除法取余法，用关键字key除以散列表长度n,得到的余数作为散列地址，n最好为一个素数；3.数字分析法，取关键字中某些比较分散的数字作为散列地址的方法；4.平方取中法，将关键字key求平方后，取中间的几位数字作为散列地址；5.折叠法，先将关键字key按散列地址要求的位数分成长度相等的几段，最后一段长度可能会短些。接着将这几段进行求和，然后去掉最高位的进位，将得到的值作为散列地址。
  处理冲突：1.开放地址法，从发生冲突的那个数组元素开始，按一定的次序，从散列表中查出一个空闲的数组元素，把发生冲突的待插入元素存入到该数组元素中；2.链接法，在散列表中的每个存储单元中增设一个指针域，将散列地址相同的元素链接起来。

int data[8]={69,65,90,37,92,6,28,54};
int hash[13]={0};

void InsertHash(int hash[],int m,int data){
int i;
i=data%13;
while(hash[i]) i=(i++)%m;
hash[i]=data;
}

void CreateHash(int hash[],int m,int data[],int n){
int i;
for(i=0;i<n;i++) InsertHash(hash,m,data[i]);
}

int HashSearch(int hash[],int m,int key){
int i;
i=key%13;
while(hash[i] && hash[i]!=key) i=(i++)%m;
if(hash[i]==0) return -1;
else return 1;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 200,667评论 5赞 472
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 84,361评论 2赞 377
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 147,700评论 0赞 333
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,027评论 1赞 272
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,988评论 5赞 361
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,230评论 1赞 277
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,705评论 3赞 393
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,366评论 0赞 255
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,496评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,405评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,453评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,126评论 3赞 315
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,725评论 3赞 303
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,803评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,015评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,514评论 2赞 346
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,111评论 2赞 341

推荐阅读更多精彩内容

  • 2018-06-14
    在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,311评论 0赞 2
  • 读书日
    说起世界读书日，如同大多数节日一样，其初设缘由被人们渐渐忽略，但却在新时代里焕发新的生机。世界读书日对于今天的我们...
    三省九思阅读 314评论 1赞 6
  • 不抱怨的世界
    最近刚换工作，钱差不多离家近，唯一不足下班迟，经常加班，于是咨询了一下身边的在职宝妈们，原来大家跟我一样的心态，都...
    晨香阅读 300评论 0赞 0
  • 瞧，这洞穴
    虽然生活在洞穴却总想看看外面的样子洞穴外也许阳光明媚，也许寒天冻地但那真实之境，蕴藏着真理 刚刚凿开的门缝如今又渐...
    俗然阅读 392评论 5赞 10