C++數(shù)據(jù)結(jié)構(gòu)之單鏈表的實現(xiàn)

第C++數(shù)據(jù)結(jié)構(gòu)之單鏈表的實現(xiàn)structLNode*next;//結(jié)點的指針域

}LNode,*LinkList;//LinkList為指向結(jié)構(gòu)體LNode的指針類型

//***********************單鏈表的基本操作函數(shù)******************

//單鏈表的初始化

voidInitList(LinkListL)

//構(gòu)造一個空的單鏈表

L=newLNode;

L-next=NULL;

//單鏈表的創(chuàng)建

voidCreateList_H(LinkListL)//前插法創(chuàng)建單鏈表

//創(chuàng)建一個長度為n的單鏈表L,逆序位插入

intn;

LNode*p;

cout"請輸入創(chuàng)建的單鏈表長度："endl;

cinn;

for(inti=0;ii++)

p=newLNode;

cout"請輸入插入的第"i+1"個數(shù)據(jù)值"endl;

cinp-data;

p-next=L-next;

L-next=p;

voidCreateList_R(LinkListL)//后插法創(chuàng)建單鏈表

//創(chuàng)建一個長度為n的單鏈表L,正序位插入

intn;

LNode*p,*r;

r=L;//尾指針r指向頭結(jié)點

cout"請輸入創(chuàng)建的單鏈表長度："endl;

cinn;

for(inti=0;ii++)

p=newLNode;

cout"請輸入插入的第"i+1"個數(shù)據(jù)值"endl;

cinp-data;

p-next=NULL;

r-next=p;

r=p;

//單鏈表的插入

boolListInsert(LinkListL,inti,ElemTypee)

//在帶頭結(jié)點的單鏈表L的第i個結(jié)點前插入新結(jié)點

LinkListp=L;

LNode*s;

intj=0;

while(pji-1)//p指向第i-1個結(jié)點

p=p-next;

j++;

if(!p||i1)//i大于表長+1或小于1，插入位置不合法

returnfalse;

s=newLNode;

s-data=e;

s-next=p-next;

p-next=s;

returntrue;

//單鏈表的刪除

boolListDelete(LinkListL,inti,ElemTypee)

//將單鏈表的第i個結(jié)點刪除

LinkListp=L;

LNode*q;

intj=0;

while(p-nextji-1)//p指向第i-1個結(jié)點

p=p-next;

j++;

if(!(p-next)||i1)//i大于表長或小于1，刪除位置不合法

returnfalse;

q=p-next;//臨時保存被刪結(jié)點的地址以備釋放

p-next=q-next;

e=q-data;//保存被刪結(jié)點的數(shù)據(jù)

deleteq;//釋放被刪結(jié)點的空間

returntrue;

//單鏈表的取值

boolGetElem(LinkListL,inti,ElemTypee)

//獲取單鏈表中第i個結(jié)點的數(shù)據(jù)

LinkListp=L;

intj=0;

while(p-nextji-1)//p指向第i-1個結(jié)點

p=p-next;

j++;

if(!(p-next)||i1)//i大于表長或小于1，第i個結(jié)點不存在

returnfalse;

e=p-next-data;//獲取第i個結(jié)點的數(shù)據(jù)

returntrue;

//單鏈表的查找

boolLocateElem(LinkListL,LNode*p,ElemTypee)

//在單鏈表中查找第一個數(shù)據(jù)為e的結(jié)點

p=L-next;//p指向首元結(jié)點

while(pp-data!=e)

p=p-next;

if(p)

returntrue;

returnfalse;

//*********************************單鏈表的基本功能函數(shù)******************************

//1、插入

voidListInsert(LinkListL)

ElemTypee;

inti;

boolflag;

cout"請輸入要插入的數(shù)據(jù)："endl;

cine;

cout"請輸入要插入的位置："endl;

cini;

flag=ListInsert(L,i,e);

if(flag)

cout"插入成功!"endl;

else

cout"位置不對，插入失??！"endl;

//2、刪除

voidListDelete(LinkListL)

ElemTypee;

inti;

boolflag;

cout"請輸入要刪除數(shù)據(jù)的位置："endl;

cini;

flag=ListDelete(L,i,e);

if(flag)

cout"刪除成功，刪除的數(shù)據(jù)為："eendl;

else

cout"位置不對，刪除失敗！"endl;

//3、取值

voidGetElem(LinkListL)

ElemTypee;

inti;

boolflag;

cout"請輸入要獲取數(shù)據(jù)的位置："endl;

cini;

flag=GetElem(L,i,e);

if(flag)

cout"獲取的數(shù)據(jù)為："eendl;

else

cout"位置不對，獲取數(shù)據(jù)失??！"endl;

//4、查找

voidLocateElem(LinkListL)

ElemTypee;

LNode*p=NULL;

boolflag;

cout"請輸入要查找的數(shù)據(jù)："endl;

cine;

flag=LocateElem(L,p,e);

if(flag)

cout"查找成功，該數(shù)據(jù)的地址為："pendl;

else

cout"查找失??！"endl;

//5、判空

voidListEmpty(LinkListL)

if(L-next)

cout"鏈表不為空！"endl;

else

cout"鏈表為空！"endl;

//6、求長

voidListLength(LinkListL)

LinkListp=L-next;//p指向第一個結(jié)點

inti=0;

while(p)//遍歷單鏈表，統(tǒng)計結(jié)點數(shù)

i++;

p=p-next;

cout"鏈表的長度為："iendl;

//7、清空

voidClearList(LinkListL)

LNode*p,*q;

p=L-next;

while(p)//從首元結(jié)點開始，依次刪除

q=p-next;

deletep;

p=q;

L-next=NULL;//頭結(jié)點指針域置空

//8、銷毀

voidDestroyList(LinkListL)

LNode*p;

while(L)//從頭結(jié)點開始依次刪除

p=L;

L=L-next;

deletep;

//9、打印

voidPrintList(LinkListL)

LinkListp=L-next;//p指向第一個結(jié)點

inti=0;

while(p)//遍歷單鏈表

i++;

cout"鏈表第"i"個數(shù)據(jù)為："p-dataendl;

p=p-next;

voidmenu()

cout"***************************************************************************"endl;

cout"***********************************1、插入*********************************"endl;

cout"***********************************2、刪除*********************************"endl;

cout"***********************************3、取值*********************************"endl;

cout"***********************************4、查找*********************************"endl;

cout"***********************************5、判空*********************************"endl;

cout"***********************************6、求長*********************************"endl;

cout"***********************************7、清空*********************************"endl;

cout"***********************************8、銷毀*********************************"endl;

cout"***********************************9、打印*********************************"endl;

cout"***********************************0、退出*********************************"endl;

cout"***************************************************************************"endl;

intmain()

LinkListL;

InitList(L);

intselect;

cout"請先創(chuàng)建單鏈表：1、前插法！2、后插法！"endl;

cinselect;

switch(select)

case1://插入

CreateList_H(L);

system("pause");//按任意鍵繼續(xù)

break;

case2://刪除

CreateList_R(L);

system("pause");

break;

default:

cout"輸入有誤,創(chuàng)建失??！"endl;

system("pause");

break;

while(1)

system("CLS");//清屏操作

menu();

cout"請輸入菜單序號："endl;

cinselect;

switch(select)

case1://插入

ListInsert(L);

system("pause");//按任意鍵繼續(xù)

break;

case2://刪除

ListDelete(L);

system("pause");

break;

case3://取值

GetElem(L);

system("pause");

break;

case4://查找

LocateElem(L);