线性表的基本操作.docx

1、线性表的基本操作实验二线性表的基本操作一、实验目的1掌握用C+/C语言调试程序的基本方法。2掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。二、实验要求1C+/C完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。三、实验内容：1.分析并运行以下各子程序的主要功能。程序1：顺序存储的线性表和运算#include#define MAXSIZE 100int listMAXSIZE;int n;/*insert in a seqlist*/int sq_insert(i

2、nt 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

3、)-; return(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 t

4、o insert a valuenposition=); 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,

5、n); break; case 1: case 2: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

6、(temp) case 0:printf(The deleting 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#includestruct node char data; struct node *

7、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 listn,n); for (i=0; idata); q=(NODE *)malloc(sizeo

8、f(NODE); printf(test3n); 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,

9、 *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,

10、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

11、*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_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:

12、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 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(); inser

13、t(&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 afte

14、r 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=

15、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; /从链表中删除结

16、点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=NUL

17、L;/比较好的习惯就是分配好空间，马上赋值 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);/下面的代码当删除函数编写成功后，可以取消

18、注释，让其执行,主要是调用函数实现链表结点的删除/printf(请输入要删除数，以-1结尾：);/scanf(%d,&temp); /while (temp!=-1)/ delformList(head,temp);/ scanf(%d,&temp);/printf(删除节点后，链表中剩余数据为：);/printLinkedList(head);/printf(n);四、思考与提高试将以上链表改为有序表，并分析有序表有哪些显著的优点和缺点？库函数载和常量定义：（代码,C+）#includeusing namespace std;const int MaxSize=100;（1）顺序表存储结构的

19、定义(类的声明)：（代码）template /定义模板类SeqListclass SeqListpublic: 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

20、 i); /删除线性表的第i个元素 void display(); /遍历线性表，按序号依次输出各元素private: datatype dataMaxSize; /存放数据元素的数组 int length; /线性表的长度;（2）初始化顺序表算法实现（不带参数的构造函数）/*输入：无*前置条件：顺序表不存在*功能：构建一个顺序表*输出：无*后置条件：表长为0*/实现代码：template SeqList: SeqList( ) length=0;（3）顺序表的建立算法（带参数的构造函数）/*输入：顺序表信息的数组形式a,顺序表长度n*前置条件：顺序表不存在*功能：将数组a中元素建为长度为n的

21、顺序表*输出：无*后置条件：构建一个顺序表*/实现代码：template SeqList: 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)

22、 int j; if (length=MaxSize) cout溢出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 (ileng

23、th) couti不合法!endl; item=datai-1;/获得要删除的元素值 for (j=i; jlength; j+) dataj-1=dataj; /注意数组下标从0记 length-; return item;（6）遍历线性表元素算法/*输入：无*前置条件：顺序表存在*功能：顺序表遍历*输出：输出所有元素*后置条件：无*/实现代码：templatevoid 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的元素等于item，返回其序号i+1 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=0) return 1; else

26、 return 0; (11)求直接前驱结点算法/*输入：要查找的元素e，待存放前驱结点值e1*前置条件：无*功能：查找该元素的所在位置，获得其前驱所在位置。*输出：返回其前驱结点的位序。*后置条件：e1值为前驱结点的值*/实现代码：templateint SeqList:Pre(datatype item) int k=Locate(item)-1; if (k0) return k; else cout无前驱结点！endl; return 0; (12)求直接后继结点算法/*输入：要查找的元素e，待存放后继结点值e1*前置条件：无*功能：查找该元素的所在位置，获得其后继所在位置。*输出：返回其后继结点的位序。*后置条件：e1值为后继结点