数据结构课程设计《单链表》.doc

文档介绍：课题设计:顺序线性表
一、设计目的

、插入、删除等基本操作的算法实现
3. 掌握线性表动态分配的顺序存储结构
二、设计内容和要求
利用malloc函数来建立表长为n(其值从键盘输入)顺序表,并能用算法实现该顺序表的插入、删除、查找、求某个元素的前驱和后继、把此顺序表逆置、从小到大排序,同时要求在屏幕上显示每次操作的结果,当所有操作完成后能撤消该顺序表
三、实验步骤
(一)顺序线性表的建立和显示
1、顺序线性表的存储结构特点及有关概念
线性表的顺序存储指的是用内存中一批地址连续的存储单元依次存储线性表中的数据元素。它的特点是线性表中相邻的元素在内存中的存储位置也是相邻的。由于线性表中的所有数据元素属于同一类型,所以每个元素在存储器中所占的空间大小相同。线性表的顺序存储结构可定义为:
typedef struct
{
ELEMTP elem[MAXSIZE]; /*存储线性表中的元素*/
int len; /*线性表的当前表长*/
}SqList;
线性表是n(n≥0)个数据元素组成的有限序列。一般记作:
L=( a1,a2,…,ai,…,an) 
表中的元素可以是一个数,一个符号或是由多个数据项组成的复杂信息,但同一线性表中的元素必须属于同一数据对象。。
2、线性表的基本操作
(1)InitList(L); 建立一个空的线性表L; (2)GetElem(L,i); 取线性表L中的第i个元素; (3)Length(L); 求线性表L的长度;
(4)Locate(L,x); 确定元素x在线性表L中位置;
(5)Insert(L,i,x); 在线性表L中第i个元素之前(或之后)插入一个新元素x;
(6)Delete(L,i); 删除线性表L中的第i个元素;
3、顺序存储结构过程及示意图
在图1中, 假设第一个元素存放的位置为b,每个元素占用的空间大小为L,则元素ai的存放位置为:
LOC(ai)=b十L*(i-1) 
图1 线性表的顺序存储结构示意图
(二)算法设计的思想分析
1、插入的算法与分析
插入时首先将线性表中原来元素ai,ai+1,... ,an从an起依次向后移动一个位置,然后在位置i上插入新元素x。
在实现操作时,还应注意对插入位置的合理性、表是否已满等特殊情况的处理。
算法:
int Insert_Sq (SqList *L ,int i, ELEMTP x)
/* 在线性表的第i-1和第i元素之间插入一个新元素x*/
{ if (i<1 || i>L->len+1) return 0; /* 不合理的插入位置 i */
if ( L->len== MAXSIZE-1) return -1; /* 表已满*/
for (j=L->len;j>=i;--j)
L->elem[j+1]=L->elem[j]; /* 插入位置及之后的元素右移*/
L->elem[i]=x; /*插入x */
++L->len; /*表长加1 */
return 1;
} /* Insert_Sq */
插入

原来长度为n的线性表(a1,...,ai-1,ai,..., an)变成长度为n-1的线性表(a1,...,ai-1,ai,...,an-1)。
算法:               
int Delete_Sq (SqList *L ,int i )
/* 删除线性表中第个i元素*/
{ if (i<1 || i>L->len) return 0; /*不合理的删除位置 i */
if (L->len==0) return -1; /* 表已空*/
for (j=i
;j<=L->len-1;j++)
L->elem[j]=L->elem[j+1]; /*被删除元素之后的元素左移*/
--L->len; /*表长减1*/
return 1;
}/* Delete_Sq */
删除
从插入和删除算法可见,当在顺序存储结构的线性表中某个位置上插入或删除一个元素时,其时间主要耗费在移动元素上,而移动元素的个数取决于插入或删除元素的位置。
假设pi是在第i个元素之前插入一个元素的概率,则在长度为n的线性表中插入一个元素时所需移动元素次数的平均次数为:
假设qi是删除第i个元素的概率,则在长度为n的线性表中删除一个元素时所需移动元素次数的平均次数为:
如果在表的任何位置上插入或删除元素的概率相等,即:
   
那么:
可见,在顺序存储结构的线性表中插入或删除一个元素时,平均约移动表中的一半元素,若表长为n,则上述算法的时间复