DataStructure^Algorithm

BubbleSort.cpp

#include <iostream>  
using namespace std;  
int a[105];  
//下标从1开始  
void BubbleSort(int a[], int n)  
{  
    int i, j;  
    for(i = 1; i < n; i++)  
    {  
        for(j = 1; j <= n - i; j++)  
        {  
            if(a[j] > a[j + 1])  
            {  
                int temp = a[j + 1];  
                a[j + 1] = a[j];  
                a[j] = temp;  
            }  
        }  
    }  
}  
int main()  
{  
    int n, i;  
    cin >> n;  
    for(i = 1; i <= n; i++)  
        cin >> a[i];  
    BubbleSort(a, n);  
    for(i = 1; i <= n; i++)  
    cout << a[i] << " ";  
    cout << endl;  
    return 0;  
}  

DbLink.cpp

//DbLink.cpp
#include "stdafx.h"  
#include <iostream>  
//双向链表  
using namespace std;  
typedef struct Dbnode{  
    int data;      //节点数据  
    Dbnode *left;  //前驱结点指针  
    Dbnode *right; //后继节点指针  
}Dbnode;  
  
//创建节点  
Dbnode *CreateNode(int data){  
    Dbnode *pnode=new Dbnode;  
    if (pnode==NULL){  
        return NULL;  
    }  
    pnode->data=data;  
    pnode->left=pnode->right=NULL;//新节点的前驱和后继指针都指向NULL  
    return pnode;  
}  
  
//在表尾插入新节点，返回表头节点  
Dbnode *AppendNode(Dbnode *head,int data){  
    if (head==NULL){  
        return NULL;  
    }  
    Dbnode *phead=head;  
    Dbnode *pnode=CreateNode(data);//创建一个新节点  
    Dbnode *q=NULL;  
    while (phead!=NULL){ //找到最后一个节点,插入到最后一个节点后面  
        q=phead;//存放末节点  
        phead=phead->right;  
    }  
    q->right=pnode;  
    pnode->left=q;  
    return head;  
}  
  
//打印双向链表  
void Print(Dbnode *head){  
if (NULL==head){ //head为NULL表示为空链表  
    return;  
}  
Dbnode *p=head;  
while (p!=NULL){  
    cout<<p->data<<" ";  
    p=p->right;  
}  
cout<<endl;  
}  
//双向链表的测长  
int GetLength(Dbnode *head){  
    if (head==NULL)//如果指针为空或链表为空，则返回0  
    {  
        return 0;  
    }  
    Dbnode *phead=head->right;  
    int i=1;  
    while (phead!=NULL){  
          phead=phead->right;  
           i++;  
    }  
    return i;  
}  
  
//双向链表的节点查找  
Dbnode *FindNode(Dbnode *head,int data){  
    if (head==NULL){  
        return NULL;  
    }  
    Dbnode *phead=head;  
    Dbnode *pnode=NULL;  
    while (phead->right!=NULL && phead->data!=data){  
        phead=phead->right;  
    }  
    if (phead->data==data){//如果是值相等退出，则返回节点  
        return phead;  
    }  
    else  //如果没有找到，则返回NULL  
        return NULL;  
}  
  
//双向链表的节点插入  
//在node节点之后插入新节点  
void InsertNode(Dbnode *node,int data){  
    if (node==NULL){  
        return ;  
    }  
    Dbnode *p=CreateNode(data); //创建一个新节点  
    if(node->right==NULL){ //node为最后一个节点  
        node->right=p;  
        p->left=node;  
    }  
    else{  //node为中间节点  
        node->right->left=p; //p向左连接  
        p->right=node->right;  
        node->right=p;    //p向右连接  
        p->left=node;  
    }  
}  
  
//双向链表的节点删除,并返回表头节点  
//如果不存在节点，则删除失败返回NULL  
//如果删除后的链表为空，也返回NULL  
Dbnode *DeleteNode(Dbnode *head,int data){  
              if (head==NULL){//链表不存在返回NULL  
                  return NULL;  
                    }  
    Dbnode *pnode=FindNode(head,data);  
              if (NULL==pnode){ //查找节点，节点不存在，返回NULL  
                 return NULL;  
                   }  
            else if (pnode->left==NULL){ //node为头节点  
              head=pnode->right;  //使第一个节点为头节点  
                    if (head!=NULL){ //链表不为空  
                     head->left=NULL;  
                          }  
  
                   }  
            else if (pnode->right==NULL){//node为最后一个节点  
                 pnode->left->right=NULL;  
                   }  
             else{  
                 pnode->left->right=pnode->right;  
                 pnode->right->left=pnode->left;  
                }  
  
    free(pnode); //释放已被删除的节点空间  
    return head;  
}  
int _tmain(int argc, _TCHAR* argv[])  
{  
    Dbnode *head=CreateNode(0);//创建表头节点，表头节点不作为存放有意义数据的节点  
    for (int i=1;i<10;i++){  
        AppendNode(head,i);  
    }  
    Print(head);  
    cout<<"=======================\n";  
    cout<<"The length:"<<GetLength(head)<<endl;  
    cout<<"===========FindNode(4)============\n";  
    Dbnode *pfind=FindNode(head,11);  
    if (pfind==NULL){  
        cout<<"no find!"<<endl;  
    }  
    else  
        cout<<"find!"<<endl;  
    cout<<"===========InsertNode 32===========\n";  
       InsertNode(head->right->right->right,32);  
       Print(head);  
     cout<<"==========DeleteNode 8=============\n";  
     Dbnode *pNhead=DeleteNode(head,8);  
        Print(pNhead);  
    system("pause");  
    delete [] head;  
    return 0;  
}  

