注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

老狗的博客

尽管每一步都很微小,但我确认我在进步

 
 
 

日志

 
 
关于我
sky

认真生活,努力工作 热爱技术,关注DB,存储,分布式,中间层,java,c++,php

网易考拉推荐

数据结构  

2014-10-02 12:06:12|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
数据结构:


1. 链表的数据结构
//单向链表
struct Node{
int data;
Node *next;
};
//双向链表
struct Node{
int data;
Node *next;
Node * prev;
};

2. 队列queue
先进先出
class queue
{
void push(const T&x);
void pop();
value_type& back ( );//return a reference of the back element
const value_type& back ( ) const;
}

3. 双向队列deque
队头和队尾皆可操作

4. 栈stack
class stack
{
void push(const T&x);
void pop();
value_type& top ( );
const value_type& top();
}

5. 二叉树的数据结构
struct bnode{
int data;
bnode* left;
bnode* right;
};
二叉树求最大高度
int maxdepth(root)
{
if (root == NULL) return 0;
int leftmax = maxdepth(root->left); 
int  rightmax = maxdepth(root->right);
int max = leftmax > rightmax ? leftmax : rightmax;
if (max != 0) {
return max+1;
} else {
return max;
}
}
6. 平衡二叉树(tree)


7. 二叉搜索树


8. 红黑树


9. 图的数据结构graph


10. map

三. 常用函数

1. 字符串处理函数

//将src的前n个字符连接到dest后面,并且添加\0,如果不足,则到'\0'为止
extern char *strncat(char *dest,char *src,int n);


//将format部分的内容复制到dest中,如果超过size,则只拷贝size-1,最后一个是\0
int snprintf(char *dest, size_t size, const char *format,);
snprintf(dest,sizeof(dest), "%s,%d", "abcdefg",10);

//将src的n个字节拷贝到目标dest
//如果num > strlen(source), 则在其后,追加num-strlen(source)个'\0'字符
//如果strlen(source) <= source, 则并不在num个字符后面添加'\0',需要手工去添加
char * strncpy ( char * dest, const char * src, size_t num );
{
 if(*dest == null || *dest == null)
 {
  return null;
 }
 
 size_t i = 0;
 for(i = 0; i < num; i++)
 {
  
  *(dest + i) = *(src + i);
if(*(src + i) == '\0') 
  {
   break;
  } 
 }
 
 while(i < num)
 {
  *(dst++) = '\0'; 
 }
 return dst;
}

//将ptr执行的内存中的前num个字节置为value
void * memset ( void * ptr, int value, size_t num );

//将内存中src指向的内容的前num个字节拷贝到dst中,不允许出现overlap
void* memcpy(void* dst, void* src, size_t num);

//将内存中src指向内容 的前num个字节拷贝到dst中, 允许出现overlap
void * memmove(void *dst, void* src, size_t num);

原型定义如下,注意memcpy中的定义出现restrict,而memmove没有

/* Copy N bytes of SRC to DEST. */
extern void *memcpy (void *__restrict __dest,
__const void *__restrict __src, size_t __n)
__THROW __nonnull ((1, 2));
/* Copy N bytes of SRC to DEST, guaranteeing
correct behavior for overlapping strings. */
extern void *memmove (void *__dest, __const void *__src, size_t __n)
__THROW __nonnull ((1, 2));



//字符串分割如"a,b,c"用","进行分割,得到"a","b","c"
char* strtok(char* ptr, char * delimiter)

//字符串比较,如果相等,则=0,如果前面大于后面,大于0,如果后面大于前面,小于0
int strcmp(char* src, char* dst)
int strncmp(const char *s1, const char *s2, size_t n);
//compare two strings ignoring case
int strcasecmp(const char *s1, const char *s2);
int strncasecmp(const char *s1, const char *s2, size_t n);

int fcntl(int fd, int cmd);
int fcntl(int fd, int cmd, long arg);
int fcntl(int fd, int cmd, struct flock *lock);


日期函数:

struct timeval
{
__time_t tv_sec; /* Seconds. */
__suseconds_t tv_usec; /* Microseconds. */
};

1秒= 1000 毫秒(millisecond) = 1000000微妙(macrosecond)


使用方式

