标签：NULL return LNode int next DuLNode 数据结构
线性表
顺序表
链表
单链表
- 初始化
typedef struct LNode
{
int data;
struct LNode* next;
}LNode, *LinkList;
bool InitLinkList(LinkList &L) //初始化
{
L = new LNode;
if (L == NULL) //内存不足，分配失败
return false;
L->next = NULL;
return true;
}
- 头插法
LinkList CreateList_Head(LinkList &L, int n) //头插法
{
L = new LNode;
L->next = NULL;
for (int i = 0; i < n; i ++ )
{
LNode *p = new LNode;
cin >> p->data;
p->next = L->next;
L->next = p;
}
return L;
}
- 尾插法
LinkList CreateList_Tail(LinkList &L, int n) //尾插法
{
L = new LNode;
L->next = NULL;
LNode *tail = L;
for (int i = 0; i < n; i ++ )
{
LNode *p = new LNode;
cin >> p->data;
tail->next = p;
p->next = NULL;
tail = p;
}
tail->next = NULL;
return L;
}
- 按位查找
LNode* GetElem(LinkList L, int i) //按位查找
{
if (i < 0)
return NULL;
LNode *p = L;
int j = 0;
while (p && j < i)
{
p = p->next;
j ++ ;
}
return p;
}
- 按值查找
LNode* LocateElem(LinkList &L, int e) //按值查找
{
LNode *p = L->next; //首元节点
while (p && p->data != e)
{
p = p->next;
}
return p; //查找成功返回值为e的节点地址p，查找失败p为NULL
}
- 按位插入
bool ListInsert(LinkList L, int i, int e) //按位插入
{
if (i < 1)
return false;
LNode *p;
if (!(p = GetElem(L, i - 1)))
return false;
LNode *s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
- 按位删除
bool ListDelete(LinkList L, int i) //按位删除
{
if (i < 1)
return false;
LNode *p;
if (!(p = GetElem(L, i - 1)))
return false;
if (p -> next == NULL) //第i个节点为空
return false;
LNode *q = p->next;
p->next = q->next;
delete q;
return true;
}
- 遍历
void Print(LinkList L)
{
LNode *p = L->next;
while (p != NULL)
{
if (p->next != NULL)
cout << p->data << " ";
else
cout << p->data;
p = p->next;
}
}
- 判空
bool Empty(LinkList L)
{
if (L -> next == NULL)
return true;
else
return false;
}
双链表
- 初始化
typedef struct DuLNode
{
int data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode, *DuLinkList;
bool InitDuLinkList(DuLinkList &L) //初始化
{
L = new DuLNode; //分配一个头节点
if (L == NULL) //分配失败
return false;
L->prior = NULL; //头节点的前指针永远指向NULL
L->next = NULL; //因为是空表，头节点之后暂时还没有节点
return true;
}
- 头插法
DuLinkList CreateList_Head(DuLinkList &L, int n) //头插法
{
L = new DuLNode;
L->next = NULL;
L->prior = NULL;
for (int i = 0; i < n; i ++ )
{
DuLNode *p = new DuLNode;
cin >> p->data;
if (L->next == NULL) //插入第一个节点与插入其他节点的方法不一样
{
L->next = p;
p->prior = L;
p->next = NULL;
}
else
{
p->next = L->next;
L->next->prior = p;
L->next = p;
p->prior = L;
}
}
return L;
}
- 尾插法
DuLinkList CreateList_Tail(DuLinkList &L, int n) //尾插法
{
L = new DuLNode;
L->next = NULL;
L->prior = NULL;
DuLNode *tail = L;
for (int i = 0; i < n; i ++ )
{
DuLNode *p = new DuLNode;
cin >> p->data;
p->prior = tail;
tail->next = p;
tail = p;
}
tail->next = NULL;
return L;
}
- 按位查找
DuLNode* GetElem(DuLinkList L, int i) //按位查找
{
if (i < 0) return NULL;
DuLNode *p = L;
int j = 0;
while (p && j < i)
{
p = p->next;
j ++ ;
}
return p;
}
- 按值查找
DuLNode* LocateElem(DuLinkList L, int e) //按值查找
{
DuLNode *p = L->next;
while (p && p->data != e)
{
p = p->next;
}
return p;
}
- 按位插入
bool ListInsert(DuLinkList &L, int i, int e) //按位插入
{
if (i < 1)
return false;
DuLNode *p;
if (!(p = GetElem(L, i))) //第i个元素不存在
return false;
DuLNode *s = new DuLNode;
s->data = e;
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;
return true;
}
- 按位删除
bool ListDelete(DuLinkList &L, int i) //按位删除
{
if (i < 1)
return false;
DuLNode *p;
if (!(p = GetElem(L, i))) //第i个元素不存在
return false;
p->prior->next = p->next;
if (p->next != NULL)
p->next->prior = p->prior;
delete p;
return true;
}
- 遍历
void Print(DuLinkList L)
{
DuLNode *p = L->next;
while (p != NULL)
{
if (p->next != NULL)
cout << p->data << " ";
else
cout << p->data;
p = p->next;
}
}
- 判空
bool Empty(DuLinkList L) //判断空表
{
if (L->next == NULL) return true;
else return false;
}
循环链表
标签：NULL,
return,
LNode,
int,
next,
DuLNode,
数据结构
From： https://www.cnblogs.com/lhycoder/p/data_structure.html