数据结构 – 线性表+顺序表+单链表

PS：记得去年我都没有上过课，没事干复习一下第一章，仅此一章。

线性表

1. 线性表的顺序表示：顺序表，只能一维。
2. 线性表的链式表示：单链表，可以多维。
3. 线性表：有限序列、表头表尾元素、九种操作。

数组静态分配

#define MaxSize 50
typedef struct
 {
    ElemType data[MaxSize];
    int len;
}List;

数组动态分配

#define MaxSize 50
typedef struct 
{
    ElemType *data; //是一个地址，没有确切的空间，所以在使用时，需要动态申请空间
    int len;
}List;

动态分配语句（申请空间）

C L.data=(Elemtype*)malloc(sizeof(ElemType)*InitSize);
C++ = new ElemType[InitSize];

顺序表插入操作（前插）

数组下标0，顺序表下标1。

bool insertt(List &L,int i,ElemType e)
{
       if((i<1||i>L.len+1)||L.len>=MaxSize)
           return 0;
        for(int j=L.len;j>=i;j--)
            L.data[j]=L.data[j-1];
        L.data[i-1]=e;
        L.len++;
        return 1;
}

顺序表删除操作

bool Delete(List &L,ElemType e)
{
    if(i<1||i>L.len)
        return 0;
    e=L.data[i-1];
    for(int j=i;j<L.len;j++)
        L.data[j-1]=L.data[j];
    L.len--;
    return 1;
}

顺序表按值查找操作

int Locate(List &L,int i,ElemType e)
{
    for(int i=0;i<L.len;i++)
    {
        if(L.data[i]==e)
            return i+1;
    }
    return 0;
}

单链表特点

1. 数据元素存储位置不一定连续。
2. 通过指针实现线性逻辑关系。
3. 存放数据元素的时候，存放了数据本身+下一个数据元素的地址称作单链表的一个结点 data+next。
4. 单链表缺点：指针域会造成空间的浪费；不能实现随机存取，只能顺序存取。
5. 单链表七种基本操作。

单链表定义

typedef struct node
{
    ElemType data;
    struct node *nextt;
}node,*List;

单链表的两种形式

1. head（头指针）-->a1-->a2
   知道头指针，可以通过遍历方式找到线性表中所有结点。
2. 但是当单链表解决问题的时候，（第二种用的更多）
   head-->头结点，头结点的next域-->线性表中第一个元素的位置
   头结点的数据域往往不存在数据元素的，有时会存放一些关键信息（表长等）
   带有头结点，无论表是否为空，head都指向头结点。
   第二种优点：链表的第一个位置和其他位置的操作统一空表和非空表的操作统一。

判断单链表L为空

第一种：head头指针为NULL时
第二种：head-->next为NULL时（头结点的next的域为空）
注意：头指针指向头结点。（头指针，是指向链表头的指针；头结点，是链表头指针指向的节点。）

单链表的头插法操作

时间复杂度：O(N)
关键代码：

s->next=L->next
L->next=s

List headinsert(List &L)
{
    node *s; //当前插入的结点
    int x; //所插入的数据
    //初始化头结点
    L=(List)malloc(sizeof(node));
    L->next=NULL;
    cin>>x;
    while(x!=9999) // 插入多个结点
    {
        s=(node*)malloc(sizeof(node));//创建空间
        s->data=x;
        s->next=L->next;
        L->next=s;
        cin>>x;

    }
    return L;
}

单链表的尾插法操作

关键代码：

tail->next=s
tail=s

List tailinsert(List &L)
{
    int x; //所插入的数据
    L=(List)malloc(sizeof(node));
    node *s,*r=L;
    cin>>x;
    while(x!=9999) // 插入多个结点
    {
        s=(node*)malloc(sizeof(node));//创建空间
        s->data=x;
        tail->next=s;
        tail=s;
        cin>>x;
    }
    tail->next=NULL;
    return L;
}

单链表的按序号查找操作

node *get(List L,int i)
{
    int j=1;//从1开始
    node *p=L->next;//头结点不保存元素，所以从下一个开始
    if(i==0) //代表是头结点
        return L;
    if(i<1)
        return NULL;
    while(p&&j<i) //遍历单链表
    {
        p=p->next;
        j++;
    }
    return p;//找到了，返回该结点
}

单链表的按值查找操作

node *Locate(List L,EleType e)
{
    node *p=L->next;
    while(p!=NULL&&p->data!=e) // 为空说明遍历完成
        p=p->next;
    return p;
}

单链表的插入结点操作

和头插法不一样的是：需要知道位置。

p=get(L,i-1);
s->next=p->next;
p->next=s;

单链表的没有头结点的插入节点操作

首先要判断是否是在头部插入的。

s->next=head
head=s

前插法和后插法区别

1. 如果第i号位置已知，两者就会产生区别：
   前插法需要遍历找到i-1号位置；
   后插法需要i号位置。
   前插法需要\(O(N)\)，后插法需要\(O(1)\)。
2. 后插法可以实现前插法。先插入再交换。时间复杂度\(O(1)\)。

单链表删除节点操作

a[i-1]、a[i]、a[i+1] 删除中间元素。

p=get(L,i-1)
q=p->next
p->next=q->next
free(q)

单链表删除给定节点 *p

先交换a[i+1]和a[i]的位置，在删除第三个元素。

q=p->next;
p->data=p->next->data;
p->next=q->next;
free(p);

单链表求表长

int cnt=0;
p=head;//是不计算头结点的
while(p->next!=NULL)
{
   cnt++;
   p=p->next;
}

特殊链表

双链表、循环链表、静态链表
双链表和循环链表 结点结构：prior+data+next

typedef struct node
{
    ElemType data;
    struct node *prior,*next;
}node,*List;

双链表的插入操作

前插法和后插法都可以，\(O(1)\)。
后插法代码：

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

表尾插入和表中表头代码是不一样的。

双链表的删除操作

时间复杂度：\(O(1)\)。
a[i-1]=p,a[i]=q,删除a[i]。

p->next=q->next;
q->next->prior=p;
free(q);
在表尾进行操作是有差异的。

循环链表

仅仅设置为指针操作效率会更高。
每一个结点插入和删除都一样。

循环双链表

循环链表的判空表：

L->next==L;

双循环链表判空表：

L->next==L;
L->prior==L;

静态链表：(并不常用)

用数组来实现链式存储。
数据域+next域（指向下一个结点的下标）。
注意：最后一个an指向-1。

#define N 50
typedef struct node
{
    ElemType data;
    int next;
}List[N];

顺序表VS链表

1. 存储方式：
   顺序表：可以实现顺序存取 + 随机存取。
   链表：只能实现顺序存取。
2. 逻辑结构和物理结构：
   顺序表：逻辑相邻物理上也相邻，通过相邻表示逻辑关系。
   链表：逻辑相邻物理上不一定相邻，通过指针表示逻辑关系。
3. 删除&插入
   顺序表：顺序表为\(O(N)\),且需要移动大量的元素。
   链表:\(O(1)\)(结点指针已知);\(O(N)\)(结点指针未知)，但是操作时只需修改指针
4. 查找
   按值查找：单链表和无序顺序表都为\(O(N)\)。
   按序查找：单链表\(O(N)\),顺序表\(O(1)\)。
5. 内存空间
   顺序存储：无论静态还是费静态都需要预先分配合适的内存空间。
   静态分配时预分配空间太大回造成浪费，太小会造成溢出。
   动态分配时虽不会溢出但是扩充需要大量移动元素，操作效率低。
   链式存储：在需要时分配结点空间即可，高效方便，但指针要使用额外空间。