【数据结构】顺序表与链表基础知识的超详细详解

2、顺序表

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

#defint N 7
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType array[N];//定长数组
    size_t size;        //有效数据个数
}SeqList;

typedef struct SeqList
{
    SLDataType* array;//指向动态开辟的数组
    size_t size;      //有效数据个数
    size_t capacity;  //容量空间大小
}SeqList;

 3.2 链表的分类

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

一共有八种链表结构， 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

//无头，单项，非循环链表
typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next; 
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
	while (plist)
	{
		printf("%d ", plist->data);
		plist = plist->next;
	}
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* head = *pplist;
	SListNode* newnode= BuySListNode(x);
	if (!( *pplist))
	{
		(*pplist) = newnode;
	}
	else
	{
		while ((*pplist)->next)
		{
			*pplist = (*pplist)->next;
		}
		(*pplist)->next = newnode;
	}
	*pplist = head;
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	if (!(*pplist))
	{
		(*pplist) = newnode;
	}
	else
	{
		SListNode* head = newnode;
		newnode->next = (*pplist);
		(*pplist) = head;
	}
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	SListNode* head = *pplist;
	assert(*pplist);
	while ((*pplist)->next->next)
	{
		*pplist = (*pplist)->next;
	}
	free((*pplist)->next);
	(*pplist)->next = NULL;
	(*pplist) = head;
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	SListNode* head = (*pplist)->next;
	free((*pplist));
	(*pplist) = NULL;
	(*pplist) = head;
}

 4、顺序表和链表的区别

最后是双向带头链表增删查改的实现 

ListNode* ListCreate(ListNode* plist)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = -1;
	newnode->next = newnode->prev = NULL;
	return newnode;
}
// 双向链表销毁
void ListDestory(ListNode* plist)
{
	while (plist)
	{
		ListNode* next = plist->next;
		plist->data=0;
		free(plist);
		plist = NULL;
		plist = next;
	}	
}
// 双向链表打印
void ListPrint(ListNode* plist)
{
	ListNode* next = plist->next;
	while (next != plist)
	{
		printf("%d ", next->data);
		next = next->next;
	}
	printf("\n");
}
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = plist;
	newnode->prev = plist->prev;
	plist->prev->next = newnode;
	plist->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* plist)
{
	ListNode* tail = plist->prev;
	plist->prev = tail->prev;
	tail->prev->next = plist;
	free(tail);
}
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = plist->next;
	newnode->prev = plist;
	plist->next->prev = newnode;
	plist->next = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* plist)
{
	ListNode* head = plist->next;
	plist->next = head->next;
	head->next->prev = plist;
	free(head);
}