【数据结构】顺序表和链表

发布于：2025-07-08 ⋅ 阅读:(22) ⋅ 点赞:(0)

线性表

线性表是由n个具有相同特性的数据元素组成的有限序列。作为一种在实际应用中广泛使用的数据结构，常见的线性表包括顺序表、链表、栈、队列和字符串等。

线性表在逻辑上呈现线性结构，表现为一条连续的直线。然而，其物理存储结构并不要求连续，通常采用数组或链式结构来实现存储。

顺序表

1.最好用数组

2.功能：增删查改。

3.静态顺序表 ，动态顺序表。

4.源文件

#include"SeqList.h"
//初始化
void SLInit(SeqList* p, size_t capacity)
{
	assert(p);
	p->a = (SLDataType*)malloc(sizeof(SLDataType) * (INIT_CAPACITY));
	if (p->a == NULL)
	{
		perror("malloc failed");
		return 0;
	}
	p->size = 0;
	p->capacity = INIT_CAPACITY;
}
//检查容量
void CheckCapacity(SeqList* p)
{
	assert(p);
	if (p->size == p->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(p->a, sizeof(SLDataType) * ((p->capacity) * 2));
		if (tmp == NULL)
		{
			perror("realloc failed");
			return 0;
		}
		p->a = tmp;
		p->capacity *= 2;
	}
}
//尾插
void SLPushBack(SeqList* p,size_t x)
{
	assert(p);
	CheckCapacity(p);
	p->a[p->size] = (SLDataType)x;
	p->size++;
}
//尾删
void SLPopback(SeqList* p) 
{
	assert(p->size>0);
	p->a[p->size-1] = 0;
	p->size--;
}
//头插
void SLPushFront(SeqList* p,size_t x)
{
	assert(p);
	CheckCapacity(p);
	for (size_t i = p->size;i > 0;i--)
	{
		p->a[i-1] = p->a[i];
	}
	p->a[0] = x;
	p->size++;
}
//头删
void SLPopFront(SeqList* p)
{
	assert(p);

	if (p->size == 0) {
		return;
	}
	for (size_t i = 0;i < p->size-1;i++)
	{
		p->a[i] = p->a[i+1];
	}
	p->size--;
}
//查找
int SLFind(SeqList* p, size_t x)
{
	assert(p);
	for (size_t i = 0;i < p->size;i++)
	{
		if (p->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//在pos位置上插入x
void SLInsert(SeqList* p, size_t pos, size_t x)
{
	assert(p);
	assert(pos <= p->size);
	CheckCapacity(p);
	for (size_t i = pos;i < p->size;i++)
	{
		p->a[i + 1] = p->a[i];
	}
	p->a[pos] = x;
	p->size++;
}
//在pos位置删数据
void SLErase(SeqList* p, size_t pos)
{
	assert(p);
	assert(pos < p->size);
	for (size_t i = p->size;i > pos;i--)
	{
		p->a[i - 1] = p->a[i];
	}
	p->size--;
}
//销毁
void SLDestory(SeqList* p)
{
	assert(p);
	free(p->a);
	p->a = NULL;
	p->capacity = p->size = 0;
}
//打印
void SLPrint(SeqList* p)
{
	assert(p);
	for (size_t i = 0;i < p->size; i++)
	{
		printf("%d", p->a[i]);
	}
	printf("\n");
}

5.头文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#define N 100
#define INIT_CAPACITY 4
typedef int SLDataType;
//静态顺序表的储存
//typedef struct SeqList
//{
//	SLDataType a[N];
//	size_t size;
//}SeqList;
//动态顺序表的储存
typedef struct SeqList
{
	SLDataType* a;
	size_t size;
	size_t capacity;
}SeqList;
//增删查改的函数

//初始化
void SLInit(SeqList* p,size_t capacity);
//检查容量
void CheckCapacity(SeqList* p);
//尾插
void SLPushBack(SeqList* p, size_t x);
//尾删
void SLPopBack(SeqList* p);
//头插
void SLPushFront(SeqList* p ,size_t x);
//头删
void SLPopFront(SeqList* p);
//查找
int SLFind(SeqList* p, size_t x);
//在pos位置上插入x
void SLInsert(SeqList* p,size_t pos, size_t x);
//在pos位置删数据
void SLErase(SeqList* p,size_t pos);
//销毁
void SLDestory(SeqList* p);
//打印
void SLPrint(SeqList* p);

6.测试

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "SeqList.h"

void testInitAndPushBack() {
    printf("=== 测试初始化和尾插 ===\n");
    SeqList list;
    SLInit(&list, 2);

    SLPushBack(&list, 10);
    SLPushBack(&list, 20);
    SLPushBack(&list, 30);  // 测试扩容

    printf("尾插后元素: ");
    SLPrint(&list);  // 应输出: 10 20 30
    printf("容量: %zu, 大小: %zu\n", list.capacity, list.size);  // 应输出: 容量: 4, 大小: 3

    SLDestory(&list);
}

void testPushAndPopFront() {
    printf("\n=== 测试头插和头删 ===\n");
    SeqList list;
    SLInit(&list, 2);

    SLPushFront(&list, 10);
    SLPushFront(&list, 20);
    SLPushFront(&list, 30);  // 测试扩容

    printf("头插后元素: ");
    SLPrint(&list);  // 应输出: 30 20 10

    SLPopFront(&list);
    printf("头删后元素: ");
    SLPrint(&list);  // 应输出: 20 10

    SLDestory(&list);
}

void testInsertAndErase() {
    printf("\n=== 测试指定位置插入和删除 ===\n");
    SeqList list;
    SLInit(&list, 5);

    SLPushBack(&list, 10);
    SLPushBack(&list, 20);
    SLPushBack(&list, 30);

    SLInsert(&list, 1, 15);  // 在位置1插入15
    printf("插入后元素: ");
    SLPrint(&list);  // 应输出: 10 15 20 30

    SLErase(&list, 2);  // 删除位置2的元素
    printf("删除后元素: ");
    SLPrint(&list);  // 应输出: 10 15 30

    SLDestory(&list);
}

void testFind() {
    printf("\n=== 测试查找功能 ===\n");
    SeqList list;
    SLInit(&list, 5);

    SLPushBack(&list, 10);
    SLPushBack(&list, 20);
    SLPushBack(&list, 30);

    int pos = SLFind(&list, 20);
    printf("查找20的位置: %d\n", pos);  // 应输出: 1

    pos = SLFind(&list, 50);
    printf("查找50的位置: %d\n", pos);  // 应输出: -1

    SLDestory(&list);
}

int main() {
    testInitAndPushBack();
    testPushAndPopFront();
    testInsertAndErase();
    testFind();

    printf("\n=== 测试空表操作 ===\n");
    SeqList empty;
    SLInit(&empty, 1);

    printf("空表删除测试:\n");
    // SLPopFront(&empty);  // 取消注释此行会触发断言，验证空表保护机制

    SLDestory(&empty);

    printf("\n所有测试完成！\n");
    return 0;
}

链表

概念：链表是一种物理存储上非连续、非顺序的数据结构，其数据元素的逻辑顺序是通过节点间的指针链接实现的。

1.最好用指针。

2.功能：增删查改。

2.链表类型分类：

  1. 单向/双向

  2. 带头/不带头

  3. 循环/非循环

  4. 典型链表结构分析

  5. 无头单向非循环链表：

    • 结构最简单
    • 通常不作为独立数据结构使用
    • 常见应用场景：哈希桶、图的邻接表等
    • 在笔试面试中出现频率较高

  6. 带头双向循环链表：

    • 结构最复杂
    • 主要用于独立存储数据
    • 实际应用中最常见的链表类型
    • 虽然结构复杂，但代码实现后能体现其优势
    • 实现难度反而低于预期（后续代码实现时将具体说明）
  7. 单链表
    • 头文件： 
      #pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
// 1、无头+单向+非循环链表增删查改实现
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);

      2.源文件：

      #include"SList.h"

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
// 单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}
// 单链表尾删
void SListPopBack(SListNode** pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* front = (*pplist)->next;
		free(*pplist);
		*pplist = front;
	}
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while ( cur !=NULL && cur->data !=x )
	{
		cur = cur->next;
	}
	return cur;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？:找不到前面的
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？:找不到前面的
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* nextNode = pos->next;
	if (nextNode!= NULL)
	{
		pos->next = nextNode->next;
		free(nextNode);
	}
}

      3测试：

      #include "SList.h"
#include <stdio.h>

void testSList() {
    printf("===== 测试单链表功能 =====\n");
    SListNode* list = NULL;

    // 测试尾插
    printf("\n测试尾插:\n");
    SListPushBack(&list, 10);
    SListPushBack(&list, 20);
    SListPushBack(&list, 30);
    SListPrint(list); // 预期输出: 10 20 30

    // 测试头插
    printf("\n测试头插:\n");
    SListPushFront(&list, 5);
    SListPrint(list); // 预期输出: 5 10 20 30

    // 测试查找
    printf("\n测试查找:\n");
    SListNode* pos = SListFind(list, 20);
    if (pos) {
        printf("找到值为20的节点，在其后插入50\n");
        SListInsertAfter(pos, 50);
        SListPrint(list); // 预期输出: 5 10 20 50 30
    }

    // 测试尾删
    printf("\n测试尾删:\n");
    SListPopBack(&list);
    SListPrint(list); // 预期输出: 5 10 20 50

    // 测试头删
    printf("\n测试头删:\n");
    SListPopFront(&list);
    SListPrint(list); // 预期输出: 10 20 50

    // 测试删除pos之后的节点
    printf("\n测试删除pos之后的节点:\n");
    pos = SListFind(list, 20);
    if (pos) {
        SListEraseAfter(pos);
        SListPrint(list); // 预期输出: 10 20
    }

    // 测试空链表操作
    printf("\n测试空链表操作:\n");
    SListNode* emptyList = NULL;
    SListPrint(emptyList); // 预期输出: 空行
    SListPopBack(&emptyList); // 应无错误
    SListPopFront(&emptyList); // 应无错误

    // 测试单个节点操作
    printf("\n测试单个节点操作:\n");
    SListNode* singleList = NULL;
    SListPushBack(&singleList, 100);
    SListPrint(singleList); // 预期输出: 100
    SListPopBack(&singleList);
    SListPrint(singleList); // 预期输出: 空行

    printf("\n===== 测试完成 =====\n");
}

int main() {
    testSList();
    return 0;
}

      4.注意：慎用assert断言。

  8. 双链表
    • 头文件： 
      #pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDatatype;

typedef struct ListNode
{
    LTDatatype _data;
    struct ListNode* next;
    struct ListNode* prev;
}ListNode;

// 创建返回链表的结点.
ListNode* ListCreate(LTDatatype x);
// 双向链表销毁
void ListDestroy(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDatatype x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDatatype x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDatatype x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDatatype x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
//判断是否为空
bool LTEmpty(ListNode* phead);
//初始化
ListNode* ListInit();

    • 源文件： 
      #include"dlist.h"
// 创建返回链表的结点.
ListNode* ListCreate(LTDatatype x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		return NULL;
	}
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->_data = x;
	return newnode;
}
// 双向链表销毁
void ListDestroy(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(plist);
}
// 双向链表打印
void ListPrint(ListNode* plist)
{
	if (plist == NULL || LTEmpty(plist)) {
		printf("链表为空\n");
		return;
	}

	ListNode* cur = plist->next;
	while (cur != plist) {
		printf("%d ", cur->_data);
		cur = cur->next;
	}
	printf("\n");
}
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDatatype x)
{
	assert(plist);
	ListNode* newnode = ListCreate(x);
	ListNode* tail = plist->prev;
	newnode->prev = tail;
	tail->next = newnode;
	newnode->next = plist;
}
// 双向链表尾删
void ListPopBack(ListNode* plist)
{
	assert(plist);
	assert(!LTEmpty(plist)); // 确保链表不为空

	ListNode* tail = plist->prev;
	ListNode* ntail = tail->prev;

	ntail->next = plist;
	plist->prev = ntail;
	free(tail);
}
// 双向链表头插
void ListPushFront(ListNode* plist, LTDatatype x)
{
	assert(plist);

	ListNode* newnode = ListCreate(x);
	ListNode* first = plist->next;

	plist->next = newnode;
	newnode->prev = plist;
	newnode->next = first;
	first->prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* plist)
{
	assert(plist);
	assert(!LTEmpty(plist)); // 链表为空时不能删除

	ListNode* first = plist->next;
	ListNode* second = first->next;

	plist->next = second;
	second->prev = plist;
	free(first);
}
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDatatype x)
{
	assert(plist);

	ListNode* cur = plist->next;
	while (cur != plist) {
		if (cur->_data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDatatype x)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* newnode = ListCreate(x);
	// prev newnode pos

	prev->next = newnode;
	newnode->prev = prev;

	newnode->next = pos;
	pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);

	ListNode* p = pos->prev;
	ListNode* n = pos->next;

	p->next = n;
	n->prev = p;
	free(pos);
	//pos = NULL;
}
bool LTEmpty(ListNode* plist)
{

	/*if (phead->next == phead)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return plist->next == plist;
}
ListNode* ListInit()
{
	ListNode* plist = ListCreate(0); // 使用 0 作为哨兵值，实际不存储数据
	plist->next = plist;
	plist->prev = plist;
	return plist;
}

    • 测试： 
      #include"dlist.h"
int main() {
    // 初始化双向循环链表
    ListNode* plist = ListInit();

    // 测试尾插
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    printf("尾插后: ");
    ListPrint(plist); // 输出: 1 2 3

    // 测试头插
    ListPushFront(plist, 0);
    ListPushFront(plist, -1);
    printf("头插后: ");
    ListPrint(plist); // 输出: -1 0 1 2 3

    // 测试查找
    ListNode* found = ListFind(plist, 2);
    if (found) {
        printf("找到节点: %d\n", found->_data); // 输出: 找到节点: 2
    }

    // 测试插入
    ListInsert(found, 10);
    printf("插入后: ");
    ListPrint(plist); // 输出: -1 0 1 10 2 3

    // 测试删除
    ListErase(found);
    printf("删除后: ");
    ListPrint(plist); // 输出: -1 0 1 10 3

    // 测试尾删
    ListPopBack(plist);
    printf("尾删后: ");
    ListPrint(plist); // 输出: -1 0 1 10

    // 测试头删
    ListPopFront(plist);
    printf("头删后: ");
    ListPrint(plist); // 输出: 0 1 10

    // 测试销毁
    ListDestroy(plist);
    plist = NULL;

    return 0;
}

顺序表和链表的区别和联系

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连续
随机访问 支持 O (1) 不支持：O (N)
任意位置插入或者删除元素 可能需要搬移元素，效率低 O (N) 只需修改指针指向
插入 动态顺序表，空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储 + 频繁访问 任意位置插入和删除频繁
缓存利用率 高 低

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布