02_顺序表与链表

线性表

线性表是n个具有相同特性的数据元素的有限序列.

线性表在逻辑上是线性结构, 但在物理结构上并不一定是连续的, 线性表在物理上存储时, 通常是以数组和链式结构的形式存储

顺序表

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

  • 静态顺序表: 使用定长数组存储
  • 动态顺序表: 使用动态开辟的数组存储
// 模拟实现动态顺序表
// SeqList.h

#pragma once

typedef int DataType;
typedef struct SeqList {
	DataType *_array;
	int _capacity;
	int _size;
}SeqList, *PSeq;

void SeqListInit(PSeq ps, int capacity);
void SeqListPushBack(PSeq ps, DataType data);
void SeqListPopBack(PSeq ps);
void SeqListPushFront(PSeq ps, DataType data);
void SeqListPopFront(PSeq ps);
void SeqListInsert(PSeq ps, int pos, DataType data);
void SeqListErase(PSeq ps, int pos);
int SeqListFind(PSeq ps, DataType data);
int SeqListSize(PSeq ps);
int SeqListCapacity(PSeq ps);
int SeqListEmpty(PSeq ps);
void SeqListClear(PSeq ps);
void SeqListRemove(PSeq ps, DataType data);
void SeqListRemoveAll(PSeq ps, DataType data);
void SeqListDestory(PSeq ps);
void CheckCapacity(PSeq ps);
void SeqListPrint(PSeq ps);
void BubbleSort(PSeq ps);
// SeqList.c

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


void SeqListInit(PSeq ps, int capacity) {
	ps->_array = (DataType*)malloc(sizeof(DataType)*capacity);
	if (NULL == ps->_array) {
		assert(0);
		return;
	}
	ps->_capacity = capacity;
	ps->_size = 0;
}

void SeqListPushBack(PSeq ps, DataType data) {
	assert(ps);
	CheckCapacity(ps);
	ps->_array[ps->_size] = data;
	ps->_size++;

	// SeqListInsert(ps, ps->_size, data);
}

void SeqListPopBack(PSeq ps) {
	assert(ps);
	if (SeqListEmpty(ps)) {
		return;
	}
	ps->_size--;

	// SeqListErase(ps, ps->_size - 1);
}

void SeqListPushFront(PSeq ps, DataType data) {
	assert(ps);
	CheckCapacity(ps);

	// 将顺序表所有元素向后搬移一个位置
	for (int i = ps->_size - 1; i >= 0; --i) {
		ps->_array[i + 1] = ps->_array[i];
	}
	// 插入元素
	ps->_array[0] = data;
	ps->_size++;

	// SeqListInsert(ps, 0, data);
}

void SeqListPopFront(PSeq ps) {
	if (SeqListEmpty(ps)) {
		return;
	}
	// 将顺序表所有元素向前搬移一个位置
	for (int i = 1; i < ps->_size; ++i) {
		ps->_array[i - 1] = ps->_array[i];
	}
	ps->_size--;

	// SeqListErase(ps, 0);
}

void SeqListInsert(PSeq ps, int pos, DataType data) {
	assert(ps);
	if (pos < 0 || pos > ps->_size) {
		return;
	}
	CheckCapacity(ps);
	for (int i = ps->_size - 1; i >= pos; --i) {
		ps->_array[i + 1] = ps->_array[i];
	}
	ps->_array[pos] = data;
	ps->_size++;
}

void SeqListErase(PSeq ps, int pos) {
	assert(ps);
	if (pos < 0 || pos >= ps->_size) {
		return;
	}
	for (int i = pos + 1; i < ps->_size; ++i) {
		ps->_array[i - 1] = ps->_array[i];
	}
	ps->_size--;
}

int SeqListFind(PSeq ps, DataType data) {
	assert(ps);
	for (int i = 0; i < ps->_size; i++) {
		if (ps->_array[i] == data) {
			return i;
		}
	}
	return -1;
}

int SeqListSize(PSeq ps) {
	assert(ps);
	return ps->_size;
}

int SeqListCapacity(PSeq ps) {
	assert(ps);
	return ps->_capacity;
}

int SeqListEmpty(PSeq ps) {
	assert(ps);
	return 0 == ps->_size;
}

void SeqListClear(PSeq ps) {
	assert(ps);
	ps->_size = 0;
}

void SeqListRemove(PSeq ps, DataType data) {
	SeqListErase(ps, SeqListFind(ps, data));
}

void SeqListRemoveAll(PSeq ps, DataType data) {
	assert(ps);
	int count = 0;
	for (int i = 0; i < ps->_size; ++i) {
		if (ps->_array[i] == data) {
			count++;
		}
		else {
			ps->_array[i - count] = ps->_array[i];
		}
	}
	ps->_size -= count;
}

void SeqListDestory(PSeq ps) {
	if (ps->_array) {
		free(ps->_array);
		ps->_array = NULL;
		ps->_capacity = 0;
		ps->_size = 0;
	}
}

