ZJU数据结构(二)线性表

1.什么是线性表

“线性表”：由同类型数据元素构成有序序列的线性结构

1. 表中元素个数称为线性表的长度
2. 线性表没有元素时，称为空表
3. 表起始位置称为表头，表结束为止称为表尾

2.线性表的抽象数据类型描述

4. 类型名称：线性表（List）
5. 数据对象集：线性表是n(≥0)个元素构成的有序序列(a₁，a₂，…，a_n)
6. 操作集：线性表L ∈ List，整数i表示位置，元素X∈ ElementTpye，线性表的基本操作有：
       1、 List MakeEmpty(): 初始化一个空线性表L；
       2、 ElementType FindKth(int K,List L): 根据位序K，返回相应元素；
       3、 int Find(ElementTpye X,List L) 在线性表L中查找X的第一次出现位置；
       4、 void Insert(ElementType X,int i,List L): 在位序i前插入一个新元素X；
       5、 void Delete(int i,List L): 删除指定位序i的元素；
       6、 int Length(List L): 返回线性表L的长度n。

3.线性表的顺序储存实现

利用数组的连续存储空间顺序存放线性表的个元素
注：顺序存储中i是序号的下标，从0开始

头文件命令及结构体格式：

#include<stdio.h>
#define MAXSIZE 100 //MAXSIZE定义为Data数组的大小
typedef struct LNode*List;
struct LNode{
    ElementType Data[MAXSIZE];//ElementType 可以为任意类型
    int Last; //Last定义线性表的最后一个元素
};
struct LNode L;
List PtrL;
//访问下标为i的元素：L.Data[i]或者Ptrl->Data[i]
//线性表的长度：L.Last+1或者PtrL->Last+1

主要操作的实现：

• 1.初始化（建立空的顺序表）

//初始化（建立空的顺序表）
List MakeEmpty()
{
    List L;
    L =(List)malloc(sizeof(struct LNode));
    L->Last=-1;
    return L;
}

• 2.按值查找

//按值查找
int Find(ElementType X,List L)//ElementType 可以为任意类型
{
    int i=0;
    while(i<=L->Last&&L->Data[i]!=X)
        i++;
    if(i>L->Last)
        return -1;//如果没找到返回-1
    else
        return i;//如果找到了返回i下标
}

• 3.插入操作实现

//插入操作实现
void Insert(ElementType X,int i,List L)//ElementType 可以为任意类型
{
    int j;
    if(L->Last==MAXSIZE-1)
    {
        printf("表满");//表假如空间已满，不能插入
        return;
    }
    if(i<1||i>L->Last+2)
    {
        printf("位置不合法");//位置越界
        return;
    }
    for(j=P->Last;j>=i-1;j--)
        L->Data[j+1]=L->Data[j]；//从后往前挪一个，给a[i]腾出位置
    L->Data[i]=X; //新元素插入
    L->Last++; //Last仍然指向最后元素
    return;
}

• 4.删除(删除表的第i(l<=i<=n)个位置上的元素)

//删除(删除表的第i(l<=i<=n)个位置上的元素)
void Delete(int i,List L)
{
    int j;
    if(i<1||i>L->Last+1)
    {
        printf("L->Data[%d]不存在元素",i);//位置越界
        return;
    }
    for (j=i,j<=L->Last;j++) //从前往后依次向前挪一个，将a[i]覆盖了
        L->Data[j-1]=L->Data[j];
    L->Last--;
    return;// Last仍然指向最后元素
}

• 5.按序查找

//按序查找
ElementType FindKth(int K,List L)
{
    if(K<0||L->Last<K)//位置越界
    {
        printf("L->Data[%d]不存在元素",K);
        return;
    }
    return L->Data[K];
}

• 6.求表长

//求表长
int Length(List L)
{
    return L->Last-1;
}

• 测试代码段

//test
int main(){
    int i=0;
    L=MakeEmpty();//
    Insert(22,0,L);
    printf("在线性表L-Data[0]插入22n");
    Insert(33,0,L);
    printf("在线性表L-Data[0]插入33n");
    Insert(44,0,L);
    printf("在线性表L-Data[0]插入44n");
    Insert(55,0,L);
    printf("在线性表L-Data[0]插入55n");
    printf("此时的线性表为：");
    for(i=0;i<Length(L);i++)
        printf("%d ",L->Data[i]);
    printf("n");
    printf("查找值为22的下标是：%dn",Find(22,L));
    printf("下标为2的线性表的值是：%dn",FindKth(2,L));
    Delete(2,L);
    printf("删除线性表中下标为2的元素n");
    Delete(2,L);
    printf("删除线性表中下标为2的元素n");
    printf("此时的线性表为：");
    for(i=0;i<Length(L);i++)
        printf("%d ",L->Data[i]);
    printf("n");
    return 0;
}

4.线性表的链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。

• 插入、删除不需要移动数据元素，只需要修改“链”。

