数据结构-线性表（顺序和链式）

• 一.线性表
• • 1.线性表的顺序存储方式
  • 2 .线性表的链式存储方式

线性表：一个或者多个元素构成的有限序列；

1. List 1 有顺序的序列；
2. 有前驱和后继的元素，除了第一和最后一个元素之外。
3. 元素之间的关系如下图所示：
   线性表的抽象数据类型：
   
   其主要包含数据的对象集合数据的逻辑关系，以及数据的操作；

线性表的存储方式： 我们在学习数据结构序言的时候知道，数据结构的逻辑结构有两种即线性与非线性，其存储方式也有俩种，即顺序存储和链式存储；
顺序存储：即在内存单元中开辟出一段连续的空间用来存放线性表中的元素；
实现代码C语言：

#include
#include
#include


#define ElementType int   //为类型int宏定义一个新的名称
#define MAXSIZE 10   //定义初始的空间分配量
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
typedef int Status;//函数的类型
//1.定义结点和指针
typedef struct 
{
    ElementType data[MAXSIZE];//定义数据的存储数组
    int length;                //线性表的长度
    
}sqlist;
//创建一个空的线性表
Status CreatList(sqlist *L){
    int tempdata;  //临时数据，用来保存输入的值
    L->length=0;  //初始长度为0
    for(int i=0;i<=MAXSIZE;i++){
        printf("请输入第%d个元素的值，-1结束n", i+1);
        scanf("%d", &tempdata);   //接受控制台的输入，并保存在临时数据中
        if(tempdata==-1){   //判断是否为输入结束语句
            return OK;   //若为输入结束语句，则直接结束方法
        }
        L->data[i] = tempdata;   //若不是结束语句则将临时数据存放在对应位置中
        L->length++;   //每放入一个数据，则长度length+1
    }
    return OK;
}
//获取线性表的长度
Status Getlength(sqlist *L){
    return  L->length;
}
//判断线性表是否为空
Status ListEmpty(sqlist *L)
{
     if (L->length==0)
     {
         
         return TURE;
     }
     else return FALSE;
   
}
//获得元素操作
Status GetElem(sqlist L,int i,ElementType *e)
{
    if (L.length==0||i<1||i>L.length)
    {
        return ERROR;
    }
    *e=L.data[i-1];
    return OK;
}
//ClearList(*L)将线性表清空

//插入操作
Status ListInsert(sqlist *L,int i,ElementType e)
{
    int k;//定义一个临时的数组
    if(i<1 || i>L->length+1)   //插入位置有误
    {
    return ERROR;
    }
    if(L->length==MAXSIZE)
    {
        return ERROR;
    }
    if(ilength)
    {
        for (k=L->length-1; k >=i-1; k--)
        {
            
            L->data[k+1]=L->data[k];
        }  
    }
     L->data[i-1]=e;  
     L->length++;
     return OK;
}
//删除操作

Status ListDelete(sqlist *L,int i,ElementType *e)
{
    int k;
    if(L->length==0)
    return ERROR;
    if (i<1||i>L->length-1)
    return ERROR;
    *e=L->data[i-1];
    if (ilength)
    {
        for (k=i; k < L->length; k++)
        {
            
            L->data[k]=L->data[k+1];
        }
        
    }
    L->length--;
    return OK;  
}
int OutputList(sqlist *L, int i) {

    int j;
    printf("更新后的线性表为：");
    for (j = 0; j < i; j++) {
        printf("%dt", L->data[j]);

    }

    return OK;
}

int main() {
    sqlist S;
    ElementType apple;
    char a;
    Status xx; 
    a = 'Y';
    int k, data, position, *e;
    CreatList(&S);
    xx=ListEmpty(&S);
    printf("判断线性表是否为空：%dn",xx);
    k=Getlength(&S);
    printf("输出元素的个数: %dn",k);
    printf("输出线性表: n");
    OutputList(&S,k);
    ListDelete(&S,2,&apple);
    k=Getlength(&S);
    printf("输出元素的个数: %dn",k);
    printf("输出删除操作后的线性表: n");
    OutputList(&S,k);
    ListInsert(&S,3,3);
    k=Getlength(&S);
    printf("输出元素的个数: %dn",k);
    printf("输出删除操作后的线性表: n");
    OutputList(&S,k);
    return OK;
}

