北邮22信通一枚~   

跟随课程进度每周更新数据结构与算法的代码和文章 

持续关注作者  解锁更多邮苑信通专属代码~

上一篇文章：

北邮22信通：（11）第三章 3.3队列的实现_青山如墨雨如画的博客-CSDN博客

下一篇文章：

北邮22信通：（13）第三章 3.4 串的实现 KMP算法_青山如墨雨如画的博客-CSDN博客

目录

一.顺序表下的串的实现

index函数：

代码部分及运行结果： 

二.单链表下的串的实现

index函数：

代码部分及运行结果：

*说明*

1.本代码基于书上第二章线性表和4.3节串的实现结合书写。

2.本篇文章分为两个部分，分别为用顺序表实现串和用单链表实现串；书上提供的代码是用顺序表实现串，小编自己给出了用单链表实现串的方法；

3.本代码对书上代码做了一个小小修改，template中只传入了一个参数class temp，更加精简。

4.顺序表VS单链表：顺序表的实现函数写起来比较精简，但是缺点是控制条件需要考虑仔细；

单链表的实现函数控制条件相对统一易于思考，但是写起来比较繁琐，并且和顺序表中部分代码重复。

*说明完毕*

一.顺序表下的串的实现

index函数：

template<class temp>
int seqlist<temp>::index(seqlist<temp>& t)
{int i = 1, j = 1;while (i <= this->getlength() && j <= t.getlength()){if (this->get(i) == t.get(j)){i++;j++;}else{i = i - j + 2;j = 1;}}if (j >= t.getlength())return i +1 - j;elsereturn -1;
}

代码部分及运行结果： 

#include <iostream>
using namespace std;
#define N 100
template<class temp>
class seqlist
{
private:temp data[N];int length;
public:seqlist() { length = 0; }seqlist(temp a[], int n);int getlength() { return length; }void printlist();void insert(int i, temp x);temp del(int i);temp get(int i);int locate(temp x);int index(seqlist& t);
};template <class temp>
seqlist<temp>::seqlist(temp a[], int n)
{if (n > N)throw "数组长度超过顺序表最大长度";for (int i = 0; i < n; i++)this->data[i] = a[i];this->length = n;
}template<class temp>
void seqlist<temp>::printlist()
{cout << "按序号依次遍历线性表中各个数据元素:" << endl;for (int i = 0; i < this->length; i++)this->data[i].print();cout << endl;
}template<class temp>
void seqlist<temp>::insert(int i, temp x)
{if (this->length >= N)throw"上溢异常";if (i < 1 || i >= this->length + 1)throw"位置异常";for (int j = this->length; j >= i; j--)this->data[j] = this->data[j - 1];this->data[i - 1] = x;this->length++;
}template<class temp>
temp seqlist<temp>::del(int i)
{if (this->length == 0)throw"下溢异常";if (i<1 || i>this->length)throw"位置异常";temp x = data[i - 1];for (int j = i; j < this->length; j++)data[j - 1] = data[j];this->length--;return x;
}template<class temp>
temp seqlist<temp>::get(int i)
{if (i<1 || i>this->length)throw"查找位置非法";return this->data[i - 1];
}template<class temp>
int seqlist<temp>::locate(temp x)
{for (int i = 0; i < this->length; i++)if (this->data[i] == x)return(i + 1);return 0;
}template<class temp>
int seqlist<temp>::index(seqlist<temp>& t)
{int i = 1, j = 1;while (i <= this->getlength() && j <= t.getlength()){if (this->get(i) == t.get(j)){i++;j++;}else{i = i - j + 2;j = 1;}}if (j >= t.getlength())return i +1 - j;elsereturn -1;
}int main()
{system("color 0A");char a[] = "hello world";char b[] = "good";char c[] = "ello";seqlist<char>seqa(a, strlen(a));seqlist<char>seqb(b, strlen(b));seqlist<char>seqc(c, strlen(c));cout << seqa.index(seqa) << endl;//1cout << seqa.index(seqb) << endl;//-1cout << seqa.index(seqc) << endl;//2return 0;
}

二.单链表下的串的实现

index函数：

注意看解释！