half_seek.cpp

int half_seek(int arr[], int low, int high, int num)
{
    if((low>=high)&&(arr[low]!=num))
        return -1;
    int mid;
    mid = (low+high)/2;
 
    if(arr[mid]==num)
        return mid;
    else if(arr[mid]>num)
        high = mid-1;
    else 
        low = mid+1;
    return half_seek(arr,low,high,num);//递归
}

HeapSort.cpp

#include <iostream>  
using namespace std;  
int n;  
int a[105];  
//下标从1开始  
void HeapAdjust(int A[], int a, int z)   
{  
    int i, j;  
    for(i = a, j = 2 * i; j <= z; i = j, j = 2 * i)  
    { //i为父，j为子  
        if(j < z && A[j + 1] > A[j]) j++;   //大顶堆，沿大孩子方向下行  
        if(A[i] < A[j])  
            swap(A[i], A[j]);  
        else break;  
    }  
}  
void HeapSort(int A[], int n)  
{  
    int i;  
    for(i = n / 2; i >= 1; i--) //从倒数第一个非叶子结点，自下而上堆化  
        HeapAdjust(A, i, n);  
    for(i = n; i > 1; i--)  
    { //交换A[1]与最后元素A[i]（i=n, ..., 1）, 再堆化  
        swap(A[1], A[i]);  
        HeapAdjust(A, 1, i - 1);  
    }  
}  
int main()  
{  
    int i;  
    cin >> n;  
    for(i = 1; i <= n; i++)  
    cin >> a[i];  
    HeapSort(a, n);  
    for(i = 1; i <= n; i++) cout << a[i] << " ";  
    cout << endl;  
    return 0;  
}  

HeapSort2.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int HEAP_SIZE = 13; //堆積樹大小
 
int parent(int);
int left(int);
int right(int);
void Max_Heapify(int [], int, int);
void Build_Max_Heap(int []);
void print(int []);
void HeapSort(int [], int);
 
/*父結點*/
int parent(int i)
{
    return (int)floor((i - 1) / 2);
}
 
/*左子結點*/
int left(int i)
{
    return (2 * i + 1);
}
 
/*右子結點*/
int right(int i)
{
    return (2 * i + 2);
}
 
/*單一子結點最大堆積樹調整*/
void Max_Heapify(int A[], int i, int heap_size)
{
    int l = left(i);
    int r = right(i);
    int largest;
    int temp;
    if(l < heap_size && A[l] > A[i])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if(r < heap_size && A[r] > A[largest])
    {
        largest = r;
    }
    if(largest != i)
    {
        temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        Max_Heapify(A, largest, heap_size);
    }
}
 
/*建立最大堆積樹*/
void Build_Max_Heap(int A[])
{
    for(int i = (HEAP_SIZE-2)/2; i >= 0; i--)
    {
        Max_Heapify(A, i, HEAP_SIZE);
    }
}
 
