线性表.md

线性表 从零开始的数据结构的学习生活

first	second	third	fourth
顺序线性表	单链表	双链表	案例分析

	顺序表	链表
存储空间	预先分配，可能会导致空间闲置或溢出	动态分配，不会出现空间闲置或者溢出
存储密度	存储密度为1，逻辑关系等于存储关系，没有额外开销	存储密度小于1，要借助指针域来表示元素之间的逻辑关系
存取元素	随机存取，按位置访问元素的时间复杂度O(1)	顺序存取，访问某位置的元素的时间复杂度为O(n)
插入、删除	插入和删除都要移动大量的元素。平均移动元素约为表的一半。时间复杂度O(n)	不需要移动元素，只需要改变指针位置，继而改变结点之间的链接关系。时间复杂度O(1)
适用情况	1.表长变化不大，或者事先就能确定变化的范围 2.很少进行插入和删除，需要下标访问元素	1.长度变化较大 2.频繁的插入和删除
	这不就是vector的使用特点吗	这不就是list的使用特点吗

==1.这就是顺序线性表==

线性表的定义

typedef struct SQList
{
    ElemType  *elem; // 顺序线性表的表头
    int length;     // 顺序线性表的长度
}SqList;

ElemType 类似于一个房子，具体怎么定义看自己而定 使用的时候 typedef --- ElemType

线性表的初始化

int initList(SqList &L)
{
    
    L.elem = new ElemType[Maxsize];  //在堆区开辟内存
    if (!L.elem)
        exit(OVERFLOW);
    L.length = 0; //将线性表的长度设置为0
    return OK;
}

OVERFLOW 已经在之前通过define定义为-2
OK则通过define定义为1

线性表的销毁

void DestroyList(SqList &L)
{
    
    if (L.elem)
    {
        delete L.elem;
    }
}

线性表的清空

void ClearList(SqList &L)
{
    
    L.length = 0;
}

获得线性表的长度

int GetLength(SqList L)
{

    return (L.length);
}

判断线性表是否为空

int IsEmpty(SqList L)
{

    if (L.length == 0)
        return 1;
    else
        return 0;
}

线性表的取值

bool GetElem(SqList L, const size_t i, ElemType &e)
{

    if (i < 1 || i > L.length)
        return ERROR;

    e = L.elem[i - 1];
    return OK;
}

线性表的查找

int LocateElem(SqList L, Elemtype e)
{

    for (int i = 0; i < L.length; i++)
    {
        if (L.elem[i] == e)
            return i + 1;        //查找成功，返回查找元素的第一个下标值
    }
    return 0;   //找不到对应的元素，返回0
}

线性表的插入

bool ListInsert_Sq(SqList &L, int i, ElemType e)
{
    if (i < 1 || i>Ll.length + 1)  //看看要插入的是否处于线性表内
        return ERROR;
    if (L.length == MAXSIZE)  //如果长度与MAXSIZE相等那说明已经没有位置可以插入了
        return ERROR;

//经过了两次的判定后 开始操作 将插入位置之后的元素依次向后挪动一位
    for (int j = L.length - 1; j >= i - 1; j--)
        L.elem[j + 1] = L.elem[j];
//插入我们想要插入的元素
    L.elem[i - 1] = e;
//线性表的长度增加一位
    L.length++;
}

线性表的删除

bool ListDelete_Sq(SqList &L, int i)
{
//第一步开始特判是否这个数据在线性表内
    if ((i < 1) || (i > L.length))
        return ERROR;
    for(int j = i; j <= L.length - 1; j++)  //将位于删除位置之后的元素依次向前挪动一位
        
    L.elem[j - 1] = L.elem[j];
//线性表的长度-1
    L.length--;

    return OK;
}

==单向链表==

链表的定义

typedef strut Lnode{
    ElemType data;
    struct Lnode *next;
}Lnode,*LinkList;//嵌套的定义

一个简单的例子

