投稿
  1. 高性能架构探索首页
  2. C/C++

线性表

admin • • C/C++ • 阅读 191

线性表

顺序表

sequence_list.hpp

#include <iostream>
using namespace std;

/*
#define是C语言中定义的语法，是预处理指令，在预处理时进行简单而机械的字符串替换，
不作正确性检查，只有在编译已被展开的源程序时才会发现可能的错误并报错。

typedef是关键字，在编译时处理，有类型检查功能。它在自己的作用域内给一个已经存在的类型一个别名，
但不能在一个函数定义里面使用typedef。用typedef定义数组、指针、结构等类型会带来很大的方便，不仅使程序书写简单，也使意义明确，增强可读性
*/

#define MAXSIZE 10000

typedef int elementType;

/*
typedef struct LNode *list 表示定义了一个别名list，list代表 struct LNode *类型的别名，
它是一个指针类型。list a，就是定义了一个struct LNode *类型的变量a
*/
typedef struct LNode *SqList;

//status枚举表示函数的执行状态，对于没有返回值的函数默认返回一个status
enum status{OK = 1 , ERROR = 0};

//--------------------顺序表的存储结构--------------------//
struct LNode 
{
    elementType Data[MAXSIZE];
    //最后一个元素的下标
    int Last;
};

//----------------------------------------初始化顺序表----------------------------------------//
status InitList(SqList &L)
{
    //1.分配内存
        //malloc(内存大小)函数
        //作用：分配一块连续的内存
        //返回值：返回一个无类型指针，需要强制转换为Sqlist类型指针
    L = (SqList)malloc(sizeof(struct LNode));
    //2.初始化数据
    L->Last = -1;

    return OK;
}

//----------------------------------------插入数据----------------------------------------//
status ListInsert(SqList &L, int index , elementType newElem)
{
    //eg：Last为2，index最大可为3，即向表尾插入
    if(index < 0 || index > (L->Last)+1)
    {
        cout << "下标越界" << endl;
        return ERROR;
    }

    //(L->Last)+1即为表长
    if((L->Last)+1 == MAXSIZE)
    {
        cout << "顺序表已满不可插入" << endl;
        return ERROR;
    }

    //如果在表尾插入
    if(index == (L->Last)+1)
    {
        L->Data[index] = newElem;
        L->Last++;

        return OK;
    }
    else
    {
        //将插入位置及之后元素后移
        for(int j = (L->Last)+1;j > index;j--)
        {
            L->Data[j] = L->Data[j-1];
        }
        //插入新元素
        L->Data[index] = newElem;
        L->Last++;

        return OK;
    }
}

//----------------------------------------根据下标取值----------------------------------------//
elementType GetElem(SqList L, int index)
{
    //eg：Last为2，index最大可为2
    if(index < 0 || index > L->Last)
    {
        cout << "下标越界" << endl;
        return false;
    }
    
    elementType elem = L->Data[index];
    return elem;
}

//----------------------------------------查找是否存在某个元素----------------------------------------//
int LocateElem(SqList L, elementType elem)
{
    //返回表中第一次出现该元素的下标
    for(int i=0;i <= L->Last;i++)
        if(L->Data[i] == elem)  return i;

    return -1;
}

//----------------------------------------删除元素----------------------------------------//
status ListDelete(SqList &L, int index)
{
    if(index < 0 || index > L->Last)
        return ERROR;
    //将该下标之后的元素前移
    for(int j=index+1;j <= L->Last;j++)
        L->Data[j-1] = L->Data[j];

    L->Last--;

    return OK;
}

SqList_Test.cpp

#include <iostream>
#include "sequence_list.hpp"
using namespace std;

void outPutList(SqList L)
{
    cout << "顺序表中的元素为: ";

    for(int i=0;i <= L->Last;i++)
    {
        cout << L->Data[i] << " ";
    }
    cout << endl;
}

