数据结构中的线性表代码实现

男娘i 2022-06-06 09:10 188阅读 0赞

# define ElemType int #

# define OK 1 #

# define ERROR 0 #

# include “stdafx.h” #

# include“iostream” 不能用<>奇怪只能用“” #

# include“errors.h”不能用<>奇怪只能用“”你们报错可以在vs用<> #

typedef int Statue;

int const LINST\_INIT\_SIZE = 100;  
int const LISTINCREATMENT = 10;

typedef struct  
\{  
ElemType \*elem;  
int length;  
int listsize;  
\}SqList;

//初始化链表  
Statue InitList\_Sq(SqList &L)  
\{  
//构造空表L  
L.elem = (ElemType *)malloc(LINST\_INIT\_SIZE*  sizeof(ElemType));

//分配成功判断
    
    if (!L.elem) exit(OVERFLOW);
    
    //线性表元素初始为0个
    L.length = 0;
    
    //保存当前线性表的内存容量
    L.listsize = LINST_INIT_SIZE;
    
    return OK;

//线性表的插入  
Statue ListInsert(SqList &L, int i, ElemType e)  
\{  
//在顺序表L中第i个位置插入新元素e

//插入位置判断
    if (i < 1 || i > L.length + 1) return ERROR;
    
    //满判断
    if (L.length >= L.listsize)  perror("OVERFLOW");
    
    //开始腾出待插入位置
    for (int i = L.length - 1; i > i - 1; i--)
    {
        L.elem[i + 1] = L.elem[i];
    }
    
    //开始插入元素e
    L.elem[i - 1] = e;
    
    //线性表元素增加1
    L.length++;
    
    
    return OK;

//线性表的删除  
Statue LinkDelete\_Sq(SqList &L, int i, ElemType &e)  
\{  
//删除位置判断  
if (i < 1 || i > L.length) return ERROR;

//空链表判断
    if (L.length == 0) perror("当前链表为空，无法删除数据。");
    
    //开始保存待删除位置的元素
    e = L.elem[i - 1];
    
    //开始移动删除元素后面的全部数据
    for (int j = i - 1; j < L.length - 1; j++)
    {
        L.elem[j] = L.elem[j + 1];
    }
    
    //开始减少1个元素
    L.length--;
    
    return OK;

//判断线性表L是否为空  
bool ListEmpty(SqList &L)  
\{  
return L.length == 0;  
\}

//得到线性表的长度，即线性表中元素的数量

int ListLength(SqList &L)  
\{  
return L.length;  
\}

//线性单链表的节点数据类型定义  
typedef struct LNode  
\{  
ElemType data;  
struct LNode \*next;  
\} LNode, \*LinkList;

//初始化线性链表  
Statue InitList\_L(LinkList &L)  
\{  
//建立头节点  
L = (LinkList)malloc(sizeof(LNode));

//开始给头节点初始化
    L->data = -1;
    L->next = NULL;
    
    return OK;

//在线性链表中取第i个数据存放在元素e  
//默认单链表有头节点  
Statue GetElem\_L(LinkList L, int i, ElemType &e)  
\{  
//保存单链表头指针，防止更改了头指针里面的地址，导致其他地方无法使用  
LinkList p = L;  
int j = 1; //用来记录节点增加的数目

//开始定位i位置的节点
    //开始拿到第一个节点元素地址
    p = p->next;
    
    //通过循环找到待查找节点的位置
    while (p && j < i) //当p不为空以及没有跑到所要节点位置就一直循环
    {
        p = p->next;
        j++;    
    }
    
    //开始判断是不是找到待查节点的位置
    //当p = null代表定位的位置超出链表节点数量
    //首先我们默认i只能取值从1开始表示第一个节点
    //得到j > i告诉了我们定位的i取值小于1也就是想找第一个节点之前的
    //当然是不存在这种节点
    if (!p || j > i) 
      return ERROR;//没有找到待查找的位置
    
    //代码进入这里说明在链表中找到了待查位置的节点
    //开始保存需要节点的数据到e中
    e = L->data;
    
    return OK;

//往带头结点单链表插入节点e  
Statue InsertNode(LinkList L, int i, ElemType &e)  
\{  
//首先定义一个节点类型变量保存当前链表地址  
LinkList q = L;

//新建一个节点，用于将e数据存入新节点当中
    LinkList p = (LinkList)malloc(sizeof(LNode));
    
    //判断是不是分配成功
    if (!p) exit(OVERFLOW);
    
    //开始写入数据
    p->data = e;
    
    //定义变量用于记录节点增加数量
    int j = 1;
    
    //开始通过循环找到待插位置的前一个节点
    while (q && j < i - 1)
    {
        q = q->next;
        j++;
    }
    
    //判断是不是找到需要的节点
    if (!p || j > i)  return ERROR;
    
    //开始将节点p插入链表
    p->next = q->next;
    q->next = p;
    
    return OK;

//单链表定位元素e的位置  
LNode\* LocateElem\_L(LinkList L, ElemType e)  
\{  
//找到第一个出现值和e相同的节点，并返回其地址，不存在则返回null  
//先判当前链表是不是为null

LinkList p;
    if (!L)
    {
        return NULL;
    }
    
    p = L;
    
    //开始遍历链表查找节点中数据为e的节点
    while (p && p->data != e)
    {
        p = p->next;
    }
    
    return p;

//线性表的应用  
//比如2个线性表的大小 注意A,B是用的顺序存储链表  
int Compare(SqList A, SqList B)  
\{  
//如果A < B 返回-1，A = B 返回0 反之返回1

int j = 0; //用于记录顺序链表A和B共同部分的索引值
    
    //开始使用循环遍历链表节点比较A和B链表上的节点大小
    while (j < A.length && j < B.length) //保证遍历完顺序表中长度小的链表
    {
        if (A.elem[j] > B.elem[j])
        {
            return 1;  //出现A链表中的节点数据大
        }
        else if(A.elem[j] == B.elem[j]) //如果比较的节点是相等，那么我们都把索引+1，比较顺序表下一个节点数据
        {
            j++;
        }
        else   //B中节点大
        {
            return -1;
        }
    
        if (A.length == B.length) return 0; //执行上面循环出现当前结果表示链表长度一样，并且数据也都相等
    
        if (A.length > B.length) return 1;  //表示A链表和B链表共有部分数据是一样的，但是A链表元素更多
    
    
        return -1;  //这个是B链表元素多的情况
    }

int main()  
\{  
return 0;  
\}