线性表--顺序表和单链表

线性表(List):0个或多个数据元素的有限序列。
线性表的数据集合为{a1,a2,a3...an},假设每个元素的类型均为DataType。其中除第一元素a1外，每个元素有且只有一个前驱元素，除最后一个an元素外，每一个元素有且只有一个后继元素。数据元素之间的关系时一对一的关系。

一、顺序表

• 线性表 -- 顺序存储结构
• 线性表的顺序存储又称顺序表，用一组地址连续的存储单元依次存储线性表中的数据元素，从而使逻辑相邻的两个元素在物理位置上也相邻。
• 开辟一段连续的存储空间

可以使用一位数组来实现顺序存储结构，一位数组可以静态分配，也可以动态分配。静态分配数组大小事先固定，一旦空间占满，再加数据则产生溢出。

1、初始化：建立一个空的线性表L

• 静态分配

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

//定义数据类型，根据实际情况而定，这里设为int
typedef int DataType;
//Status是函数类型，其值是函数结果状态码如ok、ERROR等
typedef int Status;

//线性表顺序存储结构
typedef struct{
    DataType *data;
    int length;
}sqlist;

//初始化线性表
/*
 1、返回一个状态表示初始化结果
 2、为数据表分配空间
 */
Status InitList(sqlist *L){
    //为数据表分配一个大小为MAXSIZE的数组空间，数据类型是DataType
    L -> data = malloc(sizeof(DataType) * MAXSIZE);
    
    //存储空间分配失败，退出
    if (!L -> data) exit(ERROR);
    
    //设置空表的长度为0
    L -> length = 0;
    return OK;
}

• 动态分配

2、插入数据

• 2.1 判断顺序表是否存在
• 2.2 插入数据的位置是否合法
• 2.3 将要插入位置的数据及后面的数据后移
• 2.4 将数据存入该位置
• 2.5 修改顺序表当前长度

插入数据.png

//顺序表的插入
/*
 *1、判断顺序表是否存在
 2、插入的数据是否合法
 3、找到位置，将此处及后面数据后移，修改length
 */
Status InsertList(sqlist *L,int i,DataType e){
    //判断i值是否合法(第一个位置预留不做数据存储用)
    if (i < 1 || i > L -> length + 1) return  ERROR;
    //存储空间是否已满
    if (L -> length == MAXSIZE) return ERROR;
    
    //判断插入数据是否是末位，是直接插入不用移动，否则先移动数据空余位置在插入数据
    //从最后一位开始向后移动
    
    if (i <= L -> length) {
        for (int j = L -> length; j >= i; j --) {
            L -> data[j + 1] = L -> data[j];
        }
    }

    //将数据e插入i位置
    L ->data[i] = e;
    L -> length  = L -> length + 1;
    
    return OK;
}

3、删除数据

• 3.1 判断顺序表是否存在
• 3.2 删除数据的位置是否合法
• 3.3 将要删除数据位置后的数据前移
• 3.4 修改顺序表当前长度

删除数据.png

//顺序表的删除
/*
 表已存在，最后一个数据时数组长度length-1即可，其他，将数据位置之后的数据前移后length -1
 */
Status ListDelete(sqlist *L, int i){
    
    //线性表为空直接返回
    if (L ->length == 0) return ERROR;
    
    //删除的数据在线性表中
    if (i < 1 || (i > L->length)) return ERROR;
    
    //删除的数据位置之后的数据前移，length - 1
    for (int j = i; j < L-> length; j ++) {
        L -> data[j-1] = L->data[j ];
    }
    //修改length
     L -> length = L -> length -1;
    return  OK;
}

4、查找元素、取值

//顺序表的取值
Status GemList(sqlist *L,int i,DataType *e){
    //取值是否存在表中(第一位置留用，不做存储数据使用)
    if (i < 1 || i > L -> length) return  ERROR;
    *e = L -> data[i-1];
    return OK;
}
//顺序表查找元素并返回位置
//返回表中第一个满足的元素位置
int LocateElem(sqlist L,DataType e){
    int I;
    if (L.length == 0) return ERROR;
    for ( i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            break;
        }
    }
    if (i >= L.length) return ERROR;//数据不存在
    return i + 1;
}

运行测试

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    sqlist lb;
    Status iStatus;
    iStatus = InitList(&lb);
    printf("状态码：%d\n",iStatus);
    
    //for循环插入索引 1 -10 对应 100 - 109
    for (int i = 0; i < 10; i++) {
        iStatus = InsertList(&lb, i + 1, i + 100);
    }
    TraverseList(lb);
    
    printf("\n");
    //4位置 插入数据55
    iStatus = InsertList(&lb, 4, 55);
    printf("%d插入数据4 -- 55\n",iStatus);
    TraverseList(lb);
    
    
    //删除数据位置5数据
    printf("\n");
    iStatus = ListDelete(&lb, 5);
    printf("删除位置5的数据：%d\n",iStatus);
    TraverseList(lb);
    
    printf("\n");
    
    iStatus = ListDelete(&lb, lb.length);
    printf("删除最后一个数据：%d\n",iStatus);
    TraverseList(lb);
    
    //顺序表的取值
    printf("\n");
    DataType e;
    iStatus = GemList(&lb, 4, &e);
    printf("取值结果：%d，第4位置 -- 元素%d\n",iStatus,e);
    
    //查找元素
    int location = LocateElem(lb, 107);
    printf("查找元素107 -- 位置%d\n",location);
    return 0;
}

