单链表

  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;
}