线性表（顺序表与单链表）

线性表

满足数据元素不同,但是在同一个线性表中的元素必定具有相同的特点,即属于同一数据对象, 相邻数据元素之间存在这个序偶关系. 诸如此类由(n>=0)个数据特性相同的元素构成的有限序列称为"线性表".

线性表中的元素的个数n定义为线性表的长度,如果n = 0则称为空表.

非空线性表特点

存在唯一的一个被称作"第一个"的数据元素
存在唯一的一个呗称作"最后一个"的数据元素
除了第一个之外,结构中的每个数据元素均有一个前驱
除了最后一个之外,结构中的每个数据元素都有一个后继.

线性表的类型定义

线性表是一个相当灵活的数据结构,其长度可根据需要增长或缩短,即对线性表的数据元素不仅可以进行访问,而且可以对其进行插入和删除等操作.

ADT List{
    Data: 线性表的数据对象集合为{a1,a2,......an},每个元素的类型均为DataType. 其中,除了第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每个元素有且只有一个直接后继元素. 数据元素之间的关系是一对一的关系.
    
Operation
    InitList(&L) 
    操作结果:初始化操作,建立一个空的线性表L.
    
    DestroyList(&L) 
    初始条件: 线性表L已存在
    操作结果: 销毁线性表L.
    
    ClearList(&L)
    初始条件: 线性表L已存在
    操作结果: 将L重置为空表.
    
    ListEmpty(L)
    初始条件: 线性表L已存在
    操作结果: 若L为空表,则返回true,否则返回false.
    
    ListLength(L)
    初始条件: 线性表L已存在
    操作结果: 返回L中数据元素的个数
    
    GetElem(L,i,&e)
    初始条件: 线性表L已存在,且1<=i<ListLength(L)
    操作结果: 用e返回L中第i个数据元素的值;
    
    LocateElem(L,e)
    初始条件: 线性表L已存在
    操作结果: 返回L中第1个值与e相同的元素在L中的位置. 若数据不存在则返回0;
    
    PriorElem(L,cur_e,&pre_e);
    初始条件: 线性表L已存在
    操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回其前驱,否则操作失败.
    
    NextElem(L,cur_e,&next_e);
    初始条件: 线性表L已存在
    操作结果: 若cur_e是L的数据元素,且不是最后一个,则用next_e返回其后继,否则操作失败.
        
    ListInsert(L,i,e);
    初始条件: 线性表L已存在,且1<=i<=listLength(L)
    操作结果: 在L中第i个位置之前插入新的数据元素e,L长度加1.
    
    ListDelete(L,i);
    初始条件: 线性表L已存在,且1<=i<=listLength(L)
    操作结果: 删除L的第i个元素,L的长度减1.
    
    TraverseList(L);
    初始条件: 线性表L已存在
    操作结果: 对线性表L进行遍历,在遍历的过程中对L的每个结点访问1次. 
    
}ADT List.

顺序表

typedef int ElemType;
typedef int Status;

//顺序存储
//顺序表 从下标0开始
typedef struct {
    ElemType *data;
    int length;
}sqlist;

1.1 顺序表的初始化

顺序表的初始化就是构成一个空的顺序表;
算法步骤:

  1. 为顺序表L动态分配一个预定义大小的数组空间,使elem 指向这段空间的基地址;
  2. 将表的当前长度设置为0;
//1.1 顺序表初始化
Status InitList(sqlist *L)
{
    L->data = malloc(sizeof(ElemType) * MAXSIZE);
    if(!L->data) exit(ERROR);
    L->length = 0;
    return OK;
}

1.2 顺序表的销毁

//1.2 顺序表销毁
Status DestroyList(sqlist *L)
{
    if(!L->data)
        return ERROR;
    else
    {
        free(L->data);
        L->data = NULL;
        L->length = 0;
        return OK;
    }
}

1.3 清空顺序表

//1.3 清空顺序表
Status ClearList(sqlist *L)
{
    L->length = 0;
    return OK;
}

1.4 判断顺序表是否空

//1.4 判断顺序表是否空
Status ListEmpty(sqlist L)
{
    return L.length?FALSE:TRUE;
}

1.5 获取顺序表长度

