一些概念

一些概念

  • 首元结点:第一个有元素的结点
  • 头结点:一般不放元素,“L”
  • 头指针:指向链表的第一个结点,有头结点则为头结点的指针,反之,指向首元结点的指针

    参考资料:https://www.jianshu.com/p/73d56c3d228c

C++实现

#include<iostream>
#include<string>
#include<iomanip>
#include<stdlib.h>
using namespace std;


typedef struct LNode {
trueint data; //结点的数据域
truestruct LNode *next; //结点的指针域
}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型

bool InitList_L(LinkList &L)//构造一个空的单链表L//结构体指针类型变量做为函数的形式参数
{
L=new LNode; //生成新结点作为头结点,用头指针L指向头结点//变量名 = new 类型
trueif(!L)
return false; //生成结点失败
trueL->next=NULL; //头结点的指针域置空
truereturn true;
}

void CreateList_H(LinkList &L)//前插法创建单链表
{
true//输入n个元素的值,建立到头结点的单链表L
trueint n;
trueLinkList s; //定义一个所建立的结构体指针变量
trueL=new LNode; //生成新结点作为头结点,用头指针L指向头结点
trueL->next=NULL; //先建立一个带头结点的空链表
truecout <<"请输入元素个数n:" << endl;
truecin>>n;
truecout <<"请依次输入n个元素:" <<endl;
truecout <<"前插法创建单链表..." <<endl;
truewhile(n--)
{
truetrues=new LNode; //生成新结点s
truetruecin>>s->data; //输入元素值赋给新结点的数据域
truetrues->next=L->next;
truetrueL->next=s; //将新结点s插入到头结点之后
true}
}

void CreateList_R(LinkList &L)//尾插法创建单链表
{
true//输入n个元素的值,建立带表头结点的单链表L
trueint n;
trueLinkList s, r;
trueL=new LNode;
trueL->next=NULL; //先建立一个带头结点的空链表
truer=L; //尾指针r指向头结点
truecout <<"请输入元素个数n:" <<endl;
truecin>>n;
truecout <<"请依次输入n个元素:" <<endl;
truecout <<"尾插法创建单链表..." <<endl;
truewhile(n--)
{
truetrues=new LNode;//生成新结点
truetruecin>>s->data; //输入元素值赋给新结点的数据域
truetrues->next=NULL;
truetruer->next=s;//将新结点s插入尾结点*r之后
truetruer=s;//r指向新的尾结点s
true}
}

bool GetElem_L(LinkList L, int i, int &e)//单链表的取值
{
true//在带头结点的单链表L中查找第i个元素
true//用e记录L中第i个数据元素的值
trueint j;
trueLinkList p;
truep=L->next;//p指向首元结点
truej=1; //j为计数器
truewhile (j<i && p) //顺链域向后扫描,直到p指向第i个元素或p为空
{
truetruep=p->next; //p指向下一个结点 类似结点的自加
truetruej++; //计数器j相应加1
true}
trueif (!p || j>i)
truetruereturn false; //i值不合法i>n或i<=0
truee=p->data; //取第i个结点的数据域
truereturn true;
}

bool LocateElem_L(LinkList L, int e) //按值查找
{
true//在带头结点的单链表L中查找值为e的元素
trueLinkList p;
truep=L->next;
truewhile (p && p->data!=e)//顺链域向后扫描,直到p为空或p所指结点的数据域等于e
truetruep=p->next; //p指向下一个结点
trueif(!p)
return false; //查找失败p为NULL
return true;
}

bool ListInsert_L(LinkList &L, int i, int e)//单链表的插入
{
true//在带头结点的单链表L中第i个位置插入值为e的新结点
trueint j;
trueLinkList p, s;
truep=L;
truej=0;
truewhile (p&&j<i-1) //查找第i-1个结点,p指向该结点
{
truetruep=p->next;
truetruej++;
true}
trueif (!p || j>i-1)//i>n+1或者i<1
truetruereturn false;
trues=new LNode; //生成新结点
trues->data=e; //将新结点的数据域置为e
trues->next=p->next; //将新结点的指针域指向结点ai
truep->next=s; //将结点p的指针域指向结点s
truereturn true;
}

