链表的故事导入

坐在屏幕前，看着满屏幕的星光，Jack 限入了沉思，做为一个程序员，直觉告诉他，他总感觉到使用顺序表存储运动中的星星状态虽然没有什么不妥，但是，每次移除一颗星星导致其后的所有元素都向前移动并不是一种高效的做法，如果不止几十颗星星，而是有成千上万颗星星，每删除一颗，无异于是对数据进行乾坤大挪移(同样，插入也是如此)... ...

有没有一种方法，可以让删除或插入尽可能少的移动数据？

Jack 突然想到电影《龙之吻》中主人公刘剑（李连杰饰）取枪的场景，第一个柜子里虽然没有枪，但是有放枪柜子的地址（编号），那无论是哪个柜子放枪，我们只要知道了它的地址，就都可以取到枪。。。

即是说，无论我增加间接取枪的柜子数还是减少间接取枪的柜子数，我们只需要控制好箱子里存储的柜子地址，就可以在不移动任何箱子的情况下增删柜子数:

链表的原理

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不必须相邻，那么怎么表示逻辑上的相邻关系呢？可以给每个元素附加一个指针域，指向下一个元素的存储位置。如图所示：

从图中可以看出,每个结点包含两个域：数据域和指针域，指针域存储下一个结点的地址，因此指针指向的类型也是结点类型链表的核心要素：

Ø 每个节点由数据域和指针域组成 Ø 指针域指向下一个节点的内存地址

其结构体定义：

Typedef struct LinkNode

{

ElemType data;

struct LinkNode *next;

}LinkList, LinkNode;

单链表的概念

链表的节点均单向指向下一个节点，形成一条单向访问的数据链

单链表的初始化

