数据结构学习笔记——线性表

2024-02-01 19:02:58

线性表的顺序表示（顺序表）

特点：

1.随机访问：即可以在O(1)时间内找到第i个元素
2.存储密度高，每个节点只存储数据元素
3.扩展容量不方便（即使采用动态分配，扩展长度的时间复杂度也比较高）
4.插入、删除操作不方便，需要移动大量元素

顺序表的静态分配

#define MAXsize 100 //静态顺序表的最大容量
typedef struct//静态顺序表结构
{
	int data[MAXsize];
	int length;
}Sqlist;

静态顺序表初始化

void Static_Initlist(Sqlist& L)//初始化静态顺序表
{
	L.length = 0;
	for (int i = 0; i < MAXsize; i++)
	{
		L.data[i] = 0;
	}
}

顺序表的动态分配

typedef struct//动态顺序表结构
{
	int* data;//指示动态分配数组的指针
	int length, Maxsize;
}Seqlist;

动态顺序表初始化

#define Initsize 100//动态初始容量
void Dynamic_Initlist(Seqlist& L)//初始化动态顺序表
{
	L.data = new int[Initsize];//申请堆
	L.length = 0;
	L.Maxsize = Initsize;
}

动态顺序表的动态增加

void IncreaseSize(Seqlist& L, int len)//增加动态顺序表的长度
{
	int* p = L.data;
	L.data = new int[L.Maxsize + len];//申请一快足够大的堆内寸
	for (int i = 0; i < L.length; i++)//将原堆内存中的数据赋值到新内存的对应位置
	{
		L.data[i] = p[i];
	}
	L.Maxsize += len;//顺序表的最大长度＋len
	delete p;//释放原堆内存
}

顺序表的基本操作

插入操作

