【数据结构】顺序表和链表_链式列表和顺序表

目录

1、线性表

2、顺序表

2.1 概念和结构

 3、链表

3.1 概念及结构

3.2 链表的种类

3.3 链表的实现

4、顺序表和链表的比较

1、线性表

线性表（linear list）是一种常见的数据结构，它由一组相同类型的数据元素组成，这些元素按照一定的顺序排列。因此线性表是n个具有相同特性的数据元素组成的有限序列。

常见的线性表有顺序表、链表、栈、队列、字符串等等。

线性表的常见操作包括插入、删除、查找、遍历等。插入和删除操作需要注意边界条件，查找操作可以用顺序查找或二分查找，遍历操作可以用循环或递归实现。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的。

线性表可以用数组或链表来实现。数组实现的线性表称为顺序表，链表实现的线性表称为链表。

2、顺序表

2.1 概念和结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储，同时记录表的长度和容量。在数组上完成数据的增删查改。

顺序表的特点是随机访问快，插入和删除慢，而链表的特点是随机访问慢，插入和删除快。

顺序表一般可以分为：

1.  静态顺序表：使用定长数组存储元素。

   #define MAX_SIZE 100
    
   typedef struct {
       int id;
       char name[20];
       int age;
   } Student;
    
   typedef struct {
       Student data[MAX_SIZE];//定长数组
       int length;            //有效元素个数
   } StaticTable;
   

2.  动态顺序表：使用动态开辟的数组存储。
    （是指在程序运行时才确定表的大小，表中元素的个数可以动态地改变）

   typedef struct {
       int *data;
       int length;
       int capacity;
   } DynamicTable;
   

 2.2 顺序表的实现

静态顺序表只适用于确定知道需要存多少数据的场景。如果不知道需要存多少数据，定义静态顺序表的定长数组时可能导致N定大了或者定小了，定大了浪费空间，定少了空间不够用。所以现实中基本都是使用动态顺序表，根据需要来动态地分配空间大小，所以下面我们实现动态顺序表。

#pragma once
#include <stdio.h>
#include <stdlib.h>
 
typedef int SLDateType;
 
typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity;
}SL;
 
void IntSL(SL* psl);//初始化
 
void DestorySL(SL* psl);//删除
 
void SLPushBack(SL* psl);//尾插
 
void SLPrint(SL* psl);//打印
 
void SLPopback(SL* psl);//尾删
 
void SLPushFront(SL* psl);//头插
 
void SLPopFront(SL* psl);//头删
 
void SLInsert(SL* psl, int pos);//在pos位置插入
 
void SLDelete(SL* psl, int pos);//在pos位置删除
 
int SLSearch(SL* psl);//查找

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
 
void IntSL(SL* psl)//初始化
{
	psl->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
	if (psl->a == NULL)
	{
		perror("malloc");
		return;
	}
	psl->capacity = 4;
	psl->size = 0;
}
 
void DestorySL(SL* psl)
{
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
 
void CheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity)
	{
		SLDateType* tmp = (SLDateType*)realloc(psl->a, sizeof(SLDateType) * psl->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc");
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
}
 
void SLPushBack(SL* psl)//尾插
{
	CheckCapacity(psl);
	SLDateType num = 0;
	printf("Enter a number:");
	scanf("%d", &num);
	psl->a[psl->size] = num;
	psl->size++;
}
 
void SLPrint(SL* psl)//打印
{
	if (psl->size == 0)
	{
		printf("The sequence table is empty!\n");
		return;
	}
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
		if (i % 10 == 0 && i != 0)
		{
			printf("\n");
		}
	}
	printf("\n");
}
 
void SLPopback(SL* psl)//尾删
{
	//if (psl->size == 0)
	//{
	//	printf("The sequence table is empty!\n");
	//	return;
	//}
	//psl->a[psl->size] = 0;
	//psl->size--;
	SLDelete(psl, psl->size);
}
 
void SLInsert(SL* psl, int pos)//在pos位置插入
{
	CheckCapacity(psl);
	printf("Enter the number to insert:");
	int tmp = 0;
	scanf("%d", &tmp);
	psl->size++;
	for (int i = psl->size - 1; i >= pos ; i--)
	{
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[pos - 1] = tmp;
}
 
void SLDelete(SL* psl, int pos)//在pos位置删除
{
	if (psl->size == 0)
	{
		printf("The sequence table is empty!\n");
		return;
	}
	for (int i = pos-1; i < psl->size-1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->a[psl->size - 1] = 0;
	psl->size--;
}
 
void SLPushFront(SL* psl)//头插
{
	SLInsert(psl, 1);//第一个元素
}
 
void SLPopFront(SL* psl)//头删
{
	SLDelete(psl, 1);//第一个元素
}
 
int SLSearch(SL* psl)//查找
{
	if (psl->size == 0)
	{
		printf("The sequence table is empty!\n");
		return;
	}
	printf("Enter the value to look for:");
	int tmp = 0;
	scanf("%d", &tmp);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == tmp)
		{
			printf("The value's subscript is %d\n", i);
			return i;
		}
	}
	printf("The value does not exist\n");
	return -1;
}

 3、链表

 3.1 概念及结构