int main()
{
    cout << "顺序表测试" << endl;

    SqList L;
    InitList(L);

    cout << "请输入数据,输入 0 以结束" << endl;
    for(int i=0;;i++)
    {
        elementType elem;
        cin >> elem;
        if(elem == 0)
            break;
        else
        {
            ListInsert(L,i,elem);
        }
    }
    
    cout << "您输入了 : ";

    for(int i=0;i <= L->Last;i++)
    {
        cout << L->Data[i] << " ";
    }
    cout << endl;

    cout << "1:插入 " << endl;
    cout << "2:删除" << endl;
    cout << "3:按值查找" << endl;
    cout << "4:按下标查找" << endl;

    while(true)
    {
        int choice = 0;
        int index = -1;
        elementType elem;

        cin >> choice;

        switch (choice)
        {
            case 1:
            {
                cout << "请输入下标: ";
                cin >> index;
                cout << "请输入值: ";
                cin >> elem;
                ListInsert(L,index,elem);
                outPutList(L);
                break;
            }
            case 2:
            {
                cout << "请输入下标: ";
                cin >> index;
                ListDelete(L,index);
                outPutList(L);
                break;
            }
            case 3:
            {
                cout << "请输入要查找的值: ";
                cin >> elem;
                cout << "下标: " <<LocateElem(L,elem) << endl;
                break;
            }
            case 4:
            {
                cout << "请输入要查找的下标: ";
                cin >> index;
                cout << "值为: " << GetElem(L,index) << endl;
                break;
            }

        }
    
    }

    system("pause");
}

image-20220122195528482

链表

link_list.hpp

// 双向循环链表 （double linked list）
#include <iostream>
using namespace std;

typedef int elementType;
typedef struct LinkNode *LinkList;

struct LinkNode
{
    elementType elem;

    struct LinkNode *prior;

    struct LinkNode *next;
};

enum status{OK = 1, ERROR = 0};

//----------------------------------------初始化----------------------------------------//
//初始化头节点,头节点的索引为 0 
status InitList(LinkList &L)
{
    L= new LinkNode;

    //头节点的elem用来储存链表的长度
    L->elem = 0;
    L->prior = L;
    L->next = L;

    return OK;
}

//----------------------------------------获取长度----------------------------------------//
//链表长度(不包含头节点)
int ListLength(LinkList L)
{
    return L->elem;
}

//----------------------------------------取值----------------------------------------//
//按index查找返回值(不允许查询头节点)
elementType GetElem(LinkList L, int index)
{
    //1 <= index <= ListLength(L)
    if(index < 1 || index > ListLength(L))
    {
        cout << "index越界" << endl;
        return ERROR;
    }


    //从头节点的前一个节点开始
    LinkNode *p = L->prior;
    for(int i=1;i<=index;i++)
    {
        if(i == index)
            return p->elem;

        p = p->prior;
    }
}

//----------------------------------------查找----------------------------------------//
//按数值查找返回指针 和前后数据的值
LinkNode *LocateElem(LinkList L, elementType searchElem)
{
    bool flag = false;

    //从头节点的前一个节点开始
    LinkNode *p = L->prior;
    for(int i=1;i <= ListLength(L);i++)
    {
        if(p->elem == searchElem)
        {
            //cout << " " << searchElem << " 之前一个元素为 : " << p->prior->elem << endl;
            //cout << " " << searchElem << " 之后一个元素为 : " << p->next->elem << endl;
            cout << "指针 : ";
            flag = true;
            return p;
        }

        p = p->prior;
    }

    if(flag == false)
    {
        cout << "为查询到该数据" << endl;
        return NULL;
    }
}


//----------------------------------------前插----------------------------------------//
//index前插入数据
status ListFrontInsert(LinkList &L, int index, elementType newElem)
{
    //0 <= index <= ListLength(L)
    //L->elem为链表长度，不包含头节点
    //eg:链表长度为3，则index最大可为3
    if(index < 0 || index > ListLength(L))
    {
        cout << "index越界" << endl;
        return ERROR;
    }

    //从头节点开始
    LinkNode *p = L;
    for(int i=0;i<=index;i++)
    {
        if(i == index)
            break;

        p = p->prior;
    }

    LinkNode *s = new LinkNode;

    s->elem = newElem;

    s->prior = p->prior;
    p->prior->next = s;

    p->prior = s;
    s->next = p;

    //链表长度加一
    L->elem++;

    return OK;
}

