线性表顺序存储的12个基本操作，求c语言程序，在c++6.0环境下编译的

Question

如题所述

Answer 1

//顺序表的抽象数据类型定义
#include <iostream.h>
// 所有bool型函数，返回true表示操作正常完成，否则返回false。
template <class T> // 模板声明, T是类参数(即,可变类型)
class sqList
{
protected:
T *elem ; // elem是指向存放数据元素的数组指针
int Size; // 顺序表的当前长度(元素数目)
int MaxSize; // 顺序表的最大长度（容量）
public:
sqList(int ms=10); // 构造函数
sqList(const sqList<T>&); // 复制构造函数
~sqList() // 析构函数
{ delete[] elem; }
sqList& operator=(const sqList<T>&); //"="运算符重载
bool isEmpty() // 判断顺序表是否为空表
{ return Size==0; }
bool isFull() // 判断顺序表是否已"满"
{ return Size==MaxSize; }
int Length() // 求顺序表的长度
{ return Size; }
bool GetNode(int index, T& e); // 取表中第index个数据元素存入e
int LocateNode(T e); // 查找值为e的元素
int LocateNode(T e,int,int); // 在给定范围内查找值为e的元素
bool InsertNode(T e, int index); // 插入值为e的新数据元素使其成为表的第index个元素
bool InsertNode(T e); // 按元素值e的大小插入（顺序表有序）
bool DeleteNode(int index,T& e); // 从顺序表中删除第index个数据元素 被删除元素存入e
void traverse(char); // 遍历顺序表
};
template<class T>void visitNodeData(T); //输出数据域T实例化后才能确定访问方式
template <class T>void sqList<T>::traverse(char endchar) // endchar是表结束符
{ for(int i=0; i<Size; i++) visitNodeData(elem[i]);
cout<<endchar<<" \n Length="<<Size<<"\n";
}
template <class T>sqList<T>::sqList(int ms) //构造“空”顺序表
{ if (ms<=0){ cout<<"ERROR:invalid MaxSize!!\n"; return ; }
elem=new T[ms]; MaxSize=ms; Size=0;
}
template <class T>sqList<T>::sqList(const sqList<T>& obj)
// 由顺序表obj复制构造新表
{ MaxSize=obj.MaxSize; Size=obj.Size; // 被构造表与obj表容量、表长应相同
elem=new T[MaxSize];
for(int j=0;j<Size;j++)elem[j]=obj.elem[j]; //复制数据元素
}
template<class T>sqList<T>& sqList<T>::operator=(const sqList<T>&origin)
//"="运算符重载
{ if(MaxSize!=origin.MaxSize) // 当前表与origin表容量不等
// 需释放原来的存放数据元素空间，重新为当前表申请空间
{ delete[] elem;
MaxSize=origin.MaxSize;
elem=new T[MaxSize];
}
Size=origin.Size; // 当前表长与origin表长应相同
for(int j=0;j<Size;j++)elem[j]=origin.elem[j]; //复制数据元素
}
template <class T>bool sqList<T>::GetNode(int index, T& e)
{ if(index<1||index>Size) return false;
e=elem[index-1]; return true;
}
template <class T>int sqList<T>::LocateNode(T e)
{ int i=0;
while( i<Size && elem[i]!= e )i++;
if(i<Size) return i+1; else return -1;
}
template <class T>int sqList<T>::LocateNode(T e,int low,int up)
// 在给定范围low-up间查找值为e的元素,返回-1表示被查元素不存在，否则是被查元素的序号
{ int i=low-1;
while( i<up && elem[i]!= e )i++;
if(i<up) return i+1; else return -1;
}
template <class T>bool sqList<T>::InsertNode(T e, int index)
{ int j; bool r=false;
if(index<1||index>Size+1) // 非法插入位置
cout<<"ERROR:invalid index!!\n";
else
if(isFull()) // 表满（溢出）
cout<<"ERROR: overflow !!";
else{
for(j=Size; j>=index; j--) // 数据元素依次后移
elem[j]=elem[j-1];
elem[j]=e; // 插入新数据元素
Size++; // 表长增1
r=true; // 设置插入正常标志
}
return r;
}
template <class T>bool sqList<T>::InsertNode(T e)
// 将数据元素e插入有序表，使保持有序
{ int j;
if(isFull()) // 返回，表溢出无法插入
{ cout<<"ERROR: overflow !!"; return false; }
for(j=Size; j>0; j--) // 边查找应插入位置边移动元素
if(elem[j-1]>e) elem[j]=elem[j-1];
else break;
elem[j]=e; // 插入新数据元素
Size++; // 表长增1
return true; // 返回插入正常标志
}
template <class T>bool sqList<T>::DeleteNode(int index, T& e)
{ int j; bool r=false;
if(index<1||index>Size) //非法删除位置
cout<<"ERROR:invalid index!!\n";
else
{
e = elem[index-1]; //被删数据元素值放入e
for(j=index;j<Size;j++)elem[j-1]=elem[j]; //数据元素依次前移
Size--; //表长减1
r=true; //设置删除正常标志
}
return r;
}

