Machine World | Math World

记录实验过程

【数据结构】线性表的C语言实现

【背景】

    考研复习到后期,因为专业课的需要开始对数据结构学科的复习,把之前的实验重新用C语言实现了一遍,其中线性表部分是复习的第一部分,编码过程中也发现之前的潜在问题,以前的编码利用C/C++混编,个人在纯C编程上一定程度上碰了壁,如指针与引用与取地址符号等问题在C语言上的区分,更加明确了C与C++之间的界限。而今天的主角是线性表。

    线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。

    线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。

【源码运行环境】

操作系统:MAC OS X 10.13.4

编译环境:CLion (C++ 14) cmake

【源码实现】

List.h 源码部分

//
// Created by WellLee on 2018/10/27.

//

#ifndef LIST_LIST_H
#define LIST_LIST_H

#include <stdio.h>
#include <stdlib.h>
/*
 * 说明:define 定义一些常用的符号特性
 * 作用:增加代码可读性
 * Author: WellLee
 * Last Modified: 2018年10月26日23:27:51
 */
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0
#define SqListMAXSIZE 20
typedef int Status;
typedef int Elem;
/*
 * 结构:顺序线性表
 * 作用:定义了顺序线性表的一些结构特性,封装了常用的线性表操作
 * Author: WellLee
 * Last modified: 2018年10月26日23:26:36
 */
typedef struct SequenceList{
    Elem elements[SqListMAXSIZE];
    int Cur_length;
    int Max_Length;
}SqList;

Status InitList(SqList *L);
Status ListEmpty(SqList *L);
Status ClearList(SqList *L);
Status GetElem(SqList *L, int i, Elem *e);
Status LocateElem(SqList *L, Elem e, int *l);
Status SequenceListInsert(SqList *L, int i, Elem e);
Status SequenceListDelete(SqList *L, int i, Elem *e);
Status ListLength(SqList *L,int *length);
void showElements(SqList *L);
/*
 * 结构:链式线性表
 * 作用:定义了链式线性表的一些结构特性,封装了常用的线性表操作
 * Author: WellLee
 * Last modified: 2018年10月28日00:15:42
 */
typedef struct Node{
    Elem e;
    struct Node *next;
}Node;
typedef struct Node *Link;
Status InitLinkList(Link *L);
Status LinkListEmpty(Link L);
void ShowLinkList(Link L);
Status DestroyList(Link *L);
Status LinkListLength(Link L,int *length);
Status GetElemFromLinkList(Link L, int i,Elem *e);
Status LocateElemFromLinkList(Link L,Elem e, int *i);
Status LinkListInsert(Link *L, int i, Elem e);
Status LinkListDelete(Link *L, int i, Elem *e);
Status LinkListReverse(Link *L);


#endif //LIST_LIST_H

SequenceList.c 源码部分:

//
// Created by WellLee on 2018/10/26.
//
/*
 * 文件名:SequenceList.c
 * 作用:补充对顺序线性表的操作
 * Author: WellLee
 * Last Modified: 2018年10月26日23:30:59
 */
#include "List.h"
#include "memory.h"
/*
 * 方法名:InitList
 * 作用:对顺序线性表进行初始化操作
 * Author: WellLee
 * Last Modified:2018年10月27日23:27:19
 */
Status InitList(SqList *L)
{
    int total;
    L->Cur_length = 0;
    L->Max_Length = SqListMAXSIZE;
    printf("请输入您要插入的元素个数(不超过20个)\n");
    scanf("%d", &total);
    if(total < 0 || total > 20)
    {
        printf("数组溢出\n");
        return OVERFLOW;
    }
    if(total == 0)
    {
        printf("There is nothing to do \n");
        return FALSE;
    }
    for(int i = 0; i < total; i++)
    {
        printf("请输入第%d个元素: ",i+1);
        scanf("%d",&L->elements[i]);
    }
    L->Cur_length = total;
    return TRUE;

}
/*
 * 方法名:showElements
 * 作用:显示顺序线性表的元素
 * Author: WellLee
 * Last Modified:2018年10月27日23:28:13
 */
void showElements(SqList *L)
{
    if(ListEmpty(L))
    {
        printf("这是一张空表\n");
        return;
    }
    printf("线性表元素如下:总元素为%d\n", L->Cur_length);
    for(int i = 0; i < L->Cur_length; i++)
    {
        printf("%d ",L->elements[i]);
    }
    printf("\n");
}
/*
 * 方法名:ListEmpty
 * 作用:判断线性表是否为空
 * Author: WellLee
 * Last Modified:2018年10月27日23:28:13
 */
