如何在C++中建立一個順序表

更新時間：2013年10月14日 10:03:54 作者：

在使用順序表之前，首先創(chuàng)建一個空的順序表，也就是初始化順序表。這里，在程序中只需設(shè)置順序表的結(jié)點數(shù)量ListLen為0即可。這樣，后面需要添加的數(shù)據(jù)元素將從順序表的第一個位置存儲

準(zhǔn)備數(shù)據(jù)

復(fù)制代碼代碼如下:

#define MAXLEN 100 //定義順序表的最大長度
struct DATA
{
 char key[10]; //結(jié)點的關(guān)鍵字 
 char name[20];
 int age;
};
struct SLType //定義順序表結(jié)構(gòu) 
{
 DATA ListData[MAXLEN+1];//保存順序表的結(jié)構(gòu)數(shù)組
 int ListLen;   //順序表已存結(jié)點的數(shù)量 
}; 

定義了順序表的最大長度MAXLEN、順序表數(shù)據(jù)元素的類型DATA以及順序表的數(shù)據(jù)結(jié)構(gòu)SLType。

在數(shù)據(jù)結(jié)構(gòu)SLType中，Listen為順序表已存結(jié)點的數(shù)量，也就是當(dāng)前順序表的長度，ListData是一個結(jié)構(gòu)數(shù)組，用來存放各個數(shù)據(jù)結(jié)點。

我們認(rèn)為該順序表是一個班級學(xué)生的記錄。其中，key為學(xué)號，name為學(xué)生的名稱，age為年齡。

因為數(shù)組都是從下標(biāo)0開始的，為了使用方便，我們從下標(biāo)1開始記錄數(shù)據(jù)結(jié)點，下標(biāo)0的位置不可用。

初始化順序表

在使用順序表之前，首先創(chuàng)建一個空的順序表，也就是初始化順序表。這里，在程序中只需設(shè)置順序表的結(jié)點數(shù)量ListLen為0即可。這樣，后面需要添加的數(shù)據(jù)元素將從順序表的第一個位置存儲。
示例代碼：

復(fù)制代碼代碼如下:

void SLInit(SLType * SL) //初始化順序表
{
 SL->Listlen=0; 
} 

計算線性表的長度

計算線性表的長度也就是計算線性表中結(jié)點的個數(shù)，由于我們在SLType中定義了ListLen來表示結(jié)點的數(shù)量，所以我們只需要獲得這個變量的值即可。

復(fù)制代碼代碼如下:

int SLLenght(SLType *SL)
{
 return(SL->ListLen); //返回順序表的元素數(shù)量 
} 

插入結(jié)點

插入節(jié)點就是在線性表L的第i個位置上插入一個新的結(jié)點，使其后的結(jié)點編號依次加1。
這時，插入一個新節(jié)點之后，線性表L的長度將變?yōu)閚+1。插入結(jié)點操作的難點在于隨后的每個結(jié)點數(shù)據(jù)都要向后移動，計算機比較大，示例代碼如下：

復(fù)制代碼代碼如下:

int SLInsert(SLType *SL,int n,DATA data)
{
 int i;
 if(SL->ListLen>=MAXLEN) //順序表結(jié)點數(shù)量已超過最大數(shù)量
 {
  cout<<"順序表已滿，不能插入結(jié)點！"<<endl;
  return 0;   //返回0表示插入不成功 
 } 
 if(n<1||n>SL->ListLen) //插入結(jié)點的序號不合法 
 {
  cout<<"插入序號錯誤！"<<endl;
  return 0;
 }
 for(i=SL->ListLen;i>=n;i--) //將順序表中的數(shù)據(jù)向后移動
 {
  SL->ListData[i+1]=SL->ListData[i];
 }
 SL->ListData[n]=data;
 SL->ListLen++;
 return 1; 
}

在程序中首先判斷順序表結(jié)點數(shù)量時候已超過最大數(shù)量，以及插入點的序號是否正確。前面條件都瞞住以后，便將順序表中的數(shù)據(jù)向后移動，同時插入結(jié)點，并更新結(jié)點數(shù)量ListLen。

追加結(jié)點

追加結(jié)點就是在順序表的尾部插入結(jié)點，因此不必進行大量數(shù)據(jù)的移動，代碼實現(xiàn)與插入結(jié)點相比就要簡單的多。

復(fù)制代碼代碼如下:

int SLAdd(SLType * SL,DATA data)
{
 if(SL->ListLen>=MAXLEN)
 {
  cout<<"順序表已滿，不能再添加結(jié)點了！"<<endl;
  return 0;
 } 
 SL->ListData[++SL->ListLen]=data;
 return 1;
}

刪除結(jié)點