/*印出樹狀結構*/
void print(int A[])
{
    for(int i = 0; i < HEAP_SIZE;i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}
 
/*堆積排序程序碼*/
void HeapSort(int A[], int heap_size)
{
    Build_Max_Heap(A);
    int temp;
    for(int i = heap_size - 1; i >= 0; i--)
    {
        temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        Max_Heapify(A, 0, i);
    }
    print(A);
}
 
/*輸入資料並做堆積排序*/
int main(int argc, char* argv[])
{
    int A[HEAP_SIZE] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
    HeapSort(A, HEAP_SIZE);
    system("pause");
    return 0;
}

HeapStackNew.cpp

//HeapOnly.cpp  
#include   <iostream>  
using   namespace   std;  
  
class   HeapOnly  
{  
public:  
  HeapOnly()   {   cout   <<   "constructor."   <<   endl;   }  
  void   destroy   ()   const   {   delete   this;   }  
private:  
  ~HeapOnly()   {}    
};  
  
int   main()  
{  
  HeapOnly   *p   =   new   HeapOnly;  
  p->destroy();  
  // HeapOnly   h;  
  // h.Output();  
  
  return   0;  
}  
//StackOnly.cpp  
//2005.07.18------2009.06.05  
#include   <iostream>  
using   namespace   std;  
  
class   StackOnly  
{  
public:  
  StackOnly()   {   cout   <<   "constructor."   <<   endl;   }  
  ~StackOnly()   {   cout   <<   "destructor."   <<   endl;   }  
private:  
  void*   operator   new   (size_t);  
};  
  
int   main()  
{  
  StackOnly   s;                        //okay  
  StackOnly   *p   =   new   StackOnly; //wrong  
  
  return   0;  
}

InsertSort.cpp

#include <iostream>  
#include <cstdio>  
#define N 1005  
using namespace std;  
int n, a[N];  
void InsertSort(int a[], int n) //下标从0开始  
{  
    int i, j, temp;  
    for(i = 1; i < n; i++)  
    {  
        temp = a[i];  
        for(j = i; j > 0 && temp < a[j - 1]; j--) 
            a[j] = a[j - 1];  
        a[j] = temp;  
    }  
}  
 
int main()  
{  
    int i;  
    scanf("%d", &n);  
    for(i = 0; i < n; i++) scanf("%d", &a[i]);  
    InsertSort(a, n);  
    for(i = 0; i < n; i++) printf("%d\n", a[i]);  
    return 0;  
}  

LinkHandle.cpp

#include "stdio.h"
 
struct list
{
    int key;
    struct list *next;
};
 
struct list *reverse(struct list *old)
{
    struct list *node = old;
    struct list *prev = NULL;
      
    while(node != NULL)
    {
        // get the next node, and save it at pNext
        struct list* next = node->next;
        // if the next node is null, the currect is the end of original
        // list, and it's the head of the reversed list
        if(next == NULL)
            old = node;
        
        // reverse the linkage between nodes
        node->next = prev;
 
        // move forward on the the list
        prev = node;
        node = next;
       }
 
      return old;
}
 
struct list *reverse2(struct list *head)
{
    struct list *h = head;
 
    struct list *new = NULL,*tmp;
 
    if (h == NULL) return h;
 
    do 
    {
        tmp = h;
        h = h->next;
        tmp->next = new;
        new = tmp;
    }while(h != NULL && h != head);
 
    return new;
}
 
int insert_list(struct list *l,int value)
{
    struct list *node;
 
    node = (struct list *)malloc(sizeof(struct list));
 
    while(l->next!=NULL)l=l->next;
    
    node->key = value;
    node->next = NULL;
 
    l->next = node;
}
 
struct list * list_merge( struct list *head1, struct list *head2 )
{
    struct list *res;
 
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;
 
    if (head1->key < head2->key)
    {
        res = head1;
        printf("res1 %d\n",res->key);
        res->next = list_merge( head1->next, head2);
    } else {
        res = head2;
        printf("res2 %d\n",res->key);
        res->next = list_merge( head1, head2->next);
    }
 
    return res;
}
 
 
struct list * list_merge2(struct list *head1, struct list *head2)
{
    struct list *head,*p1,*p2;
 
    if (head1 == NULL)
        return head2;
 
    if (head2 == NULL)
        return head1;
 
    if (head1->key < head2->key)
    {
        head = head1;
        p1 = head1->next;
        p2 = head2;
    }
    else
    {
        head = head2;
        p2 = head2->next;
        p1 = head1;
    }
 
    struct list *pcurrent = head;
    while (p1 != NULL && p2 != NULL)
    {
        if (p1->key <= p2->key)
        {
            pcurrent->next = p1;
            pcurrent = p1;
            p1 = p1->next;
        }
        else
        {
            pcurrent->next = p2;
            pcurrent = p2;
            p2 = p2->next;
        }
    }
 
    if (p1 != NULL)
        pcurrent->next = p1;
    if (p2 != NULL)
    pcurrent->next = p2;
    
    return head;
}
 
 
int list_len(struct list *head)
{
    int len;
 
    struct list *h = head;
 
    if (h == NULL) return 0;
 
    do 
    {
        len ++;
        h = h->next;
    }while( h != NULL && h != head);
 
    return len;
}
 
main()
{
    struct list *head1,*head2,*head = NULL, *p = NULL;
    int i;
 
    head = (struct list *)malloc(sizeof(struct list));
 
    head->key = 1;
    head->next = NULL;
 
    for ( i = 2; i < 10; i ++ )
        insert_list(head,i);
 
    p = head;
    while(p!= NULL)
    {
        printf("%d\n",p->key);
        p = p->next;
    }
 
    printf("------\n");    
 
    head = reverse(head);
    p = head;    
    while(p != NULL)
    {
        printf("%d\n",p->key);
        p = p->next;
    }
    printf("---------\n");
    p = reverse2(head);
    while(p != NULL)
    {
        printf("%d\n",p->key);
        p = p->next;
    }
 
 
 
    printf("--------\n");
 
    head1 = (struct list *)malloc(sizeof(struct list));
 
    head1->key = 1;
    head1->next = NULL;
 
    for ( i = 3; i < 20; i = i + 2 )
        insert_list(head1,i);
 
    head2 = (struct list *)malloc(sizeof(struct list));
 
    head2->key = 2;
    head2->next = NULL;
 
    for ( i = 4; i < 20; i = i + 2 )
        insert_list(head2,i);
 
    p = list_merge2( head2, head1);
    printf("list len:%d\n",list_len(p));
    while(p != NULL)
    {
        printf("%d\n",p->key);
        p = p->next;
    }
}

MergeSort.cpp

#include <iostream>  
#define N 105  
using namespace std;  
int n;  
int a[N], t[N];  
/* 归并 */  
//下标从0开始  
void Merge(int a[], int l, int m, int r)  
{  
    /* p指向输出区间 */  
    int p = 0;  
    /* i、j指向2个输入区间 */  
    int i = l, j = m + 1;  
    /* 2个输入区间都不为空时 */  
    while(i <= m && j <= r)  
    {/* 取关键字小的记录转移至输出区间 */  
        if (a[i] > a[j])  
            t[p++] = a[j++];  
        else  
            t[p++] = a[i++];  
    }  
    /* 将非空的输入区间转移至输出区间 */  
    while(i <= m) t[p++] = a[i++];  
    while(j <= r) t[p++] = a[j++];  
    /* 归并完成后将结果复制到原输入数组 */  
    for (i = 0; i < p; i++)  
        a[l + i] = t[i];  
}  
  
/* 归并排序 */  
void MergeSort(int a[], int l, int r)  
{  
    int m;  
    if (l < r)  
    {/* 将长度为n的输入序列分成两个长度为n/2的子序列 */  
        m = (l + r) / 2;  
        /* 对两个子序列分别进行归并排序 */  
        MergeSort(a, l, m);  
        MergeSort(a, m + 1, r);  
        /* 将2个排好的子序列合并成最终有序序列 */  
        Merge(a, l, m, r);  
    }  
}  
int main()  
{  
    int i;  
    cin >> n;  
    for(i = 0; i < n; i++) cin >> a[i];  
    MergeSort(a, 0, n - 1);  
    for(i = 0; i < n; i++) cout << a[i] << " ";  
    cout << endl;  
    return 0;  
}  

qsort.cpp

#include <iostream>  
using namespace std;  
int n;  
int a[105];  
//下标从0开始  
int partition(int a[], int low, int high)  
{//快速排序中的一趟  
    int key;//作为枢轴来使用  
    key = a[low];  
    while(low < high)  
    {  
        while(low < high && a[high] >= key)  
        --high;  
        a[low] = a[high];  
        while(low < high && a[low] <= key)  
        ++low;  
        a[high] = a[low];  
    }  
    a[low] = key;  
    return low;  
}  
void qsort(int a[], int low, int high)  
{//快速排序的递归形式  
    int loc;  
    if(low < high)  
    {  
        loc = partition(a, low, high);//一趟排序结果的调用  
        qsort(a, low, loc - 1);  
        qsort(a, loc + 1, high);  
    }  
}  
int main()  
{  
    int i;  
    cin >> n;  
    for(i = 0; i < n; i++) cin >> a[i];  
    qsort(a, 0, n - 1);  
    for(i = 0; i < n; i++) cout << a[i] << " ";  
    cout << endl;  
    return 0;  
}  

SelectSort.cpp

#include <iostream>  
using namespace std;  
int a[105];  
//下标从1开始  
void SelectSort(int a[], int n)  
{  
    int i, j, pos;  
    for(i = 1; i < n; i++)  
    {  
        pos = i;  
        for(j = i; j <= n; j++)  
        {  
            if(a[j] < a[pos])  
            pos = j;  
        }  
        int temp = a[pos];  
        a[pos] = a[i];  
        a[i] = temp;  
    }  
}  
int main()  
{  
    int n, i;  
    cin >> n;  
    for(i = 1; i <= n; i++) cin >> a[i];  
    SelectSort(a, n);  
    for(i = 1; i <= n; i++)  
    cout << a[i] << " ";  
    cout << endl;  
    return 0;  
}