线性表

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

（一）、定义

静态分配(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



注意:

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



注意

返回的是位置



二、线性表的顺序表示（顺序表）
（一）、定义
单链表


定义
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];



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


						
							

						
							
							
			DataStructure