データ構造(一)――順序表及び実現

3124 ワード


一、概念
まず線形テーブルを理解してください.結局、順序テーブルとチェーンテーブルは線形テーブルです.
リニアテーブルとは、リニア構造を持つテーブルです.線形構造とは何ですか.線形構造はn個のデータ要素の秩序化集合である.4つの基本的な特徴があります.
1.集合には必ず唯一の「第一要素」が存在する.
2.集合には必ず唯一の「最後の要素」が存在する.
3.最後の要素を除いて、他のデータ要素はすべて唯一の「後継」がある.
4.第1の要素を除いて、他のデータ要素はすべて唯一の「前駆」である.  
例えば(a 1,a 2,a 3,......,an)、a 1は最初の要素であり、anは最後の要素であり、この集合は極めて線形構造の集合である.
線形構造に対応して、非線形構造の論理的特徴は、1つのノード要素が複数の直接前駆体と複数の後駆動体に対応する可能性があることである.
よく使われる線形構造は、線形テーブル、スタック、キュー、デュアルキュー、配列、チェーンテーブル、列です.
 
その順番表は神馬ですか?
シーケンステーブルとは、コンピュータメモリに配列された形式で保存される線形テーブルであり、1組のアドレスで連続する記憶ユニットを用いて、データ要素を順次記憶する線形構造を指す.シーケンステーブルの格納の特徴は、開始位置が決定された場合、テーブルのいずれかの要素のアドレスが次の式で得られることです.
 location(ki)=location(k1)+(i-1)len
 
二、機能と実現
1、構造体の定義
2、初期化
3、末尾挿入値xのノード
4、各ノードの値を印刷する
5、ノードが空かどうかを判断する
6、検索値xのノードの位置
7、iノードの値を取得する
8、i位置にx値を挿入する
9、i位置のノードを削除する
  
1、構造体の定義
#define MAXSIZE 100
typedef int datatype;

typedef struct seqlist{
   datatype a[MAXSIZE];   //  
   int size;  //          ,          
}sequence_list;

2、初期化
void init_sequence_list(sequence_list *slt){
  slt->size=0;
}

3、末尾挿入値xのノード
void insert_sequence_list(sequence_list *slt,datatype x)
{
   if(slt->size==MAXSIZE){
	printf("The list is full!
"); exit(1); } slt->size=slt->size+1; slt->a[slt->size]=x; }

4、各ノードの値を印刷する
void print_sequence_list(sequence_list slt)
{
   int i;
   if(!slt) 
	printf("
The list is empty!
"); else for(i=0;i

5、ノードが空かどうかを判断する
int is_empty_sequence_list(sequence_list slt)
{
   return(slt.size==0 ? 0:1);
}

6、検索値xのノードの位置
int find_num_sequence_list(sequence_list slt,datatype x)
{
   int i=0;
   while(slt.a[i]!=x && i

7.i番目のノードの値を取得する
datatype get_data_pos(sequence_list slt,int i)
{
   if(i<0||i>=slt.size)
     {printf("The position dese not exist!
");exit(1);} else return slt.a[i]; }

8、i位置にx値を挿入する
void insert_pos_sequence_list(sequence_list *slt,int position,datatype x)
{
   int i;
   if(slt->size==MAXSIZE){
		printf("
The list is full!
"); exit(1); } if(position<0||position>slt->size){ printf("
The position does not exist!"); exit(1); } for(i=slt->size;i>position;i--) slt->a[i]=slt->a[i-1]; slt->a[position]=x; slt->size++; }

 
9、i位置のノードを削除する
void delete_pos_sequence_list(sequence_list *slt,int position)
{
   int i;
   if(slt->size==0)
     {printf("The list is empty!
");exit(1);} if(position<0||position>=slt->size) {printf("The position does not exist!
");exit(1);} for(i=position;isize-1;i++) slt->a[i]=slt->a[i+1]; slt->size--; }

 
シーケンステーブルの実装を熟練しており,スタックやキューの実装は非常に簡単である.