数据结构———线性表（上）

发布于：2022-12-19 ⋅ 阅读:(329) ⋅ 点赞:(0)

目录

知识框架:

线性表 

顺序表

1.顺序表的概念

2.顺序表结构

3.初始化链表

4.增容

5.顺序表的插入

6.顺序表的删除

7.顺序表的查找

         8.删除指定位置

9.顺序表的销毁

测试运行

 顺序表小结

链表

1.链表的结构及其概念

 2.单链表的储存结构

3.节点的创建

4.单链表的头尾插入

 5.单链表的删除

6.单链表的查找

7.单链表指定位置插入

8.单链表的打印

9.单链表的销毁

10.测试运行

小结 

知识框架:

线性表 

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

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的

线性表在物理上存储时，通常以数组和链式结构的形式存储

顺序表

1.顺序表的概念

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

2.顺序表结构

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

#define SLDataType int  //定义类型，以后修改类型时更加方便

typedef struct SL 
{
	SLDataType* p;
	int size;
	int capacity;
}SeqList;

定义一个结构体，其中存指针是为了后面可以动态开辟空间，不会造成空间的浪费，并记录数组中元素的个数和容量的大小

3.初始化链表

void SLInit(SeqList* pls)
{
	pls->p = NULL;
	pls->capacity = pls->size = 0;
}

在这里我们可以先不开辟空间，只需要将结构体内的内容初始化即可。

4.增容

void SLCheck(SeqList* pls)
{
	//当capacity==size时说明没有空间了，这时需要增加顺序表容量
	if (pls->capacity == pls->size)
	{
		//我们一般默认扩容二倍
		int newcapacity = pls->capacity == 0 ? 4 : pls->capacity * 2;
		SLDataType* ps = (SLDataType*)realloc(pls->p, sizeof(SLDataType) * newcapacity);
		if (ps == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		pls->p = ps;
		pls->capacity = newcapacity;
	}
}

5.顺序表的插入

顺序表的头插

//头插
void SLPushfront(SeqList* pls, SLDataType x)
{
	SLCheck(pls);//一上来先检查容量
	int pos = pls->size;
	while (pos)
	{
		pls->p[pos] = pls->p[pos-1];
		pos--;
	}
	pls->p[0] = x;
	pls->size++;
}

顺序表的尾插 

void SLPushback(SeqList* pls, SLDataType x)
{
	assert(pls);
	//增容
	SLCheck(pls);
	pls->p[pls->size] = x;
	pls->size++;
}

6.顺序表的删除

顺序表的头删

void SLPopfront(SeqList* pls)
{
	assert(pls);
    //数据从前向后覆盖即可，最后size减一
	for (int i=0;i<pls->size;i++)
	{
		pls->p[i] = pls->p[i + 1];
	}
	pls->size--;
}

顺序表的尾删 

void SLPopback(SeqList* pls)
{
	assert(pls);
	pls->size--;
}

7.顺序表的查找

void SeqListInsert(SeqList* pls, size_t pos, SLDataType x)
{
	SLCheck(pls);
	int cur;
	for(cur=pls->size;cur>pos;cur--)
	{
		pls->p[cur] = pls->p[cur-1];
	}
	pls->p[pos] = x;
	pls->size++;
}

8.删除指定位置

// 顺序表删除pos位置的值
void SeqListErase(SeqList* pls, size_t pos)
{
	for (pos;pos<pls->size;pos++)
	{
		pls->p[pos] = pls->p[pos + 1];
	}
	pls->size--;
}

9.顺序表的销毁

//销毁
void SLDestory(SeqList* pls)
{
	assert(pls);
	pls->capacity = pls->size = 0;
	pls->p = NULL;
	free(pls->p);
}

打印函数

void Print(SeqList* pls)
{
	for (int i = 0; i < pls->size; i++)
	{
		printf("%d ", pls->p[i]);
	}
	printf("\n");
}

测试运行

#include "SeqList.h"
void test()
{
	SeqList p;
	SLInit(&p);
	
	SLPushback(&p, 1);
	SLPushback(&p, 2);
	SLPushback(&p, 3);
	SLPushback(&p, 4);
	SLPushback(&p, 5);
	SLPushback(&p, 6);
	SLPushback(&p, 7);
	Print(&p);

	SLPushfront(&p, 0);
	SLPushfront(&p, -1);
	SLPushfront(&p, -2);
	Print(&p);

	SLPopback(&p);
	SLPopback(&p);
	Print(&p);

	SLPopfront(&p);
	SLPopfront(&p);
	Print(&p);

	printf("%d\n",SeqListFind(&p, 1));

	SeqListInsert(&p, 0,3);
	Print(&p);


	SeqListErase(&p, 0);
	Print(&p);
	SLDestory(&p);
}

int main()
{
	test();

	return 0;
}

 顺序表小结

我们可以看出顺序表在头插，头删时需要挪动n个数据时间复杂度为O（N），尾插尾删时直接可以删除，所以时间复杂度为O（1）;

顺序表的优点：

  1. 顺序表的内存空间连续。
  2. 尾插、尾删效率较高，时间复杂度是O(1)。
  3. 支持随机访问，可以高效的按下标进行操作，时间复杂度是O(1)。

顺序表的缺点：

  1. 在顺序表中间插入或删除元素时都涉及到元素的移动，效率较低，时间复杂度为O(N)。
  2. 顺序表长度固定，有时需要扩容

链表

1.链表的结构及其概念

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

 2.单链表的储存结构

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDaTaType;

typedef struct SListNode
{
	SLTDaTaType data;
	struct SListNode* next;//指向下一个结构体的地址
}SListNode;

3.节点的创建

//创建新节点
SListNode * BUYSLTNode(SLTDaTaType x)
{
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	node->data = x;
	node->next = NULL;

	return node;
}

4.单链表的头尾插入

//尾插
void SListpushBack(SListNode** pplist, SLTDaTaType x)
{
	//改变了pplist所以传二级指针
	SListNode* node = BUYSLTNode(x);
	//空
	if (*pplist == NULL)
	{
		*pplist = node;
	}
	else//非空
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = node;
	}
}

