线性表的应用

1. 链式有序表的合并
2. 旋转链表
3. 分隔链表
4. 翻转链表

#include<iostream>

#include<cstdlib>

using namespace std;

typedef int ElemType;

typedef int Status;

typedef struct LNode{

ElemType data;

struct LNode *next;

int val;

}LNode,*LinkList;

//创建链表

void CreateList_H(LinkList &L,int n){

L=new LNode;

L->next=NULL;

cout<<"请输入"<<n<<endl;

for(int i=0;i<n;++i){

LNode*p =new LNode;

cin>>p->data;

p->next=L->next;

L->next=p;

}

}

//输出链表

void PrintList (LinkList L) {

LNode *p;

p=L->next;

while(p!=NULL) {

cout<<p->data<<" ";

p=p->next;

}

cout<<endl;

}

//链式有序表的合并

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)

{

LNode *pa=La->next;

LNode *pb=Lb->next;

Lc=La;

LNode *pc=Lc;

while(pa&&pb)

{

if(pa->data<=pb->data)

{

pc->next=pa;

pc=pa;

pa=pa->next;

}

else{

pc->next=pb;

pc=pb;

pb=pb->next;

}

}

pc->next=pa?pa:pb;

delete Lb;

}

//旋转链表

struct LNode* rotateRight(struct LNode* head,int k)

{

if(k==0||head==NULL||head->next==NULL)

return head;

int n=1;

struct LNode* tail=head;

while(tail->next !=NULL)

{

tail=tail->next;

n++;

}

int movenum=k%n;

if(movenum==0)

return head;

tail->next=head;

int addnum=n-movenum;

while(addnum--)

tail=tail->next;

struct LNode* newhead=tail->next;

tail->next=NULL;

return newhead;

}

//分隔链表

struct LNode*partition(struct LNode*head,int x)

{

struct LNode*small=(struct LNode*)malloc(sizeof(struct LNode ));

struct LNode*large=(struct LNode*)malloc(sizeof(struct LNode ));

struct LNode*pa=head;

struct LNode*pb=small;

struct LNode*pc=large;

while(pa!=NULL)

{

if(pa->val < x)

{

pb->next=pa;

pb=pb->next;

}

else{

pc->next=pa;

pc=pc->next;

}

pa=pa->next;

}

pc->next=NULL;

pb->next=large->next;

struct LNode* newhead = small->next;

return newhead;

}

//翻转链表

struct LNode* reverseKGroup(struct LNode* head,int k)

{

int x=k;

int n=0;

struct LNode* s =(struct LNode*)malloc(sizeof(struct LNode));

struct LNode* cur=s;

struct LNode* slow=head;

struct LNode* fast=NULL;

struct LNode* prev=NULL;

while(slow)

{

n++;

slow=slow->next;

}

slow=head;

n/=k;

for(int i=0;i<n;i++)

{

while(x)

{

fast=slow->next;

slow->next=prev;

prev=slow;

slow=fast;

x--;

}

cur->next=prev;

while(cur->next)

cur=cur->next;

prev=NULL;

x=k;

}

cur->next=slow;

struct LNode* newhead=s->next;

return newhead;

}

int main()

{

cout << "--- 测试 1: 合并有序链表 ---" << endl;

LinkList La, Lb, Lc;

cout << "创建链表 A (需有序): ";

CreateList_H(La, 3);

cout << "创建链表 B (需有序): ";

CreateList_H(Lb, 3);

MergeList_L(La, Lb, Lc);

cout << "合并结果: ";

PrintList(Lc);

cout << endl;// --- 测试 2: 旋转链表 ---

cout << "--- 测试 2: 旋转链表 ---" << endl;

LinkList L_rotate;

cout << "创建用于旋转的链表: ";

CreateList_H(L_rotate, 5);

int k_rot = 2;

cout << "向右旋转 " << k_rot << " 位后的结果: ";

LNode* res_rot = rotateRight(L_rotate->next, k_rot);

// 临时打印

LNode* temp = res_rot;

while(temp) { cout << temp->data << " "; temp = temp->next; }

cout << endl;

cout << endl;

// --- 测试 3: 分隔链表 ---

cout << "--- 测试 3: 分隔链表 (以 3 为界) ---" << endl;

LinkList L_part;

cout << "创建用于分隔的链表: ";

CreateList_H(L_part, 5); // 例如输入 3 1 4 1 5

LNode* res_part = partition(L_part->next, 3);

temp = res_part;

while(temp) { cout << temp->data << " "; temp = temp->next; }

cout << endl;

cout << endl;

// --- 测试 4: K 个一组翻转 ---

cout << "--- 测试 4: K 个一组翻转 (k=2) ---" << endl;

LinkList L_rev;

cout << "创建用于翻转的链表: ";

CreateList_H(L_rev, 5); // 例如输入 1 2 3 4 5

LNode* res_rev = reverseKGroup(L_rev->next, 2);

temp = res_rev;

while(temp) { cout << temp->data << " "; temp = temp->next; }

cout << endl;

return 0;

}