/*typedef Strurct stdent{
    char num[8];
    char name[8];
    int score;
    struct student *next;
}Lnode,*LinkList;

这种方法不是很常用
*/
typedef Struct{
    char num[8];  //数据域
    char name[8]; //数据域
    int score;    //数据域
}Elemtype;

typedef struct Lnode{
    ElemType data;       //数据域
    struct Lnode *next;  //指针域
}Lnode,*LinkList;

单链表的初始化

Status initList_L(LinkList &L) //插入题外话：LinkList &L等价于 Lnode *&L，Lnode *&L是一个指向指针的引用
{
    L=new LNode;   //在堆区开辟处一个头节点，节点的数据类型为Lnode   L=(LinkList)malloc(sizeof(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; //或LinkList p；
    while(L)
    {
        p=L;
        L=L->next;
        delete p;
    }

    return OK;

}

清空链表

Status ClearList_L(LinkList &L)    //将L重置为空表
{
    Lnode *p,*q;    //或者LinkList p，q；
    p=L->next;      //先将此时p指向首元节点
    while(p)                 //没到表尾
    {
        q=p->next;    //接着q等于p指向的l的下下一个节点
        delete p;     //删除掉p 也就是第一个头节点
        p=q;          //将q的值传给p
    }
    L->next=NULL;    //头指针节点指针域为空
    return OK;
}

求链表的表长

Status LengthList_L(LinkList &L)
{
    int i = 0;
    LinkList p;
    p=L->next;  //指向第一个节点
    while(p){
     i++;
     p=p->next;
    }
   return i；
}

**
~~~cpp
Status GetElem_L(LinkList &L,int i,ElemType &e)
{
    LinkList p;
    p=L->next;   //初始化
    int j=1;
    while(P&&j<i)  //向后扫描，直到p指向第i给元素或者p为空
    {
        p=p->next;
        ++j;
    }
    if(!P||j>i) return ERROR;  //第i给元素不存在
    e=p->data; //取第i给元素

    return OK;
}

单链表的查找运算

Lnode *LocateElem_L(LinkList L,ELemtype e){
    LinkList p;
    p=L->next;
    while(p&&p->nextdata!=e)
        p=p->next;
        
        return p;
    
}
~改进的~
int LocateElem_L(LinkList L,Elemtype e){
    LinkList P;

    p=L->next;

    j=1;

    whiel(p&&p->next!=e)
    {
        p=p->next;
        j++;
    }
    if(P) return j;
    else return 0;
}

单链表的插入

Status LinkInsert_L(LinkList &L,int i,ElemType e){

    LinkList p;
    p=L;
    j=0;
    while(p&&j<i-1)
    {
        p=p->next;
        ++j;
    } //寻找i-1个节点，p指向i-1个节点
    if(!p||j>i-1) return ERROR;
    s=new Lnode;
    s->data=e;
    s->next=p->next;
    p->next=s;

    return OK;
}

单链表节点的删除

Status LinkDelete_L(LinkList &L,int i,ElemType e)  //i为要删除的位置
{
    LinkList p,q;
    p=L;
    int j=0;
    while(p&&j<i-1)
    {
        P=p->next;
        ++j;
    }  //寻找第i给节点

    if(!(p->next)||j>i-1)  //删除不在区间内的
    return ERROR;
    q=p->next;     //临时保存被删除节点的地址等着被释放
  
    p->next=q->next;   //改变删除节点的前驱节点的指针域
    
    e=q->next;     //保存要删除的节点的数据域
    
    delete q;    //删除节点
    
    return OK;


}

单链表的头插法

void CreateList_H(LinkList &L,int n){
        LinkList p;

        L=new Lnode;

        L->next=NULL;   //先建立一个带头节点的单链表

        for(int i=n;i>n;--i){

        p=new LNode;   //生成新节点p=(LNode*)malloc(sizeof(LNode));

        cin>>p>>data;  //输入元素值 sacnf(&p->data);

        p->next=L->next;   //插入到表头

        L->next=p;
    }
}

