Question

如何建立一个线性表，用c++的基本语法是什么？

例如我要建立一个一个线性表，并初始化
如何销毁一个线性表
如何判断该线性表是否为空啊
返回该线性表中的元素个数啊
插入元素，删除元素..等等
我才刚刚学，书上都没解释，看不懂
希望给位大虾多多补充....用c++哦

Answer 1

用c++建立一个线性表有以下5步：

1、准备数据：

定义了顺序表的最大长度MAXLEN、顺序表数据元素的类型DATA以及顺序表的数据结构SLType。在数据结构SLType中，Listen为顺序表已存结点的数量，也就是当前顺序表的长度，ListData是一个结构数组，用来存放各个数据结点。我们认为该顺序表是一个班级学生的记录。其中，key为学号，name为学生的名称，age为年龄。因为数组都是从下标0开始的，为了使用方便，我们从下标1开始记录数据结点，下标0的位置不可用。

2、初始化顺序表：

在使用顺序表之前，首先创建一个空的顺序表，也就是初始化顺序表。这里，在程序中只需设置顺序表的结点数量ListLen为0即可。这样，后面需要添加的数据元素将从顺序表的第一个位置存储。
示例代码：

3、计算线性表的长度：计算线性表的长度也就是计算线性表中结点的个数，由于我们在SLType中定义了ListLen来表示结点的数量，所以我们只需要获得这个变量的值即可。

4、插入结点：

插入节点就是在线性表L的第i个位置上插入一个新的结点，使其后的结点编号依次加1。这时，插入一个新节点之后，线性表L的长度将变为n+1。插入结点操作的难点在于随后的每个结点数据都要向后移动，计算机比较大，示例代码如下：

5、追加结点：

追加结点就是在顺序表的尾部插入结点，因此不必进行大量数据的移动，代码实现与插入结点相比就要简单的多。

Answer 2

#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 3

