ちょくれつきおくこうぞう

ちょくれつきおくこうぞう
CおよびC++言語では、プログラムの実行中に関数malloc()およびfree()を使用して連続空間を動的に申請または解放することができる「スタック」と呼ばれる共有空間が提供される.
CとC++言語ではポインタで配列にアクセスして操作できるため,列の記憶や操作においても上記の特性を十分に利用できる.
シリアルのスタックストレージ構造は、線形テーブルの順序ストレージ構造と同様に、静的割り当てではなく、プログラム実行中に動的に割り当てられたシリアル値文字シーケンスをアドレス連続ストレージユニットのセットで格納する.
ストリングのヒープストレージ構造定義

Typedef struct 
{  char *ch;   //   ，             
   int length;  //    ：     
}HString;

説明:このストレージ構造では、列は配列で格納された文字列で表されるため、このような列の操作は、新しく生成された列にストレージスペースを割り当ててから「文字列のコピー」を行う.例えば、ストリング挿入動作StrInsert(S,pos,T)(ストリングSの第pos文字にストリングTを挿入する前)のようなアルゴリズムは、ストリングSに対してストリングSとストリングTの長さの和に等しい大きさの記憶領域を再割り当てし、SとTのストリング値を新しい割り当て記憶領域にコピーすることである.
一連の実装

