线性表的建立

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业线性表的建立、插入和删除班级 ：计科021 姓名：罗晶晶 学号： 日期：2005/4/25实验题目：1、建立一个顺序存储的线性表，实现线性表的插入、删除操作2、建立一个单链表，实现单链表的插入、删除操作运行环境 ：visual C+需求分析程序的功能：（1）建立一个按关键字有序的线性表，从键盘上输入一个数，将该数插入到表中，使该线性表插入数据后仍按关键字有序。（2）建立一个线性表，从键盘上输入一个数，查找表中是否存在该数，若有则删除所有与该数相等的数。测试数据：顺序存储

2、的线性表：已建立一个有序的线性表为：请输入要插入的数据：插入数据后的顺序表为：请输入要删除的数据：删除后的顺序表为：单链表：请输入记录，输入0则结束：1 2 0现在链表中的2个记录是：1 2请输入要插入的记录：1现在链表中的3个记录是：1 1 2 0请输入要删除的数据：1删除了：1现在链表中的2个记录是：1 2概要设计顺序表的抽象数据类型的定义：ADT List 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2, . . . ，a

3、i，. . . ，an), 称 i 为 ai 在线性表中的位序。基本操作：InitList( &L )操作结果：构造一个空的线性表L。DestroyList( &L )初始条件：线性表 L 已存在。操作结果：销毁线性表 L。ListEmpty( L )初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength( L )初始条件：线性表L已存在。操作结果：返回L中元素个数。GetElem( L, i, &e )初始条件：线性表L已存在，且 1iLengthList(L)。操作结果：用 e 返回L中第 i 个元素的值。LocateElem( L, e, c

4、ompare( ) )初始条件：线性表L已存在，e为给定值，compare( )是元素判定函数。操作结果：返回L中第1个与e满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L, visit( )初始条件：线性表L已存在，Visit() 为某个访问函数。操作结果：依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。ListInsert( &L, i, e )初始条件：线性表L已存在，且 1iLengthList(L)+1 。操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,

5、i, &e)初始条件：线性表L已存在且非空，1iLengthList(L) 。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。 ADT List详细设计采用c语言定义相关的数据类型；#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct int *elem; int length; int listsize; SQLIST;其中部分操作的伪码算法如下：void Create(SQLIST &L) /建立线性表L.elem =(int*)malloc(LIST_INIT_SIZE* sizeof(int);

6、if(!L.elem)printf(为线性表分配空间失败!);L.length =0;L.listsize =LIST_INIT_SIZE;void Insert(SQLIST &A,int x) /实现有序的插入操作if(A.length =A.listsize) printf(线性表错误!);if(x A.elemA.length-1)A.elemA.length=x; elseint i=0;while(x = A.elemi) i+; for(int j=A.length; j=i; j-)A.elemj+1=A.elemj; A.elemi=x; A.length+; void li

7、stdelete(SQLIST &L,int x) /实现有序的删除操作int i=0;if(L.length=0) coutERRORendl;while(i=L.length)if(L.elemi=x) for(int j=i+1;j=L.length-1;+j) L.elemj-1=L.elemj; L.length-;elsei+;3、#include#includetypedef struct student /单链表的存储结构 long num;struct student* next;LINK;调试分析调试中遇到的问题及对问题的解决方法:在线性表中删除一个元数时，要判断是否有重复

8、的数据，有重复的话就要全部删除，解决的方法是写一个判断的for语句。算法的时间复杂度和空间复杂度。在长度为n的顺序表中插入一个元数的时间复杂度为0（n），删除一个元数的时间复杂度为0（n）测试结果顺序存储的线性表单链表源程序（带注释）1、顺序表的操作程序#include#include#include#include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct int *elem; int length; int listsize; SQLIST;void Create(SQLIST &L) /建立线性表

