《线性表的基本操作解析.docx》由会员分享，可在线阅读，更多相关《线性表的基本操作解析.docx（13页珍藏版）》请在三一文库上搜索。
1、实验二 线性表的基本操作一、实验目的1掌握用 C+/C 语言调试程序的基本方法。2掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。二、实验要求1 C+/C 完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。三、实验内容：1. 分析并运行以下各子程序的主要功能。程序 1 ：顺序存储的线性表和运算#include#define MAXSIZE 100int listMAXSIZE;int n;/*insert in a seqlist*/int sq_insert(
2、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; ji; j-)listj=listj-1;listi=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=*p_n; j+)listj-1 = listj;(*p_n)-;return(0)
3、;void main()int i,x,temp;printf(please input the number for nn);printf(n=);scanf(%d,&n);for (i=0; i=n; i+)printf(list%d=,i);scanf(%d,&listi);printf(The list before insertion isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to insert a valuenposition
4、=);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 isn);for(i=0; i=n; i+) printf(%d ,listi);printf(n);printf(%dn,n);break;1. se 1:case 2:printf(The
5、insertion is not successful!n);break;/*deleting*/printf(The list before deleting isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to delete a valuenposition=);scanf(%d,&i);temp=sq_delete(list,&n,i);switch(temp)case 0:printf(The deleting is successfu
6、l!n);printf(The list is after deleting isn);for(i=0; i=n; i+) printf(%d ,listi);printf(n);printf(%d,n);break;case 1:printf(The deleting is not successful!);break;2. 分析并运行以下各子程序的主要功能。程序 2 链式存储的线性表和运算#include#includestruct nodechar data;struct node *next;typedef struct node NODE;/*This function create
7、s 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 listn,n);for (i=0; idata);q=(NODE *)malloc(sizeof(NODE);printf(test3n);p-next=q;p=q;scanf(%c ,&(p-data);getch
8、ar();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_h
9、ead = NULL) * p_head = q;elsep=(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=N
10、ULL) return(1);if (q-data = a)* p_head = q-next;free(q);return (0);elsewhile (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
11、number of nodes for the link_listnm=);scanf(%d,&m);getchar();printf(test1n);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 bef
12、ore a*/printf(Please input the position for an ch_a=);getchar();scanf(%c,&ch_a);getchar();printf(Please input the value that you want to insertn 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
13、=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 s
14、truct tagNodeint 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=NUL
15、L)/ 如果要插入的结点最小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);
16、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
17、=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( 删除节点后，链表中剩余数据为： );/printL
18、inkedList(head);/printf(n);四、思考与提高试将以上链表改为有序表，并分析有序表有哪些显著的优点和缺点？库函数载和常量定义： (代码 ,C+ )#includeusing namespace std;const int MaxSize=100;( 1 )顺序表存储结构的定义(类的声明)： (代码)template /定义模板类SeqListclass SeqListpublic:SeqList( );/ 无参构造函数SeqList(datatype a , int n);/ 有参构造函数SeqList();/析构函数为空int Length();/ 求线性表的长度dat
19、atype Get(int i);/ 按位查找，取线性表的第i 个元素int Locate(datatype item); / 查找元素 itemvoid Insert(int i, datatype item); / 在第 i 个位置插入元素itemdatatype Delete(int i);/删除线性表的第i 个元素void display();/遍历线性表，按序号依次输出各元素private:datatype dataMaxSize;/存放数据元素的数组int length;/线性表的长度;( 2 )初始化顺序表算法实现(不带参数的构造函数)/* 输入：无* 前置条件：顺序表不存在*
20、功能：构建一个顺序表* 输出：无* 后置条件：表长为0*/实现代码：template SeqList: SeqList( )length=0;( 3 )顺序表的建立算法(带参数的构造函数)/* 输入：顺序表信息的数组形式a, 顺序表长度n* 前置条件：顺序表不存在* 功能：将数组a 中元素建为长度为 n 的顺序表* 输出：无* 后置条件：构建一个顺序表*/实现代码：template SeqList: SeqList(datatype a, int n)if (nMaxSize)cout 数组元素个数不合法endl;for (int i=0; in; i+) datai=ai;length=n;
21、 ( 4 )在顺序表的第i 个位置前插入元素e 算法/* 输入：插入元素e,插入位置i* 前置条件：顺序表存在，i 要合法* 功能：将元素e 插入到顺序表中位置 i 处* 输出：无* 后置条件：顺序表插入新元素，表长加1*/实现代码：template void SeqList:Insert(int i, datatype item)int j;if (length=MaxSize) cout 溢出 endl;if (ilength+1) couti 不合法！ =i; j-)dataj=dataj-1;datai-1=item;length+; ( 5 )删除线性表中第i 个元素算法/* 输入：
22、要删除元素位置i* 前置条件：顺序表存在,i 要合法* 功能：删除顺序表中位置为i 的元素* 输出：无* 后置条件：顺序表册除了一个元素，表长减1*/实现代码：template datatype SeqList:Delete(int i)int item,j;if (length=0)cout 表为空 ,无法删除元素!endl;if (ilength)couti 不合法 !endl;item=datai-1;/ 获得要删除的元素值for (j=i; jlength; j+)dataj-1=dataj;/注意数组下标从0 记length-;return item; ( 6 )遍历线性表元素算法/
23、* 输入：无* 前置条件：顺序表存在* 功能：顺序表遍历* 输出：输出所有元素* 后置条件：无*/实现代码：templatevoid SeqList:display()if(length=0)cout 表为空，无法输出 !endl;for(int i=0;ilength;i+)coutdatai ;( 7 )获得线性表长度算法/* 输入：无* 前置条件：顺序表存在* 功能：输出顺序表长度* 输出：顺序表长度* 后置条件：无* /实现代码：template int SeqList:Length()return Length;（ 8 ）在顺序线性表中查找e 值，返回该元素的位序算法/* 输入：查询
24、元素值e* 前置条件：顺序表存在* 功能：按值查找值的元素并输出位置* 输出：查询元素的位置* 后置条件：无* /实现代码：template int SeqList:Locate(datatype item)i+1for (int i=0; ilength; i+) if (datai=item) return i+1 ;/下标为i 的元素等于item ，返回其序号return 0;/查找失败( 9 )获得顺序线性表第 i 个元素的值/* 输入：查询元素位置i* 前置条件：顺序表存在，i 要合法* 功能：按位查找位置为i 的元素并输出值* 输出：查询元素的值* 后置条件：无* /实现代码：te
25、mplate datatype SeqList:Get(int i)if (ilength)couti 不合法 !endl;else return datai-1;( 10 )判表空算法/* 输入：无* 前置条件：无* 功能：判表是否为空* 输出：为空返回1 ，不为空返回 0* 后置条件：无* /实现代码：template bool SeqList:Empty()if (length=0)return 1;elsereturn 0;(11) 求直接前驱结点算法 /*输 前置条件：无 功 输*入：要查找的元素e,待存放前驱结点值 el置条件：无能：查找该元素的所在位置，获得其前驱所在位置。出：返
26、回其前驱结点的位序。* 后置条件： e1 值为前驱结点的值*/实现代码：templateint SeqList:Pre(datatype item)int k=Locate(item)-1;if (k0)return k;elsecout 无前驱结点！ endl;return 0;(12) 求直接后继结点算法/* 输入：要查找的元素e,待存放后继结点值el* 前置条件：无* 功能：查找该元素的所在位置，获得其后继所在位置。* 输出：返回其后继结点的位序。* 后置条件：e1 值为后继结点的值*/实现代码：templateint SeqList:Suc(datatype item)int k=Lo
27、cate(item)+1;if (klength)cout 无后继结点 !endl;return 0;elsereturn k;上机实现以上基本操作，写出 main() 程序：用以上基本操作算法，实现A=AUB 算法。 (利用函数模板实现)/* 输入：集合A, 集合B* 前置条件：无* 功能：实现A=AUB* 输出：无* 后置条件：A 中添加了 B 中的元素。*/实现代码：templateSeqList SeqList:Add(SeqList& item) if (item.Empty()return *this;elseint k=item.Length();int num=this-Len
28、gth();for (int i=1;i=k;i+)for(int j=0;jInsert(+num,item.Get(i);return *this;void main()SeqList A,B;coutA U 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(
29、);coutendl;实现代码：templatevoid SeqList:orderInsert(datatype item)int num=this-Length();for (int i=0;inum;i+)if (dataiitem)for (int k=num;ki;k-)datak=datak-1;datai+1=item;length+;break;if (dataiitem)for(int k=num;ki;k-)datak=datak-1;datai=item;length+;break;void main()SeqList A,B;A.Insert(1,3);A.Insert
30、(2,5);A.Insert(3,6);A.Insert(4,8);A.Insert(5,10);/插入顺序表cout 原顺序表为:endl;A.display();/输出顺序表coutendl;A.orderInsert(2);A.orderInsert(4); /插入元素cout插入新元素后的顺序表为：endl;A.display();/输出重新排序后的顺序表算法实现： La,Lb 为非递减的有序线性表，将其归并为 Lc ，该线性表仍有序(未考虑相同时删除一重复值) (利用函数类板实现)MergeList ：/* 输入：有序线性表La,有序线性表Lb* 前置条件：顺序表已有序* 功能：将两
31、线性表归并，不去掉相同元素* 输出：返回一个新的有序线性表Lc* 后置条件：无*/实现代码：templateSeqList SeqList:ElseAdd(SeqList Seq1,SeqListSeq2)int num=Seq2.Length();for(int i=0;i=num;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); /插入 LacoutLa 中元素为 :endl;La.display();/输出Lacoutendl;Lb.Insert(1,3);Lb.Insert(2,6);Lb.Insert(3,8);/插入LbcoutLb 中元素为 :endl;Lb.display();/输出Lbcoutendl;Lc=Lc.ElseAdd(La,Lb); / 合并两线性表 cout 合并后的Lc 为 :endl;Lc.display();/输出合并后的线性表coutendl;