【数据结构】（2）顺序表和链表

（1）线性表

数据结构实际两种结构

1.物理结构（内存中如何储存）

2.逻辑结构（是我们想像出来的）

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的（在内存里储存不一定连续），线性表在物理上存储时，通常以数组和链式结构的形式存储。

线性表：

数组（物理和逻辑上都是连续的）【可能会存在浪费】

链表；（物理上不一定是线性的，）按需申请内存】

（2）顺序表

1.概念及结构

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

顺序表一般可以分为：

静态顺序表：使用定长数组存储。
动态顺序表：使用动态开辟的数组存储。

案例

先定义一个头文件

struct SeqList
{
int a[10];
int size;
};

void SeqListPushBack(struct SeqList* pa, int x);
void SeqListPushBack(struct SeqList* pa, int x);
void SeqListPushBack(struct SeqList* pa, int x);

我们发现，在之后如果想要改变数组a的类型，就需要所有都改变，不方便。

所以我们使用typedef

并且用宏去定义只能是变量

typedef int SLDataType;
#define N 10;

struct SeqList
{
SLDataType a[N];//定长数组
int size;//有效数据个数
};

void SeqListPushBack(struct SeqList* ps, SLDataType x);
void SeqListPopBack(struct SeqList* ps );
void SeqListPushFront(struct SeqList* ps, SLDataType x);
void SeqListPopFront(struct SeqList* ps);

这个数据表我们称为静态顺序表设计（固定大小）

那我们怎么开辟动态的呢，方法如下

typedef int SLDataType;

struct SeqList
{
SLDataType *a;//执行开辟的数组
int size;//有效数据
int capacity;//容量空间的大小
};

void SeqListPushBack(struct SeqList* ps, SLDataType x);//尾插尾删
void SeqListPopBack(struct SeqList* ps );

void SeqListPushFront(struct SeqList* ps, SLDataType x);//头插头删
void SeqListPopFront(struct SeqList* ps);

void SeqListInsert(struct Seqlist*ps,int pos,SLDataType x);//任意位置的插入删除
void SeqListErase(struct Seqlist*ps,int pos);

优化一下

typedef int SLDataType;

typedef struct SeqList
{
SLDataType *a;//执行开辟的数组
int size;//有效数据
int capacity;//容量空间的大小
}SL，SeqList;

void SeqListPushBack(SL* ps, SLDataType x);//尾插尾删
void SeqListPopBack(SL* ps );

void SeqListPushFront(SL* ps, SLDataType x);//头插头删
void SeqListPopFront(SL* ps);

void SeqListInsert(SL*ps,int pos,SLDataType x);//任意位置的插入删除
void SeqListErase(SL*ps,int pos);

2.接口实现：

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

这里我们放上完整的码，大家可以研究一下

test.c

#include "Seqlist.h"

void TestSeqList1()
{
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl);

SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
//SeqListPopBack(&sl);
//SeqListPopBack(&sl);
SeqListPrint(&sl);

SeqListPushBack(&sl, 10);
SeqListPushBack(&sl, 20);
SeqListPrint(&sl);

SeqListDestory(&sl);
}

void TestSeqList2()
{
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl);

SeqListPushFront(&sl, 10);
SeqListPushFront(&sl, 20);
SeqListPushFront(&sl, 30);
SeqListPushFront(&sl, 40);
SeqListPrint(&sl);

SeqListPopFront(&sl);
SeqListPopFront(&sl);
SeqListPrint(&sl);

SeqListDestory(&sl);
}

void TestSeqList3()
{
SL s;
int pos = SeqListFind(&s, 5);
if (pos != -1)
  {
SeqListErase(&s, pos);
  }
}

// 写一个类似通讯录的菜单
void menu()
{
printf("************************************\n");
printf("请选择你的操作:>\n");
printf("1、头插  2、头删\n");
printf("3、尾插  4、尾删\n");
// ...
printf("************************************\n");
}

int main()
{
TestSeqList1();
TestSeqList2();
TestSeqList3();
return 0;
}

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Seqlist.h"
/*==================================================*/
void SeqListPrint(SL* ps)//打印
{
for (int i = 0; i < ps->size; ++i)
  {
printf("%d ", ps->a[i]);
  }
printf("\n");
}
/*==================================================*/
void SeqListInit(SL* ps)//初始化
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
/*==================================================*/
void SeqListDestory(SL* ps)//释放
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
/*==================================================*/
void SeqListCheckCapacity(SL* ps)//扩容
{
// 如果没有空间或者空间不足，那么我们就扩容
if (ps->size == ps->capacity)
  {
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//每次乘2，适合
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
    {
printf("realloc fail\n");
exit(-1);
    }

ps->a = tmp;
ps->capacity = newcapacity;
  }
}
/*==================================================*/
void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
SeqListCheckCapacity(ps);

