一些基本操作

#include 
#include 
typedef struct LNode{
	struct LNode *next;
	int data;
}LNode,*linkList;

//表尾建单链表 
linkList List_TailInsert(linkList &L){
	int x;
	L=(LNode*)malloc(sizeof(LNode));
	LNode *r,*s;//r为表尾指针
	scanf("%d",&x);
	while(x!=9999){
		s=(linkList)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		scanf("%d",&x);
	}
	r->next=NULL;
	return L; 
} 
//表头法
linkList List_HeadInsert(linkList &L){
	int x;//需要输入的数值
	LNode *s;//需要插入的结点 
	L=(linkList)malloc(sizeof(LNode));
	L->next=NULL;
	scanf("%d",&x);
	while(x!=9999){
		s=(linkList)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);
	} 
	return L; 
} 
//按照序号查找结点 
LNode * GetElem(linkList L,int i){
	int j=1;//计数，初始为1 
	LNode *p=L->next;//头节点赋值给p 
	if(i==0){
		return L;//如果i=0，则返回头节点 
	}
	if(i<1){
		return NULL;//如果i<0,则返回null 
	} 
	while(p&&jnext;
		j++;
	}//最后一次循环结束，p就指向第i个结点 
	return p;
} 

//按值查找表结点
LNode * LocationElem(linkList L,int e){
	LNode *p=L->next;
	while(p!=NULL&&p->data!=e){
		p=p->next;
	return p;
	}
} 

//插入结点
bool List_Insert(linkList &L,int i,int e){//在i的位置插入元素e 
	LNode *p=GetElem(L,i-1);//先找到第i个元素 
	if(p==NULL)//判断这个元素时候给空 
		return false;
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true; 
} 

//删除结点
bool ListDelete(linkList &L,int i,int &e){//删除表L中第i个位置元素，并返回删除元素
	LNode *p=GetElem(L,i-1);//p是第i-1个结点
	if(p==NULL)
		return false;
	LNode *q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);
	return true; 
}

int main(){
	linkList L;
	List_HeadInsert(L);//头插法建表
	linkList p;
	p=LocationElem(L,3); 
	
}
 

//队列
#include 
#include 
//队列只允许在一端进行插入，在另一端删除的线性操作
 //队头：需要删除的一端；队尾:允许插入的一端
 #define MaxSize 50
 #define ElemType int
 typedef struct {
 	ElemType data[MaxSize];//存放队列元素 
 	int front,rear;//队头指针和队尾指针 
 }SqQueue;

//队列初始化
void InitQueue(SqQueue &Q){
	Q.rear=Q.front=0;
} 
bool EnQueue(SqQueue &Q,ElemType x){
	if((Q.rear+1)%MaxSize==Q.rear)//rear指向最后一个结点，rear+1即指向第一个结点
		return false;
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%MaxSize;//%MaxSize保证了始终在0和rear-1里边循环 
	return true; 
}

//出队
bool DeQueue(SqQueue &Q,ElemType &s){
	if(Q.rear==Q.front)
		return false;//头指针和尾指针同时指向一个结点，即队列为空
	s=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
	return true; 
} 
//获得队头指针
bool GetHead(SqQueue Q,ElemType &s){
	if(Q.front==Q.rear)
		return false;
	s=Q.data[Q.front];
	return false;
} 

//获取队列元素个数：(rear+MaxSize-front)%MaxSize 

//队列，链式存储

#define Elemtype int
typedef struct linkNode{
	Elemtype data;
	struct linkNode *next;
}linkNode;//结点
typedef struct {
	linkNode *front ,*rear;
}linkQUeue; //头节点
//带头节点的初始化
 void InitQueue(linkQueue &Q){
 	Q.front=Q.rear=(linkNode*)malloc(sizeof(linkNode));
 	Q.front->next=null;
 } 
 
 //判空
 bool IsEmpty(linkQueue Q){
 	if(Q.front==Q.rear)//Q.front==NULL
 		return true;
 	else return false;
 } 
 //入队
 void EnQueue(linkQueue &Q,Elemtype x){
 	linkNode *s=(linkNode*)malloc(sizeof(Elemtype));
 	s->data=x;
 	s->next=NULL;//先把s的next赋空 
 	rear->next=s;//在把当前rear指向结点的next指向s 
 	Q.rear=s;//再把尾指针指向新节点s 
 } 
 
 //不带头节点的
 void InitQueue(linkQueue Q){
 	Q.front=Q.rear=NULL;
 } 
 //判空
 bool IsEmpty2(linkQueue Q){
 	if(Q.front==NULL)
 		return true;
 	else
 	return false;
 } 
 //不带头节点的要把插入第一个结点时特殊处理
//出队，带头节点的 
bool DeQueue (linkQueue &Q,Elemtype &x){
	if(Q.front==Q.rear)//判断是否为空结点 
		return false;
	linkNode *p=Q.front->next;//p指向front后一个结点 
	x=p->data;//x指向p的数据 
	Q.front->next=p->next; 
	if(Q.rear==p)//如果只有两个结点 
		Q.rear=Q.front;
	free(p);//释放p结点 
	return true;
}

//双端队列
 

#include 
#include 
//串
#define MaxLen 255
typedef struct{
	char ch[MaxLen];
	int length;
}SString;//顺序链表的存储 


typedef struct{
	char *ch;
	int length;
}HString;//动态链表的存储

//串的顺序存储有四种方式
//best方案：省略ch[0]然后在表尾添加一个变量表示length



typedef struct StringNode{
	char ch[4];
	struct StringNode *next; 
}StringNode,*String;



//普通的模式匹配算法
int Index(SString S,SString T){//S是父串，T是字串 
	int i=1,j=1;
	while(i<=S.length&&j<=T.length){
		if(S.ch[i]==T.ch[j]){
			++i;
			++j;
		}else{
			i=i+1-j+1;
			j=1;
		}
	}
	if(j>T.length)
		return i-T.length;
	else 
		return 0; 
} 

//KMP算法
//优化思路:主串指针不回溯，只有模式串指针回溯
int index(SString S,SString T,int next[]){
	int i=1,j=1;
	while(i<=S.length&&j<=T.length){
		if(j==0||S.ch[i]==T.ch[j]){
			++i;
			++j;
		}else{
			j=next[j];
		}
	}
	if(j>T.length)
		return i-T.length//如果找到了，返回开始的位置 
	else
		return 0; //如果没找到，返回0 
}