最近在準(zhǔn)備考研蟹倾，博客的更新沒(méi)有沒(méi)有保障匣缘。學(xué)習(xí)了一點(diǎn)數(shù)據(jù)結(jié)構(gòu)，但書(shū)中多為偽碼體現(xiàn)鲜棠，看了幾遍后仍體會(huì)不到其精要肌厨，私以為實(shí)踐才是最好的老師，so打算開(kāi)坑豁陆，用C++實(shí)現(xiàn)各個(gè)專(zhuān)題內(nèi)容柑爸。比較初級(jí)，關(guān)于其中的一些優(yōu)化和錯(cuò)誤盒音，請(qǐng)dalao積極指正表鳍。感謝。
??除去一些算法基礎(chǔ)知識(shí)及C/C++入門(mén)知識(shí)里逆，首先便是線(xiàn)性表进胯。線(xiàn)性表一般分順序表和鏈表。今天主要先來(lái)實(shí)現(xiàn)下順序表的初始化原押、創(chuàng)建、查找偎血、插入诸衔、刪除。
下列程序筆者在code block運(yùn)行成功
運(yùn)行示例
#include <cstdio>
#include <cstdlib>
#define ElementType int
#define MAXSIZE 1000
#define ERROR -1
/*線(xiàn)性表-順序表-結(jié)構(gòu)體定義*/
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
int Last; /*最后一個(gè)位置下標(biāo)颇玷，用來(lái)計(jì)算順序表的長(zhǎng)度*/
};/*L1,*Ptrl1; 結(jié)構(gòu)體定義方法*/
struct LNode L;
List PtrL = &L;
/*兩種數(shù)據(jù)訪(fǎng)問(wèn)方式 L.Data[i] || PtrL -> Data[i]*/
/*訪(fǎng)問(wèn)順序表長(zhǎng)度 L笨农。Last + 1 || PtrL -> Last + 1*/
/* 初始化 */
List MakeEmpty(){
List PtrL; /*①先定義一個(gè)節(jié)點(diǎn)的指針PrrL*/
PtrL = (List)malloc(sizeof(struct LNode)); /*②用函數(shù)malloc()來(lái)申請(qǐng)一個(gè)節(jié)點(diǎn)的空間，大小為sizeof(struct LNode)*/
PtrL -> Last = -1; /*再?gòu)?qiáng)制轉(zhuǎn)換List型帖渠，即struct LNode*型的指針*/
return PtrL;
}
/* 初始化方式2-使其返回L而非L的地址 */
struct LNode MakeEmpty2(){
struct LNode L;
*PtrL = L; /*malloc返回的必須是指針谒亦，&L不能放在等號(hào)左邊*/
PtrL = (List)malloc(sizeof(struct LNode)); /*故給L定義一個(gè)指針向量Ptrl指向L*/
L.Last = -1;
return L;
}
/* 查找 */
/* 查找X，并返回其存儲(chǔ)位置 */
int Find( List Ptrl, ElementType X )
{
int i = 0;
while( i <= PtrL->Last && PtrL->Data[i]!= X )
i++;
if ( i > Ptrl->Last ) return ERROR; /* 如果沒(méi)找到空郊，返回錯(cuò)誤信息 */
else return i; /* 找到后返回的是存儲(chǔ)位置 */
}
/* 插入 */
/* 在L的指定位置P前插入一個(gè)新元素X份招，注意P是數(shù)組下標(biāo)，從0開(kāi)始 */
bool Insert( List &PtrL, ElementType X, int P ){
int i;
if ( PtrL->Last == MAXSIZE - 1) {
/* 表空間已滿(mǎn)狞甚，不能插入 */
printf("表滿(mǎn)");
return false;
}
if ( P < 0 || P > PtrL->Last + 1) { /* 檢查插入位置的合法性 */
printf("位置不合法");
return false;
}
for( i = PtrL->Last; i >= P; i--)
PtrL->Data[i+1] = PtrL->Data[i]; /* 將位置P及以后的元素順序向后移動(dòng) */
PtrL->Data[P] = X; /* 新元素插入 */
PtrL->Last++; /* Last仍指向最后元素锁摔，長(zhǎng)度+1 */
return true;
}
/* 刪除 */
/* 從L中刪除指定位置P的元素，注意P是數(shù)組下標(biāo)哼审，從0開(kāi)始 */
bool Delete( List &PtrL, int P ){
int i;
if( P < 0 || P > PtrL->Last ) { /* 檢查空表及刪除位置的合法性 */
printf("位置%d不存在元素", P );
return false;
}
for( i = P + 1; i <= PtrL->Last; i++ )
PtrL->Data[i-1] = PtrL->Data[i]; /* 將位置P+1及以后的元素順序向前移動(dòng) */
PtrL->Last--; /* Last仍指向最后元素谐腰，長(zhǎng)度-1 */
return true;
}
int CreatNewList(List &PtrL, int n){/*此處PtrL用引用孕豹，否則無(wú)法真正輸入新表值*/
PtrL = (List)malloc(sizeof(struct LNode));
printf("輸入新順序表表值：");
for( int i = 0; i < n; i++){
scanf("%d",&PtrL->Data[i]);
PtrL->Last++;
}
printf("新順序表表值為：");
for( int i = 0; i < n; i++){
printf("%d",PtrL->Data[i]);
}
printf("\n");
return 1;
}
int main()
{
int n;
int X,Y,Z;
int P;
int findP;
MakeEmpty();
printf("輸入所要?jiǎng)?chuàng)建順序表的位數(shù)：");
scanf("%d",&n);
CreatNewList(PtrL , n);
printf("查找功能：輸入所要查找的順序表值：");
scanf("%d",&X);
findP = Find( PtrL, X );
printf("查找功能：查找到的值的下標(biāo)位于第%d位\n",findP);
printf("插入功能：輸入所要插入的值及下標(biāo)位置：");
scanf("%d %d",&Y,&P);
Insert(PtrL, Y, P);
printf("插入功能：新順序表表值：");
for( int i = 0; i < n + 1; i++){
printf("%d",PtrL->Data[i]);
}
printf("\n");
printf("刪除功能：輸入所要?jiǎng)h除的下標(biāo)位置：");
scanf("%d",&Z);
Delete( PtrL, Z );
printf("刪除功能：新順序表表值：");
for( int i = 0; i < n ; i++){
printf("%d",PtrL->Data[i]);
}
return 0;
}
