数据结构实验(1)线性表及其应用.doc

计算机系数据结构实验报告（1）

实验目的：
帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。
问题描述：
1、 构造一个空的线性表L。
2、 在线性表L的第i个元素之前插入新的元素e；
3、 在线性表L中删除第i个元素，并用e返回其值。
实验要求：文法是一个四元

1、 分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。
2、 在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。
算法分析：
由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下：

实验内容和过程：
顺序存储结构线性表程序清单：
//顺序存储结构线性表的插入删除
#include <iostream>
#include <stdlib.h>
using namespace std;

# define LISTSIZE 100
# define CREMENTSIZE 10

typedef char ElemType; //定义数据元素类型为字符型
typedef struct {
ElemType *elem; //数据元素首地址
int len; //当前元素个数
int listsize; //当前存储最大容量
}SqList;

//构造一个空的线性表L
int InitList(SqList &L)
{
L.elem=(ElemType *)malloc(LISTSIZE*sizeof(ElemType));
if (!L.elem) exit(-2); //分配空间失败
L.len=0;
L.listsize=LISTSIZE;
}

//在顺序线性表L中第i个位置之前插入新的元素e
int ListInsert(SqList &L,int i,ElemType e)
{
if (i<1||i>L.len+1) return -1; //i值不合法
if (L.len>=L.listsize)
{
ElemType *newelem=(ElemType *)realloc(L.elem,(L.listsize+CREMENTSIZE)*sizeof(ElemType));
//存储空间已满，增加分配
if(!newelem) exit (-2); //分配失败
L.elem=newelem;
L.listsize+=CREMENTSIZE;
}
ElemType *q=&(L.elem[i-1]) ;
for (ElemType *p=&(L.elem[L.len-1]);p>=q;--p) *(p+1)=*p; //插入位置及其后的元素后移
*q=e; ++L.len;
return 1;
}

//在顺序线性表L中删除第i个元素，并用e返回其值
int ListDelete(SqList &L,int i,ElemType&e)
{
if (i<1||i>L.len) return -1; //i值不合法
ElemType *p=&(L.elem[i-1]);
e=*p; ElemType*q=L.elem+L.len-1;
for (++p;p<=q+1;++p) *(p-1)=*p; //被删除元素之后的元素前移
--L.len;
return 1;
}

int main ()
{
SqList L; char e,ch;
int i,j,state;
InitList(L); //构造线性表
printf("请输入原始数据(字符串个数0~99)：L="); //数据初始化
gets(L.elem);
for ( j=1;L.elem[j-1]!='\0';j++) L.len=j; //获取表长L.len
L.elem[j]='\0';
printf("操作：插入（I）还是删除(D)?\n"); //判断进行插入还是删除操作
AGAIN:
cin>>ch;
if(ch=='I')
{
cout<<"插在第几个元素之前:"; //插入操作
cin>>i; cout<<"输入要插入的新元素:";
cin>>e;
cout<<endl;
printf("输入数据：L=(%s) ListInsert(L,%d,%c)",L.elem,i,e);
state=ListInsert (L,i,e);
}
else if (ch=='D')
{
cout<<"删除第几个元素："; //删除操作
cin>>i;
cout<<endl;
printf("输入数据：L=(%s) DeleteList(L,%d,e)",L.elem,i);
state=ListDelete(L,i,e);
}
else goto AGAIN; //操作指示符输入错误处理
cout<<endl<<"正确结果：";
if(state==-1) cout<<"ERROR,";
printf("L=(%s) ",L.elem); //输出结果
if(ch=='D'&&state!=-1) cout<<",e="<<e;
}
链式存储结构线性表程序清单：
// - - - - -单链存储结构线性表的插入删除 - - - - -
#include <iostream>
#include <stdlib.h>
using namespace std;

#define null 0

typedef char ElemType; //定义数据元素类型为字符型
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;

int GetElem(LinkList L,int i,ElemType &e) //获取第i个元素的值
{
LinkList p;int j;
p=L->next; j=1;
while(p&&j<i)
{
p=p->next; ++j; //寻找第i个元素
}
if(!p||j>i) return -1; //寻找失败
e=p->data;
return 1;
}

int ListInsert(LinkList &L,int i,ElemType e)
{
//在带头结点的单链线性表L中第i个元素之前插入元素e
LinkList p,s; int j;
p=L;j=0;
while(p&&j<i-1) {p=p->next;++j;}
if(!p||j>i-1) return -1;
s=(LinkList) malloc( sizeof(LNode));
s->data=e;s->next=p->next;
p->next=s;
return 1;
}