链表是一种动态数据结构，它由一组节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的大小可以动态地改变，可以在表的任意位置插入或删除元素。链表的实现方式是用指针来连接节点。

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。

3.2 链表的种类

1. 单向或者双向
   
2. 带头或者不带头
   
3. 循环或者非循环
   

 以上情况组合起来就有8种链表结构，其中比较常用的是：

1. 无头单向非循环链表
   
2. 带头双向循环链表
   

 3.3 链表的实现

下面是一个用无头单向非循环链表实现的动态顺序表的例子：

//Slist.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
 
// 单链表打印
void SListPrint(SListNode* plist);
 
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
 
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
 
// 单链表的尾删
void SListPopBack(SListNode** pplist);
 
// 单链表头删
void SListPopFront(SListNode** pplist);
 
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
 
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
 
//单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
 
 // 单链表的销毁
void SListDestroy(SListNode* plist);

#define _CRT_SECURE_NO_WARNINGS 1
#include "Slist.h"
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
	if (tmp == NULL)
	{
		perror("malloc");
	}
	else
	{
		tmp->data = x;
		tmp->next = NULL;
		return tmp;
	}
}
 
// 单链表打印
void SListPrint(SListNode* plist)
{
	assert(plist);
	while (plist->data != EOF)
	{
		printf("%d ", plist->data);
		if (plist->next == NULL)
		{
			return;
		}
		else
		{
			plist = plist->next;
		}
	}
	printf("\n");
}
 
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(*pplist);
	SListNode* tmp = *pplist;
	while (tmp->next != NULL)
	{
		tmp = tmp->next;
	}
	tmp->next = BuySListNode(x);
}
 
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	if (*pplist == NULL)
	{
		SListNode* tmp = BuySListNode(x);
		*pplist = tmp;
		return;
	}
	else
	{
		SListNode* tmp = BuySListNode(x);
		tmp->next = *pplist;
		*pplist = tmp;
		return;
	}
}
 
// 单链表的尾删
void SListPopBack(SListNode** pplist) 
{
	assert(*pplist);
	SListNode* tmp = *pplist;
	SListNode* next = tmp->next;
	while (next->next != NULL)
	{
		tmp = tmp->next;
		next = next->next;
	}
	free(next);
	tmp->next = NULL;
}
 
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	SListNode* tmp = *pplist;
	*pplist = (*pplist)->next;
	free(tmp);
}
 
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	int flag = 0;
	while (plist->data != x)
	{
		if (plist->next != NULL)
		{
			plist = plist->next;
		}
		else
		{
			return NULL;
		}
	}
	return plist;
}
 
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	SListNode* tmp = BuySListNode(x);
	tmp->next = pos->next;
	pos->next = tmp;
}
 
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	SListNode* tmp = pos->next;
	pos->next = tmp->next;
	free(tmp);
}
 
 
// 单链表的销毁
void SListDestroy(SListNode* plist)
{
	assert(plist);
	if (plist->next == NULL)
	{
		free(plist);
		return;
	}
	else
	{
		SListDestroy(plist->next);
		free(plist);
		return;
	}
}

 下面是一个用带头双向循环链表实现的动态顺序表的例子：

//ddlist.h
#pragma once
 
#include <stdio.h>
#include <stdlib.h>
 
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
 
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "dllist.h"
 
// 创建返回链表的头结点
ListNode* ListCreate()
{
	ListNode* ListHead = (ListNode*)malloc(sizeof(ListNode));
	if (ListHead == NULL)
	{
		perror("malloc error");
	}
	ListHead->next = ListHead;
	ListHead->prev = ListHead;
	return ListHead;
}
 
//创建新节点
ListNode* CreatNode(LTDataType x)
{
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	if (tmp == NULL)
	{
		perror("malloc error");
	}
	tmp->data = x;
	tmp->next = NULL;
	tmp->prev = NULL;
	return tmp;
}
 
//尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	ListInsert(pHead, x);
	return;
}
 
//尾删
void ListPopBack(ListNode* pHead)
{
	ListErase(pHead->prev);
	return;
}
 
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	ListInsert(pHead->next, x);
	return;
}
 
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	ListErase(pHead->next);
}
 
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* pre = pos->prev;
	ListNode* Node = CreatNode(x);
	Node->prev = pre;
	Node->next = pos;
	pos->prev = Node;
	pre->next = Node;
	return;
}
 
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	ListNode* pre = pos->prev;
	ListNode* next = pos->next;
	pre->next = next;
	next->prev = pre;
	free(pos);
	return;
}
 
 
//打印
void ListPrint(ListNode* pHead)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d   ", cur->data);
		cur = cur->next;
	}
	printf("\n");
	return;
}
 
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		pHead->next = cur->next;
		free(cur);
		cur = pHead->next;
	}
	free(pHead);
	return;
}
 
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

4、顺序表和链表的比较