内容纲要

一、线性表的类型定义

线性表的逻辑结构:线性表是一种线性数据结构,数据元素存在一对一的特点。是零个或多个数据元素的有序数列,记为:(a1,a2,……,an)。其中,a1 是第一个数据元素,也称为起始结点;an 是最后一个数据元素,也称为终端结点;n 为数据元素的个数,也称为表长,当n=0 时称为空表。对于元素ai 而言,ai-1称为ai 的直接前驱,ai+1称为ai 的直接后继。在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录,含有大量记录的线性表又称文件。

逻辑特征:

  1. 若至少含有一个元素,则有唯一的起始元素。
  2. 若至少还有一个元素,则有唯一的尾元素。
  3. 除了起始元素外,其他元素有且只有唯一的前驱元素。
  4. 除了尾元素外,其他元素有且只有唯一的后继元素。

线性表的顺序存储结构: 用一组地址连续的存储单元依次存储线性表的数据元素,是一种随机存储的数据结构。 LOC(i) = LOC(i-1) + l;LOC(ai)=LOC(a1)+(i-1)*l

优点缺点
无须为表示表中数据元素的关系而增加额外的存储空间(存储空间利用率高)插入和删除操作需要移动表中的大量数据元素
可以快速存取表中任意数据元素(随机存取)当线性表的长度变化较大时,难以确定表中的存储空间的容量
造成存储空间的碎片

顺序存储结构的运算

  • 初始化InitList(L)。其作用是建立一个空表L(即 建立线性表的构架,但不含任何数据元素)。
  • 销毁线性表DestroyList(L)。其作用是释放线性表L的内存空间。
  • 求线性表的长度ListLength(L)。其作用是返回线性表L的长度。
  • 求线性表中第i个元素GetElem(L,i,e)。其作用是线性表L的第i个元素。
  • 按值查找LocateElem(L,e)。若L中存在一个或多个值与x相等的元素,则其作用是返回第一个值为x的元素的逻辑序号。
  • 插入元素ListInsert(L,i,e)。其作用是在线性表L的第i个位置上增加一个以x为值的新元素
  • 删除元素ListDelete(L,i)。其作用是删除线性表L的第i个元素ai。
  • 输出元素值DispList(L)。其作用是按前后次序输出线性表L的所有元素值。

代码实现:

#include<stdio.h>
#include <malloc.h>

//-----------线性表的静态分配顺序存储结构------------
#define MaxSize 100
typedef int ElemType;   //假设顺序表中所有元素为int类型
typedef struct {
	ElemType date[MaxSize];    //存放顺序表中的元素
	int length;                //顺序表的实际长度
} SqList;                      //顺序表类型
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int status;

//----------线性表动态分配顺序存储空间结构-------
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LIST_INCREMENT 10  //线性表存储空间的分配增量
#define FALSE 0
#define TRUE 1
#define OK 1
#define ERROR 0
typedef int status;
typedef int ElemType;      //元素的数据类型
typedef struct {
	ElemType* elem;        //存储空间基址
	int length;			   //当前长度
	int listsize;          //当前分配存储容量
} SqList;

//构造一个空线性表
status InitList(SqList& L) {
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType*));
	if (!L.elem)return ERROR;//存储分配失败
	L.length = 0;//初始化表长为0
	L.listsize = LIST_INIT_SIZE;//初始化存储容量
	return OK;
}
//销毁线性表L
status DestoryList(SqList& L) {
	free(L.elem);
	L.elem = NULL;
	L.length = 0;
	L.listsize = 0;
	return OK;
}
//求线性表的长度
status ListLength(SqList& L) {
	return L.length;
}
//用e返回L中的第i个值1<=i<=ListLength(L)
status GetElem(SqList L, int i, ElemType& e) {
	if (i < 1 || i>ListLength(L))
		return ERROR;
	e = *(L.elem + i - 1);
	return OK;
}
//查找值等于e的位置i;
int LocateElem(SqList L, ElemType e) {
	ElemType* p;
	int i = 1;    //i的初值为第一个元素的位序
	p = L.elem;   //p的初值为第一个元素的存储地址
	while (i <= L.length && (*p++ != e))
		++i;
	if (i <= L.length)
		return i;
	else
		return 0;
}
//插入算法Insert平均时间复杂度O(n),表尾插入为最好情况O(1)
status ListInsert(SqList& L, int i, ElemType e) {
	//i的合法值1<=i<=L.length+1
	ElemType* p;
	if (i < 1 || i > L.length + 1)
		return ERROR;
	if (L.length >= L.listsize) {
		ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize + LIST_INCREMENT) * sizeof(ElemType));
		if (!newbase)
			return ERROR;       //存储分配失败
		L.elem = newbase;        //新基址
		L.listsize += LIST_INCREMENT;   //增加存储容量
	}
	ElemType* 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;
}
//删除算法Delete,平均时间复杂度为O(n),表尾删除不移动为最好情况O(1)
status ListDelete(SqList& L, int i, ElemType& e) {
	//i的合法值1<=i<=L.length
	ElemType* p, * q;
	if (i < 1 || i > L.length)
		return ERROR;
	p = L.elem + i - 1;//被删除位置
	e = *p;//被删除元素赋值给e
	q = L.elem + L.length - 1;//表尾元素的值
	for (++p; p <= q; ++p)
		*(p - 1) = *p;  //被删除元素之后的元素左移
	--L.length;//表长减一
	return OK;
}
//输出线性表
void DispList(SqList L) {
	int i = 1;
	for (int i = 1; i <= L.length; i++)
		printf("%d ", *(L.elem++));
	printf("\n表长:%d\t表容量:%d", L.length, L.listsize);
}

线性表的链式存储结构:n 个结点链结成一个链表,即为线性表(a1,a2,…an)的链式存储结构。结点由数据域和指针域构成。

数据域:存储数据元素信息的为数据域(data)。

指针域:存储直接后继存储位置(指针)的域为指针域或链域(next)。

单链表: 链表的每个结点只包含一个指针域。有带头结点和不带头结点两种,带头结点的可以简化运算的实现过程。

头指针:指向链表中头结点的存储位置。 头结点数据可以存储任何信息,也可不存储。

特征:

  • 每个数据元素由结点(Node)构成
  • 线性结构
  • 结点可以连续,也可以不连续存储。
  • 结点的逻辑顺序与物理顺序可以不一致。
  • 表可以扩充。
  • 链表中的第一个元素结点称为首结点;最后一个元素结点称为尾结点;其指针域为空(NULL);

带头结点单链表图示

单链表的运算

  • 初始化单链表算法InitList(LinkList &L):构造一个空的线性表L
  • 销毁单链表算法DestroyList(LinkList &L):销毁线性表L
  • 求单链表长度算法ListLength(LinkList L):返回L中数据元素个数
  • 求单链表中值为e的元素算法LocateElem(LinkList L, ElemType e):返回L中第1个与e相等的数据元素的位序。
  • 单链表的插入算法ListInsert_L(LinkList &L, int i, ElemType e):在带头结点的单链线性表L的第i个元素之前插入元素e
  • 单链表的删除算法ListDelete_L(LinkList &L, int i, ElemType &e):在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
  • 显示单链表DispList(LinkList L)

代码实现:

#include<stdio.h>
#include <malloc.h>

typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
//单链表结点的C语言描述
typedef struct node {
	ElemType data;
	struct node* next;
}LNode,*LinkList;
Status InitList(LinkList& L)
{
	L = (LinkList)malloc(sizeof(LNode));//产生头结点使L指向头结点地址
	if (!L) return ERROR;//分配失败
	L->next = NULL;//指针域为空
	return OK;
}

Status Destory(LinkList& L)
{
	LinkList p;
	while (L){
		p = L->next;
		free(L);
		L = p;
	}
	return OK;
}

int ListLength(LinkList L)
{
	int i = 0;
	LinkList p = L->next;//将p指向第一个结点
	while (p){
		i++;
		p = p->next;
	}
	return i;
}

int LocateElem(LinkList L, ElemType e)
{
	int i = 0;
	LinkList p = L->next;
	while (p){
		i++;
		if (p->data == e)
			return i;//找到元素直接return
		p = p->next;
	}
	return 0;
}

