线性表--数据结构设计与操作

发布于：2024-05-08 ⋅ 阅读:(26) ⋅ 点赞:(0)

单链表

1.单链表的定义：

typedef struct LNode{
    Elemtype data;
    struct Lnode *next;
}LNode ,*LinkList;


    //单链表的数据结构（手写）
#include<iostream>
#include<vector>
#include<algorithm>

typedef int TypeElem;
//单链表的定义
t
    ypedef struct LNode {
    TypeElem data;
    struct LNode* next;
}LNode,*LinkList;

//初始化单链表(带头结点)
boolInitLinkList_H(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));//L = new LNode;等价写法c++
    L->next = NULL;
    return true;
}
//不带头结点的单链表初始化
bool InitLinkList_(LinkList&L){
    L = NULL;
    return ture;
}
/*求表长O(n),扫描链表*/
int Length(LinkList&L){
    int ltn=0;
    p = L->next;
    while(p){
        p=p->next;
        len++;
    }
    return len;
    }

/*按位序查找节点*/
LNode* GetElem(LinkList L,int pos){
        LNode*p = L->next;
        int j=1;
        while(p&&j<=pos){
            j++;
            p = p->next;
        }
    return p;//返回第pos个节点的指针或NULL
}
/*按值查找表节点*/
LNode*LocateElem(LinkList&L,int val){
        LinkList p = L->next;
        while(p && p->data!=val)
            p = =->next;
        return p;
    }
/*插入节点O(n)时间主要消耗在查找到第i-1个节点上，若在指定节点后插入新节点则只需O(1)*/
bool ListInsert(LinkList&L,int pos,int e){

        LinkList p =L->next;

        int j=1;
        while(p && j<pos-1)
            p = p->next;
        if(!p)
            return false;
        LNode*s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next =p->next;
        p->next = s;
        return true;
    }
/* 删除节点*/
bool ListDelete(LinkList&L,int pos,int &e){
        LinkList p = L->next;

        while(p&&j<pos-1){
            p = p->next;
            j++;
        }
        if(!p)return false;//链表为空
        LNode*q =p->next;
        e = q->data;//用e返回被删除的元素的值
        p->next = q->next;
        free(q);
        return true;

    }
bb2ad43e-72dc-4264-a176-46f0767c916e
2.单链表的插入与删除

2-1按位序插入（在某一节点的后面插入新节点）

//带头结点
bool ListInsert(LinkList &L,int i,Elemtype e){
    if(i<1)
        return false;
    LNode*p;
    int j =0;
    p = L;
    while(p!=NULL && j<i-1){//找到第i-1个节点（节点i的前驱节点）
        p = p->next;
        j++;
    }
    if(p==NULL)//i值不合法
        return false;
    //插入操作(可封装为函数)
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;  
}
aa9534f4-63c8-49c2-8a75-a35676d1f9fb
3.单链表的建立（头插法/尾插法）

//迭代法
/*假设链表为 1→2→3→∅我们想要把它改成  ∅←1←2←3。
算法设计基本思想：
    在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用
时空复杂度分析：
    时间复杂度O(n),只需扫描一遍链表
    空间复杂度O(1),原地逆置
*/
ListNode* reverseList(ListNode* head) {
        ListNode*pre = nullptr;//节点的前一个结点
        ListNode*cur = head;
        while(cur){
            ListNode*ne = cur->next;//存储当前结点的后继节点
            cur->next = pre;//将当前节点的后继节点改为其前驱节点
            pre = cur;
            cur = ne;//迭代更新当前节点
        }
        return pre;
    }


//递归法逆置

    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
06eebb10-b37a-4e1e-898c-dea794fb482c

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

/*在带头结点的单链表L中删除所有值为x的节点，并释放其空间*/
void DeleteX(LinkList&L,int x){
    LNode*p = L;
    while(p->next){
        if(p->next-val==x){
            LNode*q = p->next;
            p->next = q->next;q
            free(q);
        }else{
            p=p->next;
        }
    }
}

    int DeleteMinEle(LinkList& L,int e) {
    if (L->next == NULL) {
        // List is empty
        return -1; // or any other appropriate value
    }

    LNode* min_pre = L;
    LNode* min_node = L->next;
    LNode* p = L->next->next; // Start from the second node
    LNode* pre = L->next;

    while (p) {
        if (p->data < min_node->data) {
            min_pre = pre;
            min_node = p;
        }
        pre = p;
        p = p->next;
    }

    e= min_node->data;
    min_pre->next = min_node->next;
    free(min_node);

    return e;//返回最小元素
}


/*就地逆置带头结点的单链表*/
void ReverseLinkList_H(LinkList& L) {
    if (L->next == NULL|| L->next->next==NULL)return;//链表为空或只有一个数据节点，无需逆置
    LNode* p = L->next;
    LNode* pre = NULL;
    while (p != NULL) {
        LNode* ne = p->next;
        p->next = pre;
        pre = p;
        p = ne;
    }
    L ->next=pre;//切记逆置后要更新头节点！！！
    return;
}

