首页 > 代码库 > 《数据结构与算法分析》学习笔记（三）——链表ADT
《数据结构与算法分析》学习笔记（三）——链表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;
}
打印链表