对于顺序存储方式而言，操作插入和删除某一个元素的时候，需要牵扯到大量的元素的移动，对于我们大型数据处理是极其不变的。

链式存储；其在逻辑上连续的线性表在存储的时候利用指针操作（个人理解就是不再要求存储方式和逻辑的对应，利用我们的指针描述其前驱后继的逻辑关系即可），有上一节点指向下一个节点的存储方式，其在内存上不连续，利用指针实现逻辑的连续性；
实现方式：对于顺序存储方式而言，数据元素仅仅含有数据元素信息，我们想让元素能含有前驱后继的关系，即在数据中存储后继的地址信息操作即可

//
//  main.c
//  LinkedList
//

#include 
#include "stdlib.h"
#include "string.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int State;
typedef int ElemType;
typedef struct Node{   //结点的存储结构
    ElemType data;   //结点的数据部分
    struct Node* next;   //指向结点的下一结点
}Node;

typedef struct Node *LinkList;  //定义LinkList（其实也就是头结点）

//初始化单链表
State InitLinkList(LinkList *L){
    *L = (LinkList)malloc(sizeof(Node));   //为头结点分配内存
    if(!*L){   //如果头结点不存在，即分配内存失败则返回ERROR
        return ERROR;
    }else{   //如果头结点存在则说明初始化成功
        return OK;
    }
    (*L)->next = NULL;   //初始单链表头结点的指针域为空
}

//单链表是否为空
State isEmpty(LinkList L){
    if(L->next){   //判断头结点的指针域是否为空
        return FALSE;   //头结点的指针域非空则返回FALSE；
    }else{
        return TRUE;   //头结点指针域为空则返回TRUE；
    }
}

//获得单链表的长度
State listLength(LinkList L){
    int i=0;  //计数器，初始为0
    LinkList p;  //定义临时结点
    p = L->next;  //单链表的首个结点
    while(p){   //如果此结点存在则计数器+1，并且指向下一结点，循环遍历
        i++;
        p = p->next;
    }
    return i;  //返回单链表的长度
}

//单链表的插入
State insertList(LinkList *L, int i, ElemType e){
    LinkList p;  //定义临时结点
    p = *L;   //临时结点指向头结点
    int j=1;   //位置计数器
    while(p && j  //因为单链表的插入是要插入到当前结点的后方，所以计数器初始为1
        p = p->next;  //如果还没有到指定位置的前方，则继续向下进行
        j++;  //位置计数器+1
    }
    if(!p){  //如果p不存在了说明链表中的结点数达不到插入结点的条件，无法插入，如果存在则继续向下进行
        return ERROR;
    }
    LinkList q;  //定义结点q
    q = (LinkList)malloc(sizeof(Node));  //为结点q分配内存空间
    q->data = e;  //为q结点的数据域赋指定值
    q->next = p->next;  //结点插入的经典方式，现将自身的next指向前结点的next结点
    p->next = q;  //将自身设为前结点的next结点
    return OK;
}

//单链表的删除
State deleteList(LinkList *L, int i, ElemType *e){
    LinkList p;  //定义临时结点
    p = *L;  //将临时结点指向头结点
    int j=1;  //计数器
    while(p && j  //判断p结点是否存在，并且计数器不能大于要删除结点的位置
        p=p->next;  //满足条件，继续向下走
        j++;  //计数器+1
    }
    if(!p){   //如果p不存在说明单链表的结点数不够所要删除的位置，无法删除，如果存在则继续向下进行
        return ERROR;
    }
    LinkList q;  //定义临时结点
    q = p->next;  //将要删除的结点赋给q
    p->next = q->next;  //将要删除结点的下一结点赋给要删除结点的上一结点，这样就避开了要删除的结点
    *e = q->data;  //将要删除的结点的数据域赋值给e用以备份返回
    free(q);  //释放q结点的内存区域，即删除了指定的结点
    return OK;
}

//清除单链表
State clearList(LinkList *L){
    LinkList p, q;  //定义两个临时结点
    p = (*L)->next;  //将p当前作为头结点的下一结点
    while(p){  //如果p存在（即还没有删除完成）
        q = p->next;  //则将q作为p结点的下一结点，然后将p删除后再将q赋给p这样的话就相当于p一直再向后删除
        free(p);
        p = q;
    }
    (*L)->next = NULL;  //全部删除后，将头结点的指针域置空，则表明单链表为空了
    return OK;
}

