Data_Structure总结
数据结构整理——数据结构基础
摘自数据结构PPT及作业 并且根据个人需要进行一些删改
Homework 1
字符串的赋值
定义的字符数组只能在定义阶段使用赋值符号char str[] = "China";，或者char *s,s="abcdefg";,在之后只能使用strcpy函数strcpy(str,"China"),并且要注意长度是否满足。
切记不能不能！！！
char str[100];
str[100]="China";即不能在赋值语句中通过赋值运算符”=”对字符数组整体赋值,并且数组之间也不能直接赋值，**a=b**。
数组在定义了之后就不能改变其地址，所以不能有a++,a=pa的操作，但是可以a+1，a[2]=*(a+2)。
删除字符串中特定字符操作
for(i=j=0;s[i]!='\0';i++){
if(s[i]!='char')//char 是要删除的字符，随需要更改
s[j++]=s[i];
}
s[j]='\0';/*一定要注意给'\0',否则这不是一个正确的字符串*/字符串数字转换
for (a = 0; ch[a] >= ’0’ && ch[a] <= ’9’; a++)
s = 10 * s + ch[a] - ’0’;区别指针数组和数组指针
指针数组：是数组，每一个元素是指针类型，定义形式 int/char/... *name[number],*(name[number])也可,例：
char *language[] = {"FORTRAN", "BASIC", "PASCAL", "JAVA", "C"};
int a[5], *num[5] = {&a[0], &a[1], &a[2], &a[3], &a[4]};
数组指针：是指针，指向数组类型，定义形式int/char/... (*name)[number],例：
{
int a[4][5];
int (*p)[5]=a;//括号里为二维数组的列数
}p是一个指针变量，它指向包含5个int元素的一维数组，此时p的增量以它所指向的一维数组长度为单位(相当于一行一行的移位);
p+i是一维数组a[i]的地址，即p+i=&a[i]；对该式两边作取内容运算（*）得*(p+i)=a[i]，由于二维数组中a[i]=&a[i][0]，则*(p+i)表示a[i][0]的地址，即*(p+i)=&a[i][0]；
*(p+2)+3表示a[2][3]地址（第一行为0行，第一列为0列），*（*(p+2)+3）表示a[2][3]的值。
函数指针
函数指针的调用
int (*fun)()=strlen;
//可以fun()
//也可以 (*fun)()十进制转十六进制
do{
h=n%16;
s[i++]=(h<=9)?h+'0':h+'A'-10;
}while((n/=16)!=0);最后记得把字符串颠倒过来
整型和字符串的相互转换
库函数
itoa(int n,char s,int Radix) Radix为要转换的进制
void itoa(int n,char s[])
{
int i,sign;
if((sign=n)<0)
n=-n;
i=0;
do{
s[i++]=n%10+'0';
}while((n/=10)>0);
if(sign<0){
s[i++]='-';
}
s[i]='\0';//一定要加字符串的结束标志
reverse(s);
}字符串转数字
n=atoi(char s)
strstr()的原型函数
O(m*n)的时间复杂度
函数index(char s[],char t[])检查字符串s中是否包含字符串t，若包含，则返回t在s中的开始位置(下标值)，否则返回-1。
int index(char s[],char t[])
{
int i,j,k;
for(i=0;s[i]!='\0';i++)
{
for(j=i,k=0;t[k]!='\0'&&s[j]==t[k];j++,k++);
if(t[k]=='\0')
return i;
}
return -1;
}
或者模糊处理（忽略大小写）
int index(char s[],char t[])
{
int i,j,k;
for(i=0;s[i]!='\0';i++)
{
for(j=i,k=0;t[k]!='\0'&&tolower(s[j])==tolower(t[k]);j++,k++);
if(t[k]=='\0')
return i;
}
return -1;
}
改进算法1：
int index(char s[ ], char t[ ])
{
int i, j, k,n,m;
n = strlen(s);
m = strlen(t);
for(i =0; n-i >= m; i++){//当剩余字符串的长度小于查找字符串的长度时，停止查找，节省时间
for(j=i,k=0;t[k]!='\0'&&s[j]==t[k]; j++,k++)
;// 注意分号！
if(t[k] == '\0')
return (i);
}
return ( -1);
}
改进算法2：
int index(char S[ ], char T[ ])
{
int i = 0, j=0;
while ( S[i]!='\0' && T[j]!='\0') {
if (S [i] == T[j] ) {
i++;
j++
}
else {
i = i-j +1;//i回退到上次匹配的起始位置的下一个位置
j = 0;//原字符串回到开头
}
}
if ( T[j] == '\0')
return i-j; //返回字符串的开始查找位置
else
return -1;
}KMP算法
O(m+n)的时间复杂度
源串称为主串，定义为S，当前匹配位置为i; 目标串称为子串，定义为T，当前匹配位置为j。当前匹配在找到不匹配的字符后，重新开始匹配时：
- 主串当前位置i不回溯，即不重置为上次匹配开始位置的一下位置；
- 子串当前位置j视情况回溯至起始串位置（0），或子串中某一位置。
int KMPindex(char S[ ], char T[ ])
{
int i = 0, j=0, *next;
next = (int *)malloc(sizeof(int)*(strlen(T)+1));//包含了'\0',所以要+1
getnext(T, next);
while ( S[i]!='\0' && T[j]!='\0') {
if (S [i] == T[j] ) {
i++;
j++ ;
}
else
(j == 0) ? i++ :( j = next[j]); //j回退到相应位置开始匹配，i值不变
}
free(next);
if ( T[j] == '\0') //匹配成功，返回匹配位置
return i-j;
else
return -1;
}
void getnext(char T[], int next[])
{
int i=0, j=-1;
next[0] = -1;
while(T[i]!='\0'){
if(j==-1 || T[i]==T[j]){ //i为后缀位置；j为前缀位置
i++;
j++;
next[i]=j;
}
else
j = next[j]; //若字符不同，则j值回溯
}
}reverse函数
倒置字符串
version1:
int first=0;
int end=strlen(s)-1;//一定要注意-1
while(first<end){
tmp=s[first];
s[first]=s[end];
s[end]=tmp;
first++,end--;
}
======================
version2:
for(i=0,j=strlen(str)-1;i<j;i++,j--)
{
k=str[i];
str[i]=str[j];
str[j]=k;
}inverp函数
将字符串反向输出但不改变原字符串
void inverp(char *a)
{
if ( *a=='\0')
return;
inverp(a+1);//运用了递归的思想，一直递归到结束再反向输出
printf("%c", *a );
}升序合并函数
将已按升序排好的两个字符串a和b中的字符按升序并归到字符串c中
以升序为例
version1 数组版本：
char a[]="acegikm";
char b[]="bdfhjlnpq";
char c[80],*p;
int i=0,j=0,k=0;
while(a[i]!='\0'&&b[j]!='\0')
{
if(a[i]<b[j]){c[k++]=a[i++];}
else{c[k++]=b[j++];}
}
c[k]='\0';//为strcat做准备
if(a[i]=='\0')//a字符串已经排列完，只剩下b字符串的剩下部分
p=b+j;//移位，也可以是p=&b[j];
else
p=a+i;//p=&a[i];
strcat(c,p);
====================
version2 链表版本：
/*lista,listb为两个升序链表的头指针*/
LinkList MERGELIST(LinkList lista,LinkList listb)
{
LinkList listc,p=lista,q=listb,r;
if(lista->data<=listb->data){
listc=lista;
r=lista;
p=lista->link;
}
else{
listc=listb;
r=listb;
q=listb->link;
}
while(p!=NULL&&q!=NULL){
if(p->data<=q->data){
r->next=p;
r=p;//r=r->pnext
p=p->next;
}
else{
r->next=q;
r=q;//r=r->pnext
q=q->next;
}
}
r->link=p?p:q;
return listc;
}Homework2
几个重要文件操作函数
in=fopen(FILEname,mode)
*fclose(FILE )
**fputs(char ,FILE )
**fgets(char ,MAXSIZE,FILE ) 错误时的返回值为NULL
*c=fgetc(FILE ) 返回值为读入字符,否则为EOF
*fputc(char ,FILE )
*fscanf(FILE ,Format,…)
*fprintf(FILE ,Format,…)
*freopen(FILEname,mode,FILE )
swap函数的定义和使用
原理：要对传入的指针的值进行交换，交换指针的指向(地址)不能使a,b的值交换，因为在函数里面指针变量是形参，地址交换是局部的，不会改变实参指针变量。
c语言实参变量和形参变量之间的数据传递是单向的的“值传递”方式。用指针变量做函数参数时同样要遵循这一规则。不可能通过执行调用函数来改变实参指针变量的值，但是可以改变实参指针变量所指变量的值。
void swap(int *m,int *n)
{
int t;
t=*m;
*m=*n;
*n=t;
}
int a=2,b=3;
swap(&a,&b);
//结果 a=3,b=2数组的传入是一对共享同一数据区的数组，即可以传入后改变数组中的元素。
函数中变量的传出
数组
如果在函数中定义了一个数组，无法传出
char *fun(){
char s[50];
...
return s;//返回值是空的 最后的返回出来s为s的首地址，没有返回数组的内容
}改进方法
1.使用malloc函数，这样它的空间不会被释放，可以传出，只有在free时才会释放空间
2.传入一个数组，作为保存的地方
struct 结构体定义
没有名字的结构体定义只能使用一次
自己不能嵌套自己，只能嵌套自己的指针
struct //少了结构名
{ int num;
float age;
} student;
struct student std1;//错误样例strcat的原型函数
！！！ strcat、strcpy不能追加自己的一部分如果有重合的情况下(内存空间不能有重合)
the behavior is undefined if the strings overlap .
[strcat和strcat_s的用法及其注意事项](The behavior is undefined if the strings overlap. )
void sstrcat(char *s, char *t)
{
int n;
n=strlen(s);
while( *(s+n)= *t )//其实隐含了一个判断 *t！='\0'
{
s++;
t++;
}
}结构体的元素获取
struct student
{
int age;
int num;
}std, *p;
p = &std;
对于非指针，用'.'运算符：std.age
对于指针，可以p->age或者(*p).age计算结构体的元素数目
#define Cnt (sizeof(struct xxx[])/sizeof(struct xxx))结构体数组的qsort函数
int cmp(const void *p,const void *q)
{
struct xxx *m=(struct xxx *)p;
struct xxx *n=(struct xxx *)q;
if(m->elment1<n->element1)
return -1;
if(m->elment1>n->element1)
return 1;
}！！！ ++ * ->的优先级和判断执行顺序
*和++具有相同的运算优先级，但是单目运算符，按照从右向左的顺序
->的优先级高于*和++的优先级
注意后++和前++，后++的值为改变之前的值
操作符的结合性
- 等号：从右向左
- 后++：整个语句执行完，再++
- 前++：先++，再执行语句中的其他操作 //注意和 ++的优先级区别*
*p++和*(p++)相同，先取指针p指向的值,再将指针p自增1；
(*p)++，先取指针p指向的值，再将该值自增1(数组的第一个元素自增1)；
*++p，先将指针p自增1(此时指向数组的第二个元素)，操作再取出该值；
++*p，先取出指针p指向的值，再将值自增1，返回值是自增之后的值；
++(*p)，先将指针指向的值自增1，并取出改变后的值；
Homework 3
Homework 4
Homework 5
数据结构基础
指针的使用
指针可以比大小，可以减（相减结果为指针所差的元素个数），但不可以相加
任何使用指针变量之前一定要给它开辟一个空间malloc或者置空NULL或者有所指向
对于一个指针，要先有指向，才能继续赋值
int x;
int *px;
*px=x;//这个是常见错误，因为这个px没有指向，是野指针！！为字符串开辟空间
p=(char *)malloc(strlen(s)+1);//一定要加1，为'\0'留位置便历一个数组
for(pi=&a[0],pj=&a[N-1];pi<=pj;pi++){
}线性表
概念：数据元素之间具有的逻辑关系为线性关系的数据元素集合称为线性表，数
据元素的个数n为线性表的长度,长度为0的线性表称为空表。构造原理：用一组地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过
数据元素的存储位置直接反映。所谓一个元素的地址是指该元素占用的k个(连续的)存储单元的第一个单元的地址。
性质：（1）同一性 （2）有穷性 （3）有序性
- 除了第一个元素与最后一个元素，序列中任何一个元素有且仅有一个直接前驱元素, 有且仅有一个直接后继元素。
- 数据元素之间的先后顺序为一对一的关系。
- 链表，队，栈，数组……
顺序表
顺序表的寻址
LOC(ai) = LOC(a1)+(i-1)*k顺序表的生成
#define MaxSize 100
ElemType A[MaxSize];
int n;元素查找
顺序查找O(n)
二分查找O(logn)
元素插入
在长度为n的顺序表list的第i个位置上插入一个新的数据元素item(在线性表的第i-1个数据元素与第i个数据元素之间插入一个由符号item表示的数据元素)
若插入成功，算法返回1，
否则，算法返回-1。一定要看明白题目所给的插入位置的明确定义，否则可能出问题
正常情况下需要做的工作：
(1) 将第i个元素至第n个元素依次后移一个位置；
(2) 将被插入元素插入表的第i个位置；
(3) 修改表的长度(表长增1)。(n++)
插入操作需要考虑的异常情况：
(1) 是否表满？n=MaxSize
(2) 插入位置是否合适？**(正常位置:0≤i≤n)**
核心代码
/* 假设N是顺序表的长度（元素个数），为一个全局变量*/
int insertElem(ElemType list[], int i, ElemType item )
{
int k;
if(N==MAXSIZE||i>N||i<0){
return -1;
}
else{
for(k=N-1;k>=i;k--){
list[k+1]=list[k]; /*将i及以后元素以此后移一位*/
}
list[i]=item;//填写i处元素
N++;//元素数量改变
return 1；
}
}元素删除
删除长度为n的顺序表list的某个数据元素(把线性表的第i个数据元素从线性表中去掉，使得长度为n 的线性表转换成长度为 n-1 的线性表)
若删除成功，算法返回1，
否则，算法返回-1。注意元素的下标是从0开始还是从1开始
正常情况下需要做的工作：
(1) 将删除元素的下一元素至第n个元素依次前移一个位置；
(2) 修改表的长度(表长减1)。**(n–)**
删除操作需要考虑的异常情况：
(1) 是否表空？**(n==0)?**
(2) 删除位置是否合适？**( 正常位置:0≤i≤n-1 )**
/* 假设N是表的长度（元素个数），为一个全局变量 */
int deleteElem( ElemType list[ ], int i )
{
int k;
if(N==0||i>N-1||i<0){
return -1;
}
else{
for(k=i;k<N-1;k++){
list[k]=list[k+1]; /*将i以后元素以此前移一位*/
}
N--;//元素数量改变
return 1；
}
}链表的操作
链表定义
struct node {
ElemType data;
struct node *link;
} ;
struct node *list, *p;类型定义
typedef struct node{//类型定义，将结点定义为LLN，方便操作
int data;
struct node *pnext;
}LLN;
LLN *p,*q;//直接使用LLN代替typedef struct node创建链表
注意是不是空表
一般链表
//以数据存入在数组中为例
LLN *createlist(LLN * first,int n,int *s){ /* 创建有n个结点的链表*/
LLN *p,*q;
int i;
if(n==0){
return NULL;//如果这是空表，要返回空
}
for(i=0;i<n;i++){
p=(LLN *)malloc(sizeof(LLN));
p->data=s[i];
p->pnext=NULL;//一定要注意开辟空间时就赋值NULL的习惯
if(first==NULL){
first=p=q;
}
else{
p->pnext=q;
p=p->pnext;
}
}
return first;//如果first时全局变量可以不用写返回，但是如果改指针了最好返回
}循环链表
LLN *createlist(LLN * first,int n,int *s){ /* 创建有n个结点的链表*/
LLN *p,*q;
int i;
for(i=0;i<n;i++){
p=(LLN *)malloc(sizeof(LLN));
p->data=s[i];
p->pnext=NULL;//一定要注意开辟空间时就赋值NULL的习惯
if(first==NULL){
first=p=q;
}
else{
p->pnext=q;
p=p->pnext;
}
if(i==n-1){
p->pnext=first;//就多了这一句
}
}
return first;//如果first时全局变量可以不用写返回，但是如果改指针了最好返回
}双向链表
获取链表的长度
单向链表
int getLength( LLN* list )
{
LLN* p; /* p为遍历链表结点的指针 */
int n=0; /* 链表的长度置初值0 */
for(p=list; p!=NULL; p=p->link)/* p依次指向链表的下一结点 */
n++; /* 对链表结点累计计数 */
return n; /* 返回链表的长度n */
}循环链表
int length( Nodeptr list )
{
Nodeptr p=list;
int n=0; /* 链表的长度置初值0 */
if(list == NULL) return 0;
do{
p=p->link;
n++;
}while(p!=list);
return n; /* 返回链表的长度n */
}双向链表
链表的插入
注意插入位置，表头/表中
注意返回值，如果改变了链表头就要返回
注意是不是空表
在结点p前插入一个结点，必须要知道该结点的前驱结点指针，否则无法插入，前驱结点
移动数组中其他元素的平均次数为n/2
核心代码
p=(LLN *)malloc(sizeof(LLN));
p->pnext=current->pnext;
current->pnext=p;
//时间复杂度O(1)算法
在线性链表中第n(n>0)个结点后面插入一个数据项为item的新结点
//没考虑在头部插入，没考虑表为空
void insertNode1( LLN * list, int n, ElemType item )
{
LLN * p=list, q;
int i;
for(i=1;i<=n-1;i++){ /* 寻找第i个结点 */
if(p->link==NULL)
break; /* 不存在第i个结点 */
p=p->link;
}
q=(Nodeptr)malloc(sizeof(Node));
q->data=item; /* 将item送新结点数据域 */
q->link = NULL;
q->link=p->link;
p->link=q; /* 将新结点插入到第i个结点之后 */
}考虑空表，考虑在头部插入，考虑返回指针
/* 设list是一个有序增序链表，将元素elem插入到相应位置上 */
Nodeptr insertNode(Nodeptr list, ElemType elem)
{
Nodeptr p,q, r;
r = (Nodeptr)malloc(sizeof(Node)); //创建一个数据项为elem的新结点
r->elem = elem; r->link = NULL;
if(list == NULL) /* list是一个空表 */
return r;
for(p=list; elem > p->elem && p != NULL; q = p, p = p->link) ;/* 找到插入位置 *//*要注意NULL空判断*/
;//即第一个比item大的地方
/*for(p=list;p!=NULL;q=p,p=p->next){
if(elem>p->elem){
break;
}
}*/
if( p == list){ /* 在头结点前插入 */
r->link = p;
return r;
}
else { /* 在结点q后插入一个结点 */
q->link = r;
r->link = p;
}
return list;
}链表的删除
一定要考虑下面特殊情况：1）链表为空；2）删除头结点。
在删除某个结点时，必须要知道该结点的前序结点指针，否则无法删除。
在寻找目标结点时要注意判断p->pnext是否为NULL
结点删除后一定要释放。但是不能使用free释放NULL。删除某个结点前，必须要事先保存指向该结点的指针，以便删除后能释放结点。
删除操作（函数）应返回头结点指针。
移动数组中其他元素的平均次数为(n-1)/2
核心代码
//q为前驱结点，p为当前结点
q->pnext=p->pnext;
free(p);
p=q->next;
q=p;//将q赋值，作为下一次的前驱结点算法
从非空线性链表中删除p指向的链结点，设p的直接前驱结点由r指出
LLN *deleteNode1( LLN* list, LLN* r, LLN* p )
{
if(p==list)
list=p->link; /* 删除链表的第一个链结点*/
else
r->link=p->link; /* 删除p指的链结点*/
free(p); /* 释放被删除的结点空间*/
return list
}从非空线性链表中删除p指向的链结点
LLN *deleteNode2( LLN* list, LLN* p ){
LLN *q,*r;
r=list;
if(p==list){
list=list->pnext;
free(p);//删除的为头结点
}
else{
for(r=list;r->pnext!=p&&r->pnext!=NULL;r=r->next);//定位到p的位置的前一个，并且要注意不能最后指向空结点
if(r->pnext!=NULL){//在不是空结点的情况下才进行考虑，否则free(NULL)会出现错误
r->pnext=p->next;
free(p);
}
}
return list;
}从非空线性链表中删除包含给定元素的结点
LLN *deleteNode( LLN* list, ElemType elem )
{
LLN * p, q; /*p指向要删除的结点，q为p的前一个结点*/
for(p=list; p!=NULL; q=p,p=p->link){
if(p->elem==elem ） /*找到要删除的链结点*/
break;
}
if(p==list) { /* 删除头结点*/
list = list->link;
free(p);
}
if(q->link != NULL) { /* 删除p指向的结点*/
q->link = p->link;
free(p);
}
return list;
}链表的翻转
Linklist *invert(Linklist *list) {
Linklist *p, *q, *r;
p = list;
q = NULL;
while (p != NULL) {
r = q;
q = p;
p = p->pnext;
q->pnext = r;
}
return q;//修改了头指针 要有返回值
} 栈的操作
FILO 先进后出
逻辑结构：线性结构，动态结构
特 点：操作仅允许在线性表一端或两端进行，是一般线性表操作的子集
可以用数组或链表模拟栈
栈的定义
#define MAXSIZE 1000
ElemType STACK[MAXSIZE];
int Top;//一般为全局变量比较方便使用栈的初始化
void initStack( )
{
Top= –1;//top为-1 作为栈为空的标志，栈顶元素下标
}判断为满和空
int isEmpty( )
{
return Top== –1;
}
int isFull( )
{
return Top==MAXSIZE–1;
}
// 为空返回1，不为空返回0；为满返回1，不为满返回0获取栈顶元素
ElemType gettop(ElemType *p)
{
if(!isempty())
return Stack[Top];
}进栈
void Push(ElemType s[], ElmeType item)
{
if( isFull() )
Error(“Full Stack!”);
else
s[++Top]=item;//先加一再赋值
}出栈
ElemType pop( ElemType s[ ])
{
if(isEmpty())
Error(“Empty Stack!”);
else
return s[Top--];
}多栈共享连续空间
入栈
void push( ElemType s[], int i, ElemType item)
{
if(top1==top2–1) /* 栈满 */
Error(“Full Stack!”);
else{
if(i==1) /* 插入第1个栈 */
STACK[++top1]=item;
else /* 插入第2个栈 */
STACK[––top2]=item;
return;
}
}出栈
EleType pop( ElemType s[ ], int i)
{
if(i==1)
if(top1==–1) //对第一个栈操作
Error(“Empty Stack1!”);
else
return s[top1––];
else
if(top2==MAXSIZE)//对第二个栈操作
Error(“Empty Stack2!”);
else
return s[top2++];
}栈的链式存储结构
链接栈就是用一个线性链表来实现一个栈结构, 同时设置一个指针变量( 这里
不妨仍用top表示)指出当前栈顶元素所在链结点的位置。栈为空时，有top=NULL。
链栈是一种特殊的链表，其结点的插入（进栈）和删除（出栈）操作始终在链表的头。
类型定义
struct node {
SElmeType data;
struct node *link;
};
typedef struct node *Nodeptr;
typedef struct node Node;
Nodeptr Top; //即为链表的头结点指针，定义为全局变量比较好，由于Top变量需要在多个函数间共享 栈初始化
void initStack()
{
Top=NULL;
}判断栈是否为空
int isEmpty( )
{
return Top==NULL;
}
/*不用判断满，因为空间是可以继续开辟的*/入栈
void push( ElemType item )
{ Nodeptr p;
if( (p=(Nodeptr)malloc(sizeof(Node)))==NULL )
Error(“No memory!”);
else{
p->data=item; /*将item送新结点数据域*/
p->link=Top; /*将新结点插在链表最前面*/
Top=p; /*修改栈顶指针的指向*/
}
}//这个代码将Top为空的情况也涵盖了出栈
ElemType pop( )
{ Nodeptr p;
ElemType item;
if ( isEmpty() )
Error(“Empty Stack!”); /* 栈中无元素*/
else{
p=Top; /* 暂时保存栈顶结点的地址*/
item=Top->data; /*保存被删栈顶的数据信息*/
Top=Top->link; /* 删除栈顶结点 */
free(p); /* 释放被删除结点*/
return item; /* 返回出栈元素*/
}
}队的操作
FIFO 先进先出
逻辑结构：线性结构，动态结构
是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。允许插入的一端称为队尾，队尾元素的位置由rear指出； 允许删除的一端称为队头, 队头元素的位置由front指出。
可以用数组或者链表模拟队
类型定义
#define MAXSIZE 1000
QElemType QUEUE[MAXSIZE];
int Front, Rear,Count;
//由于变量Front和Rear需要在多个操作（函数）间共享，为了方便操作，在此将其设为全局变量。Count为队列中元素个数。在实际应用中，由于队元素需要频繁的进出，单向结构很容易造成溢出，即rear到达数组尾，而实际队中元素并没有超出数组大小。因此，在实际应用中通常将队设计成一个循环队列，从而提高空间利用率。
初始化
void initQueue( )
{
Front = 0;
Rear = MAXSIZE-1;
Count = 0;
}判断队列是否为空或满
int isEmpty( )
{
return Count == 0;
}
nt isFull( )
{
return Count == MAXSIZE;
}
//用count判断减少麻烦进队
void enQueue(ElemType queue[ ], ElemType item)
{
if(isFull()) /* 队满，插入失败 */
Error(“Full queue!”);
else{
Rear = (Rear+1) % MAXSIZE;
queue[Rear]=item;
Count++;
/* 队未满，插入成功 */
}
}出队
ElemType deQueue(ElemType queue[ ])
{
ElemType e;
if(isEmpty())
Error(“Empty queue!”); /* 队空，删除失败 */
else{
e=queue[Front];
Count--; /* 队非空，删除成功 */
Front = (Front+1)%MAXSIZE;
return e;
}
}队列的链式存储结构
队列的链式存储结构是用一个线性链表表示一个队列，指针front与rear分别指向实际队头元素与实际队尾元素所在的链结点。
front与rear分别指向实际队头和队尾元素
类型定义
struct node {
ElmeType data;
struct node *link;
}
typedef struct node QNode; typedef struct node *QNodeptr;
//队头及队尾指针front和rear定义如下：
QNodeptr Front, Rear;
为了操作方便，通常将它们定义为全局变量 初始化队列
void initQueue()
{
Front=NULL;
Rear=NULL；//不管怎样一定要初始化
}判断队列是否为空
int isEmpty()
{
return Front==NULL;
}
//因为可以开空间，不用判断满进队
void enLQueue(ElemType item )
{ QNodeptr p;
if((p=(QNodeptr)malloc(sizeof(QNode))) ==NULL) /* 申请链结点 */
Error(“No memory! ”);
p->data=item;
p->link=NULL;
if(Front==NULL)
Front=p; /* 插入空队的情况 */
else
Rear->link=p;
Rear=p; /* 插入非空队的情况 */
}出队
ElemType deLQueue( )
{ QNodeptr p;
ElemType item;
if(isEmpty() )
Error(“Empty queue!”); /* 队为空，删除失败 */
else{
p=Front;
Front=Front->link;
item=p->data;
free(p);
return item; /* 队非空，删除成功 */
}
}销毁一个队
void destroyLQueue()
{
while(Front != NULL){ /* 队非空时 */
Rear=Front->link;
free(Front); /* 释放一个结点空间 */
Front=Rear;
}
}栈的小问题
设有一顺序栈S，n个元素 依次进栈，问这n个元素的任意排列都可以对应某一个可能的出栈顺序吗?
不同的出栈序列个数总共有多少？（与n相关）
卡特兰数
h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
or
h(n)=C(2n,n) - C(2n,n-1) (n=0,1,2,...)2个堆栈串联的情况呢？（元素不能反向运动）多个栈呢？
树
查找
顺序查找
前提要求是有序排列,查找成功返回1，否则返回-1。
连续组织方式（顺序组织方式）
直接查找
int search(keytype key[ ],int n,keytype k)
{
int i;
for(i=0;i<n; i++)
if(key[i]==k)
return i;
return -1;
}二分查找
//以递增的数数组为例
int bsearch(int item, int array[ ], int len)//对于数组需要传入数组长度
{
int low=0, high=len-1, mid;
while(low <= high){ //注意一定是小于等于<=
mid = (high + low) / 2;
if(( item < array[mid])
high = mid – 1;
else if ( item > array[mid])
low = mid + 1;
else
return (mid);
}
return -1;
//如果没有找到，需要插入的情况
int bsearch(int item, int array[ ], int len)
{
int low=0, high=len-1, mid;
while(low <= high){
mid = (high + low) / 2;
if(( item < array[mid])
high = mid – 1;
else if ( item > array[mid])
low = mid + 1;
else
return (mid);
}
return low;//对于升序排列的插入返回low作为插入点插值查找
Mid = low + ((key - data[low]) / (data[high] - data[low])) * (high - low)
其中Key是要查找的键值，data[high],data[low]是剩余待查找记录中的最大值和最小值，假设数据项为n，其插值查找法的步骤如下：
- 将记录从小到大的顺序给于1，2，3，…，n的编号
- 令low=1，high=n
- 当low<high时，重复执行步骤4和步骤5
- 令Mid=low+(key - data[low]) / (data[high] - data[low]) * (high - low)
- 若key<keyMid且high≠Mid-1，则令high=Mid-1
- 若key=keyMid，表示成功查找到键值的位置
- 若key>keyMid且low≠Mid+1，则令low=Mid+1
斐波那契查找
链接组织方式
适合于动态查找表，但查找效率低
索引查找
散列查找（Hash）
通过建立记录的关键字与记录的存储位置之间的关系实现快速查找的方法
$$
A = H(k)
$$
其中，k 为记录的关键字，H(k)称为散列函数，或哈希(Hash)函数，或杂凑函数。函数值A为k对应的记录在查找表中位置。
对于不同的关键字ki与kj，经过散列得到相同的散列地址，即有
$$
H(ki) = H(kj)
$$
这种现象称为散列冲突。
建立原则：
- 散列函数的定义域必须包括将要存储的全部关键字；若散列表允许有m个位置时，则函数的值域为[0 .. m–1](地址空间)。
- 利用散列函数计算出来的地址应能尽可能均匀分布在整个地址空间中。
- 散列函数应该尽可能简单，应该在较短的时间内计算出结果。
建立方法：
直接定址法
$$
H(k)=ak+b
$$除留余数法(以整数位关键字)
$$
H(k) = k MOD p
$$
其中，若m为地址范围大小(或称表长)，则p可为小于等于m的素数(素数对于数据的平均分布比较好)。
处理哈希冲突
开放地址法
所谓开放地址法是在散列表中的“空”地址向处理冲突开放。即当散列表未满时，处理冲突需要的“下一个”
地址在该散列表中解决。
其他代码或者算法
逆波兰表达式的计算顺序
中缀转后缀
规则：从左至右遍历中缀表达式中每个数字和符号：
- 若是数字直接输出，即成为后缀表达式的一部分；
若是符号：- 若是)，则将栈中元素弹出并输出，直到遇到“(”， “(”弹出但不输出（左、右括号都不输出，右括号不如入栈）；
- 若是“（“，则直接入栈；
- 若是+,- , *, \ 等符号，则从栈中弹出并输出优先级不低于(高于或等于)当前的符号(不包括左括号”（“)，直到遇到一个优先级低的符号；然后将当前符号压入栈中。
（优先级+，-最低，*，/次之，“(”最高）- 遍历结束，将栈中所有元素依次弹出，直到栈为空。
逆波兰表达式作用：
- 消除括号
- 将嵌入在表达式各处的无序优先级关系转换为从左到右的顺序形式
后缀算值
规则：从左至右遍历后缀表达式中每个数字和符号：
- 若是数字直接进栈；
- 若是运算符（+，-，*，/），则从栈中弹出两个元素进行计算（注意：后弹出的是左运算数），并将计算结果进栈。
- 遍历结束，将计算结果从栈中弹出（栈中应只有一个元素，否则表达式有错）。
len = strlen(exp)，flag=0;//作为是否读入数字的标志,exp为读入的后缀表达式串
for (i = 0; i < len - 1; i++) {
if (exp[i] >= '0' && exp[i] <= '9') {
num = 10 * num + exp[i] - '0';
flag = 1;
} else {
if (flag) {//如果为1，说明有数字读入
push1(num);
num = 0;
flag = 0;
}
if (exp[i] != '.') {//数字间隔符，不是间隔符就是运算符
n2 = pop1();
n1 = pop1();
push1(op(n1, exp[i], n2));
}
}
}
printf("%d", pop1());后缀转表达式树
原理：从下往上建立表达式树
规则：从左往右遍历后缀表达式中每个数字和符号
- 如果是操作数，则建立一个单节点树并将指向该节点的指针推入栈中；（栈中元素为树节点的指针）
- 如果是运算符，就从栈中弹出指向两棵树T1和T2的指针（T1先弹出）并形成一棵新树，树根为该运算符，它的左、右子树分别指向T2和T1，然后将新树的指针压入栈中。
- 重复步骤1，直到后缀表达式处理完。
typedef struct tree { //树的结构体
int num;
char op;
int flag;//表示是符号还是数字
struct tree *left, *right;
} expresstree;
expresstree *stack[1000];//表达式树构建时存放指针的地方
int top1 = -1;
expresstree *root = NULL;
for (i = 0; i < cnt; i++) {
if (posopr[i].flag == 0) {//标志
expresstree *signalnode = (expresstree *)malloc(sizeof(expresstree));
signalnode->left = NULL;
signalnode->right = NULL;
signalnode->flag = 0;
signalnode->num = posopr[i].num;
push1(signalnode);//数字直接入栈
} else {//如果是符号
expresstree *signalnode1 = (expresstree *)malloc(sizeof(expresstree));
signalnode1->left = NULL;
signalnode1->right = NULL;
signalnode1->op = posopr[i].op;
signalnode1->flag = 1;
expresstree *p1 = pop1();
expresstree *p2 = pop1();//弹出两个符号作为左右子树
signalnode1->left = p2;
signalnode1->right = p1;
root = signalnode1;
push1(signalnode1);//最后根节点入栈
}
}//生成表达式树表达式树算值
原理：后序遍历
- 如果左节点是符号，遍历左节点
- 如果右节点是符号，遍历右节点
- 如果该结点是符号且左右子树都是数字，进行运算，并释放子树空间，将该节点变为数字类型，并存入运算结果
void posorder(expresstree *p) {
if (p->left->flag == 1) {
posorder(p->left);
}
if (p->right->flag == 1) {
posorder(p->right);
}
if (p->flag == 1 && p->right->flag == 0 && p->right->flag == 0) {
p->num = op(p->left->num, p->op, p->right->num);
p->flag = 0;
free(p->left);
free(p->right);
}
}//以后序遍历表达式树实现计算枚举(enum)
相当于给每一个元素赋值 给一个字符串赋予一个值
enum color {red, yellow, green, black, white, grey};
###结果 red=0,yellow=1,green=2,black=3,white=4,grey=5;对齐输出
左对齐 ：%-[][lenth][type] 注意有负号
右对齐： % [][lenth][type]
动态开辟二维数组空间
char **lines = (char **)malloc(sizeof(char *)*n);
for (i = 0; i < n; i++) {
lines[i] = (char *)malloc(sizeof(char) * 100);
}//开辟二维数组空间显示文件的最后n行
读入命令，简便版本和复杂版本
实现操作
可以通过循环链表或者数组实现
数组版本
int main() {
FILE *in, *out;
int linecnt = 0, n, i;//记录文件行数和要输入的行数
char line[100];//每次读入一行
scanf("%d", &n);
char **lines = (char **)malloc(sizeof(char *)*n);
for (i = 0; i < n; i++) {
lines[i] = (char *)malloc(sizeof(char) * 100);
}//开辟二维数组空间
in = fopen("in.txt", "r");
out = fopen("out.txt", "w");
i = 0;
while (fgets(line, 100, in) != NULL) {
linecnt++;
strcpy(lines[i], line);
i = (i + 1) % n;//循环的过程
}
int start = i;//i++了之后到达最后一个位置的下一位，即回到了最后n行的开头
if (linecnt < n) {//防止要输出的行数多于文件本身的行数
for (i = 0; i < linecnt; i++) {
fputs(lines[i], out);
}
} else {
for (i = 0; i < n; i++) {
fputs(lines[start], out);
start = (start + 1) % n;
}
}
fclose(in);
fclose(out);
}循环链表版本
int main(){
//创建循环链表
if((fp = fopen(filename, "r")) == NULL){
printf(" Cann't open file: %s !\n", filename);
return (-1);
}
first = ptr = (struct Node *)malloc(sizeof ( struct Node));
first->line = NULL;// 一定要有置空操作，为了对付没有填满的情况
for(i=1; i<n; i++){
ptr->next = (struct Node *)malloc(sizeof ( struct Node));
ptr = ptr->next;
ptr->line = NULL;
}
ptr->next = first;
ptr = first;
while(fgets(curline, MAXLEN, fp) != NULL){
if(ptr->line != NULL) /*链表已经满了，需要释放掉不需要的行*/
free(ptr->line);
ptr->line = (char *) malloc ( strlen(curline)+1);
strcpy(ptr->line, curline);
ptr = ptr->next;
}
for(i=0; i<n; i++) {
if(ptr->line != NULL)//防止要输出的行数多于文件本身的行数
printf("%s",ptr->line);
ptr = ptr->next;
}
fclose(fp);
return 0;
}折半查找
有序数字的折半查找
找到返回位置，没找到返回-1
//以递增数组为例
int bsearch(int item, int array[ ], int len)
{
int low=0, high=len-1, mid;
while(low <= high){
mid = (high + low) / 2;
if(( item < array[mid])
high = mid – 1;
else if ( item > array[mid])
low = mid + 1;
else
return (mid);
}
return -1;有序字符串的折半查找
找到返回位置或者字符串计数值加一，否则插入字符串
/*以升序为例*/
int binarysearch(char words[][50], int n, char *str) {//二分查找 找到返回位置 不在返回-1
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (strcmp(str, words[mid]) < 0) {
high = mid - 1;
} else if (strcmp(str, words[mid]) > 0) {
low = mid + 1;
} else
return mid;
}
return -1;
}对于字符串的排序还可以是先插入再排序
Bubble sort
void sortinform(inform *p, int n) {
int i, j;
inform tmp;
for (i = 1; i < n; i++) {
for (j = 0; j < n - i ; j++) {
if (strcmp(p[j].name, p[j + 1].name) > 0) {
tmp = p[j];
p[j] = p[j + 1];
p[j + 1] = tmp;
}
}
}
}
void bubbleSort(keytype k[ ],int n)
{ int i, j, flag=1;
keytype temp;
for(i=n-1; i>0 && flag==1; i--){
flag=0; /* 每趟排序前标志flag置0 */
for(j=0;j<i;j++)
if(k[j]>k[j+1]){
temp=k[j];
k[j]=k[j+1];
k[j+1]=temp; /* 交换两个元素的位置 */
flag=1; /* 标志flag置1 */
}
}
}简单选择排序
void sortbyName(struct Student array[], int n)
{
int i, j;
struct Student tmp;
for(i=0; i<n; i++)
for(j=i; j<n; j++){
if(strcmp(array[i].name,array[j].name)>0){
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
void sortbyScore(struct Student array[], int n)
{
int i, j;
struct Student tmp;
for(i=0; i<n; i++){
for(j=i; j<n; j++){
if(array[i].score < array[j].score){
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}qsort
struct students{
char *s;
int score;
}info[n];
int cmp(const void *p,const void *q)
{
struct students *m,*n;
m=(struct students *)p;
n=(struct students *)q;
if(m->score<n->score){
return -1;
}
else if(m->score>n->score){
return 1;
}
else{
if(strcmp(m->s,n->s)<0)
rerurn -1;
if(strcmp(m->s,n->s)>0)
return 1;
}
}
qsort(info,n,sizeof(struct student),cmp);高精度
高精度加法
栈实现(两个数据栈，一个结果栈)
char stack2[10000];
char stack3[10000];
int top1 = -1, top2 = -1, top3 = -1;
int isempty1() {
return top1 == -1;
}
int isempty2() {
return top2 == -1;
}
void pushresult(char n) {
top3++;
stack3[top3] = n;
}
char pop1() {
char end = stack1[top1];
top1--;
return end;
}
char pop2() {
char end = stack2[top2];
top2--;
return end;
}
int main() {
int c, d1, d2, d3, carry = 0;
while (scanf("%c", &c) != EOF && c != '\n') {
top1++;
stack1[top1] = c;
}
while (scanf("%c", &c) != EOF && c != '\n') {
top2++;
stack2[top2] = c;
}
while (!isempty1() || !isempty2()) {
if (!isempty1()) {
d1 = pop1() - '0';
} else {
d1 = 0;
}
if (!isempty2()) {
d2 = pop2() - '0';
} else {
d2 = 0;
}
d3 = (d1 + d2 + carry) % 10;
carry = (d1 + d2 + carry) / 10;
pushresult(d3 + '0');
}
while (top3 > -1) {
printf("%c", stack3[top3]);
top3--;
}
}单词的读入(getword)
文件读取版本
int getword(FILE *fp, char *word) {
int i = 0;
int temp; //getc是返回int
while ((temp = fgetc(fp)) != EOF) {
if (temp == 12) {
return EOF;//将换页符表示为一个文件的结束
}
if ((temp >= 'a' && temp <= 'z' ) || (temp >= 'A' && temp <= 'Z')) {
word[i] = tolower1(temp);//模糊化，不区分大小写
i++;
} else if (i > 0) { //说明i中已经至少有一个字符
word[i] = '\0';
return 0;
}
}
return EOF;
}标准输入读取版本
/*来源 标识符的识别*/
int getword(char *word) {
int i = 0;
int temp;//getchar返回int类型
while ((temp = getchar()) != '\n') {
if ((temp >= 'a' && temp <= 'z' ) || (temp >= 'A' && temp <= 'Z') || temp == '_' || (temp >= '0' && temp <= '9'&& i > 0)) {//根据题目要求不同作变化
word[i] = temp;
i++;
} else if (i > 0) { //说明i中已经至少有一个字符
word[i] = '\0';
return 0;
}
}
return EOF;
}