最好情况：删除(i = n)和插入(i = n+ 1)位置在表尾，无需移动数据直接插入、删除、循环0次，时间复杂度是O(1)。
最坏情况：
插入位置在表头(i=1)，需要将原有的n个元素向后移动，循环n次，时间复杂度O(n)。
删除位置在表头(i=1)，需要将原有的n-1个元素向前移动，循环n-1次时间复杂度O(n)。
平均情况：
假设新元素插入到任何一个位置的概率是相同的(P = 1/(n+ 1)),i=1时循环n次，i = 2时循环n-1次，i = n+1，循环0次。平均循环次数:n = {n + (n - 1) + (n-2) ... + 1)}/n = (n+ 1)/2。其时间复杂度O(n)。

二、单链表

• 单链表：线性表的链式存储结构
  单链表：使用任意一组存储单元来存储数据元素，不需要使用地址连续的存储单元，从而使在逻辑上相邻的数据在物理地址上不需要相邻。其有若干个结点组成，每个节点有两个部分组成，一部分存储数据称为数据域，一部分存储指针指向下一个结点称为指针域。从而达成数据元素上的逻辑相邻。

单链表.png

typedef int Status;//函数类型，返回值为状态，ok，error
typedef int ElemType;//数据类型，根据实际情况而定，这里设定int

//定义结构体类型结点
typedef struct Node{
    ElemType data;//数据域
    struct Node *next;//指针域
}Node;

typedef struct Node *LinkList;


//初始化单链表
Status InitList(LinkList *L){
  //创建头结点，并使L指向头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if (*L == NULL) return  ERROR;
    //将头结点的指针域置空
    (*L) -> next = NULL;
    (*L) -> data = 0;
    return OK;
}

单链表的创建---头插法和尾插法

1、头插法：一只在头结点之后插入数据。生成的链表结点的次序和插入顺序相反。

头插法.png

//前插法 链表的一种创建方法
void CreatListHead(LinkList *L,int n){
    LinkList p;
    //创建一个带头结点的单链表
    *L = malloc(sizeof(Node));
    (*L) -> next = NULL;
    //循环前插入随机数据
    for (int i = 0; i< n; i++) {
        //生成新结点
        p = malloc(sizeof(Node));
        //新结点赋值
        p->data = i + 200;
        //新结点指向头结点指向的结点
        p->next = (*L)->next;
        //头结点指向新结点
        (*L)->next = p;
    }
}

2、尾插法：一直项链表的尾部插入数据，生成链表次序和插入数据次序相同。

创建使用尾插法时，添加一个尾结点提高插入的操作效率。如果没有尾结点每次插入数据都需要遍历查找到尾结点在插入数据，如此需要循环n次，时间复杂度为O(n)设置尾结点后，直接将尾结点指向新结点，并将新结点作为表尾结点即可。不需要遍历整个表，其时间复杂度时O(1)。

后插法.png

//后插法
void CreatListTail(LinkList *L,int n){
    LinkList p,r;
    //建立带头结点的单链表
    *L = malloc(sizeof(Node));
    //指向尾部结点
    r = *L;
    //循环插入
    for (int i =0; i< n; i++) {
        //创建新结点
        p = malloc(sizeof(Node));
        p -> data = i + 200;
        //表尾结点指向新结点
        r -> next = p;
        //新的结点作为为表尾结点
        r = p;
    }
    //将为结点指针指向null
    r -> next = NULL;
}

3、插入数据

• 1、遍历单链表找到插入位置的前结点
• 2、创建新结点，赋值数据域
• 3、新结点指针指向插入位置的结点
• 4、前结点的指针指向新结点

插入.png

//单链表插入数据
/*
 1、遍历单链表找到插入位置前结点
 2、创建新结点，赋值数据域
 3、新结点指针指向插入位置的结点
 4、前结点的指针指向新结点
 */
Status InsertList(LinkList *L,int i,ElemType e){
    
    //判断单链表是否存在
    int j;//用于计数

    LinkList s,p;//s为创建新结点，p为插入位置结点
    
    //遍历找到插入位置的前结点
    p = *L;
    j = 1;
    while (p && j < i) {
        p = p -> next;
        j ++;
    }
    
    //判断第i个元素是否存在
    if (!p || (j > i)) return ERROR;
    
    //创建新结点，赋值数据域
    s = malloc(sizeof(Node));
    s ->data = e;
    
    //新结点指针指向插入位置数据
    s -> next = p ->next;
    
    //前结点指针指向新创结点
    p->next = s;
    
    return  OK;
}

4、删除数据

• 1、遍历单链表找到删除位置的前结点
• 2、前结点指针指向删除结点指针指向的后结点
• 3、free释放，回收空间

删除.png

//删除元素
/*
 1、查找删除元素前结点
 2、前结点指针指向删除结点指针指向的后结点
 3、free释放删除结点，回收空间
 */
Status DelectList(LinkList *L,int i,ElemType *e){
    if ((*L) -> next  == NULL ) return 0;
    int j = 1;//计数
    LinkList p,q;
    p = (*L) -> next;
    //查找删除结点前结点
    while (p->next && (j < (i-1))) {
        p = p->next;
        j ++;
    }
    //当i>n 或者 i<1 时,删除位置不合理
    if (!(p->next) || (j>i-1)) return  ERROR;
    //获取删除结点
    q = p->next;
    //前结点指向删除结点的后结点
    p->next = q->next;
    //将删除结点值放回
    *e = q ->data;
    free(q);//释放存储空间
    return OK;
}

顺序表和链表的比较

	顺序表	链表
数据存取	顺序存取、随机存取、只需访问一次	从头遍历访问查找位置
逻辑结构	逻辑相邻	逻辑相邻
物理结构	物理存储位置	不需要物理存储位置相邻
按值查找时间复杂度	表内数据有序时(可二分O(log2n)),无序时O(n)	O(n)
按序号查找时间复杂度	O(1)	O(n)
插入、删除	移动大量的数据元素	只需修改结点指针域