//----------------------------------------后插----------------------------------------//
//index后插入数据
status ListRearInsert(LinkList &L, int index, elementType newElem)
{
    //0 <= index <= ListLength(L)
    //L->elem为链表长度，不包含头节点
    //eg:链表长度为3，则index最大可为3
    if(index < 0 || index > ListLength(L))
    {
        cout << "index越界" << endl;
        return ERROR;
    }

    //从头节点开始
    LinkNode *p = L;
    for(int i=0;i<=index;i++)
    {
        if(i == index)
            break;

        p = p->prior;
    }

    LinkNode *s = new LinkNode;

    s->elem = newElem;

    p->next->prior = s;
    s->next = p->next;

    s->prior = p;
    p->next = s;


    //链表长度加一
    L->elem++;

    return OK;
}

//----------------------------------------删除----------------------------------------//
status ListDelete(LinkList &L, int index)
{
    //1 <= index <= ListLength(L)
    if(index < 1 || index > ListLength(L))
    {
        cout << "index越界" << endl;
        return ERROR;
    }

    //从头节点的前一个节点开始
    LinkNode *p = L->prior;
    for(int i=1;i<=index;i++)
    {
        if(i == index)
            break;

        p = p->prior;
    }

    p->prior->next = p->next;
    p->next->prior = p->prior;

    delete p;

    L->elem--;

    return OK;
}

link_list_Test.cpp

#include <iostream>
#include "link_list.hpp"

using namespace std;

void outPutList(LinkList L)
{
    cout << "-----当前链表的情况-----" << endl;
    LinkNode *p = L;
    //(ListLength(L))+1 是包含头节点的长度
    for(int i=0;i < (ListLength(L))+1;i++)
    {
        if(i == 0)
        {
            cout << "链表长度为 : " << p->elem << endl;
            cout << "数据为 : ";
            p = p->prior;
        }
        else
        {
            cout << p->elem << " ";
            p = p->prior;
        }
    }
    cout << endl;
}


int main()
{
    cout << "链表测试" << endl;
    cout << "下标索引从 1 开始" << endl;
    LinkList L;
    InitList(L);

    cout << "请输入数据或输入 0 结束" << endl;
    for(int i=0;;i++)
    {
        elementType elem;
        cin >> elem;

        if(elem == 0)
            break;

        ListFrontInsert(L,i,elem);
    }
    cout << endl;

    outPutList(L);
    cout << endl;

    cout << "1:前-插入 " << endl;
    cout << "2:后-插入 " << endl;
    cout << "3:删除" << endl;
    cout << "4:按值查找" << endl;
    cout << "5:按下标查找" << endl;

    while(true)
    {
        int choice = 0;
        int index = -1;
        elementType elem;

        cin >> choice;

        switch (choice)
        {
            case 1:
            {
                cout << "请输入下标: ";
                cin >> index;
                cout << "请输入值: ";
                cin >> elem;
                ListFrontInsert(L,index,elem);
                outPutList(L);
                break;
            }
            case 2:
            {
                cout << "请输入下标: ";
                cin >> index;
                cout << "请输入值: ";
                cin >> elem;
                ListRearInsert(L,index,elem);
                outPutList(L);
                break;
            }
            case 3:
            {
                cout << "请输入下标: ";
                cin >> index;
                ListDelete(L,index);
                outPutList(L);
                break;
            }
            case 4:
            {
                cout << "请输入要查找的值: ";
                cin >> elem;
                cout << LocateElem(L,elem) << endl;
                break;
            }
            case 5:
            {
                cout << "请输入要查找的下标: ";
                cin >> index;
                cout << "值为: " << GetElem(L,index) << endl;
                break;
            }

        }
    
    }

    system("pause");
}

image-20220125191718823

原文链接: https://www.cnblogs.com/FlyingFishStudio/p/15834903.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    线性表

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/187406

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月12日 上午11:17
下一篇 2023年2月12日 上午11:17

相关推荐