设 C = a 1 , b 1 , a 2 , b 2 , ⋅ ⋅ ⋅ , a n , b n C={a_1,b_1,a_2,b_2,···,a_n,b_n} C=a1​,b1​,a2​,b2​,⋅⋅⋅,an​,bn​为线性表，才用带头结点的单链表存放，设计一个就地工作算法，将其拆分为两个线性表 A = a 1 , a 2 , ⋅ ⋅ ⋅ , a n , B = b 1 , b 2 , ⋅ ⋅ ⋅ , b n A={a_1,a_2,···,a_n},B={b_1,b_2,···,b_n} A=a1​,a2​,⋅⋅⋅,an​,B=b1​,b2​,⋅⋅⋅,bn​

    void breakLinkList(LinkList&L){
        //先获取单链表的长度
        int len = Length(L);
        LNode*curr=L->next;
        //L->next=NULL;//摘取原链表的头节点
        LinkList A= new LNode;
        LinkList B = new LNode;
       A->next=NULL,B->next=NULL;
        LNode* s1=A,*s2=B;
        for(int i=1;i<=len;i++){
            LNode*ne = p->next;
            if(i&1){
               
                p->next=NULL;
                s1->next =p;
                s1 = p;
            }else{
                p->next=NULL;
                s2->next =p;
                s2 = p;
            }
            p = ne;
        }
        printList(A);
        printList(B);

    }

对一个有序单链表去重处理O(n)

//对一个有序单链表去重处理O(n)
void DeleteMulEle(LinkList& L) {
    if (L == NULL || L->next == NULL) // If the list is empty or has only one node, no duplicates to remove
        return;
    LNode* p = L->next;
    LNode* pre = L;
    while (p!=NULL&&p->next!=NULL) {
        if (p->data != p->next->data) {
            pre = p;
        }
        else {
            LNode* q = p->next;
            p->next = q->next;
            free(q);
        }
        p = p->next;
    }

}

已知两个单链表A和B分别表示两个集合，其元素递增有序，编写函数求A与B的交集，并存放于A链表中。

void MergePublicElem(LinkList& A, LinkList& B) {
    /*
    算法设计基本思想：
        由于链表元素单调有序，故采用归并的思想提取公共元素。
    时间复杂度：O(lenA+lenB);
    空间复杂度：O(1);
    */
    LNode* pa = A->next;
    LNode* pb = B->next;
    LNode* La = A->next;
    LNode* pre = A;
    while (pa != nullptr && pb != nullptr) {
        if (pa->data == pb->data) {
            La->data = pa->data;
            pre = La;
            La = La->next;
            pa = pa->next;
            pb = pb->next;
        }
        else if (pa->data < pb->data) {
            pa = pa->next;
        }
        else {
            pb = pb->next;
        }
    }
    pre->next=NULL;
    delete La;
    printList(A);
    return;
}

两个整数序列A和B已经存放到两个单链表中，请设计算法，判断B序列是否是A序列的连续子序列。

bool AIsSubseqB(LinkList&A,LinkList &B){
/*
  算法设计基本思想：
    本题采用朴素匹配算法实现
    时间复杂度：O(nm);
    空间复杂度：O(1);      
*/
    LNode*pa= A->next;
    LNode*pb = B->next;
    LNode*pre = A;
    while(pa&&pb){
       if(pa->data== pb->data){
            pa = pa->next;
            pb = pb->next;
        }else{//如果值不相等
            pre = pre->next;
            pa = pre;//A链表新的开始比较的节点
            pb = B->next;//pb重新指向B链表首节点

        }  
    }
    if(!pb) return true;
    return false;
}

判断一个带头结点的循环双链表是否对称

#include<iostream>

typedef int ElemType;
//双链表的定义
typedef struct Node{
	ElemType data;
	Node* pre;
	Node* next;
}DNode, * DLinkList;

//初始化带头结点的循环双链表
bool InitDlist_H(DLinkList& L) {
	L = new DNode;
	L->pre = L;
	L->next = L;
	return true;
}
bool InsertElems(DLinkList& L, ElemType x) {
	DNode* s = new DNode;
	s->data = x;
	s->next = L->next;
	L->next->pre = s;
	s->pre = L;
	L->next= s;
	//L->pre = s;
	return true;
}
//头插法
void Print(DLinkList L) {
	auto p = L->next;
	while (p != L) {
		std::cout << p->data << "->";
		p = p->next;
	}
	std::cout << '\n';
}
bool issymmetry(DLinkList L) {
    /*
    Algorithm design:
    Scan from both ends of the list towards the middle, comparing corresponding elements.
    Time complexity: O(n)
    Space complexity: O(1)
    */
    DNode *left = L->next; // Points to the first node
    DNode *right = L->pre; // Points to the last node

    while (left != right && right->next != left) {
        if (left->data != right->data)
            return false;
        left = left->next;
        right = right->pre;
    }
    return true;
}

int main()
{
	DLinkList L;
	InitDlist_H(L);
	for (int i = 1; i <= 9; i++)
		InsertElems(L, i);
	Print(L);
	printf("%d\n",issymmetry(L));

	return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布