1.建立单链表结点
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode //建立结点
{
ElemType data;
struct LNode* next;
}LinkNode;
2.建立单链表;
void CreateListF(LinkNode*& L, ElemType a[], int n) //头插法创建单链表
{
LinkNode* s;
L = new LinkNode;
L->next = NULL;
for (int i = 0;i < n;i++)
{
s = new LinkNode;
s->data = a[i];
s->next = L->next;
L->next = s;
}
}
3.判断链表是否为空
bool ListEmpty(LinkNode* L) //判断链表是否为空
{
return(L->next == NULL);
}
4.求链表的长度;
int ListLength(LinkNode* L) //求链表长度
{
int n = 0;
LinkNode* p = L;
while (p->next != NULL)
{
n++;
p = p->next;
}
return n;
}
5.遍历输出链表;
void DispList(LinkNode* L) //遍历输出链表
{
LinkNode* p = L->next;
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
6.找到链表中某个数的值;
bool GetElem(LinkNode* L, int i, ElemType& e) //找到链表中某个数的值
{
int j = 0;
LinkNode* p = L;
if (i <= 0)return false;
while (j < i && p != NULL)
{
j++;
p = p->next;
}
if (p == NULL)
{
return false;
}
else
{
e = p->data;
return true;
}
}
7.输出单链表中某个值所在的位置;
int LocateElem(LinkNode* L, ElemType e) //输出链表中某个值所在的位置
{
int i = 1;
LinkNode* p = L->next;
while (p != NULL && p->data != e)
{
p = p->next;
i++;
}
if (p == NULL)
return 0;
else
return i;
}
8.插入数据元素;
bool ListInsert(LinkNode*& L, int i, ElemType e) //插入数据元素
{
int j = 0;
LinkNode* p = L, * s;
if (i <= 0)return false;
while (j < i - 1 && p != NULL)
{
j++;
p = p->next;
}
if (p == NULL)
return false;
else
{
s = new LinkNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
}
9.删除数据元素;
bool ListDelete(LinkNode*& L, int i, ElemType& e) //删除数据元素
{
int j = 0;
LinkNode* p = L, * q;
if (i <= 0)return false;
while (j < i - 1 && p != NULL)
{
j++;
p = p->next;
}
if (p == NULL)
return false;
else
{
q = p->next;
if (q == NULL)
return false;
e = q->data;
p->next = q->next;
delete q;
return true;
}
}
10.销毁链表;
void DestroyList(LinkNode*& L) //销毁链表
{
LinkNode* p1 = L, * p2 = L->next;
while (p2 != NULL)
{
delete p1;
p1 = p2;
p2 = p1->next;
}
delete p1;
}
11.简单测试;
int main()
{
LinkNode* L;
ElemType a[10] = { 1,2,3,4,5,6,7,8,9,0 };
int n = 10;
CreateListF(L, a, n);
cout << "链表长度为:" << ListLength(L) << endl;
cout << "遍历链表:";
DispList(L);
ElemType e;
GetElem(L, 3, e);
cout << "元素的值为:" << e << endl;
cout << "数e在链表中的位置为:" << LocateElem(L, e);
cout << "插入元素:";
ListInsert(L, 3, e);
cout << "再次遍历链表:";
DispList(L);
}