//1.5 获取顺序表长度
int ListLength(sqlist L)
{
    return L.length;
}

1.6 顺序表取值

算法步骤:

  1. 判断指定的位置序号i是否合理(1<=i<L.length),若不合理,则返回ERROR;
  2. 若i值合理,则将第i个数据元素L.data[i-1]赋值给参数e, 通过e返回第i个数据元素的传值.
//1.6 顺序表的取值
Status GetElem(Sqlist L,int i, ElemType *e){
    //判断i值是否合理, 若不合理,返回ERROR
    if(i<1 || i > L.length) return  ERROR;
    //data[i-1]单元存储第i个数据元素.
    *e = L.data[i-1];
    
    return OK;
}

1.7 顺序表查找元素并返回位

//1.7 顺序表查找元素并返回位置
int LocateElem(sqlist L,ElemType e)
{
    //是否空
    if(L.length == 0) return 0;
    //有的话返回位置
    for (int i = 0; i< L.length; i++) {
        if (L.data[i] == e) {
            return i+1;
        }
    }
    //没有返回0
    return 0;
}

1.8 获取e值的前一个值

//1.8 获取e值的前一个值
Status PriorElem(sqlist L,ElemType cur_e,ElemType *pre_e)
{
    //是否空
    if(L.length == 0) return ERROR;
    //查找cur_e的位置
    int i = LocateElem(L, cur_e);
    //如果不存在返回Err
    if(i == 0) return ERROR;
    //如果是第一个就不存在前驱
    if(i == 1) return ERROR;
    return GetElem(L, i-1, pre_e);
}

1.9 获取e值的后一个值

//1.9 获取e值的后一个值
Status NextElem(sqlist L,ElemType cur_e,ElemType *next_e)
{
    //是否空
    if(L.length == 0) return ERROR;
    //查找cur_e的位置
    int i = LocateElem(L, cur_e);
    //如果不存在返回Err
    if(i == 0) return ERROR;
    //判断是不是最后一个可以在GetElem判断了
    return GetElem(L, i+1, next_e);
}

1.10 顺序表的插入

算法步骤:

  1. 判断插入位置i是否合法(i值的合法范围1<=i<n+1),若不合法则返回ERROR;
  2. 判断顺序表的存储空间是否已满,若满则返回ERROR;
  3. 将第n个至第i个位置的元素依次向后移动一个位置,空出第i个位置(i = n+1)时无需要移动;
  4. 将要插入的新元素e放入第i个位置;
  5. 表长累积1.
//1.10 顺序表的插入
/*
 初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
 */
Status ListInsert(Sqlist *L,int i,ElemType 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-1; j>=i-1;j--){
       
            //插入位置以及之后的位置后移动1位
            L->data[j+1] = L->data[j];
        }
    }
    
    //将新元素e 放入第i个位置上
    L->data[i-1] = e;
    //长度+1;
    ++L->length;
    
    return OK;
    
}

1.11 顺序表删除

算法步骤:

  1. 判断删除位置i的合法(合法值 1 <= i <=n),若不合法则返回ERROR;
  2. 判断线性表是否为空
  3. 将第 i+1 个至第 n 个的元素依次向前移动一个位置( i=n 时无需移动)
  4. 表长减1;
