程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 《數據結構與算法分析》學習筆記(三)——鏈表ADT,數據結構鏈表

《數據結構與算法分析》學習筆記(三)——鏈表ADT,數據結構鏈表

編輯:C++入門知識

《數據結構與算法分析》學習筆記(三)——鏈表ADT,數據結構鏈表


今天簡單學習了下鏈表,待後續,會附上一些簡單經典的題目的解析作為學習的鞏固

首先要了解鏈表,鏈表其實就是由一個個結點構成的,然後每一個結點含有一個數據域和一個指針域,數據域用來存放數據,而指針域則用來存放下一個結點的地址。

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/
 


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved