--------------基本函数和返回类型-------------
bool InitList(Linklist &L); //初始化 bool GetElem(Linklist L, int i, ElemType &e); //取元素 bool DestroyList(Linklist &L); //删除链表 bool ListDelete(Linklist &L, int i, ElemType e); //删除元素 bool ListInsertSort(Linklist &L, ElemType e); //插入元素 bool PrintList(Linklist L); //打印链表 int Listlength(Linklist &L); //链表长度 bool ReverseList(Linklist L); //反转链表
-------------链表的存储结构------------
typedef struct LNode
{
ElemType data;
LNode *next;
}LNode, *Linklist;
---------------链表的初始化--------------
bool InitList(Linklist &L)
{
// 创建一个带头结点的空链表,L 为指向头结点的指针
L = new LNode;
if (!L) return false;
L->next = NULL;
return true;
}
----------------链表的插入------------------
bool ListInsert(Linklist & L, int i, ElemType e)
{
Linklist p, s; int j;
p = L; j = 0;
while (p->next && j < i-1)
{
p = p->next; ++j;
}
s = (LNode *)malloc(sizeof(LNode));
if (!s) return false; // 存储空间分配失败
s->data = e; // 创建新元素的结点
s->next = p->next;
p->next = s; // 修改指针
return true;
}
-----------------链表结点的删除---------------
bool ListDelete(Linklist & L, int i, ElemType e)
{//i为链表删除的第i个结点，e为删除结点中返回的值
Linklist p, q; int j;
p = L; j = 0;
while (p->next && j < i - 1)
{// 寻找第i个结点，并令p指向其前驱
p = p->next; ++j;
}
if (!(p->next) || j > i - 1) return false; // 删除位置不合理
q = p->next; p->next = q->next;// 修改指针
free(q);// 释放结点空间
return true;
}
-------------------打印链表----------------
bool PrintList(Linklist L)
{
Linklist p;
p = L;
while (p->next != NULL)
{
cout << p->next->data << " ";
p = p->next;
}
return true;
}
--------------------链表长度-------------------
int Listlength(Linklist & L)
{
Linklist p; int j=0;
p = L;
while (p != NULL)
{
p = p->next;
j++;
}
return j;
}
---------------------销毁链表--------------------
bool DestroyList(Linklist & L)
{
Linklist p;
while (L)
{
p = L;
L = L->next;
free(p);
} // while
L = NULL;
return true;
}
-------------------获取链表元素-----------------
bool GetElem(Linklist L, int i, ElemType & e)
{
Linklist p; int j;
p = L->next; j = 1;// 变量初始化，p 指向第一个结点
while (p && j< i)
{ // 顺结点的指针向后查找，直至 p 指到第i个结点或 p 为空止
p = p->next; ++j;
}
if (!p || j>i) return false; // 链表中不存在第 i 个结点
e = p->data; // 取到第 i 个元素
return true;
}
--------------------链表反转--------------------
bool ReverseList(Linklist L)
{
Linklist p;
Linklist q;
p = L->next;
while (p->next != NULL)
{//从第二个开始，依次挪到头节点后面
q = p->next;
p->next = q->next;
q->next = L->next;
L->next = q;
}
//PrintList(L);
return L;
}