c++ || 顺序表 单链表及链表习题

文章目录

• 数据
• 线性表
• • 顺序表
  • 链表
  • • 单链表
• 链表习题
• • 中间节点（只遍历一次）
  • 单链表逆置
  • 合并两个有序链表
  • 返回链表中倒数第k个节点
  • 删除链表中倒数第k个结点
  • 删除有序链表中重复的元素
  • 链表的奇偶重排
  • 判断链表中是否有环
  • 链表中环的入口结点
• 顺序表和链表的区别
• • 什么时候用顺序表，链表

数据

• 数据包含数据对象
• 数据对象是数据元素的集合
• 数据元素是数据的基本单位，有若干个数据项组成，数据项是数据元素的不可分割的最小单位

2.数据结构分为逻辑结构和物理结构

数据之间的结构：（数据元素之间的关系，逻辑结构）

• 集合结构：数据元素不能重复
• 线性结构：1：1
• 树形结构：1：N
• 网状结构或图状结构：N：M

物理结构：（存储结构）是指数据的逻辑结构在计算机中的存储形式

• 顺序存储结构
  把数据元素存放在地址连续的存储单元中，数据间的逻辑结构和物理关系是一致的
• 链式存储结构
  把数据元素存放在任意的存储单元里，可以连续也可以不连续，不能反映其逻辑关系，因此需要一个指针存放数据元素的地址
  线性表
  1.特点：

存在唯一的一个被称为"第一个"的数据元素
存在唯一的一个被称为"最后一个"的数据元素
除第一个之外，集合中的每个数据元素均只有一个前驱
除最后一个之外，集合中每个数据元素均只有一个后继

• 线性表中的元素是一对一的
• 线性表中的元素是连续的
• 线性表中的数据元素是有同一类性质的元素
  
  typedef 起别名
  1.概念：把一切合法的变量定义或声明转换成类型声明

typedef unsigned char u_int8;
typedef int Array[10];//Array整形数组类型 开辟十个空间

