一、定义说明:
单链表是通过一组任意的存储单元来存储线性表中的数据元素。每个结点都有data数据域(用来存放数据元素)和next指针域(用来存放后继节点的地址)。
对于顺序表,单链表可以解决顺序表需要一整个大量的连续的存储单元的缺点,单链表的元素可以离散地分布在存储空间中,即非随机存取的存储结构,不能直接找到表中某个特定的结点,当查找某个特定的结点时,需要从表头开始一个一个遍历。因为单链表附加了指针域,缺点就是存储空间增大。
单链表有带头结点和不带头结点两种类型。引入头结点的好处:①便于第一个结点的处理:增加头结点后,第一个结点的地址保存在头结点的指针域中,则对链表的第一个元素的操作和其他元素相同,无需进行特殊处理。(若单链表不带头结点,则第一个结点无前驱结点,在其前插入结点和删除该结点操作复杂些。)②便于空表和非空表的统一处理:增加头结点后,无论链表是否为空,头指针都是指向头结点的非空指针。
二、带头结点的程序说明
2.1 单链表的存储结构
typedef struct LNode {
Elemtype data; //数据域
struct LNode* next; //指针域
}LNode, * LinkList;
2.2 初始化
bool Initlist(LinkList &L)
{
//L = (LinkList)malloc(sizeof(LNode)); //c语言定义头结点
L = new LNode; //定义头结点
L->next = NULL; //尾指针为空,头结点指向空
return true;
}
2.3 头插法建立单链表
void List_HeadInsert(LinkList& L)
{
int n; //输入元素的个数
cout << "头插法--请输入元素个数n:" << endl;
cin >> n;
LinkList s; //定义指针变量s
cout << "请依次输入元素:" << endl;
while (n--)
{
s = new LNode; //定义变量结点
cin >> s->data;
s->next = L->next;
L->next = s;
}
}
2.4 尾插法建立单链表
void List_TailInsert(LinkList& L)
{
int n; //输入元素的个数
cout << "尾插法--请输入元素个数n:" << endl;
cin >> n;
LinkList r; //定义一个表尾指针
r = L;
LinkList s;//定义指针变量s
cout << "请依次输入元素:" << endl;
while (n--)
{
s = new LNode;
cin >> s->data;
s -> next = NULL;
r->next = s;
r = s;
}
}
2.5 打印链表
void Print_list(LinkList& L)
{
LinkList s;
s = L->next;
while(s)
{
cout << s->data << " ";
s = s->next;
}
cout << endl;
}
2.6 求链表的长度
int Length_list(LinkList& L)
{
int length=0;
LinkList s;
s = L->next;
while (s)
{
length++;
s = s->next;
}
return length;
}
2.7 按位置序号查找结点
LNode* GetElem(LinkList& L, int i)
{
if (i<1 || i>Length_list(L))
return NULL;
int j = 1;
LNode* p = L->next; //链表第一个结点赋给p,L是头结点
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p; //返回第i个结点的指针,"p != NULL"其实是在和表长对比,但我这里其实不需要
}
2.8 按值查找位置信息
int LocateElem(LinkList& L, Elemtype e)
{
LNode* p = L->next; //第一个结点赋给p;
int j = 1;
while (p != NULL && p->data != e)
{
p = p->next;
j++;
}
return j;
}
2.9在第i个结点之后插入新的结点
bool ListInsert(LinkList& L, int i, Elemtype e)
{
if (i<1 || i>Length_list(L) + 1)
return false; //判断i的合法性
if (i == 1)//这样就能在第1个位置插入结点了
{
LinkList p;
p = new LNode; //创建想要插入的结点信息
p->next = L->next;
p->data = e;
L->next = p;
}
else
{
LinkList s;
s = GetElem(L, i - 1); //查找到第i-1个结点,是查不到第1个位置的
LinkList p;
p = new LNode; //创建想要插入的结点信息
p->next = s->next;
p->data = e;
s->next = p;
}
return true;
}
2.10 删除第i个位置的结点
bool ListDelete(LinkList& L, int i)
{
if (i<1 || i>Length_list(L))
return false;
if (i == 1)
{
LNode* p = L->next;//第一个结点赋给p;
L->next = p->next;
free(p);
}
else
{
LinkList s;
s = GetElem(L, i - 1);//查找到第i-1个结点,是查不到第1个位置的
LinkList p; //被删除的结点
p = s->next;
s->next = p->next;
free(p);
}
return true;
}
2.11单链表的逆置
bool ListReverse(LinkList& L)
{
if (!L->next)
return false; //空链表不需要逆置
LinkList r, p, q; //r代表前驱节点,p当前节点,q后继节点
r = NULL;
p = L->next;
q = p->next; //从单链表的第一个节点开始,沿着链表滑动,直到最后一个节点,逐一反转
while (p)
{
p->next = r;
r = p;
p = q;
if (q) //保证指向后继节点的指针q不会移出表尾
q = q->next;
}
L->next = r; //当从循环出来时说明p为空,则r就是最后一个节点,此时把最后一个节点作为首节点
}
2.12 两个链表的合并
//(11)两个链表的合并,把B有顺序地插入A中(假设A是有顺序的)
void CombineList(LinkList& A, LinkList& B)
{
LinkList q, p, r;
q = A; //q指向A的头指针
p = B->next; //p指向B的第一个结点
while (p)
{
while ((q->next) && (q->next->data < p->data))
{
q = q->next;
} //找到现在的p应该插入到哪的位置
r = p;
p = p->next;
r->next = q->next;
q->next = r;
}
}
2.13 main函数
#include<iostream>
#include"stdlib.h"
using namespace std;
#define Elemtype int
int main()
{
LinkList L;
//(1)初始化链表,形成带有"头节点"的空链表
Initlist(L);
//(2)使用头插法建立链表
List_HeadInsert(L);
Print_list(L);
//(3)使用尾插法建立链表
List_TailInsert(L);
Print_list(L);
//(4)按照序号进行查找
int n1;
cout << "想要查找的位置序号是:" << endl;
cin >> n1;
LinkList p;
p = GetElem(L, n1);
cout << p->data << endl;
//(5)按值查找结点位置信息
int n2;
cout << "想要查找的数值是:" << endl;
cin >> n2;
cout << LocateElem(L,n2) << endl;
//(6)在第i个位置插入结点
int n3;
int n4;
cout << "想要(后插法)插入的位置和值分别是:" << endl;
cin >> n3 >> n4;
ListInsert(L, n3, n4);
Print_list(L);
//(7)在第i个位置插入结点
int n5;
cout << "想要删除的位置分别是:" << endl;
cin >> n5;
ListDelete(L, n5);
Print_list(L);
//(8)链表逆置
ListReverse(L);
Print_list(L);
//(9)合并两个链表
LinkList L1;
Initlist(L1);
List_TailInsert(L1);
cout << "合并两个链表的结果是:" << endl;
CombineList(L, L1);
Print_list(L);
system("pause");
return 0;
}
三、不带头结点的程序说明
如果不带头结点的单链表,则对表头的操作(插入和删除)要特殊处理,例如HeadInsert(头插法创建单链表)每次插入后都要更新头指针,而对于带头结点的单链表,它的头指针指向永远是头结点,只需要修改头结点的后继就可以完成插入。文章来源:https://www.toymoban.com/news/detail-745794.html
3.1 单链表的存储结构
typedef struct LNode {
Elemtype data;
struct LNode* next;
}LNode,*LinkList;
3.2 初始化
bool InitList(LinkList& L)
{
L = new LNode;
L = NULL; //不带头结点,区别:L->next=NULL
return true;
}
3.3 头插法建立单链表
void HeadInsert(LinkList& L)
{
int n;
cout << "请输入插入元素的个数" << endl;
cin >> n;
cout << "请依次输入元素的值" << endl;
LinkList s; //定义指针变量s
while (n--)
{
s = new LNode; //定义变量结点
cin >> s->data;
s->next = L;
L = s;//更新头指针
}
}
3.4 尾插法建立单链表
void TailInsert(LinkList& L)
{
int n;
cout << "请输入插入元素的个数" << endl;
cin >> n;
cout << "请依次输入元素的值" << endl;
LinkList s; //定义指针变量s
LinkList r; //定义一个表尾指针r
r = new LNode;
while (n--)
{
if (L == NULL)
{
s = new LNode;
cin >> s->data;
s->next = L;
L = s; //更新头指针L
r = s; //更新尾指针r
}
else
{
s = new LNode;
cin >> s->data;
s->next = r->next;
r->next = s;
r = s;
}
}
}
3.5 打印链表
void PrintList(LinkList& L)
{
LinkList s;
s = L;
while (s)
{
cout << s->data << " ";
s = s->next;
}
cout << endl;
}
3.6 求链表的长度
int Length_list(LinkList& L)
{
int length = 0;
LinkList s;
s = L;
while (s)
{
length++;
s = s->next;
}
return length;
}
3.7 按位置序号查找结点
LNode* GetElem(LinkList& L, int i)
{
if (i<1 || i>Length_list(L))
return NULL;
int j = 1;
LNode* p = L; //链表第一个结点赋给p
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p; //返回第i个结点的指针,"p != NULL"其实是在和表长对比,但我这里其实不需要
}
3.8 按值查找位置信息
int LocateElem(LinkList& L, Elemtype e)
{
LNode* p = L; //第一个结点赋给p;
int j = 1;
while (p != NULL && p->data != e)
{
p = p->next;
j++;
}
return j;
}
3.9在i位置插入新的结点(方法一)
//(8)在第i个位置插入结点(后插法)
bool ListInsert(LinkList& L, int i, Elemtype e)
{
if (i<1 || i>Length_list(L) + 1)
return false; //判断i的合法性
if (i == 1)//这样就能在第1个位置插入结点了
{
LinkList p;
p = new LNode; //创建想要插入的结点信息
p->next = L;
p->data = e;
L = p; //更新头指针
}
else//不是在第1个位置插入结点
{
LinkList s;
s = GetElem(L, i - 1); //查找到第i-1个结点
LinkList p;
p = new LNode; //创建想要插入的结点信息
p->next = s->next;
p->data = e;
s->next = p;
}
return true;
}
3.10 在i位置插入新的结点(方法二)
//(9)在第i个位置插入结点(前插法)
bool List_HeadInsert(LinkList& L, int i, Elemtype e)
{
if (i<1 || i>Length_list(L) + 1)
return false; //判断i的合法性
LinkList s;
s = GetElem(L, i); //查找到第i个结点
LinkList p;
p = new LNode;
p->next = s->next;
p->data = s->data;//定义一个结点p,复制原本i结点的全部信息
s->next = p;
s->data = e;//再把原本i结点变成插入的新结点的信息
return true;
}
3.11 删除第i个位置的结点
bool ListDelete(LinkList& L, int i)
{
if (i<1 || i>Length_list(L))
return false;
if (i == 1)
{
LNode* p = L;//第一个结点赋给p;
L = p->next; //更新头指针
free(p);
}
else
{
LinkList s;
s = GetElem(L, i - 1);//查找到第i-1个结点,是查不到第1个位置的
LinkList p; //被删除的结点
p = s->next;
s->next = p->next;
free(p);
}
return true;
}
3.13 main函数
#include<iostream>
using namespace std;
#include"stdlib.h"
#define Elemtype int
int main()
{
LinkList L;
InitList(L);
//(1)使用头插法创建链表
//HeadInsert(L);
//PrintList(L);
//(2)使用尾插法创建链表
TailInsert(L);
PrintList(L);
//(3)按照位置序号进行查找
//int n1;
//cout << "想要查找的位置序号是:" << endl;
//cin >> n1;
//LinkList p;
//p = GetElem(L, n1);
//cout << p->data << endl;
//(4)按值查找结点位置信息
//int n2;
//cout << "想要查找的数值是:" << endl;
//cin >> n2;
//cout << LocateElem(L, n2) << endl;
//(5)后插法插入结点
//ListInsert(L, 1, 1);
//PrintList(L);
//(6)前插法插入结点
//List_HeadInsert(L, 1, 3);
//PrintList(L);
//(7)删除结点
ListDelete(L, 1);
PrintList(L);
system("pause");
return 0;
}
四、思考
对于单链表,分为不带头结点和带头结点,有头结点只是可以少一些对于头指针的更新操作,链表的第一个元素和其他元素的处理是通用的,就会方便一点。文章来源地址https://www.toymoban.com/news/detail-745794.html
到了这里,关于数据结构(2)—单链表(带头结点和不带头结点)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!