void CheckCapacity(PSeq ps) {
	assert(ps);
	if (ps->_size == ps->_capacity) {
		int newCapacity = ps->_capacity * 2;
		int *pTemp = (DataType*)malloc(newCapacity * sizeof(DataType));
		if (NULL == pTemp) {
			assert(0);
			return;
		}
		// 拷贝元素
		for (int i = 0; i < ps->_size; ++i) {
			pTemp[i] = ps->_array[i];
		}
		free(ps->_array);
		ps->_array = pTemp;
		ps->_capacity = newCapacity;
	}
}

void SeqListPrint(PSeq ps) {
	for (int i = 0; i < ps->_size; ++i) {
		printf("%d ", ps->_array[i]);
	}
	printf("\n");
}

void Swap(int *pLeft, int *pRight) {
	int temp = *pLeft;
	*pLeft = *pRight;
	*pRight = temp;
}

void BubbleSort(PSeq ps) {
	for (int i = 0; i < ps->_size - 1; ++i) {
		int IsChange = 0;
		for (int j = 1; j < ps->_size - 1; ++j) {
			if (ps->_array[j - 1] > ps->_array[j]) {
				IsChange = 1;
				Swap(&ps->_array[j - 1], &ps->_array[j]);
			}
		}
		if (!IsChange) {
			return;
		}
	}
}

链表

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

链表的结构

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

常用的两种结构

  1. 无头单向非循环链表: 结构简单, 一般不会单独用来存数据, 更多是作为其他数据结构的子结构
  2. 带头双向循环链表: 结构最复杂, 一般用在单独存储数据

模拟实现单向带头非循环链表

// SList.h

#pragma once

typedef int SDataType;

typedef struct SListNode {
	SDataType _data;
	struct SListNode* _pNext;
}Node, *PNode;

typedef struct SList {
	PNode _pHead;
}SList, *PSList;

void SListInit(SList* s);
void SListPushBack(SList* s, SDataType data);
void SListPopBack(SList* s);
void SListPushFront(SList* s, SDataType data);
void SListPopFront(SList* s);
void SListInsert(PNode pos, SDataType data);
void SListErase(SList* s, PNode pos);
PNode SListFind(SList* s, SDataType data);
int SListSize(SList* s);
int SListEmpty(SList* s);
void SListRemove(SList* s, SDataType data);

// SList.c

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

void SListInit(SList* s) {
	assert(s);
	s->_pHead = NULL;
}

PNode BuySListNode(SDataType data) {
	PNode pNewNode = (PNode)malloc(sizeof(Node));
	if (pNewNode == NULL) {
		assert(0);
		return NULL;
	}
	pNewNode->_data = data;
	pNewNode->_pNext = NULL;
	return pNewNode;
}

void SListPushBack(SList* s, SDataType data) {
	assert(s);
	PNode pNewNode = BuySListNode(data);
	if (s->_pHead == NULL) {
		s->_pHead = pNewNode;
	}
	else {
		PNode pCur = s->_pHead;
		while (pCur->_pNext) {
			pCur = pCur->_pNext;
		}
		pCur->_pNext = pNewNode;
	}
}

void SListPopBack(SList* s) {
	assert(s);
	if (s->_pHead == NULL) {
		return;
	}
	else if (s->_pHead->_pNext == NULL) {
		free(s->_pHead);
		s->_pHead = NULL;
	}
	else {
		PNode pPre = NULL;
		PNode pCur = s->_pHead;
		while (pCur->_pNext) {
			pPre = pCur;
			pCur = pCur->_pNext;
		}
		free(pCur);
		pPre->_pNext = NULL;
	}
}

void PrintSList(SList* s) {
	assert(s);
	PNode pCur = s->_pHead;
	while (pCur) {
		printf("%d--->", pCur->_data);
		pCur = pCur->_pNext;
	}
	printf("NULL\n");
}

void SListPushFront(SList* s, SDataType data) {
	assert(s);
	PNode pNewNode = BuySListNode(data);
	pNewNode->_pNext = s->_pHead;
	s->_pHead = pNewNode;
}

void SListPopFront(SList* s) {
	PNode pDelNode = NULL;
	assert(s);
	if (s->_pHead = NULL) {
		return;
	}
	pDelNode = s->_pHead;
	s->_pHead = pDelNode->_pNext;
	free(pDelNode);
}

void SListInsert(PNode pos, SDataType data) {
	PNode pNewNode = NULL;
	if (pos == NULL) {
		return;
	}
	pNewNode = BuySListNode(data);
	pNewNode->_pNext = pos->_pNext;
	pos->_pNext = pNewNode;
}

void SListErase(SList* s, PNode pos) {
	assert(s);
	if (pos == NULL || s->_pHead == NULL) {
		return;
	}
	else {
		PNode pPrePos = s->_pHead;
		while (pPrePos && pPrePos->_pNext != pos) {
			pPrePos = pPrePos->_pNext;
		}
		if (pPrePos) {
			pPrePos->_pNext = pos->_pNext;
		}
	}
	free(pos);
}

