顺序表和顺序链表

目录

一：什么是线性表

1：线性表

1.1：什么是顺序表

二：顺序表的一般 *** 作

2.2 一般的线性 *** 作有以下几种

2.3 实际代码

2.3.1 线性表L的初始化

2.3.2 销毁线性表

2.3.3 清空线性表

2.3.4 顺序表的取值（根据i位置获取相应位置数据元素的内容）

2.3.4 查找某一个元素

2.3.5 :顺序表的插入

三：链表和基础 *** 作

3.1 引：一个链表的实例：

3.2 链表的链式存储结构：

3.3 链表的 *** 作

3.3.1 单链表的存储结构

3.3.2 单链表的基本 *** 作

3.3.4 判断链表是否为空

3.3.5 单链表的销毁：销毁后链表不存在

3.3.6 清空单链表

3.3.7 求单链表的表长

3.3.8 取值 一 取单链表中第i个元素的内容

3.3.9 单链表的查找 按值查找 ：获得该数据的地址或者第几个数据元素

3.3.10  插入 : 在第i个结点前插入值为e的新结点

3.3.11 单链表中的删除 *** 作 -删除第i个结点

 3.3.12  查找插入删除算法分析

3.3.13 单链表的建立 头插法（前插法）

3.3.14 单链表的建立 尾插法（后插法）

 

---

一：什么是线性表 1：线性表

• 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串

• 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
   

1.1：什么是顺序表

• 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组
  上完成数据的增删查改。

• 顺序表：可动态增长的数组，要求数据是连续存储的

1.1.1 顺序表的定义(静态定义和动态定义)

静态定义

#define MAXSIZE 100

typedef int ElemType;

typedef struct{

        ElemType elem[MAXSIZE]; //定长数组

        int length; //有效数据个数

}

SqList;

动态定义

#define List_INIT_SIZE 100

typedef int ElemType;

typedef struct{

        ElemType *elem;//只想动态开辟的数组

        int length; //有效数据个数

        int listsize;//容量大小

}

SqList;

二：顺序表的一般 *** 作

2.1一般的顺序表

 图在心中 撸码自然神

2.2 一般的线性 *** 作有以下几种

补：顺序表是线性表中的一种void

难度上升以后的 *** 作有 顺序表的合并

2.3 实际代码 2.3.1 线性表L的初始化

Status InitList_Sq(SqList &L){//构造一个空的顺序表

        //L.elem =new Elemtype[MAXSIZE]; C++

        L.elem = (ElemType*)malloc(MAXSIZE*sizeof(ElemType));        //分配空间

        if(!L.elem) exit(OVERFLOW);                                                       //存储分配失败

        L.length=0；                                                                                //空表长度为0

       // L.listsize =0;                                                                //动态分配，初始化存储容量

        return OK;

}

2.3.2 销毁线性表

void DestroList(SqList &L){

        if(L.elem) delete L.elem; //释放存储空间

        L.length=0;

        L.listsize=0;

}

2.3.3 清空线性表

void ClearList(SqList &L){

        L.length =0; //将线性表的的长度设为0

}

补：求线性表长度

int GetLength(SqList L){

        return L.length;

}

补：判断线性表是否为空

int IsEmpty(Sqlist L){

        if(L.length==0)return 1;

        else return 0;

}

2.3.4 顺序表的取值（根据i位置获取相应位置数据元素的内容）

int GetElem(SqList L,int i,ElemType &e){

        if(i<1||i>L.length) return ERROR; //判断i是否合理

        e = L.elem[i-1];//下标=位置-1 ||第i-1存储着第i个数据

        return OK;

}

2.3.4 查找某一个元素

法一：

int LocateElem(SqList L,Elemtype e){

        for(i=0;i

                if(L.elem[i]==e) return i+1;

        }

        return 0;

}

法二：

