内容发布更新时间 : 2024/11/13 8:59:44星期一 下面是文章的全部内容请认真阅读。

}

state=ListInsert(L,i,e); (head.data)++; }

else if (CH=='D') {

cout<<\删除第几个元素：\ //删除操作 cin>>i; cout<

printf(\输入数据：L=(%s) DeleteList(L,%d,e)\

state=ListDelete(L,i,e); (head.data)--; }

else goto AGAIN; //操作指示符输入错误处理 cout<

if(state==-1) cout<<\ //输出结果 cout<<\

for(int m=1;(head.data)>=m;m++) //一一输出数据 {

GetElem(L,m,f); cout<

cout<<\

if(CH=='D'&&state!=-1) cout<<\ //删除操作反馈e

实验结果：

由于两个程序的输出模式相同，在此只列一组测试数据： L = () ListInsert (L, 1, 'k')

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

- 6 -

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

L = () ListDelete (L, 1, e)

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

- 7 -

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()，主程序调用该函数并输出即可。

- 8 -

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; }

return 1; }

将q值返还给p - 9 -

//