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

线性表

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

顺序表

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

• 1. 静态顺序表:使用定长数组存储元素
     
• 2.动态顺序表
  
  Seqlist.h
  
  Seqlist.c

#include"Seqlist.h"

void SLInit(SL* ps){
	ps->a = (SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY);
	if (ps->a == NULL) {
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}
void SLDestroy(SL* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}
void SLPrint(SL* ps) {
	assert(ps);
	int i = 0;
	for (i = 0;i < ps->size;i++) {
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
void SLCheckCapacity(SL* ps) {
	assert(ps);
	if (ps->size == ps->capacity) {
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}
void SLPushBack(SL* ps, SLDataType x) {
	//assert(ps);

	//扩容
	//SLCheckCapacity(ps);

	//ps->a[ps->size++] = x;
	SLInsert(ps, ps->size, x);

}
void SLPopBack(SL* ps) {
	assert(ps);
	//暴力检查
	assert(ps->size > 0);
	//温柔地检查
	//if (ps->size == 0)
	//	return;
	ps->size--;
}
void SLPushFront(SL* ps, SLDataType x) {
	/*assert(ps);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0) {
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;*/
	SLInsert(ps, 0, x);
}
void SLPopFront(SL* ps) {
	assert(ps);
	int begin = 1;
	while (begin < ps->size) {
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x) {
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos) {
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
void SLErase(SL* ps, int pos) {
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size) {
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}
int SLFind(SL* ps, SLDataType x){
	assert(ps);
	int i = 0;
	for (i = 0;i < ps->size;i++) {
		if (ps->a[i] == x) 
			return i;
	}
	return -1;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"Seqlist.h"

void TestSeqList1(){
	SL s;
	SLInit(&s);
	SLPushBack(&s,1);
	SLPushBack(&s,2);
	SLPushBack(&s,3);
	SLPushBack(&s,4);
	SLPushBack(&s,5);
	SLPushBack(&s,6);
	SLPushBack(&s,7);
	SLPopBack(&s);
	SLPopBack(&s);
	
	SLPrint(&s);
	
	SLDestroy(&s);
}
void TestSeqList2() {
	SL s;
	SLInit(&s);
	SLPushFront(&s, 1);
	SLPushFront(&s, 2);
	SLPushFront(&s, 3);
	SLPushFront(&s, 4);
	SLPushFront(&s, 5);
	SLPrint(&s);
	//头插/头删N个数据，时间复杂度：O（N^2）
	//尾插/尾删N个数据，时间复杂度：O（N）
	SLPopFront(&s);
	SLPrint(&s);
	SLInsert(&s,4,40);
	SLPrint(&s);
	SLInsert(&s,0,40);
	SLPrint(&s);
	SLErase(&s, 3);
	SLPrint(&s);
}
int main() {
	TestSeqList2();

	return 0;
}

例1：


例2：


例3：


顺序表缺点：
1.中间头部插入删除数据，需要挪动数据，效率低下
2.空间不够，扩容。扩容有一定的消耗，其次还可能会有一定空间浪费

链表

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

注意:
1.从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

SList.h

#pragma once

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

typedef int SLTDataType;

typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//单链表查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//pos前插入
void SListInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);
//pos位置删除
void SLTErase(SLTNode** pphead,SLTNode* pos);

//pos后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//pos后删除
void SLTEraseAfter(SLTNode* pos);

//销毁
//void SLTDestroy(SLTNode* phead);
void SLTDestroy(SLTNode** pphead);

SList.c

#include"SList.h"

void SLTPrint(SLTNode* phead) {
	SLTNode* cur = phead;
	while (cur!=NULL) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
SLTNode* BuySLTNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

	if (newnode == NULL) {
		perror("malloc fail");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	SLTNode* newnode = BuySLTNode(x);

	//为空
	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
		//不为空
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead) {
	//温柔地检查
	//if (*pphead == NULL) 
	//	return;
	//暴力检查
	assert(pphead);
	assert(*pphead);
	//1.只有一个节点
	//2.有多个节点
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	else {
		//找尾
		/*SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL) {
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;*/
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL) {
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
void SLTPopFront(SLTNode** pphead) {
	//温柔地检查
	//if (*pphead == NULL) 
	//	return;
	//暴力检查
	assert(pphead);
	assert(*pphead);

	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x) {
	SLTNode* cur = phead;
	while (cur) {
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pos);
	assert(pphead);

	if (pos == *pphead) {
		SLTPushFront(pphead, x);
	}
	else {
		//找到pos前一个位置
		SLTNode* prev = *pphead;
		while (prev->next!= pos) {
			prev = prev->next;
		}

		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead);
	assert(pos);
	//assert(*pphead);

	if (*pphead == pos) {
		SLTPopFront(pphead);
	}
	else {
		SLTNode* prev = *pphead;
		while (prev->next != pos) {
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

//一个单链表，给了pos，但不给头指针，是否能在pos之前插入x
//能，在pos后面插入x，再将pos和x的值交换位置
//删除同理，但不能删尾
void SListInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);

	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	assert(pos->next);

	SLTNode* del = pos->next;
	pos->next = del->next;

	free(del);
	del = NULL;
}

//void SLTDestroy(SLTNode* phead) {
//	SLTNode* cur = phead;
//	while (cur) {
//		SLTNode* tmp = cur->next;
//		free(cur);
//		cur = tmp;
//	}
//}
void SLTDestroy(SLTNode** pphead) {
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur) {
		SLTNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*pphead = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

void TestSList1() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPopBack(&plist);
	SLTPopFront(&plist);
	SLTPopBack(&plist);

	SLTPrint(plist);
}
void TestSList2() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	SLTNode* ret = SListFind(plist, 2);
	SListInsert(&plist, ret, 20);
	SLTPrint(plist);

	SLTNode* res = SListFind(plist, 4);
	SLTErase(&plist, res);
	res = NULL;
	SLTPrint(plist);

	/*SLTDestroy(plist);
	plist = NULL;*/
	SLTDestroy(&plist);
	SLTPrint(plist);
}
int main() {
	TestSList2();
	return 0;
}