9、L.elem =(int*)malloc(LIST_INIT_SIZE* sizeof(int);if(!L.elem)printf(为线性表分配空间失败!);L.length =0;L.listsize =LIST_INIT_SIZE;void Insert(SQLIST &A,int x) /实现有序的插入操作if(A.length =A.listsize) printf(线性表错误!);if(x A.elemA.length-1)A.elemA.length=x; elseint i=0;while(x = A.elemi) i+; for(int j=A.length; j=i; j-

10、)A.elemj+1=A.elemj; A.elemi=x; A.length+; void listdelete(SQLIST &L,int x) /实现有序的删除操作int i=0;if(L.length=0) coutERRORendl;while(i=L.length)if(L.elemi=x) for(int j=i+1;j=L.length-1;+j) L.elemj-1=L.elemj; L.length-;elsei+; coutnOKn删除后的顺序表为:nendl;void main()SQLIST s;Create(s); s.elem0=1; s.elem1=3;s.el

11、em2=3;s.elem3=4;s.elem4=9;s.length=5;printf(nn-顺序表为-n);printf(nn已建立的顺序表为:n);for(int i=0; is.length; i+) printf(%d ,s.elemi); printf(nn请输入要插入的数据:n);int tmp;scanf(%d,&tmp);Insert(s,tmp);printf(nn插入数据后的顺序表为:n);for(i=0; ij; listdelete(s,j);for(int t=0; ts.length; t+)printf(%d ,s.elemt);getch(); 2、单链表表的操

12、作程序#include#includetypedef struct student /单链表的存储结构long num;struct student* next;LINK;int n; /定义一个全局变量(链表的结点个数)LINK* Create() /建立LINK* head;LINK* p1,*p2;n=0;p1=p2=(LINK*)malloc(sizeof(LINK); scanf(%ld,&p1-num);head=NULL;while(p1-num !=0)n=n+1;if(n=1)head=p1;else /p1指向新开的结点,p2指向链表中的最后一个结点p2-next=p1;

13、/把p1所指的结点连在p2所指结点的后面p2=p1; /p2指向链表中的最后一个结点p1=(LINK*)malloc(sizeof(LINK);scanf(%ld,&p1-num);p2-next=NULL;return head;LINK* Insert(LINK *head,LINK *stud) /插入LINK *p0,*p1,*p2;p1=head; /p1指向第一个结点p0=stud; /p0指向待插入的结点if(head=NULL)head=p0; p0-next=NULL;elsewhile(p0-num = p1-num) & (p1-next !=NULL)p2=p1; /p

14、2指向p1刚才所指的结点p1=p1-next;if(p0-num num)if(head=p1) head=p0;elsep2-next=p0;p0-next=p1;elsep1-next=p0;p0-next=NULL;n=n+1;return head;LINK* Delete(LINK*head,long num) /删除LINK *p1,*p2;if(head=NULL)printf(链表为空!nn);return(head);p1=head; / p1指向第一个结点while(num !=p1-num & p1-next !=NULL) /如果要删除的不是第一个接点，p2=p1; /

15、将p1赋给p2，使p2指向刚才检查过的结点p1=p1-next; /p1指向下一个结点if(num=p1-num) /如果删除的是第一个结点if(p1=head)head=p1-next; /head指向原来的第2个结点elsep2-next=p1-next;printf(删除了:%ld,num);n=n-1;elseprintf(没有找到%ld,num);return(head);void print(LINK *head) /输出LINK* p;printf(n现在链表中的%1d个记录是:n,n);p=head;if(head !=NULL)doprintf(%ld n,p-num);p=p-next;while(p!=NULL);void main()printf(n-单链表的操作-nn);LINK *head,*stu;long Delete_num;printf(请输入记录,输入0则结束:nn);head=Create(); /建立操作print(head);printf(请输入要插入的记录:n); /插入操作stu=(LINK*)malloc(sizeof(LINK);scanf(%1d,&stu-num);while(stu-num !=0)head=Inser