刪除結(jié)點就是刪除線性表L中的第i個結(jié)點，使得其后的所有節(jié)點編號依次減1.這是，刪除一個結(jié)點之后，線性表L的長度將變?yōu)閚-1。刪除結(jié)點和插入結(jié)點類似，都需要進行大量數(shù)據(jù)的移動。

復(fù)制代碼代碼如下:

int SLDelete(SLType *SL,int n) //刪除順序表中的數(shù)據(jù)元素
{
 int i;
 if(n<1||n>SL->ListLen) //刪除結(jié)點的序號不合法 
 {
  cout<<"刪除序號錯誤！"<<endl;
  return 0;
 }
 for(i=n;i<SL->ListLen;i++)//將順序表中的數(shù)據(jù)向前移動 
 {
  SL->ListData[i]=SL->ListData[i+1]; 
 } 
 SL->ListLen--;   //順序表元素數(shù)量減1 
 return 1;    //成功刪除返回1 
} 

查找結(jié)點

查找節(jié)點就是在線性表L中查找值為x的結(jié)點，并返回該節(jié)點在線性表L中的位置。如果在線性表中沒有找到值為x的結(jié)點，則返回一個錯誤標(biāo)志。
根據(jù)x的類型不同，查找結(jié)點可以分為：

按照序號查找結(jié)點

對于一個順序表，序號就是數(shù)據(jù)元素在數(shù)組中的位置，也就是數(shù)組的下標(biāo)標(biāo)號。按照序號查找結(jié)點是順序表查找結(jié)點最常用的方法，這是因為順序表的存儲本身就是一個數(shù)組，示例代碼如下：

復(fù)制代碼代碼如下:

DATA * SLFindByNum(SLType *SL,int n)//根據(jù)呼號返回數(shù)據(jù)元素
{
 if(n<1||n>SL->ListLen)   //查詢結(jié)點的序號不合法 
 {
  cout<<"查詢序號錯誤！"<<endl;
  return 0;
 }
 return &(SL->ListData[n]); 
} 

按照關(guān)鍵字查找結(jié)點

關(guān)鍵字可以是數(shù)據(jù)元素中的任意一項。
這里以key關(guān)鍵字為例進行介紹，例如，可以通過key查找學(xué)生的信息。示例代碼如下：

復(fù)制代碼代碼如下:

int SLFindByCont(SLType * SL,char *key)//按關(guān)鍵字查詢結(jié)點 
{
 int i;
 for(i=1;i<=SL->ListLen;i++)
 {
  if(strcmp(SL->ListData[i].key,key)==0)//如果找到結(jié)點 
  {
   return i;
  }
 }
 return 0;      //在整個表中都沒有找到，返回0 
} 

顯示所有的結(jié)點

示例代碼如下：

復(fù)制代碼代碼如下:

void SLALL(SLType *SL)
{
 int i;
 for(i=1;i<SL->ListLen;i++)
 {
  cout<<"key:"<<SL->ListData[i].key<<endl;
  cout<<"name:"<<SL->ListData[i].name<<endl;
  cout<<"age:"<<SL->ListData[i].age<<endl;
  cout<<"============================="<<endl; 
 }
} 

順序表操作完整示例：

基本上就是把上面的函數(shù)放到一塊，集中展示了一下功能，代碼有些長，請耐心閱讀^.^

復(fù)制代碼代碼如下:

