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

数据结构–线性表

admin • • C/C++ • 阅读 137

线性表

1.线性表的分类

  • 顺序表
  • 链式表
    • 单链表
    • 静态链表
    • 循环列表

2. 线性表

通常先封装成一个结构体，再进行操作

typedef struct
{
    int *elem;      //储存数据的地址
    int length;     //记录线性表的已经储存的数据长度（数量）
    int listsize;   //记录线性表的表长
}SqList;

2.1 构造

利用动态内存分配函数malloc，在头文件stdlib.h中，c++中为cstdlib

int InitList_Sq(SqList &L)
{
// 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE
    L.elem=(int*)malloc(LIST_INIT_SIZE* sizeof(int));           //动态分配内存，返回首地址赋给L.elem
    if(!L.elem) return 0;
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;      //OK被define为1
}

2.2 遍历

思路：

  • 判断是否为空表
    • 是空表，输出
      • 方法一：数组法
      • 方法二：指针法
    • 不是空表，报错
int Load_Sq(SqList &L)
{
// 输出顺序表中的所有元素
    int i;
    if(L.length==0) printf("The List is empty!");   //判断是否为空表
    else
    {
        printf("The List is: ");
        //遍历办法一 ：利用数组，
        for(int i=0;i<L.length;i++) printf("%d ",L.elem[i]); 
        //遍历办法二 ：利用指针，将头指针给中间指针，用来遍历
        for(int *p=L.elem;p!=L.elem+L.length;p++) printf("%d ",*p);     
    }
    printf("\n");
    return OK;
}

2.3 插入新元素

思路：

  • 先判断插入的位置是否合法
  • 判断储存的元素是否等于数组上限
    • 如果达到上限，realloc增配空间
int ListInsert_Sq(SqList &L,int i,int e)
{
// 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e
// i的合法值为1≤i≤L.length +1
    if(i<1 || i>L.length+1) return ERROR;     
    if(L.length>=L.listsize)
    {
      //重新分配空间，增多储存空间
        int *newbase;
        newbase=(int*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(int));
        if(!newbase) return 0;
        L.elem=newbase;
        L.listsize+=LISTINCREMENT;
    }
    int *q=&(L.elem[i-1]);  //取需要插入地方的地址
    for( int *p=&(L.elem[L.length-1]);p>=q;--p)  //由最后一个元素开始倒推
        *(p+1)=*p;
    *q=e;
    ++L.length;
    return OK;
}

2.4 删除元素

int ListDelete_Sq(SqList &L,int i, int &e)
{
// 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值
// i的合法值为1≤i≤L.length
    int *p,*q;
    if(i<1 || i>L.length) return ERROR;
    p=&(L.elem[i-1]);
    e=*p;       //用e将该元素带出来
    q=L.elem+L.length-1;        //L.elem是一个指针，此处q得到的是最后一个元素的地址
    for(p++;p<=q;++p)
        *(p-1)=*p;
    --L.length;
    return OK;
}

2.5 合并顺序表

  • 方法一 ：先合并，再排序
  • 方法二：按小到大排放到
方法一：
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
using namespace std;

typedef int Status;
typedef struct
{
    int *elem;
    int length;
    int listsize;
}SqList;

Status InitList_Sq(SqList &L)
{  // 算法2.3
    // 构造一个空的线性表L。
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if (!L.elem) return OK;        // 存储分配失败
    L.length = 0;                  // 空表长度为0
    L.listsize = LIST_INIT_SIZE;   // 初始存储容量
    return OK;
} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e)
{  // 算法2.4
    // 在顺序线性表L的第i个元素之前插入新的元素e，
    // i的合法值为1≤i≤ListLength_Sq(L)+1
    ElemType *p;
    if (i < 1 || i > L.length+1) return ERROR;  // i值不合法
    if (L.length >= L.listsize) {   // 当前存储空间已满，增加容量
        ElemType *newbase = (ElemType *)realloc(L.elem,
                                                (L.listsize+LISTINCREMENT)*sizeof (ElemType));
        if (!newbase) return ERROR;   // 存储分配失败
        L.elem = newbase;             // 新基址
        L.listsize += LISTINCREMENT;  // 增加存储容量
    }
    ElemType *q = &(L.elem[i-1]);   // q为插入位置
    for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
    // 插入位置及之后的元素右移
    *q = e;       // 插入e
    ++L.length;   // 表长增1
    return OK;
} // ListInsert_Sq

Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{  // 算法2.5
    // 在顺序线性表L中删除第i个元素，并用e返回其值。
    // i的合法值为1≤i≤ListLength_Sq(L)。
    ElemType *p, *q;
    if (i<1 || i>L.length) return ERROR;  // i值不合法
    p = &(L.elem[i-1]);                   // p为被删除元素的位置
    e = *p;                               // 被删除元素的值赋给e
    q = L.elem+L.length-1;                // 表尾元素的位置
    for (++p; p<=q; ++p) *(p-1) = *p;     // 被删除元素之后的元素左移
    --L.length;                           // 表长减1
    return OK;
} // ListDelete_Sq

