链表(一)单链表

单链表
1.概念
为了表示每个数据元素a(i)与它下一个元素a(i+1)之间的逻辑关系,对数据元素a(i)来说除了储存储本身的信息之外,还需存储一个表示它下一个元素的信息。这两部分信息组成数据元素a(i)的存储映像,称为节点，它包括两个域：存本身信息的叫数据域,存直接后继位置的叫指针域。n个节点链接成一个链表，即为线性表(a1,a2,a3.....an)的链式存储结构。由于每个节点中只存在一个指针域所以我们称之为单链表或线性链表。
2.特点
1）顺序存取
2）储存数据元素的储存单元可连续可不连续。
3.补充
根据链表节点所含指针个数、指针指向和指针链接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表、和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。
实例
4.单链表的存储结构

typtypedef struct
{
    char no[20];
    char name[20];
    float price;
}Book;
typedef struct LNode
{
  Book data;               //数据域
  struct LNode *next;      //指针域 
}LNode,*LinkList;          //LinkList为指向结构体LNode的指针类型

注：
1）LNode *和LinkList等价。
2)LNode *强调定义链表中的某个节点，如LNode *pp代表指向某个节点的指针。
3)LinkList强调定义链表指向头结点的头指针，如LinkList LL代表头指针简称表L。
5.几个概念区分

首元结点：指向链表中存储第一个数据元素a1的节点。
头结点:为处理方便在单链表第一个节点之前附设的一个节点，他的数据域可以为空。
头指针:指向链表中第一个节点的指针。有头结点则指向头结点，无头结点则指向首元结点。
实例
6-1.简单链表

#include <iostream>
#include <string.h>
#define OK 1
#define ERROR 0
using namespace std;

typedef struct node{

 int data;
 struct node*next;

}node,*Lnode;

void init(Lnode &L)
{
    L=new node;
    L->next = NULL;
}

void add(Lnode &L,Lnode &R,int d)
{
    node *n=new node;
    n->data=d;
    n->next=NULL;
    R->next=n;
    R=n;
}
void display(Lnode L)
{
    node *p=NULL;
    p=L->next;
    while(p)
    {
        cout<<"==>"<<p->data;
        p=p->next;
    }
}
void newlist(Lnode &L,Lnode &R)
{
    int n=1;
    while(n)
    {
    int t;
    cout<<"InPut.";cin>>t;
    add(L,R,t);
    cout<<" Do you want new a node[1/0] agin?"<<endl;
    cin>>n;
    }
}
int main()
{
    Lnode L,R;
    init(L);
    R=L;
    newlist(L,R);
    display(L);
}

6-2.简单图书管理系统

#include <iostream>
#include <string.h>
#define OK 1
#define ERROR 0
using namespace std;
//数据元素
typedef struct
{
    char no[20];
    char name[20];
    float price;
}Book;
//节点
typedef struct LNode
{
  Book data;               //数据域
  struct LNode *next;      //指针域
}LNode,*LinkList;          //LinkList为指向结构体LNode的指针类型
//单链表初始化
int  InitList(LinkList &L)
{
    L = new LNode;  //L指向新生成的头结点
    L->next = NULL; //头结点指针域置空
    return OK;
}
//取值
int GetBook(LinkList L,int i,Book &b)
{
    LNode *p;
    p=L->next;int j=1;  //p指向首元结点，j计数器
    while(p&&j<i)
    {
      p=p->next;
      ++j;
    }
    if(!p||j>i)//该节点不存在或i值不合法
    {
        return ERROR;
    }
    b=p->data;
    return OK;
}
void out_book(Book b);
//查找
LNode *LocateBook(LinkList L,Book b)
{
    LNode *p;
    p = L->next;                           //p指向首元结点
    while(p&&strcmp(p->data.no,b.no)!=0)   //当p不为空且p的数据域不等于b
    {
        p=p->next;                         //指向下一个节点
    }
    return p;                              //p为b的地址,查找失败p为NULL
}

