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

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)\)。

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

原文：https://www.cnblogs.com/OFSHK/p/13169987.html