数据结构导论 四 线性表的顺序存储VS链式存储
2024-08-31 08:56:25
前几章已经介绍到了顺序存储、链式存储
顺序存储:初始化、插入、删除、定位
链式存储:初始化、插入、删除、定位
顺序存储:初始化
strudt student{
int ID;//ID
char name[30];//姓名
char sex; //性别
int class;//班级
int age;//年龄 }
student={"01",“zhangsan”,"m","201","20"};
链式存储:初始化
//建立一个空链表
LinkList InitiateLinkList(){
LinkList head; //头指针
head =malloc (sizeof(node)); //动态构建一节点,它是头结点
head->next=null;
return head;
顺序存储:插入
void InsertSeqlist(SeqList ,DataType x,int i){
//将元素x插入到顺序表中L的第i个数据元素之前
if(L.length==Maxsize)
exit("表已满");
if(i<||i>L.ength+)
exit("位置错误");
for(j=L.length;j>=i;j--) //初始化
L.data[j]=L.data[j-];//依次后移
L.data[j-]=x;//元素x到下标为i-1的位置
L.length++;//表长度加1 }
链式存储:插入
void InsertLinklist (LinkList head, DataType x, int i)
//在表head的第i个数据元素结点之前插入一个以x为值的新结点
{
Node *p,*q;
if (i==) q=head;
else q=GetLinklist (head, i-); //找第 i-1个数据元素结点
if (q==NULL) //第i-1个结点不存在
exit(“找不到插入的位置”);
else
{
p=malloc(sizeof (Node) );p->data=x; //生成新结点
p->next=q->next; //新结点链域指向*q的后继结点
q->next=p; //修改*q的链域
}
}
顺序存储的插入i是先将插入后面的往后移动插入i-1个位置,空出插入的地方在进行插入
链式存储:插入结点d,先将d的尾结点连接到b的首结点,接着d的首结点连接a的尾结点,放弃a到b之间的连接
顺序存储:删除
void DeleteSeqList(SeqList L,int i) {
//删除线性表L中的第i个数据结点
if(i< || i>L.length) //检查位置是否合法
exit(“非法位置”);
for(j=i;j<L.length;j ++) //第i个元素的下标为i-1
L.data[j-]=L.data[j]; //依次左移
L.length--; //表长度减1
}
链式存储:删除
void DeleteLinklist(LinkList head, int i)
//删除表head的第i个结点
{
Node *q;
if(i==) q=head;
else q=GetLinklist(head, i-); //先找待删结点的直接前驱
if(q !== NULL && q->next != NULL) //若直接前驱存在且待删结点存在
{
p=q->next; //p指向待删结点
q->next=p->next; //移出待删结点
free(p); //释放已移出结点p的空间
}
else exit (“找不到要删除的结点”); //结点不存在
}
数据存储:定位
int LocateSeqlist(SeqList L, DataType x)
{
int i=;
while ((i<L. length) && (L.data[i]!=x) ) //在顺序表中查找值为 x 的结点
i++;
if(i<L.length) return i+; //若找到值为x的元素,返回元素的序号
else return ; //未查找到值为x的元素,返回0
}
//顺序表的求表长操作,直接输出L.length即可
链式存储:定位
int LocateLinklist (LinkList head ,Data Type x){
//求表head中第一个值等于x的结点的序号,若不存在这种结点,返回结果为0
Node *p=head;//p是工作指针
p=p->next;//初始时P指向首结点
int i=;//i代表 结点的序号,这里初值为
while(p!=null&&p->data!=x){//访问链表
i++;
p=p->next;
}
if(p!=null)
return i+;
else return ;}
最新文章
- Roguelike 相关知识
- def文件格式
- php练习题:投票
- USB Packet Types
- windows phone 新手引导
- Java应用程序实现屏幕的";拍照";
- 2016ACM竞赛训练暑期课期末考试 a题
- Core MVC
- 怎样在 SSASserver之间做同步
- Tsung记录
- Java多线程高并发学习笔记(三)——深入理解线程池
- disptch_after 自递归
- The component and implementation of a basic gradient descent in python
- jeecg中vaildfrom的复杂的表单校验
- topcoder srm 440 div1
- OpenJudge 求重要逆序对数
- linux-ubuntu 下R无法安装rjava模块的原因及解决方案
- postgresql----几何类型和函数
- Linux的账号口令机制及其爆破
- qt中 中文乱码问题