数据结构（线性表）

线性表（List）：零个或多个数据元素的有限序列

在复杂的线性表中，一个数据元素可以有若干个数据项组成。

线性表的顺序存储结构：指的是用一段地址连续的存储单元存储线性表的数据元素。

数据长度与线性表长度的区别

数组长度是存放线性表的存储空间长度，存储分配后这个量一般不变
线性表长度是线性表中数据元素的个数，随着线性表的插入和删除，这个量是变化的
在任意时刻线性表的长度应该小于数组的长度

地址计算方法

LOC(ai+1)=LOC(ai)+c

LOC(ai)=LOC(a1)+(i-1)*c

顺序存储结构的插入和删除（实现源码）

【c++实现的时候函数是有顺序的，调用的必须在被调用函数的后边】

#include"iostream"
#include"stdlib.h" 
#include"stdio.h"
typedef int Position;
typedef int ElType;
typedef struct Xxb *Node;
#define MAXSIZE 10
using namespace std;
struct Xxb{
    ElType Data[MAXSIZE];
    Position Last;  //记录最后一个元素在数组中的位置 
}; 
typedef Node List;

List Initialize(){  //初始化线性表 
    List L;
    L = (List)malloc(sizeof(struct Xxb)); 
    L->Last=-1;
    cout<<"初始化成功"<<L->Last<<endl; 
    return L;
}
bool Insert(List L,ElType x,int i){   //加入 and 插入 
    Position j=0;
    if(L->Last == MAXSIZE-1){

        return false; 
    }
    if(i<1||i>L->Last+2){
        cout<<"输入的位置不合法"<<endl;
        return false; 
    }
    for(j=L->Last;j>=i-1;j--){
        L->Data[j+1] = L->Data[j];

    }
    L->Data[i-1]=x;
    L->Last+=1;
    return true;
}
int Length(List L){  //求表长 
    return L->Last+1;
}
void show(List L){   //显示所有 
    for(int i=0;i<Length(L);i++){
        cout<<L->Data[i]<<" ";
    }
}
void Find(List L,ElType x){
    int i = 0;
    while(i<=L->Last&&L->Data[i]!=x){
        i++;
    } 
    if(i>L->Last){
        cout<<"不存在"<<endl; 
    }
    else{
        cout<<"下标为："<<i<<endl; 
    }
} 
bool Delete(List L,int i){   //按照下标删除 
    if(i<1||i>L->Last+1){
        cout<<"位序不存在元素"<<endl; 
    } 
    else{
        int j=0;
        for(j=i;j<=L->Last;j++){
            L->Data[j] = L->Data[j+1];
        }
        L->Last--;
        cout<<"删除成功"<<endl;
    }
} 

int main(){
    List L = Initialize();
    for(int i=1;i<4;i++){  //从第一个开始插入 
        int x;
        cin>>x;
        Insert(L,x,i);
    }
    show(L);
    Find(L,30);
    Delete(L,1);
    show(L);
    return 0;
}

优点：

无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速存取表中任一位置的元素

缺点：

插入删除需要移动大量元素
当线性表长度变化大时，难以确定存储空间容量
造成存储空间的“碎片”

线性表的链式存储结构（单链表）and 实现源码

解决了顺序存储的不足

所有都不考虑相邻位置，哪里有空就到哪里，只是让每个元素知道它下一个元素的位置在哪里就行了

对数据元素来说除了存储本身信息以外还要存储一个指示其直接后继的信息（直接后继的存储位置）
指针域：存储的信息成为指针或者链
数据域：存储元素信息
俩部分组成数据元素ai的存储映像，称为结点（Node）

头指针

第一节点

第二结点

最后结点（指针指向空）

头结点

是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域无意义（也可以存放链表长度）
头结点不一定时链表必须的要素

头指针

头指针指的是链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
头指针具有标识作用，所以用头指针冠以链表的名字
无论链表是否为空，头指针不为空，头指针是链表的必要元素

#include"iostream"
#include"stdlib.h" 
using namespace std;
typedef int ElementType;
typedef struct Dlb *Next;
struct Dlb{
    ElementType Data;
    Next next;

};
typedef Next Position;
typedef Next List;