int main()
{
    Arrar ar = {13,23,45,56} ,br= {1,2,3};
    u_int8 a,b;

3.typedef 与 struct

#define SEQ_INIT_SIZE 10
struct SeqList
{  //定义SeqList结构体类型
  ElemType data[SEQ_INIT_SIZE];
  int cursize;
};
int main()
{  //使用时前面必须要加上struct
  struct SeqList myseq;
  struct SeqList *pseq;
}

typedef struct 
{ 
  ElemType data[SEQ_INIT_SIZE];
  int cursize;
}SeqList; //将SeqList变量变成SeqList类型
int main()
{     //在使用时不需要写struct
   SeqList myseq;
   SeqList *pseq;
}

定义固定大小的数组缺陷：
1.定义的空间在栈上开辟，栈的大小只有1M
2.大开小用

char 1；short 2;int 4;long int 4; long long 8
float 4;double 8; bool 1
1字节（存储单元）有8个bit
函数内定义的变量都在栈区；全局变量、静态变量、静态局部变量在数据区；malloc，new的变量在堆区

• 初始化时传的是地址 void InitSeqList(SeqList *plist)
  {//如果定义的(SeqList plist)会出现 内存泄漏 值传递（未改变主函数中的值）

线性表

• 顺序表：
  1.逻辑相邻，物理相邻
  2.随机访问时间复杂度O(1)
  3.插入时间复杂度O(n) 尾插时间复杂度O(1)
  4.删除时间复杂度O(n) 尾删时间复杂度O(1)
  5.查找Search时间复杂度O(n)

• 单链表：
  1.逻辑相邻，物理上不一定相邻
  2.随机访问时间复杂度O(n)
  3.插入时间复杂度O(1) 不需要挪动数据
  4.删除时间复杂度O(1) 不需要挪动数据
  5.查找Search时间复杂度O(n)

//for(p = plist; p->next != nullptr; p = p->next);//需要前驱 插入和删除操作等
//for(p = plist->next; p != nullptr; p = p->next);//不需要前驱，打印、查找操作等
//插入操作 
       pnewnode->next=p->next;p->next=pnewnode;
//删除操作     
    Node* q=p->next;p->next=q->next;free(q);  p是删除节点的前驱 q是删除节点 
*/

顺序表

1. 顺序表 ：权限更多的数组 逻辑相邻 物理上也相邻
   插入 删除 判空 判满 获取长度 清空 销毁

#include   库函数自带的头文件
#include"sqlist.h"  用户自己定义的头文件
typedef struct SQlist   //定长顺序表
{
	int data[10];
	int length;
}SQList,*PSQlist;

typedef struct DSQlist  //不定长顺序表
{               //需要扩容
	int *data;   //存储空间基址
	int length;  //当前长度(有效长度个数)
    int listsize;//当前分配的存储容量(总的格子数)
}DSQList,*DPSQlist;


void Init_list(PDSQlist ps)//初始化函数
{
	assert(ps != nullptr);
	if (nullptr == ps)
	{
		return;
	}
	ps->data = (int*)malloc(sizeof(int) * INIT_SIZE);
	assert(ps->data != nullptr);
	ps->length = 0;
	ps->listsize = INIT_SIZE;
}
void Inc(PDSQlist ps)  //扩容
{    
	//malloc calloc realloc
    ps->data = (int*)realloc(ps->data, sizeof(int) * ps->listsize*2);
    //ps->length  不改  有效长度个数
    ps->listsize *= 2;
}
void Destroy(PDSQlist ps)  //销毁顺序表
{
	free(ps->data);
	ps->data = nullptr;
	ps->length = 0;
	ps->listsize = 0;
}

• 特点：
  1.简单
  2.随机访问数据时间复杂度O(1)
  3.插入数据时间复杂度为O(n) 尾插时间复杂度为O(1)
  4.插入和删除要挪动大量数据

链表

2.链表 ：逻辑相邻 物理上不一定相邻
不需要挪动数据
数值域
指针域

void Swap（int *a,int *b)   //交换函数
{
    int tmp = *a;
    *a = *b
    *b = tmp;
}

void Swap(int &a,int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

单链表

1.带头节点(实现简单)
2.不带头结点 (头指针 出现二级指针)
头节点是在栈区开辟的不需要释放，而数据节点是在堆区，malloc开辟的空间，销毁单链表需要释放掉全部数据节点

typedef int ELEMTYPE;
typedef struct Node
{
	ELEMTYPE data;    数据域
	struct Node* next;指针域
}Node,*PNode;
//Node * = PNode

• 插入
  单链表插入新节点首先要将新节点的next域指向之前上一个节点的next域，能够保证后边节点不丢失，再将上一个节点的next域指向新节点
  

//头插 头节点之后
bool Insert_head(Node* plist, int val)
{
	assert(plist != nullptr);

	Node *newnode = (Node *)malloc(sizeof(Node) * 1);
	assert(newnode != nullptr);
	newnode->data = val;

	newnode->next = plist->next;  //1
	plist->next = newnode;       //2  顺序不能变

	return true;
}

//尾插
bool Insert_tail(Node* plist, int val)
{
	assert(plist != nullptr);
	//创建新节点
	Node* newnode = (Node*)malloc(sizeof(Node) * 1);
	assert(newnode != nullptr);
	newnode->data = val;

	//找到插入位置
	Node* p = plist;
	for (p; p->next != nullptr; p = p->next);  //需要前驱

   //插入
	newnode->next = p->next;  //1    newnode->next = nullptr;
	p->next = newnode;        //2
     
	return true;
}

//按位置插入
bool Insert_pos(Node* plist, int pos, int val)
{
	assert(plist != nullptr);
	//创建新节点
	Node *pnewnode = (Node*)malloc(sizeof(Node) * 1);
	assert(pnewnode != nullptr);
	pnewnode->data = val;
	//插入位置  插入位置的上一个节点
	Node *p=plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//插入
	pnewnode->next = p->next;//新节点next指向之前上一个节点的next，保证后边节点不丢失
	p->next = pnewnode;
 return true;
}

• 删除
  单链表的按位置删除需要找到删除的上一个节点，申请新的节点指向要删除的节点，然后将要删除节点的上一个节点的next域指向要删除节点的下一个节点的next域，释放删除节点
  

//按位置删除
bool Del_pos(Node* plist, int pos)
{
	assert(plist != nullptr);
	if (pos < 0 || pos >= Get_length(plist))
	{
		return false;
	}
	//找到删除节点的上一个节点
	Node* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//删除节点
	Node* q = p->next;  //申请新指针指向要删除的节点
	p->next = q->next;  //p->next=q->next->next，删除节点的上一个节点的next域指向删除节点的下一个的next域
	free(q);            //释放要删除的节点

	return true;
}


单链表的按值删除，找到删除节点的前驱p，定义一个新的节点q指向要删除的节点(Node* q=p->next)，p->next=q->next(跳过q)，释放删除节点q的空间
//按值删除 释放内存
bool Del_val(Node* plist, int val)
{
	assert(plist != nullptr);
	Node* p=Get_prior(plist,val);
	if (p == nullptr)
	{
		return false;
	}

	Node* q = p->next;
	p->next = q->next;
	free(q);

	return true;
}

• 销毁
  单链表的销毁 =>销毁单链表需要释放掉全部数据节点
  两种销毁方式都可以 必须掌握第一种

第一种方法
头节点是在栈区开辟的不需要释放，而数据节点是在堆区，malloc开辟的空间

void Destroy(Node* plist)//不要就释放掉 将malloc来的直接释放掉
{                        //一直头删 
	assert(plist != nullptr);
	while (plist->next != nullptr)
	{
		Node* p = plist->next;
		plist->next = p->next;
		free(p);
	}
	plist->next = nullptr;
}

第二种方法
p=plist->next;
plist->next=nullptr; //直接将头节点与数据节点断开

void Destroy2(Node* plist)
{
	assert(plist != nullptr && plist->next != nullptr);
	Node* p = plist->next;
	Node* q =p->next; 
	plist->next = NULL;

	while (p != nullptr)
	{
		q = p->next;
		free(p);
		p = q;
	}
}

• 查找
  单链表查找值为val的前驱 Node* p=plist; 从头节点开始
  查找值为val的后继 Node* p=Search(plist,val);找到值为val的节点位置，返回下一个节点p->next;

//查找val，返回地址
Node* Search(Node* plist, int val)
{
	assert(plist != nullptr);
	for (Node* p=plist->next;p!=nullptr;p=p->next)
	{
		if (p->data == val)
		{
			return p;
		}
	}
	return nullptr;
}

//寻找值为val节点的前驱
Node* Get_prior(Node* plist, int val)
{
	assert(plist != nullptr);
	Node* p=plist;
	for (p; p->next != nullptr; p = p->next)
	{
		if (p->next->data == val)
		{
			return p;
		}
	}
}

//寻找值为val节点的后继
Node* Get_next(Node* plist, int val)
{
	assert(plist != nullptr);
	Node* p = Search(plist, val);
	if (p == nullptr)
	{
		return NULL;
	}
	return (p->next);
}

• 排序（从小到大）

	void Sort()
	{
		Node* p = head->next;    //第一个数据节点
		int n = GetLength();
		if (head == nullptr || head->next == nullptr) return ;
	
		while (p != nullptr)   //p的位置确定  
		{
			Node* q = p->next;   //p的下一个节点 用来比较
			while (q != nullptr)
			{
				if (p->data > q->data)
				{
					Msort(p->data, q->data);
				}
				q = q->next;      //将q向后遍历全部 q与之后所有节点比较
//每次都会选出p结点及之后最小值
			}
			p = p->next;     //在进行第二个节点的全部遍历
		}	
	}

链表习题 中间节点（只遍历一次）

**快慢指针 p，q；p = p->next->next；q=q->next

Node* FindAvenode()
{
	

单链表逆置

单链表的逆置
#include"list.h"
1）一直进行头插
P指向第一个数据节点 q指向p的下一个节点
plist->next=nullptr;
当p！=nullptr；对p进行头插

void Reverse(PNode plist)          //单链表的逆置
{                                   //从第一个数据节点开始 不为空则将该节点进行头插
	assert(plist != nullptr);       //保证头节点存在 
	Node* p = plist->next;          //p指向第一个有效节点的地址(可能为nullptr)
	plist->next = nullptr;          //很关键 
	Node* q =nullptr;               //给q赋值，防止野指针
	while (p != nullptr)
	{
		
		q = p->next; 
		
		Insert_head(plist, p->data);  //节点数据进行头插
		free(p);                      //释放掉p
		p = q;
	}
}    

2）不调用头节点 先将后面的节点逆置 再将plist->next指向逆置完之后的第一个有效值

//不调用头节点 先将后面的节点逆置 再将plist->next指向逆置完之后的第一个有效值
// 第一个节点的next指向nullptr
void Reverse2(PNode plist)
{
	assert(plist != nullptr);
	if (plist == nullptr || plist->next == nullptr || plist->next->next == nullptr)
	{
		return;
	}
	Node* p = plist->next;   //指向第一个有效节点
	Node* q = p->next;       //指向第二个有效节点
	Node* r = nullptr;       //指向剩余的未处理的所有节点的第一个节点  防止丢失
	
	p->next = nullptr;     //第一个节点会变成最后一个 所以要将p->next置为空
	while (q != nullptr)
	{
		r = q->next;
		q->next = p;       //调转方向
		p = q;
		q = r;
	}
	plist->next = p;
}

合并两个有序链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0 le n le 10000≤n≤1000，-1000 le 节点值 le 1000−1000≤节点值≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

思路：将链表头小的作为主链表，将另一个链表插入其中

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==NULL){return pHead2;}
        if(pHead2==NULL){return pHead1;}
        ListNode* tmp = NULL;
        if(pHead1->val >pHead2->val)
        {
            tmp = pHead1;
            pHead1=pHead2;
            pHead2=tmp;
        }
        ListNode* res = pHead1;
        while(pHead1->next&&pHead2)
        {
            if(pHead1->next->val>pHead2->val)
            {
                tmp = pHead1->next;
                pHead1->next=pHead2;
                pHead2=pHead2->next;
                pHead1->next->next = tmp;
            }
            pHead1=pHead1->next;
        }
        if(pHead1->next == NULL)
        {
            pHead1->next=pHead2;
        }
        return res;
    }
};