//插入
int ListInsert(LinkList &L,int i,Book b)
{
    LNode *p;
    p=L;int j=0;
    while(p&&(j<i-1))//找到插入位置i的前一个节点
    {
        p=p->next;
        ++j;

    }
    if(!p||j>i-1)    //i>L.length，或i<1
    {
        return ERROR;
    }
    LNode *s=NULL;         //构造新节点s
    s->data = b;
    s->next = p->next;
    p->next = s;
    return OK;
}
//删除
int ListDelete(LinkList &L,int i)
{
    LNode *p;
    p=L;int j=0;
    while((p->next)&&(j<i-1)) //插入有n+1个合法位置删除只有n个，防止引用空指针
    {                         //使用p->next作为判断条件
        p=p->next;
        ++j;
    }
    if(!(p->next)||(j>i-1))
    {
        return ERROR;
    }
    LNode *t;
    t = p->next;
    p->next = t->next;
    delete t;
    return OK;
}
//添加节点（后插法）
int AddNode(LinkList &L,LinkList &R,Book b)
{
  LNode *n= new LNode;      //相当于LNode *n;LNode k;n=&k;
  n->data=b;n->next=NULL;
  R->next=n;                //把新建节点连到尾结点
  R=n;                      //尾指针指向新建节点
  return OK;
}
void in_book(Book &t)
{
  cout<<"
ISBN:";cin>>t.no;cout<<"书名:";cin>>t.name;cout<<"价格:";cin>>t.price;
}
void out_book(Book b)
{
    cout<<"ISBN "<<b.no<<" |书名 "<<b.name<<" |价格 "
    <<b.price<<endl;
    return;
}
void display(LinkList L)
{
    LNode *p=NULL;
    p=L->next;
    while(p)
    {
        out_book(p->data);
        p=p->next;
    }
    return;
}
//创建单链表(后插法)
void CreateList(LinkList &L,LinkList &R)
{
    int n=1;
    while(n)
    {
    Book t;
    cout<<"	[数据录入]"<<endl;
    in_book(t);
    AddNode(L,R,t);
    cout<<"	是[1]否[0]继续?"<<endl;
    cin>>n;
    }
}
//删
void del_book(LinkList &L)
{
    int i;
    cout<<"	[删除数据]
序号:"<<endl;
    cin>>i;
    ListDelete(L,i);
    return;
}
//查
void search_book(LinkList &L)
{
    cout<<"	[查找数据]
ISBN:"<<endl;
    Book b;
    cin>>b.no;
    LNode *p=LocateBook(L,b);
    out_book(p->data);
    return;
}
//改
void edi_book(LinkList &L)
{
    Book b,t;
    cout<<"	[修改数据]
ISBN:"<<endl;
    cin>>b.no;
    LNode *p=LocateBook(L,b);
    in_book(t);
    p->data = t;
    return;
}
void get_book(LinkList &L)
{
    int i;Book g;
    cout<<"	[获取数据]
序号:"<<endl;
    cin>>i;
    GetBook(L,i,g);
    out_book(g);
    return;
}
int main()
{
    //初始化得到空单链表L
    LinkList L,R;
    InitList(L);
    R=L;                      //尾指针R暂指到头结点
    //增
    CreateList(L,R);
    display(L);
    //删
    del_book(L);
    display(L);
    //查
    search_book(L);
    //改
    edi_book(L);
    display(L);
    //取
    get_book(L);
    return 0;
}

7-1.运行结果

7-2.运行结果
增

删

查

改

取

此处按序号取第5个数据，即ISBN为6的数据
8.附:前插法

//创建单链表（前插法）
int CreateList(LinkList &L,Book b)
{
  LNode *n=new LNode;
  n->data=b;
  n->next=L->next;//新建节点插入到头结点之后(即首元结点之前)
  L->next=n;
}