typedef struct _LinkNode {
int data; //结点的数据域
struct _LinkNode *next; //结点的指针域 }LinkNode, LinkList; //链表节点、链表
bool InitList(LinkList* &L)//构造一个空的单链表L
{
L=new LinkNode; //生成新结点作为头结点，用头指针L指向头结点 if(!L)return false; //生成结点失败 L->next=NULL; //头结点的指针域置空
return true;
}

单链表增加元素前插法

//前插法
bool ListInsert_front(LinkList* &L, LinkNode * node){ if(!L || !node ) return false;
node->next = L->next; L->next = node; return true;
}

尾插法

//尾插法
bool ListInsert_back(LinkList* &L, LinkNode *node){ LinkNode *last = NULL; if(!L || !node ) return false;
//找到最后一个节点
last = L;
while(last->next) last=last->next;
//新的节点链接到最尾部
node->next = NULL; last->next = node; return true;
}

任意位置插入

//任意位置插法
bool LinkInsert(LinkList* &L, int i, int &e)//单链表的插入
{
//在带头结点的单链表L中第i个位置插入值为e的新结点 int j;
LinkList *p, *s;
p=L; j=0;
while (p&&j<i-1) //查找第i-1个结点，p指向该结点
{ p=p->next; j++;
}
if (!p || j>i-1){//i＞n+1或者i＜1 return false;
}
s=new LinkNode; //生成新结点 s->data=e; //将新结点的数据域置为e s->next=p->next; //将新结点的指针域指向结点ai
p->next=s; //将结点p的指针域指向结点s
return true;
}

单链表的遍历

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

单链表获取元素

bool Link_GetElem(LinkList* &L, int i, int &e)//单链表的取值
{
//在带头结点的单链表L中查找第i个元素
//用e记录L中第i个数据元素的值
int j; LinkList* p;
p=L->next;//p指向第一个结点， j=1; //j为计数器
while (j<i && p) //顺链域向后扫描，直到p指向第i个元素或p为空
{
p=p->next; //p指向下一个结点
j++; //计数器j相应加1
}
if (!p || j>i){ return false; //i值不合法i＞n或i<=0
}
e=p->data;            //取第i个结点的数据域
return true;
}

单链表查找元素

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

单链表删除元素

bool LinkDelete(LinkList* &L, int i) //单链表的删除
{
//在带头结点的单链表L中，删除第i个位置
LinkList *p, *q; int j; p=L; j=0;
while((p->next)&&(j<i-1)) //查找第i-1个结点，p指向该结点
{ p=p->next; j++;
}
if (!(p->next)||(j>i-1))//当i>n或i<1时，删除位置不合理 return false;
q=p->next; //临时保存被删结点的地址以备释放空间
p->next=q->next; //改变删除结点前驱结点的指针域11
delete q; //释放被删除结点的空间
return true; }

单链表销毁

void LinkDestroy(LinkList* &L) //单链表的销毁
{
//定义临时节点p指向头节点
LinkList *p = L; cout<<"销毁链表!"<<endl;
while(p)
{
L=L->next; //L指向下一个节点
cout<<"删除元素: "<<p->data<<endl; delete p; //删除当前节点
                  p=L;       //p 移向下一个节点
}
}

完整代码实现：

//查找元素还有问题
#include <iostream>
#include <windows.h>
using namespace std;
typedef struct _linklist
{
  int data; //数据域
  struct _linklist* next; //指针域
}linklist, linknode;
//初始化链表
bool initlink(linklist*& l)
{
  l = new linknode;
  if (!l)
  {
    return false;
  }
  l->next = null;
  return true;
}
bool linkinsert_front(linklist*& l, linknode* node)
{
  linklist* q = null;
  q = l;
  if (!l || !node)
  {
    return false;
  }
  while (q->next)
  {
    q = q->next;
  }
  node->next = null;
  q->next = node;
  return true;
}
bool linkinset_back(linklist*& l, linknode* node)
{
  linklist* q = null;
  q = l;
  if (!l || !node)
  {
    return false;
  }
  while (q->next)
  {
    q = q->next;
  }
  node->next = null;
  q->next = node;
  return true;
}
//在任意位置插入元素
bool linkinset_elem(linklist*& l, int i, int& e)
{
  int j = 0;
  linklist* q = l, * p = null;
  p = new linknode;
  if (!l)
  {
    return false;
  }
  while (!q || (j < i - 1))
  {
    q = q->next;
    j++;
  }
  if (!q || (j > (i - 1)))
  {
    return false;
  }
  p->data = e;
  p->next = q->next;
  q->next = p;
  return true;  
}
bool seekelem(linklist*& l, int i, int &e)
{
  int j = 1;
  linklist* q = null;
  q = l->next;
  if (!l)
  {
    return false;
  }
  while (!q || (j < i))
  {
    q = q->next;
    j++;
  }
  if (!q || (j > i))
  {
    return false;
  }
  e = q->data;
  return true;
}
bool seeklocation(linklist*& l, int &i, int e)
{
  int j = 1;
  linklist* q = null;
  q = l->next;
  if (!l)
  {
    return false;
  }
  while (!q || (q->data != e))
  {
    q = q->next;
    j++;
  }
  if (!q )
  {
    return false;
  }
  i = j;
  return true;
}
bool linkdelete_elem(linklist*& l, int i)
{
  int j = 0;
  linklist* q = null, * p = null;
  q = l;
  if (!l)
  {
    return false;
  }
  while (!q || (j < i-1))
  {
    q = q->next;
    j++;
  }
  if (!q || (j > i))
  {
    return false;
  }
  p = q->next;
  q->next = p->next;
  delete p;
  return true;
}
void destroylink(linklist*& l)
{
  linklist* q = l;
  cout << "\n单链表销毁\n";
  while (!q)
  {
    l = l->next;
    q = l;
    delete q;
  }
}
void linkprint(linklist*& l)
{
  linklist* q = null;
  q = l->next;
  while (q)
  {
    cout << q->data << " ";
    q = q->next;
  }
}
int main(void)
{
  linklist* l = null;
  linknode* x = null, * q = null;
  //初始化单链表
  initlink(l);
  //前插
  int n;
  cout << "请输入想要插入的数据个数：";
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    x = new linknode;
    cin >> x->data;
    linkinsert_front(l, x);
  }
  linkprint(l);
  cout << endl;
  //尾插
  int z;
  cout << "请输入想要插入的数据个数：";
  cin >> z;
  for (int i = 0; i < z; i++)
  {
    q = new linknode;
    cin >> q->data;
    linkinset_back(l, q);
  }
  linkprint(l);
  //任意位置插入元素
  cout << "\n请输入你想插入的元素：";
  cin >> n;
  linkinset_elem(l, 3, n);
  linkprint(l);
  //查找指定位置的元素
  int element = 0;
  cout << "\n请输入你想要查找的位置：";
  cin >> n;
  seekelem(l, n, element);
  cout << "查找的元素为：" << element << endl;
  //查找指定元素的位置
  cout << "请输入你要查找的元素：";
  int x = 0;
  cin >> n;
  seeklocation(l, x, n);
  cout << "查找的元素位置为：" << x << endl;
  //删除指定位置的元素
  cout << "请输入你想要删除元素的位置：";
  cin >> n;
  linkdelete_elem(l, n);
  linkprint(l);
  //销毁单链表
  destroylink(l);
  system("pause");
  return 0;
}

数据结构— —单链表