如何在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ù)元素的類型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ù)組，用來存放各個(gè)數(shù)據(jù)結(jié)點(diǎn)。
我們認(rèn)為該順序表是一個(gè)班級(jí)學(xué)生的記錄。其中，key為學(xué)號(hào)，name為學(xué)生的名稱，age為年齡。
因?yàn)閿?shù)組都是從下標(biāo)0開始的，為了使用方便，我們從下標(biāo)1開始記錄數(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來表示結(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ù)量已超過最大數(shù)量
{
cout<<"順序表已滿，不能插入結(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í)候已超過最大數(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<<"順序表已滿，不能再添加結(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)類似，都需要進(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中的位置。如果在線性表中沒有找到值為x的結(jié)點(diǎn)，則返回一個(gè)錯(cuò)誤標(biāo)志。
根據(jù)x的類型不同，查找結(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) //查詢結(jié)點(diǎn)的序號(hào)不合法
{
cout<<"查詢序號(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)行介紹，例如，可以通過key查找學(xué)生的信息。示例代碼如下：
int SLFindByCont(SLType * SL,char *key)//按關(guā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è)表中都沒有找到，返回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ù)量已超過最大數(shù)量
{
cout<<"順序表已滿，不能插入結(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<<"順序表已滿，不能再添加結(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) //查詢結(jié)點(diǎn)的序號(hào)不合法
{
cout<<"查詢序號(hào)錯(cuò)誤！"<<endl;
return 0;
}
return &(SL->ListData[n]);
}
/*******************按照關(guān)鍵字查找結(jié)點(diǎn)********************/
DATA *SLFindByCont(SLType * SL,string name)//按關(guā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è)表中都沒有找到，返回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ù)類型變量
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語言回溯法解八皇后問題，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-12-12
這篇文章主要介紹了C/C++中文件的隨機(jī)讀寫詳解及其作用，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
Qt音視頻開發(fā)之實(shí)現(xiàn)ffmpeg視頻旋轉(zhuǎn)顯示
這篇文章主要為大家詳細(xì)介紹了在Qt音視頻開發(fā)中如何利用ffmpeg實(shí)現(xiàn)視頻旋轉(zhuǎn)顯示，文中的實(shí)現(xiàn)步驟講講清晰，感興趣的小伙伴可以了解一下2023-03-03
C++實(shí)現(xiàn)LeetCode(174.地牢游戲)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(174.地牢游戲),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C語言中的for循環(huán)語句基本語法及使用,本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-06-06
這篇文章主要介紹了C語言泛型編程,針對(duì)泛型的用法做了深入淺出的實(shí)例介紹,是C程序設(shè)計(jì)中非常實(shí)用的技巧,需要的朋友可以參考下2014-09-09
C++聚合關(guān)系類的構(gòu)造函數(shù)的調(diào)用順序詳解
下面小編就為大家?guī)硪黄狢++聚合關(guān)系類的構(gòu)造函數(shù)的調(diào)用順序詳解。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考，一起跟隨小編過來看看吧2016-05-05
C語言庫函數(shù)strcpy的使用及模擬實(shí)現(xiàn)
本文主要介紹了C語言庫函數(shù)strcpy的使用及模擬實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-04-04
這篇文章主要介紹了C與C++之間相互調(diào)用的實(shí)例方法，大家參考使用吧2013-12-12
C++編程中刪除運(yùn)算符與相等運(yùn)算符的使用解析
這篇文章主要介紹了C++編程中刪除運(yùn)算符與相等運(yùn)算符的使用解析,delete和==以及!=運(yùn)算符的使用是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2016-01-01