数据结构之链表的基本操作
链表节点的数据结构
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode, *LinkList;
此处介绍四种创建链表的方法，本人使用的是第三种，测试函数已经放在了后面，可以直接使用，同时介绍带头结点的链表的基本操作：遍历、插入、获取链表长度、获取特定位置的元素、删除链表。
创建链表的四种方法
第一种创建方法：不带头结点的头插入法创建链表
每创建一个节点，都使得该节点成为链表的头结点，这样头结点不断的向前移动，就可以创建一个没有特定头结点的链表
首先创建的链表节点会成为链表的尾端，最新（最后）创建的链表节点会成为链表的头结点，因此数据的写入是逆序的
void CreateListOne()
{
LinkList Head = (LNode*)malloc(sizeof(LNode));//定义头结点
LNode *p;//定义指针
p = (LNode*)malloc(sizeof(LNode));//为指针分配空间
if (p == NULL)//预设空间分配失败的情况
{
cout << "指针p空间分配失败！" << endl;//空间分配失败的输出
}
cin >> p->data;//输入节点p的data
p->next = Head;//节点p是向前插入的，因此节点p插入后，在指针移动之前节点p是在head前面的
Head = p;//移动head指针，使得节点p成为链表新的头结点
}
第二种创建方法：不带头结点的尾插法创建链表
头结点不动，创建一个尾结点，通过尾结点和节点p的交叉移动实现创建
void CreateListTwo()
{
LinkList Head;
LNode *p, *tail;
tail = Head = NULL;//头结点和尾结点相连，均初始化为null
p = (LNode*)malloc(sizeof(LNode));
if (p == NULL)
{
cout << "指针p空间分配失败！" << endl;//空间分配失败的输出
}
cin >> p->data;//获取节点p的数据域
tail->next = p;//将节点p连接在链表尾部，此时节点p是在链表的尾部，在tail后面
tail = p;//节点p成为链表新的tail
tail->next = NULL;//结束链表，设置链表的tail后为空
}
第三种创建方法：带头结点的头插法创建链表
此处所说的头结点指的是不用于存储数据的节点，它只是个指针节点，可以在该指针内存储一些链表的基本信息，比如，链表的长度
LinkList CreateListThree()
{
LinkList Head = (LNode*)malloc(sizeof(LNode));//给头结点分配空间
LinkList p;//给节点p分配空间
Head->next = NULL;//现在链表只有一个头结点
int NodeNum;
cout << "请输入链表节点个数：";
cin >> NodeNum;
for (int i = 0; i < NodeNum; i++)
{
p = (LNode*)malloc(sizeof(LNode));
cin >> p->data;//输入节点p的数据域
p->next = Head->next;//现在节点p和头节点同时指向链表的第一个节点（除头节点外）
Head->next = p;//头节点指向节点p，使得节点p成为链表除了头结点以外的第一个节点
if (i == 0)
{
p->next = NULL;
}
// cout << "qqdds";
}
// p->next = NULL;
// cout << "fdsfdfsd" << endl;
return Head;
}
第四种创建方法：带头结点的尾插法创建链表
创建尾结点，利用尾结点进行创建
LinkList CreateListFour()
{
LinkList Head = (LNode*)malloc(sizeof(LNode));//给头结点分配空间
LinkList p = (LNode*)malloc(sizeof(LNode));//给节点p分配空间
LinkList tail;//创建链表的尾结点
tail = Head;//此时头尾节点相连，链表为空
int NodeNum;
cout << "请输入链表节点个数：";
cin >> NodeNum;
for (int i = 0; i < NodeNum; i++)
{
cin >> p->data;//填充节点p的数据域
tail->next = p;//此时节点p在尾结点的后面，已经同链表相连
tail = p;//此时节点p成为链表新的尾结点
}
tail->next = NULL;//结束链表
return Head;
}
遍历链表
void PrintLink(LinkList Head)
{
LNode *p;
p = Head->next;
cout << "遍历链表" << endl;
while (p)
{
cout << p->data << endl;
p = p->next;
}
cout << "NULL\n";
}
获取链表的长度
int GetLength(LinkList Head)
{
//cout << "获取链表的长度" << endl;
int Length = 0;//记录链表的长度
LinkList p = (LNode*)malloc(sizeof(LNode));//给节点p分配空间
p = Head->next;
if (Head->next == NULL)
{
cout << "链表的长度（不包含头结点）为：" << Length << endl;
return 0;
}
while (p)
{
// cout << "pppp";
p = p->next;
Length++;
}
cout << "链表的长度（不包含头结点）为：" << Length << endl ;
return Length;
}
向链表中插入数据
void InsertData(LinkList Head)
{
int insertPlace;
LinkList p;
LinkList insertTemp = (LNode*)malloc(sizeof(LNode));//创建需要插入的节点temp
int temp = 1;//用来计数，当该数与最开始输入的数字相等时就插入准备插入的数据
cout << "请输入插入的位置：";
cin >> insertPlace;
cout << endl << "请输入插入的数据：";
cin >> insertTemp->data;
p = Head;
while (p)
{
//cout << "dddd";
if (temp == insertPlace)
{
insertTemp->next = p->next;
p->next = insertTemp;
//cout << "fffff";
break;
}
temp++;
p = p->next;
}
}
获取链表中特定位置的元素
void GetElem(LinkList Head)
{
LNode *p;
int Pointplace;
int temp = 1;
cout << "请输入想要获取的位置：" ;
cin >> Pointplace;
if (Pointplace <= 0 || Pointplace > GetLength(Head))
{
cout << "输入的位置不合法，请重新输入！" << endl;
GetElem(Head);
}
p = Head->next;
while (p)
{
//cout << "bbbbbb" << endl;
if (temp == Pointplace)
{
//cout << "aaaaa";
cout << "链表中第" << Pointplace << "个位置的元素为：" << p->data << endl;
break;
}
temp++;
p = p->next;
}
}
删除整个链表，并释放链表所占空间
void DeleteLinkList(LinkList Head)
{
LNode *temp;//用以删除链表而建立的临时指针，在整个链表删除完毕之前，永远指向当前应当删除的节点的下一个
LinkList p = (LNode*)malloc(sizeof(LNode));//给节点p分配空间
p = Head;
while (p->next != NULL)
{
temp = p;//此时p和temp指向同一个节点
p = p->next;//此时p指向temp的下一个节点
free(temp);//释放temp，此时temp为空
}
cout << "链表删除完毕！";
}
测试
extern LinkList CreateListThree();//带头结点的头插法创建链表
extern LinkList CreateListFour();//带头结点的尾插法创建链表
extern void DeleteLinkList(LinkList Head);//删除链表
extern void PrintLink(LinkList Head);//输出链表
extern int GetLength(LinkList Head); //获取链表的长度
extern void InsertData(LinkList Head);//向链表中插入数据
extern void GetElem(LinkList Head);//获取指定位置的元素
int main()
{
LinkList Head;
//创建链表
Head = CreateListThree();
cout << endl;
//输出链表
PrintLink(Head);
cout << endl;
//获取链表的长度
GetLength(Head);
cout << endl;
/*
//向链表中插入数据，并输出检查
InsertData(Head);
cout << endl;
PrintLink(Head);
cout << endl;
*/
//获取指定位置的元素
GetElem(Head);
cout << endl;
//删除链表
DeleteLinkList(Head);
cout << endl;
system("pause");
return 0;
}
结果