//获取单链表中某个位置的元素
State getElem(LinkList L, int i, ElemType *e){
    LinkList p;  //定义临时结点
    p = L->next;   //将p设置为首个结点
    int j = 1;  //计数器
    while(p && j   //在还不到对应的位置且p存在的情况下继续循环
        p = p->next;   //沿着链表向下进行
        j++;   //计数器+1
    }
    if(!p){   //如果跳出循环是因为p不存在了，则说明此位置没有结点，返回ERROR
        return ERROR;
    }
    *e = p->data;   //将对应位置上的元素的赋值给e用于返回
    return *e;   //返回指定位置上的数据域
}

//判断单链表中是否含有某个元素,如果有，返回它所在的位置信息
State localElem1(LinkList L, ElemType e){
    LinkList p;  //定义临时结点
    p = L->next;  //将临时结点设为首个结点
    int j=1;  //计数器，因为当前为首个结点，所以计数器的初始值为1
    while(p){   //如果p存在则循环向下进行判断
        if(((ElemType)p->data==e)){   //如果找到了对应的数值则将对应的计数器数值返回即为对应位置信息
            return j;
        }
        p = p->next;  //如果不是对应数值则继续向下寻找
        j++;  //计数器+1
    }
    return ERROR;  //一直p为空了跳出循环，则说明没有对应的数值
}

//创建单链表（前插法）
State headCreatList(LinkList *L){
    *L = (LinkList)malloc(sizeof(Node));  //创建单链表首先为头结点分配内存
    (*L)->next = NULL;   //空链表头结点的指针域为空
    for(int i=1;i<9;i++){   //将1-9按照前插法的方式插入单链表
        LinkList p = (LinkList)malloc(sizeof(Node));  //新建结点且为其分配内存
        p->data = i; //将新建结点的数据域设置为i的值
        p->next = (*L)->next;  //插队到头结点的下一结点，即头插法
        (*L)->next = p;  //将头结点的指针域设置为新新结点，头插完成
    }
    return OK;
}

//创建单链表（后插法）
State tailCreatList(LinkList *L){
    (*L) = (LinkList)malloc(sizeof(Node));  //创建单链表首先为头结点分配内存
    LinkList t;  //设置临时结点表示尾指针
    t = (*L);  //尾指针指向头结点，说明此时还为空链表
    for(int i=5;i<14;i++){   //将5-14数值按照尾插法插入单链表
        LinkList p = (LinkList)malloc(sizeof(Node));  //新建结点并分配内存
        p->data = i;  //将新建结点的数据域设置为当前i值
        t->next = p;  //尾指针指向新建结点
        t = p;  //将新建结点设置为尾结点
    }
    t->next = NULL;  //尾结点的指针域为空
    return OK;
}
//单链表的打印
State printLinkList(LinkList L){
    LinkList p;  //定义临时结点
    p = L->next;  //将p设置为首个结点
    int i=1;  //计数器
    while(p){  //判断当前结点是否存在
        printf("第%d个结点的元素值为%dn", i, p->data);  //如果存在则将数据域进行打印
        p = p->next;  //向下继续进行
        i++;  //计数器+1
    }
    return OK;
}

int main(){
    LinkList L1, L2;
    int e;
    printf("使用头插法创建单链表可得结果L1：n");
    headCreatList(&L1);
    printLinkList(L1);
    printf("使用尾插法创建单链表可得结果L2：n");
    tailCreatList(&L2);
    printLinkList(L2);
    printf("其中L1的长度为%d, L2的长度为%dn",listLength(L1), listLength(L2));
    printf("向单链表L1的第三个位置插入一个666元素可得：n");
    insertList(&L1, 3, 666);
    printLinkList(L1);
    printf("将单链表L2的第三个位置的元素删除可得：n");
    deleteList(&L2, 3, &e);
    printf("删除的元素为：%dn", e);
    printf("现在的单链表L2为：n");
    printLinkList(L2);
    printf("单链表是否存在元素666？存在则返回其位置，不存在则返回0:n");
    printf("单链表L1中666元素的位置为：%dn", localElem1(L1, 666));
    printf("单链表L2中666元素的位置为：%dn", localElem1(L2, 666));
    getElem(L1, 8, &e);
    printf("获得L1中的第8个元素为：%dn", e);
    printf("清空单链表可得L1: n");
    clearList(&L1);
    printLinkList(L1);
}