Skip to content

Instantly share code, notes, and snippets.

@zxlooong
Last active December 15, 2015 16:38
Show Gist options
  • Save zxlooong/5290121 to your computer and use it in GitHub Desktop.
Save zxlooong/5290121 to your computer and use it in GitHub Desktop.
DataStructure^Algorithm
#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;
}
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);//递归
}
#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;
}
#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;
}
//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;
}
#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;
}
#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;
}
}
#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;
}
#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;
}
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment