【C语言 | 数据结构】线性表（顺序表示、链式表示）_c语言线性表的抽象数据类型表示

一、概述

• 线性表：一种可以在任意位置进行插入和删除数据元素的操作的、由n (n≥0) 个相同类型元素a(0),a(1),a(2),a(3),…,a(n-1)组成 的线性结构。
• 线性表的数据元素a(i)（0≤i≤n-1）表示抽象数据元素。在设计时，用DataType表示该抽象数据元素的数据类型；当具体确定后，用具体数据类型取代即可 。

若在C语言中，若用char类型或int类型来具体抽象元素的数据类型，对应的语句是：

typedef int DataType;
1

或

typedef char DataType;
1

二、抽象数据类型

① 数据集合：

• 表示为a(0),a(1),a(2),a(3),…,a(n-1)，每个元素都是抽象数据类型DataType。
  ① 操作集合：
• ListInitiate(L)：初始化线性表L。
• ListLength(L)：函数返沪线性表的当前元素个数。
• ListInsert(L,i,x)：在线性表L的第i个数据元素前插入数据元素x，插入成功返回1，插入失败返回0。
• ListDelete(L,i,x)：删除线性表L的第i个数据元素，所删除的数据元素由输出参数x带回，删除成功返回1，删除失败返回0。
• ListGet(L,i,x)：取线性表L的第i个数据元素，所取的数据元素由输出参数x带回，取元素成功返回1，取元素失败返回0。

三、顺序表示、实现

• 顺序存储结构的线性表称为线性表，实现顺序表的方法是使用数组。
• 定义结构体SeqList:

typedef struct
{
	DataType list[MaxSize];		//MaxSize表示数组元素的最大个数，list表示顺序表的数数组成员
	int size;					//size表示顺序表中当前存储的数据元素个数成员，且必须满足条件size≤MaxSize
}SeqList;						//SeqList是结构体名
1
2
3
4
5

• 初始化ListInitiate(L)

void ListInitiate(Seqlist *L)	//初始化顺序表L
{
	L->size = 0;				//定义初始数据元素个数
} 
1
2
3
4

• 求当前元素个数ListLength(L)

int ListLength(Seqlist *L)		//返回顺序表L的当前数据元素个数
{
	return L.size;
}
1
2
3
4

• 插入数据元素ListInsert(L,i,x)

void ListInsert(SeqList *L,int i,DataType x)
//在顺序表L的第i（0≤i≤size）个位置前插入数据元素值
//插入成功返回1，失败返回0
{
	int j;
	if(L->size >= MaxSize)
	{
		printf("顺序表已满，无法插入！\n");
		return 0;
	}
	else if(i < 0 || i > L->size)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	else
	{
		//从后向前依次后移数据，为插入做准备
		for(j = L->size; j > i; j--)
			L->list[j] = L->list[j-1];
			L->list[i] = x;				//插入x
			L->size ++;					//元素个数加1
			return 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 删除数据元素ListDelete(L,i,x)

void ListDelete(SeqList *L,int i,DataType x)
//删除顺序表L的第i（0≤i≤size）个位置处的数据元素并保存到x中
//删除成功返回1，失败返回0
{
	int j;
	if(L->size <= 0)
	{
		printf("顺序表已空，无数据可删！\n");
		return 0;
	}
	else if(i < 0 || i > L->size-1)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	else
	{
		*x = L->list[i];				//保存删除的元素到x中
		//从前向后依次前移
		for(j = i + 1; j <= L->size-1; j++)
			L->list[j-1] = L->list[j];;
		L->size--;					//数据元素个数减1
		return 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 取数据元素ListGet(L,i,x)

int ListGet(SeqList L,int i,DataType x)
//取顺序表中第i个数据元素存于x中，成功返回1，失败返回0
{
	if(i < 0 || i > L.size-1)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	else
	{
		*x = L.list[i];
		return 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

四、链式表示、实现

1、单链表

• 单链表中，构成链表的结点只有一个指向直接后继节点的指针域。
  

• 定义单链表结点的结构体：

typedef struct
{
	DataType data;				//data域用来存放数据元素
	struct Node *next;			//next域用来存放指向下一个结点的指针
}SLNode;	
1
2
3
4
5

• 初始化：ListInitiate(SLNode **head)

void ListInitiate(SLNode **head)				//初始化
{
	*head = (SLNode *)malloc(sizeof(SLNode));	//申请头结点，由head指示其地址
	(*head)->next = NULL;						//置结束标记NULL
}
1
2
3
4
5

• 求当前数据元素个数ListLength(SLNode *head)

int ListLength(SLNode *head)
{
	SLNode *p = head;							//p指向头结点
	int size = 0;								//size初始为0
	
	while(p->next 1= NULL)						//循环计数
	{
		p = p->next;
		size++；
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 插入ListInsert(SLNode *head,int i,DataType x)

int ListInsert(SLNode *head,int i,DataType x)
//在头结点的单链表head的第i（0≤i≤size）个结点前插入一个存放数据元素x的结点
//插入成功则返回1，失败则返回0
{
	SLNode *p, *q;
	int j;
	
	p = head;
	j = -1;
	while(p->next != NULL && j < i - 1)
	//最终要指针p指向第i-1个结点
	{
		p = p->next;
		j++;
	}
	if(j != i - 1)
	{
		printf("插入元素位置参数错！");
		return 0;
	}

	q = (SLNode *)malloc(sizeof(SLNOde));		//生成新结点
	q->data = x;								//新结点数据域负值

	q->next = p->next;
	p->next = q;
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 删除ListDelete(SLNode *head, int i, DataType *x)

int ListDelete(SLNode *head, int i, DataType *x)
//删除待头结点单链表head的第i（0≤i≤size-1）个结点
//被删除结点的数据域值由x带回，删除成功则返回1，失败返回0
{
	SLNode *p, *s;
	int j;
	p = head;
	j = -1;
	while(p->next != NULL && p->next->next != NULL && j < i - 1)
	//循环结束时指针p指向第i-1个结点
	{
		p = p->next;
		j++;
	}
	if(j != i - 1)
	{
		printf("删除元素位置参数错误！")
		return 0;
	}
	
	s = p->next;					//指针s指向a(i)结点
	*x = s->data;					//把指针s所指结点的数据域值赋予x
	p->next = p->next->next;		//删除
	free(s);						//释放指针s所指结点的内存空间
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 取数据元素ListGet(SLNode *head, int i, DataType *x)

int ListGet(SLNode *head, int i, DataType *x)
{
	SLNode *p;
	int j;
	p = head;
	j = -1;
	while(p->next != NULL && j < i)
	{
		p = p->next;
		j++;
	}
	if(j != i)
	{
		printf("取元素位置参数错！");
		return 0;
	}
	*x = p->data;
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 撤销单链表Destroy(SLNode **head)

void Destroy(SLNode **head)
{
	SLNode *p, *p1;
	
	p = *head;
	while(p != NULL)
	{
		p1 = p;
		p = p->next;
		free(p1);
	}
	*head = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2、循环单链表

• 循环单链表是单链表的另一种形式，其结构特点是，链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。
  

3、双向链表

• 双向链表中，每个结点除后继指针域外还有一个前驱指针域。
• 双向链表与单链表类同，也分带头结点结构和不断带头结点结构两种，带头结点的双向链表更为常用。
• 双向链表与单链表类同，也分为循环和肺循环两种结构，循环结构的双向链表更为常用。
• 这里我们讨论带头结点的双向循环链表。
  
  双向循环链表结点结构体定义如下：

typedef struct Node
{
	DataType data;
	struct Node *next;
	struct Node *prior;
}DLNode;
1
2
3
4
5
6

初始化 ListInitiate(DLNode **head)：

void ListInitiate(DLNode **head)
{
	*head = (DLNode *)malloc(sizeof(DLNode));
	(*head)->prior = *head;		//构成前驱指针循环链表
	(*head)->next = *head;		//构成后继指针循环链表
}
1
2
3
4
5
6

插入数据元素：

int ListInsert(DLNode *head, int i, DataType x)
//在带头间带你的双向循环链表的第i（0 ≤ i ≤ size）个结点前，插入一个存放数据元素x的结点
//插入：成功返回1，插入失败返回0
{
	DLNode *p, *s;
	int j;
	p = head->next;
	j = 0;
	while(p != head && j < i)	//寻找第i个结点
	{
		p = p->next;
		j++;
	}
	
	if(j != i)
	{
		printf("插入元素位置参数出错！");
		return 0;
	}
	s = (DLNode *)malloc(sizeof(DLNode));
	s->data = x;
	s->prior->next = s;
	p->prior->next = s;
	s->next = p;
	p->prior = s;
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

删除数据元素 ListDelete(DLNode *head, int i, DataType *x)：

int ListDelete(DLNode *head, int i, DataType *x)
//删除带头结点双向循环列链表head的第i（0 ≤ i ≤ size-1）个结点，被删除结点的数据元素域值由x带回
//删除：成功返回1，失败返回0
{
	DLNode *p;
	int j;
	p = head->next;
	j = 0;
	while(p->next != head && j < i)	//寻找第i个结点
	{
		p = p->next;
		j++;
	}
	if(j!=i)
	{
		printf("删除元素位置参数出错！");
	}
	*x = p->data;				//把要删除元素的值赋给参数x
	p->prior->next = p->next;
	p->next->prior = p->prior;

	free(p);
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

求当前数据元素个数 ListLength(DLNode *head)：

int ListLength(DLNode *head)
{
	DLNode *p = head;			//p指向头结点
	int size = 0;				//size初始为0
	while(p->next != head)		//循环计数
	{
		p = p->next;
		size ++;
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11

撤销内存空间 Destory(DLNode *head)：

void Destory(DLNode *head)
{
	DLNode *p, *p1;
	int i, n =ListLength(*head);
	p = *head;
	for(int i = 0 ; i <= n ; i++)
	{
		p1 = p;
		p = p->next;
		free(p1);
	}
	*head = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13