1. 首先定义一个单链表结构题

typedef struct LNode
{
  ElemType data;//定义一个自定义类型的变量存放数据
  LNode *Next;//定义一个指向结构体的指针
}LNode,*Linklist;//创建一个结构体指针

*LNode p ==Linklist p

1. 链表的初始化

void init(Linklist &L)
{
    L=new LNode;//为L动态分配一块内存空间
    L->Next=NULL;//将L的指针域设为空
}

1. 图中是用尾插法构建单链表，头插法还请移步头插法

   void created(Linklist &L)
   {
       Linklist p=L;//新创建一个p指针指向头节点L
       for(int i=0;i<20;i++)//循环创建20个节点的单链表
       {
           Linklist q=new LNode;//创建一个新的节点，并用q指针指向这个新的节点
           q->data=i;//将i的值存入q的data域
           q->Next=NULL;//将q的Next指针指向为空
           p->Next=q;//将q/L的尾指针指向新创建的q这个结构体
           p=q;//再将p指向位置移动到q（p指针后移）
       }
   }

   

2. 分别定义两个指针，一个快指针(high)一个慢指针(low)，查找一个有序链表的中间值

   int findmid(Linklist &L)
   {
       Linklist high,low=L;
       while(high->Next != NULL)
       {
           if(high->Next->Next != NULL)
           {
               high = high->Next->Next;//high每次后移两步
               low = low->low;//low指针每次后移一步
           }
        else
           {
               high=high->Next;
           }
       }
       return low->data;
   }

   high指针每次向后移动两步，low指针每次向后移动一步，这样当high指针移动到链表最后面时，恰巧low应该在链表中间位置。

   头插法和尾插法

如果将数据结构的存储方式换为头插法，只需要将created()函数换为：

void creat(Linklist &L){
    Linklist p=L;
    Linklist q=new LNode;
    q->data=0;
    q->Next=NULL;
    p->Next=q;
    for (int i = 1; i < 20; i++)
    {
        /* code */
        Linklist q=new LNode;
        q->data=i;
        q->Next=p->Next;
        p->Next=q;
    }
}

头插法创建一个节点长度为20的有序单链表输出出来的循序则为逆序

而尾插法创建一个节点长度为20的有序单链表输出出来的循序是正序：

链表节点的增、删

创建一个增加节点的函数push()

void push(Linklist &L)
{
    int n,m;
    Linklist p=L;
    cout << "在第几个节点后面增加：" << "\n";
    cin >> n;
    /*先将指针移动到插入节点*/
    for (int i = 0; i < n; i++)
    {
        /* code */
        p=p->Next;
    }
    Linklist q=new LNode;
    cout << "输入数值：" << "\n";
    cin >> m;
    q->data=m;
    q->Next=p->Next;
    p->Next=q;
}

创建一个删除节点的函数deleted()

void deleted(Linklist &L)
{
    int n;
    Linklist p,q;
    p=L;
    cout << "在第几个节点后面删除：" << "\n";
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        /* code */
        p=p->Next;
    }
    q=p->Next;
    p->Next=q->Next;
}

执行了增加节点的函数push()后输出有序链表结果如下图：

执行删除节点函数deleted()后的输出结果如下图：

对比发现增加了一个数值为100的节点，删除了一个数值为4的节点。

创建一个有序链表并快速查找中间值的完整代码：

#include "iostream"
#include <stdlib.h>
using namespace std;
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType; 
typedef struct LNode
{
    ElemType data;
    LNode *next;
}LNode,*LinkList;

Status init(LinkList &L)    //初始化
{
    L=new LNode;
    L->next=NULL;
    return OK;
}

void creat(LinkList &L)    //尾插法建立链表
{
    LinkList p,q=L;
    for(int i=0;i<20;i++)
    {
        p=new LNode;
        p->data=i+1;
        p->next=NULL;
        q->next=p;
        q=p;
    }
}

void show(LinkList L)        //显示链表
{
    LinkList p=L->next;
    while(p)
    {
        cout<<p->data<<"\t"; 
        p=p->next;
    }
    cout<<endl;
}

Status findmid(LinkList L)    //查找中间值
{
    LinkList high,mid;
    ElemType e;
    high=mid=L;
    while(high->next!=NULL)
    {
        if(high->next->next!=NULL)
        {
            high=high->next->next;
            mid=mid->next;
        }
        else
        {
            high=high->next;
        }
    }
    e=mid->data;
    return e;
}

int main()
{    
    LinkList L;
    init(L);
    creat(L);
    cout<<"显示链表："<<endl;
    show(L);
    cout<<"显示中间值："<<endl;
    cout<<findmid(L)<<endl;
    system("pause");
    return 0;
}

首先声明这里说的指针只是为了方便称呼，不是在C/C++中的指针

1. 定义一个队列(线性表的顺序结构)

   typedef struct{
       int ID[10];//每个节点的编号
       int front;//头指针
       int rear;//尾指针
   }Sql;

1. 队列初始化

   void init(Sql *data)
   {
       data->front=data->rear=0;
       for (; data->rear < 10; ++data->rear)//尾指针后移
       {
           /* code */
           data->ID[data->rear]=0;
       }
       //此时头指针在头位，尾指针在尾位
   }对队列赋值

1. 给列表赋值

   void creat(Sql *data)
   {
       int i=1;
       while(data->front!=data->rear)//当头指针后移到尾指针时候循环结束
       {
           data->ID[data->front]=i;
           data->front++;
           i++;
       }
       data->front=0;//把头指针回归到首位
   }

1. 遍历列表输出整个顺序表

   void print(Sql *data)
   {
       while(data->front!=data->rear)
       {
           cout << data->ID[data->front] << "\n";
           data->front++;//头指针后移直至结束
       }
       data->front=0;//头指针回归到原位
   }

输出一个顺序表

#include "iostream"
using namespace std;

typedef struct{
    int ID[10];//每个节点的编号
    int front;//头指针
    int rear;//尾指针
}Sql;

void init(Sql *data)
{
    data->front=data->rear=0;
    for (; data->rear < 10; ++data->rear)
    {
        /* code */
        data->ID[data->rear]=0;
    }
}

void creat(Sql *data)
{
    int i=1;
    while(data->front!=data->rear)
    {
        data->ID[data->front]=i;
        data->front++;
        i++;
    }
    data->front=0;
}

void print(Sql *data)
{
    while(data->front!=data->rear)
    {
        cout << data->ID[data->front] << "\n";
        data->front++;
    }
    data->front=0;
}

int main()
{
    /* code */
    Sql data;
    init(&data);
    creat(&data);
    print(&data);
    return 0;
}