template<class temp>
int linklist<temp>::index(linklist<temp>&t)
{node<temp>* p = this->front->next;node<temp>* q = t.front->next;node<temp>* headp = this->front->next;//需要有一个主串标记点node<temp>* headq = t.front->next;//需要有一个模式串标记点int countp = 0, countq = 0;//和顺序表思路雷同while (p != NULL && q != NULL)//但是判断条件好简单{if (p->data == q->data){p = p->next; countp++;//不要怕麻烦因为不用动脑子q = q->next; countq++;}else{p = headp->next;//主串游标指针重新指向主串标记点的下一个节点headp = headp->next;//标记点也随之后移q = headq;//模式串游标指针重新指向模式串的标记点countp = countp - countq + 1;//和顺序表思路雷同countq = 0;}}if (q == NULL)return countp - countq + 1;//和顺序表思路雷同elsereturn -1;//和顺序表思路雷同
}

代码部分及运行结果：

#include<iostream>
using namespace std;
template<class temp>
struct node
{temp data;node<temp>* next;
};template <class temp>
class linklist
{
private:node<temp>* front;
public:linklist(){this->front = new node<temp>;this->front->next = nullptr;}linklist(temp a[], int n);~linklist();void printlist();int getlength() ;node<temp>* get(int i);int locate(temp x);void insert(int i, temp x);temp del(int i);int index(linklist<temp>&t);
};//头插法
template<class temp>
linklist<temp>::linklist(temp a[], int n)
{this->front = new node<temp>;this->front->next = NULL;for (int i = n - 1; i >= 0; i--){node<temp>* s = new node<temp>;s->data = a[i];s->next = this->front->next;this->front->next = s;}
}template<class temp>
linklist<temp>::~linklist()
{node<temp>* p = this->front;while (p != NULL){this->front = p;p = p->next;delete front;}
}template<class temp>
void linklist<temp>::printlist()
{node<temp>* p = this->front->next;while (p != NULL){p->data.print();//数据域中的print方法(需要用户自定义)p = p->next;}cout << endl;
}
template<class temp>
int linklist<temp>::getlength()
{node<temp>* p = this->front->next;int cnt = 0;while (p != NULL){cnt++;p = p->next;}return cnt;
}//按位置查找，返回地址
template<class temp>
node<temp>* linklist<temp>::get(int i)
{node<temp>* p = this->front->next;int j = 1;while (p != NULL && j != i){p = p->next;j++;}return p;
}//按值查找，返回位置
template<class temp>
int linklist<temp>::locate(temp x)
{node<temp>* p = this->front->next;int j = 1;while (p != NULL){if (p->data == x)return j;p = p->next;j++;}return -1;//如果没有找到，返回无效值
}template <class temp>
void linklist<temp>::insert(int i, temp x)
{node<temp>* p = this->front;if (i != 1)p = get(i - 1);//get(i - 1)表示要插入的位置的前一个结点地址if (p != NULL){node<temp>* s = new node<temp>;s->data = x;s->next = p->next;p->next = s;}else{cout << "插入位置错误:" << endl;exit(0);}
}template<class temp>
temp linklist<temp>::del(int i)
{node<temp>* p = this->front;if (i != 1)p = get(i - 1);node<temp>* q = p->next;p->next = q->next;temp x = q->data;delete q;return x;
}template<class temp>
int linklist<temp>::index(linklist<temp>&t)
{node<temp>* p = this->front->next;node<temp>* q = t.front->next;node<temp>* headp = this->front->next;node<temp>* headq = t.front->next;int countp = 0, countq = 0;while (p != NULL && q != NULL){if (p->data == q->data){p = p->next; countp++;q = q->next; countq++;}else{p = headp->next;headp = headp->next;q = headq;countp = countp - countq + 1;countq = 0;}}if (q == NULL)return countp - countq + 1;elsereturn -1;
}int main()
{system("color 0A");char a[] = "hello world";char b[] = "good";char c[] = "ello";linklist<char>linka(a, strlen(a));linklist<char>linkb(b, strlen(b));linklist<char>linkc(c, strlen(c));cout << linka.index(linka) << endl;//1cout << linka.index(linkb) << endl;//-1cout << linka.index(linkc) << endl;//2return 0;
}