bool ListInsert(Sqlist& L, int i, int e)//插入操作 i:位置 e:插入元素
{
	if (i<1 || i>L.length + 1)return 0;//判断i的范围是否有效
	if (i > MAXsize)return 0;//当前空间以满不能插入
	for (int j = L.length; j >= i; j--)//将i个元素及之后的元素后移一位
	{
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;//将元素e插入到位置i
	L.length++;//L的长度增加1
	return 1;
}

最好情况：在表尾插入（i=n+1）元素后移指令不执行，时间复杂度为O(1)
最坏情况：在表头插入（i=1）元素后移执行n次，时间复杂度为O(n)
平均情况：假设新元素插入到任何一个位置的概率都是相同的，即i=1,2,3…,length+1的概率都是P=1/(n+1),节点平均移动的次数为=nP+(n-1)P+(n-2)P+…+1P=n(n+1)/2 * 1/(n+1) =n/2次，时间复杂度为O(n)

删除操作

bool ListDelete(Sqlist& L, int i, int& e)//删除操作 i删除元数的位置 e接收被删除元素的值的变量
{
	if (i<1 || i>L.length)return 0;//判断i的范围是否有效
	e = L.data[i - 1];//被删除元素赋值给e
	for (int j = i; j < L.length; j++)
	{
		L.data[j - 1] = L.data[j];//将第i个位置后的元素前移
	}
	L.length--;//线性表长度减一
	return 1;
}

最好情况：删除表尾元素，不需要移动其他元素（i=n），时间复杂度为O(1)
最坏情况：删除表头元素（i=1），需要移动除表头外的所有元素，时间复杂度为O(n)
平均情况：假设删除一个元素的概率相同，即i=1,2,3…,length的概率为P=1/n,平均循环次数=(n-1)P+(n-2)P+…1P=n(n-1)/2 * 1/n=(n-1)/2,时间复杂度为O(n)

查找操作

int LocateInt(Sqlist L, int e)//按值查找（顺序查找） e:查找的元素
{
	int i;
	for (i = 0; i < L.length; i++)//遍历查找
	{
		if (L.data[i] == 3)return i + 1;
	}
	return -1;//查找失败返回-1
}

最好情况：查找元素就在表头，仅需比较一次，时间复杂度O(1)
最坏情况：查找元素在表尾或不存在，需要比较n次时间复杂度O(n)
平均情况：假设查找一个元素的概率相同，即i=1,2,3…,length的概率为P=1/n,平均循环次数=nP+(n-1)P+(n-2)P+…1P=n(n+1)/2 * 1/n=(n+1)/2,时间复杂度为O(n)

线性表的链式表示（链表）

定义一个链表

typedef struct {//单链表结构体
    int data;
    LNode* next;
}LNode,*LinkList;//  LinkList 为指向LNode类型的指针 即 LinkList替换为LNode * 类型

链表初始化

带头节点初始化

bool InitList(LinkList& L)
{
    L = new LNode;
    if (L == NULL)
        return 0;//分配失败
    L->next = NULL;
    return 1;
}

不带头节点初始化

bool InitList(LinkList& L)//不带头节点链表初始化
{
    L = NULL; //空表 防止遗留脏数据
    return 1;
}

链表的基本操作

带头节点插入操作

bool ListInsert(LinkList& L, int i, int e)//在带头节点的链表中第i个位置插入元素e
{
    if (i < 1)return 0;
    LNode* p;//创建指针p指向当前头节点
    p = L;
    int j = 0;
    while (p != NULL && j < i - 1)//循环找到第i-1个节点
    {
        p = p->next;
        j++;
    }
    if (p == NULL)return 0;//检测链表中是否有第i个节点
    LNode* s = new LNode;//创建一个节点、
    s->data = e;
    s->next = p->next;//将新节点插入p（i-1）节点与第i个节点之间
    p->next = s;
    return true;
}

平均时间复杂度O(n)

不带头节点的插入操作

bool ListInsert(LinkList& L, int i, int e)//不带头节点的链表中第i个位置插入元素e
{
    if (i < 1)return 0;
    if (i == 1)
    {
        LNode* s = new LNode;
        s->data = e;
        s->next = L;
        L = s;//头指针指向第一个节点
    }
    LNode* p;//创建指针p指向当前第一个节点
    p = L;
    int j = 1;
    while (p != NULL && j < i - 1)//循环找到第i个节点
    {
        p = p->next;
        j++;
    }
    if (p == NULL)return 0;//检测链表中是否有第i个节点
    LNode* s = new LNode;//创建一个节点、
    s->data = e;
    s->next = p->next;//将新节点插入p（i-1）节点与第i个节点之间
    p->next = s;
    return true;
}

平均时间复杂度O(n)

给定节点后插

bool InsertNextNode(LNode* p, int e)//在指定节点后插入节点
{
    if (p == NULL)return 0;
    LNode* s = new LNode;
    if (s == NULL)return 0;//申请内存失败
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;
}

时间复杂度O(1)

给定节点前插

插入到给定节点后面，然后交换新节点与给定节点的值

bool InsertFrontNode(LNode* p, int e)//在指定节点前插入节点
{
    if (p == NULL)return 0;
    LNode* s = new LNode;
    if (s == NULL)return 0;//内存分配失败
    s->next = p->next;//将新节点插入指定节后然后交换p节点和新节点的data
    p->next = s;
    s->data = p->data;
    p->data = e;
    return 0;
}

时间复杂度O(1)

按位序删除节点（带头节点）

bool ListDelete(LinkList& L, int i, int& e)//按为序删除节点（带头节点）
{
    if (i < 1)return 0;
    LNode* p;//指针p指向当前节点
    p = L;
    int j = 0;
    while (p != NULL && j < i - 1)//循环遍历找到第i-1个节点
    {
        p = p->next;
        j++;
    }
    if (p == NULL)return 0;//i值不合法
    if (p->next = NULL)return 0;//第i-1个节点之后在无节点
    LNode* q = p->next;//新建指针指向p的后驱节点
    e = q->data;//获取要删除的第i个节点的值
    p->next = q->next;//将q节点从链表中断开
    delete q;
    return 1;
}

最坏、平均时间复杂度O(n)
最快时间复杂度O(1)

删除指定节点

交换删除节点p与后继节点的数据，然后删除p的后继节点

bool DeleteNode(LNode *p)//删除指定节点
{
    if (p == NULL)return 0;
    LNode* q = p->next;//创建指针指向p后继的节点
    p->data = p->next->data;//p和后继节点交换数据
    p->next = q->next;//将q节点从中断开
    delete q;
    return 1;
}

时间复杂度O(1)

码农公寓

线性表的顺序表示（顺序表）

线性表的链式表示（链表）

相关文章