实验三-链表插入及删除算法.doc

实验三 链表的插入和删除算法
一． 实验目的：
通过上机编程实现线性表链式存储结构的插入和删除算法。
二． 实验要求：
1. 给出程序设计的基本思想、原理和算法描述。
2. 画出程序流程图；根据数据结构有关知识编出算法程序；
3. 源程序给出注释。
4. 保存和打印出程序的运行结果，并结合程序进行分析。
三． 实验内容：
1．编写函数实现链表的插入；
2．编写函数实现链表的删除；
3. 编写程序实现以下功能：
(1) 创建顺序栈:22,33,45,99,8;
(2) 调用插入函数，在表中第三个位置插入元素58；
（3调用删除函数,删除表中第四个位置的元素；
（4 输出最终链表中的元素。

#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType;
typedef struct
{ ElemType elem[MaxSize];
int length;
}SqList;
static SqList L;
void InitList() /* 初始化顺序表 */
{
L.length=0;
}

int ListEmpty() /* 判断顺序表是否为空 */
{ return(L.length== 0);
}

int ListLength() /* 求顺序表长度 */
{ return(L.length);
}

void DispList() /* 显示顺序表中所有元素 */
{ int i;
if(ListEmpty()) return;
for(i=0;i<L.length; i++)
printf("%c", L.elem[i]);
printf("\n");
}

int GetElem(int i, ElemType &e) /* 读取顺序表中的元素 */
{ if(i<1 || i>L.length)
return 0;
e=L.elem[i-1];
return 1;
}

int LocateElem(ElemType e) /* 确定顺序表中元素的位置 */
{ int i=0;
while(i<L.length && L.elem[i] != e) i++;
if(i>= L.length)
return 0;
else
return i+1;
}

int ListInsert( int i, ElemType e) /*插入*/
{ int j;
if(i<1 || i>L.length+1)
return 0;
i--;
for(j=L.length; j>i; j--)
L.elem[j]=L.elem[j-1];
L.elem[i]=e;
L.length++;
return 1;
}

int ListDelete( int i, ElemType &e) /* 删除 */
{ int j;
if(i<1 || i>L.length)
return 0;
i--;
e=L.elem[i];
for(j=i; j<L.length-1; j++)
L.elem[j]=L.elem[j+1];
L.length--;
return 1;
}

void main( )
{
ElemType e;

printf("(1)初始化顺序表L\n");
InitList();

printf("(2)依次采用尾插法插入a, b, c, d，e元素\n");
ListInsert(1,'a');
ListInsert(2,'b');
ListInsert(3,'c');
ListInsert(4,'d');
ListInsert(5,'e');

printf("(3)输出顺序表L:");
DispList();

printf("(4)顺序表L长度=%d\n",ListLength());

printf("(5)顺序表L为%s\n",(ListEmpty()?"空":"非空"));

GetElem( 3, e);
printf("(6)顺序表L的第3个元素=%c\n",e);

printf("(7)元素a的位置=%d\n",LocateElem('a'));

printf("(8)在第4个元素位置上插入f元素\n");
ListInsert( 4, 'f');

printf("(9)输出顺序表L:");
DispList();

printf("(10)删除L的第3个元素\n");
ListDelete(3, e);

printf("(11)输出顺序表L:");
DispList();

}