线性表应用（非递减合并、分解链表、删除线性表）

         将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。

#include<iostream>
using namespace std;
typedef struct list
{int data;list* next;
}list,*linklist;
void Createlist(linklist& l)
{l = new list;l->next = NULL;linklist p,r;r = l;for (int i = 0; i < 5; i++){p = new list;cin >> p->data;r->next = p;r = p;}p->next = NULL;
}
void Addlist(linklist& L1, linklist& L2)
{linklist L3, pa, pb,p;pa = L1->next;pb = L2->next;L3 = L1, L3->next = NULL;while (pa || pb){if (pa==NULL){p = pb;pb = pb->next;}else if (pb==NULL){p = pa;pa = pa->next;}else if (pa->data <= pb->data){p = pa;pa = pa->next;}else{p = pb;pb = pb->next;}p->next = L3->next;L3->next = p;}delete L2;
}
void Printlist(linklist& l)
{linklist p;p = l->next;while (p){cout << p->data<<" ";p = p->next;}
}
int main()
{linklist L1, L2;cout << "输入第一个链表：" << endl;Createlist(L1);cout << "输入第二个链表：" << endl;Createlist(L2);Addlist(L1, L2);cout << "合并链表：" << endl;Printlist(L1);
}

       设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。

#include<iostream>
using namespace std;
typedef struct list
{int data;list* next;
}list,*linklist;
void Createlist(linklist& l)
{l = new list;l->next = NULL;linklist p,r;r = l;for (int i = 0; i <10; i++){p = new list;cin >> p->data;r->next = p;r = p;}p->next = NULL;
}
void Separatelist(linklist& L1, linklist& L2, linklist& L3)
{L3 = new list;L3->next = NULL;linklist p,r;p = L1->next;L2 = L1;L2->next = NULL;while (p){r = p->next;if (p->data < 0){p->next = L2->next;L2->next = p;}else{p->next = L3->next;L3->next = p;}p = r;}
}
void Printlist(linklist& l)
{linklist p;p = l->next;while (p){cout << p->data<<" ";p = p->next;}cout << endl;
}
int main()
{linklist L1, L2,L3;cout << "输入第一个链表：" << endl;Createlist(L1);Separatelist(L1, L2, L3);cout << "拆分链表：" << endl;Printlist(L2);Printlist(L3);
}

 

       已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O (1）的算法，该算法删除线性表中所有值为ite m的数据元素。

#include<iostream>
#define maxsize 100
using namespace std;
typedef struct node
{int data;
}Node;
typedef struct
{Node* elem;int length;
}Sqlist;
void Initlist(Sqlist& L)
{L.elem = new Node[maxsize];L.length = 0;
}
int Createlist(Sqlist& L)
{if (L.length == maxsize) return 0;for (int i = 0; i < 10; i++){cin >> L.elem[i].data;L.length++;}return 1;
}
void Deletelist(Sqlist& L, Node e)
{int k = 0;for (int i = 0; i < L.length; i++){if (L.elem[i].data != e.data){L.elem[k].data = L.elem[i].data;k++;}}L.length = k;
}
void Printlist(Sqlist L)
{for (int i=0;i<L.length;i++){cout << L.elem[i].data << " " ;}cout << endl;
}
int main()
{Sqlist A;Initlist(A);Createlist(A);cout << "原线性表：" << endl;Printlist(A);cout << "输入要删除的一个数：" << endl;Node n;cin >> n.data;Deletelist(A,n);Printlist(A);
}