int Load_Sq(SqList &L)
{
// 输出顺序表中的所有元素
    int i;
    if(L.length==0) printf("The List is empty!");  // 请填空
    else
    {
        for(int i=0;i<L.length;i++) printf("%d ",L.elem[i]);  // 请填空
    }
    printf("\n");
    return OK;
}

int main()
{
    SqList A,B;
    InitList_Sq(A);
    InitList_Sq(B);
    cin >> A.length;
    for(int i=0;i<A.length;i++)
    {
        cin >> A.elem[i];
    }
    cin >> B.length;
    for(int i=0;i<B.length;i++)
    {
        cin >> B.elem[i];
    }
    cout << "List A:";
    Load_Sq(A);
    cout << "List B:";
    Load_Sq(B);

    ElemType *newbase = (ElemType *)realloc(A.elem,
                                            (A.length+B.length)*sizeof (ElemType));
    A.elem=newbase;
    A.listsize+=B.length;
    for(int i=A.length;i<A.length+B.length;i++)
    {
        A.elem[i]=B.elem[i-A.length];
    }
    A.length+=B.length;
    for(int i=0;i<A.length-1;i++)
    {
        int min=i;
        for(int j=i;j<A.length;j++)
        {
            if(A.elem[min]>A.elem[j]) min=j;
        }
        int temp=A.elem[i];
        A.elem[i]=A.elem[min];
        A.elem[min]=temp;
    }
    cout << "List C:";
    Load_Sq(A);
}
方法二：
#include <iostream>
#include <cstdlib>
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
using namespace std;
typedef int Status;
typedef struct
{
    int *elem;
    int length;
    int listsize;
}SqList;

Status InitList_Sq(SqList &L)
{  // 算法2.3
    // 构造一个空的线性表L。
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if (!L.elem) return OK;        // 存储分配失败
    L.length = 0;                  // 空表长度为0
    L.listsize = LIST_INIT_SIZE;   // 初始存储容量
    return OK;
} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e)
{  // 算法2.4
    // 在顺序线性表L的第i个元素之前插入新的元素e，
    // i的合法值为1≤i≤ListLength_Sq(L)+1
    ElemType *p;
    if (i < 1 || i > L.length+1) return ERROR;  // i值不合法
    if (L.length >= L.listsize) {   // 当前存储空间已满，增加容量
        ElemType *newbase = (ElemType *)realloc(L.elem,
                                                (L.listsize+LISTINCREMENT)*sizeof (ElemType));
        if (!newbase) return ERROR;   // 存储分配失败
        L.elem = newbase;             // 新基址
        L.listsize += LISTINCREMENT;  // 增加存储容量
    }
    ElemType *q = &(L.elem[i-1]);   // q为插入位置
    for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
    // 插入位置及之后的元素右移
    *q = e;       // 插入e
    ++L.length;   // 表长增1
    return OK;
} // ListInsert_Sq

Status LoadList(SqList &L)
{

    for(int *p=L.elem;p!=L.elem+L.length;p++) cout << *p << " ";
    return OK;
}

Status merge(SqList &A,SqList &B,SqList &C) {
    C.length = A.length + B.length;
    C.elem = (int *) realloc(C.elem, (C.length) * (sizeof(int)));       //给C分配空间，大小为A+B
    int *p = A.elem, *q = B.elem,i=0;  //用p，q指针分别取A，B首元素的地址，用以下面的计算
    while (1)       //建立死循环，比较两个数组元素的大小，当有一个数组全部遍历后跳出
    {
        if (*p < *q) {
            C.elem[i++] = *p;
            p++;

            if(p==&A.elem[A.length] || q==&B.elem[B.length]) break;
        } else {
            C.elem[i++] =*q;
            q++;
            if(p==&A.elem[A.length] || q==&B.elem[B.length]) break;
        }
    }
    if(p==A.elem+A.length)      //判断哪一个数组已经到尾，然后在C的后面加上另一个数组剩下的元素
    {
        while(q!=B.elem+B.length)
        {
            C.elem[i++]=*q;
            q++;
        }
    } else{
        while(p!=A.elem+A.length)
        {
            C.elem[i++]=*p;
            p++;
        }
    }
    return OK;
}

int main()
{
    SqList A,B,C;
    int numA,numB,temp;
    InitList_Sq(A);
    InitList_Sq(B);
    InitList_Sq(C);
    cin >> numA ;
    for(int i=1;i<=numA;i++)
    {
        cin >> temp;
        ListInsert_Sq(A,i,temp);
    }
    cin >> numB;
    for(int i=1;i<=numB;i++)
    {
        cin >> temp;
        ListInsert_Sq(B,i,temp);
    }
    cout << "List A:";
    LoadList(A);
    cout << endl << "List B:";
    LoadList(B);
    merge(A,B,C);
    cout << endl << "List C:";
    LoadList(C);

    return 0;
}

原文链接: https://www.cnblogs.com/miceputil/p/12314098.html

欢迎关注

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

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    数据结构--线性表

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

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

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

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

赞 (0)
adminadmin
0 0
上一篇 2023年3月1日 下午5:19
下一篇 2023年3月1日 下午5:19

相关推荐