Answer 2

#include<stdio.h>
　　typedef int elemType;
　　/************************************************************************/
　　/* 以下是关于线性表顺序存储操作的16种算法 */
　　/************************************************************************/
　　struct List{
　　elemType *list;
　　int size;
　　int maxSize;
　　};
　　void againMalloc(struct List *L)
　　{
　　/* 空间扩展为原来的2倍，并由p指针所指向，原内容被自动拷贝到p所指向的存储空间 */
　　elemType *p = realloc(L->list, 2 * L->maxSize * sizeof(elemType));
　　if(!p){ /* 分配失败则退出运行 */
　　printf("存储空间分配失败! ");
　　exit(1);
　　}
　　L->list = p; /* 使list指向新线性表空间 */
　　L->maxSize = 2 * L->maxSize; /* 把线性表空间大小修改为新的长度 */
　　}
　　/* 1.初始化线性表L，即进行动态存储空间分配并置L为一个空表 */
　　void initList(struct List *L, int ms)
　　{
　　/* 检查ms是否有效，若无效的则退出运行 */
　　if(ms <= 0){
　　printf("MaxSize非法! ");
　　exit(1); /* 执行此函数中止程序运行，此函数在stdlib.h中有定义 */
　　}
　　L->maxSize = ms; /* 设置线性表空间大小为ms */
　　L->size = 0;
　　L->list = malloc(ms * sizeof(elemType));
　　if(!L->list){
　　printf("空间分配失败! ");
　　exit(1);
　　}
　　return;
　　}
　　/* 2.清除线性表L中的所有元素，释放存储空间，使之成为一个空表 */
　　void clearList(struct List *L)
　　{
　　if(L->list != NULL){
　　free(L->list);
　　L->list = 0;
　　L->size = L->maxSize = 0;
　　}
　　return;
　　}
　　/* 3.返回线性表L当前的长度，若L为空则返回0 */
　　int sizeList(struct List *L)
　　{
　　return L->size;
　　}
　　/* 4.判断线性表L是否为空，若为空则返回1, 否则返回0 */
　　int emptyList(struct List *L)
　　{
　　if(L->size ==0){
　　return 1;
　　}
　　else{
　　return 0;
　　}
　　}
　　/* 5.返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行 */
　　elemType getElem(struct List *L, int pos)
　　{
　　if(pos < 1 || pos > L->size){ /* 若pos越界则退出运行 */
　　printf("元素序号越界! ");
　　exit(1);
　　}
　　return L->list[pos - 1]; /* 返回线性表中序号为pos值的元素值 */
　　}
　　/* 6.顺序扫描(即遍历)输出线性表L中的每个元素 */
　　void traverseList(struct List *L)
　　{
　　int i;
　　for(i = 0; i < L->size; i++){
　　printf("%d ", L ->list[i]);
　　}
　　printf(" ");
　　return;
　　}
　　/* 7.从线性表L中查找值与x相等的元素，若查找成功则返回其位置，否则返回-1 */
　　int findList(struct List *L, elemType x)
　　{
　　int i;
　　for(i = 0; i < L->size; i++){
　　if(L->list[i] == x){
　　return i;
　　}
　　}
　　return -1;
　　}
　　/* 8.把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0 */
　　int updatePosList(struct List *L, int pos, elemType x)
　　{
　　if(pos < 1 || pos > L->size){ /* 若pos越界则修改失败 */
　　return 0;
　　}
　　L->list[pos - 1] = x;
　　return 1;
　　}
　　/* 9.向线性表L的表头插入元素x */
　　void inserFirstList(struct List *L, elemType x)
　　{
　　int i;
　　if(L->size == L->maxSize){
　　againMalloc(L);
　　}
　　for(i = L->size - 1; i >= 0; i--){
　　L->list[i + 1] = L ->list[i];
　　}
　　L->list[0] = x;
　　L->size ++;
　　return;
　　}
　　/* 10.向线性表L的表尾插入元素x */
　　void insertLastList(struct List *L, elemType x)
　　{
　　if(L->size == L ->maxSize){ /* 重新分配更大的存储空间 */
　　againMalloc(L);
　　}
　　L->list[L->size] = x; /* 把x插入到表尾 */
　　L->size++; /* 线性表的长度增加1 */
　　return;
　　}