[数据结构与算法]线性表的顺序存储与链式存储(单链表)及操作代码实现

线性表的顺序存储和链式存储（单链表）及其相关操作实现

线性表的顺序存储

顺序存储的特点

以物理位置相邻表示逻辑关系

顺序存储的优缺点

优点: 1.存储密度大（本身所占存储容量/节点结构所占存储容量）
???2.可以随机存取

缺点:1.插入和删除需要移动大量元素
???2.浪费空间（需要一片连续的存储空间）
???3.属于自由存储形式，数据元素不能自由扩充

线性表顺序存储的代码实现及相关操作解释（C++）

#include<bits/stdc++.h>
using namespace std;
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
typedef int Status;
typedef char ElemType;
typedef struct {
    ElemType *elem;
    int lenght;
}SqList;
SqList L;
Status InitList_Sq(SqList &L){//构建一个顺序表
    L.elem=new ElemType[MAXSIZE];//为顺序表分配空间
    if(!L.elem) exit(OVERFLOW);//存储分配失败
    L.lenght=0;//空表长度；
    return OK;
}
void DestoryList(SqList &L){ //销毁线性表
    if(L.elem) delete L.elem;//释放存储空间
}
void ClearList(SqList &L){//清空线性表
    L.lenght=0;//长度置零
}
int GetLength(SqList &L){//求线性表长度
    return (L.lenght);
}
int IsEmpty(SqList &L){//判断线性表是否为空
    if(L.lenght==0)return 1;
    else return 0;
}
int GetElem(SqList &L,int i,ElemType &e){//取值，取线性表位置i上的元素
    if(i<1||i>L.lenght)return ERROR;
    e=L.elem[i-1];
    return OK;
}
int LocateElem(SqList &L,ElemType e){//查找e在线性表中的位置
    for(int i=0;i<L.lenght;i++)
        if(L.elem[i]==e)return i+1;//查找成功返回序号
    return 0;//查找失败返回0
}
Status ListInsert_Sq(SqList &L,int i,ElemType e){//插入元素
    if(i<1||i>L.lenght+1) return ERROR;//i值是否合法
    if(L.lenght==MAXSIZE) return ERROR;//是否超长度
    for(int j=L.lenght-1;j>=i-1;j--)//插入位置及后移元素
        L.elem[j+1]=L.elem[j];
    L.elem[i-1]=e;
    L.lenght++;
    return OK;
}
Status ListDelete_Sq(SqList &L,int i){
    if(i<1||i>L.lenght) return ERROR;
    for(int j=i;j<L.lenght;j++)
        L.elem[j-1]=L.elem[j];
    L.lenght--;
    return OK;
}
int main(){
    int i;
    InitList_Sq(L);
    while(cin>>L.elem[i]){
        L.lenght++;i++;
        if(cin.get()=='\n')break; 
    }
    for(int i=0;i<L.lenght;i++)cout<<L.elem[i]<<" ";
    cout<<endl;
    cout<<"线性表长度为："<<GetLength(L)<<endl;
    cout<<"线性表是否为空：";
    if(IsEmpty(L))cout<<"是"<<endl;
    else cout<<"否"<<endl;
    cout<<"第三个元素为：";
    char e;
    if(GetElem(L,3,e))cout<<e<<endl;
    else cout<<"不存在"<<endl;
    cout<<"元素c在顺序表中的位置为：";
    if(LocateElem(L,'c'))cout<<LocateElem(L,'c')<<endl;
    else cout<<"不存在"<<endl;
    cout<<"在第3个位置插入元素a：";
    if(ListInsert_Sq(L,3,'a')){
        for(int i=0;i<L.lenght;i++)cout<<L.elem[i]<<" ";
        cout<<endl;
    }else{cout<<"插入位置不合法"<<endl;}
    cout<<"删除位置为6的元素：";
    if(ListDelete_Sq(L,6)){
        for(int i=0;i<L.lenght;i++)cout<<L.elem[i]<<" ";
        cout<<endl;
    }else{cout<<"删除位置不合法"<<endl;}
    return 0;
}

线性表的链式存储（单链表）

链式存储的特点

用一组任意的存储单元存储线性表的数据元素（可以连续也可以不连续）

链式存储的优缺点

优点:1.可以自由扩充数据元素
???2.插入删除等操作时间复杂度低（O(1)）

缺点:1.存储密度低
???2.不能随机存取

