数据结构部分总结（c语言版）

这是一个

 

 

/*
此头文件适用于串
其中包括最基本的函数操作

ok代表成功
no代表失败
fs为特殊失败的标志

注：此头文件中的初始化使用'0'代表结束的
使用者可以根据需要自行改变，最后一
个函数为kmp算法，可以根据需要使用

 

*/

#include<stdio.h>
#include<stdlib.h>
#define ok 1
#define no 0
#define fs -1
typedef int nowname;
typedef struct strand
{
char *chars;
int length;
}strand;

/*
初始化、赋值函数
*/
nowname strassign(strand *t,char *chars){
//printf("%s",chars);
int sum ;
char *c;
for(sum = 0 , c = chars; *c != '0' ;c++,sum++)
{
//printf("1\n");
}
if(sum == 0)
{
t->chars = null;
}
else
{
t->chars = (char*)malloc(sizeof(char)*sum);
if(!t->chars)
{
printf("初始化申请空间失败！\n");
exit(no);
}
for (int i = 0; i < sum; i++)
{
t->chars[i] = chars[i];
//printf("%c\n",t->chars[i]);
}
t->length = sum;
}
return ok;
}

/*
对串进行输出
*/
void out(strand *s)
{
int num = 0;
while (num != s->length)
{
printf("%c",s->chars[num]);
num++;
}
printf("\n");
}

 

/*
长度输出函数
*/
nowname length(strand *t)
{
return t->length;
}

/*
字符串的连接函数
*/
void concat(strand *t,strand *s1,strand *s2)
{
//printf("1\n");
int j = 0;
t->length = s1->length+s2->length;
t->chars = (char*)malloc(sizeof(char)*t->length);
for (int i = 0,j = 0; i < s1->length; i++ , j++)
{
t->chars[j] = s1->chars[i];
//printf("%c\n",t->chars[j]);
}
j = s1->length;
for (int i = 0; i < s2->length; i++ , j++)
{
t->chars[j] = s2->chars[i];
//printf("%c\n",t->chars[j]);
}
}

/*
主串s的pos位置后长度为len的子串，用sub返回
*/
strand * substring(strand *sub,strand *s,nowname pos,nowname len)
{
if(pos<1 || pos > s->length || len < 0 || len > s->length-pos+1)
{
printf("输入的位置错误！\n");
exit(no);
}
for (int i = pos-1,j = 0; j < len; i++,j++)
{
sub->chars[j] = s->chars[i];
}
sub->length = len;
return sub;
}

/*
返回子串t在主串s的第pos个位置后首次出现的位置
*/

int index(strand *s,strand *t,int pos)
{
int num = pos-1;
int i = 0;
int sum = 0;
while ( num < s->length && i< t->length)
{
if(s->chars[num] == t->chars[i])
{
num++;
i++;
sum++;
}
else
{
i = 0;
num = num - sum + 1;
sum = 0;
}
//printf("%d\n",sum);
if(i == t->length)
{
return num-i+1;
}
}
return no;
}

 

/*
串之间的比较
0 两个字符串相同
1 t大于s
-1 s大于t
*/
nowname strcompare(strand *t,strand *s)
{
for(int i = 0 ; i < t->length && i < s->length ; i++)
{
if(t->chars[i] > s->chars[i])
return ok;
else if(t->chars[i] < t->chars[i])
return fs;
}
if(t->length == s->length)
return no;
if(t->length-s->length>0)
return ok;
else
return fs;
}

/*
清空串
*/
void nullstrand(strand *t)
{
if(t->chars)
{
free(t->chars);
t->length = 0;
}
}

 

int * next(strand *s,int *next)
{
/*
i = 1 a b c d e f s d
0 1 2 3 4 5 6 7
j = 0 a b c d e f s d
0 1 2 3 4 5 6 7
1.当j>0且next[i]!=next[j]时 让j=next[j-1]
2.当next[i]==next[j]时，让j++
3.每次执行完均执行next[i] = j;
*/
int j = 0, i = 1;
next[1] = 0;//初始化一下1
while (i<s->length)
{
while (j>0&&s->chars[i]!=s->chars[j])
{
j = next[j-1];
//printf("1\n");
}
if(s->chars[i] == s->chars[j])
{
j++;
//printf("2\n");
}
//printf("3\n");
next[i] = j;
i++;
}
//printf("4\n");
/*
右移,并且加1
*/
for(int i = s->length-1; i >=1 ; i--)
{
next[i] = next[i-1];
next[i]+=1;
}
next[0] = 0;
return next;
}