1.2链表线性表[线性结构]

• 不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。

主要操作的实现:

#include <iostream>
#include <algorithm>
using namespace std;
// 1.2链表线性表[线性结构]

typedef int ElementType; // ElementType 可定义为任意类型
typedef struct LNode *List;

struct LNode{
    ElementType Data;   //数据域 
    List Next;   // 下一个链表的地址 
}; 

List L;

List MakeEmpty(); //初始化链表 
int Length(List L);  // 以遍历链表的方法求链表长度 
List FindKth(int K,List L);  // 按序号查找 
List Find(ElementType X,List L);  // 按值查找 
List Insert(ElementType X,int i,List L);  //将 X 插入到第 i-1(i>0) 个结点之后 
List Delete(int i,List L); // 删除第 i(i>0) 个结点 
void Print(List L); // 输出链表元素 


// 初始化链表
List MakeEmpty()
{
    List L = new struct LNode;
    L = NULL;
    return L;
}

// 表长
int Length(List L)
{
    List p = L;
    int cnt = 0;
    while(p)
    {
        p = p->Next;
        cnt++;
    }
    return cnt;
}

// 按序差找
List FindKth(int K, List L)
{
    List p = L;
    int cnt = 1;
    while(p && cnt<K)
    {
        p = p->Next;
        cnt++;
    }
    if(cnt == K)  return p;
    else  return NULL;
}

// 按值差找
List Find(ElementType X, List L)
{
    List p = L;
    int cnt;
    while(p && p->Data!=X)  p = p->Next;
    return p; // 若没有找到 则返回最后一个链表的Next，即NULL
}

/* 插入
1. 用 s 指向一个新的结点
2. 用 p 指向链表的第 i-1 个结点 
3. s->Next = p->Next，将 s 的下一个结点指向 p 的下一个结点 
4. p->Next = s，将 p 的下一结点改为 s   */
List Insert(ElementType X, int i, List L)
{
    List p, s;
    if(i == 1)
    {
        s = new struct LNode;
        s->Data = X;
        s->Next = L;
        return s;
    }
    p = FindKth(i-1, L);
    if(!p)
    {
        cout << "Error" << endl;
        return NULL;
    }
    else
    {
        s = new struct LNode;
        s->Data = X;
        s->Next = p->Next;
        p->Next = s;
        return L;
    }
}

/* 删除
1. 用 p 指向链表的第 i-1 个结点 
2. 用 s 指向要被删除的的第 i 个结点
3. p->Next = s->Next，p 指针指向 s 后面
4. free(s)，释放空间 */
List Delete(int i, List L)
{
    List p, s;
    if(i == 1)
    {
        s = L;
        if(L)  L = L->Next;
        else return NULL;
        delete s;
        return L;
    }
    p = FindKth(i-1, L);
    if(!p || !(p->Next))
    {
        cout << "ERROR!" << endl;
        return NULL;
    }
    else
    {
        s = p->Next;
        p->Next=s->Next;
        delete s;
        return L;
    }
}

// 输出链表元素
void Print(List L)
{
    List t;
    int flag = 1;
    cout << "Present List is: ";
    for(t = L; t; t=t->Next)
    {
        cout << t->Data << ' ';
        flag = 0;
    }
    if(flag)  cout << "NULL" << endl;
}