实验二 线性表的基本操作
一、实验目的
1．掌握用 C++/C语言调试程序的基本方法。
2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。
二、实验要求
1．C++/C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3． 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
三、实验内容：
1. 分析并运行以下各子程序的主要功能。
程序1：顺序存储的线性表和运算
#include
#define MAXSIZE 100
int list[MAXSIZE];
int n;
/*insert in a seqlist*/
int sq_insert(int list[], int *p_n, int i, int x)
{int j;
if (i*p_n) return(1);
if (*p_n==MAXSIZE) return(2);
for (j=*p_n+1; j>i; j--)
list[j]=list[j-1];
list[i]=x;
(*p_n)++;
return(0);
}
/*delete in a seq list*/
int sq_delete(int list[], int *p_n, int i)
{int j;
if (i=*p_n) return(1);
for (j = i+1; j
list[j-1] = list[j];
(*p_n)--;
return(0);
}
void main()
{int i,x,temp;
printf("please input the number for n\n");
printf("n=");
scanf("%d",&n);
for (i=0; i
{printf("list[%d]=",i);
scanf("%d",&list[i]);}
printf("The list before insertion is\n");
for (i=0; i
printf("\n");
printf("please input the position where you want to insert a value\nposition="); scanf("%d",&i);
printf("please input the value you want to insert.\nx=");
scanf("%d",&x);
temp=sq_insert(list,&n,i,x);
switch(temp)
{case 0:printf("The insertion is successful!\n");
printf("The list is after insertion is\n");
for(i=0; i
printf("\n");
printf("%d\n",n);
break;
case 1:
case 2:printf("The insertion is not successful!\n");break;}
/*deleting*/
printf("The list before deleting is\n");
for (i=0; i
printf("\n");
printf("please input the position where you want to delete a value\nposition="); scanf("%d",&i);
temp=sq_delete(list,&n,i);
switch(temp)
{case 0:printf("The deleting is successful!\n");
printf("The list is after deleting is\n");
for(i=0; i
printf("\n");
printf("%d",n);
break;
case 1:printf("The deleting is not successful!");break;}
}
2. 分析并运行以下各子程序的主要功能。
程序2链式存储的线性表和运算
#include
#include
struct node{
char data;
struct node *next;
};
typedef struct node NODE;
/*This function creates a link_list with N nodes.*/
NODE *create_link_list(int n)
{int i;
NODE *head, *p, *q;
if (n==0) return NULL;
head = (NODE *) malloc(sizeof(NODE));
p = head;
printf("Please input %d chars for the link list\n",n);
for (i=0; i
{scanf("%c ", &(p->data));
q=(NODE *)malloc(sizeof(NODE));
printf("test3\n");
p->next=q;
p=q;}
scanf("%c ",&(p->data));
getchar();
p->next=NULL;
return (head);}
/*This function inserts a node whose value is b*/
/*before the node whose value is a, if the node is not exist,*/
/*then insert it at the end of the list*/
void insert(NODE **p_head, char a, char b)
{NODE *p, *q;
q = (NODE *)malloc(sizeof(NODE));
q->data = b;
q->next =NULL;
if (* p_head == NULL) * p_head = q;
else
{p=(NODE*)malloc(sizeof(NODE));
p = * p_head;
while (p->data != a && p->next != NULL)
p = p->next;
q->next = p->next;
p->next = q;}
}
/*The function deletes the node whose value is a,*/
/*if success, return 0, or return 1*/
int deletenode(NODE **p_head, char a)
{NODE *p, *q;
q=*p_head;
if (q==NULL) return(1);
if (q->data == a)
{* p_head = q->next;
free(q);
return (0);}
else
{while (q->data != a && q->next != NULL)
{p = q;
q = q->next;}
if (q->data == a)
{p->next = q->next;
free(q);
return(0);}
else return(1);}
}
void main()
{ NODE *my_head,*p;
} /* create a link list with m nodes */ int m; char ch_a,ch_b; printf("please input the number of nodes for the link_list\nm="); scanf("%d",&m); getchar(); printf("test1\n"); my_head = (NODE *) malloc(sizeof(NODE)); my_head=create_link_list(m); /*Output the link list*/ printf("The link list is like:\n"); p=my_head; while (p != NULL) {printf("%c ",p->data); p=p->next; } printf("\n"); /*insert a node whose value is b before a*/ printf("Please input the position for a\n ch_a="); getchar(); scanf("%c",&ch_a); getchar(); printf("Please input the value that you want to insert\n ch_b="); scanf("%c",&ch_b); getchar(); insert(&my_head,ch_a,ch_b); printf("The link list after insertion is like:\n"); p=my_head; while (p != NULL) {printf("%c ",p->data); p=p->next; } printf("\n"); /*delete a node whose value is a*/ printf("Please input the position for a a="); scanf("%c",&ch_a); getchar(); deletenode(&my_head,ch_a); printf("The link list after deleting is like:\n"); p=my_head; while (p != NULL) {printf("%c ",p->data); p=p->next; } printf("\n");
3. 运行以下程序并分析各子函数的主要功能。
#include
#include
struct tagNode
{
int data;
struct tagNode *pNext;
};
typedef struct tagNode* pNode;
//将结点插入到链表的适当位置，这是一个降序排列的链表
//
void insertList(pNode head,//链表头结点
pNode pnode)//要插入的结点
{
pNode pPri=head;
while (pPri->pNext!=NULL)
{
if (pPri->pNext->datadata)
{
pnode->pNext=pPri->pNext;
pPri->pNext=pnode;
break;
}
pPri=pPri->pNext;
}
if (pPri->pNext==NULL)//如果要插入的结点最小
{
pPri->pNext=pnode;
}
}
//输出链表
void printLinkedList(pNode head)
{
pNode temp=head->pNext;
while (temp!=NULL)
{
printf("%d ",temp->data);
temp=temp->pNext;
}
}
//从链表中删除结点
void delformList(pNode head,int data)
{
pNode temp=head->pNext;
pNode pPri=head;
while (temp!=NULL)
{
if (temp->data==data)
{
pPri->pNext=temp->pNext;
free(temp);
break;
}
pPri=temp;
temp=temp->pNext;
}
}
void main()
{
pNode head=(pNode)malloc(sizeof(struct tagNode));//给头指针分配空间
pNode pTemp=NULL;
int temp;
head->pNext=NULL;//比较好的习惯就是分配好空间，马上赋值
printf("请输入要放入链表中的数据，以-1结尾：");
//读入数据，以-1结尾，把数据插入链表中
scanf("%d",&temp);
while (temp!=-1)
{
pTemp=(pNode)malloc(sizeof(struct tagNode));
pTemp->data=temp;
pTemp->pNext=NULL;
insertList(head,pTemp);
scanf("%d",&temp);
}
printf("降序排列的链表为：\n");
printLinkedList(head);
printf("\n");
//下面的代码当删除函数编写成功后，可以取消注释，让其执行,主要是调用函数实现链表结点的删除
//printf("请输入要删除数，以-1结尾：");
//scanf("%d",&temp);
//while (temp!=-1)
//{
// delformList(head,temp);
}
// scanf("%d",&temp); //} //printf("删除节点后，链表中剩余数据为："); //printLinkedList(head); //printf("\n");
四、思考与提高
试将以上链表改为有序表，并分析有序表有哪些显著的优点和缺点？ 库函数载和常量定义：（代码,C++）
#include
using namespace std;
const int MaxSize=100;
（1）顺序表存储结构的定义(类的声明)：（代码）
template //定义模板类SeqList
class SeqList
{
public:
SeqList( ); //无参构造函数
SeqList(datatype a[ ], int n); //有参构造函数
~SeqList(){}; //析构函数为空
int Length(); //求线性表的长度
datatype Get(int i); //按位查找，取线性表的第i个元素 int Locate(datatype item); //查找元素item
void Insert(int i, datatype item); //在第i个位置插入元素item datatype Delete(int i); //删除线性表的第i个元素 void display(); //遍历线性表，按序号依次输出各元素 private:
datatype data[MaxSize]; //存放数据元素的数组
int length; //线性表的长度
};
（2）初始化顺序表算法实现（不带参数的构造函数）
/*
*输 入：无
*前置条件：顺序表不存在
*功 能：构建一个顺序表
*输 出：无
*后置条件：表长为0
*/
实现代码：
template
SeqList:: SeqList( )
{
length=0;
}
（3）顺序表的建立算法（带参数的构造函数） /*
*输 入：顺序表信息的数组形式a[],顺序表长度n *前置条件：顺序表不存在
*功 能：将数组a[]中元素建为长度为n的顺序表 *输 出：无
*后置条件：构建一个顺序表
*/
实现代码：
template
SeqList:: SeqList(datatype a[], int n)
{
if (n>MaxSize)
{
cout
}
for (int i=0; i
data[i]=a[i];
length=n;
}（4）在顺序表的第i个位置前插入元素e算法 /*
*输 入：插入元素e,插入位置i
*前置条件：顺序表存在，i要合法
*功 能：将元素e插入到顺序表中位置i处 *输 出：无
*后置条件：顺序表插入新元素，表长加1
*/
实现代码：
template
void SeqList::Insert(int i, datatype item) {
int j;
if (length>=MaxSize)
{
cout
}
if (ilength+1)
{
cout
}
for (j=length; j>=i; j--)
data[j]=data[j-1];
data[i-1]=item;
length++;
}（5）删除线性表中第i个元素算法
/*
*输 入：要删除元素位置i
*前置条件：顺序表存在,i要合法
*功 能：删除顺序表中位置为i的元素
*输 出：无
*后置条件： 顺序表册除了一个元素，表长减1 */
实现代码：
template
datatype SeqList::Delete(int i)
{
int item,j;
if (length==0)
{
cout
if (ilength)
{
cout
}
item=data[i-1];//获得要删除的元素值
for (j=i; j
data[j-1]=data[j]; //注意数组下标从0记 length--;
return item;
}（6）遍历线性表元素算法
/*
*输 入：无
*前置条件：顺序表存在
*功 能：顺序表遍历
*输 出：输出所有元素
*后置条件：无
*/
实现代码：
template
void SeqList::display()
{
if(length==0)
{
cout
}
for(int i=0;i
{
cout
}
}
（7）获得线性表长度算法
/*
*输 入：无
*前置条件：顺序表存在
*功 能：输出顺序表长度
*输 出：顺序表长度
*后置条件：无
*/
实现代码：
template
int SeqList::Length()
{
return Length;
}
（8）在顺序线性表中查找e值，返回该元素的位序算法 /*
*输 入：查询元素值e
*前置条件：顺序表存在
*功 能：按值查找值的元素并输出位置
*输 出：查询元素的位置
*后置条件：无
*/
实现代码：
template
int SeqList::Locate(datatype item)
{
for (int i=0; i
if (data[i]==item)
return i+1 ;
//下标为i的元素等于item，返回其序号i+1 return 0; //查找失败
}
（9）获得顺序线性表第i个元素的值
/*
*输 入：查询元素位置i
*前置条件：顺序表存在，i要合法
*功 能：按位查找位置为i的元素并输出值 *输 出：查询元素的值
*后置条件：无
*/
实现代码：
template
datatype SeqList::Get(int i)
{
if (ilength)
{
cout
}
else return data[i-1];
}
（10）判表空算法
/*
*输 入：无
*前置条件：无
*功 能：判表是否为空
*输 出：为空返回1，不为空返回0
*后置条件：无
*/
实现代码：
template
bool SeqList::Empty()
{
if (length==0)
{
return 1;
}
else
{
return 0;
}
}
(11)求直接前驱结点算法
/*
*输 入：要查找的元素e，待存放前驱结点值e1
*前置条件：无
*功 能：查找该元素的所在位置，获得其前驱所在位置。
*输 出：返回其前驱结点的位序。
*后置条件：e1值为前驱结点的值
*/
实现代码：
template
int SeqList::Pre(datatype item)
{
int k=Locate(item)-1;
if (k>0)
return k;
else
{
cout
return 0;
}
}
(12)求直接后继结点算法
/*
*输 入：要查找的元素e，待存放后继结点值e1
*前置条件：无
*功 能：查找该元素的所在位置，获得其后继所在位置。
*输 出：返回其后继结点的位序。
*后置条件：e1值为后继结点的值
*/
实现代码：
template
int SeqList::Suc(datatype item)
{
int k=Locate(item)+1;
if (k>length)
{
cout
return 0;
}
else
{
return k;
}
}
上机实现以上基本操作，写出main()程序：
用以上基本操作算法，实现A=AUB算法。（利用函数模板实现）
/*
*输 入：集合A,集合B
*前置条件：无
*功 能：实现A=AUB
*输 出：无
*后置条件：A中添加了B中的元素。
*/
实现代码：
template
SeqList SeqList::Add(SeqList& item)
{
if (item.Empty())
return *this;
else
{
int k=item.Length();
int num=this->Length();
for (int i=1;i
{
for(int j=0;j
if (data[j]==item.Get(i))
{
break;
}
else if (num-1==j&&data[num-1]!=item.Get(i))
{
this->Insert(++num,item.Get(i));
}
}
return *this;
}
}
void main()
{
SeqList A,B;
cout
A.Insert(1,1);
A.Insert(2,2);
A.Insert(3,3);
A.Insert(4,4);
A.Insert(5,5); //插入集合A中元素
B.Insert(1,2);
B.Insert(2,6);
B.Insert(3,1);
B.Insert(4,8);
B.Insert(5,9); //插入集合B中元素
A.Add(B);
A.display();
cout
}
实现代码：
template
void SeqList::orderInsert(datatype item)
{
int num=this->Length();
for (int i=0;i
{
if ((data[i]item))
{
for (int k=num;k>i;k--)
data[k]=data[k-1];
data[i+1]=item;
length++;
break;
}
if (data[i]>item)
{
for(int k=num;k>i;k--)
data[k]=data[k-1];
data[i]=item;
length++;
break;
}
}
}
void main()
{
SeqList A,B;
A.Insert(1,3);
A.Insert(2,5);
A.Insert(3,6);
A.Insert(4,8);
A.Insert(5,10); //插入顺序表
cout
A.display(); //输出顺序表
cout
A.orderInsert(2);
A.orderInsert(4); //插入元素
cout
A.display(); //输出重新排序后的顺序表
}
算法实现：La,Lb为非递减的有序线性表，将其归并为Lc，该线性表仍有序（未考虑相同时删除一重复值）（利用函数类板实现）
MergeList：
/*
*输 入：有序线性表La,有序线性表Lb
*前置条件：顺序表已有序
*功 能：将两线性表归并，不去掉相同元素
*输 出： 返回一个新的有序线性表Lc
*后置条件：无
*/
实现代码：
template
SeqList SeqList::ElseAdd(SeqList Seq1,SeqList Seq2)
{
int num=Seq2.Length();
for(int i=0;i
Seq1.orderInsert(Seq2.Get(i));
}
return Seq1;
}
void main()
{
SeqList La,Lb,Lc;
La.Insert(1,2);
La.Insert(2,4);
La.Insert(3,6);
La.Insert(4,8); //插入La
cout
La.display(); //输出La
cout
Lb.Insert(1,3);
Lb.Insert(2,6);
} Lb.Insert(3,8); //插入Lb cout
实验二 线性表的基本操作
一、实验目的
1．掌握用 C++/C语言调试程序的基本方法。
2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。
二、实验要求
1．C++/C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3． 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
三、实验内容：
1. 分析并运行以下各子程序的主要功能。
程序1：顺序存储的线性表和运算
#include
#define MAXSIZE 100
int list[MAXSIZE];
int n;
/*insert in a seqlist*/
int sq_insert(int list[], int *p_n, int i, int x)
{int j;
if (i*p_n) return(1);
if (*p_n==MAXSIZE) return(2);
for (j=*p_n+1; j>i; j--)
list[j]=list[j-1];
list[i]=x;
(*p_n)++;
return(0);
}
/*delete in a seq list*/
int sq_delete(int list[], int *p_n, int i)
{int j;
if (i=*p_n) return(1);
for (j = i+1; j
list[j-1] = list[j];
(*p_n)--;
return(0);
}
void main()
{int i,x,temp;
printf("please input the number for n\n");
printf("n=");
scanf("%d",&n);
for (i=0; i
{printf("list[%d]=",i);
scanf("%d",&list[i]);}
printf("The list before insertion is\n");
for (i=0; i
printf("\n");
printf("please input the position where you want to insert a value\nposition="); scanf("%d",&i);
printf("please input the value you want to insert.\nx=");
scanf("%d",&x);
temp=sq_insert(list,&n,i,x);
switch(temp)
{case 0:printf("The insertion is successful!\n");
printf("The list is after insertion is\n");
for(i=0; i
printf("\n");
printf("%d\n",n);
break;
case 1:
case 2:printf("The insertion is not successful!\n");break;}
/*deleting*/
printf("The list before deleting is\n");
for (i=0; i
printf("\n");
printf("please input the position where you want to delete a value\nposition="); scanf("%d",&i);
temp=sq_delete(list,&n,i);
switch(temp)
{case 0:printf("The deleting is successful!\n");
printf("The list is after deleting is\n");
for(i=0; i
printf("\n");
printf("%d",n);
break;
case 1:printf("The deleting is not successful!");break;}
}
2. 分析并运行以下各子程序的主要功能。
程序2链式存储的线性表和运算
#include
#include
struct node{
char data;
struct node *next;
};
typedef struct node NODE;
/*This function creates a link_list with N nodes.*/
NODE *create_link_list(int n)
{int i;
NODE *head, *p, *q;
if (n==0) return NULL;
head = (NODE *) malloc(sizeof(NODE));
p = head;
printf("Please input %d chars for the link list\n",n);
for (i=0; i
{scanf("%c ", &(p->data));
q=(NODE *)malloc(sizeof(NODE));
printf("test3\n");
p->next=q;
p=q;}
scanf("%c ",&(p->data));
getchar();
p->next=NULL;
return (head);}
/*This function inserts a node whose value is b*/
/*before the node whose value is a, if the node is not exist,*/
/*then insert it at the end of the list*/
void insert(NODE **p_head, char a, char b)
{NODE *p, *q;
q = (NODE *)malloc(sizeof(NODE));
q->data = b;
q->next =NULL;
if (* p_head == NULL) * p_head = q;
else
{p=(NODE*)malloc(sizeof(NODE));
p = * p_head;
while (p->data != a && p->next != NULL)
p = p->next;
q->next = p->next;
p->next = q;}
}
/*The function deletes the node whose value is a,*/
/*if success, return 0, or return 1*/
int deletenode(NODE **p_head, char a)
{NODE *p, *q;
q=*p_head;
if (q==NULL) return(1);
if (q->data == a)
{* p_head = q->next;
free(q);
return (0);}
else
{while (q->data != a && q->next != NULL)
{p = q;
q = q->next;}
if (q->data == a)
{p->next = q->next;
free(q);
return(0);}
else return(1);}
}
void main()
{ NODE *my_head,*p;
} /* create a link list with m nodes */ int m; char ch_a,ch_b; printf("please input the number of nodes for the link_list\nm="); scanf("%d",&m); getchar(); printf("test1\n"); my_head = (NODE *) malloc(sizeof(NODE)); my_head=create_link_list(m); /*Output the link list*/ printf("The link list is like:\n"); p=my_head; while (p != NULL) {printf("%c ",p->data); p=p->next; } printf("\n"); /*insert a node whose value is b before a*/ printf("Please input the position for a\n ch_a="); getchar(); scanf("%c",&ch_a); getchar(); printf("Please input the value that you want to insert\n ch_b="); scanf("%c",&ch_b); getchar(); insert(&my_head,ch_a,ch_b); printf("The link list after insertion is like:\n"); p=my_head; while (p != NULL) {printf("%c ",p->data); p=p->next; } printf("\n"); /*delete a node whose value is a*/ printf("Please input the position for a a="); scanf("%c",&ch_a); getchar(); deletenode(&my_head,ch_a); printf("The link list after deleting is like:\n"); p=my_head; while (p != NULL) {printf("%c ",p->data); p=p->next; } printf("\n");
3. 运行以下程序并分析各子函数的主要功能。
#include
#include
struct tagNode
{
int data;
struct tagNode *pNext;
};
typedef struct tagNode* pNode;
//将结点插入到链表的适当位置，这是一个降序排列的链表
//
void insertList(pNode head,//链表头结点
pNode pnode)//要插入的结点
{
pNode pPri=head;
while (pPri->pNext!=NULL)
{
if (pPri->pNext->datadata)
{
pnode->pNext=pPri->pNext;
pPri->pNext=pnode;
break;
}
pPri=pPri->pNext;
}
if (pPri->pNext==NULL)//如果要插入的结点最小
{
pPri->pNext=pnode;
}
}
//输出链表
void printLinkedList(pNode head)
{
pNode temp=head->pNext;
while (temp!=NULL)
{
printf("%d ",temp->data);
temp=temp->pNext;
}
}
//从链表中删除结点
void delformList(pNode head,int data)
{
pNode temp=head->pNext;
pNode pPri=head;
while (temp!=NULL)
{
if (temp->data==data)
{
pPri->pNext=temp->pNext;
free(temp);
break;
}
pPri=temp;
temp=temp->pNext;
}
}
void main()
{
pNode head=(pNode)malloc(sizeof(struct tagNode));//给头指针分配空间
pNode pTemp=NULL;
int temp;
head->pNext=NULL;//比较好的习惯就是分配好空间，马上赋值
printf("请输入要放入链表中的数据，以-1结尾：");
//读入数据，以-1结尾，把数据插入链表中
scanf("%d",&temp);
while (temp!=-1)
{
pTemp=(pNode)malloc(sizeof(struct tagNode));
pTemp->data=temp;
pTemp->pNext=NULL;
insertList(head,pTemp);
scanf("%d",&temp);
}
printf("降序排列的链表为：\n");
printLinkedList(head);
printf("\n");
//下面的代码当删除函数编写成功后，可以取消注释，让其执行,主要是调用函数实现链表结点的删除
//printf("请输入要删除数，以-1结尾：");
//scanf("%d",&temp);
//while (temp!=-1)
//{
// delformList(head,temp);
}
// scanf("%d",&temp); //} //printf("删除节点后，链表中剩余数据为："); //printLinkedList(head); //printf("\n");
四、思考与提高
试将以上链表改为有序表，并分析有序表有哪些显著的优点和缺点？ 库函数载和常量定义：（代码,C++）
#include
using namespace std;
const int MaxSize=100;
（1）顺序表存储结构的定义(类的声明)：（代码）
template //定义模板类SeqList
class SeqList
{
public:
SeqList( ); //无参构造函数
SeqList(datatype a[ ], int n); //有参构造函数
~SeqList(){}; //析构函数为空
int Length(); //求线性表的长度
datatype Get(int i); //按位查找，取线性表的第i个元素 int Locate(datatype item); //查找元素item
void Insert(int i, datatype item); //在第i个位置插入元素item datatype Delete(int i); //删除线性表的第i个元素 void display(); //遍历线性表，按序号依次输出各元素 private:
datatype data[MaxSize]; //存放数据元素的数组
int length; //线性表的长度
};
（2）初始化顺序表算法实现（不带参数的构造函数）
/*
*输 入：无
*前置条件：顺序表不存在
*功 能：构建一个顺序表
*输 出：无
*后置条件：表长为0
*/
实现代码：
template
SeqList:: SeqList( )
{
length=0;
}
（3）顺序表的建立算法（带参数的构造函数） /*
*输 入：顺序表信息的数组形式a[],顺序表长度n *前置条件：顺序表不存在
*功 能：将数组a[]中元素建为长度为n的顺序表 *输 出：无
*后置条件：构建一个顺序表
*/
实现代码：
template
SeqList:: SeqList(datatype a[], int n)
{
if (n>MaxSize)
{
cout
}
for (int i=0; i
data[i]=a[i];
length=n;
}（4）在顺序表的第i个位置前插入元素e算法 /*
*输 入：插入元素e,插入位置i
*前置条件：顺序表存在，i要合法
*功 能：将元素e插入到顺序表中位置i处 *输 出：无
*后置条件：顺序表插入新元素，表长加1
*/
实现代码：
template
void SeqList::Insert(int i, datatype item) {
int j;
if (length>=MaxSize)
{
cout
}
if (ilength+1)
{
cout
}
for (j=length; j>=i; j--)
data[j]=data[j-1];
data[i-1]=item;
length++;
}（5）删除线性表中第i个元素算法
/*
*输 入：要删除元素位置i
*前置条件：顺序表存在,i要合法
*功 能：删除顺序表中位置为i的元素
*输 出：无
*后置条件： 顺序表册除了一个元素，表长减1 */
实现代码：
template
datatype SeqList::Delete(int i)
{
int item,j;
if (length==0)
{
cout
if (ilength)
{
cout
}
item=data[i-1];//获得要删除的元素值
for (j=i; j
data[j-1]=data[j]; //注意数组下标从0记 length--;
return item;
}（6）遍历线性表元素算法
/*
*输 入：无
*前置条件：顺序表存在
*功 能：顺序表遍历
*输 出：输出所有元素
*后置条件：无
*/
实现代码：
template
void SeqList::display()
{
if(length==0)
{
cout
}
for(int i=0;i
{
cout
}
}
（7）获得线性表长度算法
/*
*输 入：无
*前置条件：顺序表存在
*功 能：输出顺序表长度
*输 出：顺序表长度
*后置条件：无
*/
实现代码：
template
int SeqList::Length()
{
return Length;
}
（8）在顺序线性表中查找e值，返回该元素的位序算法 /*
*输 入：查询元素值e
*前置条件：顺序表存在
*功 能：按值查找值的元素并输出位置
*输 出：查询元素的位置
*后置条件：无
*/
实现代码：
template
int SeqList::Locate(datatype item)
{
for (int i=0; i
if (data[i]==item)
return i+1 ;
//下标为i的元素等于item，返回其序号i+1 return 0; //查找失败
}
（9）获得顺序线性表第i个元素的值
/*
*输 入：查询元素位置i
*前置条件：顺序表存在，i要合法
*功 能：按位查找位置为i的元素并输出值 *输 出：查询元素的值
*后置条件：无
*/
实现代码：
template
datatype SeqList::Get(int i)
{
if (ilength)
{
cout
}
else return data[i-1];
}
（10）判表空算法
/*
*输 入：无
*前置条件：无
*功 能：判表是否为空
*输 出：为空返回1，不为空返回0
*后置条件：无
*/
实现代码：
template
bool SeqList::Empty()
{
if (length==0)
{
return 1;
}
else
{
return 0;
}
}
(11)求直接前驱结点算法
/*
*输 入：要查找的元素e，待存放前驱结点值e1
*前置条件：无
*功 能：查找该元素的所在位置，获得其前驱所在位置。
*输 出：返回其前驱结点的位序。
*后置条件：e1值为前驱结点的值
*/
实现代码：
template
int SeqList::Pre(datatype item)
{
int k=Locate(item)-1;
if (k>0)
return k;
else
{
cout
return 0;
}
}
(12)求直接后继结点算法
/*
*输 入：要查找的元素e，待存放后继结点值e1
*前置条件：无
*功 能：查找该元素的所在位置，获得其后继所在位置。
*输 出：返回其后继结点的位序。
*后置条件：e1值为后继结点的值
*/
实现代码：
template
int SeqList::Suc(datatype item)
{
int k=Locate(item)+1;
if (k>length)
{
cout
return 0;
}
else
{
return k;
}
}
上机实现以上基本操作，写出main()程序：
用以上基本操作算法，实现A=AUB算法。（利用函数模板实现）
/*
*输 入：集合A,集合B
*前置条件：无
*功 能：实现A=AUB
*输 出：无
*后置条件：A中添加了B中的元素。
*/
实现代码：
template
SeqList SeqList::Add(SeqList& item)
{
if (item.Empty())
return *this;
else
{
int k=item.Length();
int num=this->Length();
for (int i=1;i
{
for(int j=0;j
if (data[j]==item.Get(i))
{
break;
}
else if (num-1==j&&data[num-1]!=item.Get(i))
{
this->Insert(++num,item.Get(i));
}
}
return *this;
}
}
void main()
{
SeqList A,B;
cout
A.Insert(1,1);
A.Insert(2,2);
A.Insert(3,3);
A.Insert(4,4);
A.Insert(5,5); //插入集合A中元素
B.Insert(1,2);
B.Insert(2,6);
B.Insert(3,1);
B.Insert(4,8);
B.Insert(5,9); //插入集合B中元素
A.Add(B);
A.display();
cout
}
实现代码：
template
void SeqList::orderInsert(datatype item)
{
int num=this->Length();
for (int i=0;i
{
if ((data[i]item))
{
for (int k=num;k>i;k--)
data[k]=data[k-1];
data[i+1]=item;
length++;
break;
}
if (data[i]>item)
{
for(int k=num;k>i;k--)
data[k]=data[k-1];
data[i]=item;
length++;
break;
}
}
}
void main()
{
SeqList A,B;
A.Insert(1,3);
A.Insert(2,5);
A.Insert(3,6);
A.Insert(4,8);
A.Insert(5,10); //插入顺序表
cout
A.display(); //输出顺序表
cout
A.orderInsert(2);
A.orderInsert(4); //插入元素
cout
A.display(); //输出重新排序后的顺序表
}
算法实现：La,Lb为非递减的有序线性表，将其归并为Lc，该线性表仍有序（未考虑相同时删除一重复值）（利用函数类板实现）
MergeList：
/*
*输 入：有序线性表La,有序线性表Lb
*前置条件：顺序表已有序
*功 能：将两线性表归并，不去掉相同元素
*输 出： 返回一个新的有序线性表Lc
*后置条件：无
*/
实现代码：
template
SeqList SeqList::ElseAdd(SeqList Seq1,SeqList Seq2)
{
int num=Seq2.Length();
for(int i=0;i
Seq1.orderInsert(Seq2.Get(i));
}
return Seq1;
}
void main()
{
SeqList La,Lb,Lc;
La.Insert(1,2);
La.Insert(2,4);
La.Insert(3,6);
La.Insert(4,8); //插入La
cout
La.display(); //输出La
cout
Lb.Insert(1,3);
Lb.Insert(2,6);
} Lb.Insert(3,8); //插入Lb cout