返回链表中倒数第k个节点

快慢指针 都从头节点开始，通过循环快指针走k步，在将快指针走到空同时慢指针也在走，当快指针走完链表时，慢指针就指向倒数第k个

Node* Getback_num(PNode plist, int k)   //找到倒数的第k个元素
{
	assert(plist != nullptr && k > 0 && k<=Get_length(plist));
	if (plist == nullptr ||k<=0||k>Get_length(plist))
	{
		return nullptr;
	}
	Node* p = plist;
	Node* q = plist;
	for (int i = 0; i < k; i++)//倒数第k个 就让k走几步
	{
     	if(p==NULL)return NULL;
		p = p->next;
	}
	while (p != nullptr)       //从p走到空 q就指向倒数第k个
	{
		p = p->next;
		q = q->next;
	}
	return q;
	//int n = Get_length(plist);
	//Node* p = plist->next;
	//for (int i = 0; i < n - k; i++)
	//{
	//	p = p->next;
	//}
	//return p;
}

删除链表中倒数第k个结点

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，
给出的链表为: 1→2→3→4→5, n= 2
删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5.

思路：**快慢指针 都从头节点开始，通过循环快指针走k步，在将快指针走到空同时慢指针也在走，当快指针走完链表时，慢指针就指向倒数第k个 **

