您的位置:首页 > 娱乐 > 八卦 > 短剧分销平台_前端后端_媒体代发网站_竞价推广托管服务

短剧分销平台_前端后端_媒体代发网站_竞价推广托管服务

2024/12/23 7:48:02 来源:https://blog.csdn.net/qq_51365682/article/details/142725219  浏览:    关键词:短剧分销平台_前端后端_媒体代发网站_竞价推广托管服务
短剧分销平台_前端后端_媒体代发网站_竞价推广托管服务

单链表

// 结点的定义

template <class T>

struct Node 

{

        T data ;

        Node <T> *next;   //指向下一个node 的类型与本node相同

}

// 最后一个node指针指向Null

 生成结点:  Node <T> * p =  new Node < T>;

为结点赋值:       p-> data = 'a';

                        p- > next = (其他结点的地址);  p -> next = NULL ; (尾结点)

                        delete p; //释放结点

// 单链表的类实现

template <class T> 

class LinkList

{

public :    //此处是函数定义

        LinkList();   

        ListList(T a[ ] , int n);

        int Lenght(); 

        T Get(int);  //俺下标查找

        int Loate(T); //按值定位

        void insert(T,int);  //插入

        T delete (int) ;  //删除

        ~LinkList();  

private:

        Node <T> * first;      

}

构造函数的实现一个空链表:

template <class T>
LinkList <T> :: LinkList()
{first = new Node <T>;    first->next = NULL;           
}

头插法

初始化头节点(头节点指的是first,首结点代表链表第一个结点)

template <class T>
LinkList <T> :: LinkList (T a[ ] ,int n)
{//初始化头节点first = new Node<T>;first ->next =NULL;for (int i =0 ; i<n ;i++){//生成新的结点Node <T> *s = new Node <T>;s ->data =a [i]; //链接再头节点和首结点之间s->next = first ->next;first ->next = s ;}
}

核心代码:

        s->next = first ->next;
        first ->next = s ;

因为对于first ->next的初始化指向是NULL;此处赋值给s->next则表示了s->next指向了NULL

然后将地址s赋值给了first ->next(头节点的地址域)

尾插法

template <class T>
LinkList <T> :: LinkList (T a[ ] ,int n)
{//初始化头节点Node<T> *first = new Node<T>;Node<T> *r = first;    //尾结点首先指向firstfor (int i =0 ; i<n ;i++){//生成新的结点Node <T> *s = new Node <T>;s ->data =a [i];s ->next =NULL;   //由于是尾插,直接指向NULL //链接在尾结点后面:r->next = s;//尾结点后移,由于此时的新的结点s是尾结点r= s;}//这里也可以加一句r->next = NULL;
}

  析构函数: 

template <class T>
LinkList <T> :: ~linkList
{while (first != NULL)   //或者直接while(first){Node <T> *p = first;first = first->next;delete p; }
}

按照值查找: 

查找值为x的结点的位置

顺序查找:

template <class T>
int LinkList <T> :: locate (T x)  // T类型的x
{Node<T> *p = first->next ;//首结点后的第一个结点int j=1;while(p)   //p不为空一直循环,p为NULL的时候即循环到结尾{if(p->data ==x ) return j;p = p->next ;j++;}return 0;
}

 按照值查找返回结点 ,非模板类实现:


Node * LinkList:: local (int val )
{Node* p = first;while (p ){if (p ->data == val){return p;}p = p -> next;}return NULL;
}

按下标查找:

template <class T>
T LinkList <T> :: Get (int i){
//初始化Node<T> * p = first ->next ;int j =1;while(j<i && p!=NULL)  {p= p->nextj++;}if(p==NULL || i<1) throw"位置非法";return p->data ;
}

随意位置插入:

思路:

新建结点 Node<T> *s = new Node <T>;   s->data = x;   

插入 : s ->next = p->next ;         (p->next 的值是ai的地址,将其赋值给新节点地址域)

             p->next =s ;

