顺序表

#include<iostream>
using namespace std;
//动态数组实现顺序表
struct List
{
    int *arr;
    int lenth;
};
//创建顺序表
List createList()
{
    List list;
    list.lenth=0;
    list.arr=new int[100];
    return list;
}
//插入操作
void insert(List& list,int pos,int val)
{
    if(list.lenth==100)
    {
        cout<<"顺序表已满,插入失败!"<<endl;
        return;
    }
    for(int i=list.lenth-1;i>=pos;i--)
        list.arr[i+1]=list.arr[i];
    list.arr[pos]=val;
    list.lenth++;
}
//查找操作
int find(List list,int val)
{
    for(int i=0;i<list.lenth;i++)
    {
        if(list.arr[i]==val)
            return i;
    }
    return -1;
}
//输出操作
void print(List list)
{
    for(int i=0;i<list.lenth;i++)
        cout<<list.arr[i]<<" ";
    cout<<endl;
}
int main()
{
    List list=createList();
    insert(list, 0, 1);//pos=0是插入第一个位置
    insert(list, 1, 2);
    print(list);

    int index = find(list, 2);
    cout << index << endl;
    return 0;
}

单链表

#include<iostream>
using namespace std;
//节点定义
struct Node
{
    int val;
    Node* next;
    Node(int x):val(x),next(NULL){};
};

//头插法创建单链表
Node* CreateListByHead(int a[],int n)
{
    Node* head=NULL;
    for(int i=0;i<n;i++)
    {
        Node* node=new Node(a[i]);
        if(head==NULL)
            head=node;
        else
        {
            node->next=head;
            head=node;
        }
    }
    return head;
}

//带虚拟头结点 头插法创建单链表
Node* CreateListWithHead(int a[],int n)
{
    Node* dummy=new Node(-1);
    for(int i=0;i<n;i++)
    {
        Node* node=new Node(a[i]);
        node->next=dummy->next;
        dummy->next=node;
    }
    return dummy->next;
}

//尾插法建立单链表
Node* CreateListByTail(int a[],int n)
{
    Node* head=NULL;
    Node* tail=NULL;
    for(int i=0;i<n;i++)
    {
        Node* node=new Node(a[i]);
        if(head==NULL)
        {
            head=node;
            tail=node;
        }
        else
        {
            node->next=tail->next;
            tail->next=node;
        }
    }
    return head;
}

//带虚拟头结点 尾插法建立单链表
Node* CreateListWithTail(int a[],int n)
{
    Node* dummy=new Node(-1);
    Node* tail=dummy;
    for(int i=0;i<n;i++)
    {
        Node* node=new Node(a[i]);
        node->next=tail->next;
        tail=node;
    }
    return dummy->next;
}

//按序号查找结点
Node *GetNodeByIndex(Node* head,int i)
{
    Node* p=head;
    while(i--)p=p->next;
    return p;
}

//按值查找结点
Node *GetNodeByVal(Node* head,int e)
{
    for(Node* p=head;p;p=p->next)
    {
        if(p->val==e)
        return p;
    }
    return NULL;
}

//在下表为index的位置上插入值为x的新节点
void insertNode(Node* head, int index, int x)
{
    if(index==0)
    {
        auto p=new Node(x);
        p->next=head;
        head=p;
        return;
    }
    Node *p = head;
    for (int i = 0; i < index - 1; i ++)
        p = p->next;
    Node *newNode = new Node(x);
    newNode->next = p->next;
    p->next = newNode;
}

//删除链表下标为index的节点
void deleteNode(Node* head, int index)
{
    if(index==0)
    {
        head=head->next;
        return;
    }
    Node *p = head;
    for (int i = 0; i < index - 1; i ++)
        p=p->next;
    p->next=p->next->next;
}

// 遍历链表
void print(Node *head)
{
    for (Node *p = head; p; p = p->next)
        cout<<p->val<<" ";
    cout<<endl;
}


int main() 
{
    int a[] = {1, 5, 6, 2, 9, 2};
    int n = sizeof(a) / sizeof(int);
    Node *head = CreateListByTail(a, n);
    print(head);

    insertNode(head, 2, 0);
    print(head);

    deleteNode(head, 2);
    print(head);

    return 0;
}

静态链表

const int N = 10010;
struct Node
{
    int val;
    int next;
} q[N];

1.设计一个递归算法，删除不带头结点的单链表工中所有值为的结点

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int val;
    Node* next;
    Node(int val):val(val),next(NULL){}
};
Node *createLinkedList(int vals[], int n)
{
    Node* dummy=new Node(0);
    Node* cur=dummy;
    for(int i=0;i<n;i++)
    {
        Node* p=new Node(vals[i]);
        cur->next=p;
        cur=p;
    }
    return dummy->next;
}
void print(Node* head)
{
    for(Node* p=head;p;p=p->next)
        cout<<p->val<<' ';
    cout<<endl;
}
Node *removeAllXNodes(Node* head,int x)
{
    if(head==NULL)
        return NULL;
    if(head->val==x)
        return removeAllXNodes(head->next,x);
    else
        head->next=removeAllXNodes(head->next,x);
    return head;
}
int main()
{
    int a[] = {1, 2, 3, 2, 3, 5, 7, 2}, n = sizeof(a) / sizeof(int);
    Node *head = createLinkedList(a, n);
    print(head);
    print(removeAllXNodes(head, 2));
    return 0;
}
##迭代写法

