已知带头结点的动态单链表L中的结点是按整数值递增排序的,编写算

有两个按元素值递增有序的线性表A和B以单链表作存储结构,试编写算法将A表和B表归并成一个按元素值递减有序的线性表C长度大于1的单循环链表中编写算法删除结点*s的直接前驱结点。单链表线性表中含有三类字符的数据构造三个以循环链表示的线性表,使每一个表中只含同一类的字符有一双链表,每个结点中除有prior、data和next域外,还有一访问频度域freq每当在链表上进行一次LOCATE(L,x)运算,元素值为x的结点中freq域的值增1

//系统功能:1、已知带头结点的动态单链表L中的结点是按整数值递增排序的，编写算法将值为x的结点插入到表L中，使L仍然有序。
// 2、设计算法，逆置带头结点的动态链表L。要求利用原表的结点空间，并要求用尽可能少的时间完成。
// 3、假设有两个按元素值递增有序的线性表A和B，均以单链表作存储结构，试编写算法将A表和B表归并成一个按元素值递减有序的线性表C，并要求利用原表的空间存放C。
// 4、假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向某个结点的指针，编写算法删除结点*s的直接前驱结点。
// 5、已知由单链表表示的线性表中，含有三类字符的数据元素（如：字母、数字和其它字符），设计算法构造三个以循环链表示的线性表，使每一个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的空间。（头结点可以另辟空间）
// 6、有一双链表，每个结点中除有prior、data和next域外，还有一访问频度域freq，在链表被启用前，其值均初始化为零。每当在链表上进行一次LOCATE(L,x)运算，元素值为x的结点中freq域的值增1，并使此链表中结点保持按freq递减的顺序排列，以便使频繁访问的结点总是靠近表头。设计满足上述要求的LOCATE算法并加以测试。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

typedef int Status;
typedef int ElemType;
typedef char ElemType1[100];

typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;

typedef struct LNode1{
ElemType1 data; //char data[100]
struct LNode1 *prior;
struct LNode1 *next;
int freq;
}LNode1,*LinkList1;
//**********************************初始化********9/17*************************************************
Status InitList_L(LinkList &L){
L=new LNode;
L->next=NULL;
return 1;
}
Status InitList_L1(LinkList1 &L){
L=new LNode1;
L->next=NULL;
return 1;
}
//*********************************求表长**********9/17**************************************************
Status ListLength_L(LinkList L){
LinkList p;
p=L->next; //p指向第一个结点
int i=0;
while(p){
i++;
p=p->next; }
return i;
}

//**********************************创建单链表*********9/17*************************************************
void CreateList_L(LinkList &L,int &n){
int i;
L=new LNode;
LinkList p;
L->next=NULL; //先建立一个带头结点的单链表
for( i=n;i>0;i
--){
p=new LNode;
cin>>p->data;
p->next=L->next;L->next=p; //插入到表头
}
cout<<"链表中元素排列顺序为"<<endl;

有两个按元素值递增有序的线性表A和B以单链表作存储结构,试编写算法将A表和B表归并成一个按元素值递减有序的线性表C长度大于1的单循环链表中编写算法删除结点*s的直接前驱结点。单链表线性表中含有三类字符的数据构造三个以循环链表示的线性表,使每一个表中只含同一类的字符有一双链表,每个结点中除有prior、data和next域外,还有一访问频度域freq每当在链表上进行一次LOCATE(L,x)运算,元素值为x的结点中freq域的值增1

while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
void CreateList_L1(LinkList1 &L,int &n){
int i;
L=new LNode1;
LinkList1 p;
L->next=NULL; //先建立一个带头结点的单链表
for( i=n;i>0;i--){
p=new LNode1;
cin>>p->data;
p->next=L->next;L->next=p; //插入到表头
}
cout<<"链表中元素排列顺序为"<<endl;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}

//**********************************插入********9/21~9/25****************************************************
//因为有头结点，所以不用分类讨论，也不用引入两个指针变量
void ListIsert_L(LinkList &L,int &n,ElemType e)
{
LinkList p=L,s=L;
s=new LNode;
s->next=NULL;
s->data=e;
if(L==NULL)
{
L=s;
}
else
{
while(p->next!=NULL&&p->next->data<e)
{
p=p->next;
}
s->next=p->next;
p->next=s;
}
n++;
p=L->next;
cout<<"插入元素后递增顺序为:"<<endl;
for(int i=1;i<=n;i++)
{

cout<<p->data<<" ";
p=p->next;
}
}

//*********************************逆置****9/30*********************************************************
void nizhi(LinkList &L,int n)
{
LinkList p=L->next,t;
if(L->next==NULL)
{
cout<<"无元素"<<endl;
}
else{
L->next=NULL;
while(p)
{
t=p;
p=p->next;
t->next=L->next;
L->next=t;

}
p=L->next;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
}
}
//********************************合并*********10/2************************************************
//思想：合并后逆置
//想法：合并时采用前插法，但是当只剩一个链表时，就要一个元素一个元素插
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)
{
LinkList pa=La->next;
LinkList pb=Lb->next;
LinkList pc=Lc=La; //用La的头结点作为Lc的头结点
int n;
while(pa && pb)
{
if(pa->data<=pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
…… 此处隐藏：3024字，全部文档内容请下载后查看。喜欢就下载吧 ……