学习贺利坚老师链串算法库
本人详细解析博客
版本更新日志
V1.0 : 结合顺序串操作, 使用链串进行优化, 此次链串, 空间将不受限制, 只写了最基本的操作, 相当于 单链表的拓展实践, 本版本仍然存在的问题是, 可能没有对内存进行优化, 后续需要结合具体单片机编译器, 进行优化处理.
v2.0补丁: 在每个malloc后面,加入分配空间函数,防止分配失败,导致内存泄露
并且在合法性判断哪里, 加入释放函数.
后续优化: 在时候函数库时, 数据结束后,记得释放 占用的空间.
函数库调用注意事项:
本文分成两个版本, V1.0是简洁版本, 可用于测试, 第二个优化了内存, 可能代码有点冗余 , 在开发中, 需要根据自己使用的编译器, 进行测试, 比如在c语言单片机中, 无法使用指针地址, 那就要换一种表达方式传参了.
V1.0
函数功能
//(1)将一个字符串数组赋值给链串
void Assignment_Chain_string(Chain_string *&New_String, char Assign_array[]);
//(2) 复制一个链串,到另一个链串
void Copy_Chain_String(Chain_string *&accept_string, Chain_string *copy_string);
//(3)判断两个串是否相等
bool Equal_Chain_String(Chain_string *judge_string1, Chain_string *judge_string2);
//(4)求链串串长
int Length_Chain_String(Chain_string *measure_string);
//(5)链串连接
Chain_string *Connect_Chain_String(Chain_string *link1, Chain_string *link2);
//(6)求链串的子串(从begin_loation开始的number个字符)
Chain_string *Get_Chain_Substring(Chain_string *Mother_string, int begin_loation, int number);
//(7)链串中插入串(从从begin_loation开始插入字符串,然后组合成新的串)
Chain_string *Insert_Chain_String(Chain_string *old_string, int begin_loation,Chain_string *insert_string);
//(8)删除链串(从begin 开始的number个字符)
Chain_string *Delete_Chain_String(Chain_string *old_string, int begin_loation,int number);
//(9)链串替换(从begin 开始的number个字符)
Chain_string *Replace_Chain_String(Chain_string *old_string, int begin_loation,int number,Chain_string *replace_string);
//(10)输出展示串
void Display_Chain_String(Chain_string *show_String);链串头函数
Chain_string.h#ifndef _CHAIN_STRING_H_INCLUDED
#define _CHAIN_STRING_H_INCLUDED
typedef struct Chain_string
{
char data;
struct Chain_string *next;
}Chain_string;
//(1)将一个字符串数组赋值给链串
void Assignment_Chain_string(Chain_string *&New_String, char Assign_array[]);
//(2) 复制一个链串,到另一个链串
void Copy_Chain_String(Chain_string *&accept_string, Chain_string *copy_string);
//(3)判断两个串是否相等
bool Equal_Chain_String(Chain_string *judge_string1, Chain_string *judge_string2);
//(4)求链串串长
int Length_Chain_String(Chain_string *measure_string);
//(5)链串连接
Chain_string *Connect_Chain_String(Chain_string *link1, Chain_string *link2);
//(6)求链串的子串(从begin_loation开始的number个字符)
Chain_string *Get_Chain_Substring(Chain_string *Mother_string, int begin_loation, int number);
//(7)链串中插入串(从从begin_loation开始插入字符串,然后组合成新的串)
Chain_string *Insert_Chain_String(Chain_string *old_string, int begin_loation,Chain_string *insert_string);
//(8)删除链串(从begin 开始的number个字符)
Chain_string *Delete_Chain_String(Chain_string *old_string, int begin_loation,int number);
//(9)链串替换(从begin 开始的number个字符)
Chain_string *Replace_Chain_String(Chain_string *old_string, int begin_loation,int number,Chain_string *replace_string);
//(10)输出展示串
void Display_Chain_String(Chain_string *show_String);
#endif
链串库函数
V1.0简洁版本
Chain_string.cpp/*****************************************
功 能: 链串算法库
编程人: 无数碎片寻你
时 间: 2024.7.4
版 本: V1.0
******************************************/
#include <stdio.h>
#include <malloc.h>
#include "Chain_string.h"
/**************************************************
(1)函数名: Assignment_Chain_string
功 能: 将一个字符串数组赋值给链串,从而创建新串
参 数: (1)Chain_string *&New_String:要创建的新串
(2)char Assign_array[]: 创建新串用到的数组数据
注 意: 创建新串传回是指针地址
返回值: 无
**************************************************/
void Assignment_Chain_string(Chain_string *&New_String, char Assign_array[])
{
int counter;
//尾结点,取出数组数据得到的新节点
Chain_string *rear_Node,*new_Node;
//为新链串分配空间
New_String = (Chain_string *)malloc(sizeof(Chain_string));
//初始化,尾指针指向头结点
rear_Node = New_String;
rear_Node->next = NULL;
for(counter = 0; Assign_array[counter] != '\0'; counter++)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = Assign_array[counter];
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
}
rear_Node->next = NULL;
}
/**************************************************
(2)函数名: Copy_Chain_String
功 能: 复制一个链串,到另一个链串
参 数: (1)Chain_string *&accept_string:接受复制的链串
(2)Chain_string *copy_string: 被复制的链串
思 路: 逐个遍历,复制即可
返回值: 返回链串
**************************************************/
void Copy_Chain_String(Chain_string *&accept_string, Chain_string *copy_string)
{
Chain_string *visit_Node = copy_string->next; //遍历被复制节点
Chain_string *copy_Node; //每次复制的节点
Chain_string *rear_Node; //尾插法定义的尾结点
//为接受复制链串分配空间
accept_string = (Chain_string *)malloc(sizeof(Chain_string));
//初始时,尾指针指向头结点
rear_Node = accept_string;
rear_Node->next = NULL;
while(visit_Node != NULL)
{
//为每次复制的节点,创建空间
copy_Node = (Chain_string *)malloc(sizeof(Chain_string));
copy_Node->data = visit_Node->data;
copy_Node->next = NULL;
//经典尾插
rear_Node->next = copy_Node;
rear_Node = copy_Node;
//复制节点后移
visit_Node = visit_Node->next;
}
rear_Node->next = NULL;
}
/**************************************************
(3)函数名: Equal_Chain_String
功 能: 判断两个串是否相等
参 数: (1)Chain_string *judge_string1:要进行判断的串1
(2)Chain_string *judge_string2:要进行判断的串2
返回值: bool 两个串是否相等?相等,true:不相等,false
**************************************************/
bool Equal_Chain_String(Chain_string *judge_string1, Chain_string *judge_string2)
{
Chain_string *visit_Node1 = judge_string1->next;
Chain_string *visit_Node2 = judge_string2->next;
while(visit_Node1 != NULL && visit_Node2 != NULL && visit_Node1->data == visit_Node2->data)
{
visit_Node1 = visit_Node1->next;
visit_Node2 = visit_Node2->next;
}
if(visit_Node1 == NULL && visit_Node2 == NULL)
{
return true;
}
else
{
return false;
}
}
/**************************************************
(4)函数名:Length_Chain_String
功 能:求链串串长
参 数:Chain_string *measure_string:要进行测量串长的链串
返回值:int counter:返回链串长度
**************************************************/
int Length_Chain_String(Chain_string *measure_string)
{
int counter = 0;
Chain_string *measure_Node = measure_string;
while(measure_Node->next != NULL)
{
counter++;
measure_Node = measure_Node->next;
}
return counter;
}
/**************************************************
(5)函数名:Connect_Chain_String
功 能:链串连接
参 数:(1)Chain_string *link1:要链接的第一个串
(2)Chain_string *link2:要链接的第二个串
思 路: 定义两个变量,然后进行遍历两个串
返回值: Chain_string *New_String: 返回链接的串
**************************************************/
Chain_string *Connect_Chain_String(Chain_string *link1, Chain_string *link2)
{
Chain_string *New_String;
Chain_string *visit_Node;
Chain_string *new_Node;
Chain_string *rear_Node;
//为组合串分配空间
New_String = (Chain_string *)malloc(sizeof(Chain_string));
//初始化时,尾指针指向串头
rear_Node = New_String;
rear_Node->next = NULL;
//第一个串
visit_Node = link1->next;
while(visit_Node != NULL)
{
//经典尾插法
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;
}
//第二个串
visit_Node = link2->next;
while(visit_Node != NULL)
{
//经典尾插法
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;
}
rear_Node->next = NULL;
return New_String;
}
/**************************************************
(6)函数名: Get_Chain_Substring
功 能: 求链串的子串(从begin_loation开始的number个字符)
参 数: (1)Chain_string *Mother_string:摘取子串的母串
(2)int begin_loation:开始摘取的位置
(3)int number:摘取子串的数量
返回值: Chain_string *new_Substring: 分隔得到的新子串
**************************************************/
Chain_string *Get_Chain_Substring(Chain_string *Mother_string, int begin_loation, int number)
{
int counter;
Chain_string *new_Substring;//新子串
Chain_string *new_Node; //构建子串的节点
Chain_string *visit_Node; //访问旧串的节点
Chain_string *rear_Node; //新子串的尾指针
new_Substring = (Chain_string *)malloc(sizeof(Chain_string));
new_Substring->next = NULL;
rear_Node = new_Substring; //子串初始化
if(begin_loation <= 0 || begin_loation >= Length_Chain_String(Mother_string)||
number < 0 || begin_loation+number-1 > Length_Chain_String(Mother_string) )
{
//错误:子串位置超标
printf("\nError<6>: The substring position exceeds the standard.\n");
return new_Substring;
}
//嗅探子串位置
visit_Node = Mother_string->next;//从头结点后继开始,就是从1开始,同步推进
for(counter = 1; counter <= begin_loation-1; counter++)
{
visit_Node = visit_Node->next;
}
//开始复制子串
for(counter = 0; counter < number; counter++)
{
//经典尾插
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node->data;
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;//是否超过,合法性判断
}
rear_Node->next = NULL;
return new_Substring;
}
/**************************************************
(7)函数名: Insert_Chain_String
功 能: 链串中插入串(从从begin_loation开始插入字符串,然后组合成新的串)
参 数: (1)Chain_string *old_string:原始要进行插入操作的链串
(2)int begin_loation:开始插入的位置
(3)Chain_string *insert_string: 要插入的链串
注 意: 尾插法的应用
返回值: Chain_string *new_String;
**************************************************/
Chain_string *Insert_Chain_String(Chain_string *old_string, int begin_loation,Chain_string *insert_string)
{
int counter;
//形成的新串
Chain_string *new_String;
//建立新串,新节点与尾插法
Chain_string *new_Node,*rear_Node;
//访问两个串的指针
Chain_string *visit_Node1,*visit_Node2;
//新串初始化
new_String = (Chain_string *)malloc(sizeof(Chain_string));
new_String->next = NULL;
rear_Node = new_String;
//插入位置合法性检测
if(begin_loation <= 0 || (begin_loation>Length_Chain_String(old_string)+1))
{
//错误:链串插入位置错误
printf("\nError<7>: wrong insertion position of chain string.\n");
}
//旧串1插入位置前的串(i-1个元素)
visit_Node1 = old_string->next;
for(counter = 0; counter < begin_loation-1; counter++)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node1->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node1 = visit_Node1->next; //最后出来是指向第i个元素
}
//加入串2
visit_Node2 = insert_string->next;
while(visit_Node2 != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node2->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node2 = visit_Node2->next;
}
//加入串1插入位置的后续串(第begin_loation个元素到最后)
while(visit_Node1 != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node1->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node1 = visit_Node1->next;
}
rear_Node->next = NULL;
return new_String;
}
/**************************************************
(8)函数名: Delete_Chain_String
功 能: 删除链串(从begin 开始的number个字符)
参 数: (1)Chain_string *old_string:在本串基础上截取
(2)int begin_loation:开始删除的位置
(3)int number:删除的数量
思 路: 有选择的复制剪切
返回值: Chain_string *new_String:处理完的新串,返回
**************************************************/
Chain_string *Delete_Chain_String(Chain_string *old_string, int begin_loation,int number)
{
int counter;
Chain_string *new_String;
Chain_string *new_Node;
Chain_string *visit_Node;
Chain_string *rear_Node;
new_String = (Chain_string *)malloc(sizeof(Chain_string));
new_String->next = NULL;
rear_Node = new_String;
if( begin_loation <= 0 ||
begin_loation > Length_Chain_String(old_string) ||
number < 0 ||
(begin_loation+number-1 > Length_Chain_String(old_string))
)
{
//错误: 删除位置错误
printf("\nError<8>: Error in deleting location.\n");
}
//把删除位置之前的节点复制
visit_Node = old_string->next;
for(counter = 0; counter < begin_loation-1; counter++)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;
}
//跳过要删除的节点
for(counter = 0; counter<number; counter++)
{
visit_Node = visit_Node->next;
}
//把后继节点复制加入new_String
while(visit_Node != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;
}
rear_Node->next = NULL;
return new_String;
}
/**************************************************
(9)函数名: Replace_Chain_String
功 能: 链串替换(从begin 开始的number个字符)
参 数: (1)Chain_string *old_string:在原始串上进行操作
(2)int begin_loation:开始替换的位置(头结点不算,头结点之后算第一个节点)
(3)int number:替换的数量
(4)Chain_string *replace_string:;要替换成的链串
返回值: Chain_string *new_String:替换完,形成的链串
**************************************************/
Chain_string *Replace_Chain_String(Chain_string *old_string, int begin_loation,int number,Chain_string *replace_string)
{
int counter;
//形成的新串
Chain_string *new_String;
//建立新串,新节点与尾插法
Chain_string *new_Node,*rear_Node;
//访问两个串的指针
Chain_string *visit_Node1,*visit_Node2;
//新串初始化
new_String = (Chain_string *)malloc(sizeof(Chain_string));
new_String->next = NULL;
rear_Node = new_String;
//替换位置合法性检测
if(begin_loation <= 0 || begin_loation>Length_Chain_String(old_string))
{
//错误:链串替换位置错误
printf("\nError<9>: the chain string replacement position is wrong.\n");
}
//旧串替换位置前的串
visit_Node1 = old_string->next;
for(counter = 0; counter < begin_loation-1; counter++)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node1->data;
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node1 = visit_Node1->next; //最后出来是指向第i个元素
}
//visit_Node1跳过number个节点
for(counter = 0; counter < number; counter++)
{
visit_Node1 = visit_Node1->next;
}
//把替换的串,加入
visit_Node2 = replace_string->next;
while(visit_Node2 != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node2->data;
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node2 = visit_Node2->next;
}
//旧串第二段
while(visit_Node1 != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
new_Node->data = visit_Node1->data;
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node1 = visit_Node1->next;
}
rear_Node->next = NULL;
return new_String;
}
/**************************************************
(10)函数名: Display_Chain_String
功 能: 输出展示串
参 数: Chain_string *show_String:要进行展示的串
返回值: 无
**************************************************/
void Display_Chain_String(Chain_string *show_String)
{
Chain_string *show_Node;
show_Node = show_String->next;
while(show_Node != NULL)
{
printf("%c",show_Node->data);
show_Node = show_Node->next;
}
printf("\n");
}
V2.0补丁版本
main.cpp/*****************************************
功 能: 链串算法库
编程人: 无数碎片寻你
时 间: 2024.7.4
版 本: V1.0
******************************************/
#include <stdio.h>
#include <malloc.h>
#include "Chain_string.h"
/**************************************************
(1)函数名: Assignment_Chain_string
功 能: 将一个字符串数组赋值给链串,从而创建新串
参 数: (1)Chain_string *&New_String:要创建的新串
(2)char Assign_array[]: 创建新串用到的数组数据
注 意: 创建新串传回是指针地址
返回值: 无
**************************************************/
void Assignment_Chain_string(Chain_string *&New_String, char Assign_array[])
{
int counter;
//尾结点,取出数组数据得到的新节点
Chain_string *rear_Node,*new_Node;
//为新链串分配空间
New_String = (Chain_string *)malloc(sizeof(Chain_string));
//初始化,尾指针指向头结点
rear_Node = New_String;
rear_Node->next = NULL;
for(counter = 0; Assign_array[counter] != '\0'; counter++)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(New_String->next)//释放已经分配的节点
{
Chain_string *temp = New_String->next;
New_String->next = temp->next;
free(temp);
}
free(New_String);//释放头结点
return;
}
new_Node->data = Assign_array[counter];
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
}
rear_Node->next = NULL;
}
/**************************************************
(2)函数名: Copy_Chain_String
功 能: 复制一个链串,到另一个链串
参 数: (1)Chain_string *&accept_string:接受复制的链串
(2)Chain_string *copy_string: 被复制的链串
思 路: 逐个遍历,复制即可
返回值: 返回链串
**************************************************/
void Copy_Chain_String(Chain_string *&accept_string, Chain_string *copy_string)
{
Chain_string *visit_Node = copy_string->next; //遍历被复制节点
Chain_string *copy_Node; //每次复制的节点
Chain_string *rear_Node; //尾插法定义的尾结点
//为接受复制链串分配空间
accept_string = (Chain_string *)malloc(sizeof(Chain_string));
//初始时,尾指针指向头结点
rear_Node = accept_string;
rear_Node->next = NULL;
while(visit_Node != NULL)
{
//为每次复制的节点,创建空间
copy_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!copy_Node) //检查内存分配是否成功
{
while(accept_string->next)//释放已经分配的节点
{
Chain_string *temp = accept_string->next;
accept_string->next = temp->next;
free(temp);
}
free(accept_string);//释放头结点
return;
}
copy_Node->data = visit_Node->data;
copy_Node->next = NULL;
//经典尾插
rear_Node->next = copy_Node;
rear_Node = copy_Node;
//复制节点后移
visit_Node = visit_Node->next;
}
rear_Node->next = NULL;
}
/**************************************************
(3)函数名: Equal_Chain_String
功 能: 判断两个串是否相等
参 数: (1)Chain_string *judge_string1:要进行判断的串1
(2)Chain_string *judge_string2:要进行判断的串2
返回值: bool 两个串是否相等?相等,true:不相等,false
**************************************************/
bool Equal_Chain_String(Chain_string *judge_string1, Chain_string *judge_string2)
{
Chain_string *visit_Node1 = judge_string1->next;
Chain_string *visit_Node2 = judge_string2->next;
while(visit_Node1 != NULL && visit_Node2 != NULL && visit_Node1->data == visit_Node2->data)
{
visit_Node1 = visit_Node1->next;
visit_Node2 = visit_Node2->next;
}
if(visit_Node1 == NULL && visit_Node2 == NULL)
{
return true;
}
else
{
return false;
}
}
/**************************************************
(4)函数名:Length_Chain_String
功 能:求链串串长
参 数:Chain_string *measure_string:要进行测量串长的链串
返回值:int counter:返回链串长度
**************************************************/
int Length_Chain_String(Chain_string *measure_string)
{
int counter = 0;
Chain_string *measure_Node = measure_string;
while(measure_Node->next != NULL)
{
counter++;
measure_Node = measure_Node->next;
}
return counter;
}
/**************************************************
(5)函数名:Connect_Chain_String
功 能:链串连接
参 数:(1)Chain_string *link1:要链接的第一个串
(2)Chain_string *link2:要链接的第二个串
思 路: 定义两个变量,然后进行遍历两个串
返回值: Chain_string *New_String: 返回链接的串
**************************************************/
Chain_string *Connect_Chain_String(Chain_string *link1, Chain_string *link2)
{
Chain_string *New_String;
Chain_string *visit_Node;
Chain_string *new_Node;
Chain_string *rear_Node;
//为组合串分配空间
New_String = (Chain_string *)malloc(sizeof(Chain_string));
//初始化时,尾指针指向串头
rear_Node = New_String;
rear_Node->next = NULL;
//第一个串
visit_Node = link1->next;
while(visit_Node != NULL)
{
//经典尾插法
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(New_String->next)//释放已经分配的节点
{
Chain_string *temp = New_String->next;
New_String->next = temp->next;
free(temp);
}
free(New_String);//释放头结点
return New_String;
}
new_Node->data = visit_Node->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;
}
//第二个串
visit_Node = link2->next;
while(visit_Node != NULL)
{
//经典尾插法
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(New_String->next)//释放已经分配的节点
{
Chain_string *temp = New_String->next;
New_String->next = temp->next;
free(temp);
}
free(New_String);//释放头结点
return New_String;
}
new_Node->data = visit_Node->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;
}
rear_Node->next = NULL;
return New_String;
}
/**************************************************
(6)函数名: Get_Chain_Substring
功 能: 求链串的子串(从begin_loation开始的number个字符)
参 数: (1)Chain_string *Mother_string:摘取子串的母串
(2)int begin_loation:开始摘取的位置
(3)int number:摘取子串的数量
返回值: Chain_string *new_Substring: 分隔得到的新子串
**************************************************/
Chain_string *Get_Chain_Substring(Chain_string *Mother_string, int begin_loation, int number)
{
int counter;
Chain_string *new_Substring;//新子串
Chain_string *new_Node; //构建子串的节点
Chain_string *visit_Node; //访问旧串的节点
Chain_string *rear_Node; //新子串的尾指针
new_Substring = (Chain_string *)malloc(sizeof(Chain_string));
new_Substring->next = NULL;
rear_Node = new_Substring; //子串初始化
if(begin_loation <= 0 || begin_loation >= Length_Chain_String(Mother_string)||
number < 0 || begin_loation+number-1 > Length_Chain_String(Mother_string) )
{
//错误:子串位置超标
printf("\nError<6>: The substring position exceeds the standard.\n");
free(new_Substring); // 释放头节点内存
return new_Substring;
}
//嗅探子串位置
visit_Node = Mother_string->next;//从头结点后继开始,就是从1开始,同步推进
for(counter = 1; counter <= begin_loation-1; counter++)
{
visit_Node = visit_Node->next;
}
//开始复制子串
for(counter = 0; counter < number; counter++)
{
//经典尾插
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(new_Substring->next)//释放已经分配的节点
{
Chain_string *temp = new_Substring->next;
new_Substring->next = temp->next;
free(temp);
}
free(new_Substring);//释放头结点
return new_Substring;
}
new_Node->data = visit_Node->data;
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;//是否超过,合法性判断
}
rear_Node->next = NULL;
return new_Substring;
}
/**************************************************
(7)函数名: Insert_Chain_String
功 能: 链串中插入串(从从begin_loation开始插入字符串,然后组合成新的串)
参 数: (1)Chain_string *old_string:原始要进行插入操作的链串
(2)int begin_loation:开始插入的位置
(3)Chain_string *insert_string: 要插入的链串
注 意: 尾插法的应用
返回值: Chain_string *new_String;
**************************************************/
Chain_string *Insert_Chain_String(Chain_string *old_string, int begin_loation,Chain_string *insert_string)
{
int counter;
//形成的新串
Chain_string *new_String;
//建立新串,新节点与尾插法
Chain_string *new_Node,*rear_Node;
//访问两个串的指针
Chain_string *visit_Node1,*visit_Node2;
//新串初始化
new_String = (Chain_string *)malloc(sizeof(Chain_string));
new_String->next = NULL;
rear_Node = new_String;
//插入位置合法性检测
if(begin_loation <= 0 || (begin_loation>Length_Chain_String(old_string)+1))
{
//错误:链串插入位置错误
printf("\nError<7>: wrong insertion position of chain string.\n");
free(new_String); // 释放头节点内存
return new_String;
}
//旧串1插入位置前的串(i-1个元素)
visit_Node1 = old_string->next;
for(counter = 0; counter < begin_loation-1; counter++)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));\
if(!new_Node) //检查内存分配是否成功
{
while(new_String->next)//释放已经分配的节点
{
Chain_string *temp = new_String->next;
new_String->next = temp->next;
free(temp);
}
free(new_String);//释放头结点
return new_String;
}
new_Node->data = visit_Node1->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node1 = visit_Node1->next; //最后出来是指向第i个元素
}
//加入串2
visit_Node2 = insert_string->next;
while(visit_Node2 != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(new_String->next)//释放已经分配的节点
{
Chain_string *temp = new_String->next;
new_String->next = temp->next;
free(temp);
}
free(new_String);//释放头结点
return new_String;
}
new_Node->data = visit_Node2->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node2 = visit_Node2->next;
}
//加入串1插入位置的后续串(第begin_loation个元素到最后)
while(visit_Node1 != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(new_String->next)//释放已经分配的节点
{
Chain_string *temp = new_String->next;
new_String->next = temp->next;
free(temp);
}
free(new_String);//释放头结点
return new_String;
}
new_Node->data = visit_Node1->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node1 = visit_Node1->next;
}
rear_Node->next = NULL;
return new_String;
}
/**************************************************
(8)函数名: Delete_Chain_String
功 能: 删除链串(从begin 开始的number个字符)
参 数: (1)Chain_string *old_string:在本串基础上截取
(2)int begin_loation:开始删除的位置
(3)int number:删除的数量
思 路: 有选择的复制剪切
返回值: Chain_string *new_String:处理完的新串,返回
**************************************************/
Chain_string *Delete_Chain_String(Chain_string *old_string, int begin_loation,int number)
{
int counter;
Chain_string *new_String;
Chain_string *new_Node;
Chain_string *visit_Node;
Chain_string *rear_Node;
new_String = (Chain_string *)malloc(sizeof(Chain_string));
new_String->next = NULL;
rear_Node = new_String;
if( begin_loation <= 0 ||
begin_loation > Length_Chain_String(old_string) ||
number < 0 ||
(begin_loation+number-1 > Length_Chain_String(old_string))
)
{
//错误: 删除位置错误
printf("\nError<8>: Error in deleting location.\n");
free(new_String); // 释放头节点内存
return new_String;
}
//把删除位置之前的节点复制
visit_Node = old_string->next;
for(counter = 0; counter < begin_loation-1; counter++)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(new_String->next)//释放已经分配的节点
{
Chain_string *temp = new_String->next;
new_String->next = temp->next;
free(temp);
}
free(new_String);//释放头结点
return new_String;
}
new_Node->data = visit_Node->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;
}
//跳过要删除的节点
for(counter = 0; counter<number; counter++)
{
visit_Node = visit_Node->next;
}
//把后继节点复制加入new_String
while(visit_Node != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(new_String->next)//释放已经分配的节点
{
Chain_string *temp = new_String->next;
new_String->next = temp->next;
free(temp);
}
free(new_String);//释放头结点
return new_String;
}
new_Node->data = visit_Node->data;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node = visit_Node->next;
}
rear_Node->next = NULL;
return new_String;
}
/**************************************************
(9)函数名: Replace_Chain_String
功 能: 链串替换(从begin 开始的number个字符)
参 数: (1)Chain_string *old_string:在原始串上进行操作
(2)int begin_loation:开始替换的位置(头结点不算,头结点之后算第一个节点)
(3)int number:替换的数量
(4)Chain_string *replace_string:;要替换成的链串
返回值: Chain_string *new_String:替换完,形成的链串
**************************************************/
Chain_string *Replace_Chain_String(Chain_string *old_string, int begin_loation,int number,Chain_string *replace_string)
{
int counter;
//形成的新串
Chain_string *new_String;
//建立新串,新节点与尾插法
Chain_string *new_Node,*rear_Node;
//访问两个串的指针
Chain_string *visit_Node1,*visit_Node2;
//新串初始化
new_String = (Chain_string *)malloc(sizeof(Chain_string));
new_String->next = NULL;
rear_Node = new_String;
//替换位置合法性检测
if(begin_loation <= 0 || begin_loation>Length_Chain_String(old_string)||
number < 0 || (begin_loation+number-1 > Length_Chain_String(old_string))
)
{
//错误:链串替换位置错误
printf("\nError<9>: the chain string replacement position is wrong.\n");
free(new_String); // 释放头节点内存
return new_String;
}
//旧串替换位置前的串
visit_Node1 = old_string->next;
for(counter = 0; counter < begin_loation-1; counter++)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(new_String->next)//释放已经分配的节点
{
Chain_string *temp = new_String->next;
new_String->next = temp->next;
free(temp);
}
free(new_String);//释放头结点
return new_String;
}
new_Node->data = visit_Node1->data;
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node1 = visit_Node1->next; //最后出来是指向第i个元素
}
//visit_Node1跳过number个节点
for(counter = 0; counter < number; counter++)
{
visit_Node1 = visit_Node1->next;
}
//把替换的串,加入
visit_Node2 = replace_string->next;
while(visit_Node2 != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(new_String->next)//释放已经分配的节点
{
Chain_string *temp = new_String->next;
new_String->next = temp->next;
free(temp);
}
free(new_String);//释放头结点
return new_String;
}
new_Node->data = visit_Node2->data;
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node2 = visit_Node2->next;
}
//旧串第二段
while(visit_Node1 != NULL)
{
new_Node = (Chain_string *)malloc(sizeof(Chain_string));
if(!new_Node) //检查内存分配是否成功
{
while(new_String->next)//释放已经分配的节点
{
Chain_string *temp = new_String->next;
new_String->next = temp->next;
free(temp);
}
free(new_String);//释放头结点
return new_String;
}
new_Node->data = visit_Node1->data;
new_Node->next = NULL;
rear_Node->next = new_Node;
rear_Node = new_Node;
visit_Node1 = visit_Node1->next;
}
rear_Node->next = NULL;
return new_String;
}
/**************************************************
(10)函数名: Display_Chain_String
功 能: 输出展示串
参 数: Chain_string *show_String:要进行展示的串
返回值: 无
**************************************************/
void Display_Chain_String(Chain_string *show_String)
{
Chain_string *show_Node;
show_Node = show_String->next;
if(show_Node == NULL)
{
//警告:什么都没有,无法输出字符串
printf("\nWarning<10>: Nothing, unable to output string.\n");
}
else
{
while(show_Node != NULL)
{
printf("%c",show_Node->data);
show_Node = show_Node->next;
}
printf("\n");
}
}main函数测试1:
范围正常情况下测试:
main.cpp#include <stdio.h>
#include "Chain_string.h"
int main()
{
Chain_string *test_String,*test_String1,*test_String2,*test_String3,*test_String4;
char test_char1[ ] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','\0'};
char test_char2[] = {'1','2','3','\0'};
printf("\n链串的基本运算如下:\n");
printf("\n(1)建立串test_String和test_String1\n");
Assignment_Chain_string(test_String, test_char1);
printf("\n(2)输出串test_String:\n");
Display_Chain_String(test_String);
Assignment_Chain_string(test_String1, test_char2);
printf("\n(2)输出串test_String1:\n");
Display_Chain_String(test_String1);
printf("\n(3)串test_String的长度:%d\n",Length_Chain_String(test_String));
printf("\n(4)在串test_String的第9个字符位置插入串test_String1而产生test_String2\n");
test_String2 = Insert_Chain_String(test_String,9,test_String1);
printf("\n(5)输出串test_String2:\n");
Display_Chain_String(test_String2);
printf("\n(6)删除串test_String第二个字符开始的5个字符而产生串2\n");
test_String2 = Delete_Chain_String(test_String,2,5);
printf("\n(7)输出串test_String2:\n");
Display_Chain_String(test_String2);
printf("\n(8)将串2第2个字符开始的5个字符替换成串1而产生串2\n");
test_String2 = Replace_Chain_String(test_String2,2,5,test_String1);
printf("\n(9)输出串2\n");
Display_Chain_String(test_String2);
printf("\n(10)提取串s的第2个字符开始的10个字符而产生串3\n");
test_String3 = Get_Chain_Substring(test_String,2,10);
printf("\n(11)输出串3\n");
Display_Chain_String(test_String3);
printf("\n(12)将串1和串2链接起来而成产生串4\n");
test_String4 = Connect_Chain_String(test_String1,test_String2);
printf("\n(13)输出串4\n");
Display_Chain_String(test_String4);
return 0;
}
运行结果展示:
main函数测试2:
范围超出情况下测试:
主函数文件名字
main.cpp#include <stdio.h>
#include "Chain_string.h"
int main()
{
Chain_string *test_String,*test_String1,*test_String2,*test_String3,*test_String4;
char test_char1[ ] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','\0'};
char test_char2[] = {'1','2','3','\0'};
printf("\n链串的基本运算如下:\n");
printf("\n(1)建立串test_String和test_String1\n");
Assignment_Chain_string(test_String, test_char1);
printf("\n(2)输出串test_String:\n");
Display_Chain_String(test_String);
Assignment_Chain_string(test_String1, test_char2);
printf("\n(2)输出串test_String1:\n");
Display_Chain_String(test_String1);
printf("\n(3)串test_String的长度:%d\n",Length_Chain_String(test_String));
printf("\n(4)在串test_String的第100个字符位置插入串test_String1而产生test_String2\n");
test_String2 = Insert_Chain_String(test_String,100,test_String1);
printf("\n(5)输出串test_String2:\n");
Display_Chain_String(test_String2);
printf("\n(6)删除串test_String第20个字符开始的10个字符而产生串3\n");
test_String3 = Delete_Chain_String(test_String,20,10);
printf("\n(7)输出串test_String3:\n");
Display_Chain_String(test_String3);
printf("\n(8)将串第2个字符开始的99个字符替换成串1而产生串4\n");
test_String4 = Replace_Chain_String(test_String,2,99,test_String1);
printf("\n(9)输出串4\n");
Display_Chain_String(test_String4);
printf("\n(10)提取串s的第2个字符开始的88个字符而产生串3\n");
test_String3 = Get_Chain_Substring(test_String,2,88);
printf("\n(11)输出串3\n");
Display_Chain_String(test_String3);
printf("\n(12)将串和串1链接起来而成产生串4\n");
test_String4 = Connect_Chain_String(test_String,test_String1);
printf("\n(13)输出串4\n");
Display_Chain_String(test_String4);
return 0;
}
运行结果展示:
