急求用C++做顺序表,单链表 万分感谢!!!
发布网友
发布时间：2022-05-05 04:55
共2个回答
热心网友
时间：2022-07-01 17:21
//线性表是一个容器
//警告，一下部分不得乱改。
#include "stdafx.h"
#include <iostream>
using namespace std;
#define ListIncrement 10
template<class T>
class List{
int capacity;
int size;
T*p;
public:
List();
~List();
void ClearList();
bool List_is_empty();
int Get_capacity();
int Get_size();
T*Get_p();
List<T>&operator=(List<T>&A);
int ListLength();
T GetElem_at(int i);
int LocateElem(T e);
T PriorElem(T e);
T NextElem(T e);
void IncreatCapacity(); //当需要是会自动扩大capacity;
void ReceCapacity(); //当capacity过大时会自动的减小capacity；
void pushback(T e);
void insert(int i,T e);
void delet(int i);
void combin(List<T>&A,List<T>&B);
void show();
};
template<class T>
List<T>::List():capacity(20),size(0){
p=new T[24];
memset(p,0,24*sizeof(T));
}
template<class T>
List<T>::~List(){
delete[]p;
}
template<class T>
int List<T>::Get_capacity(){
return this->capacity;
}
template<class T>
int List<T>::Get_size(){
return this->size;
}
template<class T>
T*List<T>::Get_p(){
return this->p;
}
template<class T>
List<T>& List<T>::operator =(List<T> &A){
delete[]p;
p=new T[A.capacity+4];
this->capacity=A.capacity;
this->size=A.size;
memset(p,0,sizeof(T)*(this->capacity+4));
memcpy(p,A.Get_p(),sizeof(T)*A.capacity);
return *this; //爽啊
}
template<class T>
void ClearList(){
memset(p,0,24*sizeof(T));
}
template<class T>
bool List<T>::List_is_empty(){
if(this->size==0)return 1;
else return 0;
}
template<class T>
int List<T>::ListLength(){
return this->size;
}
template<class T>
T List<T>::GetElem_at(int i){
return *(p+i-1);
}
template<class T>
int List<T>::LocateElem(T e){
for(int i=1;i<=this->size;i++){
if(*(p+i-1)==e)return i;
}
return 0;
}
template<class T>
T List<T>::PriorElem(T e){
int j;
j=this->LocateElem(e);
if(j<=1){
cout <<"该元素没有前驱或不存在\n";
return 0;
}
else return *(p+j-2);
}
template<class T>
T List<T>::NextElem(T e){
int j;
j=this->LocateElem(e);
if(j==0||j==this->size){
cout <<"该元素后驱不存在\n";
return 0;
}
else return *(p+j);
}
template<class T>
void List<T>::IncreatCapacity(){
if(this->size==this->capacity){
T*q=new T[this->capacity+ListIncrement+4];
memset(q,0,sizeof(T)*(this->capacity+ListIncrement+4));
memcpy(q,p,this->capacity*sizeof(T));
delete[]p;
p=q;
this->capacity+=ListIncrement;
}
}
template<class T>
void List<T>::ReceCapacity(){
if(this->capacity-this->size>=20){
T*q=new T[this->capacity-16];
memset(q,0,sizeof(T)*(this->capacity-16));
memcpy(q,p,sizeof(T)*(this->size));
delete[]p;
p=q;
this->capacity-=20;
}
}
template<class T>
void List<T>::pushback(T e){
this->IncreatCapacity();
*(p+this->size)=e;
this->size++;
}
template<class T>
void List<T>::insert(int i,T e){
this->IncreatCapacity();
for(int j=this->size;j>=i;j--){
*(p+j)=*(p+j-1);
}
*(p+i-1)=e;
this->size++;
}
template<class T>
void List<T>::delet(int i){
for(int j=i;j<this->size;j++){
*(p+j-1)=*(p+j);
}
memset((p+this->size-1),0,sizeof(T));
this->size--;
this->ReceCapacity();
}
template<class T>
void List<T>::combin(List<T>&A,List<T>&B){
int i=1,j=1;
while(i<=A.ListLength()&&j<=B.ListLength()){
if(*(A.Get_p()+i-1)<=*(B.Get_p()+j-1)){
this->pushback(*(A.Get_p()+i-1));
i++;
}
else{
this->pushback(*(B.Get_p()+j-1));
j++;
}
}
if(i<=A.ListLength()){
while(i<=A.ListLength()){
this->pushback(*(A.Get_p()+i-1));
i++;
}
}
else {
while(j<=B.ListLength()){
this->pushback(*(B.Get_p()+j-1));
j++;
}
}
}
template<class T>
void List<T>::show(){
for(int i=1;i<=this->size;i++){
cout <<this->GetElem_at(i)<<' ';
}
cout <<endl;
}
//以上部分不得随便乱改。
List<int>B;
List<int>A;
int _tmain(int argc, _TCHAR* argv[])
{
for(int i=1;i<16;i++){
B.pushback(i);
}
B.show();
A=B;
A.show();
return 0;
}
热心网友
时间：2022-07-01 17:22
#include <iostream>
using namespace std;
typedef int elemtype;
struct lnode
{
lnode *next;
elemtype data;
};
void initlist(lnode *& hl)
{
hl=new lnode;
hl->next=NULL;
}
elemtype getlist(lnode *& hl,int pos)
{
int i=0;
hl=hl->next;
while(hl!=NULL)
{
i++;
if(i==pos) break;
hl=hl->next;
}
return hl->data;
}
void traverlist(lnode *hl)
{
hl=hl->next;
while(hl!=NULL)
{
cout<<hl->data<<" ";
hl=hl->next;
}
cout<<endl;
}
bool insertlist(lnode *&hl,int pos,elemtype item)
{
lnode *p=hl;
int j=0;
while(p!=NULL&&j<pos-1)
{
p=p->next;
j++;
}
if(p==NULL) return 0;
lnode *newptr=new lnode;
newptr->data=item;
newptr->next=p->next;
p->next=newptr;
return 1;
}
/*bool DeleteList(lnode *&hl,int pos,ElemType &item)
{
lnode *p=GetList(hl,pos-1);
if( p==NULL ) return 0;
lnode *q=p->next;
item=q->data;
p->next=q->next;
delete q;
return 1;
}*/
void CreateList(lnode * &hl,int n)
{
lnode *ptr;
hl=new lnode ;
hl->next=NULL;
for(int i=n;i>0;i--)
{
ptr=new lnode ;
cin>>ptr->data;
ptr->next=hl->next; hl->next=ptr;
}
}
void main()
{
int a[10];
lnode *s;
initlist(s);
for(int i=0;i<10;i++)
{
cin>>a[i];
insertlist(s,1,a[i]);
}
traverlist(s);
}