class Solution {
public:
    
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        if(head==NULL)
        {
            return head;
        }
        ListNode* newhead = new ListNode(0);
        newhead->next=head;
        head=newhead;
        ListNode* p = head;
        for(int i=0;i
            p=p->next; 
        }
        ListNode* q=head;
        while(p->next!=NULL)
        {//q指向要删除节点的前一个
            p=p->next;
            q=q->next;
        }
        ListNode* tmp = q->next;
        q->next=tmp->next;
        delete tmp;
        return head->next;
    }
};

删除有序链表中重复的元素

描述：
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3.
思路：
要删除有序链表当中重复的元素使所有重复元素只出现一次，在这个过程当中，可以选定两个链表指针i和j，通过设定i为head，j为i.next，依次通过循环将重复元素的个数减为0，如果没有发现重复的元素，令j = j.next，再次进行判断；如果发现有重复元素，令i.next = j.next，除掉重复元素，依次递归进行判断。

class Solution {
public:
    
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if(head == NULL)
        {
            return head;
        }
        ListNode* p = head;
        while(p!=NULL)
        {
            for(ListNode* q = p->next; q!=NULL; q = q->next)
            {
                if(p->val == q->val)
                {
                    p->next = q->next;
                }
            }
            p = p->next;
        }
        return head;
        
    }
};