ps->a[ps->size] = x;
ps->size++;
}
/*==================================================*/
void SeqListPopBack(SL* ps)//尾删
{
// 温柔处理方式
//if (ps->size > 0)
//{
//  //ps->a[ps->size - 1] = 0;
//  ps->size--;
//}

// 暴力处理方式
assert(ps->size > 0);
ps->size--;
}
/*==================================================*/
void SeqListPushFront(SL* ps, SLDataType x)//头插
{
SeqListCheckCapacity(ps);

// 挪动数据
int end = ps->size - 1;
while (end >= 0)
  {
ps->a[end + 1] = ps->a[end];
--end;
  }
ps->a[0] = x;
ps->size++;
}
/*==================================================*/
void SeqListPopFront(SL* ps)//头删
{
assert(ps->size > 0);

// 挪动数据
int begin = 1;
while (begin < ps->size)
  {
ps->a[begin - 1] = ps->a[begin];
++begin;
  }
ps->size--;
}
/*==================================================*/
void SeqListInsert(SL* ps, int pos, SLDataType x)//任意位置增加
{
assert(ps);
assert(pos <= ps->size && pos >= 0);
SeqListCheckCapacity(ps);

int end = ps->size - 1;
while (end >= pos)
  {
ps->a[end + 1] = ps->a[end];
--end;
  }
ps->a[pos] = x;
ps->size++;
}
/*==================================================*/
void SeqListErase(SL* ps, int pos)//任意位置删除
{
assert(ps);
assert(pos < ps->size&& pos >= 0);

int start = pos;
while (start < ps->size - 1)
  {
ps->a[start] = ps->a[start + 1];
++start;
  }
ps->size--;
}
/*==================================================*/
int SeqListFind(SL* ps, SLDataType x)//找位置
{
assert(ps);
int i = 0;
while (i < ps->size)
  {
if (ps->a[i] == x);
    {
return i;
    }
++i;
  }
return -1;
}
/*==================================================*/

Seqlist.h

#pragma once
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//#define N 10000
//typedef int SLDataType;
//
//// 静态顺序表
//typedef struct SeqList
//{
//  SLDataType a[N];
//  int size; // 表示数组中存储了多少个数据
//}SL;
//
//// 接口函数 -- 命名风格是跟着STL走的，方便后续学习STL
//void SeqListInit(SL* ps); 
//
//// 静态特点：如果满了就不让插入  缺点：给多少的合适呢？这个很难确定
//// N给小了不够用，N给大了浪费
//void SeqListPushBack(SL* ps, SLDataType x);
//void SeqListPopBack(SL* ps);
//void SeqListPushFront(SL* ps, SLDataType x);
//void SeqListPopFront(SL* ps);
//// ...

typedef int SLDataType;

// 动态顺序表
typedef struct SeqList
{
SLDataType* a;
int size;      // 表示数组中存储了多少个数据
int capacity;  // 数组实际能存数据的空间容量是多大 
}SL;


// 接口函数 -- 命名风格是跟着STL走的，方便后续学习STL
void SeqListPrint(SL* ps);
void SeqListInit(SL* ps);
void SeqListDestory(SL* ps);

void SeqListCheckCapacity(SL* ps);
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListPushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps);
// ...

// 找到了返回x位置下标，没有找打返回-1
int SeqListFind(SL* ps, SLDataType x);
// 指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
// 删除pos位置的数据
void SeqListErase(SL* ps, int pos);

3.优缺点

1.可动态增长的数组

2.数据在数组中储存时必须是连续的

缺点：

1.中间或头部的插入删除很慢，需要挪动数据，时间复杂度是O（N）

2.空间不够时，扩容会有一定消耗和浪费

优点：

1.随机访问

2.缓存利用率比较高

（3）链表

1.链表的概念及结构

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

现实中：

【数据结构】（2）顺序表和链表

数据结构中：

【数据结构】（2）顺序表和链表

这样的链式结构易于增减

2.种类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向、双向

2. 带头、不带头

3. 循环、非循环

其中常用的是

【数据结构】（2）顺序表和链表

3.例子

这里我们以单向链表为例，直接来一个码，大家拷贝后研究

特别注意源程序命名

SList.c

