顺序表与单链表基本运算算法.doc

顺序表的基本运算实现
假设表中数据元素的值为整数;

#define MAX 100 //定义表最大长度容量,实际用不到那么多

//顺序表结构定义
typedef struct
{
int data[MAX]; //存放表结点
int length; //当前表长度
} SeqList;

//创建初始顺序表
SeqList *createList(int size)
{
int i;
SeqList *list;

list=(SeqList *)malloc(sizeof(SeqList)); //分配空间
printf("请输入顺序表中的整数,元素个数为%d\n",size);
for(i=0;i<size;i++)
scanf("%d",&list->data[i]) ; //逐一向顺序表中输入元素
list->length=size; //顺序表的长度赋值
return list;
}

//打印顺序表中的现有元素
printList(SeqList *list)
{

int i;
printf("\n目前顺序表中有%d个元素\n", list->length);
printf("这些元素分别是：\n");
for(i=0;i<list->length;i++)
printf("%d ",list->data[i]); //依次打印输出顺序表中的元素
printf("\n");
}

//在顺序表中查找值为e的元素,并返回它在表中的位置
Int locate(SeqList *list, int e)
{
int i=0;

while(i<list->length && list->data[i]!=e)
i++ ; //依次比较顺序表中各个元素
if(i<list->length) return i+1; //找到元素的处理
else printf("找不到元素!\n",); //未找到元素的处理
}

//在表中第i个元素之前插入新元素e
insert(SeqList *list, int i , int e)
{
int j;

if (i<1 || i>list->length+1 ) //检查插入位置的合法性
printf("插入位置非法！不能插入\n！");
else if (list->length==MAX)
printf("表满，不能插入！\n"); //检查表空满情况
else {for(j=list->length-1;j>=i-1;j--)
list->data[j+1]=list->data[j];
//从第n个元素开始到第i个元素依次向后移动一个位置
list->data[i-1]=e; //新元素e插入i位置
list->length++; //表长加1
}
}

//删除表中第i个元素
delete(SeqList *list, int i)
{
int j;
if (i<1 || i>list->length ) printf("删除位置非法！不能删除！\n");
//检查删除位置的合法性
else if (list->length==0) printf("表空，不能删除！\n"); //检查表空满情况
else
{for(j=i;j<=list->length;j++)
list->data[j-1]=list->data[j];
//从第i个元素开始到第n个元素依次向前移动一个位置
list->length--; //表长减1
}
}单链表的基本运算实现
以下算法都是带头结点的算法;
假设表中数据元素的值为整数;

//链表结点结构定义
typedef struct node
{
int data; //存放表结点值
struct node *next; //存放表结点的直接后驱元素的地址
} ListNode,*LinkList;

//头插法创建初始链表
LinkList create_h(int size)
{
LinkList head,p;
int i;

head=(LinkList)malloc(sizeof(ListNode));//申请头结点的存储空间
head->next=Null;//头结点的next域为Null

printf("请输入这%d个元素的值:\n",size);
for(i=0;i<size;i++) //将新增结点插入头结点之后
{
p=(LinkList)malloc(sizeof(ListNode));
scanf("%d",&p->data);
p->next=head->next;
head->next=p;
}
return head;
}

//尾插法创建初始链表
LinkList create_t(int size)
{
LinkList head,p,r;
int i;

head=(LinkList)malloc(sizeof(ListNode)); //申请头结点的存储空间
head->next=Null; //头结点的next域为Null
r=head;//尾指针指向头结点

printf("请输入这%d个元素的值:\n",size);
for(i=0;i<size;i++) //将新增结点插入到表尾
{
p=(LinkList)malloc(sizeof(ListNode));
scanf("%d",&p->data);
p->next=Null;
r->next=p;
r=p;//尾指针指向新增结点
} return head; }
//求链表的长度
int length(LinkList head)
{
LinkList p;
int i;

p=head->next;//工作指针指向表中第一个结点
i=0;//计数器置0

while(p!=Null)
{
i++;//计数器计数
p=p->next;//工作指针后移到下一个结点
}
return i;
}

//打印链表中的现有元素
printList(LinkList head)
{
LinkList p;

p=head->next;//工作指针指向表中第一个结点
while(p!=Null)
{
printf("%d ",p->data);//打印当前指针所指结点的值
p=p->next;//工作指针后移到下一个结点
}
}

//按位查找元素
DataType get(LinkList head ,int i)
{
LinkList p;
int j;

p=head->next; //工作指针指向表中第一个结点
j=1; //计数器置1
while(p!=Null && j<i)//定位第i个结点
{
p=p->next;
j++;
}
if(p!=Null && j==i) return p->data;//查找成功,p指向第i个结点,返回第i个结点值
else return Null;//i值非法,查找失败
}

//按值查找元素
LinkList locate(LinkList head,int x)
{
LinkList p;

p=head->next;
while(p!=Null && p->data!=x)
p=p->next;
if (p!=Null && p->data==x)
{printf("找到该元素!”);return p;}
else
{printf("找不到该元素!\n");return Null;}
}

//在链表中第i个元素前插入新元素
insert(LinkList head,int i,int x)
{
LinkList p,s;
int j;

p=head;//工作指针指向头结点,方便在第1个结点之前插入新元素
j=0;//计数器置0

while(p!=Null && j<i-1)//将p指针定位到第i个结点的直接前驱接点上
{
p=p->next;
j++;
}
if (p!=Null && j==i-1)//定位成功
{
s=(LinkList)malloc(sizeof(ListNode));//申请新结点存储空间
s->data=x;
s->next=p->next;//新结点插入
p->next=s;//新结点插入
}
Else//插入位置非法
printf("插入位置非法！\n");
}

//在链表中删除第i个结点元素
delete(LinkList head,int i)
{
LinkList p,q;
int j;

p=head; //工作指针指向头结点
j=0; //计数器置0

while(p->next!=Null && j<i-1)
//将p指针定位到第i个结点的直接前驱接点上;
{
p=p->next;
j++;
}
if(p->next!=Null && j==i-1)
{
q=p->next;//q指向要被删除的结点
p->next=q->next;//删除结点
free(q);//释放已被删除结点的存储空间
}
else
printf("空表或删除位置不合法！\n");
}