数据结构-顺序串储存结构、链式存储结构

素颜马尾好姑娘i 2022-11-27 03:09 141阅读 0赞

# 1、顺序串的定义 #

**结构体：**

#define MaxSize 100	　//串中最多字符个数
    typedef struct
    {
          char data[MaxSize];　//存放串字符
       int length;		　//存放串的实际长度
    } SqString;		　//顺序串类型

## 1.1、赋值 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center]

void Assign(SqString &s,char str[])
    {
          int i=0;
       while (str[i]!='\0')	//遍历str的所有字符
       {
        	s.data[i]=str[i];
    	i++;
       }
       s.length=i;
    }

## 1.2、插入 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 1]

int InsStr(SqString &s,int i,SqString t){
        
    	int j;
    	if(i<1 || i>s.length+1)
    		return 0; //位置参数错误返回0
    	else{
        
    		for(j=s.length-1;j>=i-1;j--){
        
    			s.data[j+length]=s.data[j];
    		}
    		for (j=0;j<t.length;j++)	//插入子串t
            	s.data[i+j-1]=t.data[j];
            s.length=s.length+t.length;	//修改s串长度
            return 1;			//成功插入返回1
    	}
    }

## 1.3、删除 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 2]  
删除顺序串s中从第i个位置开始的**j**个字符，当参数错误时返回0，成功删除时返回1。

int DelStr(SqString &s,int i,int j)
    {
          int k;
       if (i<1 || i>s.length || j<1 || i+j>s.length+1)
          return 0;		　　//位置参数值错误
       else
       {
          for (k=i+j-1;k<s.length;k++)　
    		//将s的第i+j位置之后的字符前移j位
            s.data[k-j]=s.data[k];
          s.length=s.length-j;	　　//修改s的长度
          return 1;		　　//成功删除返回1
       }
    }

## 1.4、输出 ##

void DispStr(SqString s)
    {
          int i;
       for (i=0;i<s.length;i++)
    	printf("%c",s.data[i]);
       printf("\n");
    }

# 2、链串的定义 #

链串中结点的类型定义如下：

typedef struct node
    {
          char data;		  //存放字符
       struct node *next;	  //指针域
    } LinkString;		  //链串结点类型

为了简单，每个字符用一个结点存储，如下图所示是串"abcd"的链式存储形式，用头结点指针s唯一标识。称为结点大小为1.  
![在这里插入图片描述][20200813111440239.png_pic_center]

## 2.1、赋值 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 3]

void Assign(LinkString *&s,char str[]){
          
       int i=0;
       LinkString *p,*tc;
       s=(LinkString *)malloc(sizeof(LinkString));
       tc=s;			 //tc指向s串的尾结点
       while (str[i]!='\0')
       {
        	
    	    p=(LinkString *)malloc(sizeof(LinkString));
    		p->data=str[i];
    		tc->next=p; 
    		tc=p;
    		i++;
       }
       tc->next=NULL;		//尾结点的next置NULL
    }

## 2.2、输出 ##

void DispStr(LinkString *s)
    {
          LinkString *p=s->next;
       while (p!=NULL)
       {
        	printf("%c",p->data);
    	p=p->next;
       }
       printf("\n");
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/31237b33d8964651b77eeefaee2abe7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/b4d08253f1c34cc3961904341f006e8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/f405724f7eb5493fae754ea5893df4e3.png
[20200813111440239.png_pic_center]: /images/20221124/e405de3bd84a4089811722268272dd7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/c038e18c95224c5daaf668e082857a45.png