网上移动厅官方网站_旅游网页设计说明书_湖南seo网站开发_怎样制作一个自己的网站

线性表

线性表是数据结构中最基本且常用的一种形式，用于存储具有线性关系的数据元素。其特点是数据元素之间存在一对一的顺序关系。线性表（linear list）是n个具有相同特性的数据元素的有限序列。常见的线性表：顺序表、链表、栈、队列、字符串...

两种主要存储方式： 

 顺序表（顺序储存）

• 定义：用一组连续的内存单元依次存储数据元素。

• 特点：

  • 随机访问：通过下标直接访问元素，时间复杂度为O(1)。

  • 插入和删除效率低：需要移动大量元素，时间复杂度为O(n)。

  • 存储密度高：仅存储数据元素，无需额外空间。

• 实现：通常使用数组。

• 类型：静态顺序表：使用定长数组存储元素。动态顺序表：使用动态开辟的数组存储。

//静态顺序表
struct SeqList
{int arr[100];//定长数组int size;//顺序表当前有效的数据个数
};

//动态顺序表
typedef struct SeqList
{SLDataType* arr;int size;//有效的数据个数int capacity;//空间大小
}SL;

 动态顺序表的实现 SeqList.h

#include <stdio.h>
#include <stdlib.h>
#include<assert.h>//typedef int SLDataType;//方便后续类型的替换typedef struct SeqList
{SLDataType* arr;int size;//有效的数据个数int capacity;//空间大小
}SL;//顺序表初始化
void SLInit(SL* ps);//顺序表的销毁
void SLDestroy(SL* ps);
void SLPrint(SL s);//头部插入/尾部插入
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);//尾部删除/头部删除
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);//查找
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include"SeqList.h"
void SLInit(SL* ps)
{ps->arr= NULL;ps->size = ps->capacity = 0;
}void SLDestroy(SL* ps)
{if (ps->arr){free(ps->arr);}ps -> arr = NULL;ps->size = ps->capacity = 0;}
void SLCheckCapacity(SL* ps)
{//插入数据之前先看空间够不够if (ps->capacity == ps->size){//申请空间//增容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail!");exit(1);//直接退出程序，不再继续执行//return;}//空间申请成功ps->arr = tmp;ps->capacity = newcapacity;}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{温柔的方式//if (ps == NULL)//{//	return;//}assert(ps);//等价于assert(ps!=NULL)SLCheckCapacity(ps);ps->arr[ps->size++] = x;//等价于//ps->arr[ps->size]=x;//++ps->size;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//先让顺序表中已有的数据往后移动for (int i = ps->size; i>0; i--){ps->arr[i] = ps->arr[i - 1];//arr[1]=arr[0]}ps->arr[0] = x;ps->size++;
}
//void SLPrint(SL s)
//{
//	for (int i = 0; i < s.size; i++)
//	{
//		printf("%d ", s.arr[i]);
//	}
//	printf("\n");
//}
//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//顺序表不为空//ps->arr[ps->size - 1] = -1;--ps->size;
}
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//顺序表不为空//数据整体往前挪for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1];}ps->size--;}
//在指定位置之前插入数据
//pos表示下标
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//插入数据:空间够不够SLCheckCapacity(ps);//让pos及之后的数据往后移动一位for (int i =ps->size; i > pos ; i--){ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos]}ps->arr[pos] = x;ps->size++;}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i<ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]}ps->size--;
}//查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了return i;}}//没有找到 无效下标return -1;
}

链表 

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

• 特点：

  • 插入和删除效率高：只需修改指针，时间复杂度为O(1)。

  • 随机访问效率低：需要从头遍历，时间复杂度为O(n)。

  • 存储密度低：需要额外空间存储指针。

• 类型：

  • 单链表：每个节点只包含指向下一个节点的指针。

  • 双向链表：每个节点包含指向前后节点的指针。

  • 循环链表：尾节点指向头节点，形成环。

单向或者双向：

单链表 

无头单向不循环单链表的实现 SList.h 

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//定义节点的结构
//数据+指向下一个节点的指针
typedef int SLTDataType;typedef struct SListNode
{int 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* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);

SList.c 

