线性表的顺序表示与实现 |flying0033
http://hi.csdn.net/attachment/201112/20/0_1324350552d5iN.gif /* 线性表是有N个元素的非空有限序列 存在惟一的一个被称作“第一个”数据的元素 存在惟一的一个被称作“第后一个”数据的元素 除第一个与最后一个之外,其它元素都存在唯一的一个前驱和唯一的一个后续 复杂的线性表中的元素可以由多个数据项组成 同一个线性表中的元素类型必须相同 线性表的顺序表,是用一组地址连续的存储单元依次存储线性表的数据元素 算法复杂度:取表长与访问表中的的元素为O(1)，插入与删除的时间复杂度为O(n) 顺序表适用于频繁访问,只有较少（或不进行)“插入删除操作” */#ifndef SQLIST_H
#define SQLIST_H
#define MAXSIZE100 //顺序表的最大存储容量
#define INFINITY 65535 //设置为β
typedef int ElemType;//顺序表的数据类型,自定义
typedef struct {
ElemType data; //定义一个顺序表,大小为MAXSIZE
int len; //顺序表的当前长度
}SqList;
void InitList(SqList *q); //初始化顺序表
void GetElem(SqList *q,int i,ElemType *e); //返回元素,将第i个位置的元素存入*e
void GetListLength(SqList *q,int *len); //返回顺序表的长度,将长度存入*len
void InsertList(SqList *q,int i,ElemType e); //在第i个位置插入e,最坏的情况下i为第一个位置,时间复杂度为O(n)
void DeleteList(SqList *q,int i,ElemType *e); //删除第i个位置的元素,将删除的元素存入*e,最坏情况i为第一个位置
//时间复杂度为O(n)
int LocateElem(SqList *q,ElemType e); //在顺序表中查找元素e是否存在,不存在返回-1，否则返回所在的位置
#endif //SQLIST_H
#include "SqList.h"
#include <stdio.h>
#include <string.h>
void InitList(SqList *q) //初始化顺序表
{
memset(q->data,0,sizeof(ElemType) * MAXSIZE); //初始化顺序表的元素为0
q->len = 0; //初始化顺序表的当前大小为0
}
void GetElem(SqList *q,int i,ElemType *e) //获取第i个位置的元素(下标值从零开始,i个位置的元素在表中位置为i-1)
{
if(i > 0 && i <= q->len) //如果i存在于顺序表中
*e = q->data; //返回第i个位置的元素
else
*e = INFINITY; //返回β值
}
void InsertList(SqList *q,int i,ElemType e) //在顺序表的第i个位置插入元素e
{
if(i > MAXSIZE || i <= 0)
{
printf("超出范围,元素插入失败\n");
return;
}
for(int j = q->len - 1;j >= i - 1;--j)//将i个位置与i之后的所有元素向后移一位(下标值从零开始i - 1)
q->data = q->data;
q->data = e; //将元素插入到顺序表中,下标值从零开始
++q->len; //增加当前顺序表的长度值
}
void DeleteList(SqList *q,int i,ElemType *e) //将顺序表中第i个位置的元素删除,将删除的元素存入*e
{
if(i <= 0 && i > q->len)
{
printf("超出范围,元素删除失败\n");
*e = INFINITY; //返回β值
return;
}
*e = q->data;
for(int j = i - 1;j < q->len - 1;++j) //第i个位置之后的所有元素向后移
q->data = q->data;
--q->len; //当前的顺序表长度减1
}
int LocateElem(SqList *q,ElemType e) //在顺序表中查找元素e,如果找到返回位置,否则返回-1
{
for(int i = 0;i < q->len;++i)
{
if(q->data == e)
return i + 1; //下标从0开始，所以要加上1
}
return -1;
}
#include "SqList.h"
#include <stdio.h>
int main()
{
SqList q;
InitList(&q); //初始化顺序表
int element;
int i = 1; //插入的位置
printf("请输入要插入顺序表中的内容:(CTRL + Z)结束\n");
while((scanf("%d",&element)) != EOF)
{
InsertList(&q,i,element);
++i;
}
i = 2; //第顺序表的第2个位置插入元素
fflush(stdin); //清空缓冲区,确保输入正确
printf("请输入要在第2个位置插入的元素\n");
scanf("%d",&element);
InsertList(&q,i,element);
printf("顺序表的内容为:\n");
for(int j = 0;j < q.len;++j)
printf("%d ",q.data);
printf("\n");
int e; //用于存入被删除的元素
printf("请输入要删除的元素的位置\n");
fflush(stdin);
scanf("%d",&i);
DeleteList(&q,i,&e);
printf("被删除的元素为:%d\n",e);
printf("顺序表的内容为:\n");
for(int j = 0;j < q.len;++j)
printf("%d ",q.data);
printf("\n");
printf("请输入要在表中查找的元素:\n");
fflush(stdin);
scanf("%d",&element);
if((i = LocateElem(&q,element)) == -1)
printf("顺序表中不存在元素:%d\n",element);
else
printf("在顺序表的第%d个位置找到元素:%d\n",i,element);
return 0;
}
http://hi.csdn.net/attachment/201112/20/0_1324350552d5iN.gif
作者：flying0033 发表于2011-12-20 11:06:41 原文链接
页:
[1]