Status ListInsert_L(LinkList& L, int i, ElemType e)
{
	LinkList p, s;
	p = L;
	int j = 0;
	while (p &&j < i-1){//找到第i-1个元素
		p = p->next;
		++j;
	}
	if (j > i - 1 || !p)
		return ERROR;//i小于1或大于表长
	s = (LinkList)malloc(sizeof(LNode));//生成新结点
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

Status ListDelete_L(LinkList& L, int i, ElemType& e)
{
	LinkList p, q;
	p = L;
	int j = 0;
	while (p && j < i - 1) {//找到第i-1个结点
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i - 1)
		return ERROR;//删除位置不合理
	q = p->next;
	p->next = q->next;//删除并释放结点
	e = q->data;
	free(q);
	return OK;
}

void DispList(LinkList L)
{
	LinkList p = L->next;
	int i;
	if (p != NULL) {
		printf("\n头结点的地址为:%p\n", L);
		for (i = 1; p != NULL; i++) {
			printf("第%d个结点的值为%d,地址为%p\n", i, p->data, p);
			p = p->next;
		}
	}
}

静态链表:用数组描述的链表。

优点缺点
在插入和删除操作时,只需要移动游标,不需要移动元素。没有解决连续存储分配带来的表长难以确定问题。
改进了在顺序存储结构中需要移动大量元素的缺点。失去了顺序存储结构随机存取的特性

循环链表:是另一种形式的链式存储结构,特点是表中最后一个结点的指针域指向头结点。循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p 或p->next 是否为空,而是它们是否等于头指针。

循环链表为空表:L->next == L

表尾: p->next == L

双向链表:在前趋和后继方向都能遍历的线性链表。双向链表每个结点的结构由指向其前驱结点的指针域prior,指向其后继结点的指针域next,数据域data构成。

特性:p->prior->next == p == p->next->prior

双向循环链表的运算

  • 初始化双向循环链表InitDuLinkList(DuLinkList &L)
  • 销毁双向循环链表Destory(DuLinkList& L)
  • 双向循环链表长度算法ListLength(DuLinkList L)
  • 在L中确定第i个元素前驱的位置指针p:GetElemP(L, i – 1);
  • 求单链表中值为e的元素算法LocateElem(DuLinkList L, ElemType e):返回L中第1个与e相等的数据元素的位序。
  • 双向循环链表插入算法ListInsert(DuLinkList& L, int i, ElemType e)
  • 双向循环链表删除算法ListDelete(DuLinkList L, int i, ElemType &e)
  • 打印双向循环链表DispDuLinkList(DuLinkList L)

代码实现:

#include <stdio.h>
#include <malloc.h>

typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
//双向链表结点的C语言描述
typedef struct DuLNode {
	ElemType data;
	struct DuLNode* piror, * next;
}DuLNode, * DuLinkList;

Status InitDuLinkList(DuLinkList& L)
{
	L = (DuLinkList)malloc(sizeof(DuLNode));
	if (!L)
		return ERROR;//分配失败
	L->next = L;
	L->piror = L;
	return OK;
}

Status Destory(DuLinkList& L)
{
	DuLinkList p;
	L->piror->next = NULL;//先断链在释放
	while (L) {
		p = L->next;
		free(L);
		L = p;
	}
	return OK; 
}

int ListLength(DuLinkList L)
{
	int i = 0;
	DuLinkList p = L->next;//p指向第一个结点
	while (p != L) {//p没到表头
		i++;
		p = p->next;
	}
	return i;
}

DuLinkList GetElemP(DuLinkList L, int i)
{
	int j = 0;
	DuLinkList p = L->next;
	while (p != L) {
		++j;
		if (i == j)
			return p;
		p = p->next;
	}
	return L;//空双向链表
}

int LocateElem(DuLinkList L, ElemType e)
{
	DuLinkList p = L->next;//指向第一个结点
	int i = 0;
	while (p != L) {
		++i;
		if (p->data == e)
			return i;//找到元素直接return i
		p = p->next;
	}
	return 0;
}

Status ListInsert(DuLinkList& L, int i, ElemType e)
{
	if (i < 1 || i > ListLength(L) + 1)//1<=i<=ListLength(L)+1
		return ERROR;
	DuLinkList p, s;
	p = GetElemP(L, i - 1);//找到第i-1个元素
	if (!p)
		return ERROR;//没有找到指针P
	s = (DuLinkList)malloc(sizeof(DuLNode));
	if (!s) return ERROR;//分配失败
	s->data = e;
	s->next = p->next;
	p->next->piror = s;
	s->piror = p;
	p->next = s;
	return OK;
}

Status ListDelete(DuLinkList L, int i, ElemType& e)
{
	if (i < 1 || i > ListLength(L))
		return ERROR;//i的合法值1<=i<=ListLength(L)
	DuLinkList p;
	p = GetElemP(L, i);
	e = p->data;
	if (!p)
		return ERROR;//查找失败
	p->next->piror = p->piror;
	p->piror->next = p->next;
	free(p);
	return OK;
}

void DispLinkList(DuLinkList L)
{
	DuLinkList p = L->next;
	int i = 1;
	if (p != NULL) {
		printf("头指针的地址为%p\n", L);
		for (i = 1; p != L; i++) {
			printf("当前地址%p的第%d个元素的前驱地址为:%p,数据为%d,后驱地址为%p\n", p, i, p->piror, p->data, p->next);
			p = p->next;
		}
		printf("双向循环表长为%d\n", ListLength(L));
	}
}

最后修改日期:2020年4月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。