Node removeAllXNodes(Node head,int x)
{
Node pre=new Node(0);
Node cur=head;
pre->next=cur;
while(cur)
{
if(cur->val==x)
{
pre->next=cur->next;
cur=cur->next;
}
else
{
pre=pre->next;
cur=cur->next;
}
}
return head;
}

##2.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值

void reverseprint(Node* head)
{
if(!head)return;
reverseprint(head->next);
cout<[HTML_REMOVED]val<<’ ‘;
}

###迭代写法

void reverseprint(Node head)
{
stack[HTML_REMOVED]s;
Node cur=head->next;
while(cur)
{
s.push(cur->val);
cur=cur->next;
}
while(s.size())
{
cout<<s.top()<<’ ‘;
s.pop();
}
}

##3.试编写在带头结点的单链表L中
删除一个最小值结点的高效算法(假设最小值结点是唯一的）

Node deleteMinNode(Node dummy)
{
Node premin=dummy;
Node min=dummy->next;
for(Node* cur=dummy;cur->next;cur=cur->next)
{
if(cur->next->val[HTML_REMOVED]val)
{
min=cur->next;
premin=cur;
}
}
premin->next=min->next;
delete min;
return dummy;
}

##4.试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为 O(1)
acwing 35

class Solution {
public:
ListNode reverseList(ListNode head) {
ListNode pre=NULL,cur=head;
while(cur)
{
auto q=cur->next;
cur->next=pre;
pre=cur;
cur=q;
}
return pre;
}
};

迭代写法 手动模拟 嗯想想不出来

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next)
            return head;
        auto p=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return p;
    }
};

##5.有一个带头结点的单链表 L，设计一个算法使其元素递增有序

include[HTML_REMOVED]

using namespace std;
struct Node
{
int val;
Node next;
Node(int val):val(val),next(NULL){}
};
Node createLinkedList(int vals[], int n)
{
Node dummy=new Node(0);
Node cur=dummy;
for(int i=0;i[HTML_REMOVED]next=p;
cur=p;
}
return dummy->next;
}
void print(Node head)
{
for(Node p=head;p;p=p->next)
cout<[HTML_REMOVED]val<<’ ‘;
cout<[HTML_REMOVED]a;
for(auto cur=head;cur;cur=cur->next)
{
a.push_back(cur->val);
}
sort(a.begin(),a.end());
Node dummy=new Node(0);
Node cur=dummy;
for(int x : a)
{
cur->next=new Node(x);
cur=cur->next;
}
return dummy->next;
}
int main()
{
int a[] = {1, 2, 3, 2, 0, 3, 5, 7, 2}, n = sizeof(a) / sizeof(int);
Node *head = createLinkedList(a, n);
print(head);
print(sortList(head));
return 0;
}

##6.设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值 (作为函数参数给出)之间的元素的元素 (若存在)

include[HTML_REMOVED]

using namespace std;
struct Node
{
int val;
Node next;
Node(int val):val(val),next(NULL){}
};
Node createLinkedList(int vals[], int n)
{
Node dummy=new Node(0);
Node cur=dummy;
for(int i=0;i[HTML_REMOVED]next=p;
cur=p;
}
return dummy->next;
}
void print(Node head)
{
for(Node p=head;p;p=p->next)
cout<[HTML_REMOVED]val<<’ ‘;
cout<[HTML_REMOVED]next;
while(cur)
{
if(cur->val>=l&&cur->val<=r)
{
pre->next=cur->next;
cur=cur->next;
}
else
{
pre=pre->next;
cur=cur->next;
}
}
return dummy->next;
}
int main()
{
int a[] = {1, 2, 3, 2, 0, 3, 5, 7, 2}, n = sizeof(a) / sizeof(int);
Node head = createLinkedList(a, n);
print(head);
Node dummy = new Node(0);
dummy->next = head;
print(del(dummy, 2, 4));
return 0;
}

##7.给定两个单链表，编写算法找出两个链表的公共结点

class Solution {
public:
ListNode findFirstCommonNode(ListNode headA, ListNode *headB) {
auto a=headA,b=headB;
while(a!=b)
{
if(a)a=a->next;
else a=headB;
if(b)b=b->next;
else b=headA;
}
return a;
}
};

##8.给定一个带表头结点的单链表,设head为头指针,结点结构为(data,next),data为整型元素,next 为指针,试写出算法:按递增次序输出单链表中各结点的数据元素(要求:不允许使用数组作为辅助空间)

include[HTML_REMOVED]

using namespace std;
struct Node
{
int val;
Node next;
Node(int val):val(val),next(NULL){}
};
Node createLinkedList(int vals[], int n)
{
Node dummy=new Node(0);
Node cur=dummy;
for(int i=0;i[HTML_REMOVED]next=p;
cur=p;
}
return dummy->next;
}
void print(Node head)
{
for(Node p=head;p;p=p->next)
cout<[HTML_REMOVED]val<<’ ‘;
cout<[HTML_REMOVED]next)
{
Node pre=dummy,cur=dummy->next;
while(cur->next)
{
if(cur->next->val[HTML_REMOVED]next->val)
pre=cur;
cur=cur->next;
}
cout<[HTML_REMOVED]next->val<<’ ‘;
Node p=pre->next;
pre->next=p->next;
delete p;
}
}
int main()
{
int a[] = {1, 2, 3, 2, 2, 3, 5, 7, 2}, n = sizeof(a) / sizeof(int);
Node head = createLinkedList(a, n);
print(head);
Node *dummy = new Node(0);
dummy->next = head;
Min_Delete(dummy);
return 0;
}
```