以链表为例：首先定义一个节点
struct node {
int data;
node* next;
};
定义一个向链表增加新节点的函数Push（）：
void Push(node** headRef, int data)
{
node* newNode = new node;
newNode->data = data;
newNode->next = *headRef; // *headRef是实际表头
*headRef = newNode;
}
调用该函数建立线性链表（以3个节点为例）：
void main()
{
node* head = NULL; //空表
Push(&head, 3); // 注意&运算符
Push(&head, 2);
Push(&head, 1);
Push(&head, 13);
// 表head为 {13, 1, 2, 3}
}
node* head = NULL则为空表。
计算链表结点个数的函数：
//给定链表的头指针，计算并返回链表结点的个数
int Length(node* head)
{
node* current = head;
int count = 0;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
下面分别是插入和删除函数代码，直接调用即可：
插入：
void Insert(node* &head，node* position)
{
node * before, *current;
before = current = head;
//搜索链表，确定指针before和current
while (current!=NULL)
if(current->data >= position ->data) break;
else{
before = current;
current = current->next;
}
//插入结点position
if(current == head){ //插在链表头
position ->next = head;
head = position;
}
else{ //插在链表中间
before ->next = position;
position ->next = current;
}
}
删除：
void Delete(node* &head，int data)
{
node * before, *current;
before = current = head;
//搜索链表，确定指针before和current
while (current!=NULL)
if(current->data == data) break;
else{
before = current;
current = current->next;
}
//删除数据域为data的结点
if(current!=0){
if(current == head){ //删除链表头结点
head = current ->next;
delete current;
}
else{ //删除链表中间结点
before ->next = current ->next;
delete current;
}
}
}

Answer 4

#include <iostream.h>
#include <conio.h>
#include <alloc.h>
typedef int Elemtype;
//线性表的基本操作
void Initiallist(Elemtype *L);
int Isempty(Elemtype *L);
void ListTraverse(Elemtype *L);
int NextElem(Elemtype *L);
int PriorElem(Elemtype *L);
int LocateElem(Elemtype *L,Elemtype &e);
void GetElem(Elemtype *L);
void ListInsert(Elemtype *L);
void ListDelete(Elemtype *L);
void ClearList(Elemtype *L);
const int N=10;
Elemtype temp;//全局变量！
void Initiallist(Elemtype *L)
{
for(int i=0;i<N;i++)
*(L+i)='#';
}
int Isempty(Elemtype *L)
{
if(*L=='#')
return 1;
else
return 0;
}
void ListTraverse(Elemtype *L)
{
static int k;
if(*(L)==35)
cout<<"The list is NULL!\n";
else
{
cout<<"The records of the list are:\n";
for(int i=0;i<N+k;i++)
{
if((*(L+i)>32768))
break;
else
cout<<*(L+i)<<" ";
}
k++;
}
}
int NextElem(Elemtype *L)
{
int index;
Elemtype e;
cout<<"Input the records for searching it's next Elem!\n";
cin>>e;
index=LocateElem(L,e);
if(*(L+index+1)>32768)
cout<<"It has no next Elem!\n";
else
cout<<e<<"的后继是："<<*(L+index+1)<<endl;
}
int PriorElem(Elemtype *L)
{
int index;
Elemtype e;
cout<<"Input the records for searching it's prior Elem!\n";
cin>>e;
index=LocateElem(L,e);
if(index>N)
cout<<"It has no next Elem!\n";
else if(index==-1||index==0)
{
cout<<"It has no prior Elem!\n";
return 0;
}
else
cout<<e<<"的前驱是："<<*(L+index-1)<<endl;
}
int LocateElem(Elemtype *L,Elemtype &e)
{
int i;
for(i=0;i<N+1&&(*(L+i)!='#');i++)
{
if(*(L+i)==e)
return i;
else
continue;
}
if(i<N||i>=N)
return -1;
return i;
}
void GetElem(Elemtype *L)
{
int index;
cout<<"Input the value of i:\n";
cin>>index;
if(*(L+index-1)>32768)
cout<<"The records NULL!\n";
else
cout<<"The records which you want to search are: "<<*(L+index-1)<<endl;
}
void ListInsert(Elemtype *L)
{
Elemtype e;
int index,i;
cout<<"Please input only one inserted number and it's location!\n";
cin>>e;
cin>>index;
if(index>N)
*(L+index-1)=e;
else
{
for(i=N;i>=index;i--)
*(L+i)=*(L+i-1);
*(L+index-1)=e;
}
ListTraverse(L);
}
void ListDelete(Elemtype *L)
{
Elemtype e;
int index,i;
cout<<"Input the number which you want to deleted!\n";
cin>>e;
index=LocateElem(L,e);
for(i=index;i<N+1&&(*(L+i)!='#');i++)
*(L+i-1)=*(L+i);
cout<<"Deleted "<<e<<endl;
ListTraverse(L);
}
void ClearList(Elemtype *L)
{
for(int i=0;i<N+1;i++)
*(L+i)='#';
}
int main()
{
int choice,flag=0;
char ch;
Elemtype *p,e;
p=(Elemtype *)malloc((N+1)*sizeof(Elemtype));
if(!p)
{
cout<<"No more memory can be obtained!\n";
goto loop;
}
loop: p=(Elemtype *)realloc(p,(N+1)*sizeof(Elemtype));
if(!p)
{
cout<<"overflow!\n";
exit(0);
}
Initiallist(p);
cout<<"Input "<<N<<" records!\n";//数据互不相同！
for(int i=0;i<N;i++)
cin>>*(p+i);
if(Isempty(p))
cout<<"The list is NULL!\n";
cout<<" Menu Fuction \n"
<<" 1: 遍历线性表的元素！（ 只允许调用一次！）\n"
<<" 2: 求某一元素的前驱和后继！\n"
<<" 3: 获取线性表L中的第i个数据元素内容！\n"
<<" 4: 在线性表中插入一个元素！\n"
<<" 5: 删除线性表中值为e的元素！\n"
<<" 6: 检索值为e的数据元素！\n"
<<" 7: 清空线性表！"<<endl;
do
{
cout<<"Please input your choice!\n";
cin>>choice;
switch(choice)
{
case 1: ListTraverse(p); break;
case 2: NextElem(p);
PriorElem(p);
break;
case 3: GetElem(p); break;
case 4: ListInsert(p); break;
case 5: ListDelete(p); break;
case 6:
cout<<"Input the records !\n" ;
cin>>e;
cout<<"It's location is "<<LocateElem(p,e)+1;
break;
case 7: ClearList(p);
cout<<"Now ";
ListTraverse(p);
break;
}
cout<<"\nDid you want to continue the operation?(Y/N)\n";
cin>>ch;
if(ch=='Y'||ch=='y')
flag=1;
else
flag=0;
}while(flag);
free(p);
getch();
return 0;
}