bool ListDelete_L(LinkList &L, int i) //单链表的删除
{
true//在带头结点的单链表L中,删除第i个位置
trueLinkList p, q;
trueint j;
truep=L;
truej=0;
truewhile((p->next)&&(j<i-1)) //查找第i-1个结点,p指向该结点
true{
truetruep=p->next;
truetruej++;
true}
trueif (!(p->next)||(j>i-1))//当i>n或i<1时,删除位置不合理
truetruereturn false;
trueq=p->next; //临时保存被删结点的地址以备释放空间
truep->next=q->next; //改变删除结点前驱结点的指针域
truedelete q; //释放被删除结点的空间
truereturn true;
}

void Listprint_L(LinkList L) //单链表的输出
{
LinkList p;
p=L->next;
while (p)
{
cout<<p->data<<"\t";
truetruep=p->next;
}
cout<<endl;
}

int main()
{
trueint i,x,e,choose;
trueLinkList L;
truecout << "1. 初始化\n";
truecout << "2. 创建单链表(前插法)\n";
truecout << "3. 创建单链表(尾插法)\n";
truecout << "4. 取值\n";
truecout << "5. 查找\n";
truecout << "6. 插入\n";
truecout << "7. 删除\n";
truecout << "8. 输出\n";
truecout << "0. 退出\n";
truechoose=-1;
truewhile (choose!=0)
{
truetruecout<<"请输入数字选择:";
truetruecin>>choose;
truetrueswitch (choose)
truetrue{
truetruecase 1: //初始化一个空的单链表
truetruetrueif (InitList_L(L))
truetruetruetruecout << "初始化一个空的单链表!\n";
truetruetruebreak;
truetruecase 2: //创建单链表(前插法)
truetruetrueCreateList_H(L);
cout << "前插法创建单链表输出结果:\n";
Listprint_L(L);
truetruetruebreak;
case 3: //创建单链表(尾插法)
truetruetrueCreateList_R(L);
cout << "尾插法创建单链表输出结果:\n";
Listprint_L(L);
truetruetruebreak;
truetruecase 4: //单链表的按序号取值
truetruetruecout << "请输入一个位置i用来取值:";
truetruetruecin >> i;
truetruetrueif (GetElem_L(L,i,e))
{
truetruetruetruecout << "查找成功\n";
truetruetruetruecout << "第" << i << "个元素是:"<<e<< endl;
truetruetrue}
truetruetrueelse
truetruetruetruecout << "查找失败\n\n";
truetruetruebreak;
truetruecase 5: //单链表的按值查找
truetruetruecout<<"请输入所要查找元素x:";
truetruetruecin>>x;
truetruetrueif (LocateElem_L(L,x))
truetruetruetruecout << "查找成功\n";
truetruetrueelse
truetruetruetruecout << "查找失败! " <<endl;
truetruetruebreak;
truetruecase 6: //单链表的插入
truetruetruecout << "请输入插入的位置和元素(用空格隔开):";
truetruetruecin >> i;
truetruetruecin >> x;
truetruetrueif (ListInsert_L(L, i, x))
truetruetruetruecout << "插入成功.\n\n";
truetruetrueelse
truetruetruetruecout << "插入失败!\n\n";
truetruetruebreak;
truetruecase 7: //单链表的删除
truetruetruecout<<"请输入所要删除的元素位置i:";
truetruetruecin>>i;
truetruetrueif (ListDelete_L(L, i))
truetruetruetruecout<<"删除成功!\n";
truetruetrueelse
truetruetruetruecout<<"删除失败!\n";
truetruetruebreak;
truetruecase 8: //单链表的输出
truetruetruecout << "当前单链表的数据元素分别为:\n";
truetruetrueListprint_L(L);
truetruetruecout << endl;
truetruetruebreak;
truetrue}
true}
truesystem("pause");
truereturn 0;
}