int SListSize(SList* s) {
	assert(s);
	PNode pCur = s->_pHead;
	size_t count = 0;
	while (pCur) {
		++count;
		pCur = pCur->_pNext;
	}
	return count;
}

int SListEmpty(SList* s) {
	assert(s);
	return s->_pHead == NULL;
}

void SListRemove(SList* s, SDataType data) {
	assert(s);
	if (s->_pHead == NULL) {
		return;
	}
	PNode pPre = NULL;
	PNode pCur = s->_pHead;
	while (pCur) {
		if (pCur->_data == data) {
			if (pCur == s->_pHead) {
				s->_pHead = pCur->_pNext;
			}
			else {
				pPre->_pNext = pCur->_pNext;
			}
			free(pCur);
			return;
		}
		else {
			pPre = pCur;
			pCur = pCur->_pNext;
		}
	}
}

模拟实现双向带头循环链表

// DList.h

#pragma once

typedef int DLDataType;

typedef struct DListNode {
	struct DListNode* _pNext;
	struct DListNode* _pPre;
	DLDataType _data;
}DLNode, *PDLNode;

void DListInit(PDLNode* pHead);
void DListPushBack(PDLNode pHead, DLDataType data);
void DListPopBack(PDLNode pHead);
void DListPushFront(PDLNode pHead, DLDataType data);
void DListPopFront(PDLNode pHead);
void DListInsert(PDLNode pos, DLDataType data);
void DListErase(PDLNode pos);
void DListClear(PDLNode pHead);
void DListDestory(PDLNode* pHead);
// DList.c

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

void DListInit(PDLNode* pHead) {
	assert(pHead);
	*pHead = (PDLNode)malloc(sizeof(DLNode));
	if (*pHead == NULL) {
		assert(0);
		return;
	}
	(*pHead)->_pNext = *pHead;
	(*pHead)->_pPre = *pHead;
}

PDLNode BuyDListNode(DLDataType data) {
	PDLNode pNewNode = (PDLNode)malloc(sizeof(DLNode));
	if (pNewNode == NULL) {
		assert(0);
		return pNewNode;
	}
	pNewNode->_pNext = NULL;
	pNewNode->_pPre = NULL;
	return pNewNode;
}

void DListPushBack(PDLNode pHead, DLDataType data) {
	PDLNode pNewNode = BuyDListNode(data);
	pNewNode->_pNext = pHead;
	pNewNode->_pPre = pHead->_pPre;
	pHead->_pPre->_pNext = pNewNode;
	pHead->_pPre = pNewNode;
}

void DListPopBack(PDLNode pHead) {
	assert(pHead);
	if (pHead == pHead->_pNext) {
		return;
	}
	PDLNode pDelNode = pHead->_pPre;
	pDelNode->_pPre->_pNext = pHead;
	pHead->_pPre = pDelNode->_pPre;
	free(pDelNode);
}

void DListPushFront(PDLNode pHead, DLDataType data) {
	PDLNode pNewNode = BuyDListNode(data);
	pNewNode->_pNext = pHead->_pNext;
	pHead->_pNext->_pPre = pNewNode;
	pHead->_pNext = pNewNode;
	pNewNode->_pPre = pHead;
}

void DListPopFront(PDLNode pHead) {
	assert(pHead);
	if (pHead->_pNext == pHead) {
		return;
	}
	PDLNode pDelNode = pHead->_pNext;
	pHead->_pNext = pDelNode->_pNext;
	pDelNode->_pNext->_pPre = pHead;
	free(pDelNode);
}

void DListInsert(PDLNode pos, DLDataType data) {
	if (pos == NULL) {
		return;
	}
	PDLNode pNewNode = BuyDListNode(data);
	pNewNode->_pNext = pos;
	pNewNode->_pPre = pos->_pPre;
	pos->_pPre = pNewNode;
	pNewNode->_pPre->_pNext = pNewNode;
}

void DListErase(PDLNode pos) {
	if (pos == NULL) {
		return;
	}
	pos->_pNext->_pPre = pos->_pPre;
	pos->_pPre->_pNext = pos->_pNext;
	free(pos);
}

void DListClear(PDLNode pHead) {
	PDLNode pCur = pHead->_pNext;
	while (pCur != pHead) {
		pHead->_pNext = pCur->_pNext;
		free(pCur);
		pCur = pHead->_pNext;
	}
	pHead->_pNext = pHead;
	pHead->_pPre = pHead;
}

void DListDestory(PDLNode* pHead) {
	DListClear(*pHead);
	free(*pHead);
	*pHead = NULL;
}

顺序表与链表的区别

顺序表:

  • 空间连续, 支持随机访问
  • 中间或前面的部分插入删除时间复杂度O(N). 增容的代价比较大

链表:

  • 以节点为单位存储, 不支持随机访问
  • 任意位置插入删除时间复杂度O(1). 没有增容问题

 


我们的征途是星辰大海!