头文件命令及结构体格式：

#include<stdio.h>
#include<malloc.h>
typedef struct ElementType;//ElementType可以定义为任意类型
typedef struct LNode*List;
struct LNode
{
    ElementType Data;
    List Next;
};
struct Lnode L;
List L;

主要操作的实现：

• 1.初始化链表

//初始化链表
List MakeEmpty()
{
    List L=(List)malloc(sizeof(struct LNode));
    L=NULL;
    return L;
}

• 2.以遍历链表的方法求链表长度

//以遍历链表的方法求链表长度
int Length(List L)
{
    List p=L;//p指向表的第一个节点
    int j=0;
    while(p) //当p不为空
    {
        p=p->next;
        j++;//p指向表的第j个节点
    }
    return j;
}

• 3.按序号查找

//按序号查找
List FindKth(int K,List L)
{
    List p=L;
    int i=1; //从1开始
    while(p!=NULL&&i<K)
    {
        p=p->Next;
        i++
    }
    if(i==K)
        return p;//找到第K个，返回指针
    else return NULL;//否则返回空值
}

• 4.按值查找

//按值查找
List Find(ElementType X,List L)
{
    List p=L;
    while(p!=NULL&&p->Data!=X)
        p=p->Next;
    return p;
}

• 5.插入
      1.先构造一个新的结点，用s指向；
      2.在找到链表的第i-1个结点，用p指向；
      3.然后修改指针，插入节点（p之后插入的新结点是s）
           s->Next =p->Next, p->Next=s

//插入
List Insert(ElementType X,int i,List L)
{
    List p,s;
    if(i==1)//新结点插入在表头
    {
        s=(List)malloc(sizeof(struct LNode));
        s->Data=X;
        s->Next=L;
        return s;
    }
    p=FindKth(i-1, L);//查找第i-1个结点
    if(p==NULL)//第i-1个结点不存在
    {
        printf("结点错误");
        return NULL;
    }
    else
    {
        s=(List)malloc(sizeof(struct LNode));
        s->Data=X;
        s->Next=p->Next;    //将s的下一个结点指向p的下一个结点
        p->Next=s;          //将p的下一结点改为s
        return L;
    }
}

• 6.删除
      1.先找到链表的第i-1个结点，用p指向；
      2.再用指针s指向要被删除的结点（p的下一个结点);s=p->Next
      3.然后修改指针，删除s所指结点；p->Next=s->Next
      4.最后释放s所指结点 free(s)

//删除
List Delete(int i,List L)
{
    List p,s;
    if(i==1) //若删除第一个结点
    {
        s=L;//s指向第一个结点
        if(L!=NULL)//从链表中删除
            L=L->Next;
        else
            return NULL;
        free(s);
        return L;
    }
    p=FindKth(i-1,L);//查找第i-1个结点
    if(p==NULL||p->Next==NULL)
    {
        printf("结点不存在")
        return NULL;
    }
    else
    {
        s=p->Next//s指向第i个结点
        p->Next=s->Next;
        free(s);
        return L;
    }
}

• 7.输出链表元素

//输出链表元素
void Print(List L)
{
    List t;
    int flag=1;
    printf("当前链表为：");
    for(t=L;t;t->Next)
    {
        printf("%d",t->Data);
        flag=0;
    }
    if(flag)
        printf("NULL");
    printf("n");
}


//8.测试
int main()
{
    L=MakeEmpty();
    Print(L);
    L=Insert(22, 1, L);
    L=Insert(33, 1, L);
    L=Insert(44, 1, L);
    L=Insert(55, 1, L);
    Print(L);
    printf("当前情况链表长度为：%dn"，length(L));
    printf("此时链表中第三个结点的值为：%dn",FindKth(3,L)->Data);
    printf("查找22是否在该链表中:");
    if(Find(22,L))
        printf("Yes n");
    else
        printf("No  n");
    printf("查找33时都在该链表中：")；
    if(Find(33,L))
        printf("Yes n");
    else
        printf("No  n");
    L=Delete(1,L);
    L=Delete(4,L);
    Print("删除后n");
    Print(L);
    return 0;
}

课后编程练习链接

        1. 两个有序链表序列的合并 这是一道C语言函数填空题，训练最基本的链表操作。一定要做；

        2. 一元多项式的乘法与加法运算 在“小白专场”里，我们会详细讨论C语言实现的方法。本题一定要做；

        3. Reversing Linked List 根据某大公司笔试题改编的2014年春季PAT真题，不难，可以尝试；

        4. Pop Sequence Pop Sequence 是2013年PAT春季考试真题，考察队堆栈的基本概念的掌握，应可以一试。

最后

以上就是落寞马里奥为你收集整理的ZJU数据结构(二)线性表ZJU数据结构(二)线性表的全部内容，希望文章能够帮你解决ZJU数据结构(二)线性表ZJU数据结构(二)线性表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。