C++实现链串的基本数据结构

#include 
using namespace std;


//此处规定链串结点大小均为1
typedef struct snode
{
	char data;//存放一个字符
	struct snode* next;//指向下一个结点的指针
}LinkStrNode;//链串的结点类型

void StrAssign(LinkStrNode*& s, char cstr[])//使用尾插法建立链串，同时一个字符串常量是以‘’标识结尾赋给链串s，即生成一个其值等于cstr的链串s
{   //尾插法顺序与数组一致
	int i;
	LinkStrNode* r, * p;//尾插法都是要使用两个指针的
	s = new LinkStrNode;//分配存储空间
	r = s;//r指向s
	for (i = 0; cstr[i] != ''; i++)
	{
		p = new LinkStrNode;
		p->data = cstr[i];
		r->next = p;
		r = p;
	}
	r->next = NULL;//尾结点的next域置为空
}

void DestroyStr(LinkStrNode*& s)//销毁串，过程与销毁带头结点的单链表运算的实现过程相同
{
	LinkStrNode* pre = s, * p = s->next;//都是需要使用两个指针来进行销毁串的操作
	while (p != NULL)//扫描链串，直到尾结点的next
	{
		delete pre;
		pre = p;  //两个结点同步后移一个结点
		p = pre->next;
	}
	delete pre;//释放最后一个结点，p指向NULL
}

void StrCopy(LinkStrNode*& s, LinkStrNode* t)//将链串t复制给链串s，采用尾插法进行复制，过程和串的建立类似
{
	LinkStrNode* p = t->next, * q, * r;//由于还要一个指针指向t，所以需要三个指针
	s = new LinkStrNode;//分配存储空间
	r = s;//r指向s
	while (p != NULL)//扫描链串t
	{
		q = new LinkStrNode;
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL;//尾结点的next域置为空
}

bool StrEqual(LinkStrNode* s, LinkStrNode* t)//判断两个链串是否相等
{
	LinkStrNode* p = s->next, * q = t->next;//使用两个指针分别指向两个链串
	while (p != NULL && q != NULL && p->data == q->data)
	{
		p = p->next;
		q = q->next;//两个链串长度相等，且对应位置的值相等
	}
	if (p == NULL && q == NULL)//当两个都指向空时，两个链串相等
		return true;
	else
		return false;
}

int StrLength(LinkStrNode* s)//求串长
{
	int i = 0;//用i来计算结点的个数,不包括其头结点
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		i++;
		p = p->next;
	}
	return i;
}

LinkStrNode* Concat(LinkStrNode* s, LinkStrNode* t)//两个串的连接，形成结果串，使用尾插法建立连接后的结果串str并且返回它
{
	LinkStrNode* str, * p = s->next, * q, * r;//str是需要返回的串，所以这里有四个指针
	str = new LinkStrNode;
	r = str;//指向结果串的尾结点
	while (p != NULL)
	{
		q = new LinkStrNode;
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	p = t->next;
	while (p != NULL)
	{
		q = new LinkStrNode;
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}//完全类似的过程
	r->next = NULL;
	return str;
}

LinkStrNode* SubStr(LinkStrNode* s, int i, int j)//返回链串中从第i个字符开始的由连续的j个字符组成的子串，当参数不正确时，返回一个空串
{   //采用尾插法建立结果链串str并返回它
	int k;
	LinkStrNode* str, * p = s->next, * q, * r;//尾插法一定要用两个指针，这里str是结果串，而p指向链串s
	str = new LinkStrNode;
	str->next = NULL;//置结果串为空串
	r = str;//r指向结果串的尾结点
	if (i <= 0 || i > StrLength(s) || j<0 || i + j - 1>StrLength(s))
		return str;//参数不正确时，返回空串
	for (k = 1; k < i; k++)
		p = p->next;//一直循环，直到让p指向s的第i个数据结点
	for (k = 1; k <= j; k++)
	{
		q = new LinkStrNode;
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL;
	return str;
}

LinkStrNode* InsStr(LinkStrNode* s, int i, LinkStrNode* t)//将链串s2插入链串s1的第i个位置上，得到一个结果串，当参数不正确的时候返回一个结果串
{
	int k;
	LinkStrNode* str, * p = s->next, * p1 = t->next, * q, * r;//这里为了方便起见，采用两个指针，分别指向链串s和链串t
	str = new LinkStrNode;
	str->next = NULL;
	r = str;//r指向结果串的尾结点
	if (i <= 0 || i > StrLength(s) + 1)//参数不正确时返回空串
		return str;
	for (k = 1; k < i; k++)
	{
		q = new LinkStrNode;
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	while (p1 != NULL)
	{
		q = new LinkStrNode;
		q->data = p1->data;
		r->next = q;
		r = q;
		p1 = p1->next;
	}
	while (p != NULL)
	{
		q = new LinkStrNode;
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL;
	return str;
}

LinkStrNode* DelStr(LinkStrNode* s, int i, int j)//在链串s中删去从第i个字符开始的长度为j的子串，得到一个结果串。当参数不正确时，返回一个空串
{
	int k;
	LinkStrNode* str, * p = s->next, * q, * r;
	str = new LinkStrNode;
	str->next = NULL;
	if (i <= 0 || i > StrLength(s) || j<0 || i + j - 1>StrLength(s))
		return str;//返回空串
	r = str;//r指向结果串的尾结点
	for (k = 1; k < i; k++)
	{
		q = new LinkStrNode;
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	for (k = 0; k < j; k++)
		p = p->next;//让p跳j个结点
	while (p != NULL)
	{
		q = new LinkStrNode;
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL;
	return str;
}

LinkStrNode* RepStr(LinkStrNode* s, int i, int j, LinkStrNode* t)//在链串s中将从第i字符开始的j个字符构成的子串用链串t替换，当参数不正确时，返回空串
{
	int k;
	LinkStrNode* str, * p = s->next, * p1 = t->next, * q, * r;//这里为了方便起见，采用两个指针，分别指向链串s和链串t
	str = new LinkStrNode;
	str->next = NULL;
	r = str;//r指向结果串的尾结点
	if (i <= 0 || i > StrLength(s) || j<0 || i + j - 1>StrLength(s))//参数不正确时返回空串
		return str;
	for (k = 1; k < i; k++)
	{
		q = new LinkStrNode;
		q->data = p->data;//这里没必要加上 q->next = NULL;
		r->next = q;
		r = q;
		p = p->next;
	}
	for (k = 0; k < j; k++)
		p = p->next;//让p跳j个结点
	while (p1 != NULL)
	{
		q = new LinkStrNode;
		q->data = p1->data;
		r->next = q;
		r = q;
		p1 = p1->next;
	}
	while (p != NULL)
	{
		q = new LinkStrNode;
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL;
	return str;
}

void DispStr(LinkStrNode* s)//输出串s的所有元素值
{
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}






 //以上的链串不管怎么样都不能运行，我真的十分疑惑


int main()
{
	
}