Question

怎样C++实现线性表的建立、插入、删除、倒序？

急！

Answer 1

这个百度上可以搜索出来的，下面是我找的结果（因为作者匿名，不能声明作者了）：
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define ListSize 100 //表空间大小可根据实际需要而定，这里假设为100
typedef int DataType; //DataType可以是任何相应的数据类型如int, float或char
typedef struct //顺序表的定义
{ DataType data[ListSize]; //数组data用于存放表结点
int length; //当前的表长度
}SeqList;
void main()
{
SeqList L,L1,L2,L3;
DataType newelem; //新元素
int position; //插入位置、删除位置
char ch; //用于菜单
int i,t;
int dlta[20]; //希尔排序序列
L.length=0; //顺序表初始长度为0
void CreateList(SeqList *L); //建立顺序表L
void PrintList(SeqList L); //打印顺序表L
int LocateList(SeqList L,DataType newelem); //在无序顺序表L中查找元素newelem的位置
void InsertList(SeqList *L,DataType newelem,int position); //在顺序表L中插入元素newelem，位置为position
void DeleteList(SeqList *L,int position); //在顺序表L中删除位置为position的元素
void Sort1List(SeqList *L); //对顺序表L进行直接插入排序
void Sort2List(SeqList *L); //对顺序表L进行折半插入排序
int Locate1List(SeqList L,DataType newelem); //对有序顺序表L进行折半查找，newelem数据元素的位置
int Partition(SeqList *L,int low,int high); //快速排序划分函数，用于将【low,high】划分两部分，前半部分元素均小于后半部分
void Qsort(SeqList *L,int low,int high); //快速排序递归算法，【low,high】为范围
void Merge(SeqList *L,int i,int m,int n); //归并排序合并函数，将【i,m】【m+1,n】两段有序，合并为【i,n】一段有序
void MSort(SeqList *L,int s,int t); //归并排序递归算法
void ShellInsert(SeqList *L,int dk); //希尔排序步长为dk函数
void ShellSort(SeqList *L,int dlta[],int t); //希尔排序算法，dlta为步长序列
void MergeList(SeqList L1,SeqList L2,SeqList *L3); //对递增顺序表L1，L2进行合并，结果存放在顺序表L3中
void Merge1List(SeqList L1,SeqList L2,SeqList *L3); //对递增顺序表L1，L2求交集，结果存放在顺序表L3中
void Merge2List(SeqList L1,SeqList L2,SeqList *L3); //对递增顺序表L1，L2求并集，即去重复，结果存放在顺序表L3中
void Merge3List(SeqList *L1,SeqList L2); //对递增顺序表L1，L2进行合并，结果存放在顺序表L1中
void reverse(SeqList *L); //逆置线性表函数
void delall(SeqList *L, DataType newelem); //删除特定元素（线性表中有重复元素）
do {
cout<<endl;
cout<<" *******************顺序线性表功能菜单*******************"<<endl;
cout<<" * a：建立线性表 b：无序查找元素 *"<<endl;
cout<<" * c: 插入元素 d：删除元素 *"<<endl;
cout<<" * e：直接插入排序 f：折半插入排序 *"<<endl;
cout<<" * g：有序折半查找 h：快速排序 *"<<endl;
cout<<" * i：归并排序 j: 希尔排序 *"<<endl;
cout<<" * K： l: *"<<endl;
cout<<" * m： n: *"<<endl;
cout<<" * o： p: *"<<endl;
cout<<" * q：二个递增顺序表合并 r: 二个递增顺序表原地合并*"<<endl;
cout<<" * s：二个递增顺序表求交集 t: 二个递增顺序表求并集 *"<<endl;
cout<<" * u：逆置线性表 v: 删除特定元素 *"<<endl;
cout<<" * w： x: *"<<endl;
cout<<" * z：退出 *"<<endl;
cout<<" ********************************************************"<<endl;
cout<<" 请输入你的选择：";
cin>>ch;
switch (ch)
{
case 'a':
CreateList(&L);
PrintList(L);
break;
case 'b':
cout<<" 输入要查找的值：";
cin>>newelem;
cout<<LocateList(L,newelem)<<endl;
break;
case 'c':
cout<<" 请输入要插入的数据元素：";
cin>>newelem;
cout<<" 请输入要插入的元素位置：";
cin>>position;
InsertList(&L,newelem,position);
PrintList(L);
break;
case 'd':
cout<<" 请输入要删除的元素位置：";
cin>>position;
DeleteList(&L,position);
PrintList(L);
break;
case 'e':
Sort1List(&L);
PrintList(L);
break;
case 'f':
Sort2List(&L);
PrintList(L);
break;
case 'g':
cout<<" 输入要查找的值：";
cin>>newelem;
cout<<Locate1List(L,newelem)<<endl;
case 'h':
cout<<" 创建顺序表"<<endl;
CreateList(&L);
Qsort(&L,1,L.length);
PrintList(L);
break;
case 'i':
cout<<" 创建顺序表"<<endl;
CreateList(&L);
MSort(&L,1,L.length);
PrintList(L);
break;
case 'j':
cout<<" 创建顺序表"<<endl;
CreateList(&L);
cout<<" 请输入序列数：";
cin>>t;
cout<<" 请输入序列数：";
for (i=1;i<=t;i++)
cin>>dlta[i];
ShellSort(&L,dlta,t);
PrintList(L);
break;
case 'q':
cout<<" 创建第一个顺序表"<<endl;
CreateList(&L1);
cout<<" 创建第二个顺序表"<<endl;
CreateList(&L2);
Sort1List(&L1); //对第一个顺序表进行直接插入排序
PrintList(L1);
Sort2List(&L2); //对第二个顺序表进行折半排序
PrintList(L2);
MergeList(L1,L2,&L3);
PrintList(L3);
break;
case 'r':
cout<<" 创建第一个顺序表"<<endl;
CreateList(&L1);
cout<<" 创建第二个顺序表"<<endl;
CreateList(&L2);
Sort1List(&L1); //对第一个顺序表进行直接插入排序
PrintList(L1);
Sort2List(&L2); //对第二个顺序表进行折半排序
PrintList(L2);
Merge3List(&L1,L2);
PrintList(L1);
break;
case 's':
cout<<" 创建第一个顺序表"<<endl;
CreateList(&L1);
cout<<" 创建第二个顺序表"<<endl;
CreateList(&L2);
Sort1List(&L1); //对第一个顺序表进行直接插入排序
PrintList(L1);
Sort2List(&L2); //对第二个顺序表进行折半排序
PrintList(L2);
Merge1List(L1,L2,&L3);
PrintList(L3);
break;
case 't':
cout<<" 创建第一个顺序表"<<endl;
CreateList(&L1);
cout<<" 创建第二个顺序表"<<endl;
CreateList(&L2);
Sort1List(&L1); //对第一个顺序表进行直接插入排序
PrintList(L1);
Sort2List(&L2); //对第二个顺序表进行折半排序
PrintList(L2);
Merge2List(L1,L2,&L3);
PrintList(L3);
break;
case 'u':
cout<<" 创建顺序表"<<endl;
CreateList(&L);
PrintList(L);
reverse(&L);
PrintList(L);
break;
case 'v':
cout<<" 创建顺序表（有重复）"<<endl;
CreateList(&L);
cout<<" 请输入要删除的特定数据元素：";
cin>>newelem;
PrintList(L);
delall(&L, newelem);
PrintList(L);
break;
default:
break;
}
}while (ch!='z');
}
void CreateList(SeqList *L) //顺序表的建立，先确定输入数据元素个数，再依次输入数据元素
{
int i,n;
cout<<" 请输入元素个数：";
cin>>n;
cout<<" 请依次输入"<<n<<"个数：";
for (i=1; i<=n; i++)
cin>>L->data[i];
L->length=n;
}
void PrintList(SeqList L) //顺序表的打印，依次输出
{
int i;
cout<<" ";
for (i=1; i<=L.length; i++)
cout<<L.data[i]<<" ";
cout<<endl;
}
int LocateList(SeqList L,DataType newelem) //无序顺序表的查找，将被查元素放置到【0】单元起到哨兵作用，依次从尾部向头部查找
{
int i;
i=L.length;
L.data[0]=newelem; //哨兵技术
while (L.data[i]!=newelem)
i--;
return i;
}
void InsertList(SeqList *L,DataType newelem,int position) //顺序表的插入元素，先确定插入位置合理性，超越范围强制为首元素或尾元素；合理从尾部至插入位置依次后移
{
int i;
if (position<1)
position=1; //强制插入位置为首元素
else
if (position>L->length)
position=L->length+1; //强制插入位置为尾元素
;
for (i=L->length; i>=position; i--) //依次后移【插入位置，尾部】
L->data[i+1]=L->data[i];
L->data[position]=newelem;
L->length++;
}
void DeleteList(SeqList *L,int position) //顺序表的删除元素，先确定删除的合理性，将【删除位置+1，尾部】依次前移
{
int i;
if ((position<1) || (position>L->length))
{
cout<<" 删除位置不对！";
}
else
{
for (i=position; i<L->length; i++) //依次前移，范围【删除位置+1，尾部】
L->data[i]=L->data[i+1];
L->length--;
}
}
void Sort1List(SeqList *L) //直接插入排序，
{
int i,j;
for (i=2; i<=L->length; i++)
{
L->data[0]=L->data[i]; //哨兵技术
j=i-1;
while (L->data[0]<L->data[j]) //依次后移
{
L->data[j+1]=L->data[j];
j--;
}
L->data[j+1]=L->data[0];
}
}
void Sort2List(SeqList *L) //折半插入排序
{
int low,mid,high,i,j;
for (i=2; i<=L->length; i++)
{
low=1;
high=i-1;
L->data[0]=L->data[i]; //为后移作准备
if (L->data[1]>L->data[i]) //判断是否小于最小值
{
low=1;
high=1;
}
if (L->data[i-1]<L->data[i]) //判断是否大于最大值
{
low=i-1;
high=i-1;
}
while (low<high) //确定插入位置
{
mid=(low+high)/2;
if (L->data[mid]==L->data[0])
{
low=mid;
high=mid;
}
else
{
if (L->data[mid]<L->data[0])
low=mid+1;
else
high=mid-1;
}
}
if (L->data[low]<L->data[0]) //判断L->data[low]是否包括在后移范围内
low++;
for (j=i; j>low; j--) //依次后移
L->data[j]=L->data[j-1];
L->data[low]=L->data[0];
}
}
int Locate1List(SeqList L,DataType newelem) //有序顺序表的折半查找
{
int low,high,mid;
if (newelem<L.data[1]) //判断是否小于最小值
return 0;
if (newelem>L.data[L.length]) //判断是否大于最大值
return 0;
low=1;
high=L.length;
while (low<=high)
{
mid=(low+high)/2;
if (newelem==L.data[mid])
return mid;
if (newelem<L.data[mid])
high=mid-1;
else
low=mid+1;
}
return 0;
}
int Partition(SeqList *L, int low, int high)
{
int pivokey=L->data[low];
L->data[0]=L->data[low];
while (low<high)
{
while ((low<high) && (L->data[high]>=pivokey))
high--;
L->data[low]=L->data[high];
while ((low<high) && (L->data[low]<=pivokey))
low++;
L->data[high]=L->data[low];
}
L->data[low]=L->data[0];
return low;
}
void Qsort(SeqList *L, int low, int high)
{
int pivotloc;
if (low<high)
{
pivotloc=Partition(L,low,high);
Qsort(L,low,pivotloc-1);
Qsort(L,pivotloc+1,high);
}
}
void Merge(SeqList *L, int i, int m, int n)
{
SeqList L1;
int p,q,k;
for (q=m+1;q<=n;q++)
L1.data[q]=L->data[q];
p=m;
q=n;
k=n;
while ((p>=i)&&(q>=m+1))
{
if (L->data[p]>L1.data[q])
{
L->data[k]=L->data[p];
p--;
}
else
{
L->data[k]=L1.data[q];
q--;
}
k--;
}
if (p<i) //尾部处理
for (p=q;p>=m+1;p--)
{
L->data[k]=L1.data[p];
k--;
}
}
void MSort(SeqList *L, int s, int t)
{
int m;
if (s!=t)
{
m=(s+t)/2;
MSort(L,s,m);
MSort(L,m+1,t);
Merge(L,s,m,t);
}
}
void ShellInsert(SeqList *L,int dk)
{
int i,j;
for (i=dk+1;i<=L->length;i++)
if (L->data[i]<L->data[i-dk])
{
L->data[0]=L->data[i];
for (j=i-dk;(j>0)&&(L->data[0]<L->data[j]);j=j-dk)
L->data[j+dk]=L->data[j];
L->data[j+dk]=L->data[0];
}
}
void ShellSort(SeqList *L,int dlta[],int t)
{
int k;
for (k=1;k<=t;k++)
ShellInsert(L,dlta[k]);
}
void MergeList(SeqList L1,SeqList L2,SeqList *L3) //对递增顺序表L1，L2进行合并，结果存放在顺序表L3中
{
int i,j,k;
i=L1.length;
j=L2.length;
k=i+j;
L3->length=k;
while ((i>0)&&(j>0)) //控制范围
{
if (L1.data[i]<L2.data[j])
{
L3->data[k]=L2.data[j];
j--;
}
else
{
L3->data[k]=L1.data[i];
i--;
}
k--;
}
if (i==0) //尾部处理
for (i=j;i>0;i--)
{
L3->data[k]=L2.data[i];
k--;
}
else
for (j=i;j>0;j--)
{
L3->data[k]=L1.data[j];
k--;
}
}
void Merge1List(SeqList L1,SeqList L2,SeqList *L3) //对递增顺序表L1，L2求交集，结果存放在顺序表L3中
{
int i,j,k;
i=1;
j=1;
k=1;
while ((i<=L1.length)&&(j<=L2.length)) //控制范围
{
if (L1.data[i]==L2.data[j]) //相等元素，存入L3
{
L3->data[k]=L1.data[i];
i++;
j++;
k++;
}
else
if (L1.data[i]<L2.data[j])
i++;
else
j++;
}
L3->length=k-1;
}
void Merge2List(SeqList L1,SeqList L2,SeqList *L3) //对递增顺序表L1，L2求并集，即去重复，结果存放在顺序表L3中
{
int i,j,k;
i=1;
j=1;
k=1;
while ((i<=L1.length)&&(j<=L2.length)) //控制范围
{
if (L1.data[i]==L2.data[j]) //相等，存入L3
{
L3->data[k]=L1.data[i];
i++;
j++;
}
else
if (L1.data[i]<L2.data[j])
{
L3->data[k]=L1.data[i];
i++;
}
else
{
L3->data[k]=L2.data[j];
j++;
}
k++;
}
if (i>L1.length) //尾部处理
for (i=j;i<=L2.length;i++)
{
L3->data[k]=L2.data[i];
k++;
}
else
for (j=i;j<=L1.length;j++)
{
L3->data[k]=L1.data[j];
k++;
}
L3->length=k-1;
}
void Merge3List(SeqList *L1,SeqList L2) //对递增顺序表L1，L2进行合并，结果存放在顺序表L1中
{
int i,j,k;
i=L1->length;
j=L2.length;
k=i+j;
L1->length=k;
while ((i>=1)&&(j>=1))
{
if (L1->data[i]>=L2.data[j])
{
L1->data[k]=L1->data[i];
i--;
}
else
{
L1->data[k]=L2.data[j];
j--;
}
k--;
}
if (i<1)
for (i=j;i>=1;i--)
{
L1->data[k]=L2.data[i];
k--;
}
}
void reverse(SeqList *L) //顺序表逆置
{
int i;
for (i=1;i<(L->length+1)/2;i++)
{
L->data[0]=L->data[i]; //三角交换
L->data[i]=L->data[L->length-i+1];
L->data[L->length-i+1]=L->data[0];
}
}
void delall(SeqList *L, DataType newelem) //删除特定元素newelem
{
int i,j;
j=0;
for (i=1;i<=L->length;i++)
{
if (L->data[i]!=newelem)
{
j++;
L->data[j]=L->data[i];
}
}
L->length=j;
}

