精华内容
下载资源
问答
  • 2 基于链式存储结构的线性表实现2.1 问题描述依据最小完备性和常用性相结合的原则,采用单链表作为线性表的物理结构,函数形式定义12种表操作基本运算。按要求构造一个具有菜单的功能演示系统,演示系统,实现...

    e2d6b6c813b2a7383ef0a7f65ec8deea.png

    2 基于链式存储结构的线性表实现

    2.1 问题描述

    依据最小完备性和常用性相结合的原则,采用单链表作为线性表的物理结构,以函数形式定义12种表操作基本运算。按要求构造一个具有菜单的功能演示系统,演示系统,实现线性表的文件形式保存,且能实现多表管理。

    2.1.1 线性链表的基本概念

    线性表是一个具有n(n>=0)个元素的线性关系有限序列。元素的个数为线性表的长度,当n=0时,线性表为空表,用一对空括号表示。

    线性表的逻辑结构为线性结构,即元素之间一对一连接的结构关系。线性表的链式表示,即其物理结构为链式结构采取链表,即不要求逻辑上相邻的元素在物理层面也相邻,顾名思义就是利用链表存储数据,它用附加指针表示节点间的逻辑关系。(如图2-1,2-2,2-3所示)。

    532cf6fad9d4e56ba0419d6319ee40d9.png
    图2-1线性单链表物理结构

    a5782d61aa55f3b26fa150491d654a10.png
    图2-2循环单链表物理结构

    67e77d58dfb8e5bb6a0f7a37928a9300.png
    图2-3线性双链表物理结构

    为了表示某个元素ai与其后继节点之间的逻辑关系,所以我们在存储ai时,还需存储一个指示其后继元素的信息。这两部分组成数据元素ai的存储映象,称为节点(node)。

    //本文原创版权所有,商业引用请注明出处
    // Created by 南隹 on 2019/11/13
    // Copyright © 2019 南隹. All rights reserved.
    //

    2.1.2 演示系统与文件

    演示系统可选择实现线性表的文件形式保存。其中,①需要设计文件数据记录格式,以高效保存线性表数据逻辑结构(D,{R})的完整信息;②需要设计线性表文件保存和加载操作合理模式。

    演示系统可选择实现多个线性表管理。演示系统界面,及文件路径配置,文件路径配置为自定义,文件保存形式为单线性表按表名存储,表示数据文件的存储。

    2.2 系统设计

    2.2.1 数据物理结构

    结构实现定义(如图2-6所示):

    typedef struct Lnode{

    Elemtype data;

    struct Lnode *next;

    }Lnode,*LinkList;//元素定义

    typedef struct{

    Lnode head[10];

    int length;

    }SqList;//实现多表管理

    d5e80ae501bc686f574b0a26bc7e3915.png
    图2-6多表管理结构示意

    从表定义了解此次线性表为动态链表,即用单链表实现,链表是实际工程操作中非常有用的数据结构实现方法,优势在于只要条件允许对表中元素数量没有限制。

    2.2.2 演示系统

    演示系统的欢迎菜单为新建表、打开文件、退出程序三个主功能,预定义操作文件数目为10(可以自行修改)。新建表功能按顺序建立两个链式结构的线性表头,用户自由选择需要操作的表,然后进入次级菜单进行表操作。打开已有文件功能使用文件名即表名定位文件,利用空表读取特定存在线性表里的元素,用“r+”打开,故不改变文件本身的数据。退出程序操作实现文件和表操作的保存保证程序安全退出。(基本结构示意见图2-7)

    次级菜单定义单链表的14个基本操作,我们在文件操作结束退出次级菜单后实现文件的写操作。为方便起见,在初始化模块添加两个功能选择,一个是用户自定义表长并根据表长生成简单链表的功能,另一个是用户自定义表长并根据表长依次输入要存储的数据的功能。

    4bd779dd81f65958eabdfa6547e6e609.png
    图2-7演示系统结构

    2.2.3 效率分析

    效率分析即从程序占用内存,函数空间复杂度和时间复杂度入手给出分析。具有同数量级复杂度的功能,在实现方法上一般类似,比如Loaddata,Listprint它们都是基于ListTraverse来设计的,所以效率都是O(n);而LocatElem,PriorElem,NextElem是基于LocatElem,平均效率为O(n);由于在表节点中包含了Listempty,Listlen所需信息,所以其效率为O(1);ListInsert,ListDelete都要对表进行移位运算,所以平均效率为O(n).

    2.3 系统实现

    2.3.1 运行环境、编译环境描述

    本实验程序语言编写环境为Visual Stdio Code,编译环境为Xcode Version 9.4。

    2.4 程序源码

    //
    
    展开全文
  • 2.4 线性表的链式存储结构及运算实现;2.4 线性表的链式存储结构及运算实现;2.4.1 单链表;元素(数据元素映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素映象;2.4.1 单链表; ; ; ; ; ; ; ...
  • 2 基于链式存储结构的线性表实现2.1 问题描述依据最小完备性和常用性相结合的原则,采用单链表作为线性表的物理结构,函数形式定义12种表操作基本运算。按要求构造一个具有菜单的功能演示系统,演示系统,实现...

    10f153f6dafb56aceb601847656beef6.png

    2 基于链式存储结构的线性表实现

    2.1 问题描述

    依据最小完备性和常用性相结合的原则,采用单链表作为线性表的物理结构,以函数形式定义12种表操作基本运算。按要求构造一个具有菜单的功能演示系统,演示系统,实现线性表的文件形式保存,且能实现多表管理。

    2.1.1 线性链表的基本概念

    线性表是一个具有n(n>=0)个元素的线性关系有限序列。元素的个数为线性表的长度,当n=0时,线性表为空表,用一对空括号表示。

    线性表的逻辑结构为线性结构,即元素之间一对一连接的结构关系。线性表的链式表示,即其物理结构为链式结构采取链表,即不要求逻辑上相邻的元素在物理层面也相邻,顾名思义就是利用链表存储数据,它用附加指针表示节点间的逻辑关系。(如图2-1,2-2,2-3所示)。

    99f60a23a726d86a1bd9e83f935bfc5b.png
    图2-1线性单链表物理结构

    2eee18be9ab6bdee32a94832fa91e2c1.png
    图2-2循环单链表物理结构

    914b6e04f575a140f8d9892cebfcf71b.png
    图2-3线性双链表物理结构

    为了表示某个元素ai与其后继节点之间的逻辑关系,所以我们在存储ai时,还需存储一个指示其后继元素的信息。这两部分组成数据元素ai的存储映象,称为节点(node)。

    //本文原创版权所有,商业引用请注明出处
    // Created by 南隹 on 2019/11/13
    // Copyright © 2019 南隹. All rights reserved.
    //

    2.1.2 演示系统与文件

    演示系统可选择实现线性表的文件形式保存。其中,①需要设计文件数据记录格式,以高效保存线性表数据逻辑结构(D,{R})的完整信息;②需要设计线性表文件保存和加载操作合理模式。

    演示系统可选择实现多个线性表管理。演示系统界面,及文件路径配置,文件路径配置为自定义,文件保存形式为单线性表按表名存储,表示数据文件的存储。

    2.2 系统设计

    2.2.1 数据物理结构

    结构实现定义(如图2-6所示):

    typedef struct Lnode{

    Elemtype data;

    struct Lnode *next;

    }Lnode,*LinkList;//元素定义

    typedef struct{

    Lnode head[10];

    int length;

    }SqList;//实现多表管理

    ffd428a7a728cd42e8881b510e4f4142.png
    图2-6多表管理结构示意

    从表定义了解此次线性表为动态链表,即用单链表实现,链表是实际工程操作中非常有用的数据结构实现方法,优势在于只要条件允许对表中元素数量没有限制。

    2.2.2 演示系统

    演示系统的欢迎菜单为新建表、打开文件、退出程序三个主功能,预定义操作文件数目为10(可以自行修改)。新建表功能按顺序建立两个链式结构的线性表头,用户自由选择需要操作的表,然后进入次级菜单进行表操作。打开已有文件功能使用文件名即表名定位文件,利用空表读取特定存在线性表里的元素,用“r+”打开,故不改变文件本身的数据。退出程序操作实现文件和表操作的保存保证程序安全退出。(基本结构示意见图2-7)

    次级菜单定义单链表的14个基本操作,我们在文件操作结束退出次级菜单后实现文件的写操作。为方便起见,在初始化模块添加两个功能选择,一个是用户自定义表长并根据表长生成简单链表的功能,另一个是用户自定义表长并根据表长依次输入要存储的数据的功能。

    7d4fa79ecee9c6936d7830fb9424e4a4.png
    图2-7演示系统结构

    2.2.3 效率分析

    效率分析即从程序占用内存,函数空间复杂度和时间复杂度入手给出分析。具有同数量级复杂度的功能,在实现方法上一般类似,比如Loaddata,Listprint它们都是基于ListTraverse来设计的,所以效率都是O(n);而LocatElem,PriorElem,NextElem是基于LocatElem,平均效率为O(n);由于在表节点中包含了Listempty,Listlen所需信息,所以其效率为O(1);ListInsert,ListDelete都要对表进行移位运算,所以平均效率为O(n).

    2.3 系统实现

    2.3.1 运行环境、编译环境描述

    本实验程序语言编写环境为Visual Stdio Code,编译环境为Xcode Version 9.4。

    2.4 程序源码

    //
    //  main.c
    //  数据结构实验二
    //  实验目的:加深线性表物理及逻辑结构的理解,使用带表头的单链表实现,文件管理及演示系统操作
    //  Created by 南隹 on 2019/11/2.
    //  Copyright © 2019 南隹. All rights reserved.
    //
    #include "C1.h"
    #include "fun.h"
    #include "mue.h"
    int main(void)
    {
        menu_1();
        return 0;
    }
    //
    //  C1.h
    //  数据结构实验二
    //
    //  Created by 南隹 on 2019/11/4.
    //  Copyright © 2019 南隹. All rights reserved.
    //
    #ifndef C1_h
    #define C1_h
    #include <stdio.h>
    #include <stddef.h>//malloc等动态分配函数
    #include <stdlib.h>//系统清屏函数
    #include <stdio.h>//标准输入输出函数
    #include <math.h>
    #include <limits.h>
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define LIST_INIT_SIZE 10
    #define MaxSize 10
    
    FILE *fp;
    typedef int Status;//status是函数类型,其值为函数结果状态代码
    typedef int Boolean;
    typedef int Elemtype;//ElemType是用户自定义类型,为了便于根据不同使用情况修改代码
    typedef struct Lnode{
        Elemtype data;
        struct Lnode *next;
    }Lnode,*LinkList;//元素定义
    
    typedef struct{
        Lnode head[10];
        int length;
    }SqList;//实现多表管理
    #endif /* C1_h */
    //
    //  fun.h
    //  数据结构实验二
    //
    //  Created by 南隹 on 2019/11/5.
    //  Copyright © 2019 南隹. All rights reserved.
    //
    #ifndef fun_h
    #define fun_h
    #include "C1.h"
    Status filere(Lnode *L,FILE *fp);
    Status Savedata(FILE *fp,Lnode *L);
    Status Loaddata(FILE *fp,Lnode *L);
    Status EXit(SqList L1,FILE *fp);
    void Initlist(Lnode *L);
    void Destorylist(Lnode *L);
    void  Cleralist(Lnode *L);
    Status Listempty(Lnode *L);
    Status Listlength(Lnode *L);
    Lnode * Locatedelem(Lnode *L,Elemtype x);
    Lnode * Getelem(Lnode *L,int i);
    Lnode * Priorelem(Lnode *L,Elemtype x);
    Lnode * Nextelem(Lnode *L,Elemtype x);
    Status Listinsert(Lnode *L,int i,Elemtype x);
    Status Listdelete(Lnode *L,int i);
    void Printlist(Lnode *L);
    //FILE 文件管理函数
    FILE *fp;
    //fileread 文件打开
    Status filere(Lnode *L,FILE *fp){
        if(fp==NULL){
            printf("数据文件打开失败n");
            return 0;}
        printf("当前正在读取用户指定表名的数据。n");
        if(Loaddata(fp,L)==ERROR){
            printf("数据提取失败!n");
            return ERROR;
        }
        fclose(fp);
        return OK;
    }
    //filewrite
    Status Loaddata(FILE *fp,Lnode *L){
        Lnode *p;
        p=L;
        L->data=0;
        char ch;
        ch=fgetc(fp);
        if('#'==ch){
            printf("文件缺失!n");
            return 0;
        }
        fscanf(fp, "%d",&(p->data));
        while(ch=='@'){
            p->next=(Lnode *)malloc(sizeof(Lnode));
            p=p->next;
            if(!p){
                printf("OVERFLOW!n");
                return 0;
            }
            fscanf(fp, "%d",&(p->data));
            L->data++;
            ch=fgetc(fp);
        }
        printf("文件已读取完毕n");
        return OK;
    }
    //依次向文件中覆盖地写入
    Status Savedata(FILE *fp,Lnode *L)
    {
        Lnode *p;
        p=L;
        if(fp==NULL){
            printf("文件缺失!n");
            return 0;
        }
        while(p){
            fputc('@',fp);
            fprintf(fp, "%d",p->data);
            p=p->next;
        }
        fputc('#',fp);
        fclose(fp);
        printf("表数据存储成功。n");
        return 1;
    }
    //退出函数
    Status EXit(SqList L1,FILE *fp)
    {
        return 0;
    }
    //功能实现
    //初始化表
    void Initlist(Lnode *L)
    {
            L=(Lnode *)malloc(sizeof(Lnode));
            L->data=0;//初始化表元素为0
            L->next=NULL;
    }  
        //DESTORYLIST
    void Destorylist(Lnode *L)
    {
            Lnode *p=L->next,*q;// 约等于初始化操作
            while(p){
                q=p;
                p=p->next;
                free(q);
            }
            L->data=0;
            printf("销毁成功!n");
    }
        //LISTEMPTY清空表
    void  Cleralist(Lnode *L){
            L->data=0;
            Lnode *p=L->next,*q;
            while(p){
                q=p;
                p=p->next;
                free(q);
            }
            printf("清空成功!n");
    }    
        //LISTEMPTY判断表是否为空表
    Status Listempty(Lnode *L){
            if(L->data==0){
                return 1;
            }
            else return FALSE;
    }    
        //LISTLENGTH
    Status Listlength(Lnode *L){
            int i=0;
            if(L->data==0){
                return 0;
            }
            Lnode *p=L->next;
            while(p!=NULL){
                i++;
                p=p->next;
            }
            if(L->data==0){
                return 0;
            }
            return i;
    }
        
    //LOCATEDELEM
    Lnode * Locatedelem(Lnode *L,Elemtype x)//若找到则返回节点指针,若找不到则返回0
    {
            Lnode *p=L->next;
            while(p&&p->data!=x){
                p=p->next;
            }
            return p;
    }
        
        //GETELEM i
    Lnode * Getelem(Lnode *L,int i){
            int j=1;
            Lnode *p=L->next;
            if(i<1||i>L->data)//head表头元素记录表长
            {
                return NULL;
            }
            while(j<i){
                p=p->next;
                j++;
            }
            return p;//返回第一个对应元素的指针
    }
        
        //PRIORELEM
    Lnode * Priorelem(Lnode *L,Elemtype x){
            Lnode *p=L->next,*q=NULL;
            while(p&&p->data!=x)//从第一个节点开始查找data域为x的节点
            {
                q=p;
                p=p->next;
            }
            return q;
        }
        
        //NEXTELEM
    Lnode * Nextelem(Lnode *L,Elemtype x){
            Lnode *p=L->next;
            while(p&&p->data!=x)//从第一个节点开始查找data域为x的节点
            {
                p=p->next;
            }
            p=p->next;
            return p;
        }
    //LISTINSERT
    Status Listinsert(Lnode *L,int i,Elemtype x){
            int j=1;
            Lnode *p=L->next;
            Lnode *s;
            s=(Lnode *)malloc(sizeof(Lnode));//创建data域为x的节点
            if(!s){printf("OVERFLOW!n");return 0;}
            s->data=x;
            s->next=NULL;
            if(i<0||i>L->data+1){
                printf("the wrong input in.");
                return FALSE;
            }
            if(i==0){
                s->next=p;
                L->next=s;
                L->data++;
                return 1;
            }
            while(j<i){
                p=p->next;
                j++;
            }
            L->data++;
            s->next=p->next;//先保存后节点
            p->next=s;
            return 1;//运算成功,返回1
    }
    
        //LISTDELETE
    Status Listdelete(Lnode *L,int i)
    {
            Lnode *p=L->next,*q;
            int j=1;
            if(i<0||i>Listlength(L)-1){
                printf("the wrong input in.");
                return FALSE;
            }
            if(i==0){
                q=p->next;
                L->next=q;
                free(p);
                L->data--;
                return 1;
            }
            while(j<i){//找到第i-1个节点
                p=p->next;
                j++;
            }
            q=p->next;
            p->next=q->next;
            free(q);//释放第i个节点内存
            L->data--;
            return OK;
    }
    //PRINTLIST
    void Printlist(Lnode *L)
    {
            if(L->data==0)
            {
                printf("此表不存在!n");
            }
            if(L->data!=-1)
            {
                Lnode *p=L->next;
                int i=1;
                while(p){
                    printf("a[%d]=%dt",i,p->data);//顺便打印元素序号
                    p=p->next;
                    i++;}
                printf("n");
            }
    }
    #endif /* fun_h */
    //
    //  mue.h
    //  数据结构实验二
    //
    //  Created by 南隹 on 2019/11/5.
    //  Copyright © 2019 南隹. All rights reserved.
    //
    #ifndef mue_h
    #define mue_h
    #include "C1.h"
    #include "fun.h"
    void menu_1(void);
    void menu_2(Lnode *L);
    void listchose(SqList L);
    //menu 菜单:实现用户界面
    void menu_1(void)
    {
        int i,x;
        char filename[20];
        x=0;
        SqList Lis;
        Lis.length=0;
        for(i=0;i<10;i++){
            Lis.head[i].next=NULL;
        }
        Lnode L;
        int op=1;//在函数内实现变量控制和输出控制
        while(op){
            printf("nn");
            printf("                    主菜单                        n");
            printf("-------------------------------------------------n");
            printf("          1. 新建表文件           2. 打开已有文件n");
            printf("          3. 退出系统              n");
            printf("-------------------------------------------------n");
            printf("    请选择你的操作[1~3]:");
            scanf("%d",&op);
            switch(op){
                case 1:
                    printf("您要管理第几个表[0-10]:");
                    scanf("%d",&x);
                    if(x<0||x>10){
                        printf("错误输入!n");
                        continue;
                    }
                    listchose(Lis);
                    break;
                case 2:
                    printf("input file name: ");
                    scanf("%s",filename);
                    fp=fopen(filename,"rb");
                    if(filere(&L,fp)){
                        Listdelete(&L, 0);
                        menu_2(&L);
                    }
                    //这里从文件中逐个读取数据元素恢复顺序表,对于不同的物理结构,可通过读取的数据元素恢复内存中的物理结构。
                    break;
                case 3:
                    EXit(Lis, fp);
                    exit(0);
                    break;
            }//end of switch
        }//end of while
    }
    void menu_2(Lnode *L)
    {
        char filename[20];
        int oper,flag;
        flag=1;
    lop:
        printf("ttt次级菜单n");
        printf("===========================n");
        printf("1.初始化表t2.清空表  t3.判断非空n");
        printf("4.输出表长t5.元素定位t6.读取元素n");
        printf("7.取前元素t8.取后元素t9.插入元素n");
        printf("10.删除元素t11.打印表 t12.保存表n");
        printf("13.销毁表t14.返回上级 n");
        printf("==========================n");
        printf("请根据序号输入对应操作指令:");
        scanf("%d",&oper);
        if(oper>=1&&oper<=12) flag=1;
        if(oper<1||oper>12) flag=0;
        if(flag){
            switch(oper){
                case 1:
                    Initlist(L);
                    printf("已初始化,您要系统顺序生成自定义长度的表或者自定义插入元素?(1/0).n");
                    int i;//功能一选择参数
                    scanf("%d",&i);
                    if(i==1){
                        printf("please input the length of this List.n");
                        scanf("%d",&i);
                        int j;//元素值控制变量
                        Lnode *p;
                        p=L;
                        if(i>0&&i<MaxSize){
                            for(j=0;j<i;j++){
                                p->data=j;
                                p->next=(Lnode *)malloc(sizeof(Lnode));
                                p=p->next;
                            }
                            p=NULL;
                            printf("已初始化并顺序生成%d元素的顺序表。n",i);
                            L->data=i;
                        }
                        else printf("输入错误!n");}
                    if(i==0){
                        printf("please input the length of this List.n");
                        scanf("%d",&i);
                        int j;
                        Lnode *p;
                        p=L;
                        if(i>0&&i<MaxSize){
                            for(j=0;j<i;j++){
                                p->next=(Lnode *)malloc(sizeof(Lnode));
                                printf("please input the value of a[%d]=:",j+1);
                                Elemtype x;
                                scanf("%d",&x);
                                p->next->data=x;
                                p=p->next;
                            }
                            p->next=NULL;
                            printf("已初始化并自定义生成%d元素的顺序表。n",i);
                            L->data=i;
                        }
                        else printf("输入错误!n");
                    }
                    goto lop;;
                case 2:
                    printf("确定清空表?(1/0)n");
                    scanf("%d",&i);
                    if(i){
                        Cleralist(L);;//以255退出系统,一般为不正常退出
                        printf("表已清空。n");
                    }
                    goto lop;
                case 3:
                    if(Listempty(L)){
                        printf("空表。n");
                    }
                    else printf("不空.n");
                    goto lop;
                case 4:
                    printf("表长为:%d.n",Listlength(L));
                    goto lop;
                case 5:
                    printf("n请输入要定位的元素:");
                    Elemtype x;
                    scanf("%d",&x);
                    if(Locatedelem(L, x)){
                        printf("您要将此元素修改为:");
                        Elemtype y;
                        scanf("%d",&y);
                        Locatedelem(L, x)->data=y;
                    }
                    else{
                        printf("未找到对应元素节点!n");
                    }
                    goto lop;
                case 6:
                    printf("输入您要查找的元素序号:");
                    scanf("%d",&x);
                    if(Getelem(L,x)){
                        printf("您要查找第%d号元素的值为%d.n",x,Getelem(L, x)->data);
                    };
                    goto lop;;
                case 7:
                    printf("请输入您要取前元素的元素值:");
                    scanf("%d",&x);
                    if((Locatedelem(L, x))&&Priorelem(L, x)){
                        printf("对应该元素值的第一个元素的前元素元素值为:%dn",Priorelem(L, x)->data);
                    }
                    goto lop;
                case 8:
                    printf("请输入您要取后元素的元素值:");
                    scanf("%d",&x);
                    if((Locatedelem(L, x))&&Nextelem(L, x)){
                        printf("对应该元素值的第一个元素的后元素元素值为:%dn",Nextelem(L, x)->data);
                    }
                    goto lop;
                case 9:
                    printf("请输入您要插入元素的元素值:");
                    scanf("%d",&x);
                    printf("请输入您要插入元素的元素序号:");
                    scanf("%d",&i);
                    if(Listinsert(L, i-1, x)){printf("插入成功!n");}
                    goto lop;
                case 10:
                    printf("您要删除的是第几号元素:");
                    scanf("%d",&x);
                    if(Listdelete(L, x-1)){
                        printf("删除成功!n");}
                    goto lop;
                case 11:
                    if(L->data)
                    {
                        Printlist(L);
                        goto lop;
                    }
                    else
                    {
                        printf("该表为空表不能打印!n");
                        goto lop;
                    }
                    goto lop;
                case 12:
                    printf("input file name: ");
                    scanf("%s",filename);
                    if ((fp=fopen(filename,"wb"))==NULL)
                    {
                        printf("File open erroen ");
                    }
                    Savedata(fp, L);
                    goto lop;
                case 13:
                    printf("确定销毁表?(1/0)n");
                    scanf("%d",&i);
                    if(i){
                        Destorylist(L);
                        printf("表已销毁。n");
                        break;
                    }
                    goto lop;
                case 14:
                    flag=0;
                    break;
            }
        }
    }
    void listchose(SqList L)
    {
        int i;//控制参数序号
        int op;//控制选择
    Lop:
        printf("请输入您要操作的表:");
        scanf("%d",&i);
        menu_2(&L.head[i]);
        printf("是否还要继续操作其他几个表?(1/0)n");
        scanf("%d",&op);
        if(op==1){
            goto Lop;
        }
        else if(op==0){}
        else{
            printf("错误输入!n");
        }
    }
    #endif /* mue_h */
    展开全文
  • 链式存储分配特点: 根据线性表的长度动态申请存储空间,解决顺序存储中存在存储空间难以确定问题。 指针变量特点 变量三要素 名字,内存地址,值 变量左值,右值 左值指变量内存地址 右值:值 在...

    链式存储分配的特点:

    根据线性表的长度动态的申请存储空间,以解决顺序存储中存在的存储空间难以确定的问题。

    指针变量的特点

    变量的三要素

    名字,内存地址,值

    变量的左值,右值

    左值指变量的内存地址
    右值:值
    在赋值表达式中,赋值号左边需要左值,右边需要右值;如a=a+100

    指针变量

    指针变量的右值本身又是一个左值。

    单链表的存储

    结点之间可以连续,也可以不连续存储;
    结点的逻辑顺序与物理顺序可以不一致;
    表可扩充。

    1、链表结点数据类型的定义

    通过指针把它的一串存储结点链接成一个链
    存储结点由两部分组成
    data字段
    link字段
    在这里插入图片描述

    template <typename T>
    struct Node 
    { 
      T data; 
      Node<T> *next;      //此处<T>也可以省略
    }; 
    

    2、头结点

    如果链表有头节点,则链式结构中的第一个节点称为头结点:其数据域可以存储一些附加信息,如链表长度;其指针域指向链表中的第一个节点。

    3、单链表的声明

    template <class T>
    class LinkList { 
      public: 
      LinkList ( ) {first=new Node<T>; first -> next= NULL ;}
         LinkList ( T a[ ], int n ) ; 
      ~LinkList ( ) ; 
      int Length ( ) ;
      T Get ( int i ) ; 
      int Locate ( T x ) ;
      void Insert ( int i, T x ) ;
      T Delete ( int i ) ; 
      void PrintList ( ) ; 
      private: 
      	Node<T>  *first; // 单链表的头指针  , <T>可以省略
    }; 
    

    4、头插法

    插到头结点后面!!
    顺序是倒的!!

    template <class T>  
    LinkList<T>:: LinkList(T a[ ], int n) {
        first=new Node<T>;   //生成头结点
       first->next=NULL;
       Node<T> *s;
       for (int i=0; i<n; i++){ 
              s=new Node<T>; 
              s->data=a[i];  //为每个数组元素建立一个结点
              s->next=first->next;
              first->next=s;
    	}
    }
    

    5、尾插法

    将新建的节点插入到链表的最后
    顺序是正的!!
    注意尾指针

    template <class T>  
    LinkList<T>:: LinkList(T a[ ], int n) {
        Node<T> *r,*s;      //尾指针
        first=new Node<T>;   //生成头结点
    	r=first;          
        for (int i=0; i<n; i++)	{ 
            s=new Node<T>; 
            s->data=a[i];  //为每个数组元素建立一个结点
            r->next=s; r=s;      //插入到终端结点之后
    	}
        r->next=NULL;    //单链表建立完毕,将终端结点的指针域置空
     }
    

    6、遍历

    template <class T>  
    LinkList<T>:: PrintList()
    {
        Node<T> *p;
    	p=first->next;          
         while(p)
    	{
    		cout<<p->data;
                p=p->next;
    	}
     }
    

    补充:不带头结点的情况

    1、头插

    {
        first=NULL;
        for(int i=0;i<n;i++)    { 
             s=new node<T>;
             s->data=a[i];
             s->next=first;
             first=s;   
        }
    }
    

    2、尾插

    要考虑首元节点的情况

    	node<T> *r;
        head=NULL;
        if(n<=0return;
        s=new node<T>;
        s->data=a[0];
        s->next=head;
        head=s;   
        r=head;
        for(int i=1;i<n;i++)    { 
             s=new node<T>;
             s->data=a[i];
             r->next=s;
             r=s;   
        }
    
    

    7、带头节点与不带头结点的对比在这里插入图片描述

    8、单链表中按位置查找

    伪代码

    1.工作指针P初始化,计数器初始化
    2.执行下列操作,直到p为空或指向第i个节点
    	2.1 工作指针后移
    	2.2 计数器增1
    3. 若p为空,则第i个元素不存在,抛出位置异常;否则查找成功,返回节点p的数据元素
    

    实现

    template <class T>
    T LinkList<T>::Get(int i) {   
    	  Node<T> *p; int j;
    	  p=first->next;  j=1;  //或p=first;  j=0;
    	  while (p && j<i) {
        		p=p->next;       //工作指针p后移
    		j++;
      	 }
    	  if (!p) throw "位置";
    	  else return p->data;
    }
    

    ==时间性能为 O ( n ) ==。

    9、单链表的插入操作(按位置进行插入)

    伪代码

    1 工作指针p初始化,计数器初始化
    2 查找第i-1个节点,并使工作指针p指向该节点
    3 若查找不成功(P==NULL),说明位置错误,抛出位置异常,否则
    	3.1 生成一个元素值为x的新节点s
        3.2  将s插入到p之后
    

    实现

    template <class T>  
    void LinkList<T>::Insert(int i, T x){  
       Node<T> *p; int j;
       p=first ; j=0;    //工作指针p初始化
       while (p && j<i-1)   {
         p=p->next;   //工作指针p后移
         j++;
       }
       if (!p) throw "位置";
        else { 
    	  Node<T> *s;
          s=new Node<T>; 
    	  s->data=x;  //向内存申请一个结点s,其数据域为x
          s->next=p->next;       //将结点s插入到结点p之后
          p->next=s;	
    	}
     }
    

    10、(补充)不带头结点的单链表中插入结点

    Insert(int i, T x){  
       Node<T> *p; int j;
       if(i<=0throw “位置非法”;
       if (i==1{ s=new Node<T>;s->next=head;head=s;return}
       p=first ; j=1;    //工作指针p初始化
       while (p && j<i-1)   {
         p=p->next;   //工作指针p后移
         j++;
       }
       if (!p) throw "位置";
        else { 
    	  Node<T> *s;
          s=new Node<T>; 
    	  s->data=x;  //向内存申请一个结点s,其数据域为x
          s->next=p->next;       //将结点s插入到结点p之后
          p->next=s;	
    	}
     }
    
    

    11、单链表中节点的删除(删除编号是i的结点)

    在这里插入图片描述

    template <class T>  
    T LinkList<T>::Delete(int i){ 
      Node<T> *p; int j;
      p=first ; j=0;  //工作指针p初始化
      while (p && j<i-1) {  //查找第i-1个结点
        p=p->next; 
        j++;
      }
      if (!p || !p->next) throw "位置";  //结点p不存在或结点p的后继结点不存在
        else {
      	     Node<T> *q; T x;
              q=p->next; x=q->data;  //暂存被删结点
              p->next=q->next;  //摘链
              delete q; 
              return x;
    	}
    }
    

    12、带头节点与不带头结点的对比

    在这里插入图片描述

    13、析构函数

    template <class T>
    LinkList<T>:: ~LinkList()
    {
       Node<T> *q;
       while (first)
       {
           q=first->next;
           delete first;
           first=q;
        }
    }
    
    展开全文
  • 线性表的链式存储结构线性表的链式存储结构单链表头结点和头指针结点和单链表c语言描述单链表操作的实现单链表获取第i个数据元素插入数据元素删除数据元素重置为一个空表生成包含n个数据元素链表 线性表的链式...

    线性表的链式存储结构

    单链表

    概念: 用一组地址任意的存储单元存放线性表中的数据元素。
    +     = 以元素(数据元素的映象)+ 指针(指示后继元素存储位置) \\ `\\ \ \ \ \ \ = 结点 (表示数据元素 或 数据元素的映象)

    • 以线性表中第一个数据元素a1a_1的存储地址作为线性表的地址,称作线性表的头指针。链表是由头指针唯一确定的,知道了头指针就知道了链表。
    • aia_i的地址被它的直接前驱ai1a_{i-1}存放。
    • 最后一个结点ana_n的指针域为空。

    头结点和头指针

    有的时候为了操作方便,在第一个结点之前虚加一个“头结点”,以指向头结点的指针为链表的头指针。

    在这里插入图片描述
    若线性表为空时,头指针不再为空,头结点的指针域为空。
    一般单链表都是带头结点的。
    总结一下头指针和头结点的异同:

    1. 头指针是链表的必要条件,而头结点不是;
    2. 头指针是链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针;
    3. 头指针具有标识作用,常用头指针冠以链表名;
    4. 头结点使得在第一元素结点前插入结点和删除第一结点不再特殊,和其它结点的操作统一;
    5. 头结点将空表和非空表的操作统一;
    6. 头结点的数据域一般为空(或存放链表长度)。

    结点和单链表的c语言描述

    typedef struct LNode{
    	int data; //数据域
    	struct LNode* next;//指针域
    }LNode,*LinkList;//结点别名 结点指针别名
    
    LinkList L;//单链表的头指针,全局变量不是必须的
    

    单链表操作的实现

    单链表的初始化

    添加头结点,链表的尾结点指针别忘了设成NULL

    int InitList(LinkList& L)
    {
    	//加入头结点
    	LNode* a = new LNode;
    	L = a;
    	L->next=NULL;
    	return 0;
    }
    

    添加元素至链表尾部

    int ListAppend(LinkList& L,int e) {
    	LNode* p = L;
    	while (p->next) { //找到链表尾部
    		p = p->next;
    	}
    	LNode* node = new LNode;
    	node->data = e;
    	node->next = NULL; //结尾别忘了设成NULL
    	p->next = node; //加入新结点
    	return 0;
    }
    

    单链表获取第i个数据元素

    对于单链表来说,无论是按下标获取元素还是按值获取元素都要对链表进行遍历操作,所以时间复杂度都是O(n)。
    按下标获取元素思路:关键是使用一个计数器j记录访问过的结点数,不断用j和要查找的元素下标i进行比较。

    int GetElem(LinkList& L, int i, int& e) {
    	LNode* p=L; int j = 0;
    	while (p&&j<i) { p=p->next; j++; }
    	if (!p || j>i)	return -1;
    	e = p->data;
    	return 0;
    }
    

    插入数据元素

    向位置i插入指定数据元素e。
    思路:让待插入结点的指针*s指向插入位置i的后一结点*ai+1,然后让位置i的结点的指针*ai指向待插入结点*s。
    在链表中插入结点只需要修改指针,时间复杂度O(1)。
    但是,若在第i个结点插入指针,首先要找到第i个结点,这一步需要O(n)。那么,这和顺序表的时间消耗不是一样了吗?
    不是的。虽然都是O(n)的消耗,但顺序表需要移动元素,这是在存储器上操作的;链表只需要比较操作,这是在运算器上操作的。二者不是一个数量级!

    int ElemInsert(LinkList& L, int i, int e) {
    	LNode* p = L;
    	int j = 1; //位置i从1开始计算,如果需要从0开始,令j=0
    	while (p&&j<i) { p=p->next; j++; }
    	if (!p || j>i) return -1;
    	LNode* s = new LNode;
    	s->data = e;
    	s->next=p->next;
    	p->next=s;
    	return 0;
    }
    

    后插与前插

    • 后插结点:p指向链表某结点,s指向待插入的、值为x的新结点,将*s插入到*p的后面。上边的例子就是一个后插结点的操作,直接修改*s让它指向*p的后继结点,再让*p指向*s即可。
    • 前插结点:设p指向链表中某结点,s指向待插入的、值为x的新结点,将*s插入到*p的前面。与后插不同的是:首先要找到*p的前驱*q,然后再在*q之后插入*s,设单链表头指针为L。

    前插伪代码:

    	q=L;
    	while(q->next!=p) q=q++;//找*p的直接前驱
    	s->next=q->next;
    	q->next=s;
    

    显然,前插的时间复杂度是O(n)。

    前插的时间主要消耗在了查找*p的前驱上,*p已知的情况下,能不能用后插实现前插,将时间复杂度降到O(1)呢?
    思路:*s插到*p之后,交换p->dara与s->data。
    代码略。

    删除数据元素

    删除第i个元素ai的操作:
    思路:使待删除结点ai的直接前驱ai-1指向待删除结点的直接后继ai+1

    int ElemDelete(LinkList& L,int i,int& e){
    	LNode* p=L,*q;
    	int j=0;
    	while(p&&j<i-1) {p=p->next;j++;}  //p指向a_{i-1}
    	if(!(p->next)||j>i-1) return -1;
    	q=p->next; //q指向a_{i}
    	p->next=q->next;//a_{i-1}指向a_{i+1}
    	e=q->data;
    	return 0;
    }
    

    时间复杂度O(n)。

    重置为一个空表

    思路:让头指针指向最后一个结点的指针,这个指针是空指针。

    int ClearList(LinkList& L){
    	while(L->next){
    		LNode* p = new LNode;
    		p=L->next;L->next=p->next;//不断的删去当前的第一个结点
    		delete p;
    	}
    	return 0;
    }
    

    时间复杂度O(n)。

    如何从线性表得到单链表(构造单链表)

    链表是一个动态结构,生成链表的过程是逐个结点插入的过程。

    • 第一步:建立空表(带头结点),也就是单链表初始化。
    • 第二步:用元素构建结点,并插入。循环此步骤,直至所有元素都插入完成。

    我们对上边提到的添加元素至链表尾部中的方法不断调用就可以实现第二步,这种方法也叫尾插法

    //传入使用 InitList 初始化之后的L
    int CreatList(LinkList& L,int e[],int n){
    	LNode *r=L;//初始化尾指针
    	for(int i=0;i<n;i++){
    		LNode* p = new LNode;
    		p->data=e[i];
    		r->next=p;//尾部插入新结点
    		r=p;//新结点变为新的尾结点
    	}
    	r->next=NULL;//尾结点的next指向NULL	
    }
    

    此外,还有一种头插法
    头插法: 通过逆位序输入n个元素的值,建立单链表。

    //传入使用 InitList 初始化之后的L
    int CreatList(LinkList& L,int e[],int n){
    	for(int i=0;i<n;i++){
    		LNode* p=new LNode;
    		p->data=e[i];
    		p->next=L->next;
    		L->next=p;
    	}
    	return 0;
    }
    

    循环链表(单向)

    最后一个结点的指针域的指针又指回第一个结点的链表。
    和单链表的差别仅在于,辨别链表中最后一个结点的条件不再是“后继是否为空”,而是“后继是否为头结点”。

    特点:

    1. 对于单链表只能从头结点开始遍历整个链表,而对于单循环链表则可以从表中任意结点开始遍历整个链表。
    2. 有时对链表常做的操作是在表尾、表头进行,此时可以改变一下链表的标识方法,不用头指针而用一个指向尾结点的指针R来标识,可以使得操作效率提高。
    3. 在做链表合并和分裂时,如果不是必须从链表头开始,则可以直接在链表指针处合并,时间复杂度可达O(1)。

    双向链表和双向循环链表

    双向循环链表的空表的结构:头指针指向头结点;头结点的前向指针prior指向自身,后向指针next也指向自身,如图:
    在这里插入图片描述

    插入

    在这里插入图片描述
    s为待插入结点,p为插入位置原来的结点,q为p的直接后继。
    已知项是p的后继是q。
    需要修改的是p的后继,q的前驱,s的后继,s的前驱。
    插入分四步:

    1. 令s的前驱指向p
    2. 令s的后继指向p的后继
    3. 令p的后继(或s的后继)结点的前驱q指向s
    4. 令p的后继指向s
      这四步能不能交换?
      可以交换,但不是无条件的。必须时刻保证能够通过s和p能找到q。
      一个反例:上来就令p的后继指向s,这时我们就无法找到q了。
      规律:第1步的顺序任意,第2步在第4步之前,第3步在第4步之前

    删除

    已知结点p,p的后继结点是s,s的后继结点是q,现在要删除s。
    两步:

    1. p的后继指向p的后继的后继(q)
    2. p的后继(q)的前驱指向p

    双向链表的操作特点:

    • “查询”和单链表相同
    • 插入和删除时需要同时修改两个方向上的指针
    • 访问某个结点的直接前驱和直接后继时间复杂度都是O(1)。
    • 查找第i个结点,向第i给结点插入或删除第i个结点,都要区分是哪个方向
    • 如果是双向循环链表,修改指针要同时考虑前驱环链和后继环链上的修改。
    • 某个结点的直接前驱的直接后继,或它的直接后继的直接前驱,即为该结点本身。

    存储密度:
    分母是结点所占的存储量,分子是数据元素所占的存储量。
    双向链表和双向循环链表的优点是前驱操作更方便
    缺点是存储密度变低了。

    静态链表

    前边的链表结构都属于动态链表,还有一类静态链表。
    借助数组来描述线性表的链式存储结构,结点也有数据域data和指针域next,与动态链表中的指针不同的是,这里的指针是结点的相对地址(数组的下标,整型),称之为静态指针。

    #define MAXSIZE 100
    typedef struct sLNode{
    	int data;
    	int next; //这个“指针”实际上是基址的相对偏移量
    }component,SLinkList[MAXSIZE];
    
    

    静态链表适用于不支持“指针”的高级语言,或者最大元素固定但插入、删除操作频繁的链表应用中。有关基于静态链表上的线性表操作基本与动态链表相同,除了一些描述方法有区别外,算法思路是相同的。

    特点:

    • 所有数据元素均存储在连续的空间段,但是相邻两个元素不一定处在相邻的空间,即物理上相邻,逻辑上不一定相邻
    • 修改指针域即可完成插入和删除操作,不需要移动元素,但是也不能随机访问静态链表中的元素;
    • 一次性分配所有存储空间,插入、删除时无需再向操作系统申请或释放空间,但也限制了最大表长。

    代码可以参考:
    https://www.cnblogs.com/zrj-xjyd/p/8735145.html

    顺序表和链表的比较

    1. 顺序表和链表各有优缺点。
      顺序表优点:
    • 方法简单,各种高级语言都有数组,容易实现。
    • 不用为表示结点间的逻辑关系而增加额外的存储开销。
    • 顺序表具有按元素序号随机访问的特点。

    顺序表缺点:

    • 在顺序表中做插入或删除,平均移动大约表中一半的元素,对n较大的顺序表效率低。
    • 需要预先分配足够大的存储空间,估计过大会导致顺序表后部大量闲置;估计过小会导致溢出。

    链表的优缺点和顺序表相反。
    链表的优点:

    • 插入和删除不需要移动元素,只需要修改指针
    • 动态分配,不需要预先分配,没有溢出和闲置的问题

    缺点:

    • 链表需要指针,不是每一个高级语言都有。
    • 需要借助附加信息,即指针,来描述逻辑关系
    • 只能顺序访问,不能随机访问
    1. 实际中怎样选取存储结构?
    • 基于存储的考虑
      1. 存储规模难以估计时,不宜采用顺序表
      2. 链表的存储密度较低
    • 基于运算的考虑
      1. 经常按序号访问,顺序表更好
      2. 经常做插入、删除,链表更好
    • 基于环境的考虑
      1. 顺序表容易实现,任何高级语言都有数组类型
    展开全文
  • 这就是我今天要实现的线性表链式存储结构...  我们知道在顺序表中它的物理存储位置是连续的所以当我们顺序表的形式实现线性表的插入和删除时我们需要移动大量的元素; 假设线性表中的每个数据存储的位置...
  • 掌握线性表的基本操作在两种存储结构的实现,其中链表操作为侧重点。 会灵活运用线性表结构解决某些实际问题。 二、 实验内容 1. 线性表顺序存储结构下基本操作的实现(初始化、赋值、取值、插入、删除、归并...
  • 1.线性表的链式图。 2.头结点和头指针异同。 头指针head 头指针是指链表指向第一个结点指针,若链表有头结点,则是指向头结点指针。 头指针具有标识作用,所以常用头指针冠链表名字。 无论...
  • 2.3.1 线性表的链式存储结构——链表 链表: 1.每个节点中除数据域外,设置了一个指针域,用指向其后继节点,这样构成链接表称为线性单向链表,简称单链表。 2.每个节点中除数据域外,设置两个指针域,分别...
  • 线性表链式实现

    2019-06-26 21:24:57
    今天复习 以链式存储方式 实现的线性表结构,简称为链表。这里我们只介绍单链表 基本理论 以链式存储方式实现的线性表结构,简称为链表。 链表与顺序结构不同,顺序存储结构要求线性表逻辑结构与物理结构相同,...
  • 上一篇博客中说明了什么是线性表——线性表就是一个个数据元素逻辑上一对一相邻关系(但是在物理结构上并不一定是连续得到)组织起来有限序列。 根据物理存储方式不同可以将线性表分为两种,一种叫顺序表,...
  • 链式存储空间为代价换取了时间,其实写代码基本没有绝对事情,我们总是在寻找最合适方式处理我们遇到问题,在时间和空间之间找平衡点,有时候时间要求更多一点,有时候空间要求更多一点,具体情况具体.....
  •   栈的链式存储结构也称为链栈,栈的链式存储结构本质上还是以线性表的链式存储来实现的,一般来说,链表有头指针,栈也有栈顶指针,那么可以把栈顶放在链表的头部,用头指针来表示栈顶指针,但是这里我们不用头...
  • 链表结构 链表节点为单位,每个节点分两部分,一部分存放有效数据,另一部分存向另外节点地址,一个节点实际就是一个结构体 ...线性表的链式存储实现 基本操作 void creat_list(NODE* head,int n); //创建链...
  • 熟练掌握线性表的基本操作在顺序存储和链式存储的实现 2. 以线性表的各种操作建立插入删除等的实现为重点 3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现 实验 条件 运行Visual c++微机一台 实验...
  • 1.数据结构中,线性表的储存是最重要的,有顺序存储的顺序表,和链式存储的单链表(当然还有双链表,循环链表,此处只讨论单链表)。顺序表是基于数组实现的,而单链表主要是居于链式存储实现的。下面我们来看看...
  • 2.1 链式存储结构之一:单链表 利用单链表(也称线性链表)来实现,从链表第一个数据元素开始,依次将线性表的结点存入。需要注意是,链表每个数据元素除了要存储线性表的数据元素信息之外,还要有一
  • 本课主题: 线性表的链式表示与实现 教学目的: 掌握线性链表、单链表、静态链表的概念、...以链式结构存储的线性表称之为线性链表。 特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻
  • 采用链式存储结构实现。 2,抽象数据类型ADT设计(线性表需要提供什么接口?) 3,ADT实现(采用何种具体存储结构,如顺序数组或单链表) 二,定义接口ListInterface,确定线性表要提供方法 public interface ...
  • 线性表链式存储

    2017-07-10 19:23:40
     c/c++程序链表是指针变量来实现线性表的数据结构,特性是使用不连续的存储空间来存储数据,内存分配是在执行时才会发生,不需要实现声明,这种分配方式称为动态内存分配。 优点:①因为是使用时才分配内存,...
  • 知识回顾 顺序表特点:物理位置相邻表示逻辑关系。 顺序表优点:任一元素均可随机存取。 顺序表缺点:进行插入和删除操作时,需移动大量...例:26个英文小写字母表的链式存储结构 逻辑结构:( a, b,... ,y,z) .
  • 1.单链表 ①特点 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻元素 每个数据元素ai,除存储本身信息外...以线性表中第一个数据元素a1 的存储地址作为线性表的地址,称
  • 链式存储结构特点:数据元素存储对应是不连续存储空间,每个存储节点对应一个需要存储元素,,元素之间逻辑关系通过存储节点之间链接关系反映出来。 java中是一维数组和对象引用基础上去讨论和...
  • 熟练掌握线性表的基本操作在顺序存储和链式存储的实现 验 2. 以线性表的各种操作建立插入删除等的实现为重点 目 3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现 实 验 运行 Visual c++ 微机一...
  • 这几天复习数据结构,打算把所有数据结构的代码和伪代码整理出来,备查阅。 实现代码来自于实验楼,因学校教材《数据结构(c语言版)》上面竟然出现了new关键字以及引用&,让人搞不清是c还是c++,虽然自己...
  • 因为Swift语言是面向对象语言,所以在相关示例实现的时候与之前在大学学数据结构时C语言的实现有些出入,不过数据结构还是要注重思想,至于实现语言是面向对象的还是面向过程的影响不大。 接触过数据结构的小伙伴...
  • 2、链式存储结构 结点在存储器中位置是任意,即逻辑上相邻数据元素在物理上不一定相邻。 线性表的链式表示又称为非顺序映像或链式映像。 用一组物理位置任意存储单元来存放线性表的数据元素。这组存储...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 321
精华内容 128
关键字:

以链式存储结构实现的线性表