线性表

一、线性表的顺序表示（顺序表）

（一）、定义

静态分配(main)

定义

typedef struct{
    Element data[MaxSize];
    int length;
}SqlList;

初始化

SqlList l;

动态分配

定义

typedef struct{
    Element *data;
    int MaxSize,length;
}SeqList;

初始化

SeqList seqList;
l.data = (Element *)malloc(sizeof(sizeof(Element)));

（二）、操作

仅讨论比较重要的插入,删除和按值查找操作

插入

功能:在顺序表L的第i(1<=i<=L.length)个位置插入新元素,需要检验i的合法性

code

bool ListInsert(int i,SqlList &l,Element e){
    if(i<1||i>l.length+1){  //就位置而言,i应处于1-length之间
        return false;
    }
    if(l.length>=MaxSize){  //检查顺序表是否已满
        return false;
    }
    //将i位置后的元素后移
    for(int j=l.length+1;j>i;j--){
        l.data[j]=l.data[j-1];
    }
    l.data[i]=e;
    l.length++;  //插入和删除记得要改变长度
    return true;
}

注意
- i的合法范围在1和length+1之间
- 掺入和删除记得要改变.length

删除

功能:删除顺序表L中第i(1<=i<=l.length)个位置的元素

code

bool ListDelete(SqlList &l,int i,Element &e){
    if(i<1||i>l.length){  //就位置而言,i应处于1到length之间,这里已经排除了l为空的情况
        return false;
    }
    e=l.data[i-1];  //第i个位置对应的下标为i-1
    for(int j=i;j<l.length;j++){  //遍历的是第i个位置(i-1下标)后面所有的元素,对应的下标为i到length-1
        l.data[j-1]=l.data[j];
    }
    l.length--;
    return true;
}

注意:
- i<1||i>l.length包含了l为空的情况,因为此时i>l.length
- 第i个位置对应i-1的下标
- for循环遍历的是第i个位置(对应i-1下标)后的所有元素

查找

功能:在顺序表中查找第一个元素值等于e的元素,并返回次序

code

int locate(sqlList l,Element e){
    for(int i=0;i<l.length;i++){
        if(l.data[i]==e){
            return i+1;  //注意返回的是位置
        }
    }
    return 0;  //-1+1
}

注意
- 返回的是位置

二、线性表的顺序表示（顺序表）

（一）、定义

单链表

定义

typedef struct LNode{
    ElementType data;
    struct LNode *next;
}LNode,*LinkList;  //将struct LNode定义为Lnode,很巧妙

分类
- 不带头结点的链表
- 带头结点的链表(相关的操作依据带头结点的链表)
  
  优点:
  - 不需要对头结点特殊化处理
  - 不需要对空链表做特殊化处理

双链表

定义

typedef struct DNode{
   	ElementType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

（二）、操作

头插法建立单链表

功能:从一个空表开始,生成新结点,并将读取到的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头
特点:输入数据的次序与结点数据的次序相反

code

LinkList listHeadInsert(){
    int x;
    LinkList l=(LNode *)malloc(sizeof(LNode));
    l->next=NULL;
    scanf("%d",&x);
    while(x!=-1){
        LNode *node=(LNode *)malloc(sizeof(LNode));
        node->data=x;
        node->next=l->next;
        l->next=node;
        scanf("%d",&x);
    }
    return l;
}

注意:
- 上述函数缺乏普遍性

尾插法建立单链表

功能:基本功能同头插法,,用于建立链表
特点:输入数据的次序与结点数据的次序相同

code

LinkList listTailInsert(){
    int x;
    LinkList l,tail;
    l=(LNode *)malloc(sizeof(LNode));
    l->next=NULL;
    tail=l;
    scanf("%d",&x);
    while(x!=-1){
        LNode *node=(LNode *)malloc(sizeof(LNode));
        node->data=x;
        tail->next=node;
        tail=node;
        scanf("%d",&x);
    }
    tail->next=NULL;
    return l;
}

注意:尾部的NULL可以最后设置

按序号查找结点值

功能:在链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL

code

LNode *getElem(LinkList l,int i){
    LNode *temp=l->next;
    int num=1;  //temp的初始值为l的下一个结点
    if(i==0){  //特殊情况
        return l;
    }
    if(i<0){  //无效情况
        return NULL;
    }
    while(temp!=NULL&&num!=i){
        num++;
        temp=temp->next;
    }
    return temp;
}

注意
- 由于temp的初始值为头结点的下一个结点,num初值为1
- 如何编写各情况下的代码(其实也可以看做是集合的划分)
  - 特殊情况
  - 无效情况
  - 有效的普通情况

按值查找表结点

功能:依次比较表中各结点数据域的值,若某结点的数据域等于给定值e,则返回该节点的指针,否则返回NULL

code

LNode *locateElem(LinkList l,ElementType e){
    LNode *temp=l->next;
    while(temp!=NULL&&temp->data!=e){
        temp=temp->next;
    }
    return temp;
}

插入节点操作

功能:将值为x的新节点插入到单链表的第i个位置上,如果插入成功返回true,否则返回false

code

bool addElem(LinkList l,ElementType e,int i){
    LNode *pre=getElem(l,i-1);
    LNode *node;
    if(pre==NULL){  //无效情况
        return false;
    }else{  //有效情况
        node=(LNode *)malloc(sizeof(LNode));
        node->next=pre->next;
        pre->next=node;
        return true;
    }
}

删除结点操作

功能:将单链表的第i个结点删除

code

bool deleteELem(LinkList l,int i){
    LNode *pre=getELemt(i,i-1);
    if(pre==NULL){
        return false;
    }else{
        LNode *temp=pre->next;
        pre->next=temp->next;
        free(temp);  //释放内存
        return true;
    }
}

注意:释放内存空间

三、静态链表

（一）、定义

含义:借助数组来描述线性表的链式存储结构

定义

#define MaxSize 50
typedef struct{
    ElementType data;
    int next;
}SLinkList[MaxSize];

用途;可以使用在一些不支持指针的高级语言中