精华内容
下载资源
问答
  • 2021-05-22 18:38:15

    1.概述

    通常来说顺序表是在计算机的内存中以数组的形式保存的线性表,是用一组地址连续的存储单元依次存储数据元素的线性数据结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

    将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构就是顺序结构。

    采用顺序存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L  1≤i≤n 其中,L是元素占用存储单元的长度。如顺序表的每个结点占用len个内存单元,用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系:location (ki+1) = location (ki) +len

    location (ki) = location(k1) + (i-1)len

    存储结构要体现数据的逻辑结构,顺序表的存储结构中,内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。

    2.基本操作

    /* c2-1.h 线性表的动态分配顺序存储结构 */

    #define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */

    #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */

    typedef struct

    {

    ElemType *elem; /* 存储空间基址 */

    int length; /* 当前长度 */

    int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */

    }SqList;

    /* bo2-1.c 顺序表示的线性表(存储结构由c2-1.h定义)的基本操作(12个) */

    Status InitList(SqList *L) /* 算法2.3 */

    { /* 操作结果:构造一个空的顺序线性表 */

    (*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

    if(!(*L).elem)

    exit(OVERFLOW); /* 存储分配失败 */

    (*L).length=0; /* 空表长度为0 */

    (*L).listsize=LIST_INIT_SIZE; /* 初始存储容量 */

    return OK;

    }

    Status DestroyList(SqList *L)

    { /* 初始条件:顺序线性表L已存在。操作结果:销毁顺序线性表L */

    free((*L).elem);

    (*L).elem=NULL;

    (*L).length=0;

    (*L).listsize=0;

    return OK;

    }

    Status ClearList(SqList *L)

    { /* 初始条件:顺序线性表L已存在。操作结果:将L重置为空表 */

    (*L).length=0;

    return OK;

    }

    Status ListEmpty(SqList L)

    { /* 初始条件:顺序线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */

    if(L.length==0)

    return TRUE;

    else

    return FALSE;

    }

    int ListLength(SqList L)

    { /* 初始条件:顺序线性表L已存在。操作结果:返回L中数据元素个数 */

    return L.length;

    }

    Status GetElem(SqList L,int i,ElemType *e)

    { /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */

    /* 操作结果:用e返回L中第i个数据元素的值 */

    if(i<1||i>L.length)

    exit(ERROR);

    *e=*(L.elem+i-1);

    return OK;

    }

    int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))

    { /* 初始条件:顺序线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) */

    /* 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。 */

    /* 若这样的数据元素不存在,则返回值为0。算法2.6 */

    ElemType *p;

    int i=1; /* i的初值为第1个元素的位序 */

    p=L.elem; /* p的初值为第1个元素的存储位置 */

    while(i<=L.length && !compare(*p++,e))

    ++i;

    if(i<=L.length)

    return i;

    else

    return 0;

    }

    Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)

    { /* 初始条件:顺序线性表L已存在 */

    /* 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */

    /* 否则操作失败,pre_e无定义 */

    int i=2;

    ElemType *p=L.elem+1;

    while(i<=L.length && *p!=cur_e)

    {

    p++;

    i++;

    }

    if(i>L.length)

    return INFEASIBLE;

    else

    {

    *pre_e=*--p;

    return OK;

    }

    }

    Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)

    { /* 初始条件:顺序线性表L已存在 */

    /* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, */

    /* 否则操作失败,next_e无定义 */

    int i=1;

    ElemType *p=L.elem;

    while(i(*L).length+1) /* i值不合法 */

    return ERROR;

    if((*L).length>=(*L).listsize) /* 当前存储空间已满,增加分配 */

    {

    newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));

    if(!newbase)

    exit(OVERFLOW); /* 存储分配失败 */

    (*L).elem=newbase; /* 新基址 */

    (*L).listsize+=LISTINCREMENT; /* 增加存储容量 */

    }

    q=(*L).elem+i-1; /* q为插入位置 */

    for(p=(*L).elem+(*L).length-1;p>=q;--p) /* 插入位置及之后的元素右移 */

    *(p+1)=*p;

    *q=e; /* 插入e */

    ++(*L).length; /* 表长增1 */

    return OK;

    }

    Status ListDelete(SqList *L,int i,ElemType *e) /* 算法2.5 */

    { /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */

    /* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 */

    ElemType *p,*q;

    if(i<1||i>(*L).length) /* i值不合法 */

    return ERROR;

    p=(*L).elem+i-1; /* p为被删除元素的位置 */

    *e=*p; /* 被删除元素的值赋给e */

    q=(*L).elem+(*L).length-1; /* 表尾元素的位置 */

    for(++p;p<=q;++p) /* 被删除元素之后的元素左移 */

    *(p-1)=*p;

    (*L).length--; /* 表长减1 */

    return OK;

    }

    Status ListTraverse(SqList L,void(*vi)(ElemType*))

    { /* 初始条件:顺序线性表L已存在 */

    /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */

    /* vi()的形参加'&',表明可通过调用vi()改变元素的值 */

    ElemType *p;

    int i;

    p=L.elem;

    for(i=1;i<=L.length;i++)

    vi(p++);

    printf("\n");

    return OK;

    }

    /* algo2-1.c 实现算法2.1的程序 */

    #include"c1.h"

    typedef int ElemType;

    #include"c2-1.h" /* 采用线性表的动态分配顺序存储结构 */

    #include"bo2-1.c" /* 可以使用bo2-1.c中的基本操作 */

    Status equal(ElemType c1,ElemType c2)

    { /* 判断是否相等的函数,Union()用到 */

    if(c1==c2)

    return TRUE;

    else

    return FALSE;

    }

    void Union(SqList *La,SqList Lb) /* 算法2.1 */

    { /* 将所有在线性表Lb中但不在La中的数据元素插入到La中 */

    ElemType e;

    int La_len,Lb_len;

    int i;

    La_len=ListLength(*La); /* 求线性表的长度 */

    Lb_len=ListLength(Lb);

    for(i=1;i<=Lb_len;i++)

    {

    GetElem(Lb,i,&e); /* 取Lb中第i个数据元素赋给e */

    if(!LocateElem(*La,e,equal)) /* La中不存在和e相同的元素,则插入之 */

    ListInsert(La,++La_len,e);

    }

    }

    void print(ElemType *c)

    {

    printf("%d ",*c);

    }

    int main()

    {

    SqList La,Lb;

    Status i;

    int j;

    i=InitList(&La);

    if(i==1) /* 创建空表La成功 */

    for(j=1;j<=5;j++) /* 在表La中插入5个元素 */

    i=ListInsert(&La,j,j);

    printf("La= "); /* 输出表La的内容 */

    ListTraverse(La,print);

    InitList(&Lb); /* 也可不判断是否创建成功 */

    for(j=1;j<=5;j++) /* 在表Lb中插入5个元素 */

    i=ListInsert(&Lb,j,2*j);

    printf("Lb= "); /* 输出表Lb的内容 */

    ListTraverse(Lb,print);

    Union(&La,Lb);

    printf("new La= "); /* 输出新表La的内容 */

    ListTraverse(La,print);

    return 0;

    }

    更多相关内容
  • 数据结构中,线性表是一种入门级的数据结构,线性表分为序列表和链表,在下文中爱站技术频道小编将实例详解C语言线性表的顺序与实现步骤,下面一起跟着爱站技术频道的步伐来学习吧!1.概述通常来说顺序表是在计算机...

    数据结构中,线性表是一种入门级的数据结构,线性表分为序列表和链表,在下文中爱站技术频道小编将实例详解C语言线性表的顺序与实现步骤,下面一起跟着爱站技术频道的步伐来学习吧!

    1.概述

    通常来说顺序表是在计算机的内存中以数组的形式保存的线性表,是用一组地址连续的存储单元依次存储数据元素的线性数据结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

    将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构就是顺序结构。

    采用顺序存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L  1≤i≤n 其中,L是元素占用存储单元的长度。如顺序表的每个结点占用len个内存单元,用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系:location (ki+1) = location (ki) +len

    location (ki) = location(k1) + (i-1)len

    存储结构要体现数据的逻辑结构,顺序表的存储结构中,内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。

    2.基本操作

    /* c2-1.h 线性表的动态分配顺序存储结构 */

    #define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */

    #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */

    typedef struct

    {

    ElemType *elem; /* 存储空间基址 */

    int length; /* 当前长度 */

    int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */

    }SqList;

    /* bo2-1.c 顺序表示的线性表(存储结构由c2-1.h定义)的基本操作(12个) */

    Status InitList(SqList *L) /* 算法2.3 */

    { /* 操作结果:构造一个空的顺序线性表 */

    (*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

    if(!(*L).elem)

    exit(OVERFLOW); /* 存储分配失败 */

    (*L).length=0; /* 空表长度为0 */

    (*L).listsize=LIST_INIT_SIZE; /* 初始存储容量 */

    return OK;

    }

    Status DestroyList(SqList *L)

    { /* 初始条件:顺序线性表L已存在。操作结果:销毁顺序线性表L */

    free((*L).elem);

    (*L).elem=NULL;

    (*L).length=0;

    (*L).listsize=0;

    return OK;

    }

    Status ClearList(SqList *L)

    { /* 初始条件:顺序线性表L已存在。操作结果:将L重置为空表 */

    (*L).length=0;

    return OK;

    }

    Status ListEmpty(SqList L)

    { /* 初始条件:顺序线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */

    if(L.length==0)

    return TRUE;

    else

    return FALSE;

    }

    int ListLength(SqList L)

    { /* 初始条件:顺序线性表L已存在。操作结果:返回L中数据元素个数 */

    return L.length;

    }

    Status GetElem(SqList L,int i,ElemType *e)

    { /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */

    /* 操作结果:用e返回L中第i个数据元素的值 */

    if(i<1||i>L.length)

    exit(ERROR);

    *e=*(L.elem+i-1);

    return OK;

    }

    int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))

    { /* 初始条件:顺序线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) */

    /* 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。 */

    /* 若这样的数据元素不存在,则返回值为0。算法2.6 */

    ElemType *p;

    int i=1; /* i的初值为第1个元素的位序 */

    p=L.elem; /* p的初值为第1个元素的存储位置 */

    while(i<=L.length && !compare(*p++,e))

    ++i;

    if(i<=L.length)

    return i;

    else

    return 0;

    }

    Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)

    { /* 初始条件:顺序线性表L已存在 */

    /* 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */

    /* 否则操作失败,pre_e无定义 */

    int i=2;

    ElemType *p=L.elem+1;

    while(i<=L.length && *p!=cur_e)

    {

    p++;

    i++;

    }

    if(i>L.length)

    return INFEASIBLE;

    else

    {

    *pre_e=*--p;

    return OK;

    }

    }

    Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)

    { /* 初始条件:顺序线性表L已存在 */

    /* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, */

    /* 否则操作失败,next_e无定义 */

    int i=1;

    ElemType *p=L.elem;

    while(i

    {

    i++;

    p++;

    }

    if(i==L.length)

    return INFEASIBLE;

    else

    {

    *next_e=*++p;

    return OK;

    }

    }

    Status ListInsert(SqList *L,int i,ElemType e) /* 算法2.4 */

    { /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L)+1 */

    /* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */

    ElemType *newbase,*q,*p;

    if(i<1||i>(*L).length+1) /* i值不合法 */

    return ERROR;

    if((*L).length>=(*L).listsize) /* 当前存储空间已满,增加分配 */

    {

    newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));

    if(!newbase)

    exit(OVERFLOW); /* 存储分配失败 */

    (*L).elem=newbase; /* 新基址 */

    (*L).listsize+=LISTINCREMENT; /* 增加存储容量 */

    }

    q=(*L).elem+i-1; /* q为插入位置 */

    for(p=(*L).elem+(*L).length-1;p>=q;--p) /* 插入位置及之后的元素右移 */

    *(p+1)=*p;

    *q=e; /* 插入e */

    ++(*L).length; /* 表长增1 */

    return OK;

    }

    Status ListDelete(SqList *L,int i,ElemType *e) /* 算法2.5 */

    { /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */

    /* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 */

    ElemType *p,*q;

    if(i<1||i>(*L).length) /* i值不合法 */

    return ERROR;

    p=(*L).elem+i-1; /* p为被删除元素的位置 */

    *e=*p; /* 被删除元素的值赋给e */

    q=(*L).elem+(*L).length-1; /* 表尾元素的位置 */

    for(++p;p<=q;++p) /* 被删除元素之后的元素左移 */

    *(p-1)=*p;

    (*L).length--; /* 表长减1 */

    return OK;

    }

    Status ListTraverse(SqList L,void(*vi)(ElemType*))

    { /* 初始条件:顺序线性表L已存在 */

    /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */

    /* vi()的形参加'&',表明可通过调用vi()改变元素的值 */

    ElemType *p;

    int i;

    p=L.elem;

    for(i=1;i<=L.length;i++)

    vi(p++);

    printf("\n");

    return OK;

    }

    /* algo2-1.c 实现算法2.1的程序 */

    #include"c1.h"

    typedef int ElemType;

    #include"c2-1.h" /* 采用线性表的动态分配顺序存储结构 */

    #include"bo2-1.c" /* 可以使用bo2-1.c中的基本操作 */

    Status equal(ElemType c1,ElemType c2)

    { /* 判断是否相等的函数,Union()用到 */

    if(c1==c2)

    return TRUE;

    else

    return FALSE;

    }

    void Union(SqList *La,SqList Lb) /* 算法2.1 */

    { /* 将所有在线性表Lb中但不在La中的数据元素插入到La中 */

    ElemType e;

    int La_len,Lb_len;

    int i;

    La_len=ListLength(*La); /* 求线性表的长度 */

    Lb_len=ListLength(Lb);

    for(i=1;i<=Lb_len;i++)

    {

    GetElem(Lb,i,&e); /* 取Lb中第i个数据元素赋给e */

    if(!LocateElem(*La,e,equal)) /* La中不存在和e相同的元素,则插入之 */

    ListInsert(La,++La_len,e);

    }

    }

    void print(ElemType *c)

    {

    printf("%d ",*c);

    }

    int main()

    {

    SqList La,Lb;

    Status i;

    int j;

    i=InitList(&La);

    if(i==1) /* 创建空表La成功 */

    for(j=1;j<=5;j++) /* 在表La中插入5个元素 */

    i=ListInsert(&La,j,j);

    printf("La= "); /* 输出表La的内容 */

    ListTraverse(La,print);

    InitList(&Lb); /* 也可不判断是否创建成功 */

    for(j=1;j<=5;j++) /* 在表Lb中插入5个元素 */

    i=ListInsert(&Lb,j,2*j);

    printf("Lb= "); /* 输出表Lb的内容 */

    ListTraverse(Lb,print);

    Union(&La,Lb);

    printf("new La= "); /* 输出新表La的内容 */

    ListTraverse(La,print);

    return 0;

    }

    关于实例详解C语言线性表的顺序与实现步骤爱站技术频道小编就说到这里了,相信认真看完这篇文章的朋友对这方面知识都了解了,如果你想了解更多,那就关注爱站技术频道吧!

    展开全文
  • c语言线性表-顺序表(完整版)

    千次阅读 多人点赞 2020-10-01 17:32:49
    c语言线性表顺序存储表示 这几天我尝试写写c语言顺序表,我是这样想的:在学链表之前,先搞懂顺序表。 不喜勿喷,本人新手,大多代码借鉴书上。如有错误之处,请原谅! 首先创建一个结构体: typedef struct { ...

    c语言线性表顺序存储表示

    这几天我尝试写写c语言顺序表,我是这样想的:在学链表之前,先搞懂顺序表。
    不喜勿喷,本人新手,大多代码借鉴书上。如有错误之处,请原谅!
    首先创建一个结构体:

    typedef struct
    {
    	ElemType *elem;//存储空间的基地址 
    	int length;//当前长度 
    }Sqlist;//顺序表的结构类型为Sqlist 
    

    然后建立一个空表,并填上数据:

    Status InitList(Sqlist &L)//建立一个空表 
    {
    	L.elem = new ElemType[MAXSIZE];
    	if(!L.length)
    	{
    		exit(OVERFLOW);//OVERFLOW需要重定义
    	}
    	L.length = 0;
    	return 0;
    }
    

    顺序表结构至此已经搭建好了,下一步便是往空表上填数据。

    Status MyList(Sqlist &L)//在空表上输入数字,建立一个属于自己填写的表 
    {
    	int b,i=0;
    	printf("表的长度: ");
    	scanf("%d",&L.length);
    	Interrupt(); 
    	printf("输入要填入表的数字:\n");
    	for( ; i < L.length ; i++ )
    	{
    		scanf("%d",&b);	
    		L.elem[i] = b;		
    	}
    	Interrupt(); 
    	return 0;
    }
    

    剩下的工作,便是对自己所创建的顺序表进行修改,装饰。
    顺序表操作包括:增,删,查。
    为了观察输入的顺序表是否正确,先增加个 遍历函数

    Status TraverseList(Sqlist &L)//遍历 ,使现有表中的数据重新打印出来 
    {
    	int j;
    	if(L.length==0)
    	{
    		printf("空表\n");
    		return 0;
    	}
    	else
    	{
    		for(j=0 ; j < L.length ; j++)//建立一个for函数,读取顺序表中的数据 
    			printf("%d  ",L.elem[j]);
    		printf("\n");//最后换行 
    		return 0;
    	}
    }
    

    顺序表的取值(按值查找):

    Status GetElem(Sqlist &L,int i,int &e)//取值 。i:为要取的值得位置,&e:为i位置的接受变量,并且返回主函数 
    {
    	scanf("%d",&i);
    	Interrupt();
    	if(i<0||i>L.length)//判断i的取值是否超范围 
    	{
    		printf("ERROR\n");//如果超范围,返回ERROR,并结束 
    		return 0;
    	}
    	else
    	{
    		e = L.elem[i-1];//返回将第i位置的数据赋值给e,并输出 
    		printf("%d\n",e);
    		return 0;
    	}
    }
    

    顺序表的删除操作:

    Status DeleteElem(Sqlist &L,int i)//删除 。i:为要删除数据的位置 
    {
    	int j;
    	scanf("%d",&i);//输入要删除的第i位 
    	Interrupt();
    	if(i<0||i>L.length)//判断输入的i 是否超范围,如果超出,返回错误。 
    	{
    		printf("ERROR\n");
    		return 0;
    	}
    	else
    	{
    		for(j = i; j<=L.length;j++)//被删除元素之后的元素都向前移一位 
    			L.elem[j-1] = L.elem[j];
    		L.length = L.length-1;//表长减1 
    		return 0;
    	}
    }
    

    顺序表的插入:

    Status ListInsert(Sqlist &L,int i,ElemType e)//顺序表的插入  i:为要插入的表的位置。e:要插入该位置的元素 
    {
    	int j;
    	scanf("%d",&i);
    	scanf("%d",&e);
    	Interrupt();
    	if(i>L.length+1||L.length>=MAXSIZE||i<1)//判断要插入表的位置i是否超出范围 
    	{
    		printf("ERROR\n");
    		return 0;
    	}
    	else
    	{
    		for(j=L.length;j>=i;j--)//插入位置及之后的元素分别向后移一位 
    			L.elem[j]=L.elem[j-1];
    		L.elem[i-1]=e;//将新元素e放入第i个位置 
    		++L.length;//表长加1 
    		return 0;
    	}
    }
    

    顺序表的查找(按位查找):

    Status LocateElem(Sqlist &L,ElemType e)//查找。在顺序表L中查找值为e的数据元素 
    {
    	int j,i=0;
    	bool text=true;//利用bool类型,来判断表里有没有值为e的值 
    	scanf("%d",&e);//输入e的值 
    	Interrupt();
    	for(j=0;j<L.length;j++)//遍历整个顺序表,和e值一一作比较, 
    	{
    		if(L.elem[j]==e)
    		{
    			printf("第 %d 位\n",j+1);
    			i++;
    			text=false;
    		}
    	}
    
    	if(text)//bool类型的输出 
    		printf("没有找到");
    	return 0;
    }
    

    最后附上 完整代码c语言顺序表 存储结构。主函数中为了方便操作增加了一些代码。

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 100//顺序表所能表达的最大长度 
    #define OVERFLOW 1
    
    
    
    typedef int Status;//重命名,使Status和int有相同的作用
    typedef int ElemType;
    
    void Interrupt(void)//创建一个中断函数 
    {
    	while(1) //用于检测换行符,使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    }
    
    typedef struct
    {
    	ElemType *elem;//存储空间的基地址 
    	int length;//当前长度 
    }Sqlist;//顺序表的结构类型为Sqlist 
    
    Status InitList(Sqlist &L)//建立一个空表 
    {
    	L.elem = new ElemType[MAXSIZE];
    	if(!L.length)
    	{
    		exit(OVERFLOW);
    	}
    	L.length = 0;
    	return 0;
    }
    
    Status MyList(Sqlist &L)//在空表上输入数字,建立一个属于自己填写的表 
    {
    	int b,i=0;
    	printf("表的长度: ");
    	scanf("%d",&L.length);
    	Interrupt(); 
    	printf("输入要填入表的数字:\n");
    	for( ; i < L.length ; i++ )
    	{
    		scanf("%d",&b);	
    		L.elem[i] = b;		
    	}
    	Interrupt(); 
    	return 0;
    }
    
    Status TraverseList(Sqlist &L)//遍历 ,使现有表中的数据重新打印出来 
    {
    	int j;
    	if(L.length==0)
    	{
    		printf("空表\n");
    		return 0;
    	}
    	else
    	{
    		for(j=0 ; j < L.length ; j++)//建立一个for函数,读取顺序表中的数据 
    			printf("%d  ",L.elem[j]);
    		printf("\n");//最后换行 
    		return 0;
    	}
    }
    
    Status GetElem(Sqlist &L,int i,int &e)//取值 。i:为要取的值得位置,&e:为i位置的接受变量,并且返回主函数 
    {
    	scanf("%d",&i);
    	Interrupt();
    	if(i<0||i>L.length)//判断i的取值是否超范围 
    	{
    		printf("ERROR\n");//如果超范围,返回ERROR,并结束 
    		return 0;
    	}
    	else
    	{
    		e = L.elem[i-1];//返回将第i位置的数据赋值给e,并输出 
    		printf("%d\n",e);
    		return 0;
    	}
    	
    }
    
    Status DeleteElem(Sqlist &L,int i)//删除 。i:为要删除数据的位置 
    {
    	int j;
    	scanf("%d",&i);//输入要删除的第i位 
    	Interrupt();
    	if(i<0||i>L.length)//判断输入的i 是否超范围,如果超出,返回错误。 
    	{
    		printf("ERROR\n");
    		return 0;
    	}
    	else
    	{
    		for(j = i; j<=L.length;j++)//被删除元素之后的元素都向前移一位 
    			L.elem[j-1] = L.elem[j];
    		L.length = L.length-1;//表长减1 
    		return 0;
    	}
    }
    
    Status ListInsert(Sqlist &L,int i,ElemType e)//顺序表的插入  i:为要插入的表的位置。e:要插入该位置的元素 
    {
    	int j;
    	scanf("%d",&i);
    	scanf("%d",&e);
    	Interrupt();
    	if(i>L.length+1||L.length>=MAXSIZE||i<1)//判断要插入表的位置i是否超出范围 
    	{
    		printf("ERROR\n");
    		return 0;
    	}
    	else
    	{
    		for(j=L.length;j>=i;j--)//插入位置及之后的元素分别向后移一位 
    			L.elem[j]=L.elem[j-1];
    		L.elem[i-1]=e;//将新元素e放入第i个位置 
    		++L.length;//表长加1 
    		return 0;
    	}
    }
    
    Status LocateElem(Sqlist &L,ElemType e)//查找。在顺序表L中查找值为e的数据元素 
    {
    	int j,i=0;
    	bool text=true;//利用bool类型,来判断表里有没有值为e的值 
    	scanf("%d",&e);//输入e的值 
    	Interrupt();
    	for(j=0;j<L.length;j++)//遍历整个顺序表,和e值一一作比较, 
    	{
    		if(L.elem[j]==e)
    		{
    			printf("第 %d 位\n",j+1);
    			i++;
    			text=false;
    		}
    	}
    
    	if(text)//bool类型的输出 
    		printf("没有找到");
    	return 0;
    }
    
    int main()
    {
    	int a,i=0; 
    	char c;
    	Sqlist L;//将L定义为Sqlist类型的变量,便于直接引用 
    	InitList(L); 
    	MyList(L);
    	TraverseList(L);
    	printf("操作输入序号选择:\n 1:遍历顺序表\n 2:顺序表取值\n 3:删除元素\n 4:插入元素\n 5:顺序表查找\n 6:表长\n输入#退出\n");	
    	while(1)
    	{
    		int f = 0;
    		printf("请选择:"); 
    		scanf("%c",&c);
    		Interrupt();
    		switch(c)
    		{
    			case '1': printf("遍历顺序表: ");TraverseList(L); break;
    			case '2': printf("顺序表取值(取值位置): ");GetElem(L, a , a ); break;
    			case '3': printf("删除元素(删除的位置): ");DeleteElem(L,a); break;
    			case '4': printf("插入元素(位置 插入的元素): ");ListInsert(L,a,a); break;
    			case '5': printf("顺序表查找(输入要查找的元素): ");LocateElem(L,a); break;
    			case '6': printf("表长: %d \n",L.length); break;
    			case '#': f = 1; break;
    			default: printf("ERROR\n");
    		}
    		if (f == 1) 
    		{
    			printf("已正常退出!\n");
    			break;
    		}
    	}
    	
    	return 0;
    }
    

    (完)

    展开全文
  • c语言建立线性表 顺序储存 储存结构 初始化(建立)顺序表 查找操作 一、按值查找,找到返回对应的下标 二、按照下标返回元素 插入操作 一、在线性表尾部添加元素 二、在位置i处插入元素 三、顺序表(有序)插入,...

    顺序储存

    储存结构

    采用的是用内存动态分配方式定义线性表的顺序储存结构

    #define LIST_MAX_SIZE 100  //线性表的最大长度
    #define LISTINCREMENT 10  //线性表一次增加的量
    
    typedef struct {
    	int* elem; //指向存放线性表数据元素的基地址
    	int length; //线性表当前长度(当前存储的元素个数)
    	int listsize; // 当前分配的存储容量
    }SQList;
    

    初始化(建立)顺序表

    操作步骤:

    1. 申请一片连续的空间,并将其地址空间赋给elem指针变量。
    2. 开始是length 值为0.
    3. 对listsize 赋初值,其值是申请空间的最大容量。
    //创建一个线性表 
    //注意点是:如果无法分配空间,打印提示,并直接返回
    void CreateList(SQList &L)
    {
    	L.elem = (int *)malloc(LIST_MAX_SIZE * sizeof(int));
    	if (!L.elem) {
    		printf("分配地址出错\n");
    		return;
    	}
    	L.length = 0;
    	L.listsize = LIST_MAX_SIZE;
    }
    
    //求线性表中的元素个数
    int ListLength(SQList L) {
    	return L.length;
    }
    

    查找操作

    一、按值查找,找到返回对应的下标

    一、按值查找,找到返回对应的下标,没有则返回-1。如果有多个返回第一个的位置
    条件:1、线性表存在;2、线性表中有元素

    算法:在条件满足的情况下,遍历一遍,如果下标在i~length之间就返回下标

    int ListLocate(SQList L, int e) {
    	if (!L.elem ) {
    		printf("线性表没有初始化\n");
    		return -1;
    	}
    	if (L.length == 0) {
    		printf("线性表中没有元素\n");
    		return -1;
    	}
    	int i = 1;
    	//下标是从1开始存储元素的
    	while (i <= L.length && e != L.elem[i])
    		i++;
    	if (i <= L.length) {
    		printf("元素已经找到\n");
    		return i;
    	}
    	else {
    		printf("线性表中没有该元素\n");
    		return -1;
    	}
    }
    

    二、按照下标返回元素

    条件:1、线性表存在;2、下表没有越界

    int GetList(SQList L,int i) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return -1;
    	}
    	if (i<1 || i>L.length) {
    		printf("数组下标越界\n");
    		return -1;
    	}
    	return L.elem[i];
    }
    

    插入操作

    插入步骤,在后边一定要将 length 加1

    一、在线性表尾部添加元素

    条件:线性表存在

    在条件满足情况下:L.elem[++L.length] = val; 表示在尾部添加元素

    void ListPush(SQList& L,int val) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return ;
    	}
    	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
    	{
    		//在原来基础上扩大
    		int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
    		if (!newbase) {
    			printf("分配空间错误\n");
    			return;
    		}
    		L.elem = newbase; //获得新基址
    		L.listsize += LISTINCREMENT;//更新容量
    	}
    	//在尾部插入
    	L.elem[++L.length] = val;
    }
    

    二、在位置i处插入元素

    步骤:

    1. 将位置i以后的元素后移一个位置。
    2. 在i处插入值
    void ListInsert(SQList& L, int i, int val) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return;
    	}
    	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
    	{
    		//在原来基础上扩大
    		int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
    		if (!newbase) {
    			printf("分配空间错误\n");
    			return;
    		}
    		L.elem = newbase; //获得新基址
    		L.listsize += LISTINCREMENT;//更新容量
    	}
    	for (int j = L.length; j >= i; --j) {
    		L.elem[j + 1] = L.elem[j]; //i后面的元素后移
    	}
    	//插入元素
    	L.elem[i] = val;
    	L.length++;
    }
    

    三、顺序表(有序)插入,(如都是由小到大)

    基本思路是:

    1. 先找到值val插入的位置。

    int pos = L.length;
    	while (pos > 0 && val < L.elem[pos])
    		pos--;
    	//这个循坏结束后,POS对应位置元素是小于等于val的,所以可以将val插到其后边
    
    for (int i = L.length; i >= pos+1; i--)
    		L.elem[i + 1] = L.elem[i];
    	//在pos后边插入
    	L.elem[pos + 1] = val; 
    
    1. 然后将该位置以后到结尾的元素依次向后移到一位,然后在空出的位置插入val

    void ListInsertorder(SQList& L, int val) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return;
    	}
    	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
    	{
    		//在原来基础上扩大
    		int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
    		if (!newbase) {
    			printf("分配空间错误\n");
    			return;
    		}
    		L.elem = newbase; //获得新基址
    		L.listsize += LISTINCREMENT;//更新容量
    	}
    	//找到要插入的位置
    	int pos = L.length;
    	while (pos > 0 && val < L.elem[pos])
    		pos--;
    	//这个循坏结束后,POS对应位置元素是小于等于val的,所以可以将val插到其后边
    	for (int i = L.length; i >= pos+1; i--)
    		L.elem[i + 1] = L.elem[i];
    	//插入
    	L.elem[pos + 1] = val;
    	L.length++;
    }
    

    删除操作

    插入步骤,在后边一定要将 length 减1

    一、删除位置i的元素,删除成功后,返回删除的值

    两种情况一个是在尾部,另一个是其余位置。 如果是在结尾只要length减一就可以了。
    条件:添加 i不能越界

    基本步骤:

    1. 判断位置i是否合理
    2. 将位置i处的值取出
    3. 将位置i+1到结尾的元素向前移动一位
    4. length –
    int ListDelete(SQList& L, int i) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return -1;
    	}
    	if (i<1 || i>L.length) {
    		printf("数组越界\n");
    		return -1;
    	}
    	int val = L.elem[i];
    	if (i == L.length)
    		L.length--;
    	else
    	{
    		//元素往前移
    		for (; i < L.length; i++)
    			L.elem[i] = L.elem[i + 1];
    		L.length--;
    	}
    	return val;
    }
    

    二、删除值为val的第一个元素,没有返回-1

    int ListDelete_Sq(SQList& L, int val) {
    	//找到元素在的位置
    	int i = 1;
    	while (i <= L.length && val != L.elem[i])
    		i++;
    	//分情况删除
    	if (i == L.length)
    		L.length--;
    	else if (i < L.length) {
    		//元素前移
    		for (; i < L.length; ++i)
    			L.elem[i] = L.elem[i + 1];
    		L.length--;
    	}
    	else
    	{
    		printf("要删除的数据元素不存在\n");
    		return -1;
    	}
    }
    

    三、在非递减有序的有序表中删除多余的相同元素

    基本思路是:

    因为是有序的所有相同元素一定是相邻的,所有只要依次比较相邻的元素,删去相同的。

    void Listdelete_Sq(SQList& L) {
    	int i = 1;
    	while (i < L.length) {
    		if (L.elem[i] != L.elem[i + 1])i++;
    		else { //删除 第i+1个元素
    			if (i == L.length - 1)
    				L.length--;
    			else {
    				for (int j = i + 1; j < L.length; j++)
    					L.elem[j] = L.elem[j + 1];//删除第i个元素
    				L.length--;//长度减一
    			}
    		}
    	}
    }
    

    其余操作

    一、将线性表中的所有元素转置

    void reverse_Sq(SQList& L) {
    	int i = 1, j = L.length;
    	while (i < j)
    	{
    		int temp = L.elem[i];
    		L.elem[i] = L.elem[j];
    		L.elem[j] = temp;
    		i++, j--;
    	}
    }
    

    二、两个有序的顺序表合并后任然有序

    思路是:

    取出第一个边和第二个表中最小的数据,两者比较,将最小的插入到第三个表中,重复上述步骤。直到有一个表为空。然后继续将不为空的表中的元素依次插入到第三个表中。

    SQList MergeList_Sq(SQList La, SQList Lb) {
    	SQList Lc;
    	Lc.listsize = Lc.length = La.length + Lb.length;
    	Lc.elem = (int*)malloc(Lc.listsize * sizeof(int));
    	int i, j, k;
    	i = j = k = 1;
    	while (i <= La.length && j <= Lb.length) {
    		if (La.elem[i] <= Lb.elem[j])Lc.elem[k++] = La.elem[i++];
    		else
    			Lc.elem[k++] = Lb.elem[j++];
    	}
    	while(i<=La.length)
    		Lc.elem[k++] = La.elem[i++];
    	while(j<=Lb.length)
    		Lc.elem[k++] = Lb.elem[j++];
    	return Lc;
    }
    

    完整代码

    #include<stdio.h>
    #include<malloc.h>
    
    #define LIST_MAX_SIZE 100  //线性表的最大长度
    #define LISTINCREMENT 10  //线性表一次增加的量
    
    typedef struct {
    	int* elem; //指向存放线性表数据元素的基地址
    	int length; //线性表当前长度(当前存储的元素个数)
    	int listsize; // 当前分配的存储容量
    }SQList;
    
    //创建一个线性表 
    //注意点是:如果无法分配空间,打印提示,并直接返回
    void CreateList(SQList &L)
    {
    	L.elem = (int *)malloc(LIST_MAX_SIZE * sizeof(int));
    	if (!L.elem) {
    		printf("分配地址出错\n");
    		return;
    	}
    	L.length = 0;
    	L.listsize = LIST_MAX_SIZE;
    }
    
    //求线性表中的元素个数
    int ListLength(SQList L) {
    	return L.length;
    }
    
    //增加容量 
    void increte_List(SQList& L) {
    	//在原来基础上扩大
    	int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
    	if (!newbase) {
    		printf("分配空间错误\n");
    		return;
    	}
    	L.elem = newbase; //获得新基址
    	L.listsize += LISTINCREMENT;//更新容量
    }
    
    /* 查找操作*/
    //一、按值查找,找到返回对应的下标,没有则返回-1。如果有多个返回第一个的位置
    //条件:1、线性表存在;2、线性表中有元素
    
    int ListLocate(SQList L, int e) {
    	if (!L.elem ) {
    		printf("线性表没有初始化\n");
    		return -1;
    	}
    	if (L.length == 0) {
    		printf("线性表中没有元素\n");
    		return -1;
    	}
    	int i = 1;
    	//下标是从1开始存储元素的
    	while (i <= L.length && e != L.elem[i])
    		i++;
    	if (i <= L.length) {
    		printf("元素已经找到\n");
    		return i;
    	}
    	else {
    		printf("线性表中没有该元素\n");
    		return -1;
    	}
    }
    
    //二、按照下标返回元素
    //条件:1、线性表存在;2、下表没有越界
    
    int GetList(SQList L,int i) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return -1;
    	}
    	if (i<1 || i>L.length) {
    		printf("数组下标越界\n");
    		return -1;
    	}
    	return L.elem[i];
    }
    
    /* 插入元素*/
    //一、在线性表尾部添加元素
    //条件:线性表存在
    void ListPush(SQList& L,int val) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return ;
    	}
    	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
    		increte_List(L);
    	//在尾部插入
    	L.elem[++L.length] = val;
    }
    
    //二、在位置i处插入元素
    void ListInsert(SQList& L, int i, int val) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return;
    	}
    	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
    		increte_List(L);
    	for (int j = L.length; j >= i; --j) {
    		L.elem[j + 1] = L.elem[j]; //i后面的元素后移
    	}
    	//插入元素
    	L.elem[i] = val;
    	L.length++;
    }
    
    //三、顺序表(有序)插入,(如都是由小到大)
    void ListInsertorder(SQList& L, int val) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return;
    	}
    	if (L.length == L.listsize)//当前存储空间已经满了,增加分量
    		increte_List(L);
    	//找到要插入的位置
    	int pos = L.length;
    	while (pos > 0 && val < L.elem[pos])
    		pos--;
    	//这个循坏结束后,POS对应位置元素是小于等于val的,所以可以将val插到其后边
    	for (int i = L.length; i >= pos+1; i--)
    		L.elem[i + 1] = L.elem[i];
    	//插入
    	L.elem[pos + 1] = val;
    	L.length++;
    }
    
    /* 删除操作*/
    // 一、删除位置i的元素,删除成功后,返回删除的值
    // 两种情况一个是在尾部,另一个是其余位置
    //添加 i不能越界
    int ListDelete(SQList& L, int i) {
    	if (!L.elem) {
    		printf("线性表没有初始化\n");
    		return -1;
    	}
    	if (i<1 || i>L.length) {
    		printf("数组越界\n");
    		return -1;
    	}
    	int val = L.elem[i];
    	if (i == L.length)
    		L.length--;
    	else
    	{
    		//元素往前移
    		for (; i < L.length; i++)
    			L.elem[i] = L.elem[i + 1];
    		L.length--;
    	}
    	return val;
    }
    
    //二、删除值为val的第一个元素,没有返回-1
    
    int ListDelete_Sq(SQList& L, int val) {
    	//找到元素在的位置
    	int i = 1;
    	while (i <= L.length && val != L.elem[i])
    		i++;
    	//分情况删除
    	if (i == L.length)
    		L.length--;
    	else if (i < L.length) {
    		//元素前移
    		for (; i < L.length; ++i)
    			L.elem[i] = L.elem[i + 1];
    		L.length--;
    	}
    	else
    	{
    		printf("要删除的数据元素不存在\n");
    		return -1;
    	}
    }
    
    //三、在非递减有序的有序表中删除多余的相同元素
    void Listdelete_Sq(SQList& L) {
    	int i = 1;
    	while (i < L.length) {
    		if (L.elem[i] != L.elem[i + 1])i++;
    		else { //删除 第i+1个元素
    			if (i == L.length - 1)
    				L.length--;
    			else {
    				for (int j = i + 1; j < L.length; j++)
    					L.elem[j] = L.elem[j + 1];//删除第i个元素
    				L.length--;//长度减一
    			}
    		}
    	}
    }
    
    /*其余操作*/
    //一、将线性表中的所有元素转置
    
    void reverse_Sq(SQList& L) {
    	int i = 1, j = L.length;
    	while (i < j)
    	{
    		int temp = L.elem[i];
    		L.elem[i] = L.elem[j];
    		L.elem[j] = temp;
    		i++, j--;
    	}
    }
    
    //二、两个有序的顺序表合并后任然有序
    SQList MergeList_Sq(SQList La, SQList Lb) {
    	SQList Lc;
    	Lc.listsize = Lc.length = La.length + Lb.length;
    	Lc.elem = (int*)malloc(Lc.listsize * sizeof(int));
    	int i, j, k;
    	i = j = k = 1;
    	while (i <= La.length && j <= Lb.length) {
    		if (La.elem[i] <= Lb.elem[j])Lc.elem[k++] = La.elem[i++];
    		else
    			Lc.elem[k++] = Lb.elem[j++];
    	}
    	while(i<=La.length)
    		Lc.elem[k++] = La.elem[i++];
    	while(j<=Lb.length)
    		Lc.elem[k++] = Lb.elem[j++];
    	return Lc;
    }
    
    void show(SQList L)
    {
    	for (int i = 1; i <= L.length; ++i)
    		printf("%d ", L.elem[i]);
    	printf("\n");
    }
    
    int main()
    {
    	SQList La, Lb,Lc;
    	CreateList(La);
    	CreateList(Lb);
    	for (int i = 1; i <= 5; ++i)
    	{
    		int x;
    		scanf_s("%d", &x);
    		ListPush(La, x);
    	}
    	for (int i = 1; i <= 5; ++i)
    	{
    		int x;
    		scanf_s("%d", &x);
    		ListPush(Lb, x);
    	}
    	show(La), show(Lb);
    	reverse_Sq(Lb);
    	show(Lb);
    	Lc = MergeList_Sq(La, Lb);
    	show(Lc);
    	return 0;
    }
    
    
    
    
    

    链式储存

    存储结构

    typedef struct LNode {
    	int date;
    	LNode* next;
    }LNode;
    

    建立链表

    一、尾插法建立

    ,需要建立三个指针,一个指向头指针,一个始终指向尾部,一个指向新建立的

    基本思路是:

    为头节点申请空间后,让s也指向头结点。然后为p申请空间并赋值,将s的下一个指针指向p,然后指针s后移。(即将p赋给s),重复这个步骤

    LNode* create_E(int n) {
    	LNode* head, * s,*p;
    	head = (LNode *)malloc(sizeof(LNode));
    	head->next = NULL;
    	s = head;
    	while (n--) {
    		p = (LNode*)malloc(sizeof(LNode));
    		scanf_s("%d", &p->date);
    		s->next = p; //把新节点插入链表的结尾
    		s = p; //指针s后移
    	}
    	s->next = NULL;
    	return head;
    }
    

    二、头插法建立

    核心思路:

    在头结点后插入新节点。理解好这句。
    我们要在头结点后边插入新节点,要什么做呢?首先是将原本头结点的next放到新建立的节点的next把,然后再讲头结点的next指向p。

    //只需要两个指针
    LNode* create_H(int n) {  //得到的链表与输入的值相反
    	LNode* head, * p;
    	head = (LNode*)malloc(sizeof(LNode));
    	head->next = NULL;
    	while (n--) {
    		p = (LNode*)malloc(sizeof(LNode));
    		scanf_s("%d", &p->date);
    		p->next = head->next; //在头结点后插入新节点
    		head->next = p;
    	}
    	return head;
    }
    

    查找位置i的两种方法

    1、在i满足1<=i<=length 的情况下一直往后移动i次就可以了。

    LNode* p = head->next;
    	int len = GetLength(head);
    	if (i > len||i<1) {
    		printf("i值不合理\n");
    		return -1;
    	}
    	while (--i) {
    		p = p->next;
    	}
    

    因为在这里 p初值是 head->next 所以只要移动i-1次就到位置i了,所以是while(–i),如果是p初值是 head,则是 i–

    2、

    LNode* p, * s;
    	p = head; //赋值是头结点,不是next
    	int j = 0;
    	while (p && j < i ) { //找第i个位置
    		p = p->next;
    		j++;
    	}
    	if (!p || j > i) //对应的情况是i超过长度,与i小于0
    	{
    		printf("i不合理\n");
    		return;
    	}
    

    链表的查找操作

    一、在链表中查找第i的节点

    //需要检测 i的值是否合理
    
    int GetElem(LNode* head,int i) {
    	LNode* p = head->next;
    	int len = GetLength(head);
    	if (i > len||i<1) {
    		printf("i值不合理\n");
    		return -1;
    	}
    	while (--i) {
    		p = p->next;
    	}
    	return p->date;
    }
    

    二、在单链表中按值查找第一个与val相等的节点

    int LocateElem(LNode* head,int val) {
    	int i = 1;
    	LNode* p = head->next;
    	if (!p)
    	{
    		printf("当前链表为空\n");
    		return -1;
    	}
    	while (p && p->date != val) {
    		p = p->next;
    		i++;
    	}
    	//printf("位置i为:%d", i);
    	if (i > GetLength(head))
    	{
    		printf("当前链表中没有该值\n");
    		return -1;
    	}
    	else
    		return i;
    
    }
    

    三、查找与val值相等的节点个数

    int findnum(LNode* head,int val) {
    	LNode* p = head->next;
    	int num = 0;
    	while (p) {
    		if (p->date == val)
    			num++;
    		p = p->next;
    	}
    	return num;
    }
    

    四、找链表中的最大值与最小值

    
    void find_max_min(LNode* head) {
    	LNode* p = head->next;
    	int Max = p->date, Min = p->date;
    	while (p) {
    		if (p->date > Max)
    			Max = p->date;
    		else
    			Min = p->date;
    		p = p->next;
    	}
    	printf("最大值是:%d  最小值是:%d\n", Max, Min);
    }
    

    插入操作

    一、在位置i前插入数据val

    void ListInsert_P(LNode* head, int i, int val) {
    	LNode* p, * s;
    	p = head; //赋值是头结点,不是next
    	int j = 0;
    	while (p && j < i - 1) { //找第i-1个位置
    		p = p->next;
    		j++;
    	}
    	if (!p || j > i - 1) //对应的情况是i超过长度,与i小于1
    		return;
    	else
    	{
    		s = (LNode*)malloc(sizeof(LNode));
    		s->date = val;
    		s->next = p->next;
    		p->next = s;
    	}
    }
    

    二、在位置i后插入数据val

    //第0个就是在头结点后边
    void ListInsert_N(LNode* head, int i, int val) {
    	LNode* p, * s;
    	p = head; //赋值是头结点,不是next
    	int j = 0;
    	while (p && j < i ) { //找第i个位置
    		p = p->next;
    		j++;
    	}
    	//printf("j: %d\n", j);
    	if (!p || j > i) //对应的情况是i超过长度,与i小于0
    	{
    		printf("i不合理\n");
    		return;
    	}
    	else
    	{
    		s = (LNode*)malloc(sizeof(LNode));
    		s->date = val;
    		s->next = p->next;
    		p->next = s;
    	}
    }
    

    三、在第一个值为val的后边添加值val1

    void ListInsert_V(LNode* head, int val, int val1) {
    	int i = LocateElem(head, val);//找到值val对应的位置
    	//printf("位置i为:%d", i);
    	ListInsert_N(head, i, val1);
    }
    

    删除操作

    int ListDelete(LNode* head, int i) {
    	LNode* p, * q;
    	int val;
    	p = head;
    	int j = 0;
    	while (p->next && j > i - 1) {
    		p = p->next;
    		j++;
    	}
    	if (!p->next || j > i - 1)
    		return -1;
    	else
    	{
    		q = p->next;
    		p->next = q->next;
    		val = q->date;
    		free(q);//释放删除的节点
    	}
    	return val;
    }
    

    链表逆置

    void List_reverse(LNode* head) {
    	LNode* p, * pre,*temp;
    	pre = NULL;
    	p = head->next;
    	while (p) {
    		temp = p->next;
    		p->next = pre;
    		pre = p;
    		p = temp;
    	}
    	head->next = pre; //pre指向的是原来链表的终点
    }
    

    合并两个有序表

    LNode* MargeList(LNode* head1, LNode* head2) {
    	LNode* Lc,*La,*Lb,*head;
    	head = (LNode*)malloc(sizeof(LNode));
    	head->next = NULL;
    	Lc = head;
    	La = head1->next;
    	Lb = head2->next;
    	while (La && Lb) {
    		if (La->date <= Lb->date)
    		{
    			Lc->next = La;
    			Lc = La;  //记得后移
    			La = La->next;
    
    		}
    		else
    		{
    			Lc->next = Lb;
    			Lc = Lb;
    			Lb = Lb->next;
    		}
    	}
    	Lc->next = La ? La : Lb;
    	return head;
    }
    

    完整代码

    #include<stdio.h>
    #include<malloc.h>
    
    
    typedef struct LNode {
    	int date;
    	LNode* next;
    }LNode;
    
    /* 建立链表*/
    //一、尾插法建立,需要建立三个指针
    //一个指向头指针,一个始终指向尾部,一个指向新建立的
    LNode* create_E(int n) {
    	LNode* head, * s,*p;
    	head = (LNode *)malloc(sizeof(LNode));
    	head->next = NULL;
    	s = head;
    	while (n--) {
    		p = (LNode*)malloc(sizeof(LNode));
    		scanf_s("%d", &p->date);
    		s->next = p; //把新节点插入链表的结尾
    		s = p; //指针s后移
    	}
    	s->next = NULL;
    	return head;
    }
    
    //二、头插法建立 
    //只需要两个指针
    LNode* create_H(int n) {  //得到的链表与输入的值相反
    	LNode* head, * p;
    	head = (LNode*)malloc(sizeof(LNode));
    	head->next = NULL;
    	while (n--) {
    		p = (LNode*)malloc(sizeof(LNode));
    		scanf_s("%d", &p->date);
    		p->next = head->next; //在头结点后插入新节点
    		head->next = p;
    	}
    	return head;
    }
    
    /*求链表的长度*/
    int GetLength(LNode* head) {
    	LNode* p = head->next;
    	int len = 0;
    	while (p) {
    		p = p->next;
    		len++;
    	}
    	return len;
    }
    
    
    /*链表的查找*/
    //一、在链表中查找第i的节点
    //需要检测 i的值是否合理
    
    int GetElem(LNode* head,int i) {
    	LNode* p = head->next;
    	int len = GetLength(head);
    	if (i > len||i<1) {
    		printf("i值不合理\n");
    		return -1;
    	}
    	while (--i) {
    		p = p->next;
    	}
    	return p->date;
    }
    
    //二、在单链表中按值查找第一个与val相等的节点
    int LocateElem(LNode* head,int val) {
    	int i = 1;
    	LNode* p = head->next;
    	if (!p)
    	{
    		printf("当前链表为空\n");
    		return -1;
    	}
    	while (p && p->date != val) {
    		p = p->next;
    		i++;
    	}
    	//printf("位置i为:%d", i);
    	if (i > GetLength(head))
    	{
    		printf("当前链表中没有该值\n");
    		return -1;
    	}
    	else
    		return i;
    
    }
    // 三、查找与val值相等的节点个数
    int findnum(LNode* head,int val) {
    	LNode* p = head->next;
    	int num = 0;
    	while (p) {
    		if (p->date == val)
    			num++;
    		p = p->next;
    	}
    	return num;
    }
    
    //四、找链表中的最大值与最小值
    void find_max_min(LNode* head) {
    	LNode* p = head->next;
    	int Max = p->date, Min = p->date;
    	while (p) {
    		if (p->date > Max)
    			Max = p->date;
    		else
    			Min = p->date;
    		p = p->next;
    	}
    	printf("最大值是:%d  最小值是:%d\n", Max, Min);
    }
    
    /*插入操作*/
    //一、在位置i前插入数据val
    
    void ListInsert_P(LNode* head, int i, int val) {
    	LNode* p, * s;
    	p = head; //赋值是头结点,不是next
    	int j = 0;
    	while (p && j < i - 1) { //找第i-1个位置
    		p = p->next;
    		j++;
    	}
    	if (!p || j > i - 1) //对应的情况是i超过长度,与i小于1
    		return;
    	else
    	{
    		s = (LNode*)malloc(sizeof(LNode));
    		s->date = val;
    		s->next = p->next;
    		p->next = s;
    	}
    }
    
    //二、在位置i后插入数据val
    //第0个就是在头结点后边
    void ListInsert_N(LNode* head, int i, int val) {
    	LNode* p, * s;
    	p = head; //赋值是头结点,不是next
    	int j = 0;
    	while (p && j < i ) { //找第i个位置
    		p = p->next;
    		j++;
    	}
    	//printf("j: %d\n", j);
    	if (!p || j > i) //对应的情况是i超过长度,与i小于0
    	{
    		printf("i不合理\n");
    		return;
    	}
    	else
    	{
    		s = (LNode*)malloc(sizeof(LNode));
    		s->date = val;
    		s->next = p->next;
    		p->next = s;
    	}
    }
    
    //三、在第一个值为val的后边添加值val1
    void ListInsert_V(LNode* head, int val, int val1) {
    	int i = LocateElem(head, val);//找到值val对应的位置
    	//printf("位置i为:%d", i);
    	ListInsert_N(head, i, val1);
    }
    
    /*删除操作*/
    //一、删除位置i的节点,并返回删除节点的值
    
    int ListDelete(LNode* head, int i) {
    	LNode* p, * q;
    	int val;
    	p = head;
    	int j = 0;
    	while (p->next && j > i - 1) {
    		p = p->next;
    		j++;
    	}
    	if (!p->next || j > i - 1)
    		return -1;
    	else
    	{
    		q = p->next;
    		p->next = q->next;
    		val = q->date;
    		free(q);//释放删除的节点
    	}
    	return val;
    }
    
    /*链表逆置*/
    void List_reverse(LNode* head) {
    	LNode* p, * pre,*temp;
    	pre = NULL;
    	p = head->next;
    	while (p) {
    		temp = p->next;
    		p->next = pre;
    		pre = p;
    		p = temp;
    	}
    	head->next = pre; //pre指向的是原来链表的终点
    }
    
    /*合并两个有序表*/
    LNode* MargeList(LNode* head1, LNode* head2) {
    	LNode* Lc,*La,*Lb,*head;
    	head = (LNode*)malloc(sizeof(LNode));
    	head->next = NULL;
    	Lc = head;
    	La = head1->next;
    	Lb = head2->next;
    	while (La && Lb) {
    		if (La->date <= Lb->date)
    		{
    			Lc->next = La;
    			Lc = La;  //记得后移
    			La = La->next;
    
    		}
    		else
    		{
    			Lc->next = Lb;
    			Lc = Lb;
    			Lb = Lb->next;
    		}
    	}
    	Lc->next = La ? La : Lb;
    	return head;
    }
    
    void show(LNode* head) {
    	LNode* p = head->next;
    	while (p) {
    		printf("%d ", p->date);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    int main() {
    	LNode* head1,*head2,*head;
    	head1 = create_E(5);
    	show(head1);
    	/*head2 = create_H(5);
    	show(head2);
    	List_reverse(head2);
    	show(head2);
    	head = MargeList(head1, head2);
    	show(head);*/
    	ListInsert_V(head1, 3, 8);
    	show(head1);
    	ListInsert_P(head1, 3, 47);
    	show(head1);
    	return 0;
    }
    

    循环链表

    • 简单来说就是将原本最后一个结点的指针域由空指针指向头结点。
    • 最后一个结点的语句是:p->next == head
    /* 创建循环链表(返回尾指针)*/
    
    LNode* circular(int n) {
    	LNode* head, * s, * p,*tail;
    	head = (LNode*)malloc(sizeof(LNode));//为头结点申请空间
    	head->next = NULL;
    	s = head;
    	while (n--) {
    		p = (LNode*)malloc(sizeof(LNode));
    		scanf_s("%d", &p->date);
    		s->next = p; //把新节点插入链表的结尾
    		s = p; //指针s后移
    	}
    	s->next = head;//建立循环
    	tail = s;
    	return tail;
    }
    
    /*打印循环链表*/
    void show_cir(LNode* tail) {
    	LNode* head = tail->next;
    	LNode* p = tail->next->next;
    	while (p != head) {
    		printf("%d ", p->date);
    		p = p->next;
    	}
    	printf("\n");
    }
    

    双向链表

    储存结构

    /*双向链表*/
    typedef struct Node {
    	int date;
    	Node* prior;
    	Node* next;
    }DuLinkList;
    

    建立双向链表

    /*建立双向链表*/
    DuLinkList* create_DuL(int n) {
    	DuLinkList* head, * p, * s;
    	head = (DuLinkList*)malloc(sizeof(DuLinkList));
    	head->next = NULL;
    	head->prior = NULL;
    	s = head;
    	while (n--) {
    		p = (DuLinkList*)malloc(sizeof(DuLinkList));
    		scanf_s("%d", &p->date);
    		s->next = p;
    		p->prior = s;
    		s = p;
    	}
    	s->next = NULL;
    	return head;
    }
    

    插入操作

    /*双向链表的插入操作*/
    void ListInsert_DuL(DuLinkList* head, int i, int val) {
    	int len = Get_num(head);
    	if (i<1 || i>len)
    	{
    		printf("i不合法\n");
    		return;
    	}
    	DuLinkList* p ,*s;
    	s = (DuLinkList*)malloc(sizeof(DuLinkList));
    	s->date = val;
    	p = head;
    	while (--i)//i-- 得到的是位置i的结点,
    		p = p->next;
    	//printf("p = %d\n", p->date);
    	//循环结束后p指向的是i的前一个结点
    	s->next = p->next;
    	p->next->prior = s;
    	p->next = s;
    	s->prior = p;
    }
    

    删除操作

    
    /*双向链表的删除操作*/
    int ListDelete_DuL(DuLinkList* head, int i) {
    	int len = Get_num(head);
    	if (i<1 || i>len)
    	{
    		printf("i不合法\n");
    		return -1;
    	}
    	DuLinkList* p;
    	p = head;
    	while (--i)
    		p = p->next;
    	//printf("p = %d\n", p->date);
    	//循环结束后p指向的是i的前一个结点
    	p = p->next; //为了简便指向位置i的结点
    	int val = p->date;
    	p->prior->next = p->next;
    	p->next->prior = p->prior;
    	free(p);
    	return val;
    }
    

    其余操作

    /*双向链表中结点个数(存有数据的)*/
    int Get_num(DuLinkList* head) {
    	DuLinkList* p = head->next;
    	int num = 0;
    	while (p != NULL) {
    		p = p->next;
    		num++;
    	}
    	//printf("num = %d\n", num);
    	return num;
    }
    
    void show_DuL(DuLinkList* head) {
    	DuLinkList* p = head->next;
    	while (p) {
    		printf("%d ", p->date);
    		p = p->next;
    	}
    	printf("\n");
    }
    

    在这里插入图片描述

    展开全文
  • 一、线性表的定义 线性表是一种最常用也是最简单的数据结构。简单来讲,一个线性表是n个数据元素的有限排列,在不同情况下,每个数据元素有着不同的含义。 二、线性表的组成 一个线性表的结构体由三部分组成:1....
  • c语言实现线性表

    2022-04-01 18:13:26
    线性表类型: 线性表的初始化: 线性表的尾插法: 线性表的打印 线性表检查增容 线性表尾删法 线性表的头插法 线性表的头删法 线性表的删除 指定位置插入 查找数据 ...
  • C语言创建线性表

    千次阅读 2019-09-20 22:30:55
    在VS2019中创建的,结构体里定义了默认的构造函数(不清楚这算不算C++的语法),线性表的长度是动态分配的。 Incream_List 线性表扩容函数 ListInsert 插入数据函数 ListInit 初始化时输入一批数据 ListDelete 删除...
  • 线性表创建(C)

    2021-05-24 02:43:28
    main.c#define _CRT_SECURE_NO_WARNINGS#include "header.h"#... //建立线性表InitList_Sq(&LA);//初始化线性表。。。。。。。。。。。。。。。。。//添加自己的程序代码while (1);}header.h#include #inc...
  • c语言线性表

    2021-05-22 09:22:59
    线性表线性表:零个或多个数据元素的有限序列。注意:1线性表有序元素之间有序列。若元素存在多个,则第一个无前驱,最后一个无后驱,其他元素仅有一个前驱和后驱。2.线性表有限数列之内的数据有限。无限的数列只...
  • 1.第一步定义线性表结构typedef struct {ElementType data[MaxSize];int length;}Lineartable;2.第二步线性表初始化//初始化线性表Lineartable* INITAL(){Lineartable *lineartable;lineartable = (Lineartable *)...
  • C语言线性表

    2021-11-07 18:51:17
    线性表 #include <stdio.h> #include <stdlib.h> #define LIST_INIT_SIZE 100 //线性表存储空间的初始分量 #define LISTINCREMENT 10 //线性表存储空间增量(当存储空间不够时使用) typedef int ...
  • 适合c语言数据结构初学者
  • c语言线性表实现电话簿(学生信息)

    千次阅读 多人点赞 2019-09-30 16:13:34
    c语言线性表实现电话簿 #include<stdio.h> #include<string.h> #include<stdlib.h> #define LIST_INIT_SIZE 10 typedef struct Student{ char num[20],name[20]; float score; }Student; ...
  • c语言 线性表

    2022-02-03 21:26:52
    线性表创建 数据插入与删除 链表与线性表的对比
  • #define MAXSIZE 100//线性表的最大长度 typedef struct { int *elem; int length;//线性表的当前长度 //int maxlength;//线性表的最大长度 }SqList; SqList q; int i,k; //初始化函数 void initSqList...
  • 生成线性表,完成线性表的顺序表示和实现,实现线性表创建、插入、删除和查找、清空、释放等操作
  • C语言实现线性表

    千次阅读 2020-05-25 20:45:29
    (1)掌握线性表的顺序存储结构 (2)熟练使用顺序存储结构和实现线性表的操作 (3)能熟练掌握顺序存储结构中算法的实现 二:实验内容 (1)建立顺序结构的线性表 (2)实现顺序表的插入、删除、查找、输出等基本操作 三:...
  • 线性表的基本操作(C语言实现)

    千次阅读 2021-11-25 15:51:05
    文章目录这里使用的工具是DEV C++可以借鉴一下实现效果顺序存储...2.创建线性表时,数据从键盘输入整形数据 3.线性表类型定义和或各种操作的实现,可以用教材给出的方法,也可以自己设计。 实现效果 顺序存储代码实现
  • 定义线性表结构 typedef struct SQLIST { int *list; int len; int maxlen; }L; 创建表 L* creatlist(int maxlen) { L *sqlist= (L*)malloc(sizeof(L)); if (sqlist != NULL) { sqlist->list = (int...
  • C语言线性表总结

    2020-09-20 09:06:54
    C语言线性表顺序存储结构地址计算方法插入与删除优缺点链式存储结构单链表静态链表循环链表双向链表优缺点 顺序存储结构 地址计算方法 结构代码 #define MAXSIZE 20 //分配起始储存空间大小 typedef int ElemType //...
  • 线性表:零个或多个数据元素的有限序列 强调几点: 首先它是一个序列。也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他都有一个前驱和后继。 其次线性表强调是有限...
  • 创建链表 /*2.获取链表长度 /*3.向指定位置插入链表,成功返回1,否则返回0 /*4.删除链表的某个节点 /*5.输出链表 /*6.判断链表是否为空,不空返回1,否则返回0 */ #include #include #define ElementType ...
  • 声明部分: #include <stdio.h> #include <stdlib.h> #define INIT_SIZE 1 #define BOLCK_SIZE 10 typedef struct ... //创建线性表 void DestoryList(SqList *L); //销毁线性表 void Inc
  • 数据结构(C语言)——线性表(定义,基本操作)一、 线性表的定义二、线性表的基本操作什么时候要传入引用“==&==”————对参数的修改结果需要“==带回来==”为什么要实现数据结构的基本操作? 一、 线性表...
  • c语言线性表的链式表示和实现

    千次阅读 多人点赞 2016-12-26 15:36:49
    /*线性表的链式存储实现*/ #include #include #include typedef struct node{ int data; struct node *next; }Node,*pNode; //创建一个带头节点的空单链表 pNode CreateListHead(void){ pNode L =
  • C语言线性表之顺序表的13种函数操作

    千次阅读 多人点赞 2019-01-19 11:28:16
    学习数据结构开始就会学到第一种数据存储结构–线性表,学习线性表时一定会先学到顺序表,顺序表...直接看一下创建一个线性表及多种操作的代码吧。 #include&lt;stdio.h&gt; #include&lt;stdlib.h&...
  • 话不多说,直接上 ...相信大家做c语言单链表或者顺序表的时候,肯定对下面这串代码一点都不陌生吧 typedef int datatype; typedef struct ListNode{ datatype data; struct ListNode *next; }; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,129
精华内容 3,651
关键字:

c语言线性表的创建

友情链接: question_test.rar