课 程 设 计 报 告
课程名称： 数据结构
专业班级： 计算机辅修一班
学 号： 财大1309100108
姓 名： 徐倬迅
指导教师： 袁凌
报告日期： 2015、6、23
计算机科学与技术
目录
实验一 基于顺序结构的线性表实现 1
1.1问题描述 1
1.2系统设计 1
1.3.系统实现 2
1.4效率分析 5
实验二 基于链式结构的线性表实现 5
2.1问题描述 5
2.2系统设计 5
2.3系统实现 6
2.4效率分析 10
四 实验总结与评价 10
实验一 基于顺序结构的线性表实现
1.1问题描述
基于顺序存储结构，实现线性表的基本的、常见的运算。
1.2系统设计
1.2.1提供12个功能，分别是：
1. InitiaList
2. DestroyList
3. ClearList
4. ListEmpty
5. ListLength
6. GetElem
副食
7. LocatElem
8. PriorElem
9. NextElem
10. ListInrt
11. ListDelete
12. ListTrabver
lolly1.2.2物理结构为顺序存储结构，数据元素为包含一个整型变量的结构体：
typedef struct{
int item1;
}Elemtype;
有声书typedef struct{
Elemtype * elem;
int length;
int listsize;
}SqList;
1.2.3构建线性表之前先声明一个头结点，用于存储该表的基本信息和首结点地址：
SqList L1, L2;//声明头结点
1.2.4文件预处理
出版社英文
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1;
#define FALSE 0;
#define OK 2;
#define ERROR -1;
#define OVERFLOW -2;
typedef int status;
#define LIST_INIT_SIZE 100;
#define LISTINCREMENT 10;//预处理
1.3.系统实现
1.3.1 InitialList功能
初始化线性表，传入的是头结点地址。申请一个大小为LIST_INT_SIZE、类型为Elemtype的线性存储空间，并用头结点中的首结点指针指向该空间首地址。具体实现如下：
status IntiaList(SqList * L) {
L->elem = (Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype));
if(!L->elem)
exit(OVERFLOW);
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return OK;
}// IntiaList
上海演讲
1.3.2 DestroyList功能
销毁头结点中首结点址针指向的线性存储空间，传入的是头结点地址。具体实现如下：
status DestroyList(SqList * L){
if(L->elem != NULL)
{
free(L->elem);
po是什么意思
RetSqList(L);
}
el
return ERROR;
return OK;
}// DestroyList
1.3.3 ClearList功能
与Destroy类似但是又有不同，ClearList并不销毁物理空间，而是修改逻辑关系值：
status ClearList(SqList * L){
if(L->elem == NULL)
return ERROR;
L->length = 0;
return OK;//ClearList
1.3.4 ListEmpt功能
判空功能，判断表是否为空表。传入的是头结点值，而非地址，因为不需要对头结点进行修改。实现如下：
status ListEmpty(SqList L){diplomacy
if(L.elem == NULL)
return ERROR;
if(0 == L.length)
return TRUE;
el
return FALSE;//ListEmpty
1.3.5 ListLenth功能
求表长功能，由于创建过程中已经把表长信息包含在头结点中，所以直接调用并显示即可：
int ListLength(SqList L){
if(L.elem == NULL)
return ERROR;
return L.length;
}//ListLenth
1.3.6 GetElem功能
获取第i号元素，传入的是头结点值、元素编号i、以及出口表结点地址。
status GetElem(SqList L,int i,Elemtype * e){
if(i<1 || i>L.length)
return ERROR;
el{
*e=L.elem[i-1];
return OK;
}
}//GetElem
1.3.7 LocatElem功能
获取指定元素编号，传入头结点值、存储了所需元素信息的一个临时表结点值、equal函数地址。采用顺序比较法从表头遍历并比较，一旦找到，返回编号i。时间复杂度为,O(n)。
int LocatElem(SqList L,Elemtype e,status (* compare)(Elemtype ,Elemtype )){
if(L.elem==NULL)
return ERROR;
int i;
for(i=L.length i>0 i--)
{
if(compare(e,L.elem[i-1]))
return i;
}
return --i;
}//LocatElem
1.3.8 PriorElem功能
求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是先调用LocatElem确定指定元素的位置，如果不是首结点则可直接取到PriorElem的地址。时间复杂度为O(n)。具体实现如下：
status PriorElem(SqList L,Elemtype cur,Elemtype * pre_e){
if(L.elem==NULL)
return ERROR;
int i=LocatElem(L, cur, equal);
if(i<=1)
return ERROR;
el{
assignEle(pre_e,L.elem[i-2]);
return OK;
}
}//PriorElem
esntial
1.3.9 NextElem功能
status NextElem(SqList L,Elemtype cur,Elemtype * next_e){
if(L.elem==NULL)
return ERROR;
int i=LocatElem(L, cur, equal);
if(i==L.length && i==0)
return ERROR;
el{
assignEle(next_e,L.elem[i]);
return OK;
}
}//NextElem
1.3.10 ListInrt功能
插入一个数据元素，传入头结点地址、插入位置i、临时表结点值。在调用插入函数前构造一个临时表结点，用于存储数据元素信息。进入插入子函数，插入前先判断插入位置是否合理，再判断是否“满载”。如果满载则重新申请更大的存储空间。接下来正式插入数据元素，“先空位置再插入”。平均时间复杂度为 ，O(n)，n即listlenth。
bad boysstatus ListInrt(SqList * L,int i,Elemtype e){
if(i<1 || i>L->length+1)
return ERROR;
if(L->length >= L->listsize)nel
{
Elemtype *newba = (Elemtype *)realloc(L->elem, (L->listsize+LISTINCREMENT)*sizeof(Elemtype));
if(!newba)
exit(OVERFLOW);
L->elem = newba;
L->listsize += LISTINCREMENT;
}
Elemtype *inrt = &(L->elem[i-1]);
Elemtype *cur=&(L->elem[L->length-1]);
for( cur>=inrt cur--)
{
*(cur+1) = *cur;
}
*inrt = e;
++L->length;
return OK;
}//ListInrt
1.3.11 ListDelete功能
status ListDelete(SqList * L,int i,Elemtype * e){
if(i<1 || i>L->length)
return ERROR;
assignEle(e, L->elem[i-1]);