int LocateElem(SqList L,Elemtype e){

        i=0；

        while(i

        if(i

        else return 0;

}

ASL:(平均查找长度 Average Search Length)： (n+1)/2

2.3.5 :顺序表的插入

   1：插入 会移动后面的元素

   2：插入的异常情况： i<1或者i>L.length 在数组之外

                                       存储空间已满

 Status ListInsert_Sq(SqList &L,int i,ElemType e){

        if(i<1||L.length+1) return ERROR; //i不合法

        if(L.length==MAXSIZE) return ERROR; //当前存储空间已满

        for(j=L.length-1;j>=i-1;j--){

                L.elem[j+1]=L.elem[j]; //插入及插入后的元素都往后移

        }

        L.elem[i-1]=e; //L.elem[j] 也行 将元素e放入第i个位置 下标为i-1

        L.length++;

        return OK;

}

 时间效率：1：n+1中可能 最多n+1 最少0 所以 n/2

2.3.6 顺序表的删除

Status ListDlete_Sq(SqList &L,int i){

        if(i<1||i>length+1) return ERROR;

        for(j=i;j

               L.elem[j-1]=L.elem[j];        

        }

        L.length--;

        return OK;

}

时间效率： 最多n-1 最少0 所以 n-1/2

三：链表和基础 *** 作 3.1 引：一个链表的实例：

 

3.2 链表的链式存储结构：

1结点：

 2 链表

 3：单链表 双链表 循环链表

3：头指针 头结点 首元结点

 

 

3.3 链表的 *** 作

 

3.3.1 单链表的存储结构

typedef struct Lnode{ //声明节点的类型 和指向节点的指针类型

        ElemType data;   //结点的数据域

        struct Lnode *next; //结点的指针域

}Lnode,*LinkList; //LinkList为指向结构体Lnode 的指针类型

 

3.3.2 单链表的基本 *** 作

 实例：

 

3.3.3 单链表的基本 *** 作的实现 -单链表的初始化（带头节点的单链表）

 

Status InitList_L(LinkList &L){

       L =  (LinkList)malloc(sizeof(LNode));//L =new LNode;

       L->next =NULL;

       return OK;

}

3.3.4 判断链表是否为空

 

int ListEmpty(LinkList L){

        if(L->next) //非空

                return 0;

        else

                return 1;

}

3.3.5 单链表的销毁：销毁后链表不存在

Status DestroyList_L(LinkList &L){     

        while(L){

                p=L;

                L=L->next;

                delete p;

        }

}

3.3.6 清空单链表

链表仍存在，但链表中无元素，成为空链表(头指针和头结点仍然在)

 

Status ClearList(LinkList &L){     

        Lnode *p ,*q;//LinkList p,q;

        p=L->next;

        while(p){ //删到表尾  p作为删表的指针 q作为定位 防止丢失位置

                q=p->next;

                delete(p);

                p=q;

        }

        L->next =NULL;

        return OK;

}

3.3.7 求单链表的表长

int Listlength_L(LinkList L){ //返回L中数据元素的个数

        LinkList p;int i=0;

        p=L->next; //p指向第一个结点

        while(p){   //遍历单链表 统计结点数

                i++;

                p=p->next;       

        }

}

3.3.8 取值 一 取单链表中第i个元素的内容

思考：顺序表里如何找到第 i 个元素?  L-> elem[i-1]

=》从链表的头指针出发，顺着链域next逐个结点往下搜索，.直至搜索到第i个
结点为止。因此，链表不是随机存取结构

Status GetElem_L(LinkList_L, int i,ElemType &e){ //获取线性表中的某个数据元素的内容 通过变量e返回

        LinkList p;int j=1;//记录从第一个开始

        p=L->next;         //初始化 第一个

        while(p&&j

                p=p->next;

                j++;

        }

        if(!p||j>i) return ERROR;         //第i个元素出错  不存在

        e = p->data;                         //取第i个值

        return OK;

}

3.3.9 单链表的查找 按值查找 ：获得该数据的地址或者第几个数据元素

心中有图 撸码自然神

Lnode *LocateElem_L(LinkList L,Elemtype e){

        //查找e的数据元素的指针

        //找到 返回L中值为e的数据元素的地址， 查找失败返回NULL

        p = L->next;

        while(p&&p->data!=e){

                p=p->next;

        }

        return p;

}

Lnode LocateElem_L(LinkList L,Elemtype e){

        //查找e的数据元素 的位置序号

        //找到 返回L中值为e的数据元素的位置序号， 查找失败返回NULL

        p = L->next;

        j=1;

        while(p&&p->data!=e){

                p=p->next;

                j++;

        }

        if(p) return j;

        else return 0;

}

3.3.10  插入 : 在第i个结点前插入值为e的新结点

 

S->next  = p->next          p->next = s

//在L中 第i个元素之前插入数据元素e

Status ListInsert_L(LinkList &L,int i,ElemType e){

         p = L;j=0; //p=L->next;j=1;

        while(p&&j

                p=p->next;

                j++;

        } 

        if(!p||j>i-1) return ERROR; // i>节点位置或者<1  插入位置非法

        s=(LinkList)malloc(sizeof(Lnode));        s->data =e;//

        s->next =p->next; //插入结点

        p->next =s;

        return OK;

}

3.3.11 单链表中的删除 *** 作 -删除第i个结点

 p->next = p->next->next;

//将线性表L中的第i个数据元素删除

Status ListDelete_L(LinkList &L,int i,ElemType &e){

        p=L;j=0;

        while(p->next&&j

                p=p->next;

                j++;       

        }

        if(!(p->next)||j>i-1) return ERROR; //保证p的下一个就是删除结点存在 并且 位置合理

        // p->next = p->next->next; 但是因为e要记录被删除的值 所以需要辅助指针q
        q = p->next;

        p->next = q->next;//删除 *** 作

        e = q->data;//保存数据

        delete q; //释放空间

        return OK;

}

 

 3.3.12  查找插入删除算法分析

 

3.3.13 单链表的建立 头插法（前插法）

void CreateList_H(LinkList &L,int n){

        L = (LInkList)malloc(sizeof(Lnode));

        L->next =NULL;//先建立一个带头结点的 单链表

        for(i=0;i

                p = (LinkList)malloc(sizeof(Lnode)); //生成新结点p

                scanf("%d",&p->data);//输入元素值

                p->next = L->next;//插入到表头

                L->next = p;

        }

}

算法的复杂度 O(n)

3.3.14 单链表的建立 尾插法（后插法）

算法思想：

 

//建立带头节点的单链表L 用尾插法

void CreateList_R(LinkList &L,int n){

        L = (LInkList)malloc(sizeof(Lnode));

        L->next =NULL;

        r=L;//尾指针

        for(i=0;i

                p = (LinkList)malloc(sizeof(Lnode)); //生成新结点p

                scanf("%d",&p->data);//输入元素值

                p->next = NULL;

                r->next = p;//插入到队尾

                r=p; //指向新的尾节点

        }

}