链表的奇偶重排

描述：
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。

思路：
使用两个链表
将所有的奇结点放在p的后面
偶结点放在q的后面
最后将奇链表尾接到偶链表的头

class Solution {
public:
    
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode* p = head;
        ListNode* q = head->next;
        ListNode* p1 = p;
        ListNode* q1 = q;
        while(p1->next != NULL&& q1->next != NULL)
        {
            p1->next = q1->next;
            p1 = p1->next;
            q1->next = p1->next;
            q1 = q1->next;
        }
        p1->next = q;
        
        return p;
    }
};

判断链表中是否有环

描述：
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
思路：
双指针，fast 与 slow。
它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
图解：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL) return NULL;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && slow)
        {
            slow = slow->next;
            if(fast->next!=NULL)
            {
                fast = fast->next->next;
            }
            else 
            {
                return false;
            }
            
            if(slow == fast)
            {
                return true;
            }
        }
        return false;
    }
};

链表中环的入口结点

描述：
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
思路：
双指针 先判断有环 有环则查找出入环节点
快慢指针相遇后，将fast（或slow）指针移到链表头部，然后以相同的速度移动，当它们相遇时，相遇的点即为环的入口

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
    if(!pHead) return NULL;
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) //有环
            {
                fast= pHead;
                while(fast!=slow)
                {
                    slow=slow->next;
                    fast = fast->next;
                }
                return fast;
            }
        }
        
        return NULL;
    }
};

顺序表和链表的区别

	顺序表	链表
底层实现	连续存储的容器，动态数组，在堆上分配空间	动态链表，在堆上分配空间
空间利用率	不易造成内存碎片，空间利用率高	结点不连续，易造成内存碎片，小元素使节点密度低，空间利用率低
查询元素	find O(n) binary_search O(logn)	find O(n)
插入删除	插入：尾插(空间够)：O(1),(空间不够)：需要内存申请和释放，对之前数据进行拷贝。中间插入(空间够)：内存拷贝,(空间不够)：需要内存申请和释放，对之前数据进行拷贝。删除：最后删除：O(1),中间删除：内存拷贝，不需要释放内存	插入（内存申请）：insert O(1),push_front O(1),push_back O(1);删除(内存释放)：pop_back O(1),pop_front O(1),Erase O(1)

什么时候用顺序表，链表

1. 需要高效的随机存取，很少使用插入和删除操作：用顺序表
2. 需要大量的删除和插入操作，随机存取很少使用：用链表