//头插
void SListpushFront(SListNode** pplist, SLTDaTaType x)
{
	SListNode* newnode = BUYSLTNode(x);
	newnode->next = *pplist;
	*pplist = newnode;

}

 5.单链表的删除

//尾删
void SListpopBack(SListNode** pplist)
{
	SListNode* node = *pplist;
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next==NULL)
	{
		free(*pplist);
		(*pplist) = NULL;
	}
	else
	{
		//找尾
		SListNode* node = NULL;
		SListNode* tail = *pplist;
		while(tail->next!=NULL)
		{
			node = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		node->next = NULL;
	}
}
//头删
void SListpopFront(SListNode** pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* next = (*pplist)->next;
		free(*pplist);
		*pplist =next;
		
	}
}

6.单链表的查找

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDaTaType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;

}

7.单链表指定位置插入

//后插入
void SListInsertAfter(SListNode** pos, SLTDaTaType x, SLTDaTaType y)
{	
	assert(pos);
	SListNode* cur = *pos;
	cur = SListFind(*pos, x);
	SListNode* newnode = BUYSLTNode(y);
	newnode->next = cur->next;
	cur->next = newnode;
}
//前插入
void SListInsert(SListNode** pos, SLTDaTaType x, SLTDaTaType y)
{
	assert(pos);

	SListNode* cur = *pos;
	SListNode* pre = NULL;
	SListNode* node = BUYSLTNode(y);

	if (cur->next==NULL)
	{
		SListpushFront(pos, y);
		return;
	}
	else
	{
		while (cur->data != x)
		{
			pre = cur;
			cur = cur->next;
		}
		if (pre == NULL)
		{
			SListpushFront(pos, y);
		}
		else
		{
			pre->next = node;
			node->next = cur;
		}
		
	}
}

8.单链表的打印

void SLisprint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur!=NULL)
	{
		printf("%d—>", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

9.单链表的销毁

void SListDistory(SListNode** pplist)
{

	while (*pplist)
	{
		SListNode* next = (*pplist)->next;
		free(*pplist);
		*pplist = next;
	}
}

10.测试运行

#include "SList.h"

test1()
{
	SListNode* plist=NULL;
	//尾加
	SListpushBack(&plist, 3);
	SListpushBack(&plist, 4);
	SLisprint(plist);
	
	//头加
	SListpushFront(&plist, 2);
	SListpushFront(&plist, 1);
	SLisprint(plist);


	//查找单链表,修改值
	SListNode* cur = SListFind(plist, 3);
	cur->data =30;
	SLisprint(plist);


	//尾删
	SListpopBack(&plist);
	SLisprint(plist);

	//头删
	SListpopFront(&plist);
	SLisprint(plist);

	//后插入
	SListInsertAfter(&plist,2,3);
	SListInsertAfter(&plist,30,4);
	SListInsertAfter(&plist,4,5);
	SLisprint(plist);

	printf("\n");
//	前插入
	SListInsert(&plist, 2, 19);
	SLisprint(plist);
	SListInsert(&plist, 19, 6);
	SLisprint(plist);

	指定后删除
	//SListNode* pos = SListFind(plist, 3);
	//SListEraseafter(pos);
	//SLisprint(plist);
	SListDistory(&plist);


}
int main()
{
	test1();
	return 0;
}

小结 

 链表的优点：

在插入和删除操作时，只需要修改被删节点上一节点的链接地址，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

 链表的缺点：

1、没有解决连续存储分配带来的表长难以确定的问题。

2、失去了顺序存储结构随机存取的特性。

总结

上面就是顺序表和单链表的内容，但是还有很多的地方没有介绍的，顺序表和链表在此基础上还可以进行优化，下一篇中将继续深入学习，请大家多多支持,祝大家学有所成。

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布