数据结构 实验4

栈与字符串

只有几个用链表 *** 作的简单题目

1. 实验目的（结出本次实验所涉及并要求掌握的知识点）

1. 掌握栈的结构及基本运算的实现方法。
2. 掌握用栈实现表达式计算的基本方法。
3. 掌握用栈进行问题求解的基本方法。
4. 理解掌握串的有关概念和运算实现。
5. 掌握快速模式匹配等串的典型算法。

2.实验内容（结出实验内容具体描述）

1.已知顺序栈的存储结构及基本 *** 作以定义，利用顺序栈结构，编写算法函数void Dto16(unsigned int m),实现十进制无符号整数m到十六进制的转换。

2.基于下面的链式存储结构，重新实现栈的基本 *** 作，并基于链式栈，改写上题的进位转换程序。

4.利用字符串采用带头结点的链式存储结构，请编写函数node* substring(node* s,int i,int len)函数，在字符串s中从第i个位置起取长度为len的字串，函数返回字串链表

5.字符串采用带头结点的链表存储，设计算法函数void delstring(linkstring s,int i,int len)在字符串s中删除从第i个位置开始，长度为len的字串。

6.字符串采用带头结点的链表存储，编写函数linkstring index(linkstring s,linkstring t),查找字串t在主串s中第一次出现的位置，若匹配不成功，则返回NULL。

3.算法描述及实验步骤（用适当的形式表达算法设计思想与算法实现步骤）

#include //实验1
#include 
#include 
#include 
using namespace std;
typedef struct node
{
    char data;
    struct node *next;
} node;

void Doto16(int m) //直接对16做除法，记录商及余数，倒序输出
{
    cout << "十进制数" << m << "对应的十六进制数:";
    int b;
    node *top = NULL;
    node *p;
    while (m)
    {
        b = m % 16;
        m /= 16;
        p = new node;
        if (b < 10)
            b = b + '0';
        else
            b = b - 10 + 'A';
        p->data = b;
        p->next = top;
        top = p;
    }
    while (top)
    {
        cout << setw(2) << top->data;
        top = top->next;
    }
    cout << endl;
}

int main()
{
    int n;
    cout << "请输入待转换的十进制数" << endl;
    cin >> n;
    Doto16(n);
    system("pause");
    return 0;
}

 

#include //实验2
#include 
#include 
#include 
using namespace std;
typedef struct node
{
    char data;
    struct node *next;
} node;

void Doto16(int m) //直接对16做除法，记录商及余数，倒序输出
{
    cout << "十进制数" << m << "对应的十六进制数:";
    int b;
    node *top = NULL;
    node *p;
    while (m)
    {
        b = m % 16;
        m /= 16;
        p = new node;
        if (b < 10)
            b = b + '0';
        else
            b = b - 10 + 'A';
        p->data = b;
        p->next = top;
        top = p;
    }
    while (top)
    {
        cout << setw(2) << top->data;
        top = top->next;
    }
    cout << endl;
}

int main()
{
    int n;
    cout << "请输入待转换的十进制数" << endl;
    cin >> n;
    Doto16(n);
    system("pause");
    return 0;
}

#include //实验4
#include 
#include 
#include 
#include 
using namespace std;
typedef struct node
{
    char data;
    struct node *next;
} node;

node *createstr()
{
    node *s = new node;
    s->next = NULL;
    node *p = NULL, *r = s;
    char ch;
    cout << "请输入#为结束符:";
    cin >> ch;
    while (ch != '#')
    {
        p = new node;
        p->data = ch;
        r->next = p;
        r = p;
        cin >> ch;
    }
    if (r)
        r->next = NULL;
    return s;
}

void output(node *s)
{
    node *p = s->next;
    if (!p)
    {
        cout << "空的" << endl;
        return;
    }
    while (p)
    {
        cout << setw(4) << p->data;
        p = p->next;
    }
    cout << endl;
}

void dellist(node *s)
{
    node *p = s;
    while (s)
    {
        s = s->next;
        free(p);
        p = s;
    }
}

node *substring(node *s, int pos, int len) //先找到pos位置，再创新链存节点
{
    node *p, *q, *r, *w;
    p = s->next;
    r = new node;
    w = r;
    int cnt = 1;
    while (p && cnt < pos)
    {
        p = p->next;
        cnt++;
    }
    if (!p)
    {
        cout << "pos太大了" << endl;
        return NULL;
    }
    else
    {
        cnt = 0;
        while (p && cnt < len)
        {
            cnt++;
            q = new node;
            q->data = p->data;
            w->next = q;
            w = q;
            p = p->next;
        }
    }
    if (cnt < len || !p)
    {
        cout << "len太大了" << endl;
        return NULL;
    }
    else
    {
        w->next = NULL;
        return r;
    }
}

