如何在C++中建立一個(gè)順序表
準(zhǔn)備數(shù)據(jù)
#define MAXLEN 100 //定義順序表的最大長(zhǎng)度
struct DATA
{
char key[10]; //結(jié)點(diǎn)的關(guān)鍵字
char name[20];
int age;
};
struct SLType //定義順序表結(jié)構(gòu)
{
DATA ListData[MAXLEN+1];//保存順序表的結(jié)構(gòu)數(shù)組
int ListLen; //順序表已存結(jié)點(diǎn)的數(shù)量
};
定義了順序表的最大長(zhǎng)度MAXLEN、順序表數(shù)據(jù)元素的類(lèi)型DATA以及順序表的數(shù)據(jù)結(jié)構(gòu)SLType。
在數(shù)據(jù)結(jié)構(gòu)SLType中，Listen為順序表已存結(jié)點(diǎn)的數(shù)量，也就是當(dāng)前順序表的長(zhǎng)度，ListData是一個(gè)結(jié)構(gòu)數(shù)組，用來(lái)存放各個(gè)數(shù)據(jù)結(jié)點(diǎn)。
我們認(rèn)為該順序表是一個(gè)班級(jí)學(xué)生的記錄。其中，key為學(xué)號(hào)，name為學(xué)生的名稱(chēng)，age為年齡。
因?yàn)閿?shù)組都是從下標(biāo)0開(kāi)始的，為了使用方便，我們從下標(biāo)1開(kāi)始記錄數(shù)據(jù)結(jié)點(diǎn)，下標(biāo)0的位置不可用。
初始化順序表
在使用順序表之前，首先創(chuàng)建一個(gè)空的順序表，也就是初始化順序表。這里，在程序中只需設(shè)置順序表的結(jié)點(diǎn)數(shù)量ListLen為0即可。這樣，后面需要添加的數(shù)據(jù)元素將從順序表的第一個(gè)位置存儲(chǔ)。
示例代碼：
void SLInit(SLType * SL) //初始化順序表
{
SL->Listlen=0;
}
計(jì)算線性表的長(zhǎng)度
計(jì)算線性表的長(zhǎng)度也就是計(jì)算線性表中結(jié)點(diǎn)的個(gè)數(shù)，由于我們?cè)赟LType中定義了ListLen來(lái)表示結(jié)點(diǎn)的數(shù)量，所以我們只需要獲得這個(gè)變量的值即可。
int SLLenght(SLType *SL)
{
return(SL->ListLen); //返回順序表的元素?cái)?shù)量
}
插入結(jié)點(diǎn)
插入節(jié)點(diǎn)就是在線性表L的第i個(gè)位置上插入一個(gè)新的結(jié)點(diǎn)，使其后的結(jié)點(diǎn)編號(hào)依次加1。
這時(shí)，插入一個(gè)新節(jié)點(diǎn)之后，線性表L的長(zhǎng)度將變?yōu)閚+1。插入結(jié)點(diǎn)操作的難點(diǎn)在于隨后的每個(gè)結(jié)點(diǎn)數(shù)據(jù)都要向后移動(dòng)，計(jì)算機(jī)比較大，示例代碼如下：
int SLInsert(SLType *SL,int n,DATA data)
{
int i;
if(SL->ListLen>=MAXLEN) //順序表結(jié)點(diǎn)數(shù)量已超過(guò)最大數(shù)量
{
cout<<"順序表已滿(mǎn)，不能插入結(jié)點(diǎn)！"<<endl;
return 0; //返回0表示插入不成功
}
if(n<1||n>SL->ListLen) //插入結(jié)點(diǎn)的序號(hào)不合法
{
cout<<"插入序號(hào)錯(cuò)誤！"<<endl;
return 0;
}
for(i=SL->ListLen;i>=n;i--) //將順序表中的數(shù)據(jù)向后移動(dòng)
{
SL->ListData[i+1]=SL->ListData[i];
}
SL->ListData[n]=data;
SL->ListLen++;
return 1;
}
在程序中首先判斷順序表結(jié)點(diǎn)數(shù)量時(shí)候已超過(guò)最大數(shù)量，以及插入點(diǎn)的序號(hào)是否正確。前面條件都瞞住以后，便將順序表中的數(shù)據(jù)向后移動(dòng)，同時(shí)插入結(jié)點(diǎn)，并更新結(jié)點(diǎn)數(shù)量ListLen。
追加結(jié)點(diǎn)
追加結(jié)點(diǎn)就是在順序表的尾部插入結(jié)點(diǎn)，因此不必進(jìn)行大量數(shù)據(jù)的移動(dòng)，代碼實(shí)現(xiàn)與插入結(jié)點(diǎn)相比就要簡(jiǎn)單的多。
int SLAdd(SLType * SL,DATA data)
{
if(SL->ListLen>=MAXLEN)
{
cout<<"順序表已滿(mǎn)，不能再添加結(jié)點(diǎn)了！"<<endl;
return 0;
}
SL->ListData[++SL->ListLen]=data;
return 1;
}
刪除結(jié)點(diǎn)
刪除結(jié)點(diǎn)就是刪除線性表L中的第i個(gè)結(jié)點(diǎn)，使得其后的所有節(jié)點(diǎn)編號(hào)依次減1.這是，刪除一個(gè)結(jié)點(diǎn)之后，線性表L的長(zhǎng)度將變?yōu)閚-1。刪除結(jié)點(diǎn)和插入結(jié)點(diǎn)類(lèi)似，都需要進(jìn)行大量數(shù)據(jù)的移動(dòng)。
int SLDelete(SLType *SL,int n) //刪除順序表中的數(shù)據(jù)元素
{
int i;
if(n<1||n>SL->ListLen) //刪除結(jié)點(diǎn)的序號(hào)不合法
{
cout<<"刪除序號(hào)錯(cuò)誤！"<<endl;
return 0;
}
for(i=n;i<SL->ListLen;i++)//將順序表中的數(shù)據(jù)向前移動(dòng)
{
SL->ListData[i]=SL->ListData[i+1];
}
SL->ListLen--; //順序表元素?cái)?shù)量減1
return 1; //成功刪除返回1
}
查找結(jié)點(diǎn)
查找節(jié)點(diǎn)就是在線性表L中查找值為x的結(jié)點(diǎn)，并返回該節(jié)點(diǎn)在線性表L中的位置。如果在線性表中沒(méi)有找到值為x的結(jié)點(diǎn)，則返回一個(gè)錯(cuò)誤標(biāo)志。
根據(jù)x的類(lèi)型不同，查找結(jié)點(diǎn)可以分為：
按照序號(hào)查找結(jié)點(diǎn)
對(duì)于一個(gè)順序表，序號(hào)就是數(shù)據(jù)元素在數(shù)組中的位置，也就是數(shù)組的下標(biāo)標(biāo)號(hào)。按照序號(hào)查找結(jié)點(diǎn)是順序表查找結(jié)點(diǎn)最常用的方法，這是因?yàn)轫樞虮淼拇鎯?chǔ)本身就是一個(gè)數(shù)組，示例代碼如下：
DATA * SLFindByNum(SLType *SL,int n)//根據(jù)呼號(hào)返回?cái)?shù)據(jù)元素
{
if(n<1||n>SL->ListLen) //查詢(xún)結(jié)點(diǎn)的序號(hào)不合法
{
cout<<"查詢(xún)序號(hào)錯(cuò)誤！"<<endl;
return 0;
}
return &(SL->ListData[n]);
}
按照關(guān)鍵字查找結(jié)點(diǎn)
關(guān)鍵字可以是數(shù)據(jù)元素中的任意一項(xiàng)。
這里以key關(guān)鍵字為例進(jìn)行介紹，例如，可以通過(guò)key查找學(xué)生的信息。示例代碼如下：
int SLFindByCont(SLType * SL,char *key)//按關(guān)鍵字查詢(xún)結(jié)點(diǎn)
{
int i;
for(i=1;i<=SL->ListLen;i++)
{
if(strcmp(SL->ListData[i].key,key)==0)//如果找到結(jié)點(diǎn)
{
return i;
}
}
return 0; //在整個(gè)表中都沒(méi)有找到，返回0
}
顯示所有的結(jié)點(diǎn)
示例代碼如下：
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ù)放到一塊，集中展示了一下功能，代碼有些長(zhǎng)，請(qǐng)耐心閱讀^.^
#include<iostream>
#include<string>
using namespace std;
#define MAXLEN 100 //定義順序表的最大長(zhǎng)度
/**************順序表的定義部分*****************/
struct DATA
{
string key; //結(jié)點(diǎn)的關(guān)鍵字
string name;
int age;
};
struct SLType //定義順序表結(jié)構(gòu)
{
DATA ListData[MAXLEN+1];//保存順序表的結(jié)構(gòu)數(shù)組
int ListLen; //順序表已存結(jié)點(diǎn)的數(shù)量
};
/************順序表的初始化函數(shù)*****************/
void SLInit(SLType * SL) //初始化順序表
{
SL->ListLen=0;
}
/***********計(jì)算線性表的長(zhǎng)度*******************/
int SLLenght(SLType *SL)
{
return(SL->ListLen); //返回順序表的元素?cái)?shù)量
}
/*********插入結(jié)點(diǎn)*******************************/
int SLInsert(SLType *SL,int n,DATA data)
{
int i;
if(SL->ListLen>=MAXLEN) //順序表結(jié)點(diǎn)數(shù)量已超過(guò)最大數(shù)量
{
cout<<"順序表已滿(mǎn)，不能插入結(jié)點(diǎn)！"<<endl;
return 0; //返回0表示插入不成功
}
if(n<1||n>SL->ListLen) //插入結(jié)點(diǎn)的序號(hào)不合法
{
cout<<"插入序號(hào)錯(cuò)誤！"<<endl;
return 0;
}
for(i=SL->ListLen;i>=n;i--) //將順序表中的數(shù)據(jù)向后移動(dòng)
{
SL->ListData[i+1]=SL->ListData[i];
}
SL->ListData[n]=data;
SL->ListLen++;
return 1; //成功插入，返回1
}
/***********************追加結(jié)點(diǎn)*************************/
int SLAdd(SLType * SL,DATA data)
{
if(SL->ListLen>=MAXLEN)
{
cout<<"順序表已滿(mǎn)，不能再添加結(jié)點(diǎn)了！"<<endl;
return 0;
}
SL->ListData[++SL->ListLen]=data;
return 1;
}
/***********************刪除結(jié)點(diǎn)*************************/
int SLDelete(SLType *SL,int n) //刪除順序表中的數(shù)據(jù)元素
{
int i;
if(n<1||n>SL->ListLen) //刪除結(jié)點(diǎn)的序號(hào)不合法
{
cout<<"刪除序號(hào)錯(cuò)誤！"<<endl;
return 0;
}
for(i=n;i<SL->ListLen;i++)//將順序表中的數(shù)據(jù)向前移動(dòng)
{
SL->ListData[i]=SL->ListData[i+1];
}
SL->ListLen--; //順序表元素?cái)?shù)量減1
return 1; //成功刪除返回1
}
/*******************按照序號(hào)查找結(jié)點(diǎn)********************/
DATA * SLFindByNum(SLType *SL,int n)//根據(jù)序號(hào)返回?cái)?shù)據(jù)元素
{
if(n<1||n>SL->ListLen) //查詢(xún)結(jié)點(diǎn)的序號(hào)不合法
{
cout<<"查詢(xún)序號(hào)錯(cuò)誤！"<<endl;
return 0;
}
return &(SL->ListData[n]);
}
/*******************按照關(guān)鍵字查找結(jié)點(diǎn)********************/
DATA *SLFindByCont(SLType * SL,string name)//按關(guān)鍵字查詢(xún)結(jié)點(diǎn)
{
int i;
for(i=1;i<=SL->ListLen;i++)
{
if(SL->ListData[i].name==name)//如果找到結(jié)點(diǎn)
{
return &(SL->ListData[i]);
}
}
return 0; //在整個(gè)表中都沒(méi)有找到，返回0
}
/*******************顯示所有的結(jié)點(diǎn)********************/
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é)點(diǎn)保存數(shù)據(jù)類(lèi)型變量
DATA *pdata;//定義指向結(jié)點(diǎn)的指針變量
string name;
cout<<"順序表操作演示："<<endl;
SLInit(&SL);//初始化順序表
do
{ //循環(huán)添加結(jié)點(diǎn)數(shù)據(jù)
cout<<"請(qǐng)輸入要添加的結(jié)點(diǎn)（學(xué)號(hào) 姓名 年齡）：";
cin>>data.key>>data.name>>data.age;
if(data.age) //若年齡不為0
{
if(!SLAdd(&SL,data))//若添加結(jié)點(diǎn)失敗
{
break; //退出循環(huán)
}
}else
{
break;
}
}while(1);
cout<<"順序表中的結(jié)點(diǎn)順序?yàn)椋? <<endl;
SLALL(&SL); //顯示所有的結(jié)點(diǎn)
cout<<"請(qǐng)輸入要取出的結(jié)點(diǎn)序號(hào)：";
cin>>i;
pdata=SLFindByNum(&SL,i);//按序號(hào)查找結(jié)點(diǎn)
if(pdata)
{
cout<<"第"<<i<<"個(gè)結(jié)點(diǎn)為：key:"<<pdata->key<<",name:"<<pdata->name<<",age:"<<pdata->age<<endl;
}
cout<<"請(qǐng)輸入要查找的姓名：";
cin>>name;
pdata=SLFindByCont(&SL,name);
if(pdata)
{
cout<<"key:"<<pdata->key<<",name:"<<pdata->name<<",age:"<<pdata->age<<endl;
}
cout<<"請(qǐng)輸入您要?jiǎng)h除的結(jié)點(diǎn)的序號(hào)：";
cin>>i;
if(SLDelete(&SL,i))
{
cout<<"數(shù)據(jù)刪除成功"<<endl;
SLALL(&SL);
}
cout<<"請(qǐng)輸入您要插入的結(jié)點(diǎn)的序號(hào)：";
cin>>i;
cout<<"請(qǐng)輸入第"<<i<<"號(hào)結(jié)點(diǎn)的key，name，以及age"<<endl;
cin>>data.key>>data.name>>data.age;
if(SLInsert(&SL,i,data))
{
cout<<"插入數(shù)據(jù)成功"<<endl;
SLALL(&SL);
}
return 0;
}
運(yùn)行界面：
相關(guān)文章
C++實(shí)現(xiàn)LeetCode(6.字型轉(zhuǎn)換字符串)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(6.字型轉(zhuǎn)換字符串),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C++ 處理中文符號(hào)實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-01-01
C++實(shí)現(xiàn)String與UF8互轉(zhuǎn)
這篇文章介紹了C++實(shí)現(xiàn)String與UF8互轉(zhuǎn)的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-05-05
C語(yǔ)言使用openSSL庫(kù)AES模塊實(shí)現(xiàn)加密功能詳解
這篇文章主要介紹了C語(yǔ)言使用openSSL庫(kù)AES模塊實(shí)現(xiàn)加密功能,詳細(xì)分析了C語(yǔ)言加密的相關(guān)概念、原理及AES模塊加密具體實(shí)現(xiàn)技巧,需要的朋友可以參考下2017-05-05
C++類(lèi)型轉(zhuǎn)換運(yùn)算符的實(shí)例詳解
這篇文章主要介紹了C++類(lèi)型轉(zhuǎn)換運(yùn)算符的實(shí)例詳解的相關(guān)資料,希望通過(guò)本文大家能夠掌握這部分內(nèi)容，需要的朋友可以參考下2017-09-09
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言數(shù)獨(dú)游戲的求解方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
在編寫(xiě)C語(yǔ)言源代碼時(shí),應(yīng)該多使用注釋,這樣有助于對(duì)代碼的理解,這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中注釋與注意事項(xiàng)的相關(guān)資料,需要的朋友可以參考下2021-09-09
劍指offer之C語(yǔ)言不修改數(shù)組找出重復(fù)的數(shù)字
今天小編就為大家分享一篇關(guān)于劍指offer之C語(yǔ)言不修改數(shù)組找出重復(fù)的數(shù)字，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-02-02
C++程序中使用Windows系統(tǒng)Native Wifi API的基本教程
這篇文章主要介紹了C++程序中使用Windows系統(tǒng)Native Wifi API的基本教程,包括在程序中控制無(wú)線網(wǎng)卡開(kāi)關(guān)的方法,需要的朋友可以參考下2016-03-03
這篇文章主要介紹了C++內(nèi)存分布及用法，從內(nèi)存的基礎(chǔ)概念到內(nèi)存分配進(jìn)行了講解，內(nèi)存是我們開(kāi)發(fā)中最重要的一部分，往往邏輯上的錯(cuò)誤就會(huì)造成內(nèi)存泄漏，導(dǎo)致程序無(wú)法運(yùn)行，下面我們就來(lái)了解文章對(duì)該內(nèi)容的詳細(xì)介紹2022-08-08