Java教程

数据结构—线性表

本文主要是介绍数据结构—线性表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、基本概念
    • 1.线性表的定义及特点
    • 2.存储结构
  • 二、线性表的链式存储结构
    • 1.结点
    • 2.基本操作


前言

线性表是最基础最常用的一种线性结构,同时也是其它数据结构的基础。因此,为了打好基础,学习本章的时候应明确相关概念,以免混淆。


一、基本概念

1.线性表的定义及特点

1.定义:由 n(n>=0)个数据特性相同的元素构成的有限序列被称为线性表。
2.特点:
1.集合中必存在唯一的一个"第一元素"。
2.集合中必存在唯一的一个 “最后元素” 。
3.除最后一个元素之外,均有 唯一的后继(后件)。
4.除第一个元素之外,均有 唯一的前驱(前件)。
总结:除了线性表所拥有的唯一的第一元素及最后元素,剩下元素均拥有唯一的前驱及后继。

2.存储结构

线性表主要由顺序表示或链式表示。
顺序表示 的特点:逻辑关系相邻的元素在物理位置上也相邻。查找元素快
链式表示 的特点:相比于顺序表示,链式表示不要求物理位置。插入和删除操作时,只需修改结点的下一个元素指针,但查找元素时效率不如顺序存储。好操作

二、线性表的链式存储结构

1.结点

节点由两部分组成:1.数据域 2.指针域
数据域用来存储数据,指针域用来存储下一个结点的地址。
在这里插入图片描述

2.基本操作

1.创建链表

typedef struct
{
	ElemType data[10];   /* 数组,存储数据元素 */
	int length;               /* 线性表当前长度 */
}SqList;

2.初始化链表

Status InitList(SqList *L) 
{ 
    L->length=0;
    return OK;
}

3.创建结点

Status ListInsert(SqList *L,int i,ElemType e)
{ 
	int k;
	if (L->length==10)  /* 顺序线性表已经满 */
		return ERROR;
	if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
		return ERROR;

	if (i<=L->length)        /* 若插入数据位置不在表尾 */
	{
		for(k=L->length-1;k>=i-1;k--)  /* 将要插入位置之后的数据元素向后移动一位 */
			L->data[k+1]=L->data[k];
	}
	L->data[i-1]=e;          /* 将新元素插入 */
	L->length++;

	return OK;
}

4.删除结点

Status ListInsert(SqList *L,int i,ElemType e)
{ 
	int k;
	if (L->length==MAXSIZE)  /* 顺序线性表已经满 */
		return ERROR;
	if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
		return ERROR;

	if (i<=L->length)        /* 若插入数据位置不在表尾 */
	{
		for(k=L->length-1;k>=i-1;k--)  /* 将要插入位置之后的数据元素向后移动一位 */
			L->data[k+1]=L->data[k];
	}
	L->data[i-1]=e;          /* 将新元素插入 */
	L->length++;

	return OK;
}

5.查找

int LocateElem(SqList L,ElemType e)
{
    int i;
    if (L.length==0)
            return 0;
    for(i=0;i<L.length;i++)
    {
            if (L.data[i]==e)
                    break;
    }
    if(i>=L.length)
            return 0;

    return i+1;
}


这篇关于数据结构—线性表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!