int main()
{
    node *S;
    S = createstr();
    output(S);
    node *str1;
    int pos, len;
    cout << "请输入需获取子链的起始位置:";
    cin >> pos;
    cout << "请输入需获取子链的起始长度:";
    cin >> len;
    str1 = substring(S, pos, len);
    cout << "子链为:";
    output(str1);
    dellist(str1);
    dellist(S);
    system("pause");
    return 0;
}

#include //实验5
#include 
#include 
#include 
using namespace std;
typedef struct node
{
    char data;
    struct node *next;
} node;

node *createstr()
{
    node *s = new node;
    s->next = NULL;
    node *p, *r = s;
    char ch;
    cout << "请输入#为结束符:";
    cin >> ch;
    while (ch != '#')
    {
        p = new node;
        p->data = ch;
        r->next = p;
        r = p;
        cin >> ch;
    }
    if (r)
        r->next = NULL;
    return s;
}

void output(node *s)
{
    node *p = s->next;
    if (!p)
    {
        cout << "空的" << endl;
        return;
    }
    while (p)
    {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
}

void dellist(node *s)
{
    node *temp = s;
    node *p = s->next;
    s = s->next;
    free(temp);
    while (s)
    {
        s = s->next;
        free(p);
        p = s;
    }
}

void delstring(node *s, int pos, int len) //先找到pos位置，再利用其前驱节点改变指针指向，释放内存
{
    node *p = s->next;
    node *q = s;
    int cnt = 1;
    node *temp;
    while (p && cnt < pos)
    {
        q = q->next;
        p = p->next;
        cnt++;
    }
    if (!p)
    {
        cout << "pos开始位置太大了" << endl;
        return;
    }
    cnt = 1;
    while (p && cnt < len)
    {
        temp = p;
        p = p->next;
        free(temp);
        cnt++;
    }
    if (!p)
    {
        cout << "len太大了" << endl;
        q->next = NULL;
        return;
    }
    temp = p;
    q->next = p->next;
    free(temp);
    return;
}

int main()
{
    node *S;
    S = createstr();
    cout << "链表为:";
    output(S);
    int pos, len;
    cout << "请输入需删除子链的起始位置:";
    cin >> pos;
    cout << "请输入需删除子链的起始长度:";
    cin >> len;
    delstring(S, pos, len);
    cout << "新链为:";
    output(S);
    dellist(S);
    system("pause");
    return 0;
}

#include //实验6
#include 
#include 
#include 
using namespace std;
typedef struct node
{
    char data;
    struct node *next;
} node;

node *createstr()
{
    node *s = new node;
    s->next = NULL;
    node *p, *r = s;
    char ch;
    cout << "请输入#为结束符:";
    cin >> ch;
    while (ch != '#')
    {
        p = new node;
        p->data = ch;
        r->next = p;
        r = p;
        cin >> ch;
    }
    if (r)
        r->next = NULL;
    return s;
}

void output(node *s)
{
    node *p = s->next;
    if (!p)
    {
        cout << "空的" << endl;
        return;
    }
    while (p)
    {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
}

void dellist(node *s)
{
    node *temp = s;
    node *p = s->next;
    s = s->next;
    free(temp);
    while (s)
    {
        s = s->next;
        free(p);
        p = s;
    }
}

node *index(node *s, node *t) //朴素算法匹配,即遍历主串中每一个连续的子链，看是否与其匹配
{
    node *p = s->next;
    node *q = t->next;
    if (!q)
    {
        return NULL;
    }
    while (p)
    {
        int flag = 1;
        node *temp = q;
        node *temp1 = p;
        while (temp && temp1)
        {
            if (temp->data != temp1->data)
            {
                flag = 0;
                break;
            }
            temp = temp->next;
            temp1 = temp1->next;
        }
        if (flag == 1)
        {
            break;
            return p;
        }
        p = p->next;
    }
    return p;
}

int main()
{
    node *s, *t;
    s = createstr();
    t = createstr();
    cout << "主串链表为:";
    output(s);
    cout << "子串链表为:";
    output(t);
    node *p = index(s, t);
    if (!p)
        cout << "不匹配" << endl;
    else
        cout << "匹配成功,结点位置值为:" << p->data << endl;
    dellist(s);
    dellist(t);
    system("pause");
    return 0;
}

4.调试过程及运行结果（详细记录在调试过程中出现的问题及解决方法。记录实验执行的结果）

1.

2.

4.

5.

6.