线性表练习题

• 顺序表与单链表对比
• • 题目
  • 答案
• 顺序表有序插入
• • 题目
  • 代码
• 就地逆置
• • 题目
  • 代码
• 删除有序单链表某区间元素
• • 题目
  • 代码

请说明顺序表和单链表有何优缺点，并分析下列情况采用何种存储结构更好些。
①若线性表的总长度基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素。
②如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。

顺序表：

• 优点：
  1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间
  2.随机存取：可以快速存取表中任一位置的元素
• 缺点：
  1.表的容量难以确定，表的容量难以扩容
  2.插入和删除操作需要移动大量元素

单链表：

• 优点：
• 缺点：

①顺序表
②单链表

已知顺序表L中的元素递增有序排列，设计算法将元素x插入到表L中并保持表L仍递增有序。

#include 

using namespace std;
const int MaxSize=100;
using namespace std;
template
class SeqList{
private:
    int length;
    T data[MaxSize];
public:
    SeqList(){}
    SeqList(T data[],int length);
    ~SeqList(){}
    int getLength();
    T get(int i);
    int getIndex(T x);
    void Insert(T x,int i);
    T Delete(int i);
    int isEmpty();
    void printList();
};
template
SeqList::SeqList(T d[],int length){
    this->length=length;
    for(int i=0;i
int SeqList::getLength(){
    return length;
}
template
T SeqList::get(int i){
    if(i<1||i>length)
        throw"查找位置非法";
    return data[i-1];
}
template
int SeqList::getIndex(T x){
    for(int i=0;i
void SeqList::Insert(T x,int i){
    //注意检查操作合法性
    if(length==MaxSize) throw"上溢";
    if(i<1||i>length+1) throw"插入位置错误";
    for(int j=length;j>=i;j--){
        data[j]=data[j-1];
    }
    data[i-1]=x;
    length++;
}
template
T SeqList::Delete(int i){
    T x;
    //注意检查操作合法性
    if(length==0) throw"下溢";
    if(i<1||i>length) throw"删除位置错误";
    x=data[i-1];
    for(int j=i;j
int SeqList::isEmpty(){
    return length==0?1:0;
}
template
void SeqList::printList(){
    for(int i=0;i sl(a,9);
    int x=3,i=1;
    while(sl.get(i)<=x){
        i++;
    }
    sl.Insert(x,i);
    sl.printList();
    return 0;
}

试分别以顺序表和单链表作存储结构，各编写一个实现线性表就地逆置的算法。

顺序表

const int MaxSize=10;    //10只是示例性的数据，可以根据实际问题具体定义
class SeqList
{
public:
   SeqList( ){length=0;}       //无参构造函数，创建一个空表
   SeqList(int a[ ], int n);       //有参构造函数
   void Insert(int i, int x);   //在线性表中第i个位置插入值为x的元素
   int Delete(int i);        //删除线性表的第i个元素
   int Locate(int x);       //按值查找，求线性表中值为x的元素序号
   void Reverse();
   void PrintList( );      //遍历线性表，按序号依次输出各元素
private:
   int data[MaxSize];      //存放数据元素的数组
   int length;            //线性表的长度
};

SeqList::SeqList(int a[ ], int n)
{
      if (n>MaxSize) throw "参数非法";
      for (int i=0; i=MaxSize) throw "上溢";
      if (i<1 || i>length+1) throw "位置非法";
      for (int j=length; j>=i; j--)
        data[j]=data[j-1];   //注意第j个元素存在数组下标为j-1处
      data[i-1]=x;
      length++;
}

int SeqList::Delete(int i)
{
      if (length==0) throw "下溢";
      if (i<1 || i>length) throw "位置非法";
      int x=data[i-1];
      for (int j=i; j>1;i++){
        temp=data[i];
        data[i]=data[length-i-1];
        data[length-i-1]=temp;
    }
}

void SeqList::PrintList( )
{
  for (int i=0; i 
单链表
 利用头插法进行单链表的逆置
 
#include 
using namespace std;

template
struct Node
{
	T data;
	Node *next;
};

template
class linkList
{
public:
	linkList();
	linkList(T a[], int n);
	~linkList();
	void PrintList();
	T Get(int i);
	void Insert(int i, T x);
	void Delete(int i);
public:
	Node *first;
};

template
linkList::linkList()
{
	first=new Node;
	first->next=NULL;
}

template
linkList::linkList(T a[], int n)
{
	first=new Node;
	Node *r=first;
	for(int i=0;i *s=new Node;
		s->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=NULL;
}

template
linkList::~linkList()
{
	while(first!=NULL)
	{
		Node *q=first;
		first=first->next;
		delete q;
	}
}

template
void linkList::PrintList()
{
	Node *p=new Node;
	p=first->next;
	while(p!=NULL)
	{
		cout<data<<" ";
		p=p->next;
	}
}

template
T linkList::Get(int i)
{
	Node *p=first->next;
	int count=1;
	while(p!=NULL&&countnext;
		count++;
	}
	if(p==NULL) throw "查找位置异常";
	else return p->data;
}

template
void linkList::Insert(int i, T x)
{
	Node *p=first;
	int count=0;
	while(p!=NULL&&countnext;
		count++;
	}
	if(p==NULL) throw "插入位置异常";
	else
	{
		Node *s=new Node;
		s->data=x;
		s->next=p->next;
		p->next=s;
	}
}

template
void linkList::Delete(int i)
{
  Node *p;
  int j;
  p=first ; j=0;  //工作指针p初始化
  while (p!=NULL && jnext;
    j++;
  }
  if (p==NULL || p->next==NULL) throw "删除位置异常";  //结点p不存在或结点p的后继结点不存在
  else {
    Node *q;
	T x;
    q=p->next; x=q->data;  //暂存被删结点
    p->next=q->next;  //摘链
    delete q;
  }
}
template
void Rerverse(Node *first){
    //从链表的第二个元素开始摘，然后头插入链表中
    Node *p=first->next,*s=NULL;
    if(p==NULL) throw "空表";
    if(p->next==NULL) return;
    while(p->next!=NULL){
        s=p->next;
        p->next=s->next;

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

    }
}
template
Node* Copy(Node *oFirst){
    Node *p=oFirst->next;
    Node *nFirst=new Node;
    Node *s=nFirst;
    Node *t=NULL;

    while(p!=NULL){
        t=new Node;
        t->data=p->data;

        s->next=t;
        s=s->next;

        p=p->next;
    }
    t->next=NULL;
    return nFirst;
}
int main()
{
	int a[]={1,2,3,4,5};
    linkList test(a,5);
	cout<<"线性表a的初始状态："< *p=new Node;
	p=Copy(test.first)->next;
    Rerverse(test.first);

	cout<<"线性表a的状态："<data<<" ";
		p=p->next;
	}

	return 0;
}


 
删除有序单链表某区间元素 
题目 
 
 
已知单链表中各结点的元素值为整型且递增有序，设计算法删除链表中大于mink且小于maxk的所有元素，并释放被删除结点的存储空间。
 
 
代码 
#include 

using namespace std;
template
struct Node{
    T data;
    Node *next;
};
template
class linkList{
public:
	linkList();
	linkList(T a[],int n);
	~linkList();
	int Length();
	T Get(int i);
	void Set(int i,T x);
	int Locate(T x);
	void Insert(int i,T x);
	T Delete(int i);
	int Empty();
	void PrintList();
private:
    Node *first;
};
template
linkList::linkList(){
    first=new Node;
    first->next=nullptr;
}
template
linkList::linkList(T a[],int n){
    //头插法
    

    //尾插法
    first=new Node;
    Node *p=first,*s=nullptr;
    for(int i=0;i;
        s->data=a[i];
        p->next=s;
        p=s;
    }
    p->next=nullptr;
}
template
linkList::~linkList(){
    Node *p=nullptr;
    while(first!=nullptr){
        p=first;
        first=first->next;
        delete p;
    }
}
template
int linkList::Length(){
    int cnt=1;
    Node *p=first->next;
    while(p->next!=nullptr){
        cnt++;
        p=p->next;
    }
    return cnt;
}
template
T linkList::Get(int i){
    int cnt=1;
    Node *p=first->next;
    while(cntnext;
        cnt++;
    }
    //别漏了还有异常这种情况
    if(p==nullptr) throw"查找位置错误";
    else return p->data;
}
template
int linkList::Locate(T x){
    Node *p=first->next;
    int pos=1;
    while(p!=nullptr){
        if(p->data==x)  return pos;
        p=p->next;
        pos++;
    }
    return 0;
}
template
void linkList::Insert(int i,T x){
    Node *p=first;
    int cnt=0;
    //要将数据插入到第i个位置，就要找到第i-1个位置再做插入操作
    while(cntnext;
        cnt++;
    }
    if(p==nullptr)  throw"插入位置有误";
    else{
        Node *s=new Node;
        s->next=p->next;
        s->data=x;
        p->next=s;
    }

}
template
T linkList::Delete(int i){
    Node *p=first;
    int cnt=0;
    //要删除第i个元素，就要找到第i-1个位置，再做删除操作
    while(cntnext;
        cnt++;
    }
    //p->next==nullptr：p不存在后继结点
    if(p==nullptr||p->next==nullptr)  throw"删除位置有误";
    else{
        Node *s=p->next;
        T data=s->data;
        p->next=s->next;
        delete s;
        return data;
    }

}
template
int linkList::Empty(){
    if(first->next==nullptr)
        return 1;
    return 0;
}
template
void linkList::PrintList(){
    Node *p=first->next;
    while(p!=nullptr){
        cout<data<next;
    }
}
template
void linkList::Set(int i,T x){
    int cnt=1;
    Node *p=first->next;
    while(cntnext;
        cnt++;
    }
    if(p==nullptr) throw"位置错误";
    else{
        p->data=x;
    }
}
int main()
{
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    linkList ll(a,10);
    int mink=4,maxk=9;
    int i=1;
    while(ll.Get(i)<=mink){
        i++;
    }
    while(ll.Get(i)