单链表的尾插法

void CreateList_R(LinkList &L,int n)
{
    L=new LNode;
    L->next=NULL;
    r=L;   //尾指针r指向头节点
    for(int i=0;i<n;i++)
    {
        P=new LNode;  //生成新结点，输入元素值
        cin>>P->data;
        p->next=NULL;
        r->next=p;   //插入到表尾
        r=p;         //r指向新的尾结点
    }
}

循环列表的定义

typedef struct CLnode
{
    ElemType data;
    CLnode *next;
}*CircList;

循环列表的初始化

void InitList(CircList &L)
{
    L = new CLnode;
    L->next = L;
}

带尾指针的循环链表的合并

LinkList Connect(LinkList Ta,LinkList Tb){  //假设Ta，Tb都是非空的单循环链表
    p->Ta->next;                     //p存表头节点
    Ta->next=Tb->next->next;         //Tb表头连结Ta表尾
    delete Tb->next;                 //释放Tb表头结点
    Tb->next=p;                      //修改指针

    return Tb;

}

==循环链表的基本操作和单链表基本上相同，唯一不同的是，由于循环链表的最后一个结点的next不再是空指针，而是指向头结点，因此，循环中的结束条件要发生变化==

单链表--------------循环链表
while(p)--------->while(p!=L)
while(p->next)--->while(p->next!=L)

==1.双向链表==

双链表的定义

Typedef struct DulNode{

Elemtype     data;

struct DulNode *prior,*next;

}DulNode,*DuLinkList;

双向链表的插入

void ListInsert_Dul(DuLinkList &L,int i,ElemType e){
    if(!(p=GetElemP_Dul(L,i)))

    return ERROR;

    s=new DulLNode;

    S->data=e;

    S->prior=p->Prior; //第一步 S的前驱等于p的前驱

    P->prior->next=s;  //第二步 用p的前驱节点的next指向插入的元素s，更改插入的节点与前面节点之间的关系

    s->next=p;         //第三步 插入节点s的后继指向p

    p->prior=s;        //第四步 p节点的前驱改为s

    return OK;
}

双向链表的删除

void ListDelete_Dul(DuLink &L,int i,ElemType &e){
    if(!(p=GeyELemp_Dul(L,i)))

    return ERROR;

    e=p->data;

    p->Prior->next=p->next;    //p的前驱节点的nest等于p的后继

    p->next->prior=p->Prior;    //p的后继节点的前驱等于p的前驱节点

    free(p);                    //将p删除
 
    return OK;
}

线性表的合并

void union(List &La,List &Lb){
    La_len=Listlength(La);
    Lb_Len=Listlength(Lb);

    for(int i=1;i<=Lb_Len;i++)
    {
        GetElem(Lb,i,e);
        if(!LocateElem(La,e))
        Listinsert(&La,++La_Len,e);
    }
}

有序表的合并

//顺序表
void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
    pa=LA.elem;
    pb=LB.elem;   //指针pa和pb的初值分别指向两个表的第一个元素
    LC.length=LA.length+Lb.length;  //新表长度为待合并两表的长度之和
    LC.elem=mew ElemType[LC.length];  //为合并后的新表分配一个数组空间
    pc=LC.elem;                    //指针pc指向新表的第一个元素
    pa_last=LA.elem+LA.length-1;    //指针pa——last 指向la表的最后一个元素
    pb_last=LB.elem+LB.length-1;    //指针pb——last 指向LB表的最后一个元素


    while(pa<=pa_last&&pb<=pb_lats){    //两个表都非空
        if(*pa<=*pb)                    //依次选取两个表中值较小的节点
        *pc++=*pa++;
        else
        *pc++=*pb++;
    }

    while(pa<=pa_last) *pc++=*pa++;  //LB表已达到表尾，将LA中剩余元素加入LC
    while(pa<=pb_last) *pc++=*pb++;  //LA表已达到表尾，将LB中剩余元素加入LC
}