List Initialize(){  //初始化 
    List L;
    L=(List)malloc(sizeof(struct Dlb));   //申请内存 
    if(!L)  //判空 
    exit(-1);
    L->next = NULL;
    cout<<"初始化成功"<<endl;
    return L;
}

void Insert(List L,ElementType x){
    Position tmp,pre;
    pre = L;
    cout<<"到了这里"<<endl; 
    while(pre){
        if(pre->next==NULL)
        break;
        pre = pre->next;

    }
    tmp = (Position)malloc(sizeof(struct Dlb));
    tmp->Data = x;
    tmp->next = pre->next;
    pre->next = tmp;
    cout<<"添加成功"<<endl;
}
int Length(List L){
    List p;
    int n=0;
    p=L->next;
    while(p){
        p=p->next;
        n++;
    }
    return n;
}
bool Delete(List L,int i){   //删除的是输入的数   包扩了按值查找 
    List tmp,pre;  //删除介质，游标
    pre = L;
    while(pre){
        if(pre->next->Data==i){
            break;
        }
        pre = pre->next;
    }
    tmp = pre->next;
    pre->next = tmp->next;
    free(tmp);
    cout<<"删除成功"<<endl;
}
void Findxb(List L,int k){
    List p;
    p=L->next;
    int n=1;
    while(p){
        if(n==k){
            cout<<p->Data<<endl;

        }
        p=p->next;
        n++;
    } 
} 
void show(List L){  //输出 
    List p= L->next;
    cout<<"链表输出：";
    while(p){
        cout<<p->Data<<" ";
        p=p->next;
    } 
}
int main(){
    List q = Initialize();
    List y;
    for(int i=0;i<3;i++){
        int x;
        cin>>x;
        Insert(q,x);
    }
    show(q); 
    cout<<Length(q);
    Delete(q,10);
    show(q);
    cout<<Length(q)<<" ";
    Findxb(q,2);

}

静态链表

用数组描述的链表叫静态链表

typedef struct{  //头指针的cur为第一个备用空闲的下标

ElemType data;
int cur;  //游标 为0时表示无指项

}

用游标代替指针，适合在没有指针的高级语言中用，道理和上面的单链表一样。

优点：

插入删除时只需要修改游标。
改进了顺序存储

缺点：

没有解决连续存储分配带来的表长难以确定的问题
失去了顺序存储结构随机存储的特性

循环链表

将单链表中终端结点的指针端由空指针指向头结点，就使整个单链表形成一个环，头尾相接的单链表称为单循环链表，简称单循环链表（circular linked list）

循环链表和单链表的主要差异在于循环的判断条件上，原来是判断p->next是否为空，现在是判断p->是否为头结点

源码：（只完成了增，删除修改查看没有实现，道理很简单，参照单链表可以写出来）

#include"iostream"
#include"stdlib.h"
using namespace std;
typedef struct Xhlb *Next;
struct Xhlb{
    int Data;
    Next next;
}; 
typedef Next List;
List Initialize(){
    List L;
    L = (List)malloc(sizeof(struct Xhlb));
    if(!L)
    exit(-1);
    L->next = L;
    cout<<"初始化成功"<<endl;
    return L;
}
void Insert(List L,int x){
    List tmp,per;
    per = L;
    while(per->next!=L){
        per = per->next;
    }
    tmp = (List)malloc(sizeof(struct Xhlb));
    tmp->Data = x;
    tmp->next=L;
    per->next = tmp;
    cout<<"添加成功！"<<endl;
}
int main(){
    List L = Initialize();
    for(int i=0;i<3;i++){
        int x;
        cin>>x;
        Insert(L,x);
    }
    List q;
    q=L->next;
    for(int i=0;i<6;i++){
        cout<<q->Data<<" ";

        if(q->next==L) 
        q=q->next->next;
        else
        q=q->next;
    }

}

输出结果

初始化成功
10 20 30
添加成功！
添加成功！
添加成功！
10 20 30 10 20 30

双向链表

在单链表中的每个结点中，再设置一个指向其前驱结点的指针域

结构

typedef struct Sxlb *Next;
typedef struct Sxlb *Prior;
struct Sxlb{
    ElemType data;
    Next next;
    Prior prior;
};

插入（有顺序）

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

删除（有顺序）

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

木兰辞

人生若只如初见，何事秋风悲画扇。