线性表链式存储的代码实现及相关操作解释（C++）

#include<bits/stdc++.h>
using namespace std;
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
typedef int Status;
typedef char ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
LinkList L;
Status InitList(LinkList &L){
    L=new LNode;
    L->next=NULL;
    return OK;
}
int ListEmpty(LinkList L){//判断链表是否为空
    if(L->next) return 0;//非空
    else return 1;//空
}
Status DestroyList_L(LinkList &L){
    LNode *p;
    while(L){
        p=L;
        L=L->next;
        delete p;
    }
    return OK;
}
Status ClearList_L(LinkList &L){//将L重置为空
    LNode *p,*q;
    p=L->next;
    while(p){//没到表尾
        q=p->next;
        delete p;
        p=q;
    }
    L->next=NULL;//头结点指针域为空
    return OK;
}
int ListLength_L(LinkList L){//链表的长度
    LinkList p;
    p=L->next;
    int i=0;
    while(p){
        i++;
        p=p->next;
    }
    return i;
}
Status GetElem_L(LinkList L,int i,ElemType &e){//取链表的第i个元素
    LinkList p;
    p=L->next;
    int j=1;
    while(p&&j<i){
        p=p->next;++j;
    }
    if(!p||j>i)return ERROR;
    e=p->data;
    return OK;
}
LNode *LocateElem_L(LinkList L,ElemType e){//查找元素返回该元素的地址
    LinkList p;
    p=L->next;
    while(p&&p->data!=e){
        p=p->next;
    }
    return p;
}
int LocateElem_Li(LinkList L,ElemType e){//查找元素e在链表的位置
    LinkList p;
    int j=1;
    p=L->next;
    while(p&&p->data!=e){
        p=p->next;j++;
    }
    if(p)return j;
    else return 0;
}
Status ListInster_L(LinkList &L,int i,ElemType e){//在第i个位置之前插入元素e
    LinkList p,s;int j=0;
    p=L;
    while(p&&j<i-1){p=p->next;++j;}
    if(!p||j>i-1)return ERROR;
    s=new LNode;s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}
Status ListDelete_L(LinkList &L,int i,ElemType &e){//删除一个元素
    LinkList p,s;int j=0;
    p=L;
    while(p->next&&j<i-1){p=p->next;++j;}
    if(!(p->next)||j>i-1)return ERROR;
    s=p->next;
    p->next=p->next->next;
    e=s->data;
    delete s;
    return OK;
}
void CreateList_H(LinkList &L,int n){//头插法建立单链表
    LinkList p;
    L->next=NULL;
    for(int i=n;i>0;--i){
        p=new LNode;//建立新结点
        cin>>p->data;
        p->next=L->next;//
        L->next=p;//
    }
}
void CreateList_R(LinkList &L,int n){//尾插法建立单链表
    L->next=NULL;
    LinkList r,p;
    r=L;
    for(int i=0;i<n;i++){
        p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;//
        r=p;//
    }
}
int main(){
    LinkList p;
    int n;
    cin>>n;
    InitList(L);
    CreateList_R(L,n);
    cout<<"建立一个单链表：";
    p=L->next;
    while(p){cout<<p->data<<" ";p=p->next;}
    cout<<endl;
    cout<<"单链表是否为空：";
    if(ListEmpty(L))cout<<"是"<<endl;
    else cout<<"否"<<endl;
    cout<<"单链表的长度为：";
    cout<<ListLength_L(L)<<endl;
    cout<<"第三个元素为：";
    char e;
    if(GetElem_L(L,3,e))cout<<e<<endl;
    else cout<<"不存在"<<endl;
    cout<<"元素c在顺序表中的位置为：";
    if(LocateElem_Li(L,'c'))cout<<LocateElem_Li(L,'c')<<endl;
    else cout<<"不存在"<<endl;
    cout<<"在第3个位置插入元素a：";
    if(ListInster_L(L,3,'a')){
        p=L->next;
        while(p){cout<<p->data<<" ";p=p->next;}
        cout<<endl;
    }else{cout<<"插入位置不合法"<<endl;}
    cout<<"删除位置为6的元素：";
    if(ListDelete_L(L,6,e)){
        p=L->next;
        while(p){cout<<p->data<<" ";p=p->next;}
        cout<<endl;
    }else{cout<<"删除位置不合法"<<endl;}
    return 0;
}