#include "SList.h"void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur)//pcur!=NULL{printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
SLTNode*  SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//*pphead就是指向第一个结点的指针//空链表和非空链表SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;} else{//要先找到尾节点，再将尾节点和新节点连接起来SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail指向的就是尾节点ptail->next = newnode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//空链表和非空链表SLTNode* newnode = SLTBuyNode(x);// newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{//链表不能为空assert(pphead && *pphead);//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//链表有多个节点else{//找尾SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}
void SLTPopFront(SLTNode** pphead)
{//链表不能为空assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//pcur==NULLreturn NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//链表不为空 pos就说明链表不可能为空assert(pphead && *pphead);assert(pos);SLTNode* prev = *pphead;//若pos==*pphead;说明是头插if (pos == *pphead){SLTPushFront(pphead, x);}else{while (prev->next != pos){prev = prev->next;//pos的前一个节点}SLTNode* newnode = SLTBuyNode(x);newnode->next = pos;prev->next = newnode;}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//pos是头节点if (pos == *pphead){//头删SLTPopFront(pphead);}//不是else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos&&pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}void SListDesTroy(SLTNode** pphead)
{//销毁一个一个节点assert(pphead&&*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

 双链表

 带头双向循环链表的实现 List.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//双向链表
//带头双向循环链表
//节点=数据+指向下一个节点的指针+指向前一个节点的指针//双向链表为空时，此时链表中只剩下一个头节点
typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//声明双向链表中提供的方法//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDesTroy(LTNode* phead);
void LTprint(LTNode* phead);
//插入数据之前，链表必须初始化到只有一个头结点的情况//哨兵位节点不能被删除，节点的地址也不能发生改变
//一级指针即可 （不改变哨兵位的位置）
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void PopBack(LTNode* phead);
//头删  
void PopFront(LTNode* phead);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点处的数据 
void LTErase(LTNode* pos);LTNode* LTfind(LTNode* phead, LTDataType x);

List.c

#include "List.h"void LTprint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);} node->data = x;node->next = node->prev = node;//不能置为NULL 需要满足双向链表的循环条件return node;
}
//void LTInit(LTNode** pphead)
//{
//	//给双向链表创建一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode; phead->prev = newnode;//这两行不能交换位置}
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
//尾删
void PopBack(LTNode* phead)
{//链表必须有效且链表不能为空（只有一个哨兵位）assert(phead&&phead->next!=phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//删除free(del);del = NULL;
}
//头删  
void PopFront(LTNode* phead)
{assert(phead && phead->next != NULL);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}
LTNode* LTfind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}
//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next=newnode;
}
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev= pos->prev;pos->prev->next= pos->next;free(pos);pos = NULL;
}
//销毁 
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;
}

对比

链表例题

1.面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k)
{struct ListNode* fast,*slow;fast = slow = head;//fast先走k步while(k--){fast=fast->next;}//然后再一起走while(fast){fast=fast->next;slow=slow->next;}return slow->val;
}

2. 206. 反转链表 - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
//思路1：创建新的链表将原链表的节点拿过来头插
struct ListNode* reverseList(struct ListNode* head) 
{struct ListNode* cur= head ;struct ListNode* newhead = NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

3.876. 链表的中间结点 - 力扣（LeetCode） 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) 
{struct ListNode* fast,* slow;fast = head, slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

4.链表的回文结构_牛客题霸_牛客网 

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*///找到中间节点 然后逆置中间节点的后面节点 然后再进行比较
class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow = head;struct ListNode* fast = head;while (fast&&fast->next)//不能交换位置{slow = slow->next;fast = slow->next->next;}//此时slow指向的刚好是中间节点return slow;}struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur=head;struct ListNode* newhead=NULL;while(cur){struct ListNode*next=cur->next;//头插cur->next=newhead;newhead=cur;cur=next;}return newhead;}bool chkPalindrome(ListNode* A){struct ListNode* mid=middleNode(A);struct ListNode* rmid=reverseList(mid);while(rmid&&A){if(rmid->val!=A->val){return false;}rmid=rmid->next;A=A->next;}return true;}
};

5.203. 移除链表元素 - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode Listnode;//思路:创建新的链表 将值！=val的 数字 尾插到新的链表当中 然后返回新的链表的头
struct ListNode* removeElements(struct ListNode* head, int val) 
{Listnode* newhead,*newtail;newhead = newtail = NULL;Listnode* pcur = head;while(pcur){if(pcur->val!=val){if(newhead==NULL){newhead=newtail=pcur;}else{newtail->next=pcur;newtail=newtail->next;}}pcur=pcur->next;}if(newtail)newtail->next=NULL;return newhead;
}

6.21. 合并两个有序链表 - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///创建新链表 遍历原链表 将节点值小的拿到新链表中进行 尾插
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1==NULL && list2==NULL)return NULL;if(list1==NULL)return list2;if(list2==NULL)return list1;struct ListNode* l1=list1;struct ListNode* l2=list2;struct ListNode* newhead, *newtail;newhead=newtail= (struct ListNode*)malloc(sizeof(struct ListNode));while(l1 && l2){if(l1->val < l2->val){newtail->next=l1;newtail=newtail->next;l1=l1->next;}else{newtail->next=l2;newtail=newtail->next;l2=l2->next;}}if(l1){newtail->next=l1;}if(l2){newtail->next=l2;}struct ListNode* ret=newhead->next;free(newhead);newhead=NULL;return ret;
}

7.160. 相交链表 - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///相交：判断尾指针 用尾地址判断 不要用值判断//思路：A链表的节点依次和B链表所有节点比较，A某个节点和B某个节点相等，这个节点就是交点 4typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{ListNode* curA=headA;ListNode* curB=headB;int lenA=0;int lenB=0;while(curA->next){curA=curA->next;++lenA;}while(curB->next){curB=curB->next;++lenB;}if(curA!=curB){return NULL;}int gap=abs(lenA-lenB);//假设ListNode* longlist=headA;ListNode* shortlist=headB;if(lenA<lenB){longlist=headB;shortlist=headA;}while(gap--){longlist=longlist->next;}while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}

8.链表分割_牛客题霸_牛客网

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode *greathead, *greattail;struct ListNode *smallhead, *smalltail;struct ListNode *pcur = pHead;greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));smallhead = smalltail = (struct ListNode*)malloc(sizeof(struct ListNode));while(pcur){if(pcur->val < x){smalltail->next = pcur;smalltail = pcur;}else {greattail->next = pcur;greattail = pcur;}pcur = pcur -> next;}smalltail -> next = greathead->next;greattail -> next = nullptr;return smallhead -> next;}
};