《线性表的基本操作.doc》由会员分享，可在线阅读，更多相关《线性表的基本操作.doc（12页珍藏版）》请在三一文库上搜索。
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_inser
2、t(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)-;retur
3、n(0);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 valuenpo
4、sition=); 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;case 1:case 2:
5、printf(The 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
6、is successful!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#include struct nodechar data;struct node *next; typedef struct node NODE; /*T
7、his 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 listn,n); for (i=0; idata); q=(NODE *)malloc(sizeof(NODE);printf(test3n); p-next=q; p=q
8、;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)
9、;q-data = b; q-next =NULL;if (* p_head = 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
10、, 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); 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 */ i
11、nt m;char ch_a,ch_b; printf(please input the 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=
12、p-next; printf(n);/*insert a node whose value is b before 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
13、 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
14、-data); p=p-next; printf(n);3. 运行以下程序并分析各子函数的主要功能。#include #include struct 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-pNex
15、t=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=h
16、ead;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(
17、%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 (t
18、emp!=-1)/ delformList(head,temp);/ scanf(%d,&temp);/printf( 删除节点后，链表中剩余数据为： );/printLinkedList(head);/printf(n);四、思考与提高试将以上链表改为有序表，并分析有序表有哪些显著的优点和缺点 库函数载和常量定义： （代码 ,C+）#include using namespace std; const int MaxSize=100;(1) 顺序表存储结构的定义 (类的声明 )：(代码) template / 定义模板类 SeqListclass SeqListpublic:SeqList(
19、 ); / 无参构造函数SeqList(datatype a , int n);/ 有参构造函数SeqList(); / 析构函数为空int Length(); / 求线性表的长度datatype Get(int i);/ 按位查找，取线性表的第 i 个元素int Locate(datatype item); / 查找元素 itemvoid Insert(int i, datatype item); / 在第 i 个位置插入元素 item datatype Delete(int i); / 删除线性表的第 i 个元素 void display();/ 遍历线性表，按序号依次输出各元素priva
20、te:datatype dataMaxSize; / 存放数据元素的数组int length; / 线性表的长度;（2）初始化顺序表算法实现（不带参数的构造函数） /* 输入：无*前置条件：顺序表不存在* 功能：构建一个顺序表* 输出：无* 后置条件：表长为 0*/实现代码：template SeqList: SeqList（ ）length=0;（3）顺序表的建立算法（带参数的构造函数）/* 输入：顺序表信息的数组形式 a, 顺序表长度 n*前置条件：顺序表不存在*功能：将数组 a 中元素建为长度为 n 的顺序表* 输出：无*后置条件：构建一个顺序表*/实现代码：template SeqLi
21、st: SeqList（datatype a, int n）if (nMaxSize) cout 数组元素个数不合法 endl;for (int i=0; in; i+) datai=ai;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溢
22、出endl;if (ilength+1) couti 不合法！ =i; j-) dataj=dataj-1;datai-1=item; length+; (5)删除线性表中第i个元素算法/*输入：要删除元素位置 i*前置条件：顺序表存在 ,i 要合法 *功能：删除顺序表中位置为i 的元素*输出：无*后置条件：顺序表册除了一个元素，表长减 1*/实现代码： template datatype SeqList:Delete(int i)int item,j;if (length=0) cout 表为空 ,无法删除元素 !endl;if (ilength) couti 不合法 !endl;item=
23、datai-1;/ 获得要删除的元素值 for (j=i; jlength; j+)dataj-1=dataj; / 注意数组下标从 0 记 length-;return item;(6)遍历线性表元素算法/* 输入：无*前置条件：顺序表存在* 功能：顺序表遍历* 输出：输出所有元素*后置条件：无*/ 实现代码： template void SeqList:display() if(length=0)cout 表为空，无法输出 !endl; for(int i=0;ilength;i+) coutdatai ;(7) 获得线性表长度算法/* 输入：无*前置条件：顺序表存在* 功能：输出顺序表长
24、度* 输出：顺序表长度*后置条件：无*/ 实现代码： template int SeqList:Length() return Length;(8) 在顺序线性表中查找 e 值，返回该元素的位序算法 /* 输入：查询元素值 e*前置条件：顺序表存在* 功能：按值查找值的元素并输出位置* 输出：查询元素的位置*后置条件：无*/实现代码：template int SeqList:Locate(datatype item)for (int i=0; ilength; i+)if (datai=item)return i+1 ;i+1/ 下标为 i 的元素等于 item ，返回其序号 return 0
25、; / 查找失败(9) 获得顺序线性表第 i 个元素的值/* 输入：查询元素位置 i*前置条件：顺序表存在， i 要合法* 功能：按位查找位置为 i 的元素并输出值* 输出：查询元素的值*后置条件：无*/实现代码：template datatype SeqList:Get(int i)if (ilength)couti 不合法 !endl;else return datai-1;(10) 判表空算法/* 输入：无*前置条件：无* 功能：判表是否为空* 输出：为空返回 1，不为空返回 0*后置条件：无*/ 实现代码： template bool SeqList:Empty()if (length
26、=0) return 1;else return 0;(11) 求直接前驱结点算法/*输入：要查找的元素 e,待存放前驱结点值 el* 前置条件：无*功能：查找该元素的所在位置,获得其前驱所在位置。*输出：返回其前驱结点的位序。*后置条件： e1 值为前驱结点的值*/实现代码：templateint SeqList:Pre(datatype item)int k=Locate(item)-1;if (k0)return k;elsecout 无前驱结点！ endl;return 0;(12) 求直接后继结点算法/*输入：要查找的元素 e,待存放后继结点值 el* 前置条件：无*功能：查找该元素
27、的所在位置,获得其后继所在位置。*输出：返回其后继结点的位序。*后置条件： e1 值为后继结点的值 */实现代码： template int SeqList:Suc(datatype item)int k=Locate(item)+1;if (klength)cout 无后继结点 !endl;return 0;elsereturn k;上机实现以上基本操作,写出 main() 程序： 用以上基本操作算法,实现 A=AUB 算法。(利用函数模板实现) /*输 入：集合A,集合B* 前置条件：无* 功能：实现 A=AUB* 输出：无* 后置条件： A 中添加了 B 中的元素。*/实现代码：temp
28、lateSeqList SeqList:Add(SeqList& item) if ()return *this;elseint k=();int num=this-Length();for (int i=1;i=k;i+)for(int j=0;jInsert(+num,(i);return *this;void main()SeqList A,B;coutA U B 的结果是:endl;(1,1) ;(2,2) ;(3,3) ;(4,4) ;(5.5) ;插入集合A中元素(1,2) ;(2.6) ;(3,1) ;(4,8) ;(5,9) ;插入集合B中元素(B);();coutendl;实
29、现代码：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;(1,3) ;(2,5);(3,6) ;(4,8) ;(5,10
30、) ; / 插入顺序表 cout 原顺序表为 :endl;(); / 输出顺序表 coutendl;(2);(4); / 插入元素cout 插入新元素后的顺序表为:endl;(); / 输出重新排序后的顺序表算法实现：La,Lb为非递减的有序线性表，将其归并为Lc,该线性表仍有序(未考虑相同时删除一重复值) (利用函数类板实现)MergeList ：/*输入：有序线性表La 有序线性表Lb* 前置条件：顺序表已有序*功能：将两线性表归并，不去掉相同元素* 输出： 返回一个新的有序线性表 Lc* 后置条件：无*/实现代码：templateclass datatypeSeqList SeqList
31、:ElseAdd(SeqList Seq1,SeqList Seq2) int num=();for(int i=0;i=num;i+)(i);return Seq1;void main()SeqList La,Lb,Lc;(1,2) ;(2,4) ;(3,6) ;(4.8) ;/ 插入 LacoutLa 中元素为 :endl;();/输出 Lacoutendl;(1,3) ;(2,6) ;(3.8) ;/插入 LbcoutLb 中元素为 :endl;();/输出 Lbcoutendl;Lc=(La,Lb); /合并两线性表 cout合并后的 Lc为:endl;();/输出合并后的线性表coutendl;