今天簡單學習了下鏈表,待後續,會附上一些簡單經典的題目的解析作為學習的鞏固
首先要了解鏈表,鏈表其實就是由一個個結點構成的,然後每一個結點含有一個數據域和一個指針域,數據域用來存放數據,而指針域則用來存放下一個結點的地址。
1、先給出結點的定義。
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
ElementType Element;
Position next;
};
2、下面就是一些常見的鏈表的操作
List init(List L);
int IsEmpty(List L);
int IsLast(Position P,List L);
Position Find(ElementType X,List L);
void Delete(ElementType X,List L);
Position FindPrevious(ElementType X,List L);
void Insert(ElementType X,List L,Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
void Print(List L);
3、具體每個的分析啦
List init(List L)
{
L=new struct Node;
L->next =nullptr;
return L;
}
這個是初始化鏈表,鏈表默認有一個空的頭指針,不用來存放數據,只是用來處理一些特殊的情況,個人認為一個結點的代接換取代碼的簡潔是很好的選擇,
int IsEmpty(List L)
{
return L->next==nullptr;
}
這個是判斷鏈表是否為空。
Position Find(ElementType X,List L)
{
Position p;
p=L->next;
while (p!=nullptr&&p->Element!=X )
{
p=p->next;
}
return p;
}
由於鏈表跟指針不同,沒有下標可以直接訪問,所以我們需要一個個的遍歷。
int IsLast(Position P,List L)
{
Position p;
p=L->next;
if (p->next!=nullptr)
{
p=p->next;
}
return p==P;
}
判斷是否是最後一個。
void Delete(ElementType X,List L)
{
Position p,tempCell;
p=FindPrevious(X,L);
if(!IsLast(p,L))
{
tempCell=p->next;
p->next=tempCell->next;
delete tempCell;
}
}
刪除的話重點是別忘記釋放內存
Position FindPrevious(ElementType X,List L)
{
Position p;
p=L;
while (p->next!=nullptr&&p->next->Element!=X)
{
p=p->next;
}
return p;
}
與查找相關
//Insert(after legal Position P)
void Insert(ElementType X,List L,Position P)
{
Position tempCell;
tempCell = new struct Node;
if (tempCell==nullptr)
{
cout<<("Out of space!!")<<endl;
}
tempCell->Element=X;
tempCell->next = P->next;
P->next=tempCell;
}
默認插入在結點的後面
void DeleteList(List L)
{
Position p;
p=L->next;
L->next=nullptr;
while (p!=nullptr)
{
Position pTemp=p->next;
delete p;
p=pTemp;
}
}
清空鏈表
void Print(List L)
{
Position p;
p=L->next;
while(p!=nullptr)
{
cout << p->Element.coe << p->Element.index <<" “;
p=p->next
}
cout<<endl;
}
打印鏈表
不太了解你基礎怎樣,但,《數據結構與算法》許卓群等著,這本書很不錯,是我們大二下學期的教材用書。
另外,如果你C語言不錯的話,《數據結構與算法分析》也相當好,
介紹:《數據結構與算法分析》是《Data Structures and Algorithm Analysis in C》一書第2版的簡體中譯本。原書曾被評為20世紀頂尖的30部計算機著作之一,作者Mark
Allen Weiss在數據結構和算法分析方面卓有建樹,他的數據結構和算法分析的著作尤其暢銷,並受到廣泛好評.已被世界500余所大學用作教材。
在本書中,作者更加精煉並強化了他對算法和數據結構方面創新的處理方法。通過C程序的實現,著重闡述了抽象數據類型的概念,並對算法的效率、性能和運行時間進行了分析。
下面的網站對你的學習也許有幫助~~
參考資料:www.yuanma.org/