int ListDelete(LinkList&L,int i,ElemType&e)
{
//在带头结点的单链线性表L中,删除第i个元素，并由e返回其值
LinkList p,q; int j;
p=L;j=0;
while(p->next&&j<i-1)
{
p=p->next;++j;
}
if(!(p->next)||j>i-1) return -1;
q=p->next;p->next=q->next;
e=q->data;free(q);
return 1;
}

int newdata(LinkList&L,char *ch)
{

int k;
printf("请输入原始数据(字符串个数0~99)：L="); //数据初始化
gets(ch);
for (k=0;ch[k]!='\0';k++) ListInsert(L,k+1, ch[k]); //将初始化数据插入链表L中
cout<<"OK"<<endl;
return k; //返回链表中的元素个数
}

int main ()
{
char *ch;
ch=(char *)malloc(100*sizeof(char)); //定义数组用来辅助数据初始化
LinkList L; //头指针
LNode head; //头结点
L=&head; head.next=null;
int i,k,state; char e,CH,f;
k=newdata(L,ch); //调用函数使链表数据初始化
head.data=k; //将元素个数存入头结点的数据域
printf("操作：插入（I）还是删除(D)\n"); //判断进行插入还是删除操作
AGAIN:
cin>>CH;
if(CH=='I')
{
cout<<"插在第几个元素之前:"; //插入操作
cin>>i; cout<<"输入要插入的新元素:";
cin>>e;
cout<<endl;
printf("输入数据：L=(%s) ListInsert(L,%d,%c)",ch,i,e);
state=ListInsert(L,i,e);
(head.data)++;
}
else if (CH=='D')
{
cout<<"删除第几个元素："; //删除操作
cin>>i;
cout<<endl;
printf("输入数据：L=(%s) DeleteList(L,%d,e)",ch,i);
state=ListDelete(L,i,e);
(head.data)--;
}
else goto AGAIN; //操作指示符输入错误处理
cout<<endl<<"正确结果：";
if(state==-1) cout<<"ERROR,"; //输出结果
cout<<"L=(";
for(int m=1;(head.data)>=m;m++) //一一输出数据
{
GetElem(L,m,f);
cout<<f;
}
cout<<")";
if(CH=='D'&&state!=-1) cout<<",e="<<e; //删除操作反馈e
}
实验结果：
由于两个程序的输出模式相同，在此只列一组测试数据：
L = () ListInsert (L, 1, 'k')

L = (EHIKMOP) ListInsert (L, 9, 't')

L = (ABCEHKNPQTU) ListInsert(L, 4, 'u')

L = () ListDelete (L, 1, e)
L = (DEFILMNORU) ListDelete_Sq(L, 5, e)

L = (CD) ListDelete_Sq(L, 1, e)

测试过程中所注意到的问题主要还是输出与输入界面的问题，通过灵活使用cout和cin函数来不断改进。另外，在用户端看来在设计算法时程序的可重复性未考虑，显得不够人性化。
时间复杂度分析：
假定线性表有n个节点，顺序存储结构下，插入程序段以*(p+1)=*p作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记T(n)=O(n)；删除程序段以*(p-1)=*(p)作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记T’(n)=O(n)。链式存储结构下，插入程序段以p=p->next作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记T(n)=O(n);删除程序段以p=p->next作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记T’(n)=O(n)。
总结和感想：
改进设想在于减少中间变量，优化数据初始化操作，和增加程序可重复性。具体操作完成估计就该把上述程序全面修改了，还包括算法的修改和增进。
从完成该实验的过程中，出现的问题很多，一方面由于对C语言的不够熟悉，在语法和语句执行效率上总是不尽人意，另一方面由于在设计算法时考虑不全面，在后来写入程序时屡屡修改，使程序设计效率大大降低。基于上述两点，今后需全面复习C语言以效后计，并做好在设计算法方面的工作。
思考题：
实现链表的逆置算法：
以上述链式存储结构线性表程序做基础，可省略数据初始化和输入输出等操作，此处只列出实现逆置的用户函数Inversion()，主程序调用该函数并输出即可。

int Inversion(LNode head) //形参为链表的头结点
{
LinkList p,q,r;
p=head.next; q=r=0; //p中存放第一个节点的地址
while(p)
{
q=p->next; //q作为中间变量
p->next=r; //逆序替换元素的地址域
r=p;
p=q; //将q值返还给p
}
return 1;
}

- 9 -