线性表

您所在的位置：网站首页 › 线性表的元素类型必须是一致的吗为什么 › 线性表

线性表

2024-07-12 01:24| 来源: 网络整理| 查看: 265

线性表：零个或多个数据元素的有限序列。

线性表元素的个数表示为n（n>=0）定义为线性表的长度，当n=0时，成为空表。

若线性表有n个元素，则从1到n-1时（从1开始，不是从0开始），其中的元素有且只有一个直接后继，当2到n时，元素有且只有一个直接前驱。

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

c语言一维数组来实现顺序存储结构。

看看线性表的顺序存储结构的代码。

#define MAXSIZE 20 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; } SqList;

先看看获取元素的操作

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; Status GetElem(SqList *L, int i, ElemType *e) { if(L->length == 0 || i < 1 || i > L->length) { return ERROR; } *e = L->data[i - 1]; return OK; }

顺序存储结构的插入和删除

Status ListInsert(SqList *L, int i, ElemType e) { if(L->length == MAXSIZE) { return ERROR; } if(i < 1 || i > L->length + 1) { return ERROR; } if(i < L->length + 1) { int k; 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; } Status ListDelete(SqList *L, int i, ElemType *e) { if(L->length == 0) { return ERROR; } if(i < 1 || i > L->length) { return ERROR; } *e = L->data[i - 1]; if(i < L->length) { int k; for(k = i; k < L->length; ++k) { L->data[k - 1] = L->data[k]; } } L->length --; return OK; }

线性表顺序存储结构和优缺点

优点：1.无须为表示表中的元素之间的逻辑关系而增加额外的存储空间。

2.可以快速地存取表中任一位置的元素。

缺点：1.插入和删除操作需要移动大量元素。

2.当线性表长度变化较大时，难以确定存储空的容量。

3.造成存储空间的“碎片”。

线性表的链式存储结构：

为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对这个数据元素来说，除了存储其本身的信息之外，还需要存储一个指示直接后继的信息。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素的存储映像，称为节点Node。

n个结点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。我们把链表中第一个结点的存储位置叫做头指针。有时为了方便会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

头指针和头结点的异同

头指针：1.头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。

2.头指针具有标识作用，所以经常用头指针冠以链表的名字。

3.无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点：1.头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可以存放链表的长度）。

2.有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了。

3.头结点不一定是链表必须要素。

struct Node { ElemType data; struct Node *next; }; typedef struct Node *LinkList;

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

单链表的读取

Status GetElem(LinkList L, int i, ElemType *e) { LinkList p = L->next; int j = 1; // 计数器 while (p && j < i) // j还没有等于i时 { p = p->next;// 让p指向下一个结点 ++j; } if(!p || j < i) { return ERROR; } *e = p->data; return OK; }

查找最坏的情况是编译n-1次。时间复杂度是O(n)。

由于单链表结构中没有定义长度，所以不能事先知道要循环多少次，因此就不方便使用for来遍历。其主要核心思想是“工作指针后移”。

单链表的插入

Status ListInsert(LinkList *L, int i, ElemType e) { int j; LinkList p, s; p = *L; j = 1; while (p && j < i)// 寻找第i - 1个结点 { p = p->next; ++j; } if(!p || j > i) { return ERROR; } s = malloc(sizeof(struct Node));// 生成新结点 s->data = e; s->next = p->next;// p的后继结点赋给s的后继结点 p->next = s;// s赋给p的后继结点 return OK; }

【本文地址】

线性表

线性表

今日新闻

推荐新闻