#define _CRT_SECURE_NO_WARNINGS 
#include"SList.h"
/*=================================================*/
SListNode* BuySListNode(SListDataType x)
{
SListNode* newNode = (SListNode*)malloc(sizeof//建立新结点
  (SListNode));
if (newNode == NULL)
  {
printf("申请结点失败\n");
exit(-1);
  }
newNode->data = x;
newNode->next = NULL;
return newNode;
}
/*=================================================*/
void SListPrint(SListNode* phead)//遍历打印列表
{
SListNode* cur = phead;
while (cur != NULL)
  {
printf("%d->", cur->data);
cur = cur->next; 
  }
printf("NULL\n");
}
/*=================================================*/
void SListPushBack(SListNode** pphead, SListDataType x)//尾插
{
assert(pphead);
SListNode* newNode = BuySListNode(x);
if (*pphead == NULL)
  {
*pphead = newNode;
  }
else
  {
SListNode* tail = *pphead;
while (tail->next != NULL)
    {
tail = tail->next;
    }
tail->next = newNode;//将新的结点连在后面
  }
}
/*=================================================*/
void SListPopBack(SListNode** pphead)
{
//1.空
//2.一个
//3.一个结点以上
if (*pphead == NULL)
  {
return;
  }
else if ((*pphead)->next == NULL)
  {
free(*pphead);
*pphead = NULL;
  }
else
  {
//小心野指针
SListNode* tail = *pphead;
SListNode* prev = NULL;
while (tail->next != NULL)
    {
prev = tail;
tail = tail->next;
    }
free(tail);
prev->next = NULL;
  }
}
/*=================================================*/
void SListPushFront(SListNode** pphead, SListDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
/*=================================================*/
void SListPopFront(SListNode** pphead)
{
if (*pphead == NULL)
  {
return;
  }
else 
  {
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
  }
}
/*=================================================*/
SListNode* SListFind(SListNode* phead, SListDataType x)
{
SListNode* cur = phead;
while (cur)
  {
if (cur->data == x)
    {
return cur;
    }
cur = cur->next;
  }
return NULL;
}
/*=================================================*/
void SListInsertAfter(SListNode* pos, SListDataType x)//与find连用
{
assert(pos);
SListNode* newnode = BuySListNode(x);
//一定注意以下顺序
newnode->next = pos->next;
pos->next = newnode;
}
/*=================================================*/
void SListEraseAfter(SListNode* pos)
{
assert(pos->next);
if (pos->next)
  {
SListNode* next = pos->next;
SListNode* nextnext = next->next;
pos->next = nextnext;
free(next);
  }
}
/*=================================================*/
void SListDestory(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)//释放所有
  {
SListNode* next = cur->next;
free(cur);
cur = next;
  }
}
/*=================================================*/

SList.h

#pragma once
#include<Stdio.h>
#include<malloc.h>
#include<assert.h>

typedef int SListDataType;
//结点
typedef struct SListNode
{
SListDataType data;
struct SListNode* next;
}SListNode;

SListNode* BuySListNode(SListDataType x);

void SListPushBack(SListNode** pphead,SListDataType x);
void SListPopBack(SListNode** pphead);

void SListPushFront(SListNode** pphead, SListDataType x);
void SListPopFront(SListNode** pphead);

void SListPrint(SListNode* phead);
void SListSize(SListNode* phead);

SListNode*SListFind(SListNode*plist, SListDataType x);//单链表查找
void SListInsertAfter(SListNode* pos, SListDataType x);//随意插入
void SListEraseAfter(SListNode* pos);//删除

void SListDestory(SListNode** pphead);

test.h

#define _CRT_SECURE_NO_WARNINGS 
#include"SList.h"

int main()
{
SListNode* pList = NULL;
SListPushBack(&pList, 1);
SListPushBack(&pList, 2);
SListPushBack(&pList, 3);
SListPushBack(&pList, 4);
SListPrint(pList);

SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPrint(pList);

SListPushFront(&pList,1);
SListPushFront(&pList,2);
SListPushFront(&pList,3);
SListPushFront(&pList,4);
SListPushFront(&pList,5);
SListPrint(pList);

SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPrint(pList);

return 0;
}

（4）顺序表和链表的区别和联系

顺序表：一白遮百丑

白：空间连续、支持随机访问

丑：中间或前面部分的插入删除时间复杂度O(N) 2.增容的代价比较大。

链表：一(黑)毁所有

黑：以节点为单位存储，不支持随机访问

所有：任意位置插入删除时间复杂度为O(1) 2.没有增容问题，插入一个开辟一个空间。

秒客网

【数据结构】（2）顺序表和链表

（1）线性表

（2）顺序表

1.概念及结构

2.接口实现：

test.c

Seqlist.c

Seqlist.h

3.优缺点

（3）链表

1.链表的概念及结构

2.种类

3.例子

SList.c

SList.h

test.h

（4）顺序表和链表的区别和联系

相关文章