Status ListEmpty(SqList *L)
{
    if(L->Cur_length == 0)
    {
        return TRUE;
    }
    return FALSE;
}
/*
 * 方法名:ClearList
 * 作用:清空顺序线性表
 * Author: WellLee
 * Last Modified:2018年10月27日23:28:13
 */
Status ClearList(SqList *L)
{
    memset(L->elements,0, sizeof(L->elements));
    L->Max_Length = 0;
    L->Cur_length = 0;
    return TRUE;
}
/*
 * 方法名:GetElem
 * 作用:获取顺序线性表指定位置的元素
 * Author: WellLee
 * Last Modified:2018年10月27日23:28:13
 */
Status GetElem(SqList *L, int i, Elem *e)
{
    if(i >= L->Cur_length || i < 0)
    {
        return OVERFLOW;
    }
    Elem a = L->elements[i];
    *e = a;
    printf("e = %d\n", *e);
    return TRUE;

}
/*
 * 方法名:LocateElem
 * 作用:定位元素在线性表的第一次出现位置
 * Author: WellLee
 * Last Modified:2018年10月27日23:28:13
 */
Status LocateElem(SqList *L, Elem e, int *l)
{
    if(ListEmpty(L))
    {
        return OVERFLOW;
    }
    for(int i = 0; i < L->Cur_length; i++)
    {
        if(e == L->elements[i])
        {
            *l = i + 1;
            return TRUE;
        }
    }
    return FALSE;
}
/*
 * 方法名:SequenceListInsert
 * 作用:顺序线性表插入操作
 * Author: WellLee
 * Last Modified:2018年10月27日23:28:13
 */
Status SequenceListInsert(SqList *L, int i, Elem e)
{
    if(i < 0 || L->Cur_length > (SqListMAXSIZE - 1))
    {
        return OVERFLOW;
    }
    if(i > L->Cur_length - 1)
    {
        printf("当前线性表长度为:%d ,无法满足您的插入需求\n");
        return FALSE;
    }
    for(int j = L->Cur_length - 1;j >= i; j--)
    {
        L->elements[j + 1] = L->elements[j];
    }
    L->elements[i] = e;
    L->Cur_length  += 1;
    return TRUE;
}
/*
 * 方法名:SequenceListDelete
 * 作用:删除顺序线性表中的元素
 * Author: WellLee
 * Last Modified:2018年10月27日23:28:13
 */
Status SequenceListDelete(SqList *L, int i, Elem *e)
{
    if(ListEmpty(L) || i > L-> Cur_length - 1)
    {
        return OVERFLOW;
    }
    *e = L->elements[i];
    for (int j = i; j < L->Cur_length - 1; j++)
    {
        L->elements[j] = L->elements[j+1];
    }
    L->elements[L->Cur_length - 1] = 0;
    L->Cur_length -= 1;
    return TRUE;
}
/*
 * 方法名:ListLength
 * 作用:获取线性表的长度
 * Author: WellLee
 * Last Modified:2018年10月27日23:28:13
 */
Status ListLength(SqList *L,int *length)
{
    *length = L->Cur_length;
    return TRUE;
}

LinkList.c 源码如下:

//
// Created by WellLee on 2018/10/28.
//
#include "List.h"
#include "time.h"
/*
 * 方法名:InitLinkList
 * 作用:初始化链式线性表
 * Author: WellLee
 * Last Modified:2018年10月28日12:21:18
 */
Status InitLinkList(Link *L)
{
    Link p,r;
    int length;
    srand(time(0));
    printf("请输入链表长度: ");
    scanf("%d",&length);
    *L = (Link)malloc(sizeof(Node));
    r = *L;
    for (int i = 0; i < length; i++) {
        p = (Node *)malloc(sizeof(Node));
        p->e = rand() % 100 + 1;
        r->next = p;
        r = p;
    }
    r->next = NULL;
    printf("链表创建完成\n");
}
/*
 * 方法名:ShowLinkList
 * 作用:显示链式线性表中的元素
 * Author: WellLee
 * Last Modified:2018年10月28日12:21:18
 */
void ShowLinkList(Link L)
{
    Link temp = L->next;
    if(!temp)
    {
        printf("这是一张空表\n");
        return;
    }
    printf("链式线性表元素如下:\n");
    while(temp != NULL)
    {
        printf("%d ",temp->e);
        temp = temp->next;
    }
    printf("\n");
}
/*
 * 方法名:LinkListEmpty
 * 作用:判断链式线性表是否为空
 * Author: WellLee
 * Last Modified:2018年10月28日12:21:18
 */
Status LinkListEmpty(Link L)
{
    if(L->next == NULL)
    {
        return TRUE;
    }
    return FALSE;
}
/*
 * 方法名:DestroyList
 * 作用:销毁链式线性表
 * Author: WellLee
 * Last Modified:2018年10月28日12:21:18
 */