#include<iostream>
#include<string>
using namespace std;
#define MAXLEN 100 //定義順序表的最大長度
/**************順序表的定義部分*****************/ 
struct DATA
{
 string key; //結(jié)點的關(guān)鍵字 
 string  name;
 int age;
};
struct SLType //定義順序表結(jié)構(gòu) 
{
 DATA ListData[MAXLEN+1];//保存順序表的結(jié)構(gòu)數(shù)組
 int ListLen;   //順序表已存結(jié)點的數(shù)量 
}; 
/************順序表的初始化函數(shù)*****************/ 
void SLInit(SLType * SL) //初始化順序表
{
 SL->ListLen=0; 
} 
/***********計算線性表的長度*******************/
int SLLenght(SLType *SL)
{
 return(SL->ListLen); //返回順序表的元素數(shù)量 
} 
/*********插入結(jié)點*******************************/
int SLInsert(SLType *SL,int n,DATA data)
{
 int i;
 if(SL->ListLen>=MAXLEN) //順序表結(jié)點數(shù)量已超過最大數(shù)量
 {
  cout<<"順序表已滿，不能插入結(jié)點！"<<endl;
  return 0;   //返回0表示插入不成功 
 } 
 if(n<1||n>SL->ListLen) //插入結(jié)點的序號不合法 
 {
  cout<<"插入序號錯誤！"<<endl;
  return 0;
 }
 for(i=SL->ListLen;i>=n;i--) //將順序表中的數(shù)據(jù)向后移動
 {
  SL->ListData[i+1]=SL->ListData[i];
 }
 SL->ListData[n]=data;
 SL->ListLen++;
 return 1;     //成功插入，返回1 
}
/***********************追加結(jié)點*************************/ 
int SLAdd(SLType * SL,DATA data)
{
 if(SL->ListLen>=MAXLEN)
 {
  cout<<"順序表已滿，不能再添加結(jié)點了！"<<endl;
  return 0;
 } 
 SL->ListData[++SL->ListLen]=data;
 return 1;
}
/***********************刪除結(jié)點*************************/ 
int SLDelete(SLType *SL,int n) //刪除順序表中的數(shù)據(jù)元素
{
 int i;
 if(n<1||n>SL->ListLen) //刪除結(jié)點的序號不合法 
 {
  cout<<"刪除序號錯誤！"<<endl;
  return 0;
 }
 for(i=n;i<SL->ListLen;i++)//將順序表中的數(shù)據(jù)向前移動 
 {
  SL->ListData[i]=SL->ListData[i+1]; 
 } 
 SL->ListLen--;   //順序表元素數(shù)量減1 
 return 1;    //成功刪除返回1 
} 
/*******************按照序號查找結(jié)點********************/
DATA * SLFindByNum(SLType *SL,int n)//根據(jù)序號返回數(shù)據(jù)元素
{
 if(n<1||n>SL->ListLen)   //查詢結(jié)點的序號不合法 
 {
  cout<<"查詢序號錯誤！"<<endl;
  return 0;
 }
 return &(SL->ListData[n]); 
} 
/*******************按照關(guān)鍵字查找結(jié)點********************/
DATA *SLFindByCont(SLType * SL,string name)//按關(guān)鍵字查詢結(jié)點 
{
 int i;
 for(i=1;i<=SL->ListLen;i++)
 {
  if(SL->ListData[i].name==name)//如果找到結(jié)點 
  {
   return &(SL->ListData[i]);
  }
 }
 return 0;      //在整個表中都沒有找到，返回0 
} 
/*******************顯示所有的結(jié)點********************/
void SLALL(SLType *SL)
{
 int i;
 for(i=1;i<=SL->ListLen;i++)
 {
  cout<<"key:"<<SL->ListData[i].key<<",name:"<<SL->ListData[i].name<<",age:"<<SL->ListData[i].age<<endl;
 }
} 
int main()
{
 int i;
 SLType SL; //定義順序表變量 
 DATA data; //定義結(jié)點保存數(shù)據(jù)類型變量 
 DATA *pdata;//定義指向結(jié)點的指針變量
 string name;
 cout<<"順序表操作演示："<<endl;
 SLInit(&SL);//初始化順序表
 do
 { //循環(huán)添加結(jié)點數(shù)據(jù) 
  cout<<"請輸入要添加的結(jié)點（學(xué)號 姓名 年齡）：";
  cin>>data.key>>data.name>>data.age;
  if(data.age)  //若年齡不為0
  {
   if(!SLAdd(&SL,data))//若添加結(jié)點失敗 
   {
    break;   //退出循環(huán) 
   }
  }else
  {
   break;
  } 
 }while(1);
 cout<<"順序表中的結(jié)點順序為：" <<endl;
 SLALL(&SL);    //顯示所有的結(jié)點
 cout<<"請輸入要取出的結(jié)點序號：";
 cin>>i;
 pdata=SLFindByNum(&SL,i);//按序號查找結(jié)點
 if(pdata)
 {
  cout<<"第"<<i<<"個結(jié)點為：key:"<<pdata->key<<",name:"<<pdata->name<<",age:"<<pdata->age<<endl;
 } 
 cout<<"請輸入要查找的姓名：";
 cin>>name;
 pdata=SLFindByCont(&SL,name);
 if(pdata)
 {
  cout<<"key:"<<pdata->key<<",name:"<<pdata->name<<",age:"<<pdata->age<<endl;
 } 
 cout<<"請輸入您要刪除的結(jié)點的序號：";
 cin>>i;
 if(SLDelete(&SL,i))
 {
  cout<<"數(shù)據(jù)刪除成功"<<endl;
  SLALL(&SL); 
 }
 cout<<"請輸入您要插入的結(jié)點的序號：";
 cin>>i;
 cout<<"請輸入第"<<i<<"號結(jié)點的key，name，以及age"<<endl;
 cin>>data.key>>data.name>>data.age;
 if(SLInsert(&SL,i,data))
 {
  cout<<"插入數(shù)據(jù)成功"<<endl;
  SLALL(&SL); 
 } 
 return 0;
}