Answer 2

#include<iostream>
using namespace std;
typedef int ElemType;
struct NodeType
{
ElemType data;
NodeType *next;
};
class LinkList
{
private:
NodeType *Head;
public:
LinkList();//构造
~LinkList();//析构
void create();//建表
void insert(); //插入
ElemType delet();
void display();
void inverse();//逆转函数
};
//创建空链表
LinkList::LinkList()
{
Head=new NodeType;
Head->next=NULL;
Head->data=0;
}
LinkList::~LinkList()
{
NodeType *p=Head->next;
//使指针p指向链表的第一个节点
while(p!=NULL)
{
Head->next=p->next;
//使头指针指向p的下一个节点
delete p;

p=Head->next;
//使p节点指向头指针向的那个节点
}
delete Head;
//最后将头节点也删除
cout<<"已经删除链表!"<<endl;
}
void LinkList::display()
{
NodeType *p;
p=Head->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
void LinkList::create() //逆转链表元素
{
NodeType *s;
ElemType x;
cout<<"请输入一组数据并且以-10结束。"<<endl;
cin>>x; //输入数据元素。
while(x!=-10)
{
s=new NodeType; //动态的申请一个节点
s->data=x; //给节点的数据域赋值
s->next=Head->next; //使s指向第一个节点
Head->next=s; //使头节点指向新申请的s节点
cout<<"输入的元素："<<endl;
cin>>x;
}
cout<<"链表插入结束链表建成!"<<endl;
}
void LinkList::insert()
{
cout<<"要插入元素的位置："<<endl;
int i;
cin>>i;
cout<<"要插入的元素："<<endl;
ElemType x;
cin>>x;
NodeType *p,*q,*s; //定义结构体类型指针

int k=1;

p=Head; //让p指向Head节点

q=p->next; //让q指向第一个节点

while(k<i && q!=NULL)
{
p=q;
q=q->next;
k++;
}

if(k==i) //实现插入
{
s=new NodeType;
s->data=x;
p->next=s;
s->next=q;
cout<<"记录成功插入!"<<endl;
}
else
cout<<"插入记录失败！";
}
ElemType LinkList::delet()
{
cout<<"输入要删除的元素："<<endl;
int x;
cin>>x;
NodeType *p,*q;
ElemType y;
int k=1;
p=Head;
q=p->next;
while(q!=NULL && q->data!=x)
{
p=q;
q=q->next;
}
if(q->data==x)
{
y=q->data;
p->next=q->next;
delete q;
cout<<"记录成功删除!"<<endl;
}
else
{
cout<<"x不存在"<<endl;
y=-1;
}
return y;
}

void LinkList::inverse() // 链表的逆置
{
NodeType *p,*q;
p=Head->next; //让p指向第一个元素

Head->next=NULL; //让Head的指针域为空
while(p!=NULL)
{
q=p->next; //让q指向第二个元素
p->next=Head->next; //让p的指针域为空
Head->next=p;
p=q;
}

}
void main()
{
LinkList h;
h.create();
h.display();
h.delet();
h.display();
h.insert();
h.display();
cout<<"进行链表元素逆置"<<endl;
h.inverse();
h.display();
}

希望可以帮到你!

Answer 3

#include "iostream.h"
typedef struct NODE
{
int x;
struct NODE *next;
}node;
class Link
{
public:
node* create();
void sert(node* h,int n);
void del(node *h,int n);
};
node* Link::create()
{
node *h;
h=new node;
return h;
}
void Link::sert(node* h,int n)
{
node *p;
node *q;
p=h;
while (p->next=NULL)
{
q=p->next;
p=q;
}
q=new node;
q->x=n;
p->next=q;
}
void Link::del(node* h,int n)
{
node *p;
node *q;
p=h;
while (p->next!=NULL)
{
q=p->next;
if(q->x=n)
{
p->next=q->next;
delete(q);
break;
}
p=q;
}
}
void main()
{
Link lk;
lk.create();
}