struct timeval tv;

gettimeofday(&tv, NULL);


typedef long time_t

time_t time(time_t * t);


time_t secs = time(NULL);




四. 多线程编程基础知识

1. 普通锁
pthread_mutex_t
a. 加锁

/* Wait until lock for MUTEX becomes available and lock it. */
extern int pthread_mutex_lock (pthread_mutex_t *__mutex) __THROW;

一直等,等到拿到锁为止

/* Try to lock MUTEX. */
extern int pthread_mutex_trylock (pthread_mutex_t *__mutex) __THROW;

立即返回,成功拿到锁,返回0,否则,则失败


b. 释放

c. 初始化

/* Initialize MUTEX using attributes in *MUTEX_ATTR, or use the
default values if later is NULL. */
extern int pthread_mutex_init (pthread_mutex_t *__restrict __mutex,
__const pthread_mutexattr_t *__restrict
__mutex_attr) __THROW;


argp.h:60:# define __restrict restrict
argp.h:62:# define __restrict
regex.h:531:# define __restrict restrict
regex.h:533:# define __restrict
regex.h:540:# define __restrict_arr __restrict
regex.h:542:# define __restrict_arr

restrict关键字告诉编译器可以做一些优化的假定


# if defined __cplusplus && __GNUC_PREREQ (2,8)
# define __THROW>--throw ()
# else
# define __THROW
# endif


2. 读写锁
pthread_rwlock_t
a. 加读锁

/* Acquire read lock for RWLOCK. */
extern int pthread_rwlock_rdlock (pthread_rwlock_t *__rwlock) __THROW;


/* Try to acquire read lock for RWLOCK. */
extern int pthread_rwlock_tryrdlock (pthread_rwlock_t *__rwlock) __THROW;

/* Try to acquire read lock for RWLOCK or return after specfied time. */
extern int pthread_rwlock_timedrdlock (pthread_rwlock_t *__restrict __rwlock,
__const struct timespec *__restrict
__abstime) __THROW;

c. 加写锁

/* Acquire write lock for RWLOCK. */
extern int pthread_rwlock_wrlock (pthread_rwlock_t *__rwlock) __THROW;


/* Try to acquire write lock for RWLOCK. */
extern int pthread_rwlock_trywrlock (pthread_rwlock_t *__rwlock) __THROW;

/* Try to acquire write lock for RWLOCK or return after specfied time. */
extern int pthread_rwlock_timedwrlock (pthread_rwlock_t *__restrict __rwlock,
__const struct timespec *__restrict
__abstime) __THROW;

d. 释放锁

extern int pthread_rwlock_unlock (pthread_rwlock_t *__rwlock) __THROW;


e. 初始化

extern int pthread_rwlock_init (pthread_rwlock_t *__restrict __rwlock,
__const pthread_rwlockattr_t *__restrict
__attr) __THROW;


f.  销毁锁

/* Destroy read-write lock RWLOCK. */
extern int pthread_rwlock_destroy (pthread_rwlock_t *__rwlock) __THROW;


五 信号
 typedef void (*sighandler_t)(int);
 sighandler_t signal(int signum, sighandler_t handler);

The signal() system call installs a new signal handler for the signal with number signum. The signal handler is set to sighandler which may be a user specified function, or either SIG_IGN or SIG_DFL.
可以是用户指定函数,也可以是SIG_IGN或者SIG_DFL
Upon arrival of a signal with number signum the following happens. If the corresponding handler is set to SIG_IGN, then the signal is ignored. If
the handler is set to SIG_DFL, then the default action associated with the signal (see signal(7)) occurs. Finally, if the handler is set to a
function sighandler then first either the handler is reset to SIG_DFL or an implementation-dependent blocking of the signal is performed and next
sighandler is called with argument signum.
Using a signal handler function for a signal is called "catching the signal". The signals SIGKILL and SIGSTOP cannot be caught or ignored.

int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact);
The sigaction() system call is used to change the action taken by a process on receipt of a specific signal.
  signum specifies the signal and can be any valid signal except SIGKILL and SIGSTOP.
       If act is non-null, the new action for signal signum is installed from act.  If oldact is non-null, the previous action is saved in oldact.

  评论这张
 
阅读(138)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018