您的位置: 首页  >  文章  >  数据结构---顺序表和链表

数据结构---顺序表和链表

分类: 文章 • 2022-10-06 14:17:47

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。
数据结构---顺序表和链表

2.顺序表

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

    1. 静态顺序表：使用定长数组存储。
    1. 动态顺序表：使用动态开辟的数组存储。
#define N 100 typedef int SLDataType;
 
typedef struct SeqList {   
		  SLDataType array[N]; // 定长数组 
		  size_t size;        // 有效数据的个数   
}SeqList;
// 顺序表的动态存储
 typedef struct SeqList {
     		 SLDataType* array;  // 指向动态开辟的数组
       	 size_t size ;       // 有效数据个数
             size_t capicity ;   // 容量空间的大小
   }SeqList;

数据结构---顺序表和链表

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

 // 顺序表的动态存储
  typedef struct SeqList {
     	   SLDataType* array;  // 指向动态开辟的数组
           size_t size ;       // 有效数据个数
           size_t capicity ;
                   // 容量空间的大小 
}SeqList;
 
// 基本增删查改接口 
void SeqListInit(SeqList* psl, size_t capacity); 
void SeqListDestory(SeqList* psl); 
void CheckCapacity(SeqList* psl); 
void SeqListPushBack(SeqList* psl, SLDataType x); 
void SeqListPopBack(SeqList* psl); 
void SeqListPushFront(SeqList* psl, SLDataType x); 
void SeqListPopFront(SeqList* psl);
int SeqListFind(SeqList* psl, SLDataType x);
 void SeqListInsert(SeqList* psl, size_t pos, SLDataType x); 
 void SeqListErase(SeqList* psl, size_t pos); 
 void SeqListRemove(SeqList* psl, SLDataType x); 
 void SeqListModify(SeqList* psl, size_t pos, SLDataType x);
  void SeqListPrint(SeqList* psl);

链表

3.1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链 接次序实现的
数据结构---顺序表和链表实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

  1. 单向、双向
  2. 带头、不带头
  3. 循环、非循环
    无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了，后面我们代码实现了就知道了。
// 1、无头单向非循环链表增删查改实现
typedef int SLTDataType;
typedef struct SListNode {
	SLTDataType _data;
	struct SListNode* _next;
}SListNode;

typedef struct SList {
	SListNode* _head; 
}SList;

void SListInit(SList* plist);
void SListDestory(SList* plist);

SListNode* BuySListNode(SLTDataType x);
void SListPushFront(SList* plist, SLTDataType x);
void SListPopFront(SList* plist); 
SListNode* SListFind(SList* plist, SLTDataType x); // 在pos的后面进行插入 void SListInsertAfter(SListNode* pos, SLTDataType x); // 在pos的前面进行插入 void SListEraseAfter(SListNode* pos); void SListRemove(SList* plist, SLTDataType x);

void SListPrint(SList* plist); 
void TestSList();
//带头结点的增删改查
typedef int LTDataType;
typedef struct ListNode {
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

typedef struct List {
	ListNode* _head; 
}List;

void ListInit(List* plist);
void ListDestory(List* plist);

void ListPushBack(List* plist, LTDataType x);
void ListPushBack(List* plist);
void ListPushFront(List* plist, LTDataType x); 
void ListPopFront(List* plist);

ListNode* ListFind(List* plist, LTDataType x); // 在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 删除pos位置的节点 void ListErase(ListNode* pos); void ListRemove(List* plist, LTDataType x);

void ListPrint(List* plist);

3.3 链表面试题
https://leetcode-cn.com/problems/remove-linked-list-elements/description/

4.链表和顺序表的关系

顺序表：一白遮百丑
白：空间连续，支持随机访问
丑：
1.中间或前面部分的插入删除时间复杂度O(N)
2.增容的代价比较大
链表：一（胖）毁所有
胖：一节点为单位存储，不支持随机访问
所有
1.任意位置插入删除时间复杂度为O(1)
2.没有增容问题，插入一个开辟的一个空间

相关推荐