//链表
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    pa=La->next;
    pb=Lb->next;
    pc=Lc=La;   //用La的头节点作为Lc的头节点
    while(pa&&pb){
        if(pa->data<=pb->data)
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else{
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
        pc->next=pa?pa:pb;  //插入剩余段

        delete Lb;  //释放Lb的头节点
    }
}

==案例分析==

多项式的运算

void PolyOperate(SqList &L1, SqList &L2, SqList &L3)
{
    for (int i = 0; i < L1.length && i < L2.length; ++i)
    {
        L3.elem[i] = L1.elem[i] + L2.elem[i];
        L3.length += 1;
    }
    if (L1.length <= L2.length)
    {
        for (int j = L1.length; j < L2.length; ++j)
        {
            L3.elem[j] = L2.elem[j];
            L3.length += 1;
        }
    }
    else
    {
        for (int j = L2.length; j < L1.length; ++j)
        {
            L3.elem[j] = L1.elem[j];
            L3.length += 1;
        }
    }
}

稀疏多项式的运算

void SQL_I(SqList &L1, SqList &L2, SqList &L3)
{
    ElemType *p1 = L1.elem;
    ElemType *p1_last = L1.elem + L1.length - 1;
    ElemType *p2 = L2.elem;
    ElemType *p2_last = L2.elem + L2.length - 1;
    ElemType *p3 = L3.elem;
    while (p1 <= p1_last && p2 <= p2_last)
    {
        if (p1->index < p2->index)
        {
            p3->index = p1->index;
            p3->coef = p1->coef;
            ++p1;
            ++p3;
            ++L3.length;
        }
        else if (p1->index > p2->index)
        {
            p3->index = p2->index;
            p3->coef = p2->coef;
            ++p2;
            ++p3;
            ++L3.length;
        }
        else if (p1->index == p2->index)
        {
            p3->index = p1->index;
            p3->coef = p1->coef + p2->coef;
            ++p1;
            ++p2;
            ++p3;
            ++L3.length;
        }
    }
    while (p1 <= p1_last)
    {
        p3->index = p1->index;
        p3->coef = p1->coef;
        ++p1;
        ++p3;
        ++L3.length;
    }
    while (p2 <= p2_last)
    {
        p3->index = p2->index;
        p3->coef = p2->coef;
        ++p2;
        ++p3;
        ++L3.length;
    }
}

系数多项式的相加

void SPO_II(LinkList &La, LinkList &Lb, LinkList &Lc)
{
    Lnode *pa = La->next;
    Lnode *pb = Lb->next;
    Lc = La;
    Lnode *pc = Lc;
    while(pa && pb)
    {
        if(pa->data.index < pb->data.index)
        {
            pc->next = pa;
            pc = pc->next;
            pa = pa->next;
        }
        else if(pa->data.index > pb->data.index)
        {
            pc->next = pb;
            pc = pc->next;
            pb = pb->next;
        }
        else if(pa->data.index == pb->data.index)
        {
            pa->data.coef += pb->data.coef;
            pc->next = pa;
            pc = pc->next;
            pa = pa->next;
            pb = pb->next;
        }
    }
    pc->next = (pa ? pa : pb);
    delete Lb;
}

图书管理系统 - 单链表实现

typedef struct Book
{
    string isbn;
    string name;
    float price;
} ElemType;
struct Lnode
{
    ElemType data;
    Lnode *next;
} *LinkList;

//使用read函数向ElemType的对象写入数据
istream &read(istream &in, ElemType &rhs)
{
    in>>rhs.isbn;
    in>>rhs.name;
    in>>rhs.price;
    return in;
}
ostream &print(ostream &out, ElemType &rhs)
{
    out<<rhs.isbn<<" "
        <<rhs.name<<" "
        <<rhs.price<<endl;
    return out;
}
//读
read(cin, L->data);
//写
print(cout, L->data);