/**************************************
整数对应 32 bit 二进制数串中数字1的个数
2016-10-24
liukun
***************************************/
#include <stdio.h>
// #include <math.h> // 整数对应 32 bit 二进制数串中数字1的个数
int binary1counter(int n)
{
// if(n<0) return -1;
int i;
// int binaLength = ceil(log2(n));
int counter1=0;
for(i=0;i<32;++i) //for(i=0;i<binaLength;++i)
{
if(n & 1!=0)counter1++;
n = n>>1;
}
printf("%d\n",counter1);
return 1;
} int main()
{
binary1counter(-21);
return 0;
}
void linkListSort(LinkList &L)
// 将单链表L的节点重排，使其递增有序 2016-12-16
{
LNode *p=L->next, *pre;
LNode *r=p->next;
p->next=NULL;
p=r; //保存p->next，防止断链
while(p!=NULL){
r=p->next;
pre=L;
while(pre->next!=NULL && pre->next->data<p->data) //在有序表中查找插入 *p 的前驱节点 *pre,将*p插入到 *pre 之后
pre=pre->next;
p->next=pre->next;
pre->next=p;
p=r; //扫描剩下的节点
}
}
/******************************
C 简单的格式化读取文本操作
笨蛋，
居然遇到了一个奇怪的后缀自增问题
2016-11-29
*******************************/
#include<stdio.h>
typedef struct people
{
char name[10];
int age;
}people; void readFile()
{
FILE *fp;
char ch;
if((fp=fopen("E:\\data.dat","r"))==NULL) {
printf("file cannot be opened/n");
}
people p[2];
int i=0;
while (!feof(fp))
{
fscanf(fp,"%s %d",&p[i].name, &p[i].age);
printf("%s %d\n",p[i].name, p[i].age);
i++;
}
fclose(fp);
}
/******************
二叉树相关算法
2016-11-26
//真是想跑去看会儿电影
********************/
#include<stdio.h>
#define MAXSIZE 500 typedef stuct BiTreeNode
{
int data;
BiTreeNode * lchild;
BiTreeNode * rchild;
}* BiTree; //非递归方法求解二叉树高度
int BtDepth(BiTree T)
{
if(!T)
return 0;
int front=-1,rear=-1;
int last=0,level=0;
BiTree Q[MAXSIZE];
Q[++rear]=T;
BiTree p;
while(front>rear)
{
p=Q[++front];
if(p->lchild)
Q[++rear]=p->lchild;
if(p->rchild)
Q[++rear]=p->rchild;
if(front==last)
{
level++;
last=rear; //last 指向下一层
}
return level;
}
} int Btdepth2(BiTree t)
{
if(!T)
return 0;
int ldep=Btdepth2(T->lchild);
int rdep=Btdepth2(T->rchild);
return ldep>rdep?ldep+1:rdep+1;
} bool IsComplete(BiTree T)
// 判断给定二叉树是否为完全二叉树
{
InitQueue(Q);
if(!T)
return 1;
EnQueue(Q,T);
while(!IsEmpty(Q))
{
DeQueue(Q,p);
if(p) //非空节点子孙入队（子孙可能为空指针）
{
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild);
}
else //节点为空，检查之后有没有非空节点，有的话就不是完全二叉树了
while(!IsEmpty(Q))
{
DeQueue(Q,p);
if(p)
return 0;
}
}
}
/*
栈的应用
括号匹配
2016-11-24
//真是智障
*/
#include<stdio.h>
#define MAXSIZE 500 /* 字符栈 */
char cStack[MAXSIZE];
int top=-1; bool BracketsChecks(char *str)
{
int i=0,top=-1;
while(str[i]!='\0')
{
switch(str[i]){
case '('://cStack[++top]='(';break;
case '['://cStack[++top]=str[i];break;
case '{':cStack[++top]=str[i];break;
case ')':if(cStack[top--]!='(') return false;break;
case '}':if(cStack[top--]!='{') return false;break;
case ']':if(cStack[top--]!='[') return false;break;
default: break;
}
i++;
}
if(top==-1)
return true;
return false;
} int main()
{
char str[]= "1+2*(5*6)+{5/7+[55+55]}";
if(BracketsChecks(str))
{
printf("OK\n");
}
return 0;
}
/***********************
2016-11-18
[矩阵]调整为阶梯矩阵
liu kun
> 指针动态传递二维数组
*************************/
#include<stdio.h>
#include<math.h>
#define EPSINON 1e-5 /* 主要数据结构 */
typedef float dataType;
struct rowinfo
{
int index;
int leftZeroCount;
};
dataType matrix[4][5]={0,0,1,2,1,1,2,3,4,5,0,0,1,2,1,0,1,2,3,4}; /* 浮点数判0 */
bool equalZero(dataType d)
{
return fabs(d)<EPSINON;
} /* 指针实现动态传递 */
void adaptMatrix(dataType ** matrix,dataType ** toMatrix, int m, int n)
/* m rows n columns*/
{
int i,j;
rowinfo rowlen[m];
for(i=0;i<m;i++)
{
rowlen[i].index=i;
for(j=0;j<n&&equalZero(*((dataType *)matrix+n*i+j));j++);
rowlen[i].leftZeroCount=j;
}
//sort the rowinfo array
for(i=1;i<m;i++)
{
rowinfo temp = rowlen[i];
for(j=i-1;rowlen[j].leftZeroCount>temp.leftZeroCount && j>=0; rowlen[j+1]=rowlen[j--]);
rowlen[j+1] = temp;
}
// copy to newMatrix
for(i=0;i<m;i++)
{
for(j=0;j<n;++j) *((dataType *)toMatrix+n*i+j)= *((dataType *)matrix+ n*rowlen[i].index +j);
}
} // Test main function
int main()
{ dataType toMatrix[4][5];
int columNum = sizeof(matrix[0])/sizeof(matrix[0][0]);
adaptMatrix((dataType **)matrix, (dataType **)toMatrix,4,columNum);
int i,j;
for(i=0;i<4;i++)
{
for(j=0;j<columNum;j++)
printf("%.2f ",toMatrix[i][j]);
printf("\n");
}
return 0;
}
/****************************************
打印杨辉三角
date: 2016-10-15
writer: liu kun
reference: 数据结构 殷人昆
*****************************************/
#include <iostream>
#include<iomanip>
#include "queue.h"
using namespace std; //控制数字间隔
char blank[3+1] = " ";
void YANGVI(int n)
{
Queue q;
EnQueue(q,1);EnQueue(q,1);
int i,j;QElemType s=0,t;
for(i=1;i<=n;i++)
{
cout<<endl;
// 每行起始位置排版
for(int bl_count=0;bl_count<n-i;bl_count++)
cout<<blank;
EnQueue(q,0);
for(j=1;j<=i+2;j++) //第 i 行的 i+2 个系数，包括一个 0
{
DeQueue(q,t);
EnQueue(q,s+t); //计算下一行系数并入队
s=t;
if(j!=i+2)cout<<setw(sizeof(blank)-1)<<s<<blank;
}
}
};
int main()
{
YANGVI(10);
return 0;
}
> queue.h #ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED
#define MAXSIZE 500
typedef int QElemType; typedef struct Queue{
int maxSize=MAXSIZE;
QElemType *data=new QElemType[maxSize];
int front=0;
int rear=front;
}Queue; void InitQueue(Queue &q); int EnQueue(Queue &q, QElemType x)
{
//check full
if((q.rear+1)%q.maxSize==q.front)
{
return 0;
}
else{
q.data[q.rear]=x;
q.rear = (q.rear+1)%q.maxSize;
return 1;
}
} int DeQueue(Queue &q,QElemType& x)
{
// check empty, ERROR code 1
if(q.rear==q.front) return 0;
else{
x = q.data[q.front];
q.front=(q.front+1)%q.maxSize;
return 1;
}
} int QueueEmpty(Queue &q)
{
if(q.rear==q.front)return 1;
else return 0;
} // 引用作为地址传值
int QueueFull(Queue &q)
{
return (q.rear+1)%q.maxSize==q.front;
} int QueueSize(Queue& q)
{
return (q.rear+q.maxSize-q.front)%q.maxSize;
}
#endif // QUEUE_H_INCLUDED
简单排序算法实现
simpleSort.h
#ifndef SIMPLESORT_H_INCLUDED
#define SIMPLESORT_H_INCLUDED
typedef int EleType; int RbinarySearch(EleType A[], const EleType x, int low, int high)
{
if(low>high) return -1;
int mid = (low+high)/2;
if(A[mid]==x)
return mid;
else
if(A[mid]>x)
{
high = mid -1;
return(binarySearch(A,x,low,high));
}
else
{
low = mid + 1;
return(binarySearch(A,x,low,high));
}
} int binarySearch(EleType A[], const EleType x, int low, int high)
{
while(low<=high){
int mid = (low+high)/2;
if(A[mid]==x)
return mid;
else if(A[mid]>x) high = mid -1;
else low = mid + 1;
}
return -1;
} int insertSort(EleType A[], int n)
/* 数组下标从0开始，n为元素个数 */
{
if(n<1) return 0;
register int i,j;
for(i=1;i<n;i++)
{
EleType tem=A[i];
for(j=i-1;j>=0 && A[j]>tem; A[j+1]=A[j--]);
A[j+1]=tem;
}
return 1;
} int selectSort(EleType A[], int n)
{
if(n<1) return 0;
int i,j;
for(i=0;i<n;i++)
{
int minInd=i;
for(j=i+1;j<n;j++)
{
if(A[j]<A[minInd])minInd = j;
}
EleType tem=A[i];
A[i]=A[minInd];
A[minInd]=tem;
}
return 1;
} int partion(EleType A[], int low, int high)
{
const EleType pivot = A[low];
while(low<high)
{
while(low<high&&A[high]>=pivot) high--;
A[low]=A[high];
while(low<high&&A[low]<pivot) low++;
A[high] = A[low];
}
A[high]=pivot;
return high;
} int quickSort(EleType A[], int n, int low, int high)
{
if(n<1) return 0;
if(low>high) return 1;
int p = partion(A,low,high);
quickSort(A,n, low, p-1);
quickSort(A,n, p+1, high);
return 1;
} #endif // SIMPLESORT_H_INCLUDED
或者使用标准库里提供的排序函数，到这儿就算是使用说明书上的知识了。
#include<stdio.h>
#include<stdlib.h> int A[] = {5,4,6,8,8,7,9,1,3,2,0};
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
} int main()
{
int i;
int testNum = sizeof(A)/sizeof(int);
qsort(A,testNum ,sizeof(A[0]),cmp);
for(i=0;i<testNum;i++)
printf("%d ",A[i]);
return 0;
}
/*
2016-11-17
判断字符串是否中心对称
*/
#include<stdio.h>
#include<string.h>
#define MAXSIZE 500 char str[] = "ehhhe";
bool isSymmetry(char * str)
{
char stack[MAXSIZE]="";
int top=-1;
int leftPart = strlen(str)/2;
int rightBegin = (1+strlen(str))/2;
int i;
for(i=0;i<leftPart;++i)
{
stack[++top]=str[i];
}
int strL = strlen(str);
for(i=rightBegin;i<strL;++i)
{
if( !str[i]==stack[top--] ) return false;
/*
if(str[i]==stack[top])
top--;
else
return false;
*/
}
return true;
} int main()
{
if(isSymmetry(str))
printf("%s", "Format OK!\n");
return 0;
}
/*
2016-11-17
判断字符串是否中心对称
P64 04
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 500 typedef struct charNode{
char data;
charNode * next;
}charNode; char str[] = "abcba"; void initCharNode(charNode *head, char * str)
{
int i;
charNode * p=head;
for(i=0;i<strlen(str);i++)
{
charNode * cnode = (charNode *)malloc(sizeof(charNode));
cnode->data=str[i];
cnode->next=NULL;
p->next = cnode;
p=cnode;
}
} bool isSymmetry(charNode *hd, const int n)
{
char stack[MAXSIZE]="";
int top=-1;
int leftPart = n/2;
int rightBegin = (n+1)/2;
int i;
charNode * p=hd;
for(i=0;i<leftPart;++i)
{
p=p->next;
stack[++top]=p->data;
}
if(n%2!=0) p=p->next;
for(i=rightBegin;i<n;++i)
{
p=p->next;
if( p->data !=stack[top--]) return false;
}
return true;
} int main()
{
charNode * hdnode = (charNode *)malloc(sizeof(charNode));
initCharNode(hdnode, str);
if(isSymmetry(hdnode,strlen(str)))
printf("%s", "Format OK!\n");
return 0;
}