/*
         
 */
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW   -2//   
#define OK          1//      
#define ERROR      -1//      
typedef int datatype;
typedef struct {
	char* ch; //   ，             
	int len; //    ：    
} HString;
//       
datatype InitHString(HString* s) {
	s->ch = (char*) malloc(sizeof(char));
	if (NULL == s->ch)
		return OVERFLOW;
	s->ch = NULL;
	s->len = 0;
	return OK;
}
//    
datatype assigment_string(HString* s, const char* str) {
	if (s->ch)
		free(s->ch);
	int length = 0, i;
	while (str[length] != '\0')
		length++;
	s->ch = (char*) malloc(length * sizeof(char));
	if (!s->ch)
		return OVERFLOW;
	for (i = 0; i < length; i++)
		*(s->ch + i) = *(str + i);
	s->len = length;
	*(s->ch + s->len) = '\0';
	return OK;
}
//  
void PrintString(const HString* s) {
	int i = 0;
	while (*(s->ch + i) != '\0') {
		printf("%c", *(s->ch + i));
		i++;
	}
	printf("
");
}
//     
datatype GetLength(const HString* s) {
	int len = 0;
	while (*(s->ch + len) != '\0')
		len++;
	return len;
}
//         ，    
datatype HSLocal(const HString* s, char c) {
	int i;
	for (i = 0; i < s->len; i++) {
		if (c == *(s->ch + i))
			return i + 1;
	}
	return -1;
}
//    
datatype HSCat(HString* s, const HString* t) {
	int i = 0;
	char* temp = (char*) malloc((s->len + t->len) * sizeof(char));
	if (!temp)
		return OVERFLOW;
	for (i = 0; i < s->len; i++)
		*(temp + i) = *(s->ch + i);
	free(s->ch); //        
	for (i = 0; i < t->len; i++)
		*(temp + i + s->len) = *(t->ch + i);
	s->len += t->len;
	s->ch = temp; // s->ch    temp
	*(s->ch + s->len) = '\0';
	return OK;
}
datatype HSCopy(HString* to, const HString* from) {
	//           	if(to->ch)
	{
		free(to->ch);
		to->ch = NULL;
		to->len = 0;
	}
	int i = 0;
	to->len = from->len;
	to->ch = (char*) malloc(from->len * sizeof(char));
	if (!to->ch)
		return OVERFLOW;
	for (i = 0; i < from->len; i++)
		*(to->ch + i) = *(from->ch + i);
	*(to->ch + to->len) = '\0';
	return OK;

}
//  s pos      t
datatype HSInsert(HString* s, const HString *t, int pos) {
	if (pos < 0 || pos > s->len)
		return ERROR;
	else {
		s->ch = (char*) realloc(s->ch, (s->len + t->len) * sizeof(char));
		int i, j = 1;
		//  
		for (i = s->len + t->len - 1; i >= pos + t->len; i--) {
			*(s->ch + i) = *(s->ch + (s->len - j));
			j++;
		}
		//insert  
		for (i = 0; i < t->len; i++)
			*(s->ch + i + pos) = *(t->ch + i);
	}
	s->len += t->len;
	*(s->ch + s->len) = '\0';
	return OK;
}
//  s index       x   
datatype HSdel(HString* s, int index, int x) {
	// index value invalid
	if (index < 0 || index > s->len)
		return ERROR;
	//  if x+index> s->len
	if ((index + x) >= s->len)
		s->len = index;
	else {
		int i;
		for (i = index; i < s->len; i++) {
			*(s->ch + i) = *(s->ch + i + x);
		}
		s->len -= x;
	}
	*(s->ch + s->len) = '\0';
	return OK;
}
//   
datatype HScomp(const HString* s1, const HString* s2) {
	int i = 0;
	for (i = 0; i < s1->len && i < s2->len; i++) {
		if (*(s1->ch + i) != *(s2->ch + i))
			return *(s1->ch + i) - *(s2->ch + i);
	}
	if (i < s1.len) {
		return 1;
	} else if (i < s2.len) {
		return -1;
	} else {
		return 0;
	}
}
/*    
 *     s  index     length      temp  
 * */
datatype HSsub(HString* temp, const HString* s, int index, int length) {
	if (index < 0 || index > s->len)
		return ERROR;
	if (length > s->len)
		length = s->len - index;
	temp->len = length;
	temp->ch = (char*) malloc(length * sizeof(char));
	if (!temp->ch)
		return OVERFLOW;
	int i;
	for (i = 0; i < length; i++) {
		*(temp->ch + i) = *(s->ch + index + i);
	}
	*(temp->ch + temp->len) = '\0';
	return OK;
}
//    ，  s  index     length   ，  t   
datatype HSReplace(HString* s, int index, int length, const HString*t) {
	if (index < 0 || index > s->len)
		return ERROR;
	//  length   s        index      
	if (length > s->len)
		length = s->len;
	int i;
	for (i = 0; i < length; i++) {
		*(s->ch + i + index) = *(t->ch + i);
	}
	*(s->ch + s->len) = '\0';
	return OK;
}
int main(int argc, char** argv) {
	// bulid string
	HString S;
	InitHString(&S);
	assigment_string(&S, "hello world!");
	PrintString(&S);
	printf("length=%d
", GetLength(&S));

#if 0
	//localion
	int local=HSLocal(&S,'w');
	printf("local=%d
",local);
	free(S.ch);
#endif 

#if 0
	// insert
	HString S1;
	InitHString(&S1);
	assigment_string(&S1,"****");
	HSInsert(&S,&S1,2);
	PrintString(&S);
	printf("length=%d
",GetLength(&S));
	free(S1.ch);
#endif
#if 0	
	// copy
	HString S2;
	InitHString(&S2);
	assigment_string(&S2,"beijing");
	HSCopy(&S,&S2);
	PrintString(&S);
	printf("length=%d
",GetLength(&S));
	free(S.ch);
	free(S2.ch);
#endif
#if 0
	//cat 
	HString S3;
	InitHString(&S3);
	assigment_string(&S3,"////");
	HSCat(&S,&S3);
	PrintString(&S);
	printf("length=%d
",GetLength(&S));
	free(S3.ch);
	free(S.ch);
#endif 

#if 0
	// delete 
	HSdel(&S,2,5);
	PrintString(&S);
	printf("length=%d
",GetLength(&S));
	free(S.ch);
#endif 

#if 0
	// complar 
	HString S4;
	InitHString(&S4);
	assigment_string(&S4,"hello world!");
	datatype ret=HScomp(&S,&S4);
	if(ret>0)
	printf("S>S4
");
	else if(ret<0)
	printf("S<S4
");
	else
	printf("S=S4
");
	free(S4.ch);
	free(S.ch);
#endif

#if 0
	// sub
	HString S5;
	HSsub(&S5,&S,2,5);
	PrintString(&S5);
	printf("length=%d
",GetLength(&S5));
	free(S.ch);
	free(S5.ch);
#endif

#if 1       
	// replace
	HString S6;
	InitHString(&S6);
	assigment_string(&S6, "************************************");
	HSReplace(&S, 2, 50, &S6);
	PrintString(&S);
	printf("length=%d
", GetLength(&S));
	free(S6.ch);
	free(S.ch);

#endif
	//		free(S.ch);
	return 0;
}