字符串的链式存储和操作

#include <stdio.h>
#include <stdlib.h>

typedef struct linkNode
{
    char data;
    struct linkNode *next;
}node, *linkStr;

// 1.初始化字符串
void init(linkStr *s)
{
    *s = NULL;
}

// 2.输出字符串
void display(linkStr s)
{
    if(!s)
    {
        printf("字符串为空！\n");
        return;
    }
    while (s)
    {
        printf("%c",s->data);
        s = s->next;
    }
    printf("\n");
}

// 3.根据用户输入构造字符串
void strCreate(linkStr *s)
{
    char c;
    node *p, *r = *s;
    printf("请输入字符，回车表示结束输入...\n");
    while ((c = getchar()) != '\n')
    {
        p = (node*) malloc(sizeof(node));
        p->data = c;
        if(!*s)
            *s = p;
        else
            r->next = p;
        r = p;
    }
    if(r) r->next = NULL;
}

// 4.查找第i个字符
node *find(linkStr s, int i)
{
    if(i < 1 || !s)
        return NULL;
    if(i == 1)
        return s;
    int j = 1;
    while (s && i!=j)
    {
        s = s->next;
        j++;
    }
    return s;
}

// 5.将字符串t插入字符串s中第i个字符开始的位置上
void strInsert(linkStr *s, int i, linkStr t)
{
    if(!t)
        return;
    if(i < 1)
    {
        printf("非法的插入操作！\n");
        return;
    }
    node *p = find(*s,i-1),*r = t;
    while (r->next)
        r = r->next;
    if(i == 1)
    {
        r->next = *s;
        *s = t;
        return;
    }
    if(p)
    {
        r->next = p->next;
        p->next = t;
        // t还需删除
    } else
        printf("非法的插入操作！\n");
}

// 6.将串s从第i个字符起删除len个长度的子串
void strDel(linkStr *s, int i, int len)
{
    if(!*s)
    {
        printf("字符串为空，无法删除！\n");
        return;
    }
    if(i < 1 || len < 1)
    {
        printf("非法的删除操作！\n");
        return;
    }
    node *pre = *s,*r,*q;
    int j = 1;
    while (pre && j < i-1) // 找到删除的前驱结点
    {
        pre = pre->next;
        j++;
    }
    j = 0;
    r = pre;
    while (r && j < len) // 找到删除的最后一个结点
    {
        j++;
        if(pre == *s && j == 1)
            continue;
        r = r->next;
    }
    if(r)
    {
        if(pre == *s)
        {
            q = pre;
            *s = r->next;
            free(q);
        } else
        {
            pre->next = r->next;
            pre = pre->next;
            while (pre != r->next)
            {
                q = pre;
                free(q);
                pre = pre->next;
            }
        }
    } else
        printf("非法的删除操作！\n");
}

// 7.字符串的连接运算
void strConcat(linkStr *s,linkStr t)
{
    node *p = *s;
    if(!t) // t为空串时
        return;
    if(!*s) // s为空串时
        *s = t;
    else
    {
        while (p->next) // 找到s的尾结点
            p = p->next;
        p->next = t;
    }
}

// 8.截取子串
linkStr substring(linkStr s, int i, int len)
{
    linkStr t; // 字串
    init(&t);
    if(i < 1 || len < 1)
    {
        printf("非法的截取操作！\n");
        return t;
    }
    node *p = s,*q,*r,*n; // p、q为主串工作指针，r指向字串尾指针
    int j = 1;
    while (p && j < i) // 寻找第i个结点
    {
        p = p->next;
        j++;
    }
    q = p,j = 1;
    while (q && j < len) // 寻找第i+len-1个结点
    {
        j++;
        q = q->next;
    }
    if(!q) // 表示超过s的边界
    {
        printf("非法的截取操作！\n");
        return t;
    }
    while (p != q->next)
    {
        n = (node*) malloc(sizeof(node));
        n->data = p->data;
        if(!t) // 处理首结点
            t = n;
        else
            r->next = n;
        r = n; // 更新尾指针
        p = p->next;
    }
    r->next = NULL; // 处理字串尾部
    return t;
}

int main()
{
    linkStr str,t,s;
    init(&str);
    init(&t);
    strCreate(&str);
    printf("字符串str: ");
    display(str);
    strCreate(&t);
    printf("字符串t: ");
    display(t);
    int i = 1,len = 5;
    printf("将字符t插到str中的第%d个字符开始的位置上\n",i);
    strInsert(&str,i,t);
    printf("字符串str: ");
    display(str);
    printf("将串str从第%d个字符起删除%d个长度的子串\n",i,len);
    strDel(&str,i,len);
    printf("字符串str: ");
    display(str);
    init(&t);
    strCreate(&t);
    printf("字符串t: ");
    display(t);
    printf("把字符串t拼接在str后\n");
    strConcat(&str,t);
    printf("字符串str: ");
    display(str);
    s = substring(str,i,len);
    printf("字符串str从第%d个字符开始长度为%d的子串:\n",i,len);
    display(s);
    return 0;
}