线性表的基本操作.doc

实验二 线性表的基本操作
一、实验目的
1．掌握用 C++/C语言调试程序的基本方法。
2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等.
二、实验要求
1．C++/C完成算法设计和程序设计并上机调试通过.
2．撰写实验报告，提供实验结果和数据。
3． 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
三、实验内容:
1。 分析并运行以下各子程序的主要功能。
 程序1:顺序存储的线性表和运算
#include<stdio。h>
#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〈0 || 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〈0 |｜ i>=＊p_n） return(1)；
for （j = i+1; j〈=＊p_n； 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<=n； i++)
｛printf(”list［%d］=",i)；
scanf（”％d",＆list[i］)；｝

printf（”The list before insertion is\n”);
for (i=0; i<=n； i++） printf(”%d ",list［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〈=n; i++) printf（”%d ",list［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<=n； i++） printf（"%d ”,list[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<=n； i++) printf(”%d "，list［i］）;
printf（"\n”）；
printf（”％d"，n)；
break;
case 1:printf（"The deleting is not successful！"）；break;｝
｝
2。 分析并运行以下各子程序的主要功能.
程序2链式存储的线性表和运算
#include〈stdio。h〉
＃include〈malloc.h〉
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〈n； 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 〈stdio。h>
＃include <stdlib.h〉
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—〉data〈pnode->data)
｛
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〈iostream〉
using namespace std;
const int MaxSize=100；
（1）顺序表存储结构的定义(类的声明）：（代码)
template 〈class datatype〉 //定义模板类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 <class datatype〉
SeqList<datatype〉:: SeqList（ ）
｛
length=0;
}
（3）顺序表的建立算法(带参数的构造函数）
/＊
＊输 入：顺序表信息的数组形式a［],顺序表长度n
*前置条件：顺序表不存在
＊功 能：将数组a［］中元素建为长度为n的顺序表
＊输 出:无
＊后置条件:构建一个顺序表
*/
实现代码:
template 〈class datatype>
SeqList<datatype〉:： SeqList（datatype a［］， int n）
｛
if (n〉MaxSize）
{
cout〈〈”数组元素个数不合法”〈<endl;
}
for （int i=0； i〈n; i++）
data[i］=a[i]；
length=n；
｝(4)在顺序表的第i个位置前插入元素e算法
/＊
＊输 入：插入元素e,插入位置i
＊前置条件：顺序表存在,i要合法
*功 能:将元素e插入到顺序表中位置i处
*输 出：无
＊后置条件：顺序表插入新元素，表长加1
*/
实现代码：
template 〈class datatype>
void SeqList<datatype>:：Insert（int i， datatype item）
｛
int j；
if (length〉=MaxSize)
{
cout<〈”溢出”<<endl;
｝
if (i〈1 |｜ i〉length+1)
｛
cout〈〈”i不合法！"〈<endl；
}
for (j=length； j>=i； j——）
data[j]=data[j—1]；
data［i—1］=item;
length++；
｝（5）删除线性表中第i个元素算法
/＊
＊输 入:要删除元素位置i
*前置条件：顺序表存在,i要合法
*功 能：删除顺序表中位置为i的元素
*输 出：无
＊后置条件： 顺序表册除了一个元素，表长减1
*/
实现代码：
template <class datatype>
datatype SeqList〈datatype〉::Delete(int i)
｛
int item,j；
if （length==0）
{
cout<〈”表为空,无法删除元素！"〈〈endl；
｝
if (i<1 ｜｜ i>length）
{
cout<〈"i不合法！”<<endl;
}
item=data[i—1］；//获得要删除的元素值
for (j=i； j<length； j++）
data[j-1］=data［j］; //注意数组下标从0记
length-—;
return item;
}（6）遍历线性表元素算法
/＊
＊输 入:无
*前置条件:顺序表存在
＊功 能:顺序表遍历
＊输 出：输出所有元素
＊后置条件：无
＊/
实现代码:
template〈class datatype〉
void SeqList〈datatype〉::display（)
｛
if(length==0）
｛
cout<<”表为空，无法输出！”〈<endl;
}
for（int i=0；i<length；i++）
｛
cout<<data［i］<〈”　”;
｝
｝
（7)获得线性表长度算法
/*
*输 入:无
＊前置条件：顺序表存在
＊功 能：输出顺序表长度
*输 出：顺序表长度
＊后置条件：无
＊/
实现代码：
template <class datatype>
int SeqList〈datatype〉:：Length（)
{
return Length；
｝
（8）在顺序线性表中查找e值,返回该元素的位序算法
/*
*输 入：查询元素值e
＊前置条件:顺序表存在
＊功 能：按值查找值的元素并输出位置
*输 出：查询元素的位置
*后置条件：无
＊/
实现代码：
template 〈class datatype〉
int SeqList〈datatype〉:：Locate（datatype item）
｛
for （int i=0; i〈length； i++)
if （data[i］==item）
return i+1 ；
//下标为i的元素等于item，返回其序号i+1
return 0； //查找失败
｝
（9）获得顺序线性表第i个元素的值
/*
*输 入:查询元素位置i
＊前置条件：顺序表存在,i要合法
*功 能：按位查找位置为i的元素并输出值
＊输 出:查询元素的值
*后置条件：无
＊/
实现代码：
template 〈class datatype>
datatype SeqList<datatype>::Get（int i）
{
if （i〈0|｜i〉length)
｛
cout〈〈"i不合法!”<〈endl;
｝
else return data[i-1];
｝
（10）判表空算法
/*
*输 入：无
*前置条件：无
*功 能：判表是否为空
*输 出：为空返回1,不为空返回0
＊后置条件：无
*/
实现代码：
template 〈class datatype>
bool SeqList〈datatype〉::Empty（）
{
if (length==0）
｛
return 1;
｝
else
{
return 0;
}
}
（11)求直接前驱结点算法
/＊
*输 入：要查找的元素e，待存放前驱结点值e1
＊前置条件：无
*功 能：查找该元素的所在位置，获得其前驱所在位置.
*输 出：返回其前驱结点的位序。
*后置条件:e1值为前驱结点的值
＊/
实现代码：
template<class datatype>
int SeqList<datatype〉::Pre(datatype item)
{
int k=Locate(item)-1；
if (k>0)
return k；
else
{
cout<<”无前驱结点！"〈<endl;
return 0；
}
}
（12）求直接后继结点算法
/*
*输 入：要查找的元素e，待存放后继结点值e1
*前置条件：无
＊功 能：查找该元素的所在位置，获得其后继所在位置.
*输 出：返回其后继结点的位序。
＊后置条件：e1值为后继结点的值
＊/
实现代码:
template〈class datatype>
int SeqList〈datatype>：：Suc（datatype item)
｛
int k=Locate（item）+1；
if (k〉length)
｛
cout〈〈”无后继结点！”〈<endl;
return 0；
}
else
｛
return k;
}
｝
上机实现以上基本操作，写出main（)程序：
用以上基本操作算法，实现A=AUB算法。（利用函数模板实现）
/＊
＊输 入：集合A,集合B
*前置条件：无
＊功 能：实现A=AUB
*输 出：无
＊后置条件：A中添加了B中的元素。
*/
实现代码:
template〈class datatype>
SeqList〈datatype〉 SeqList<datatype>::Add（SeqList<datatype〉＆ item)
｛
if (item。Empty())
return ＊this；
else
｛
int k=item.Length（);
int num=this->Length（);
for （int i=1；i<=k；i++）
{
for（int j=0；j<num；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〈int〉 A，B；
cout<<"A∪B的结果是:”〈<endl；
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〈〈endl；
｝
实现代码：
template<class datatype〉
void SeqList<datatype>::orderInsert(datatype item）
｛
int num=this->Length(）;
for （int i=0；i<num;i++）
{
if (（data［i］〈item＆＆data[i+1］〉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<int〉 A,B；
A.Insert(1,3)；
A。Insert（2,5）；
A。Insert（3,6）；
A。Insert(4，8);
A。Insert(5,10）； //插入顺序表
cout〈〈”原顺序表为："<〈endl;
A.display(); //输出顺序表
cout〈〈endl;
A.orderInsert（2）；
A。orderInsert(4); //插入元素
cout〈<”插入新元素后的顺序表为:"<<endl；
A.display(）； //输出重新排序后的顺序表
｝
算法实现：La，Lb为非递减的有序线性表，将其归并为Lc，该线性表仍有序（未考虑相同时删除一重复值）（利用函数类板实现）
MergeList：
/＊
*输 入：有序线性表La，有序线性表Lb
*前置条件:顺序表已有序
*功 能：将两线性表归并,不去掉相同元素
*输 出： 返回一个新的有序线性表Lc
＊后置条件：无
＊/
实现代码:
template〈class datatype>
SeqList<datatype> SeqList<datatype>::ElseAdd(SeqList〈datatype〉 Seq1,SeqList〈datatype> Seq2)
｛
int num=Seq2。Length()；
for(int i=0;i<=num;i++)｛
Seq1.orderInsert（Seq2。Get(i）)；
}
return Seq1；
}
void main（)
{
SeqList〈int〉 La,Lb,Lc；
La。Insert(1，2)；
La。Insert(2，4）;
La.Insert（3，6)；
La。Insert（4,8)； //插入La
cout<〈"La中元素为:”〈〈endl;
La。display(）； //输出La
cout<〈endl；
Lb.Insert（1，3);
Lb。Insert(2,6);
Lb。Insert(3,8)； //插入Lb
cout〈<”Lb中元素为："〈〈endl;
Lb.display()； //输出Lb
cout〈〈endl；
Lc=Lc.ElseAdd（La，Lb)； //合并两线性表
cout<〈”合并后的Lc为:"〈<endl；
Lc。display（）； //输出合并后的线性表
cout<<endl；
｝