【数据结构】线性表的深度学习

数据结构再度学习(详细注释版）：线性表<顺序表，单链表>

顺序表

//
//  main.c
//  SQList
//
//  Created by Eason on 2020/7/28.
//  Copyright © 2020 Eason. All rights reserved.
//

#include<stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define maxsize 100
typedef int Status;
typedef int ElemType;
//线性表的存储结构
typedef struct{
    int 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 insertList(SqList *L, int i, ElemType e){
    if(L->length==maxsize){  //判断线性表是否已满
        printf("目前线性表的长度已满，不可再插入元素");
        return ERROR;
    }
    if(i<1||i>L->length+1){   //判断插入位置是否合法
        printf("您输入的插入位置有误");
        return ERROR;
    }
    if(i!=L->length+1){   //判断是否是插在线性表的最后，如果不是的话要进行线性表的元素后移操作
        for(int i=i;i<L->length;i++){
            L->data[i]=L->data[i-1];
        }
    }
    L->data[i-1]=e;   //如果是插在线性表的最后，则直接写入就可。如果不是最后则已经后移完成，将插入元素写入对应位置即可
    return OK;
}
//打印线性表
Status printList(SqList *L){
    for(int i=0;i<L->length;i++){   //for循环遍历的方式访问线性表的元素并进行打印
        printf("\n第%d个元素为%d", i+1, L->data[i]);
    }
    return OK;
}
//删除线性表
Status deleteList(SqList *L, int i, int *e){
    if(L->length==0){   //判断目前的顺序表是否为空，若为空则不可进行删除操作
        printf("线性表的长度为0，不可进行删除操作");
        return ERROR;
    }
    if(i==0||i>L->length){
        printf("您输入的删除位置有误，不可进行删除操作");
        return ERROR;
    }
    e = L->data[i-1];  //将要删除位置的元素存储起来
    if(i!=L->length){  //如果要删除的位置不在最后，那么要进行顺序表的前移操作
        for(int n=i;n<L->length;n++){
            L->data[n-1] = L->data[n];
        }
        L->length--;
        return e;
    }
    L->data[i-1] = 0;  //如果要删除的位置在最后，那么直接将最后一个元素置0
    return e;
}
//合并线性表（集合相并）
Status Union(SqList *LA, SqList *LB){
    int lengtha = LA->length;
    int lengthb = LB->length;
    int isEqual = 0;   //判断是否存在相同元素的标志
    for(int i=0;i<lengthb;i++){
        if(searchList(LA, LB->data[i])){   //判断LA中是否含有与制定元素相等的元素
            isEqual = 1;   //若含有，则判断置1（TRUE）
        }
        if(!isEqual){    //若判断为！1（0）即不想等的时候执行插入操作，并将LA的长度+1
            insertList(LA, ++lengtha, LB->data[i]);
            LA->length++;
        }
        isEqual = 0;   //判断完一个后再次循环判断下一个，对应的判断标志初始化为0
    }
    return OK;
}
//线性表查找元素
Status searchList(SqList *LA, int e){
    int lengtha = LA->length;  //线性表的长度
    for(int i=0;i<lengtha;i++){   //遍历线性表
        if(LA->data[i]==e){   //比较当前线性表元素是否相等
            return TRUE;
        }
    }
    return FALSE;
}
//删除线性表中指定的元素
Status deleteValue(SqList *L, int e){
    int i=0;  //循环遍历的计数位
    while(L->data[i]!=e&&i<L->length){  //循环要么找到相同元素要么全部遍历
        i++;
    }
    if(i<L->length){   //如果不是全部遍历，则表明是找到了相同的元素
        for(int n=i;n<L->length;n++){  //按照线性表删除元素的做法进行遍历向前移动
            L->data[n]=L->data[n+1];
        }
        L->length--;  //进行删除操作后将线性表的长度-1
        return OK;
    }
    printf("线性表中没有对应的元素，无法删除");  //如果是全部遍历，则表明线性表中没有指定的元素
    return ERROR;
}
//相交线性表（两集合的交集）
Status mergeList(SqList *LA, SqList *LB){
    int lengthb = LB->length;  //遍历循环使用B线性表的长度
    int isEqual = 0;  //判断是否相等的标志位
    for(int i=0;i<lengthb;i++){   //循环便利线性表B中的元素线性表A进行比较
        if(searchList(LA, LB->data[i])){   //判断当前A中是否有这个B中的元素
            isEqual = 1;   //如果有的话，标识位置1（true）
        }
        if(isEqual){   //如果相等则需要进行删除操作
            deleteValue(LA,LB->data[i]);   //将匹配到的与B中的元素相等的元素进行删除
        }
        isEqual = 0;  //新的一轮将标识位初始化置0
    }
    return OK;
}
int main(int argc, const char * argv[]) {
    SqList sqlistA;
    SqList sqlistB;
    int e;
    printf("请输入线性表A的内容：\n");
    CreatList(&sqlistA);
    printList(&sqlistA);
    printf("\n请输入线性表B的内容：\n");
    CreatList(&sqlistB);
    printList(&sqlistB);
    printf("\n目前线性表A的长度为%d", getLength(&sqlistA));
    printf("\n目前线性表B的长度为%d", getLength(&sqlistB));
    Union(&sqlistA, &sqlistB);
    printf("\n合并后的线性表A的长度为%d, 线性表A的内容为：", getLength(&sqlistA));
    printList(&sqlistA);
    mergeList(&sqlistA, &sqlistB);
    printf("\n再与线性表B进行相交的线性表A的变成了：");
    printList(&sqlistA);
    insertList(&sqlistA, 2, 9);
    printf("\n向线性表A中的第二个位置插入元素9操作后得：");
    printList(&sqlistA);
    deleteList(&sqlistA, 2, e);
    printf("\n将线性表A的中第二个位置元素删除操作后得：");
    printList(&sqlistA);
    return 0;
}

单链表

//
//  main.c
//  LinkedList
//
//  Created by Eason on 2020/7/29.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <stdio.h>
#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<i){  //因为单链表的插入是要插入到当前结点的后方，所以计数器初始为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<i){  //判断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<i){   //在还不到对应的位置且p存在的情况下继续循环
        p = p->next;   //沿着链表向下进行
        j++;   //计数器+1
    }
    if(!p){   //如果跳出循环是因为p不存在了，则说明此位置没有结点，返回ERROR
        return ERROR;
    }
    *e = p->data;   //将对应位置上的元素的赋值给e用于返回
    return *e;   //返回指定位置上的数据域
}