//将值为x的结点插入到位置为i的结点,那么首先要找到i-1 号结点
template <class T>
void LinkList <T> :: Insert (T x , int i)
{Node <T> * p = first ; int j = 0 ;while (p && j<i-1){p = p->next ; j++;}if (p == NULL) throw "插入位置非法"else {// 新建结点 Node<T> *s = new Node <T>;s->data = x;      //插入s ->next = p->next ; p->next =s ;}
}

在指定结点后插入:

//在指定的p结点之后插入
template <class T>
void LinkList <T> :: insertAfter (Node<T> * p , T x )
{Node <T> *s =  new Node <T>;s -> data =x ;s->next = p->next; p- next = s ;
}//在指定的p结点之前插入
//需要先找到p结点的前面一个结点q ,循环来找
template <class T>
void ListList <T> ::insertBefore (Node<T>  * p ,T x )
{Node <T> *q = first ; //从头节点开始找while (q ->next != p ){   // 找到q结点的条件q =q->next ; }insertAfter (q,x);  //在q后插入,等于在p前插入
}
//上述方法时间复杂度是O(n)
//下列实现时间复杂度是O(1)
template <class T>
void LinkList <T> :: insertBefore (Node <T> * p ,T x)
{Node <T> *s = new Node<T>;* s = *p ;p ->next = s;    //将原来的p结点当成新插入的结点,把新的结点变为p结点放在后面p ->data = x;    // 等同于前插
}

结点删除:

首先需要把ai代表的结点摘除,使用s 表示:
        s = p->next ;

        p->next = s -> next ;

//  或者这里直接 : p ->next = p.next.next;  后续就不需要删除新建结点s了

然后删除结点:

        delete s ;

template <class T>
T LinkList <T> ::  detele (int i)
{Node <T> * p = first ;int j = 0;while(p  && j <i ){p = p->next ;j++ ;}if (p->next ==NULL)throw "删除位置非法"else {s = p->next ;   //让中间结点(待删除)赋值给sp->next = s ->next ;  // 然后第三结点赋值给第一个结点的地址域delete s; //删除中间结点}
}
// 上述操作时间复杂度O(n)
//改成O(1):
template <class T>  //返回T因为一般删除都会返回结点的x值
T LinkList <T> ::delete (Node <T> *p )
{if(p->next){// p非最后一个结点 ,使用删除后面的一个结点代替删除自己T x =p ->data ;p -> data = p ->next ->data ;Node <T>  *q = p ->next ;  //表示出来后一个结点q ->next = p ->next  ; //准备将q出链delete q;return x ;//一般删除结点都返回其值else{...正常循环}
}
}

或者非模板的普通函数实现://输入是指针

void delNode (ListNode *prev)
{ListNode * curr = prev -> next;prev->next = curr -> next ;delete curr;
}

求取链表长度:

template <class T>
int LinkList <T> :: Length(){Node <T> * p = first ;int i =0;while ( p ){p = p ->next;i++;}return i;
}
//上述时间复杂度 O(N)

反转链表(力扣206题):

在原链表直接反转:

template <class T>LineList<T>* LinkList<T> :: reverse(LineList * head){//当结点只有一个或者时一个空节点的时候不需要反转直接返回if(head == NULL || head->next == NULL ) return head;Node<T> *a = head , *b = head->next ;while(b) {Node<T> * c= b->next ;   //首先需要c来维持原链表的数据获取 //开始交换b->next = a;a =b ;  //把b指针赋值给a指针, 此时a指向第二个元素b =c ;  //此时b指向第三个元素}head -> next = NULL;return a;  //最后返回新的头节点
} 

力扣206原题:

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head ==nullptr || head->next ==nullptr) return head;auto *a = head;auto *b =head->next;while (b){auto *c = b->next;b -> next= a;a = b ;b =c ;}head->next =nullptr;return a;}
};

合并链表(力扣21题):

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* list3 = new ListNode;//获取头结点auto *head1 = list1;  auto * head2 = list2;auto * head3 = list3;while(head1 != nullptr && head2 !=nullptr){if(head1->val <= head2->val){head3->next = head1;head1 = head1->next;}else   {head3 ->next = head2;head2 =head2 ->next;}head3 = head3->next;}//若有l1和l2任一链表循环到头,另一直接全部剩余插入l3head3->next  = head1==nullptr? head2:head1;return list3->next;        }
};

循环链表:

尾指针地址域指向头节点,上述代码循环条件改为p!= r

双链表:

每个结点有两个指针域,指向前驱和后继

template <class T> 
struct DulNode 
{T data;DulNode <T> * prior, *next ;
}

插入操作:

首先更改新结点的指针域

然后动链表

删除操作:

顺序表和链表的对比:

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com