//1.11 顺序表删除:删除位置i的数据
Status ListDelete(sqlist *L,int i)
{
    //判断是否空
    if (L->length == 0) {
        return ERROR;
    }
    
    //i是否合法
    if ((i<1) || i>L->length) {
        return ERROR;
    }
    
    for (int j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    
    L->length --;
    return OK;
}

1.12 遍历输出

//1.12 顺序输出List
Status TraverseList(sqlist L)
{
    for (int i = 0; i<L.length; i++) {
        printf("%d ",L.data[i]);
    }
    printf("\n");
    return OK;
}

链式表(单链表)

单链表

注意这里使用了头节点，为什么使用头节点？


头节点
typedef int ElemType;
typedef int Status;

typedef struct Node{
    ElemType data;
    struct Node* next;
}Node;

typedef struct Node *LinkList ;

2.1链式表的初始化

//2.1 初始化
Status InitList(LinkList *L)
{
    //创建头节点
    *L = (LinkList)malloc(sizeof(Node));
    if(*L == NULL) return ERROR;
    (*L)->next = NULL;
    
    return OK;
}

2.2 销毁

//2.2 销毁
Status DestroyList(LinkList *L)
{
    if (!*L) {
        return ERROR;
    }
    //需要先把节点都清空了
    ClearList(L);
    free(*L);
    *L = NULL;
    return OK;
}

2.3 清空

//2.3 清空
Status ClearList(LinkList *L)
{
    Node* next;
    Node* p = (*L)->next;
    while (p) {
        next = p->next;
        free(p);
        p = next;
    }
    (*L)->next = NULL;
    return OK;
}

2.4 判断是否空

//2.4 判断是否空
Status ListEmpty(LinkList L)
{
    return L->next?FALSE:TRUE;
}

2.5 获取长度

//2.5 获取长度
int ListLength(LinkList L)
{
    int i=0;
    Node* p = L->next;
    while (p) {
        p = p->next;
        i++;
    }
    return i;
}

2.6 取值

//2.6 取值:取位置i的值到e中
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;
    p = L->next;
    j = 1;
    while (p && j<i) {
        p = p->next;
        j++;
    }
    if(p && j==i)
    {
        *e =  p->data;
        return OK;
    }
    else
        return ERROR;
}

2.7 查找元素并返回位置

//2.7 查找元素并返回位置
int LocateElem(LinkList L,ElemType e)
{
    int i = 1;
    Node* p = L->next;
    while (p) {
        if(p->data == e)
        {
            return i;
        }
        p = p->next;
        i++;
    }
    //没有返回0
    return 0;
}

2.8 获取前一个值

//2.8 获取e值的前一个值
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{
    Node* pre = L;
    while (pre->next) {
        if(pre->next->data == cur_e)
            break;
        pre = pre->next;
    }
    //第一个点没前驱
    if(pre == L) return ERROR;
    //cur_e 不存在就返回ERROR
    if(!pre) return ERROR;
    *pre_e = pre->data;
    return OK;
}

2.9 获取后一个值

//2.9 获取e值的后一个值
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{
    Node* p = L->next;
    while (p) {
        if(p->data == cur_e)
            break;
        p = p->next;
    }
    //cur_e 不存在就返回ERROR
    if(!p) return ERROR;
    //最后一个没有后驱
    if(!(p->next)) return ERROR;
    *next_e = p->next->data;
    return OK;
}

2.10 插入

单链表的插入
//2.10 顺序表的插入：在i的位置插入e
Status ListInsert(LinkList *L, int i, ElemType e)
{
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    while (p && j<i) {
        p = p->next;
        j++;
    }
    
    if(p && j==i)
    {
        s = (Node*)malloc(sizeof(Node));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return OK;
    }
    else
        return ERROR;
}

2.11 删除

单链表的删除
//2.11 删除:删除位置i的数据
Status ListDelete(LinkList *L,int i)
{
    int j=0;
    //待删除的点的前一个点
    Node* pre_p = (*L);
    //需要删除的点
    Node* p;
    ElemType e;
    while (pre_p->next && j<i-1) {
        pre_p = pre_p->next;
        j++;
    }
    if(pre_p->next && j == i-1)
    {
        p = pre_p->next;
        e = p->data;
        pre_p->next = p->next;
        free(p);
        return OK;
    }
    return ERROR;
}

2.12 顺序输出List

//2.12 顺序输出List
Status TraverseList(LinkList L)
{
    LinkList p = L->next;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

2.13 前插法

单链表前插法
//2.13 前插法
void CreateListHead(LinkList *L, int n){
    InitList(L);
    for (int i=1; i<=n; i++) {
        Node* p = (Node*)malloc(sizeof(Node));
        p->data = i;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

2.14 尾插法

单链表后插法
//2.14 尾插法
void CreateListTail(LinkList *L, int n){
    InitList(L);
    Node* tail = *L;
    for (int i = 1; i<= n; i++) {
         Node* p = (Node*)malloc(sizeof(Node));
        p->data = i;
        p->next = NULL;
        tail->next = p;
        tail = tail->next;
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

友情链接更多精彩内容