//判断单链表中是否含有某个元素,如果有，返回它所在的位置信息
State localElem(LinkList L, ElemType *e){
    LinkList p;  //定义临时结点
    p = L->next;  //将临时结点设为首个结点
    int j=1;  //计数器，因为当前为首个结点，所以计数器的初始值为1
    while(p){   //如果p存在则循环向下进行判断
        if(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个结点的元素值为%d\n", 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的长度为%d\n",listLength(L1), listLength(L2));
    printf("向单链表L1的第三个位置插入一个666元素可得：\n");
    insertList(&L1, 3, 666);
    printLinkList(L1);
    printf("将单链表L2的第三个位置的元素删除可得：\n");
    deleteList(&L2, 3, &e);
    printf("删除的元素为：%d\n", e);
    printf("现在的单链表L2为：\n");
    printLinkList(L2);
    printf("单链表是否存在元素666？存在则返回其位置，不存在则返回0:\n");
    printf("单链表L1中666元素的位置为：%d\n", localElem(L1, 666));
    printf("单链表L2中666元素的位置为：%d\n", localElem(L2, 666));
    getElem(L1, 8, &e);
    printf("获得L1中的第8个元素为：%d\n", e);
    printf("清空单链表可得L1: \n");
    clearList(&L1);
    printLinkList(L1);
}