Status DestroyList(Link *L)
{
    Link temp = *L;
    Link freePoint;
    freePoint = temp;
    temp = temp->next;
    freePoint->next = NULL;
    while(temp != NULL)
    {
        freePoint = temp;
        temp = temp->next;
        printf("释放元素为%d 的节点内存\n",freePoint->e);
        free(freePoint);

    }
    return TRUE;

}
/*
 * 方法名:LinkListLength
 * 作用:获取链式线性表长度
 * Author: WellLee
 * Last Modified:2018年10月28日12:21:18
 */
Status LinkListLength(Link L,int *length)
{
    Link temp = L->next;
    *length = 0;
    while(temp != NULL)
    {
        *length += 1;
        temp = temp->next;
    }
}
/*
 * 方法名:GetElemFromLinkList
 * 作用:从链式线性表中获取指定位置的元素
 * Author: WellLee
 * Last Modified:2018年10月28日12:21:18
 */
Status GetElemFromLinkList(Link L, int i, Elem *e)
{
    int cur_length;
    LinkListLength(L, &cur_length);
    if(!L || i > cur_length || i <= 0){
        printf("越界!\n");
        return OVERFLOW;
    }
    Link temp = L->next;
    for(int j = 0; j < i - 1; j++)
    {
        temp = temp->next;
    }
    *e = temp->e;
    return TRUE;

}
/*
 * 方法名:LocateElemFromLinkList
 * 作用:定位元素在链式线性表中的位置
 * Author: WellLee
 * Last Modified:2018年10月28日12:21:18
 */
Status LocateElemFromLinkList(Link L,Elem e,int *i)
{
    int cur_length= 0;
    LinkListLength(L, &cur_length);
    if(!L)
    {
        printf("越界\n");
        return OVERFLOW;
    }
    Link temp = L->next;
    int flag = FALSE;
    int c;
    for(c = 0; c < *i; c++){
       if(temp->e != e){
           temp = temp->next;
           continue;
       }
       flag = TRUE;
       break;
    }
    if(flag) {
        *i = c + 1;
    } else{
        *i = -1;
    }
    return TRUE;
}
/*
 * 方法名:LinkListInsert
 * 作用:向链式线性表中指定位置插入元素
 * Author: WellLee
 * Last Modified:2018年10月28日12:21:18
 */
Status LinkListInsert(Link *L, int i, Elem e)
{

    Link temp = *L;
    Link p = *L;
    temp = temp->next;
    int length = 0;
    LinkListLength(*L, &length);
    if(i < 0 || i > length + 1) {
        printf("越界\n");
        return OVERFLOW;
    }
    for(int c = 0; c < i - 1; c++)
    {
        p = temp;
        temp = temp->next;
    }
    Link node = (Link)malloc(sizeof(Node));
    node->e = e;
    node->next = temp;
    p->next = node;
    return TRUE;

}
/*
 * 方法名:LinkListDelete
 * 作用:删除链式线性表中指定位置的元素
 * Author: WellLee
 * Last Modified:2018年10月28日12:21:18
 */
Status LinkListDelete(Link *L, int i, Elem *e)
{
    Link temp = *L;
    Link p = *L;
    temp = temp->next;
    int length;
    LinkListLength(p,&length);
    if(i < 0 || i > length)
    {
        printf("越界\n");
        return OVERFLOW;
    }
    for(int c = 0; c < i-1; c++)
    {
        p = temp;
        temp = temp->next;
    }
    Link freepoint;
    freepoint = temp;
    p->next = temp->next;
    *e = freepoint->e;
    free(freepoint);
    return TRUE;
}

【分析/总结】

顺序线性表具有如下优点

  1. 无需为表示表中元素之间的逻辑关系增加额外的存储空间;

  2. 考研快速地存储表中任一位置的元素;

顺序线性表具有以下缺点

  1. 插入和删除操作需要移动大量元素;

  2. 当线性表长度变化较大时,难以确定存储空间的容量;

  3. 造成存储空间的碎片;

链式线性表具有以下优点

  1. 插入和删除操作只需要改变指针指向,时间效率高;

  2. 不需要提前分配空间,随用随分配,灵活性高;

  3. 在内存空间分配上灵活性高;

链式线性表具有以下缺点

  1. 查找效率慢;

  2. 需要为地址开辟额外的存储空间;

总结:

从功能需求上看若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。反之宜采用链式存储结构。

而从空间分配上看,当线性表元素变化较大或者根本不知道有多大的时候,宜采用单链表存储结构。反之宜采用顺序存储结构。

【参考文献】

《大话数据结构》.程杰.清华大学出版社

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注