数据结构-线性表的C语⾔实现相关代码
本博客内的源码⽂件已上传,只要5积分,需要⾃取
顺序表
注意:
构建顺序表的时候,只能⽤malloc分配内存⽽不能⽤new,
因为new分配的内存空间不⼀定是连续的,⽽malloc是连续的,
顺序存储要求逻辑上相邻的元素在物理上的存储单元也是相邻的。
如果使⽤new也能得到相同的结果但是在存储结构上并不符合
代码部分:
参考了
#include<iostream>//cout等输⼊输出流头⽂件
#include<stdio.h>//scanf(), printf(),gets() 等函数的的头⽂件
using namespace std;//保证在程序中可以直接使⽤std命名空间中的成员,原本⽤法是std::xxxx的,现在就可以直接输xxxx了. //顺序表的定义
#define Size 5 //对Size进⾏宏定义,表⽰顺序表申请空间的⼤⼩
typedef struct Table {
int*head;//定义⼀个指向int类型地址的指针、声明了⼀个名为head的长度不确定的数组,也叫“动态数组”
//注意,head 是我们声明的⼀个未初始化的动态数组,不要只把它看做是普通的指针。
int length;//表的长度
int size;//记录顺序表分配的存储容量
}table;//将Table类型重新定义为table
//初始化顺序表
table initTable(){
table t;
t.head =(int*)malloc(Size *sizeof(int));//构造⼀个空的顺序表,动态申请存储空间
/*t.head = new int[5];*/
if(!t.head)//如果申请失败,作出提⽰并直接退出程序
{
printf("初始化失败");
exit(0);
}
t.length =0;//空表的长度初始化为0
t.size = Size;//空表的初始存储空间为Size
return t;
}
//输出顺序表中元素的函数
void displayTable(table t){
for(int i =0; i < t.length; i++){
printf("%d ", t.head[i]);
}
molloc函数printf("\n");
}
int main(){
table t =initTable();
/
/向顺序表中添加元素
for(int i =1; i <= Size; i++){
t.head[i -1]= i;
t.length++;
}
printf("顺序表中存储的元素分别是:\n");
displayTable(t);
return0;
}
输出结果如下:
顺序表的插⼊、删除
顺序表的插⼊算法:
注意insertTable⾥⾯不能直接使⽤insertTable(table t, int i,int data)
需要加上&,声明引⽤,否则修改之后的成员值不能返回到主调函数
//顺序表的插⼊算法
void insertTable(table &t,int i,int data)
{
//判断i的范围是否有效,否则⾮法
if(i > t.length){
printf("插⼊位置⽆效,请重新选择有效位置插⼊");
}
else{
if(t.length == t.size){
//判断当前存储空间是否已满,否则不能插⼊
printf("当前顺序表已满,⽆法插⼊");
}
else{
//进⾏数据的插⼊
for(int m = t.size; m >= i; m--){//将第i个位置以及其后的元素往后移动
t.head[m]= t.head[m -1];
}
t.head[i -1]= data;//在第i个位置插⼊数据
t.length++;//表的长度+1
}
}
}
顺序表的删除算法(另⼀种传参⽅式):
table *p =&t;
delteTable(p,2);
//顺序表的删除算法
void delteTable(table *t,int i){
//判断i的范围是否有效,否则⾮法
if(i > t->length){
printf("插⼊位置⽆效,请重新选择有效位置插⼊");
}
else{
for(int m = i; m < t->length; m++){
t->head[m -1]= t->head[m];
}
t->length--;
}
}
单链表
学习资料:
链表的数据位置不要求连续,
请求分配内存的时候可以使⽤new,如果是C++的话,
C语⾔只能⽤malloc,因为C语⾔没有new这个操作符
链表中每个数据的存储都由以下两部分组成: 1. 数据元素本⾝,其所在的区域称为数据域; 2. 指向直接后继元素的指针,所在的区域称为指针域;
即链表中存储各数据元素的结构如下图 所⽰:
上图 所⽰的结构在链表中称为节点。也就是说,链表实际存储的是⼀个⼀个的节点,真正的数据元素包含在这些节点中,如下图 所⽰:
定义单链表:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 10            /*宏定义SIZE为10*/
//定义单链表
typedef struct single_Linked_Lists {
int data;/*data为数据域*/
struct list *next;/*指针域,指针指向直接后继元素*/
}list;/*定义single_Linked_Lists为link*/
/*定义全局头尾节点*/
list *head =NULL;
list *end =NULL;
由于指针域中的指针要指向的也是⼀个节点,因此要声明为 list类型(这⾥要写成 struct list*的形式)
另外,可以看到除了结构体的定义外,还声明了头结点和尾结点
头结点的数据域可以不设任何信息,也可以记录表长等相关信息。
头结点的指针域指向线性表的第⼀个元素结点。
头结点和头指针的区分:
不管带不带头结点,头指针始终指向链表的第⼀个结点,⽽头结点是带头指针的链表中的第⼀个结点,其内通常不设置任何信息所以链表中有头节点时,头指针指向头节点;反之,若链表中没有头节点,则头指针指向⾸元节点。
头结点带来的优点:
1. 由于开始结点的位置被存放在头结点的指针域中,所以在链表的第⼀个位置上的操作和在表的其他位置上的操作并⽆区别,⽆需进⾏特殊处理
2. ⽆论链表是否为空,它的头指针都是指向头结点的⾮空指针(空表中的头结点的指针域为空),因此空表和⾮空表的处理也就统⼀了
链表的建⽴:
参考博客:
头插法:
核⼼思路:
1. 新插⼊的结点的指针指向原来的⾸元结点
2. 头结点的指针指向新插⼊的结点
/
/头插法建⽴单链表{1,2,3,4,5}
void ListInitHead(list *l){
l->next =NULL;
for(int i =1; i<=5; i++){
list *s =(list*)malloc(sizeof(list));
if(s ==NULL){
printf("malloc error!");
exit(0);
}
else
{
/
*给要插⼊的结点赋值*/
s->data = i;
s->next = l->next;
l->next = s;
}
}
}
打印输出结果:
尾插法:
头插法虽然简单,但是读⼊数据的顺序与⽣成链表中元素的顺序是相反的,若我们希望读⼊数据的顺序和⽣成链表中的元素顺序保持⼀致,就可以使⽤尾插法
为此增加⼀个尾指针r,使其始终指向当前链表的尾结点
核⼼思路:
1. 原链表中的尾结点(r原本指向)指向要插⼊的结点
2. r指向新的表尾结点

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。